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

黃廉真，吳曉軍，康文雄

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

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

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

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

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

高速目標(biāo)定位;圓形匹配;擊中率

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

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

1 算法原理

1.1 圓環(huán)采樣模板

圓環(huán)采樣模板由兩個同心圓構(gòu)成圓環(huán)，在圓環(huán)內(nèi)有n個等距分布的矩形采樣區(qū)，即

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

圖1是一個由8個矩形采樣區(qū)構(gòu)成的圓環(huán)采樣模板，其中對稱的灰色矩形為矩形采樣區(qū).圓環(huán)采樣模板是以圓心為原點，所有矩形采樣區(qū)內(nèi)點的坐標(biāo)集合.

圖1 圓環(huán)采樣模板

1.2 擊中率

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

當(dāng)圓環(huán)采樣模板有m個矩形采樣區(qū)被擊中，則擊中率ρ為

圖2 矩形采樣區(qū)被擊中示意圖

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

圖3 各種情況下圓環(huán)采樣模板的擊中率

1.3 遮斷容忍性

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

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

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

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

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

2 快速圓定位實現(xiàn)流程

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

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

算法實現(xiàn)流程為:

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

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

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

3)根據(jù)設(shè)置的圓環(huán)采樣模板參數(shù)構(gòu)建圓環(huán)采樣模板.

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

式中:R'、r'分別為縮放后圓環(huán)大小圓半徑.本文根據(jù)實際情況設(shè)q為3.

5)每當(dāng)采用圓環(huán)采樣模板進(jìn)行搜索獲得的擊中率值高于設(shè)定閾值時，則返回當(dāng)前圓環(huán)采樣模板的中心和各矩形采樣區(qū)中獲得的關(guān)鍵點，并以這些關(guān)鍵點確定圓的半徑和圓心，然后，按照式(1)繼續(xù)搜索，直至搜索結(jié)束.

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

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

3 實驗結(jié)果與性能分析

3.1 快速定位

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

表1 各主要步驟耗時統(tǒng)計數(shù)據(jù) ms

3.2 高可靠性

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

表2 不同半徑圓的檢測結(jié)果

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

3.3 低內(nèi)存消耗

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

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

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

4 結(jié)論

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

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

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

［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］陳燕新，戚飛虎.一種新的基于隨機(jī)Hough變換的橢圓檢測方法［J］.紅外與毫米波學(xué)報，2000，19(1):43－47.

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

［7］胡正平，王成儒，練秋生.基于圖像分解的快速多圓/橢圓檢測方法［J］.儀器儀表學(xué)報，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.機(jī)器視覺算法與應(yīng)用［M］.楊少榮，吳迪靖，段德山，譯.北京:清華大學(xué)出版社，2008.

［14］鄒光華.基于幾何特征的快速模板匹配算法［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，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.

國家自然科學(xué)基金資助項目(61105019);廣東省自然科學(xué)基金資助項目(S2011040002474);廣東省科技計劃資助項目 (2011B010200023);華南理工大學(xué)中央高校基本科研業(yè)務(wù)費專項資金資助項目(2012ZZ0108);深圳市南山區(qū)科技研發(fā)資金資助項目(南科院201002);數(shù)字制造裝備與技術(shù)國家重點實驗室資助項目(DMETKF2009013).

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

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

(編輯 張 紅)