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

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

(浙江大學 機械工程學院，浙江　杭州　310027)

0　引言

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

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

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

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

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

1　Hough變換圓檢測

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

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

(1)

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

圖1　Hough參數空間變換

由于這種算法需要在三維參數空間進行累積，當像素點為N，則需要進行N3次計算，所以僅在理論上可以取得較好的結果。在檢測多目標輪廓圓時，容易產生大量無效累積，增加存儲量，并且使得復雜圖像中的圓檢測幾乎不可能實現，嚴重影響該方法的實際應用[9]。

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

2.1　算法基本思想

為了提高算法的可靠性，首先對原始圖像進行去噪、形態學和二值化等預處理操作，消除圖像中的無關信息，增強有關信息的可檢測性。然后在圖像預處理的基礎上，利用Canny算子提取邊緣輪廓曲線，統計所有邊緣輪廓像素點集合S，按照8鄰域連續的定義方式將所有連續的輪廓邊界點統計分為不同的子集，同時去除點數小于預先設定的閾值T1的噪聲集。

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

2.2　算法步驟

算法流程如圖2所示。

圖2　算法流程

2.3　實驗

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

圖3　輪廓圓特征提取測試實驗結果

表1　輪廓圓特征提取測試結果數據

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

圖4　輪轂的原始圖像

圖5　輪轂輪廓圓特征提取

3　結論

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

該算法不僅具有傳統Hough變換的優點，而且由于降低了參數空間的維數，使無效點帶來的計算消耗量大大降低，并且提高了檢測效率，具有較高的實用價值。

表2　輪轂圖像輪廓圓參數檢測實驗結果數據

參考文獻：

[1]蔣聯源，蘇勤，祝英俊．快速隨機Hough變換多圓檢測算法[J]．計算機工程應用，2009，45(17)：163-166．

[2]尚璐，李銳，宋信玉．改進的Hough變換圓檢測算法[J]．電子設計工程，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變換運用形狀角及梯度檢測圓[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]王紅茹，丁文．一種改進的基于對稱性的Hough變換圓檢測算法[J]．微電子學與計算機，2014，31(6)：121-124．

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