一種基于Hough變換的快速圓檢測算法

王　敏，童水光，陳玉輝，從飛云

(浙江大學(xué) 機(jī)械工程學(xué)院，浙江　杭州　310027)

0　引言

在實現(xiàn)機(jī)器視覺的過程中，提取圖像的目標(biāo)特征信息是檢測的第一步。圓作為一種基本的幾何特征，在許多應(yīng)用場合中快速而準(zhǔn)確地檢測出輪廓圓及其數(shù)目，可為更進(jìn)一步的操作提供理論依據(jù)，具有廣泛的工業(yè)應(yīng)用價值。例如在基于圖像處理的輪轂自動化加工系統(tǒng)中，對輪轂輪廓圓的識別就屬于這樣的一類應(yīng)用。傳統(tǒng)霍夫變換(Conventional Hough Transform，CHT)是圖像處理領(lǐng)域?qū)δ繕?biāo)特征識別與提取的重要方法之一，也是檢測輪廓圓的有效方法[1]。然而若將CHT直接用于輪廓圓檢測，由于圓有3個獨(dú)立參數(shù)，需要在三維參數(shù)空間進(jìn)行累積，致使這種算法僅在理論上可以取得較好的結(jié)果，在實際中因計算量和內(nèi)存需求量過大而難以應(yīng)用[2]。為了解決這個問題，Xu等人研究出了隨機(jī)霍夫變換(Randomized Hough Transform，RHT)[3-4]，在目標(biāo)圖像里隨機(jī)采樣非共線的3個輪廓點(diǎn)計算出圓的參數(shù)，并將其變換至參數(shù)空間進(jìn)行累計，屬于“多到一”的映射，從而避免了CHT復(fù)雜的“一到多”映射。Chen等人研究出了改進(jìn)的圓檢測算法(Randomized Circle Detection，RCD)[5]，在證據(jù)累積驗證前先進(jìn)行預(yù)判，即確定隨機(jī)采樣的4點(diǎn)是否共圓，然后驗證其圓的真?zhèn)涡?，它在噪聲比小?.7的條件下能夠大大提升圓的檢測速度。方菲等人利用形狀角特征判別是否為圓形[6]。盡管這些研究卓有成效，但是目前的研究中仍存在以下問題：

(1) 盡管避免了經(jīng)典Hough變換“多到一”的映射，但由于隨機(jī)采樣的無目標(biāo)性，給驗證圓的過程增加了負(fù)擔(dān)，降低了檢測速度。

(2) 在三維空間的累積計算中，增加了算法執(zhí)行的難度，不能在實時性要求高的場合應(yīng)用。

(3) 在特征圓和噪聲增多的情況下，容易產(chǎn)生大量無效累積，增加存儲量，影響計算的準(zhǔn)確性，降低圓檢測的性能和效率。

本文從減少參數(shù)空間維度和避免無用點(diǎn)累積的角度，提出一種基于對稱性的快速Hough變換圓檢測方法。其主要思想是利用圓的先驗幾何特性來提取有效點(diǎn)、規(guī)避無用點(diǎn)，將參數(shù)空間維數(shù)降低至二維空間，從而減少無效點(diǎn)帶來的計算消耗，提高檢測效率，并在實驗中取得了較好的效果。

1　Hough變換圓檢測

Hough變換是由Paul Hough于1962年提出的一種基于表決原理的參數(shù)估計技術(shù)[7]。假設(shè)半徑為r，圓心在(x0，y0)處的目標(biāo)一般圓方程是：

(x-x0)2+(y-y0)2=r2.

(1)

顯然，由式(1)可知目標(biāo)圓方程中一共包括x0、y0和r三個自由參數(shù)。由Hough變換原理可知，圖像在O-XY坐標(biāo)空間中的輪廓圓上的像素點(diǎn)都有同樣的特征參數(shù)，若將其變換至O-XYR三維的參數(shù)空間中，則輪廓圓上所有的像素點(diǎn)(xi,yi)相應(yīng)地轉(zhuǎn)換為在三維參數(shù)空間中的所有圓錐面Σi并相交于一點(diǎn)(x0，y0,r)[8]，而此點(diǎn)在參數(shù)坐標(biāo)空間中的坐標(biāo)即為輪廓圓的三個參數(shù)。二維輪廓圓圖像的坐標(biāo)空間轉(zhuǎn)化至三維圓錐面參數(shù)的坐標(biāo)空間示意圖如圖1所示。

圖1　Hough參數(shù)空間變換

由于這種算法需要在三維參數(shù)空間進(jìn)行累積，當(dāng)像素點(diǎn)為N，則需要進(jìn)行N3次計算，所以僅在理論上可以取得較好的結(jié)果。在檢測多目標(biāo)輪廓圓時，容易產(chǎn)生大量無效累積，增加存儲量，并且使得復(fù)雜圖像中的圓檢測幾乎不可能實現(xiàn)，嚴(yán)重影響該方法的實際應(yīng)用[9]。

2　基于對稱Hough圓變換法的輪轂圖像輪廓圓特征提取

2.1　算法基本思想

為了提高算法的可靠性，首先對原始圖像進(jìn)行去噪、形態(tài)學(xué)和二值化等預(yù)處理操作，消除圖像中的無關(guān)信息，增強(qiáng)有關(guān)信息的可檢測性。然后在圖像預(yù)處理的基礎(chǔ)上，利用Canny算子提取邊緣輪廓曲線，統(tǒng)計所有邊緣輪廓像素點(diǎn)集合S，按照8鄰域連續(xù)的定義方式將所有連續(xù)的輪廓邊界點(diǎn)統(tǒng)計分為不同的子集，同時去除點(diǎn)數(shù)小于預(yù)先設(shè)定的閾值T1的噪聲集。

由圓的性質(zhì)可知，圓內(nèi)任意弦的中垂線必過圓心，即弦的中垂線是圓的對稱軸，而圓心即是所有對稱軸的交點(diǎn)。利用霍夫變換把若干弦的中點(diǎn)變換到二維參數(shù)空間，就可得到若干條擬合直線，所有直線的交點(diǎn)即為圓心。所以，為了快速而準(zhǔn)確地檢測到圓心，對Canny算子提取的邊緣輪廓分別沿6個方向{0°，30°，60°，90°，120°，150°}進(jìn)行截取，在對每個方向進(jìn)行截取時，求得每條截線與輪廓的交點(diǎn)作為采樣點(diǎn)。設(shè)置多組不同的掃描線重復(fù)上述的操作，求得6組不同方向上的多個中點(diǎn)。然后利用CHT將所有的中點(diǎn)變換至二維參數(shù)空間以獲得不同方向上的擬合直線方程，由于采樣點(diǎn)不全是圓的邊緣點(diǎn)，包含噪聲點(diǎn)，所以所有直線不一定準(zhǔn)確交于一點(diǎn)，因此把到各個直線最近的點(diǎn)作為圓心點(diǎn)，然后求出該圓心點(diǎn)到不同邊界點(diǎn)上的半徑，若所有半徑值的方差小于給定的閾值T2，則判定為圓形，同時求出其平均值作為半徑。反之，若方差大于給定的閾值T2，則判定為該組邊緣點(diǎn)集為非圓形。

2.2　算法步驟

算法流程如圖2所示。

圖2　算法流程

2.3　實驗

為驗證提出算法的可行性，在同樣的系統(tǒng)環(huán)境下，通過CHT、RHT和上述算法對一幅由簡單幾何圖形合成的大小為500 pixel×500 pixel的測試圖像進(jìn)行輪廓圓特征提取測試實驗，測試圖片和實驗結(jié)果如圖3所示，實驗數(shù)據(jù)如表1所示。通過比較可以得出，本文所提出的算法在運(yùn)行時間上有很大程度的提高，同時具有更高的檢測精度。

圖3　輪廓圓特征提取測試實驗結(jié)果

表1　輪廓圓特征提取測試結(jié)果數(shù)據(jù)

輪轂輪廓圓的特征識別對于汽車輪轂自動化打磨去毛刺工序具有重要意義。圖4為1 398 pixel×1 394 pixel的工業(yè)相機(jī)拍攝的實際汽車輪轂圖像，首先將其進(jìn)行二值化等預(yù)處理，然后利用Canny算子提取其邊緣輪廓，應(yīng)用RHT和本文算法對其進(jìn)行測試實驗，結(jié)果如圖5所示。所得結(jié)果數(shù)據(jù)對比如表2所示，可以看出本文提出的算法更接近真實值，具有更高的檢測精度。

圖4　輪轂的原始圖像

圖5　輪轂輪廓圓特征提取

3　結(jié)論

傳統(tǒng)Hough變換(CHT)和隨機(jī)Hough變換(RHT)都是采樣點(diǎn)到三維參數(shù)空間的映射過程，空間復(fù)雜度高，且存在大量無效累積，通用性差。而一些改進(jìn)的Hough變換方法也由于三維參數(shù)空間計算量大，無效采樣和無效累積的存在使檢測效率低下。本文提出的基于對稱性的快速Hough變換圓檢測法能夠更好地提取有效點(diǎn)，規(guī)避無效點(diǎn)，利用采樣點(diǎn)到二維參數(shù)空間的映射得到擬合直線方程，進(jìn)而求得距離直線最近的點(diǎn)，將其作為圓心點(diǎn)完成對輪廓圓的特征提取。

該算法不僅具有傳統(tǒng)Hough變換的優(yōu)點(diǎn)，而且由于降低了參數(shù)空間的維數(shù)，使無效點(diǎn)帶來的計算消耗量大大降低，并且提高了檢測效率，具有較高的實用價值。

表2　輪轂圖像輪廓圓參數(shù)檢測實驗結(jié)果數(shù)據(jù)

參考文獻(xiàn)：

[1]蔣聯(lián)源，蘇勤，祝英?。焖匐S機(jī)Hough變換多圓檢測算法[J]．計算機(jī)工程應(yīng)用，2009，45(17)：163-166．

[2]尚璐，李銳，宋信玉．改進(jìn)的Hough變換圓檢測算法[J]．電子設(shè)計工程，2011，19(14)：168-171．

[3]Xu L，Oja E．A new curve detection method：Randomized Hough Transform(RHT)[J]．Pattern Recognition Letters，1990，11(5)：331-338．

[4]Xu L，Oja E．Randomized hough transform：basic mechanisms，algorithms and computational comp lexities[J]．Image Understanding，1993，57(2)：131-154．

[5]Chen Teh-chuan，Chung Kuo-liang．An efficient randomized algorithm for detecting circles[J]．Computer Vision and Image Understanding，2001，83(2)：172-191．

[6]方菲，耿春明．基于Hough變換運(yùn)用形狀角及梯度檢測圓[J]．機(jī)械工程與自動化，2015(1)：165-167．

[7]Hough V，Paul C．Method and means for recognizing complex patterns: USA,3069654[P].1962-12-18.https://www.researchgate.net/publication/236519005_Method_and_Means_for_Recognizing_Complex_Patterns.

[8]王紅茹，丁文．一種改進(jìn)的基于對稱性的Hough變換圓檢測算法[J]．微電子學(xué)與計算機(jī)，2014，31(6)：121-124．

[9]秦開懷，王海穎，鄭輯濤．一種基于Hough變換的圓和矩形的快速檢測方法[J]．中國圖像圖形學(xué)報，2010，15(1)：109-115．