一種用Ｈｏｕｇｈ變換檢測(cè)圓的快速算法

摘要:為了克服傳統(tǒng)Hough變換檢測(cè)圓時(shí)耗時(shí)巨大的缺陷，給出了一種新的基于Hough變換檢測(cè)圓的快速算法#65377;新算法與傳統(tǒng)的方法相比具有以下特點(diǎn):計(jì)算量少，提高了檢測(cè)的速度;保留了傳統(tǒng)Hough變換識(shí)別率高#65380;抗噪性強(qiáng)#65380;對(duì)不完整邊緣具有魯棒性等所有優(yōu)點(diǎn);不需要任何特殊的限定條件#65377;實(shí)驗(yàn)表明，新的快速算法可以快速進(jìn)行目標(biāo)識(shí)別，在實(shí)時(shí)目標(biāo)識(shí)別系統(tǒng)中具有良好的表現(xiàn)#65377;

關(guān)鍵詞:目標(biāo)識(shí)別;霍夫變換; 圓的檢測(cè); 快速算法

中圖分類號(hào):TP317文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2007)10-0197-03



0引言

在日常生活和軍事應(yīng)用中，在不同視角下，許多物體以類似圓的形狀出現(xiàn)，準(zhǔn)確而有效地檢測(cè)出這些圓形物體在圖像中的位置就成為圖像分析的一項(xiàng)重要工作#65377;在應(yīng)用中經(jīng)常采用的一種方法就是Hough變換或其改進(jìn)算法#65377;Hough變換是Paul Hough在1962年提出的一種圖像邊緣檢測(cè)技術(shù)，它可以檢測(cè)圖像空間中的任意解析曲線[1]#65377;Hough變換以其對(duì)局部缺損的不敏感#65380;對(duì)隨機(jī)噪聲的魯棒性以及適于并行處理等優(yōu)良特性，備受圖像處理#65380;模式識(shí)別和計(jì)算機(jī)視覺(jué)領(lǐng)域?qū)W者的青睞#65377;Hough變換的突出優(yōu)點(diǎn)就是可以將圖像中較為困難的全局檢測(cè)問(wèn)題轉(zhuǎn)換為參數(shù)空間中相對(duì)容易解決的局部峰值檢測(cè)問(wèn)題#65377;然而利用傳統(tǒng)的Hough變換檢測(cè)圖像中的圓時(shí)，所需的計(jì)算量非常大#65380;檢測(cè)速度慢，需要研究新的快速方法#65377;到目前為止，對(duì)Hough快速算法的研究主要集中在四個(gè)方面:對(duì)解析曲線方程進(jìn)行變形來(lái)減少計(jì)算的復(fù)雜性[2];利用曲線的某些特殊性質(zhì)來(lái)簡(jiǎn)化計(jì)算[3];通過(guò)減少累加器空間的維數(shù)來(lái)減少運(yùn)算所需的存儲(chǔ)空間[4];利用相位信息來(lái)減少計(jì)算量[5] #65377;但這些算法在實(shí)際應(yīng)用中往往具有較大的局限性或要求的條件比較苛刻，不能適應(yīng)一般情況#65377;如對(duì)解析曲線方程進(jìn)行變形來(lái)減少計(jì)算復(fù)雜性的算法需要精確計(jì)算出邊緣點(diǎn)的方向信息;利用曲線的某些特殊性質(zhì)的算法在某些特殊情況下不能正常識(shí)別目標(biāo)，如圓的邊緣提取出來(lái)不到3/4圓周時(shí);通過(guò)減少累加器空間的維數(shù)來(lái)減少運(yùn)算所需的存儲(chǔ)空間只是減少運(yùn)算時(shí)所需的存儲(chǔ)器空間，并不能減少算法的運(yùn)算時(shí)間;利用相位信息的算法的抗噪性能不如傳統(tǒng)算法[1]#65377;本文在Duda提出的傳統(tǒng)Hough變換思想的基礎(chǔ)上，結(jié)合坐標(biāo)平移的知識(shí)提出了一種新的用Hough變換檢測(cè)圓的快速算法#65377;新算法可以較顯著地提高檢測(cè)速度，不需要任何限定條件;新算法需要與傳統(tǒng)算法一樣大小的累加器空間#65377;

本文介紹了Hough變換的原理，提出了用Hough變換檢測(cè)圖像中圓的快速算法及計(jì)算量的分析#65377;

1Hough變換原理

Hough變換檢測(cè)圓的基本思想是將圖像空間中的邊緣點(diǎn)映射到參數(shù)空間中，然后將在參數(shù)空間中得到的所有坐標(biāo)點(diǎn)元素對(duì)應(yīng)的累加值進(jìn)行累加統(tǒng)計(jì)，根據(jù)累加值判斷圓的大小和圓心所在位置#65377;在笛卡爾坐標(biāo)系下圓的方程為

3實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證新算法的可行性和識(shí)別效果，分別用Duda提出的傳統(tǒng)Hough變換算法[1]和本文所提出的新算法進(jìn)行了目標(biāo)識(shí)別實(shí)驗(yàn)對(duì)比#65377;系統(tǒng)運(yùn)行主機(jī)為PC機(jī)，CPU為Intel P4#65380;主頻1.8 GHz，內(nèi)存512 MB DDR 333 MHz，標(biāo)準(zhǔn)C++代碼源程序#65377;

3.1合成圖像檢測(cè)實(shí)驗(yàn)

合成圖像為無(wú)噪聲圖像序列，如圖2所示，序列共有47張圖，合成圖像分辨率為800×600，圖像序列中第N+1張圖比第N張圖多一個(gè)半徑為隨機(jī)大小的圓#65377;在本次試驗(yàn)中，圓的半徑限定最小為20個(gè)像素，最大為40個(gè)像素#65377;識(shí)別結(jié)果如圖3所示#65377;第一組比較實(shí)驗(yàn)為比較改進(jìn)后的新算法相對(duì)于傳統(tǒng)算法提高的倍數(shù)#65377;

從圖3(a)可以看出，本文提出的新算法與傳統(tǒng)Hough算法相比速度有了很大的改善，并且對(duì)目標(biāo)的檢測(cè)效果也很顯著#65377;在速度方面，第一組實(shí)驗(yàn)新算法的平均速度比傳統(tǒng)算法的平均速度高6.5倍左右，最高為6.777 5#65377;在檢測(cè)效果方面，新算法和傳統(tǒng)Hough算法的總體檢測(cè)率均為99.82%，新算法的檢測(cè)序列中僅有第21#65380;24兩幀各有一個(gè)圓未檢測(cè)出來(lái)，原始Hough算法同樣也未檢測(cè)出這兩幀中的這兩個(gè)圓，并且傳統(tǒng)Hough算法的檢測(cè)序列中也僅僅是這兩個(gè)圓未檢測(cè)出#65377;新算法的檢測(cè)序列中檢測(cè)出的圓的坐標(biāo)與圓的真實(shí)坐標(biāo)最大相差兩個(gè)像素#65377;以上兩點(diǎn)表明改進(jìn)的快速算法相對(duì)于傳統(tǒng)Hough算法不僅可較高地提高檢測(cè)速度，而且具有較強(qiáng)的目標(biāo)識(shí)別性#65377;

3.2實(shí)際圖像的目標(biāo)識(shí)別

在實(shí)際圖像中，圓形物體的形狀絕大多數(shù)情況下并不是標(biāo)準(zhǔn)的圓，而且實(shí)際圖像中有各種各樣的噪聲#65377;在用Hough變換進(jìn)行目標(biāo)識(shí)別前，需要從圖像中提取目標(biāo)的邊緣并二值化#65377;邊緣提取的好壞對(duì)識(shí)別效果有較大的影響#65377;實(shí)際應(yīng)用中，由于各種影響，目標(biāo)的邊緣往往不能全部提取出來(lái)，給識(shí)別帶來(lái)了較大的困難#65377;以下通過(guò)實(shí)際圖像來(lái)驗(yàn)證新算法的效果，物體的邊緣分別通過(guò)Sobel算子(圖4，圖像分辨率為273×275)來(lái)提取#65377;新算法和傳統(tǒng)算法的珍珠識(shí)別圖像如圖5所示#65377;Canny算子(圖6，圖像分辨率為344×256)來(lái)提取;傳統(tǒng)算法和新算法的電廠識(shí)別圖像如圖7所示;實(shí)驗(yàn)數(shù)據(jù)如表1#65380;2所示#65377;

從表1#65380;2可以看出，在實(shí)際情況下，新算法與傳統(tǒng)算法相比速度有了很大的改善，并且對(duì)目標(biāo)的識(shí)別效果也是很顯著的#65377;在速度方面，新算法的平均速度比傳統(tǒng)算法的平均速度高六倍左右;在識(shí)別效果方面，兩種算法均能正確地識(shí)別物體#65377;圖4(a)新算法識(shí)別出的上方目標(biāo)坐標(biāo)的水平方向與傳統(tǒng)算法大兩個(gè)像素，垂直方向比傳統(tǒng)算法小一個(gè)像素，下方目標(biāo)兩種算法得到的坐標(biāo)一致#65377;圖4(c)新算法識(shí)別出的最下方目標(biāo)坐標(biāo)的水平方向比傳統(tǒng)算法一致，垂直方向比傳統(tǒng)算法大兩個(gè)像素，其他目標(biāo)兩種算法得到的坐標(biāo)一致#65377;圖6(a)兩種算法得到的坐標(biāo)一致#65377;從實(shí)驗(yàn)結(jié)果可以看出，本文提出的新算法同時(shí)也繼承了Hough變換對(duì)邊緣具有魯棒性的優(yōu)點(diǎn)#65377;

3.3實(shí)驗(yàn)分析

一般情況下，當(dāng)目標(biāo)邊緣點(diǎn)和噪聲點(diǎn)較少時(shí)，新算法提高的倍數(shù)介于五倍左右，這主要是系統(tǒng)其他開(kāi)銷(xiāo)在計(jì)算中需要的時(shí)間相對(duì)計(jì)算開(kāi)銷(xiāo)來(lái)說(shuō)比較顯著#65377;隨著目標(biāo)邊緣點(diǎn)和噪聲點(diǎn)的增多，需要計(jì)算的時(shí)間就越多，這樣系統(tǒng)其他開(kāi)銷(xiāo)相對(duì)計(jì)算開(kāi)銷(xiāo)來(lái)說(shuō)影響就沒(méi)有邊緣點(diǎn)和噪聲點(diǎn)少時(shí)顯著#65377;可以看出這種情況下新算法提高的倍數(shù)在六倍左右，這與理論計(jì)算值11(由于設(shè)圓的半徑為20~40個(gè)像素點(diǎn)，R在計(jì)算時(shí)取中間值30)有一定差別#65377;但是考慮到實(shí)際實(shí)現(xiàn)中Windows系統(tǒng)會(huì)有各種系統(tǒng)開(kāi)銷(xiāo)，而且理論計(jì)算值是在只考慮算法中乘法運(yùn)算和加法運(yùn)算所用時(shí)間的情況下，并沒(méi)有考慮比較#65380;賦值#65380;選擇#65380;循環(huán)等各種其他運(yùn)算或操作，這種差別是可以接受的#65377;通過(guò)平移得到的參數(shù)空間中的累加值與通過(guò)計(jì)算得到的參數(shù)空間中的累加值基本一樣，所以新算法保留了所有Hough變換的優(yōu)點(diǎn)，如識(shí)別率高#65380;抗噪性強(qiáng)#65380;對(duì)邊緣具有魯棒性等，并且新算法的目標(biāo)識(shí)別率和原始算法的目標(biāo)識(shí)別率在實(shí)驗(yàn)中的圖像序列中的每幀都一樣#65377;在數(shù)字圖像中受坐標(biāo)離散化的影響，通過(guò)平移所得到的坐標(biāo)點(diǎn)集合和通過(guò)計(jì)算得到的坐標(biāo)點(diǎn)集合不可能完全一樣，所以兩種算法得到的目標(biāo)坐標(biāo)不可能完全一致，但是實(shí)際中這種不一致對(duì)識(shí)別效果來(lái)說(shuō)影響很小，可以忽略不計(jì)#65377;

4結(jié)束語(yǔ)

本文在Hough變換的基礎(chǔ)上，通過(guò)坐標(biāo)平移來(lái)減少參與運(yùn)算的點(diǎn)數(shù)構(gòu)造出了一種新的檢測(cè)圓的快速算法#65377;新算法不僅保留了原始Hough變換檢測(cè)圓識(shí)別率高#65380;抗噪性強(qiáng)#65380;對(duì)目標(biāo)邊緣具有魯棒性等優(yōu)點(diǎn)，同時(shí)大大解決了Hough變換比較耗時(shí)的缺點(diǎn)#65377;實(shí)驗(yàn)結(jié)果表明，新算法具有與原始算法一樣的識(shí)別率，可以較顯著地提高識(shí)別速度(在圓的半徑為20~40個(gè)像素時(shí)可以將識(shí)別速度提高六倍左右)#65377;

參考文獻(xiàn):

[1]DUDA R O， HART P E. Use of the Hough transform to detect lines and curves in pictures[J]. Communications of the ACM， 1972，15(1):1115.

[2]DAVIES E R. A modificd Hough scheme for general circle location[J]. Patt Rec Lett， 1988，6:37-43.

[3]GONEID A， ELGINDI S， SEWISY A.A method for the Hough transform detection of circles and ellipses using a 1dimensional array[C]//Proc of the IEEE International Conference on Systems，Man and Cybernetics. Orlando:[s.n.]， 1997:3154-3157.

[4]MINOR L G， SKLANSKY J. Detection and segmentation of blobs in infrared images[J]. IEEE Trans SMC， 1981，11:194-201.

[5]ATHERTON T J，KERBYSON D J.Using phase to represent radius in the coherent circle Hough transform[M].London:IEEE，1993:1-4.

[6]IA32 intel architecture software developer’s manual volume 1: basic architecture[EB/OL].(2001).ftp://download.intel.com/design/Pentium 4/manuals/25366521.pdf.

[7]IA32 intel architecture optimization reference manual[EB/OL].(2001).ftp://download.intel.com/design/Pentium4/manuals/24896613.pdf.

[8]KERBYSON D J， ATHERTON T J.Circle detection using Hough transform filters[M]. Washington， DC: IEEE Conference Publication， 1995:370-374.

[9]KICRKEGAIIRD P. A method for detection of circular arcs based on the Hough transfrom[J]. Machine Vision and Adulications， 1992，5:249-263.

[10]HINTON G. The microarchitecture of the Pentium 4 processor[EB/OL].[2001].http://www.intel.com/technology/itj/q12001/pdf/art_2.pdf.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”