改進的Hough變換圓檢測算法

尚璐，李銳，宋信玉

（重慶大學光電技術及系統教育部重點實驗室，重慶400030）

快速而準確地檢測出圓及其參數是計算機視覺和模式識別中的一項重要研究內容，在機器視覺自動測量系統、智能檢測等領域有著廣泛的應用前景。標準Hough變換[1]（Standard Hough Transform，SHT）檢測圓是一種最傳統的檢測算法。它的最大優點是：對噪聲不敏感，檢測后可有效去噪；而且在圓變形，甚至部分區域丟失的情況下仍然可以得到比較理想的結果。

Hough變換的基本思想是將圖像空間中具有一定關系的像元進行聚類，尋找能把這些像元用某一解析形式聯系起來的參數空間累積對應點。但由于圓有3個自由參數，需在三維參數空間中進行累積，使得這種做法因計算量和內存需求量過大而不合實際。為了克服這些缺點，XU[2-3]等提出了隨機Hough變換（Randomized Hough Transform，RHT），在圖像空間隨機地選取非共線的三個點映射成參數空間的一個點，是“多對一”的映射。當用RHT處理簡單圖像時，它表現出相當優異的性能，但在處理復雜圖像時，由于隨機采樣引入大量的無效采樣和累積，使算法的性能下降。為此，很多學者提出了改進的RHT算法。如：利用圓內接直角三角形長邊過圓心的性質[4]，對圓參數進行求解；以隨機采樣到的2個圖像點及在此兩點的中垂線上搜索第3個圖像點來確定候選圓[5]；利用圓邊緣上各點梯度所在的直線過圓心的特點，對選取的任意三點進行約束[6]。它們都有效的減少了“多對一”映射的計算量，同時使用動態鏈表結構降低了參量分配空間，但隨著圓和噪聲的增多，隨機采樣的無效累積增多，性能將大大降低。此外，林金龍等提出的一種用點Hough變換實現圓檢測方法[7]，極大地降低了計算復雜性和對資源的需求；Chen等提出了一種非RHT的隨機圓檢測算法（Randomized Circle Detection，RCD）[8]，它在中等以下的噪聲比情況下檢測速度較RHT快。本文提出一種改進的Hough變換圓檢測算法。利用圓為中心對稱圖形的幾何特征，通過Hough變換計算出圓心，然后再進行一次Hough變換計算出圓半徑。該算法不僅有效提高了圓檢測效率，而且在圓和噪聲增多時，性能不會降低。

1 原理

圓的標準方程為：

式中含有3個參數。在本文算法中，3個參數并不是一次性求出，而是分兩步求出：第一步求出圓心，這是該算法的核心；第二步求出圓半徑。

1.1 圓心的檢測

假定數字圖像大小為M×N，經過邊緣檢測得：

式（2）中Pij表示第i行第j列像素點灰度值（0≤i＜M，0≤j＜N）。

假設圓心坐標為（a，b），圖1（a）中hi為數字圖像中第i行的水平掃描線。li，mi為hi與圓的兩個交點，ni為li和mi的中點。它們滿足：

由于圓是中心對稱圖形，故圓心的橫坐標必定在直線x=a上。

所以可以通過對每一行進行掃描，找出這樣的對稱點，并在一維空間中采用Hough變換對它們的中點進行累加計數，計數最大值對應的參數坐標即為a的值。

圖1 圓心的獲取Fig.1 Detect circle center

同理，圖1（b）中uj為數字圖像中第j列的垂直掃描線，wj，qj為uj與圓的兩個交點，ej為wj和qj的中點。它們滿足：

由于圓是中心對稱圖形，故圓心的縱坐標必定在直線y=b上。

所以可以通過對每一列進行掃描，找出這樣的對稱點，并在一維空間中采用Hough變換對它們的中點進行累加計數，計數最大值對應的參數坐標即為b的值。

這樣通過對稱點的Hough變換就可以計算出圓心（a，b）。

1.1.1 單 圓圓心檢測

計算單圓圓心橫坐標a的算法步驟：

1）遍歷整幅圖像，找出滿足以下條件的像素點pxj。

①像素點為非邊緣點pxj（與行數x無關）。

②對pxj的左右相鄰像素點進行搜索，找到左右相鄰的第一個邊緣像素點，記為mxp（向左搜索），lxq（向右搜索）。

（pxj，mxp，lxq取橫坐標值）

2）在一維空間中采用Hough變換對滿足條件的pxj進行A（Pxj）累加計數。

3）參數空間中A（Pxj）最大值對應的pxj即為圓心橫坐標，a=pxj（pxj取橫坐標值）。

同理可以計算出單圓圓心縱坐標，b=pix（pix取縱坐標值）。

這樣就求得了圓心坐標（a，b）。

1.1.2 多 圓圓心檢測

多個圓的圓心檢測與單個圓的圓心檢測類似。在數字圖像中，圓周包含的像素點越多，圓的半徑就越大。根據這一性質，可知半徑越大的圓，圓周中包含的對稱點就越多。故在檢測N個圓的圓心時，參數空間中A（Pij）最大的N個值所對應的Pij即為它們的圓心坐標。

1.2 半徑累積

利用圓心坐標（a，b），將邊緣像素點pij代入圓方程（x-a）2+（y-b）2=r2，計算出一個候選半徑r，在一維空間中采用Hough變換對候選半徑r進行累加計數。看r的計數值A（r）是否大于構成圓允許的最小點數Tm=λ×2πr（λ為比例系數，本文中λ=0.8）來確定真圓，r即為該圓的半徑。

2 復雜度分析

在標準Hough變換檢測圓算法中，由于圓有3個自由參數，需要在三維參數空間中進行累積，共進行N3次計算（假設圖中有N個像素點），復雜度函數為：

按照本文的方法，對復雜度進行分析。計算圓心時，在一維空間中進行累加計數求出圓心坐標，共進行了2×N次計算，復雜度函數為：

同理，計算半徑時，共進行了N次計算，復雜度函數為：

故本文算法在執行時共進行了3×N次計算，復雜度函數為：

O（N3）遠大于O（3N），由此可見，檢測效率大大提高。

3 實驗結果

本文的所有實驗都是在248 MB內存的Celeron1700 MHz計算機上用VC++6.0編程實現的。

3.1 實驗1

實驗1采用的圖像如圖2（a）所示，其大小為280×220，圖中含有3個已知圓，圖2（b）為用Kirsch算子提取的邊緣圖像，圖2（c）為半徑累積的描述圖，表1為用SHT，RHT和本文算法對圖2（b）分別進行檢測的平均執行時間的比較結果（執行50次）。表2為用本文算法對圖2（b）進行檢測的檢測值與真實值的比較。

圖2 實驗圖像的檢測結果Fig.2 Result of detected value

表1 檢測平均執行時間比較結果Tab.1 Comparison of runtime

表2 本文算法對圖2（b）的檢測結果Tab.2 Result of detected value of image2（b）

由表1可知，對于圖2（a）所示的合成圖像，用本文算法檢測圓的速度明顯快于SHT算法和RHT算法，執行時間大大縮短。

3.2 實驗2

在實驗2中，對圖像中含有1～5個圓（圖3（a）含有2個圓，圖3（c）含有5個圓）的情況，用RHT，RCD和本文算法（單幅圖像大小為280220）分別進行檢測。圖4為3種算法平均執行時間的比較（執行50次）。表3為圖3（c）中5個圓的檢測值與真實值的比較。

圖3 實驗圖像Fig.3 Imgae of experiment

圖4 實驗2中3種算法平均執行時間比較Fig.4 Comparison of runtime of experiment 2

為了檢測本文算法的抗噪性能，在圖3（a）中任意加入了不同程度的噪聲，噪聲比大約為25%～150%。圖3（b）所示為在圖3（a）中增加了759個噪聲點的圖像。圖5為圖3（a）和它增加不同比例的噪聲后分別用RHT，RCD和本文算法檢測平均執行時間的比較（執行50次）。

圖5 實驗2中3種算法平均執行時間比較Fig.5 Comparison of runtime of experiment 2

由實驗2可以看出，檢測單個圓時，本文算法與RCD檢測算法的執行時間都非常短，比RHT檢測算法快了一個數量級。當圓的個數和噪聲增加時，RHT檢測算法和RCD檢測算法的執行時間呈線性增加，而本文算法的執行時間幾乎沒有變化。

表3 本文算法對圖3（c）的檢測結果Tab.3 Result of detected value of image3（c）

4 結論

提出一種改進的Hough變換圓檢測算法。該算法不僅保留了標準Hough變換的優點，對噪聲不敏感，而且由于利用圓對稱點的幾何特征進行Hough變換來檢測圓心，使執行時間明顯少于標準Hough變換，計算量也低于其他采用幾何性質來減少Hough變換維數的算法，對單個圓和多個圓同樣有效，具有較高的實用價值。

[1]Hough P V C.Method and means for recognizing complex patterns[P].US:Patent 3069654，1962.

[2]XU L，OJA E.A new curve detection method:Randomized Hough Transform（RHT）[J].Pattern Recognition Letters，1990，11（5）:331-338.

[3]XUL，OJAE.Randomized hough transform:basic mechanisms，algorithms and computational comp lexities[J].Image Understanding，1993，57（2）:131-154.

[4]商飛，王豐貴，田地，等.一種基于圓內接直角三角形的圓檢測方法[J].光學學報，2008，28（4）:739-743.

SHANG Fei，WANG Feng-gui，TIAN Di，et al.A method for circle detection based on right triangles inscribed in a circle[J].Acta Optica Sinica，2008，28（4）:739-743.

[5]黎自強，滕弘飛.廣義Hough變換:多個圓的快速隨機檢測[J].計算機輔助設計與圖形學學報，2006，18（1）:27-33.

LI Zi-qiang，TENG Hong-fei.Generalized Hough transform:fast randomized multi-circle detection[J].Journal of Computer-Aided Design&Computer Graphics，2006，18（1）:27-33.

[6]陳燕新，戚飛虎.基于隨機Hough變換的快速圓檢測方法[J].上海交通大學學報，1998，32（10）:17-20.

CHEN Yan-xin，QI Fei-hu.Fast circle detection using randomized Hough transform[J].Journal of Shanghai Jiaotong University，1998，32（10）:17-20.

[7]林金龍，石青云.用點Hough變換實現圓檢測的方法[J].計算機工程，2003，29（11）:17-18.

LIN Jin-long，SHI Qing-yun.Circle recognition through a point Hough transformation[J].Computer Engineering，2003，29（11）:17-18.

[8]CHEN Teh - chuan ， CHUNG Kuo - liang . An efficient randomized algorithm for detecting circles[J]. Computer Vision and Image Understanding，2001，83（2）:172-191.