基于Hough變換運(yùn)用形狀角及梯度檢測圓

方 菲，耿春明

（北京航空航天大學(xué) 機(jī)械工程及自動化學(xué)院，北京 100191）

0 引言

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

1 相關(guān)理論

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

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

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

圓有如下性質(zhì)：

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

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

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

2 算法描述

2.1 算法基本思想

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

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

常見的生物措施。在茄子種植中，可以根據(jù)當(dāng)?shù)氐膶?shí)際情況、自然環(huán)境，選擇抗病蟲害的茄子種子，避免出現(xiàn)病蟲害；在病蟲害的預(yù)防中，可以先使用化學(xué)藥水浸泡種子，使種子能夠抗病蟲害；在選擇茄子種子時要選擇種粒飽滿、質(zhì)量高、無病蟲害的種子。

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

2.2 算法步驟

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

圖1 算法流程圖

算法中主要有3個步驟：利用形狀角分類輪廓邊緣線、采用保留下的輪廓邊緣線初步確定圓心和半徑、精確定位圓位置。前兩個步驟的程序?qū)崿F(xiàn)過程主要依據(jù)算法原理中的公式進(jìn)行，第三個步驟的程序?qū)崿F(xiàn)主要過程如下：

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

3 實(shí)驗

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

圖2 實(shí)驗圖像1及其檢測結(jié)果

圖3 實(shí)驗圖像2及其檢測結(jié)果

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

通過對實(shí)際應(yīng)用中圖像的測試，證明此算法具有較好準(zhǔn)確性、快速性及魯棒性。

4 結(jié)語

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

［1］王敏，李啟堂，丁書斌.單參數(shù)Hough變換實(shí)現(xiàn)圓檢測方法的研究［J］.機(jī)械設(shè)計與制造，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］趙小川，何灝，繆遠(yuǎn)誠.MATLAB數(shù)字圖像處理實(shí)戰(zhàn)［M］.北京：機(jī)械工業(yè)出版社，2013.

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

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

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

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