基于局部搜索快速隨機檢測多個圓

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

關鍵詞:廣義霍夫變換; 多個圓檢測; 直線擬合

中圖分類號:TP301.6文獻標志碼:A

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

0引言

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

1隨機多個圓檢測效率分析

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

2相關的理論

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

定義1在圖像空間中，圓和噪聲像素點統稱為圖像點，其他點為非圖像點。

性質1假定圖像空間中ω個數字圓的像素數分別為N1，N2，…，Nω，并且圖像空間中噪聲點數m是ω個數字圓的像素數和的τ倍，則隨機采樣一點在同一圓上的概率約是無噪聲時的1/(1 +τ)。

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

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

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

5.2討論

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

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

6結束語

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

參考文獻:

[1]劉占偉，滕弘飛.基于人智—圖形—計算的布局設計方法[J].大連理工大學學報，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]束志林，戚飛虎.一種新的隨機Hough快速圓檢測算法[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]王成儒，胡正平，練秋生.一種高效的混合圓/橢圓檢測方法[J].貴州工業大學學報，2002，31(4):100－103.

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

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”