基于Hough變換運用形狀角及梯度檢測圓

方 菲，耿春明

（北京航空航天大學 機械工程及自動化學院，北京 100191）

0 引言

常見幾何圖形的識別是機器視覺中非常重要的一項任務，其中圓形的快速準確檢測在圖像處理中占據著重要地位。常用的檢測圓算法［1］主要有Hough變換（CHT）［2］及相應改進算法、環路積分微分法、最小二乘擬合算法和遺傳算法等。其中應用最廣的是Hough變換及相應改進算法。Hough變換的基本原理［3］是將圖像空間中具有某種關系的像素變為參數空間的聚焦點，并通過判斷參數空間的各個聚焦點的累積程度來完成這種給定關系的特征曲線檢測。Hough變換對圖像的噪聲不敏感，有較好的魯棒性，但當參數空間的維數達到或超過3時，這種方法的計算時間和存儲空間都會變的很大。圓的參數空間為三維：圓心（a，b）、半徑r，因此在實際應用中這種方法不適合用來檢測圓。針對上述問題，結合輪廓線的形狀角特征及梯度信息，本文提出了一種新的基于Hough變換檢測圓的改進算法，最終可以準確并且快速地得到檢測結果。

1 相關理論

在圖像空間檢測圓中，廣義Hough變換是通過在全圖所有邊緣像素點中隨機采樣來確定候選圓，但因為存在噪聲點、非圓形形狀的邊緣點等各種無效采樣，導致大量的候選圓為假圓。本文首先利用形狀角這個幾何不變量來判斷輪廓線是否為圓形，剔除噪聲點以及非圓形邊緣輪廓點等無效采樣點；然后再通過保留下的輪廓線的梯度信息來確定候選圓，利用梯度信息可將檢測圓輪廓的累加矩陣從三維轉變為二維；此外，確定候選圓后，在對邊緣點進行證據積累（Evidence Collecting，EC）時，由于圓必定在其外接正方形之內，因此可不必考慮位于候選圓外接正方形之外的邊緣點［4］，以此減少算法的計算量，提高檢測圓的速度。

［5］定義形狀角Sθ為：

其中：mi為輪廓上每一點與該輪廓質心的連線；gi為輪廓上每一點的法向量；αi為mi和gi的夾角；n為輪廓邊緣點的總個數。

圓有如下性質：

性質1：根據圓形的質心就是圓心可知，理想圓的形狀角Sθ為0°。

性質2：根據圓的性質——圓的切線垂直于過切點的直徑可知，圓心在圓上任意一點的法線上。對于圖像上的每一個在圓上的邊緣點，加上它的梯度信息（方向信息），就可確定一條直線，圓的圓心就在這條直線上。

性質3：假設已確定候選圓Oij（圓心為（aij，bij）、半徑為rij），為檢驗候選圓是真圓還是假圓而進行證據積累時，可不考慮位于此圓外接正方形之外的邊緣像素點，即對于邊緣點（xm，ym）（（xm，ym）∈U，其中U是圖像空間中所有邊緣像素點的集合），當xm＞aij＋rij或xm＜aij－rij或ym＞bij＋rij或ym＜bij－rij時，則不再對（xm，ym）進行證據積累。

2 算法描述

2.1 算法基本思想

為降低噪聲影響，首先對給定的原始圖像進行預處理，主要是采用中值濾波對圖像進行平滑處理；然后采用Canny算子對預處理后的圖像進行邊緣檢測并記錄輪廓線的梯度信息，為了不盲目投票，先依據上文所述的性質1對檢測出的邊緣輪廓線進行初步分類，剔除形狀非圓形的邊緣輪廓，只保留形狀為圓形的輪廓線；接著再利用保留下的輪廓線的梯度信息根據性質2初步確定圓心和半徑；最終運用證據積累的方法精確定位圓的位置。

根據式（1）計算圖像上所有邊緣輪廓的形狀角Sθ，當某一段輪廓的形狀角滿足Sθ≤ε（ε為給定的一個很小的值）時，可以認為該輪廓的形狀為圓形，則保留此段邊緣。經過該步驟后，可以過濾掉一些形狀為非圓形的邊緣輪廓，只保留形狀為圓形的邊緣輪廓，即可過濾復雜背景下的一些干擾物體，從而提高檢測速度。

常見的生物措施。在茄子種植中，可以根據當地的實際情況、自然環境，選擇抗病蟲害的茄子種子，避免出現病蟲害；在病蟲害的預防中，可以先使用化學藥水浸泡種子，使種子能夠抗病蟲害；在選擇茄子種子時要選擇種粒飽滿、質量高、無病蟲害的種子。

由式（4）初步解出圓心坐標（xo，yo），由此坐標與輪廓上任一個邊緣點可初步求出半徑r，這時該圓形的位置已大致確定。下一步利用證據積累的方法精確定位此圓形輪廓的位置。在初步解出的圓心坐標與半徑的基礎上，分別給定一個圓心和半徑的變化范圍to和tr，使得圓心坐標和半徑分別在［xo－to，xo＋to］，［yo－to，yo＋to］，［r－tr，r＋tr］范圍內變換。采用證據積累法累計出在每一種情況確定的圓上有多少點是位于邊緣輪廓上的，找出具有最多邊緣點的圓，此時求得的圓的位置便是精確定位的。在進行證據積累時，根據性質3可知，只需驗證位于圓外接正方形內的邊緣點即可，不必遍歷全圖的所有邊緣點，這樣可提高檢測速度。

2.2 算法步驟

具體算法流程如圖1所示。

圖1 算法流程圖

算法中主要有3個步驟：利用形狀角分類輪廓邊緣線、采用保留下的輪廓邊緣線初步確定圓心和半徑、精確定位圓位置。前兩個步驟的程序實現過程主要依據算法原理中的公式進行，第三個步驟的程序實現主要過程如下：

循環所有情況，iNumOfCircle表示為在每一種情況下既在圓上又位于邊緣輪廓上的元素個數。記錄當iNumOfCircle值最大時的半徑及圓心位置，此時求得的圓即是最終確定的圓位置。

3 實驗

本文中的算法在Windows XP操作系統、Microsoft Visual C＋＋6.0平臺上實現，實驗中所采用的圖像大小為480×640、灰度為256，實驗圖像及其檢測結果如圖2、圖3所示。

圖2 實驗圖像1及其檢測結果

圖3 實驗圖像2及其檢測結果

圖2的檢測時間為42ms，圖3的檢測時間為57 ms。從檢測結果圖像（將檢測到的圓在圖中用白線沿邊緣圈出）可以看出，本文提出的算法能較準確地找到圓的位置；從檢測算法所耗費的時間可以看出，此算法能較快速地得到檢測結果。

通過對實際應用中圖像的測試，證明此算法具有較好準確性、快速性及魯棒性。

4 結語

廣義的Hough變換有計算時間長或存儲空間大等問題，為解決這些問題，一些基于Hough變換的改進方法常利用導數信息或梯度信息，但當背景復雜或受噪聲干擾影響較大時，導數或梯度信息會十分敏感，所以僅僅利用導數或梯度信息可能會導致誤檢或漏檢。所以在本文提出的這種計算方法中，不僅結合梯度信息，也結合了形狀角這一幾何不變量特征。因為形狀角只與輪廓的形狀有關，所以對噪聲或復雜背景的敏感度較小。這樣在解決了時間和空間復雜度高問題的同時，也保證了算法對干擾噪聲或復雜背景的敏感程度，也就是說本文介紹的結合輪廓線形狀角及梯度信息的Hough變換檢測圓的改進算法不僅提高了圓檢測速度，也具有較好的魯棒性。

［1］王敏，李啟堂，丁書斌.單參數Hough變換實現圓檢測方法的研究［J］.機械設計與制造，2007（7）：61－63.

［2］Illingworth J， Kittler J. A survey of the Hough transform［J］.Computer Vision Graphics and Image Process，1988，44（1）：87－116.

［3］趙小川，何灝，繆遠誠.MATLAB數字圖像處理實戰［M］.北京：機械工業出版社，2013.

［4］陳愛軍，李金宗，李東東.一種改進的隨機圓檢測算法［J］.光電工程，2006，33（12）：91－95.

［5］秦開懷，王海潁，鄭輯濤.一種基于Hough變換的圓和矩形的快速檢測方法［J］.中國圖像圖形學報，2010，15（1）：109－115.

［6］崔繼文，譚久彬.基于梯度信息的隨機 Hough變換圓輪廓測量技術［J］.紅外與激光工程，2006，35（增刊1）：419－424.

［7］陳星.一種基于梯度Hough變換的同心圓檢測新方法［J］.技術縱橫，2011（7）：86－89.