一種新的高速圓形匹配算法

黃廉真，吳曉軍，康文雄

(1.哈爾濱工業大學深圳研究生院，518055 深圳廣東;2.華南理工大學自動化科學與工程學院，510640 廣州)

一種新的高速圓形匹配算法

黃廉真1，吳曉軍1，康文雄2

(1.哈爾濱工業大學深圳研究生院，518055 深圳廣東;2.華南理工大學自動化科學與工程學院，510640 廣州)

針對現有圓形匹配算法無法同時滿足高速度、低內存消耗以及高精度要求的情況，提出了一種基于擊中率的新型圓形匹配算法.算法引入以輪廓作為匹配特征信息的圓環采樣模板，匹配的結果由擊中率表征，并進一步根據搜索目標與定位區域的灰度相關性剔除誤檢對象.實驗表明，算法能夠實現毫秒級快速定位，且在內存消耗和可靠性方面都獲得較好的性能.

高速目標定位;圓形匹配;擊中率

圖像及視頻中的圓形匹配是計算機視覺技術中的一項重要研究內容，廣泛應用于目標識別、視頻跟蹤、工件定位等領域.根據算法實現基本原理的不同，圓形匹配算法可分為Hough變換和模板匹配兩類.以標準Hough變換(SHT)為基礎，研究人員提出了眾多改進算法，例如改進Hough變換(IHT)［1－2］、隨機 Hough 變換(RHT)［3］、3 點橢圓檢測算法［4－5］、利用梯度方向信息檢測圓算法［6］以及基于子圖分解的多圓/橢圓檢測算法［7］等.然而，由于處理對象為大量的輪廓信息，故都會存在運算量大和內存消耗大兩方面的不足.模板匹配在目標識別和精確定位等領域中具有廣泛應用，根據匹配信息的不同，模板匹配算法有基于灰度相關和基于幾何特征兩類.基于灰度相關算法根據圖像灰度信息進行匹配，算法原理簡單，但其抗干擾性差.基于幾何特征的模板匹配算法以模板的幾何基元［8－9］，如邊緣、角點、模板重心等作為匹配信息進行匹配.如基于Hausdorff距離的模板匹配算法［10］和基于廣義霍夫變換的模板匹配算法［11］等，此類算法的魯棒性很強，模板匹配算法的實用性強，但其運算量大.為此，模板匹配算法經常利用金字塔分割法來提高計算速度，然而這樣也帶來了內存消耗劇增的問題.

針對上述問題，本文提出基于擊中率的圓形匹配算法，算法基于圖形輪廓信息實現快速圖形匹配和定位，算法引入圓環采樣模板、矩形采樣區和擊中率概念，運算則以整型加減運算和邏輯運算為主.計算量幾乎恒定，與圖像的復雜度和需要檢測的目標的數量和大小無關;而且需要搜索的目標圓的半徑越大，則運算速度越快.算法具有快速識別定位、低內存消耗、高穩定性的特點，并具有一定魯棒性，屬于基于幾何特征的模板匹配算法范疇.實驗證明，算法能夠取得耗時“毫秒級”的效果，同時在內存消耗等方面也具有較好的性能.

1 算法原理

1.1 圓環采樣模板

圓環采樣模板由兩個同心圓構成圓環，在圓環內有n個等距分布的矩形采樣區，即

式中:r為小圓半徑;R為大圓半徑;(x，y)為圓心坐標.h為矩形采樣區的高;w為寬;(xi，yi)為n個矩形采樣區中心.

圖1是一個由8個矩形采樣區構成的圓環采樣模板，其中對稱的灰色矩形為矩形采樣區.圓環采樣模板是以圓心為原點，所有矩形采樣區內點的坐標集合.

圖1 圓環采樣模板

1.2 擊中率

本文通過n點確定一個圓，圓環采樣模板的每一個矩形采樣區內第1個被檢測到的輪廓點都被認為關鍵點，同時認為該矩形采樣區被擊中.當在圖2中灰色矩形采樣區內找到關鍵點后，該矩形采樣區內其他所有的點都將被忽略，無論這些點是否為輪廓點，同時認為在圓環采樣模板的圓環內有目標圓弧長l，如圖2所示.

當圓環采樣模板有m個矩形采樣區被擊中，則擊中率ρ為

圖2 矩形采樣區被擊中示意圖

理想情況下，當被檢測圖形的中心與圓環采樣模板的圓心重合且半徑滿足要求，則擊中率必為1.否則，擊中率就會比較低，如圖3所示.圓環采樣模板的大圓和小圓的半徑差越小，其篩檢能力越強.

圖3 各種情況下圓環采樣模板的擊中率

1.3 遮斷容忍性

遮斷容忍性，是指算法允許輪廓點部分丟失和圖形被部分遮擋.設丟失的輪廓點總數為s，丟失率為σ.

根據擊中率的分析，當要求擊中率為1時，僅需要每個矩形采樣區中都包含有至少一個輪廓點，其他的輪廓點則可忽略.因此，極限情況下

也即是n點確定一個圓，圖4中4個示例的擊中率分別為 1，0.875，1，1.圖 4 表明即使輪廓點部分丟失也能準確檢測對象.當圖形被部分遮擋時，算法可通過降低擊中率閾值實現對象的檢測值，典型情況如圖4(b)所示.

圖4 模板在不同丟失輪廓情況下對圓的檢測示意圖

根據圓環采樣模板的遮斷容忍性，合理設置圓環采樣模板的參數以及擊中率閾值，可以使得算法在惡劣情況下依然能夠檢測目標.

2 快速圓定位實現流程

本文通過采用C++語言實現算法，并對50幅大小為640*480的各異圖像進行測試，驗證算法的性能.圖5(a)為其中一幅待處理圖像，圖像中有半徑各異的待檢測3個同心圓，如圖5(b)～(d)所示.

圖5 試驗圖片以及3個待檢測的半徑不等近似圓

算法實現流程為:

1)對圖片進行一定比率p的縮放，減少運算量.p主要由模板參數以及實際應用的計算時間要求決定.同時為了確保在縮放后R＞r，p必須滿足p≤(R-r)/2.p越小，則內存消耗越小，速度越快，但精確度和準確性同時也減弱.本文設p為4.圖像的縮放方式采用如圖6所示的方式，即取左上角P11替代整個區域.

圖6 縮放比率為4的示意圖

2)對縮放后的圖像采用Canny檢測算子提取圖像輪廓信息.

3)根據設置的圓環采樣模板參數構建圓環采樣模板.

4)用圓環采樣模板在整幅輪廓圖像中以間隔方式滑動搜索.滑動間隔q由縮放后的圓環大小圓半徑決定，q的取值需滿足q≤(R'-r')/2.此時，圓環采樣模板在滑動計算時，中心位置的取值為

式中:R'、r'分別為縮放后圓環大小圓半徑.本文根據實際情況設q為3.

5)每當采用圓環采樣模板進行搜索獲得的擊中率值高于設定閾值時，則返回當前圓環采樣模板的中心和各矩形采樣區中獲得的關鍵點，并以這些關鍵點確定圓的半徑和圓心，然后，按照式(1)繼續搜索，直至搜索結束.

6)對返回的一系列圓進行處理.圓心位置以及半徑大小相近的圓認為是同一個圓，并取這些圓的圓心和半徑平均值作為該圓的圓心和半徑.

7)采用差方和(SSD)法計算步驟6)返回的圓心對應的圖形與需檢測目標圖形的灰度相關性.如果相關性滿足設定值則認為在該位置附近存在目標圖形，否則丟棄.

3 實驗結果與性能分析

3.1 快速定位

當建立模板后，算法的計算耗時主要集中在輪廓提取和對目標的搜索.本文通過將圖像縮小至1/16，模板以間隔為3的方式滑動，使得計算量縮小為1/144.另外，如果計算過程中發現擊中率低于設定停止閾值則停止計算.整個算法的主要運算操作是整數加減乘法和邏輯比較，算法執行效率非常高.表1是整個程序各本算法主要步驟的耗時數據和文獻［14］算法的總耗時數據，該數據的取得是由Pentium Dual-Core CPU E5200 2.5 GHz，1.98 GB內存的計算機進行運算得到.由表1中數據可知，本文算法的計算耗時幾乎不受圓半徑大小影響.對比兩種算法，當圓半徑比較大的時候，本文算法的快速性能優勢非常明顯.當半徑較小時，兩者性能相近.

表1 各主要步驟耗時統計數據 ms

3.2 高可靠性

在實驗過程中，為了避免出現漏檢和誤檢情況，算法適當降低擊中率閾值，同時在后期對檢測的對象采用差方和(SSD)進行檢驗.表2為定位3種不同半徑圓的結果.

表2 不同半徑圓的檢測結果

由于算法以輪廓作為匹配特征信息，因此算法對光照的變化不敏感.圖7(a)是正常光照情況下圖像的定位效果圖;圖7(b)、(c)則是光照不強和光照過強情況下的定位效果;圖7(d)則是在受到部分遮擋時的檢測效果.

3.3 低內存消耗

本文算法的內存消耗主要用于裝載灰度圖、存儲縮放后灰度圖及輪廓圖，構建圓環采樣模板.相比于Hough變化和金字塔分割法加速，本算法具有明顯優勢，表3中列出了當處理640*480圖像時，本文算法、Hough變化、金字塔分割加速的主要內存消耗的比較數據.從表3中可以看出本文算法可以大大減低內存空間的消耗.

圖7 算法在受到光照干擾或部分遮擋時的檢測效果

表3 在處理640*480圖像時本文算法與Hough變化和金字塔分割加速的內存消耗比較

4 結論

1)本文提出基于擊中率的圓形匹配算法以輪廓為特征信息進行匹配，實現快速識別定位.試驗和理論證明，算法能夠取得耗時“毫秒級”快速定位效果，同時在內存消耗和可靠性方面都取得較好的性能，具有較強的抗干擾能力，對光照變化不敏感.

2)算法的實現只需要整數加減乘法和邏輯比較，而且內存消耗低，因此，算法非常適合應用于嵌入式系統，例如利用FPGA進行實現.除此，在自動化運用過程中，由于本算法具有快速定位的特點，因此利用其作為一種輔助判斷方法.

3)圓環采樣模板計算依據是輪廓信息，因此當輪廓信息雜多，可能會出現多檢或漏檢，對此算法可根據實際應用附加其他特征信息進行2次驗證，提高準確定性.另外，算法對參數的設置比較敏感，需要經過實驗選擇合適參數模板.

［1］KIM Heung-Soo，KIM Jong-Hwan.A two-step circle detection algorithm from the intersection chords［J］.Pattern Recognition Letters，2001，22(6/7):787 －798.

［2］YIN Peng-yeng.A new circle/ellipse detector using genetic algorithms［J］.Pattern Recognition Letters，1999，20(7):731－740.

［3］XU L，OJA E.Randomized Hough transform:basic mechanisms，algorithms and computational complexities［J］.Computer Vision Graphic Image Process:Image understanding，1993，57(2):131 －154.

［4］YOO J H，SETHI I K.An ellipse detection method from the polar and poles definition of conics［J］.Pattern Recognition，1993，26(2):307－315.

［5］陳燕新，戚飛虎.一種新的基于隨機Hough變換的橢圓檢測方法［J］.紅外與毫米波學報，2000，19(1):43－47.

［6］陳燕新，戚飛虎.利用梯度方向信息的隨機Hough變換［J］.紅外與毫米波學報，1998，17(5):375－379.

［7］胡正平，王成儒，練秋生.基于圖像分解的快速多圓/橢圓檢測方法［J］.儀器儀表學報，2002，23(3):292－294.

［8］SHARK L K，KUREKIN A A，MATUSZEWSKI B J.Development and evaluation of fast branch-and-bound algorithm for feature matching based on line segments［J］.Pattern Recognition，2007，40(5):1432－1450.

［9］PARAMANAND C，RAJAGOPALAN A N.Efficient geometric matching with higher-order features［J］.Optical Society of America，2010，27(4):739－748.

［10］HUTTENLOCHER D P，KLANDERMAN G A，RUCKLIDGE W J.Comparing images using the hausdorff distance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15(9):850 －863.

［11］ULRICH M，STEGER C，BAUMGARTNER A.Realtime object recognition using a modified generalized Hough transform ［J］. Pattern Recognition，2003，36(11):2557－2570.

［12］TANIMOTO S L.Template matching in pyramids［J］.ComputerGraphics and Image Processing， 1981，16(4):356－369.

［13］STEGER C，ULRICH M，WIEDEMANN C.機器視覺算法與應用［M］.楊少榮，吳迪靖，段德山，譯.北京:清華大學出版社，2008.

［14］鄒光華.基于幾何特征的快速模板匹配算法［D］.哈爾濱:哈爾濱工業大學，2011.

A new algorithm for rapid circle matching

HUANG Lian-zhen1，WU Xiao-jun1，KANG Wen-xiong2

(1.Harbin Institute of Technology Shenzhen Graduate School，518055 Shenzhen，Guangdong，China;2.College of Automation Science and Engineering，South China University of Technology，510640 Guangzhou，China)

For the existing circle matching algorithms could not simultaneously meet the requirements of highspeed，low memory consumption and high accuracy，a new algorithm based on hit rate was proposed.The Ring Sample Template was introduced and its edge was used as matching information.The matching result was determined by hit rate，and the Grey Scale Correlation between source and destination was calculated to eliminate wrong destination.The result showed that the algorithm could get destination position in milliseconds，and had good performances on both memory consumption and reliability.

rapid target locating;circle match;hit rate

TP391

A

0367－6234(2012)07－0087－05

2011－09－13.

國家自然科學基金資助項目(61105019);廣東省自然科學基金資助項目(S2011040002474);廣東省科技計劃資助項目 (2011B010200023);華南理工大學中央高?；究蒲袠I務費專項資金資助項目(2012ZZ0108);深圳市南山區科技研發資金資助項目(南科院201002);數字制造裝備與技術國家重點實驗室資助項目(DMETKF2009013).

黃廉真(1985—)，男，碩士.

康文雄，auwxkang@scut.edu.cn.

(編輯 張 紅)