尚璐，李銳，宋信玉

（重慶大學(xué)光電技術(shù)及系統(tǒng)教育部重點實驗室，重慶400030）

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

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

1 原理

圓的標(biāo)準(zhǔn)方程為：

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

1.1 圓心的檢測

假定數(shù)字圖像大小為M×N，經(jīng)過邊緣檢測得：

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

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

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

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

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

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

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

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

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

1.1.1 單 圓圓心檢測

計算單圓圓心橫坐標(biāo)a的算法步驟：

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

①像素點為非邊緣點pxj（與行數(shù)x無關(guān)）。

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

（pxj，mxp，lxq取橫坐標(biāo)值）

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

3）參數(shù)空間中A（Pxj）最大值對應(yīng)的pxj即為圓心橫坐標(biāo)，a=pxj（pxj取橫坐標(biāo)值）。

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

這樣就求得了圓心坐標(biāo)（a，b）。

1.1.2 多 圓圓心檢測

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

1.2 半徑累積

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

2 復(fù)雜度分析

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

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

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

故本文算法在執(zhí)行時共進行了3×N次計算，復(fù)雜度函數(shù)為：

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

3 實驗結(jié)果

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

3.1 實驗1

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

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

表1 檢測平均執(zhí)行時間比較結(jié)果Tab.1 Comparison of runtime

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

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

3.2 實驗2

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

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

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

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

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

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

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

4 結(jié)論

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

[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]商飛，王豐貴，田地，等.一種基于圓內(nèi)接直角三角形的圓檢測方法[J].光學(xué)學(xué)報，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].計算機輔助設(shè)計與圖形學(xué)學(xué)報，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].上海交通大學(xué)學(xué)報，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變換實現(xiàn)圓檢測的方法[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.