基于輪廓矢量化形狀匹配快速算法

等:基于輪廓矢量化的形狀匹配快速算 結(jié)果規(guī)范化用相對長度差來描述尺寸的差異度其定義可 tl12

|

L2

(

n(L，L1θ12l12反映了兩條線段的總體差異程度。由此可見線段(向量)的匹配過程比較簡便。如何將這一特性應(yīng)用于形狀

3思路 根據(jù)尺寸因素匹配。設(shè)lili'分別為輪廓S和矢量化后各自對應(yīng)的第i條向量的模則li與li' l(

本文算法的思想是通過對輪廓

線點集的離散化采樣部分點依次相連構(gòu)成向量群

lili

lili ＜條線段去近輪廓曲線從而使其線性化最后結(jié)合11節(jié)

=(=

( ( i i

(的線段匹配計算出相似度。于是問題就轉(zhuǎn)換為如何確

lili0 >0 (離散點之間的采樣間隔。文獻(xiàn)［6］根據(jù)匹配輪廓之間的相對長度(相對弧長)來獲取與源圖特征點相對應(yīng)的目標(biāo)圖的期望點;但是源圖中的特征點必須是圓弧過度到線段或者線段過度到線段的頂點因此該算法只適用于由線段和弧構(gòu)成的簡單圖形。

其中:δ為最大長度差它用來擴大局部輪廓的不相似性。下文中的Δ也是相同作用。本文取δ03。2根據(jù)角度因素匹配。θisisi+1titi+1i1，23，n1的夾角，θnsns1tnt1的夾角從相對性上考慮θi0時認(rèn)為兩向量完全相似θiΔ時則完全不同本文方法是如圖2所示從區(qū)域A中心點O出發(fā)以 因此S與T中對應(yīng)向量的相似度值θ(i)可以由式(6)計算0，逆時針箭頭所示方向每隔一個固定角度γ

發(fā)出射線射線與輪廓的交點作為特征點集ppp，…

θ(i)= ( 相鄰兩點連成向量組成沿逆時針方向的嚴(yán)格近輪廓的向量群即{12p2334…}。采樣角γ的大小決定了向量的個數(shù)n(n=2π/γ)也決定了向量群最終近輪廓的精度，而本文會在實驗部分對其大小的確定作進一步地分析。

θ＞其中:Δ為最大角度本文取Δ=5°ρ兩種思路均有一定的可行性為使最后的匹配結(jié)果能綜合尺寸和角度兩方面因素輪廓S與T的相似度 可由上述ρS種相似度求和所得1 ∑［τθ(i)+(1τ)l(i) (S ni

!b

a

其中:τ為角度權(quán)重因子。通過實驗發(fā)現(xiàn)輪廓曲線的軌跡與角度因素關(guān)系較大本文取τ06。圖1線段的匹 圖2輪廓離散關(guān)于中心點O的確定提出了模板累加法將模板為3×3的方陣對原始數(shù)據(jù)作卷積運算。當(dāng)累加次數(shù)達(dá)到一定時會在圖形中間某處出現(xiàn)最大值該點作為中心點;但是該算法需要多次對圖形內(nèi)部的像素點進行累加速度不夠快。本文將區(qū)域A的重心作為中心點(x0y0)計算如下:

所謂的平移尺度和旋轉(zhuǎn)不變性是指以源圖為匹配模板，當(dāng)目標(biāo)圖像發(fā)生任意的平移縮放和旋轉(zhuǎn)變化時匹配的結(jié)果不受影響。顯然不變性對于算法的合理性提出了更高的要求。中的形狀上下文法考量的是目標(biāo)邊緣點的相互位置關(guān)系不涉及點的絕對位置所以對平移具有不變性。］利用模板累加法確定邊界匹配起始點從而保證旋轉(zhuǎn)x=1∑q 不變性;文獻(xiàn)［7］提出了類似的方法 SqA i ( y=

∑q(

本身的銳化程度有關(guān)?？傮w來說現(xiàn)有文獻(xiàn)中提到的關(guān)于域A的面積。與求輪廓點重心的方法相比式(4)算得的中心根據(jù)12節(jié)假設(shè)源圖的輪廓S矢量化后得到的n個向量矢量化后得到的向量群為t1t2，t2t3，t3t4，…，tnt1圖3顯示出了經(jīng)矢量化后的輪廓S和輪廓T模型為表述方便每種輪廓

本文基于輪廓矢量化的算法利用了向量的平移不變性使得整體輪廓無論怎樣平移都對匹配結(jié)果不產(chǎn)生影響。為了消除圖形的尺寸大小對于匹配結(jié)果的影響算法在匹配之前采用對形狀歸一化的方法:以最小包絡(luò)圓圓心為基點將圖形進行縮放使得縮放后圖形的最小包絡(luò)圓為一個單位圓。 計算機應(yīng)用研 第31本文的匹配算法主要用于撓性印刷電路板(flexibleprincircuitFPC)定序列排列排序中形狀發(fā)生偏轉(zhuǎn)的0和0偏轉(zhuǎn))可在匹配之前將源圖以中心點O為旋轉(zhuǎn)中心轉(zhuǎn)至相應(yīng)

余匹配值大多在0%以下這說明本文的算法對于檢測兩種不同批次的焊盤形狀有較強的區(qū)分性。 xi→ocosαsin x→ 6 = × (yi→o'sinαcos yi→o 表1不同批次焊盤的匹配結(jié) 其中xi→o'，yi→oxi→o，yi→o分別表示輪廓上的任意點pi相對于中心點旋轉(zhuǎn)后和旋轉(zhuǎn)前的坐標(biāo)，α表示偏轉(zhuǎn)角。最后根據(jù)為驗證文中算法的有效性選取某型號FPC板上的焊盤圖像預(yù)處理先提取表面再得到輪廓以此作為實驗對象。圖4為某焊盤金面到輪廓的過程示意圖。4本文的1.2節(jié)中提到采樣角γ的大小決定了近輪廓的向量個數(shù)n，從而反映了矢量化的精度而這個精度勢必會影響

44. 51. 49. 47. 39. 30. 41. 44. 50. 49. 58. 47. 41. 48. 51. 50. 56. 54. 34. 30. 51. 49. 49. 56. 45. 51. 31. 54. 47. 58. 54. 45. 38. 41. 42. 39. 47. 34. 51. 38. 31. 39. 30. 41. 30. 31. 41. 31. 41. 48. 51. 54. 42. 39. 30. 33為了驗證文中算法對形狀匹配的綜合性能本實驗選擇實驗1中的兩組輪廓作為實驗對象結(jié)合.2節(jié)中的方法選取輪廓上的一定量特征點分別使用簡化后的極坐標(biāo)法平均f距離(MD)法形狀上下文法以及本文方法進行匹配運算考慮到極坐標(biāo)法和形狀上下文法對各自的特征點數(shù)量較敏感均選取4個特征點其余方法選用2個特征點匹配結(jié)果和各自所耗時間如表2所示2或選擇兩組種類不同的相似焊盤為實驗對象(第一組命名為1和2，第二組命名為輪廓3和4每組中均有一個缺陷焊盤。采用陸續(xù)增大n的方法計算對應(yīng)的相似度。圖5為輪廓示意圖和所得的實驗數(shù)據(jù)曲線。從圖5(a)(b)

匹配結(jié)果ρρρ12396.80.84.ρρρ12396.80.84.0.0.0.———0.0.0.94.89.90.4.4.4.61.59.55.0.0.0.1 3 1

1!""0&01!""0&0!""0&)*)*(a)輪廓1和2的匹配結(jié) (b)輪廓3和4的匹配結(jié)5理論上向量個數(shù)n越大所得的匹配結(jié)果越精確。但這會導(dǎo)致兩個問題:a)運算速度變慢;b)匹配結(jié)果出錯。應(yīng)該說運算復(fù)雜度與向量個數(shù)呈線性增長關(guān)系這是第一個問題產(chǎn)生的原因;而對于第二個問題當(dāng)n過大時由于原始輪廓像素點個數(shù)有限無法提供足夠精細(xì)的離散點使之每一個與中心點的連線夾角都等于γ。鑒于此在實用中一般先通過實驗對同一批次的焊盤確定出使其相似度值穩(wěn)定的向量個數(shù)范圍如圖5(a)中的2～0再計算它們對應(yīng)相似度的算術(shù)平均值ρ將其與不同向量個數(shù)算得的相似度值進行比較最接近該值的對應(yīng)向量個數(shù)作為最后確定的n。為了驗證本文算法的有效性選用八種不同批次的正常焊盤各自進行匹配。焊盤樣例編號如圖6所示匹配的結(jié)果如表1所示。觀察表1可知除了自匹配(相似度為0%)以外其

從表2中可以看出似度數(shù)值都比較大這是因為C上的焊盤本身形狀都很相似;從人眼上判斷一般認(rèn)為輪廓1和2比輪廓3和4相似即ρ12＞34而輪廓1和3屬于不同種類的焊盤其相似度值13理應(yīng)更小顯然上述兩種方法都沒有很好地給予區(qū)分。匹配速度方面按照文獻(xiàn)介紹的極坐標(biāo)法實際上需要選取焊盤表面上的所有像素點作為特征點其數(shù)量大約為本實驗的0～5倍因此其匹配速度已經(jīng)沒有優(yōu)勢;而形狀上下文法在本實驗中耗時最多;至于MD法其最大的缺點在于無法用百分比定量地評價相似度。綜合以上實驗結(jié)果可知文中焊盤形狀匹配算法的綜合性能較好平均匹配耗時小于.6s可實際用于焊盤金面的形狀匹配但該算法不能應(yīng)用于凹痕非常劇烈的形狀中，這會導(dǎo)致輪廓線性化異常;另外需通過實驗確定近向量的個數(shù)也比較麻煩這兩方面仍然需要提高。在現(xiàn)有的形狀匹配算法基礎(chǔ)上提出了一種基于輪廓矢量化的算法。對待匹配圖像進行預(yù)處理先提取輪廓上的特征點將其連成向量再進行匹配運算。通過焊盤的實例運算結(jié)果表明文中算法對相似度的計算有一定的可靠性且匹配速度快具有一定的推廣性。 (下轉(zhuǎn)第1251頁)李等:一種融合多模式單演特征的人臉識別方 充分利用了方向和幅值的分類能力。在Ｒ和SEL人臉庫上的實驗證明本文MMP和MP能夠有效捕獲圖像中有利于分類的特征同時融合兩種模式的方法能夠有效地增強特征的判別能力。由于采用分塊子模式策略該方法在處理過程中有效避免了同一時間處理高維特征帶來的小樣本問題。［1］WANGDaran，LIUHuingANGAnzhi，etal．Pefoance．y6［2］BEＲPN，HESPANHAJPKＲIEGMANDJ．s．fisherfaces:recognitionusingclassspecificlinear．Ine，1997，19(7):7110［3］OJALATEM，MAENPAATuiresolutiongraytern．Enegence，2002，24(7):9717．［4］GUOZhenhua，ZHANGLeiZHANGDAcpletedodeingoflocalbinarypatternoperatorfortextureclassification［J．EETransonageProcessing201，19(6):16573［5］TANoyangTＲIGGSBEnhancedlocaltexturefeaturesetsforconditionEonageProcessing201，19(6):16350ieSANChutDagedescripto．ETransonPaenysisandMaeInligence201032(10):17050．［7］GONGDayi，LIShuaoXANGn．Facerecognitionusing

weberlocaldescripto//Procofthe1stAanConferenceonPatternnn．2011:5892［8］LUChengunECSLEＲ．Gaborfeaturebasedclassificationusingtheenhancedfisherlineardciinatedlforfacerecognitio．Enegence，2002，11(4):4676．nWenetbinarypatternhitgamsequence(S):anovelnonstatisticaldlforfacerepresentationandrecognition［C］//Procofthe5thInternationalConferenceonCpurn．2005:7861［10］ZHANGLinZHANGLeiGUOZhenhua，etal．MonogenicPanewapproachforrotationinvarianttextureclassification［C］//Procofthe10thInternationalConferenceonageProcessing．2010:26770．oyngZENGimingetotepoallocalmonogenicbinarypatternsforfacialexpressionrecognitio．ESglProcessingLetters，2012，19(5):2436［12］EBEGM，SEＲGThemonogenicsignal［J．ETransonSgnalProcessing200，49(12):31364［13］楊海燕劉國棟MBLBP算子和urPCA算法的人．47354739．與．6［15］TAKEDAHFAＲSIUSMILANFAＲ．nlregressionforageprocessingandreconstructio．ETransonIaeProcessing，2007，16(2):3466．［16］張寶昌．人臉特征提取和非線性識別方法的研究D．哈爾濱:哈爾濱工業(yè)大學(xué)，2006．1238頁［1］周瑜劉俊濤白翔．形狀匹配方法研究與展望J．自動化學(xué)報2012，38(6):8890gskeleton．puterVsnandIagesg20080(3):3265［3］XEJun，HENGPAMUBAＲAKSShapehngandodelingcontext．necognton20084117567XiangYANGweiLONGINnofcontourpartsbasedonshapeiilaityJ．Pattencn，2008，41(7):21899［5］HUNGMH，HSIEHCH，KUOC．Styretrievalofshapeesbasedondatabaseclassificatio．JlofslComnesn20067(5J．華南理工大學(xué)學(xué)報自然科學(xué)版，2006，342)771［7］張國敏殷建平祝恩等基于極坐標(biāo)區(qū)間運算的2D．0．［8］XUGang，YANGnn．Fastshapehingusingahybridmode//ProcofInternationalConferenceonCpur

ringandhny．2009:2471［9