徐貴力，趙　妍，姜　斌，王正盛，李開宇，郭瑞鵬

(南京航空航天大學自動化學院，江蘇南京210016)

?

基于局部尺度特征描述和改進DTW技術的局部輪廓匹配算法

徐貴力，趙妍，姜斌，王正盛，李開宇，郭瑞鵬

(南京航空航天大學自動化學院，江蘇南京210016)

摘要：基于輪廓的圖像匹配是計算機視覺領域中的重要問題，但是目前尚未有較成熟的算法能夠很好地解決局部輪廓匹配問題及非相似變換和非剛體變換引起的輪廓形變問題.根據(jù)局部輪廓結(jié)構在產(chǎn)生形變時具有相對穩(wěn)定性的規(guī)律及融合輪廓局部信息和全局信息的輪廓描述思想，本文提出了一種具有尺度、旋轉(zhuǎn)、平移不變性，形變魯棒性和初始點無關性的局部尺度輪廓描述算法.在此基礎上，針對線性匹配方法效果不佳以及傳統(tǒng)DTW技術約束路徑的線性度不滿足輪廓采樣特性要求的問題，提出一種基于改進DTW技術的輪廓匹配算法，即結(jié)合輪廓采樣特性設置九宮格的路徑約束條件，以旋轉(zhuǎn)角度為參數(shù)，計算全局最佳匹配路徑.實驗結(jié)果表明，對于存在尺度、平移、旋轉(zhuǎn)及形變關系的兩輪廓，該方法能較好地實現(xiàn)輪廓間的局部匹配，并且其匹配準確率平均約為92%，較HD算法提高了30%，較傳統(tǒng)DTW算法提高了26%.

關鍵詞：計算機視覺;輪廓描述;局部尺度;局部輪廓匹配;動態(tài)時間規(guī)整;形變

1　引言

不同于紋理、顏色等其它基本特征，輪廓形狀是紅外、雷達和可見光等異源圖像間的共性特征，且具有較好的不變性［1］，因此，輪廓匹配在導航制導、目標跟蹤、醫(yī)療診斷等領域得到廣泛的應用.輪廓匹配算法通常由兩部分組成:輪廓描述和輪廓匹配.

基于輪廓點空間位置關系的輪廓描述方法是近年來比較重要的輪廓描述方法，它通過對輪廓點序列的空間位置分布關系的統(tǒng)計來描述輪廓，取得了很好的描述效果，學者們圍繞著該方法所涉及的統(tǒng)計范圍、統(tǒng)計方法和統(tǒng)計信息這三個問題展開研究，設計出了多種基于空間位置關系的輪廓描述方法.Xin Shu等［2］根據(jù)輪廓點在極坐標下的分布關系提出了一種輪廓點分布直方圖(CPDH)的描述算法; TU等［3，4］定義一組信息特征，分別在小的局部范圍內(nèi)和整個形狀輪廓上考察目標輪廓點及其全局鄰域輪廓點之間夾角的統(tǒng)計關系.這類算法的描述符設計簡單有效，具有較好的幾何不變性和準確的輪廓描述能力，是研究界的重點，但是基本上只能處理簡單閉合的輪廓.基于多尺度理論的輪廓描述方法主要通過曲線的凹凸特性來判定輪廓的性質(zhì)，代表性方法有Felzenszwalb等［5］提出的輪廓樹描述方法，采用層次化的描述方法表示不同分辨率上獲得的輪廓信息; Bartolini等［6］提出了一種基于傅里葉變換的描述子WARP，它結(jié)合傅里葉系數(shù)的相位信息和振幅信息來描述輪廓，使得描述更加精確;牛慶肖等［7］提出一種基于八方向鏈碼和快速傅里葉變換的輪廓描述方法，該描述具有旋轉(zhuǎn)、尺度和平移不變性.輪廓的簡單幾何變換只是關系到輪廓頻域描述子的簡單操作，但是不能很好地描述出現(xiàn)遮擋情況的輪廓.總體來看，較好的輪廓描述方法必須要融合輪廓的全局信息和局部信息，這也將是本文研究的重點.

輪廓匹配的過程可以認為是在解空間中尋求最優(yōu)解使得目標函數(shù)最小的過程，代表性方法有Chui等［8，9］在迭代最近點(ICP)算法［10］的基礎上提出基于薄板樣條的魯棒點匹配算法(TPS-RPM).該算法由兩部分組成:更新匹配關系和根據(jù)匹配關系更新形變參數(shù)，TPSRPM用確定性模擬退火算法多次迭代計算全局最優(yōu)解，以取得更好的匹配效果，但是由于退火算法的固有限制，所以收斂速度慢，另外，由于缺少輪廓空間信息，故在多條復雜輪廓的情況下匹配精度不高.Van等［11］采用蟻群算法搜索最佳匹配，但是匹配效果依賴于蟻群算法的尋優(yōu)能力，有時得不到較好的結(jié)果.Liu等［12］先對輪廓進行采樣，并對采樣點進行特征描述，然后用動態(tài)規(guī)劃求最佳匹配，該方法減小了搜索空間，但是性能受特征點提取算法的制約.

目前輪廓匹配主要存在以下兩個問題:不同視角變換所引起的輪廓形變問題;局部遮擋所導致的局部輪廓匹配的問題.針對以上問題，根據(jù)局部輪廓結(jié)構在產(chǎn)生形變時具有相對穩(wěn)定性的規(guī)律及一個好的輪廓描述方法需融合輪廓局部信息和全局信息的主流思想，本文提出了一種具有尺度、旋轉(zhuǎn)、平移不變性，形變魯棒性和初始點無關性的局部尺度輪廓描述算法:采用保持輪廓局部結(jié)構的特征描述符表示輪廓，根據(jù)局部尺度進行非均勻采樣，每個采樣點的特征矢量描述的是一段輪廓的局部信息，一系列順序采樣點的特征構成輪廓的全局信息;在此基礎上，提出一種基于改進DTW技術的輪廓匹配算法，即結(jié)合輪廓采樣特性設置九宮格的路徑約束條件，在該約束條件下通過逐步判斷和迭代來優(yōu)化出最佳匹配路徑;最后，以旋轉(zhuǎn)角度為參數(shù)，計算全局最短路徑.

2　基于局部尺度的輪廓描述算法

2.1保持輪廓局部結(jié)構的描述符

研究發(fā)現(xiàn)當輪廓發(fā)生形變時，其輪廓上某一點處的特征信息會發(fā)生一定的變化，但是輪廓上其它點相對于該點的位置，即該點之外的輪廓局部結(jié)構，相對保持穩(wěn)定，例如圖1(a)中點A和其局部輪廓上的點B～F，當發(fā)生形變時，如圖1(b)，點A處的特征信息，如曲率、坐標、到質(zhì)心的距離等，明顯產(chǎn)生了變化，相比而言，順序用線段AB～AF的長度構成特征矢量來描述輪廓中A點會更加穩(wěn)定，即A處的特征描述可以表示為矢量(|AB|，|AC|，|AD|，|AE|，|AF|)，即使輪廓發(fā)生一定程度的形變，相應A'處的特征描述矢量變?yōu)?|A'B'|，|A'C'|，| A'D'|，| A'E'|，| A'F'| )，但該矢量變化并不是很大，該特征描述反映的是點A附近的局部結(jié)構信息.

表1中以A和A'處的曲率和局部結(jié)構矢量為例，定量地說明了反映局部結(jié)構的矢量描述穩(wěn)定性更好(0.12＜＜0.98)，對于標量曲率值，其計算方法如式(1)所示，對于局部結(jié)構矢量，其矢量計算公式結(jié)合式(1)和式(2)，其中變量a和b分別表示形變前后的標量特征元素，變量a和b分別表示形變前后的矢量特征，變量ai和bi分別表示形變前后的矢量特征中的第i個特征元素，變量k表示特征矢量中元素的個數(shù);另外，當進行局部輪廓匹配時，不僅需要輪廓的整體信息，更需要結(jié)合其局部信息，將二者融合在描述算法中.

考慮以上兩種情況，并且參考文獻［13］中的輪廓描述方法，本文最終采用保持輪廓局部結(jié)構的描述符表示輪廓.已知輪廓曲線q，設輪廓上一點qi，該點的前一個相鄰點為qi -1，后一個相鄰點為qi +1，其中輪廓末點的下一個點被認為是首點.在點qi處定義k條線段，線段qiqi -1和qiqi +1分別是第一條線段和最后一條線段，為了清楚地看到并區(qū)分邊界線段和其它線段，分別對點qi和其相鄰點qi -1，qi +1之間的間隔做了放大處理，并對它們形成的兩條邊界線段進行延長和加粗處理，如圖2所示，其余k -2條線段是通過在兩條邊界線段間等角度劃分，并且分別延劃分角度方向第一次與輪廓相交得到.

表1　定量驗證形變對描述特征的影響

θ1(qi)和θk(qi)分別是第一條和最后一條線段的方向角，這里的方向角定義為水平軸正半軸逆時針指向該線段所形成的角度，θj(qi)∈［0，2π］，其中，j∈［1，k］.為了使所獲得的線段均能夠與輪廓發(fā)生相交，定義兩邊界線段之間的角度為

其余k -2條線段劃分間隔為Δθ1k(qi)/(k -1).故這k條線段長度組成的k維矢量，構成了點qi處的特征描述，即v(qi)=［di1，di2，…，dik］，其中，dij是第j個線段的長度，如圖2所示.

可見點qi處的特征描述v(qi)反映的是一段輪廓的局部結(jié)構，即輪廓局部信息.若輪廓為開輪廓，則從輪廓上點qi發(fā)出的k條線中有可能存在不能與輪廓相交的線，相應的dij被標記為d∞，如圖2(b)中虛線所示.

2.2基于局部尺度進行非均勻采樣

點qi處的局部尺度定義為其特征描述矢量中所有有限長度的平均值［14］，即

其中，Ci= { dij∈v(qi)|dij≠d∞}，|Ci|表示Ci這個集合中元素的個數(shù).局部尺度值的大小和該點特征矢量所能描述的輪廓信息的多少成正比.因此，可以根據(jù)局部尺度值對輪廓進行非均勻采樣，即若該點的特征矢量所能描述的輪廓信息較多，那么在此處的采樣就比較稀疏，反之，比較稠密，如圖3所示.

已知輪廓上任意一點qi，其局部尺度值Scale(qi)，則該點與下一個即將被采樣的點之間采樣間隔offset(qi)=?＊Scale(qi)，?∈(0，1］，其中?控制著采樣點密度，綜合時間和效果兩個因素，本文以下的實驗中?均取0.7.迭代此過程，直至整個輪廓采樣結(jié)束，結(jié)果如圖3所示.一系列順序采樣點的特征描述矢量組成了整個輪廓的全局描述.

即歸一化后特征矢量v1(qi)=［d1i1，d1i2，…，d1ik］.對于存在縮放關系的兩輪廓，尤其是縮放倍數(shù)較大時，如縮小4倍時，本文算法的匹配效果明顯會優(yōu)于文獻［14］算法，在下面的實驗部分將得以驗證.

由于每個點的特征描述反映的并不只是該點的信息，而是其相對保持穩(wěn)定的鄰域局部結(jié)構，故其對輪廓變形具有一定的魯棒性;由于結(jié)合了輪廓的局部信息

2.3特征描述符的歸一化研究

對于存在縮放關系的兩輪廓需要對前文特征矢量中的每一個元素進行歸一化處理，即用特征矢量中每一個元素除以所有有效元素的平均值，它反映每一個元素與平均值的相對大小關系，與輪廓尺度無關.和全局信息，故適合于局部輪廓匹配;此外，由于一系列順序采樣點的特征描述能夠構成輪廓的全局信息，與起始點的選擇無關，故該算法不受初始點的影響.

3　基于改進DTW的輪廓匹配算法

由于本文中兩個待匹配輪廓上的采樣點之間并不存在一一對應的線性關系，因此，將DTW非線性規(guī)整技術應用于輪廓匹配中，為了減少計算量和放寬對輪廓采樣點位置一致性的要求，本文結(jié)合輪廓描述特點，在九宮格中設置局部路徑約束條件，在該約束條件下通過逐步判斷和迭代來優(yōu)化出最佳匹配路徑;最后，以旋轉(zhuǎn)角度為參數(shù)，計算全局最短路徑，以提高匹配的正確率.

局部路徑約束的DTW算法原理圖如圖5(a)所示.本文將詳細地以閉合輪廓和開輪廓(閉合輪廓的一部分)之間的匹配為例，重點闡述其匹配算法的原理:把開輪廓上的每個采樣點n =1～N在二維直角坐標系中的橫軸標出，把閉合輪廓上的每個采樣點在縱軸上標出，為了避免起始點的影響在縱軸上對閉合輪廓取兩個采樣周期m =1～2* M.通過這些整數(shù)坐標畫出網(wǎng)格線，網(wǎng)格中的每個交叉點(i，j)表示開輪廓上的某一采樣點與閉合輪廓上某一采樣點的對應.

該算法主要分兩步實現(xiàn):一是計算兩個輪廓各采樣點之間的特征矢量距離;二是通過求得的特征矢量距離矩陣，優(yōu)化出一條最佳匹配路徑，即沿該路徑的積累距離達到最小值.

已知開輪廓q和閉合輪廓r，則開輪廓上任意采樣點qi和閉合輪廓上任意采樣點rj之間的特征矢量距離為:

根據(jù)上述兩式可見，D(qi，rj)的取值范圍是［0，1)，值越接近1表示越不匹配，越接近0表示越匹配.

優(yōu)化最佳路徑的過程是逐步判斷和遞推的過程.對于網(wǎng)格中任意格點(m，n)，到達該格點的積累距離等于該點的特征矢量距離加其前續(xù)格點的積累距離.但是前續(xù)格點是如何選擇的，前續(xù)格點的選擇是由路徑的局部約束條件確定的.

根據(jù)第二部分特征描述的特點，如圖4所示，兩個輪廓中的采樣點并不是呈一對一的線性對應關系，因此，線性匹配算法在這里是行不通的.另外，約束條件的設置使得路徑約束的非線性度必須要和該采樣特性相匹配，文獻［14］設置了三條路徑，如圖5(b)中路徑①，②，③所示，但是根據(jù)圖4中兩輪廓采樣點特性發(fā)現(xiàn)，本文采樣點的對應關系達到了一對三，其非線性度大于文獻［14］中的路徑設置，二者非線性度不匹配，故文獻［14］中的路徑設置在這里不合適.綜合考慮采樣特性和計算復雜度兩個因素本文提出在該點左下方的九宮格內(nèi)設置路徑約束條件，如圖5(b)所示，每條路徑反應了不同的線性關系，其中路徑⑥，⑦即反映了一對三的非線性關系，所以格點(m，n)的前續(xù)格點為圖5(b)中九個標注格點中積累距離最小的那個格點，即

所求得的積累距離矩陣中第N列元素的最小值，即min(Cost(:，N))所對應的行數(shù)為開輪廓末點對應在閉合輪廓上的位置，這個最小值所對應的網(wǎng)格交叉點即是優(yōu)化出來的最佳路徑的末端，如圖5(a)中B點.根據(jù)該路徑在縱軸上所跨越的長度，可獲得該路徑的端點A，即得到開輪廓首點對應在閉合輪廓上的位置，從而獲得兩個輪廓之間的最優(yōu)匹配.

另外，對于開輪廓之間的匹配(本文只針對包含關系的兩開輪廓間的匹配，即其中一個開輪廓是另一個開輪廓一部分的情況)，同樣地，本算法主要分為兩大塊，首先基于局部尺度進行非均勻采樣，對采樣點采用保持輪廓局部結(jié)構的描述符進行輪廓描述，對特征描述矢量進行歸一化處理;其次采用基于九宮格路徑約束的DTW算法就行優(yōu)化匹配.針對以上這兩部分，現(xiàn)從理論的角度分析該算法在開輪廓間匹配的有效性:首先，一系列順序采樣點的特征描述矢量組成了整個輪廓的全局信息，即使是開輪廓，另外，某一點的特征描述反映了該點的局部輪廓信息，適合于局部之間的匹配;其次，在DTW算法第一步計算特征矢量距離時，對于從開輪廓上的點發(fā)出的k條線中存在不能與輪廓相交的情況，將對應特征的距離定為0(越接近0表示越匹配)，如式(2)所示，從而去除開輪廓對匹配的影響.為了進一步說明，本文在實驗部分將給出對應的實驗用例進行驗證.

為了使算法的普適性更好，精確性更高，避免局部最優(yōu)化導致錯誤匹配，本文引入待匹配輪廓之間的旋轉(zhuǎn)角度參數(shù)β，此時的積累距離矩陣為Cost(m，n，β)，

4　實驗結(jié)果對比和分析

為了驗證該算法能夠一定程度上地解決局部輪廓匹配問題及非相似變換和非剛體變換引起的輪廓形變問題，本文設計以下兩組實驗:開輪廓和閉合輪廓之間的匹配以及開輪廓與開輪廓之間的匹配.

實驗所用的輪廓均是由圖6(MPEG7數(shù)據(jù)庫)這些原始形狀變換得到的，其中，圖(a1)尺寸為圖(a2)是的4倍，圖(a3)尺寸與(a1)相近但產(chǎn)生了一定程度的形變;圖(b1)尺寸為圖(b2)的4倍，圖(b3)尺寸與(b2)相近但產(chǎn)生了一定程度的形變;同樣的，圖(c1)尺寸為圖(c2)2倍，圖(c3)尺寸與(c2)相近但產(chǎn)生了一定的形變;圖(d1)尺寸為圖(d2)2倍，圖(d3)尺寸與(d2)相近但存在一定的形變.

4.1實驗可視化結(jié)果

4.1.1開輪廓和閉合輪廓的匹配

為了驗證本文算法在開-閉輪廓匹配方面的有效性，本文以圖6(a1)～(a3)中的三幅圖像和圖6(b1)～(b3)中的三幅圖像為原型進行輪廓提?。?5］，兩組圖均采用文獻［14］中的局部Hausdorff Distance(HD)算法［14］，文獻［13］中的基于局部尺度和傳統(tǒng)DTW的算法，以及本文算法進行匹配，匹配結(jié)果如圖7和圖8所示.其中，第一行是存在4倍縮放且發(fā)生旋轉(zhuǎn)的開-閉輪廓之間的匹配結(jié)果，第二行是存在縮放、形變以及旋轉(zhuǎn)的開-閉輪廓匹配結(jié)果.為了說明算法不受起始點的限制，本實驗將輪廓分別按順時針和逆時針兩個方向旋轉(zhuǎn)一定角度.

4.1.2開輪廓和開輪廓的匹配

本文以圖6(c1)～(c3)中的三幅圖像和圖6(d1)～(d3)中的三幅圖像為原型，進行兩組實驗驗證該算法適用于開輪廓之間的匹配.實驗結(jié)果如圖9、10所示.其中，第一行是發(fā)生旋轉(zhuǎn)的開輪廓-開輪廓之間的局部匹配結(jié)果，第二行是存在2倍縮放、一定形變以及旋轉(zhuǎn)關系的開輪廓-開輪廓局部匹配結(jié)果.

4.2實驗定量化結(jié)果

從三個因素來定量化評價輪廓匹配算法的有效性［16］:錯匹配率ef，漏匹配率em和準確率P.

其中，Af表示錯誤匹配輪廓點的集合; Am表示漏匹配輪廓點的集合; Az1是指匹配出來所有輪廓點的集合; Az2是指理想匹配所有輪廓點的集合; A表示正確匹配輪廓點的集合; card(X)表示集合X中元素的個數(shù).對于上述實驗圖片，分別計算三種算法的上述三個因素，如表2可見，本文方法的匹配準確率平均約為0.92，較HD算法提高了30%，較文獻［14］算法提高了26%.

4.3結(jié)果分析

由以上實驗結(jié)果可知，對于存在縮放、任意角度旋轉(zhuǎn)以及一定程度形變的兩輪廓，無論是開輪廓-閉合輪廓匹配，還是開輪廓-開輪廓匹配，本文算法都能取得較好的匹配結(jié)果，但是，被學者認可的局部Hausdorff距離匹配算法以及文獻［13］中的傳統(tǒng)DTW算法在這里卻產(chǎn)生了錯誤匹配.分析其原因:采用本文的非均勻采樣方法進行采樣，雖然對所有采樣點的特征描述構成了整條輪廓的全局信息，并且每個采樣點的特征描述能夠反映小段輪廓的局部信息，但是，兩個輪廓上對應采樣點的位置并不一致，對于本文及現(xiàn)有的采樣方法所獲得的采樣點非一致的情況，本文算法得到了較好的匹配結(jié)果(如4.1可視化結(jié)果和4.2定量化結(jié)果所示)，實驗證明本文算法一定程度上不受采樣點非一致的影響，但是基于局部Hausdorff距離的輪廓匹配方法對采樣點位置一致性要求較嚴格，因此，在輪廓發(fā)生旋轉(zhuǎn)之后，其輪廓點位置會發(fā)生變化，則其匹配結(jié)果變差，如圖9第一行樣本圖像逆時針旋轉(zhuǎn)60度和不發(fā)生旋轉(zhuǎn)的結(jié)果所示，因此，此處采用Hausdorff距離算法的話，隨機性較大;另外，采用文獻［13］算法，其中的傳統(tǒng)DTW技術屬于非線性匹配方法，其實驗結(jié)果仍然不是很理想，主要是因為約束條件的設置問題，約束條件的設置反映著非線性匹配的非線性度，該文獻中約束條件設置的是圖5中①、②、③三條路徑約束，而本文中兩輪廓采樣點特征描述之間對應關系的非線性度更大，二者非線性度不匹配，因此其實驗結(jié)果不是很理想，另外文獻［14］輪廓描述中并沒有對特征矢量進行歸一化處理，所以對于存在較大縮放的兩輪廓，其匹配結(jié)果較差，如圖7第一行所示，其縮放關系為4倍;因此，將本文的輪廓描述算法和與之相匹配的九宮格路徑DTW技術結(jié)合，得到了較好的匹配結(jié)果，如圖7～10(d)所示.

表2　匹配精度的定量化分析

5　結(jié)論

(1)本文提出了一種基于保持局部結(jié)構描述符和改進DTW的輪廓匹配算法，一定程度上解決了存在幾何變換關系的兩輪廓間的局部匹配問題及非相似變換和非剛體變換引起的輪廓較小形變問題，且不受起始點的限制.

(2)基于保持局部結(jié)構的輪廓描述符較好地融合了輪廓的全局信息和局部信息，具有旋轉(zhuǎn)、尺度不變性，并且對一定程度的形變具有魯棒性.

(3)針對線性匹配方法效果不佳以及傳統(tǒng)DTW技術約束路徑的線性度不滿足輪廓匹配特性要求，提出一種基于改進DTW技術的輪廓匹配算法.即結(jié)合輪廓采樣特性設置九宮格的路徑約束條件，在該約束條件下通過逐步判斷和迭代來優(yōu)化出最佳匹配路徑.

(4)本文算法的匹配準確率平均約為92%，較HD算法提高了30%，較文獻［13］算法提高了26%.

參考文獻

［1］曹傳東，徐貴力，陳欣等.基于力場轉(zhuǎn)換理論的圖像粗大邊緣檢測方法［J］.航空學報，2011，32(5): 891 -899.Cao C D，Xu G L，Chen X，et al.Image edge detection al-gorithm based on force field transformation［J］.Acta Aeronoutica et Astronautica Sinica，2011，32(5): 891 -899.(in Chinese)

［2］Xin Shu，Xiaojun Wu.A novel contour descriptor for 2D shape matching and its application to image retrieval［J］.Image and Vision Computing，2011，(29): 286 -294.

［3］Tu Z W，Yuille A.Shape matching and recognition: using generative models and informative features［A］.Proceedings of the 8th European Conference on Computer Vision(ECCV)［C］.Prague，Czech Republic: Springer，2004.195 -209.

［4］Tu Z W，Zheng S F，Yuille A.Shape matching and registration by data-driven EM［J］.Computer Vision and Image Understanding，2008，109(3): 290 -304.

［5］Felzenszwalb P F，Schwartz J D.Hierarchical matching of deformable shapes［A］.Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition(CVPR)［C］.Minneapolis，MN，USA: IEEE，2007.1 -8.

［6］Bartolini I，Ciaccia P，Patella M.Warp: accurate retrieval of shapes using phase of Fourier descriptors and time warping distance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(1): 142 -147.

［7］牛慶肖，張樺，徐光平，薛彥兵.基于鏈碼和快速傅里葉變換的輪廓描繪方法［J］.光電子激光，2011，22(12): 1857 -1861.Niu Q X，Zhang H，Xu G P，et al.A contour description method based on chain and fast Fourier transform［J］.Journal of Optoelectronics Laser，2011，22(12): 1857 - 1861.(in Chinese)

［8］Chui H，Rangarajan A.A new point matching algorithm for non-rigid point matching［A］.IEEE International Conference on Computer Vision and Pattern Recognition［C］.USA: IEEE，2000.44 -51.

［9］Chui H，Rangarajan A.A new point matching algorithm for non-rigid registration［J］.Computer Vision and Image Understanding，2003，89(2): 114 -141.

［10］Besl P J，Mckay N D.A method for registration of 3-D shapes［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14(4): 239 -256.

［11］Van K O，Hamarneh G，Zhang H，et al.Contour correspondence via ant colony optimization［A］.Proceedings of the 15th Pacific Conference on Computer Graphics and Applications［C］.USA: IEEE，2007.271 -280.

［12］Liu L，Wang G，Zhang B，et al.Perceptually based approach for planar shape morphing［A］.Proceedings of the 12th Pacific Conference on Computer Graphics and Applications［C］.USA: IEEE，2004.111 -120.

［13］Damien Michel，Iasonas Oikonomidis，Antonis Argyros.Scale invariant and deformation tolerant partial shape matching［J］.Image and Vision Computing，2011，29: 459 -469.

［14］高晶，孫繼銀，劉婧.基于鄰域灰度信息的Hausdorff距離圖像匹配方法［J］.計算機應用，2011，31(3): 741 -744.Gao J，Sun J Y，Liu J.Image matching method based on normalized grayscale variance Hausdorf distance［J］.Journal of Computer Applications，2011，31(3): 741 - 744.(in Chinese)

［15］陳青，劉金平，唐朝暉，李建奇，吳敏.基于分數(shù)階微分的圖像邊緣細節(jié)檢測與提?。跩］.電子學報，2013，41(10): 1873 -1880.Chen Qing，Liu JinPing，，Tang ZhaoHui，Li JianQi，Wu Min.Detection and extraction of image edge curves and detailed features using fractional differentiation［J］.Acta Electronica Sinica，2013 41(10): 1873 - 1880.(in Chinese)

［16］Grigorescu C，Petkov N，Westenberg M A.Contour detection based on nonclassical receptive field inhibition［J］.IEEE Transactions on Image Processing，2003，12(7):729 -739.

徐貴力男，1972年生，黑龍江佳木斯人.現(xiàn)為南京航空航天大學博士生導師，從事光電檢測、計算機視覺方面的研究.

E-mail: guilixu@163.com

趙妍女，1989年生，河南人新鄉(xiāng)人.碩士研究生，從事機器視覺方面的研究.

E-mail: zhao.yan109@163.com

Partial Contour Matching Algorithm Based on Local Scale Description and Improved DTW

XU Gui-li，ZHAO Yan，JIANG Bin，WANG Zheng-sheng，LI Kai-yu，GUO Rui-peng
(Institute of Automation，Nanjing University of Aeronautics and Astronautics，Nanjing，Jiangsu 210016，China)

Abstract:Image matching based on contour is an important issue in computer vision，but now there is no mature algorithm that can solve the problems of partial contour matching and deformation caused by non-similar transformation and non-rigid transformation.According to the conclusions that partial contour structure has relative stability and a good description need to merge the contour’s local and global information，a local scale description method is proposed which is scale，rotation invariant，deformation tolerant and initial point independence.On this basis，a contour matching algorithm is proposed based on improved DTW.Experimental results show that the proposed method can realize the partial matching between open contour and open contour as well as closed contour.Its matching precision is 92%on average，and improves 30%compared with HD method，improves 26%compared with traditional DTW.

Key words:machine vision; contour description; local scale; partial matching; dynamic time warping; deformation

作者簡介

基金項目:國家自然科學基金(No.61473148)

收稿日期:2014-05-26;修回日期: 2014-11-13;責任編輯:孫瑤

DOI:電子學報URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.020

中圖分類號：TP391

文獻標識碼：A

文章編號：0372-2112(2016)01-0135-08