歐陽暉，張俊前

(1.重慶市勘測院，重慶 401121； 2.重慶市地理國情監(jiān)測工程技術研究中心，重慶 401121)

?

高分辨率遙感影像圓特征提取算法研究

歐陽暉1，2*，張俊前1，2

(1.重慶市勘測院，重慶 401121； 2.重慶市地理國情監(jiān)測工程技術研究中心，重慶 401121)

高分辨率遙感影像的圓特征提取廣泛應用于攝影測量中，其精度高低對相機標定和特殊目標監(jiān)測有著重大的影響。在實際應用中，圓特征提取的精度高低主要取決于所使用的圓特征提取算法。本文研究總結了重心法、中心收縮法和基于邊緣跟蹤的最小二乘圓擬合算法等常用的圓特征提取算法的原理和實現(xiàn)步驟，并根據(jù)實驗數(shù)據(jù)的比較分析，給出了這3種常用圓特征提取算法各自的優(yōu)缺點和適用情況。最后，提出并實現(xiàn)了一種基于邊緣二次跟蹤的雙圓檢測算法，解決了由成像目標缺損引起的提取圓心位置偏差的問題。

圓特征提取；二值化；雙圓檢測

1 引 言

特征提取是模式識別和計算機視覺的重要內容，它是對圖像進行進一步分析的重要基礎。因為圓具有同向擴散性，相對于方形或十字形目標靶能很好地降低攝影測量誤差，因而被廣泛用于攝影測量中。如相機定標中采用圓形柵格形式的標定靶標，二維運動測量中也常以圓斑作為標記物。在這些應用中，圓的中心定位精度對測量精度和相機定標精度都有著至關重要的影響。因此圓特征提取方法的研究，對模式識別及攝影測量具有重大意義。

常用的圓特征提取算法有重心法、Hough變換法、圓擬合算法和中心收縮法?？妆热酸槍χ匦姆?、Hough變換法等在檢測精度和速度上的不足，提出了一種基于圓擬合的激光光斑中心檢測算法，根據(jù)最小二乘原理用圓來逼近激光光斑輪廓，從而提取光斑中心和半徑[1]；朱桂英等對經典Hough變換算法、隨機Hough變換算算法及廣義Hough變換算法進行了總結，并提出了一種改進的Hough變換應用于圓檢測，檢測速度有所提高[2]；霍建亮等人提出了一種利用最小二乘法迭代修正隨機圓檢測的改進算法，對圓局部信息缺損和噪聲具有很好的魯棒性[3]；李婷等提出結合Blob分析和最小二乘法實現(xiàn)對圓形物體的自動檢測，提高了檢測的準確性和檢測的效率[4]；Chung等分析了影響隨機圓檢測算法速度和精度的因素，提出了采樣策略和校準策略，使用梯度編碼約束隨機采樣和利用了圓直徑特性校準初次檢測結果，同時提升了速度和精度[5]；劉好龍等分析了重心法、Hough變換法、圓擬合算法的圓特征提取應用中的局限性，提出了一種提高圓擬合精度的一種方法[6]；陳珂等針對現(xiàn)有圓檢測算法運算復雜度高，難以達到復雜自然場景中的實時檢測要求的問題，提出一種利用一維概率Hough累積提取有效圓及其初始半徑，最后利用圓的直接最小二乘擬合進一步定位圓半徑和圓心[7]。

在參數(shù)不超過二維的情況下，Hough變換有著很理想的想過，但當參數(shù)達到或超過三維時(圓的參數(shù)空間為三維：圓心(x，y)，半徑r)，這種變換的計算時間和存儲空間急劇增大，很難在實際應用中使用[3]，因此本文不做研究。本文分析總結了重心法、中心收縮法和基于邊緣跟蹤的最小二乘圓擬合算法在圓特征提取應用中的優(yōu)缺點和適用性，并針對成像目標缺損影響圓特征提取精度的問題，提出了一種全新的基于邊緣二次跟蹤的雙圓檢測算法。

2 數(shù)據(jù)預處理

2.1 圖像增強

在圖像的生成、傳輸、接收和處理過程中往往會受到噪聲干擾，這些噪聲使得圖像上像素點的灰度值不能正確地反映空間物體對應點的灰度值，降低了圖像質量，影響了圖像的可判讀性。圖像增強是在不追究圖像降質原因的情況下，通過作用于圖像的空間域或頻率域，突出感興趣目標物，衰減其他次要信息，以求改善圖像的視覺效果，提高圖像的目視可讀性和機器識別性，使圖像更適合于人或機器處理。

圖像增強按目的可分為兩類：一類是圖像平滑，另一類是圖像銳化。前者是為了抑制噪聲、改善圖像的視覺效果，而后者則是為了突出邊緣，使圖像更易于機器識別和處理。

本課題主要采用中值濾波算法來增強圖像，具體原理及實現(xiàn)步驟參見參考文獻[8]。

2.2 二值化

圖像二值化是一種圖像分割方法，它將圖像中感興趣的目標物從背景中分割出來，其過程類似于按近似屬性進行聚類。它將像素點按灰度分成兩部分，使得圖像上所有的像素點的灰度值不是“0”就是“255”，從而從多值的數(shù)字圖像中提取出目標物體以供進一步研究。

本文選用最常用的全局閾值法——OTSU算法。

OTSU算法，又稱大津法、最大類間法，由Otsu于1979年提出，因計算簡單、自適應強而被公認為效果最好、應用面最廣的全局閾值法。該方法的主要思想是找到一個灰度值，將圖像中所有像素分為兩類，并使得類內方差最小，類間方差最大，那么此灰度值就是最佳二值化閾值。具體原理及實現(xiàn)步驟參見參考文獻[10]。

3 常用圓特征提取算法

3.1 重心法

重心法，又稱一階矩法，它將組成圓的所有像素的x坐標和y坐標的平均值作為該圓的灰度質心，亦即圓心，再由位于圓最外側的點到該圓心的距離作為半徑。該算法簡單明了，計算速度快，但抗噪能力差，對于圖像中圓斑有缺損，區(qū)域輪廓呈凹形時，得到的中心有可能位于區(qū)域外，產生較大誤差。

為了減少計算量，本文對重心法做了改進，通過計算圓的最外一層像素點的x坐標和y坐標的平均值得到圓的灰度質心，即圓心坐標，然后將邊緣跟蹤起始點到圓心的距離作為圓的半徑。其具體實現(xiàn)過程如下：

(1)對整幅圖像按從上到下，從左往右的順序進行逐行掃描，開始8-鄰域跟蹤；

(2)跟蹤完一個區(qū)域(即圓)后，得到圓的最外層點的x坐標之和M10以及y坐標之和M01，還有該圓的最外層像素點的數(shù)量num和起始點坐標(StartPt.x，StartPt.y)。那么該圓的圓心坐標X，Y和半徑R可由下式計算得到：

X=M10/num

(1)

Y=M01/num

(2)

(3)

(3)由圓的圓心坐標和半徑可以得到圓的外接矩形，按照自上而下，從左往右的順序遍歷矩形內的像素點，并計算矩形內像素點到圓心得距離Range，對Range小于或等于圓半徑R的點進行標記(灰度值賦0)，防止對該區(qū)域進行重復跟蹤遍歷。

(4)繼續(xù)跟蹤檢測下一個圓，直到遍歷完整幅圖像像素。

3.2 中心收縮法

中心收縮法假設圓形區(qū)域是封閉、連通的平面，無空洞，且是可塑的，若在保持區(qū)域連通條件下，由區(qū)域邊緣各處同時向里均勻收縮，使區(qū)域逐漸縮小，類似于逐層剝去圓的邊緣像素。最終會出現(xiàn)以下兩種情況：①最后只剩下一個像素，如圖1左側圓所示，則將此點作為該區(qū)域的中心；②最后沒有剩下像素，且最后一次收縮對象為4個像素點，如圖1右側圓所示，則將最后一次收縮的4個像素點的幾何中心作為該區(qū)域的中心。因此，中心收縮法又叫剝皮法。

圖1 圓域重心收縮的兩種可能結果

在具體實現(xiàn)時主要采用對圖像進行反復邊緣跟蹤的方法達到“剝皮”的效果。實現(xiàn)過程如下：

(1)對整幅圖像按自上而下，從左到右的順序逐行掃描，當找到一個區(qū)域的起始點后進行8-鄰域跟蹤；

(2)在對一個區(qū)域進行8-鄰域跟蹤的過程中，對除了起始點以外的被跟蹤像素的灰度賦值為0，起始點的灰度賦為250；如此一個圓被逐層跟蹤多次后，就只剩下由灰度值為250的已跟蹤起始點和灰度值為255的單點組成的線段；

(3)再次按自上而下，從左到右的順序對整幅圖像進行掃描，當遇到第一個灰度值大于等于250的像素點時，便以此像素點為起始點，對上一步得到的直線進行8-鄰域跟蹤。

(4)每跟蹤完一條線段，判讀跟蹤的最后一個像素點的灰度：若灰度值為255，則說明該點在第一次遍歷時是一個孤立點，沒有被跟蹤，因此將該點的坐標作為圓心坐標，跟蹤的第一個點到該點的距離即為半徑；若灰度值為250，則表明該點在第一次遍歷過程中曾作為起始點被跟蹤，因此以該點為起始點的由4個像素組成的最小封閉區(qū)域的幾何中心即為圓心，半徑為跟蹤第一個點到圓心的距離。

3.3 基于邊緣跟蹤的最小二乘圓擬合

最小二乘法(Least Squares Analysis)是一種數(shù)學優(yōu)化技術，它通過最小化誤差的平方和找到一組數(shù)據(jù)的最佳函數(shù)匹配。它用最簡的方法求得一些絕對不可知的真值，而令誤差平方和為最小。一般最小二乘法用于曲線擬合(Least Squares Fitting)。

圓的解析方程為：

(X-A)2+(Y-B)2=R2

(4)

擬合的目的就是根據(jù)一組數(shù)據(jù)計算A，B，R值。

展開公式(4)得：

X2-2AX+A2+Y2-2BY+B2=R2

(5)

令a=-2A，b=-2B，c=A2+B2-R2，可得圓曲線的另一種形式：

X2+Y2+aX+bY+c=0

(6)

因此只要求出參數(shù)a，b，c就可以求得圓心和半徑：

(7)

(8)

(9)

具體實現(xiàn)過程如下：

(1)對整幅圖像按自上而下，從左到右的順序逐行進行掃描，當找到第一個區(qū)域的起始點后，暫停掃描，開始以此點為起始點進行8-鄰域跟蹤；

(2)對該區(qū)域的邊界點一邊進行跟蹤，一邊將跟蹤過的點的x坐標和y坐標分別存儲在兩個數(shù)組中；

(3)跟蹤完畢后得到所有邊界點的x坐標和y坐標，帶入以上推導公式，即可求得該圓的擬合圓心和半徑；

(4)以所得擬合圓的圓心和半徑求得該圓的外接矩形，然后對矩形內的像素點按自上而下，從左到右的順序進行遍歷，計算每個像素點到圓心的距離range，凡是range≤R的點，都一律賦值為0，防止重復對該區(qū)域進行遍歷；

(5)繼續(xù)對圖像進行掃描，尋找下一個區(qū)域，直到掃描完圖像的所有像素。

4 實驗與分析

4.1 實驗平臺

操作系統(tǒng)：windows 7旗艦版32位SP1，處理器：AMD Phenom Ⅱ N660雙核，內存4G。

4.2 實驗過程

采用控制單一變量的方法，對同一張影像l-1.bmp進行相同的圖像預處理操作，然后分別用不同的圓檢測方法提取影像中的圓特征信息，最后對不同的圓特征提取方法所得到的數(shù)據(jù)進行對比分析。原始影像如圖2所示：

圖2 原始影像

主要過程如下：

(1)讀取影像數(shù)據(jù)；

(2)圖像平滑：進行中值濾波，減少噪聲干擾；

(3)二值化：采用OTSU算法分離背景和目標；

(4)利用重心法對影像圓特征進行提取，得到影像中圓的圓心位置和半徑大??；

(5)圖像還原；

(6)重復(1)～(4)操作，分別利用基于邊緣跟蹤的最小二乘圓擬合算法、中心收縮法對影像進行圓特征提取，得到影像中圓的圓心位置和半徑大??；

(7)比較分析各算法提取的圓心坐標精度。

4.3 實驗結果與分析

影像中一共有50個大小不同的圓，用三種不同的圓特征提取算法對影像中的圓特征進行了提取，得到三組不同數(shù)據(jù)。下表1中，(X1，Y1)為重心法所測圓心坐標，(X2，Y2)為基于邊緣跟蹤的最小二乘圓擬合法所測圓心坐標，(X3，Y3)為中心收縮法所測圓心坐標。

三種圓特征提取算法結果比較 表1

(1)提取精度分析

對這三組數(shù)據(jù)兩兩進行比較，從圓心X、Y坐標和半徑R的差值的平均值以及方差大小進行比較，結果如圖3、圖4所示：

圖3 差值平均值比較結果

圖4 差值方差比較結果

由此可見，重心法和基于邊緣跟蹤的最小二乘圓擬合算法的提取精度要優(yōu)于中心收縮法，三種圓特征提取算法的提取精度相差在亞像素級，基于邊緣跟蹤的最小二乘圓擬合算法和重心法提取精度相差不大，二者的圓心坐標提取差值的平均值小于0.2個像素，方差也在0.16～0.21之間，半徑提取的差值平均值為0.33，方差為1.02，這是因為半徑的提取是通過已提取圓心與圓外圍點的距離運算得到，存在誤差累積。中心收縮法圓心提取的精度只能達到像素級，與前兩種能達到亞像素級精度的方法提取的圓心坐標差值的平均值達到了0.74個像素，接近一個像素，半徑差值在0.53個像素，且差值分布較分散，圓心坐標的差值方差在2.6～10.2之間，半徑差值的方差最高達到5.95。

(2)提取效率分析

對同一幅影像采用同一種二值化方法處理后，分別用三種圓檢測算法進行圓特征提取，統(tǒng)計不同算法的運行時間，每種算法重復試驗10次，然后取該算法這10次運行的平均時間作為算法一般運行時間，并與其他算法的一般運行時間進行比較。結果如表2所示：

三種圓特征提取算法運行時間比較 表2

由上表可知，重心法和基于邊緣跟蹤的最小二乘圓擬合算法的運行效率較中心收縮法高。因為重心法和基于邊緣跟蹤的最小二乘圓擬合算法都只需對圓的最外圍一圈像素進行跟蹤和解算處理，而中心收縮算法則需要對同一個圓重復進行邊緣跟蹤處理，計算量大，所需計算時間長。

(3)抗噪性分析

對圖像進行二值化后，在目標物的周圍加入椒鹽噪聲，以此含有椒鹽噪聲的二值化圖像作為原圖像，分別用三種圓特征提取方法提取該圖像中的圓特征，并將提取得到的圓心在圖中用十字絲進行標記，方便直觀地進行比較。圖5中(a)為原圖像，(b)為重心法提取結果，(c)為基于邊界的最小二乘圓擬合算法提取結果，(d)為中心收縮法的提取結果。

圖5 不同圓特征提取算法的抗噪性實驗結果

由上圖不難看出，基于邊緣跟蹤的最小二乘圓擬合算法的抗噪性能最好，幾乎不受椒鹽噪聲的影響，能夠準確提取出圓特征信息；而重心法和中心收縮法的抗噪性則相對較差，出現(xiàn)了很多誤檢圓心。從誤檢點的分布和數(shù)量來比較，重心法的抗噪性較之于中心收縮法較好，誤檢點數(shù)量少，且其分布較之于重心法誤檢點的分布離正確圓心位置較遠。

5 基于邊緣二次跟蹤的雙圓檢測算法

該方法主要針對雙圓目標靶，能夠在一定程度上提高解算的目標靶位置精度。使用雙圓檢測算法前必須對目標進行邊緣銳化，提取出雙圓邊緣，然后在利用基于邊緣跟蹤的最小二乘圓擬合檢測出外圓特征的條件下，再對內圓用同樣的方法進行圓特征提取，然后比較兩次提取圓心坐標的差值，如果該差值小于給定閾值，則取兩圓圓心的平均坐標作為雙圓的共同圓心，否則不對該目標進行解算。

該方法不僅能提高目標圓心的測量精度，而且可有效避免因為成像目標缺損引起的圓心位置偏差。

主要實現(xiàn)過程如下：

(1)對整幅圖像自上而下，從左往右進行逐行掃描，直到遇到第一個非零點；

(2)將該非零點作為第一個圓的起始點，對該圓進行8-鄰域跟蹤，并記錄被跟蹤點的x坐標和y坐標；

(3)跟蹤完畢后，利用跟蹤得到了圓的邊界點的x坐標和y坐標進行最小二乘擬合，得到外圓的擬合圓心(A1，B1)和半徑R1；

(4)由上一步得到的外圓的圓心和半徑可以得到外圓的外接矩形，按自上而下，從左到右的順序掃描該矩形內的像素，并計算像素點到外圓圓心的距離range1，對于range1∈[R-2，R+2]的點賦值為0，以消除外圓輪廓余點(外輪廓在跟蹤后未被標記的點)的干擾；

(5)對外圓的外接矩形內的點再次按照自上而下，從左到右的順序進行掃描，直到遇到第一個非零點，即為內圓的起始點；

(6)對內圓進行8-鄰域跟蹤，利用跟蹤得到的內圓邊界點的x坐標和y坐標通過最小二乘圓擬合法得到內圓的圓心坐標(A2，B2)和半徑R2；

(7)對內圓的外接矩形內的點進行掃描，并計算掃描像素點到內圓圓心的距離range2，對于range2∈[0，R+2]的點全部賦值為0，防止重復遍歷；

(8)比較得到外圓和內圓的圓心坐標的差值(A1-A2)、(B1-B2)，若二者都小于設定閾值I=1，則雙圓的圓心坐標為：

A=(A1+A2)/2

(10)

B=(B1+B2)/2

(11)

否則，跳出循環(huán)，舍棄對該圓的檢測；

(9)繼續(xù)對圖像進行掃描，尋找下一個雙圓區(qū)域，直到掃描完圖像中的所有像素點。

6 結 語

本文在研究總結三種常用圓特征提取算法原理的基礎上，通過實驗分析，比較了三種圓特征提取算法在提取精度、提取效率和抗噪性等方面的差異，發(fā)現(xiàn)重心法和基于邊緣跟蹤的最小二乘圓擬合算法精度和運行效率相近，明顯優(yōu)于中心收縮法，且基于邊緣跟蹤的最小二乘圓擬合算法相對其余兩種算法的抗噪能力突出。最后，針對成像目標缺損引起的提取圓心位置偏差的現(xiàn)象，提出并實現(xiàn)了一種基于邊緣二次跟蹤的雙圓檢測算法。本文研究發(fā)現(xiàn)，在效率和精度方面，各提取算法已經接近極限，發(fā)展空間有限，這一點在本文的實驗數(shù)據(jù)中可以看出。因此，未來的發(fā)展方向在于發(fā)現(xiàn)一種高穩(wěn)定性、高適應性的圓特征提取算法或提取流程。

[1] 孔兵，王昭，譚玉山. 基于圓擬合的激光光斑中心檢測算法[J]. 紅外與激光工程，2002，31(3)：276～279.

[2] 朱桂英，張瑞林. 基于Hough變換的圓檢測方法[J]. 計算機工程與設計，2008，29(6)：1462～1464.

[3] 霍建亮，曾翎，王德勝等. 基于最小二乘法改進的隨機圓檢測算法[J]. 光電工程，2011，38(5)：145～150.

[4] 李婷，柳寧. 基于機器視覺的圓定位技術研究[J]. 計算機工程與應用，2012，48(9)：153～156.

[5] Chung Kuo-Liang，Huang Yong-Huai，Shen Shi-Ming，et al. Efficient sampling strategy and refinement strategy for randomized circle detection[J]. Pattern Recognition，2012，45(1)：252～263.

[6] 劉好龍，侯文，范亞龍等. 一種改進的激光光斑中心定位算法[J]. 計算機測量與控制，2014，22(1)：139～141.

[7] 陳珂，吳建平，李金祥等. 一維概率Hough變換的實時魯棒多圓檢測方法[J]. 計算機輔助設計與圖形學學報，2015(10)：1831～1841.

[8] 朱明勝. 圖像增強技術研究與實現(xiàn)[D]. 合肥：安徽大學，2014.

[9] 童立靖，張艷，舒巍等. 幾種文本圖像二值化方法的對比分析[J] . 北方工業(yè)大學學報，2011(1)：25～33.

[10] 郭佳，劉曉玉，吳冰等. 一種光照不均勻圖像的二值化方法[J] . 計算機應用與軟件，2014(3)：183～186.

Circular Feature Extraction and Precision Evaluation of the High Resolution Image

Ou Yanghui1，2，Zhang Junqian1，2

(1.Chongqing Survey Institute，Chongqing 401121，China；2.Chongqing Engineering Research Center of Geographic National Condition Monitoringr，Chongqing 401121，China)

Circular feature extraction of the high resolution image has been widely used in photogrammetry，and the precision of the extraction has a great effect on digital camera calibration and specific target monitoring. Based on the summarize of 3 common circular feature extraction algorithms，according to the results of the tests，this paper calculated that the advantages and disadvantages of the 3 different circular feature extraction algorithms，include gravity algorithm、center shrink algorithm and least squares analysis algorithm based on edge tracking. At last，this paper suggested a double circle extraction algorithm，solved the problem of inaccurate center position caused by deviation of the target.

circular feature extraction；image binarization；double circle extraction

1672-8262(2016)05-58-06

P231.1，TP751

A

2016—03—17

歐陽暉(1990—)，男，助理工程師，主要從事航空攝影測量數(shù)據(jù)獲取和數(shù)據(jù)處理工作。

住房和城鄉(xiāng)建設部科學技術計劃項目(2015-K8-009)