基于局部搜索快速隨機(jī)檢測(cè)多個(gè)圓

摘要:以隨機(jī)采樣一個(gè)圖像點(diǎn)P1的5×5鄰域圖像點(diǎn)作擬合直線l1，與l1距離為d(d>0)的平行線l3與l2(l2是通過P1點(diǎn)并垂直于l1的直線)的交叉點(diǎn)為Q，然后以Q為起點(diǎn)，在直線l3上按給定規(guī)則搜索兩圖像點(diǎn)P2和P3，用P1#65380;P2和P3來確定候選圓。當(dāng)采樣和搜索圖像點(diǎn)P2#65380;P3時(shí)，通過剔除孤立#65380;半連續(xù)噪聲和非共圓點(diǎn)顯著地減少了無效采樣和無效計(jì)算。數(shù)值實(shí)驗(yàn)結(jié)果表明，該算法能快速檢測(cè)多個(gè)圓。在檢測(cè)多個(gè)圓時(shí)，其檢測(cè)速度比隨機(jī)圓檢測(cè)算法快一個(gè)數(shù)量級(jí);在孤立和半連續(xù)噪聲不低于所有噪聲的80%時(shí)，其檢測(cè)速度比多個(gè)圓的快速隨機(jī)檢測(cè)算法大約快20%。

關(guān)鍵詞:廣義霍夫變換; 多個(gè)圓檢測(cè); 直線擬合

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

文章編號(hào):1001－3695(2008)02－0469－04

0引言

幾何圖形的識(shí)別是計(jì)算機(jī)視覺領(lǐng)域的重要任務(wù)之一，它主要應(yīng)用于復(fù)雜布局的設(shè)計(jì)與裝配自動(dòng)化#65380;深海探測(cè)#65380;生物圖像檢測(cè)及國防建設(shè)等。對(duì)于復(fù)雜布局，文獻(xiàn)[1]提出了基于人智—圖形—計(jì)算的布局設(shè)計(jì)方法。多個(gè)圓快速檢測(cè)是該方法的一個(gè)重要問題，但該文沒有提出適合解決復(fù)雜布局中的形—數(shù)轉(zhuǎn)換的有效方法。標(biāo)準(zhǔn)Hough變換(standard Hough transform，SHT)#65380;廣義Hough變換(generalized Hough transform，GHT)只適合檢測(cè)單個(gè)圓[2~4]，所以國內(nèi)外的學(xué)者對(duì)多個(gè)圓的快速檢測(cè)作了大量的研究，如Xu等人[5]提出了隨機(jī)Hough變換(randomized Hough transform，RHT)。該方法是多到一的映射，避免了標(biāo)準(zhǔn)Hough變換一到多映射的巨大計(jì)算量。但由于無目標(biāo)的隨機(jī)采樣會(huì)造成大量的無效采樣與無效累積，致使算法性能降低。鑒于此，T.Chen等人[6]提出了一種非RHT系列的隨機(jī)圓檢測(cè)算法(randomized circle detection， RCD)。該方法只有在中等以下的噪聲比情況下，其檢測(cè)速度較RHT快。束志林等人[7]利用梯度信息提出了一種改進(jìn)的RHT算法。該算法較好地解決了無效采樣問題但對(duì)噪聲較敏感。還有學(xué)者研究出一類方法[8，9]，其思想是直接從圖像空間找出所有曲線段，再用數(shù)值方法從這些曲線段中檢測(cè)出圓(或圓弧)。這類方法解決了多個(gè)圓檢測(cè)的無效采樣問題，但算法的時(shí)間復(fù)雜度仍然沒有顯著降低。而文獻(xiàn)[10]通過減少隨機(jī)采樣點(diǎn)數(shù)和識(shí)別孤立#65380;半連續(xù)噪聲降低了無效采樣，減少了無效確認(rèn)圓的次數(shù)，相當(dāng)程度上提高了多個(gè)圓的檢測(cè)效率。本文提出了一種基于局部搜索的多個(gè)圓隨機(jī)檢測(cè)方法，它能在文獻(xiàn)[10]的基礎(chǔ)上進(jìn)一步提高了多個(gè)圓的檢測(cè)速度。

1隨機(jī)多個(gè)圓檢測(cè)效率分析

在圖像空間檢測(cè)多個(gè)圓時(shí)RHT和RCD是通過隨機(jī)采樣來確定候選圓，所以致使大量的候選圓為假圓。文獻(xiàn)[10]通過減少隨機(jī)采樣點(diǎn)數(shù)和識(shí)別無效采樣，使候選圓中假圓的數(shù)量(即確認(rèn)圓的失敗次數(shù))顯著減少(文獻(xiàn)[10]中的表2)RCD和在隨機(jī)檢測(cè)多個(gè)圓時(shí)[10]，其算法均分為兩步:a)確定候選圓;b)確認(rèn)候選圓為真圓。這些算法的步驟b)都是利用文獻(xiàn)[10]的式(6)在包含候選圓的區(qū)域計(jì)算落在候選圓的點(diǎn)數(shù)大于λ×2πr(λ為比例系數(shù);r為候選圓半徑)來確認(rèn)候選圓是否為真圓，其開銷遠(yuǎn)遠(yuǎn)大于步驟a)。一旦a)對(duì)無效采樣沒有被識(shí)別(即候選圓為假圓)則b)為無效計(jì)算。因此，在隨機(jī)多個(gè)圓檢測(cè)算法中更好地避免與識(shí)別無效采樣是進(jìn)一步提高檢測(cè)效率的瓶頸。

2相關(guān)的理論

設(shè)矩陣A=[aij]h(huán)eight×width表示圖像空間的0，1數(shù)字化信息(圖像點(diǎn)值為1，非圖像點(diǎn)值為0)。 其中:width為圖像空間的寬度;height為高度。

定義1在圖像空間中，圓和噪聲像素點(diǎn)統(tǒng)稱為圖像點(diǎn)，其他點(diǎn)為非圖像點(diǎn)。

性質(zhì)1假定圖像空間中ω個(gè)數(shù)字圓的像素?cái)?shù)分別為N1，N2，…，Nω，并且圖像空間中噪聲點(diǎn)數(shù)m是ω個(gè)數(shù)字圓的像素?cái)?shù)和的τ倍，則隨機(jī)采樣一點(diǎn)在同一圓上的概率約是無噪聲時(shí)的1/(1 +τ)。

表2列出的是RCD#65380;文獻(xiàn)[10]和本算法分別對(duì)圖9(a)及其五種噪聲比下的圖像空間檢測(cè)50次的平均時(shí)間(單位:ms)與確認(rèn)真圓的平均失敗次數(shù)(沒有識(shí)別無效采樣的次數(shù))。 比較表2和文獻(xiàn)[6]的圖7可知:本文算法的檢測(cè)速度比RCD和RHT快一個(gè)數(shù)量級(jí)。從表2可知:本文算法在非孤立#65380;非半連續(xù)噪聲點(diǎn)數(shù)不大于所有噪聲的20%時(shí)，盡管未能識(shí)別的無效采樣較文獻(xiàn)[10]稍多，但其平均檢測(cè)時(shí)間卻較文獻(xiàn)[10]少。其原因就是采樣次數(shù)的顯著減少便節(jié)省了總的檢測(cè)時(shí)間。

實(shí)驗(yàn)2根據(jù)文獻(xiàn)[9]構(gòu)造，圖3(a)為有4個(gè)圓的164×210圖像空間。用Kirsch算子提取邊緣后，結(jié)果如圖3(b)所示，它的圖像點(diǎn)數(shù)為2 168。分別用文獻(xiàn)[9，10]和本文方法檢測(cè)圖3(a)50次，本文算法平均檢測(cè)時(shí)間只有215 ms，并且50次檢測(cè)結(jié)果均相同(表3)， 文獻(xiàn)[9，10]的平均檢測(cè)時(shí)間分別為385和20 143 ms。

實(shí)驗(yàn)3圖4是返回式人造衛(wèi)星回收艙的結(jié)構(gòu)圖;圖5是該回收艙中某一層的平面布局圖。用RCD#65380;文獻(xiàn)[10]和本文算法分別對(duì)圖5檢測(cè)50次，三種方法均能檢測(cè)出圖5中的10個(gè)圓，并且檢測(cè)精度相同，但RCD和文獻(xiàn)[10]的平均檢測(cè)時(shí)間分別為1 453和201 ms，本文算法只有163 ms。

5.2討論

在4.2節(jié)中由于獲取P1的隨機(jī)性，筆者通過改變參數(shù)d就能使本算法能在帶有曲#65380;直線段等噪聲的圖像檢測(cè)出不同半徑的圓(或殘缺圓)。這就保證了算法的可靠性。

本算法#65380;文獻(xiàn)[10]中的算法和RCD均是由Tε和λ控制檢測(cè)精度。故本文算法精度與RCD和文獻(xiàn)[10]中的算法相同。

6結(jié)束語

本文提出了一種基于局部搜索的隨機(jī)多個(gè)圓檢測(cè)算法。與文獻(xiàn)[10]一樣，該算法僅要求給出整個(gè)圖像空間的0#65380;1數(shù)字化信息，但它不需要梯度方向信息，對(duì)較殘缺圓#65380;不連續(xù)圓和圖像空間中包含噪聲線段的情形也能較好地適應(yīng)，其檢測(cè)速度不僅較文獻(xiàn)[6]快一個(gè)數(shù)量級(jí)而且在孤立#65380;半連續(xù)噪聲不低于所有噪聲的80%時(shí)，檢測(cè)速度比文獻(xiàn)[10]大約快20%。它特別適合于布局先驗(yàn)知識(shí)圖中圓的個(gè)數(shù)特別多的檢測(cè)問題。

參考文獻(xiàn):

[1]劉占偉，滕弘飛.基于人智—圖形—計(jì)算的布局設(shè)計(jì)方法[J].大連理工大學(xué)學(xué)報(bào)，2006，46(2):228－234.

[2]HUDA L D， LAINE W， et al. Circle recognition through a 2D Hough transform and radius histogram[J]. Image and Vision Computing， 1999，17(1):15－26.

[3]SOOKIM H， HWANKIM J. A two－step circle detection algorithm from the intersection chords[J]. Pattern Recognition Letters， 2001，22(6－7):787－798.

[4]PENG Yen－yin. A new circle/ellipse detector using genetic algorithms[J]. Pattern Recognition Letters， 1999，20(7):731－740.

[5]XU L，OJA E.Randomized Hough transform(RHT):basic mechanisms，algorithms，and computational complexities[J].CVGIP:Image Understan－ding， 1993，57(2):131－154.

[6]CHEN T， CHUNG Kuo－liang. An efficient randomized algorithm for detecting circles[J]. Computer Vision and Image Understan－ding， 2001，83(2):172－191.

[7]束志林，戚飛虎.一種新的隨機(jī)Hough快速圓檢測(cè)算法[J].計(jì)算機(jī)工程，2003，29(6):87－88.

[8]YU Qiao， ONG S H. Connectivity－based multiple－circle fitting[J]. Pattern Recognition， 2004，37(4):755－765.

[9]王成儒，胡正平，練秋生.一種高效的混合圓/橢圓檢測(cè)方法[J].貴州工業(yè)大學(xué)學(xué)報(bào)，2002，31(4):100－103.

[10]黎自強(qiáng)，滕弘飛.廣義Hough變換:多個(gè)圓的快速隨機(jī)檢測(cè)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18(1):27－33.

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