尚璐，李銳，宋信玉

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

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

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

1 原理

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

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

1.1 圓心的檢測(cè)

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

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

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

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

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

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

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

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

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

這樣通過對(duì)稱點(diǎn)的Hough變換就可以計(jì)算出圓心（a，b）。

1.1.1 單 圓圓心檢測(cè)

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

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

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

②對(duì)pxj的左右相鄰像素點(diǎn)進(jìn)行搜索，找到左右相鄰的第一個(gè)邊緣像素點(diǎn)，記為mxp（向左搜索），lxq（向右搜索）。

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

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

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

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

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

1.1.2 多 圓圓心檢測(cè)

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

1.2 半徑累積

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

2 復(fù)雜度分析

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 實(shí)驗(yàn)1

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

圖2 實(shí)驗(yàn)圖像的檢測(cè)結(jié)果Fig.2 Result of detected value

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

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

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

3.2 實(shí)驗(yàn)2

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

圖3 實(shí)驗(yàn)圖像Fig.3 Imgae of experiment

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

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

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

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

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

4 結(jié)論

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

[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)接直角三角形的圓檢測(cè)方法[J].光學(xué)學(xué)報(bào)，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]黎自強(qiáng)，滕弘飛.廣義Hough變換:多個(gè)圓的快速隨機(jī)檢測(cè)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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]陳燕新，戚飛虎.基于隨機(jī)Hough變換的快速圓檢測(cè)方法[J].上海交通大學(xué)學(xué)報(bào)，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]林金龍，石青云.用點(diǎn)Hough變換實(shí)現(xiàn)圓檢測(cè)的方法[J].計(jì)算機(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.