基于同底三角形面積描述的形狀檢索

胡大盟,黃偉國(guó)，楊劍宇，朱忠奎

(蘇州大學(xué)城市軌道交通學(xué)院，江蘇蘇州 215131)

?

基于同底三角形面積描述的形狀檢索

胡大盟,黃偉國(guó)，楊劍宇，朱忠奎

(蘇州大學(xué)城市軌道交通學(xué)院，江蘇蘇州 215131)

為了在形狀匹配的過程中提高形狀特征對(duì)邊界噪聲和圖像變形的魯棒性，同時(shí)兼顧形狀匹配算法的檢索精度和運(yùn)算效率，提出一種基于同底三角形面積的形狀匹配方法.該方法首先計(jì)算每個(gè)輪廓采樣點(diǎn)的同底三角形面積描述子，并對(duì)該描述子進(jìn)行局部平滑，使其更加魯棒.然后采用加權(quán)L1度量方法計(jì)算兩個(gè)形狀所有輪廓點(diǎn)的同底三角形描述子之間的距離，獲得匹配代價(jià)矩陣.最后利用動(dòng)態(tài)規(guī)劃算法計(jì)算匹配代價(jià)矩陣的相似度，獲得形狀距離，實(shí)現(xiàn)形狀匹配.通過在MPEG-7、Kimia以及鉸接形狀數(shù)據(jù)庫(kù)上測(cè)試分析表明，該方法對(duì)變形目標(biāo)具有良好的魯棒性，且提高了運(yùn)算效率和檢索精度.

同底三角形；局部平滑；動(dòng)態(tài)規(guī)劃；混合檢索；形狀匹配

1　引言

隨著數(shù)字化多媒體信息技術(shù)的快速發(fā)展，形狀檢索成為了機(jī)器視覺領(lǐng)域中研究的熱點(diǎn).與物體的紋理、顏色等特征相比，形狀特征是一種更高級(jí)的視覺信息，識(shí)別的魯棒性和穩(wěn)定性更高.形狀檢索的關(guān)鍵在于能否構(gòu)造出形狀特征信息豐富的描述子，而形狀的輪廓包含了大量的形狀信息，因此國(guó)內(nèi)外研究機(jī)構(gòu)和學(xué)者們基于形狀的輪廓構(gòu)造出不同的具有變換不變性的特征描述子，并將這些描述子廣泛應(yīng)用于圖像及視頻匹配、目標(biāo)識(shí)別、機(jī)器人導(dǎo)航、場(chǎng)景分類以及圖像分割等計(jì)算機(jī)視覺領(lǐng)域[1].

基于輪廓邊界點(diǎn)的空間位置關(guān)系的形狀描述方法是近年來最為重要的方法[2].BelongieS等[3]提出了形狀上下文(ShapeContexts,SC)描述方法，該方法對(duì)目標(biāo)輪廓的描述能力強(qiáng)，但存在抑制噪聲能力較弱，算法復(fù)雜度高等問題.LingHB等[4]在SC的基礎(chǔ)上提出了內(nèi)距離形狀上下文(Inner-DistanceShapeContext,IDSC)，該方法用輪廓點(diǎn)之間的內(nèi)距離代替SC中的輪廓點(diǎn)之間的歐氏距離.該方法對(duì)非剛性鉸接物體具有較好的描述效果，但對(duì)具有復(fù)雜類內(nèi)信息的目標(biāo)識(shí)別精度不高，且算法復(fù)雜度較高.鄭丹晨等[5]基于SC提出了一種利用角點(diǎn)典型形狀上下文特征(CornerRepresentativeShapeContext，CRSC)進(jìn)行快速識(shí)別的方法，該方法能夠降低特征點(diǎn)的匹配時(shí)間，有利于解決大規(guī)模形狀樣本的匹配問題，但該方法檢索精度不高；GrigorescuC等[6]同樣利用輪廓點(diǎn)的空間位置分布關(guān)系提出了距離集(Distancesets)的局部描述子，該方法能夠較好的獲得形狀的局部特征，然而忽略了全局特征，特征描述不完整導(dǎo)致形狀檢索精度較低.

近年來還出現(xiàn)了利用更加穩(wěn)定的三點(diǎn)空間位置關(guān)系來對(duì)形狀進(jìn)行特征描述的方法.ElRube等[7]提出了多尺度三角形面積表示方法(Multi-scaleTriangle-areaRepresentation，MTAR)，該方法具有較好的抗噪性，但要對(duì)形狀進(jìn)行小波分解，計(jì)算量較大.AlajlanN等[8]利用輪廓點(diǎn)構(gòu)成的三角形面積(Triangle-areaRepresentation，TAR)來描述形狀，并通過控制三角形的邊長(zhǎng)來獲得形狀的多尺度信息，該方法能夠有效獲得形狀的局部和全局特征，但是該算法需要不斷改變邊長(zhǎng)，特征提取較為復(fù)雜，且對(duì)變形點(diǎn)較為敏感.TemlyakovA等[9]利用德勞內(nèi)三角化方法對(duì)形狀輪廓進(jìn)行分解，并通過定義特征三角形(FeatureTriangle)和葉子三角形(LeafTriangle)來對(duì)形狀內(nèi)部的小三角形進(jìn)行分類.該方法具有較好的形狀變換不變性，但是計(jì)算復(fù)雜度較高.王斌[10]提出了一種多尺度拱高(Multi-ScaleArcHeight，MSAH)形狀描述方法，該方法用多尺度的拱高函數(shù)來度量形狀輪廓線上點(diǎn)的彎曲程度.該算法復(fù)雜度較低，但在形狀數(shù)據(jù)庫(kù)上的檢索率不高.

此外，為了進(jìn)一步提高形狀描述子的檢索率，一些學(xué)者提出了度量學(xué)習(xí)算法，這些算法能夠解決形狀距離矩陣中存在不滿足三角不等式的問題.如Bai等[11]提出的協(xié)同傳導(dǎo)(Co-transduction)的形狀檢索方法，Yang等[12]提出的稠密化距離空間(DensifyingDistanceSpaces)的形狀檢索方法.這些算法通過獲得顯著的檢索路徑，進(jìn)一步提高描述子的檢索精度.

針對(duì)現(xiàn)有形狀輪廓特征描述方法存在特征描述不完整，且形狀特征獲取復(fù)雜度較高，抗噪能力一般的問題，本文基于輪廓點(diǎn)的空間位置關(guān)系提出一種同底三角形面積的形狀描述方法.另外，為了提高描述方法的形狀檢索精度，本文還提出一種混合檢索方.本文提出的形狀描述方法在抗噪聲干擾、運(yùn)算效率以及匹配精度等方面的表現(xiàn)良好.

2　同底三角形面積表示

(1)

Si={si,u}，(u=i,i+1,…,n,1,2…,i-1)

(2)

將式(2)中的CBTA描述子寫成n維列向量形式：Si=(si,i,…,si,n,si,1,si,2,…,si,i-1)T，則可用n×n的矩陣{Si}(i=1,…,n)來描述整個(gè)形狀的特征.圖2(b)、(c)、(d)是蝴蝶形狀-1的輪廓上不同采樣點(diǎn)的CBTA描述子曲線，由圖可知采樣點(diǎn)在輪廓上所處位置的不同，其對(duì)應(yīng)的CBTA描述子曲線也不同，這表明CBTA描述方法能區(qū)分出同一形狀中不同輪廓點(diǎn)的相對(duì)位置關(guān)系.而在同一類形狀中相似位置處的點(diǎn)的CBTA描述子向量的曲線的走勢(shì)基本一致，如蝴蝶形狀-1中點(diǎn)A的CBTA曲線與蝴蝶形狀-2中點(diǎn)A'的CBTA曲線具有較高的相似性(圖2(b)和圖3(b)).以上分析表明CBTA描述子不僅具有較好的區(qū)分輪廓采樣點(diǎn)位置的能力，還具有對(duì)同類形狀的相似位置處點(diǎn)的聚類能力.

pi點(diǎn)的CBTA描述子Si的第一個(gè)元素si,i值的正負(fù)表征了該點(diǎn)的凹凸性質(zhì).當(dāng)順時(shí)針采樣輪廓點(diǎn)時(shí)，該元素為正值表示pi點(diǎn)為凹點(diǎn)，負(fù)值表示pi點(diǎn)為凸點(diǎn)，零值表示pi點(diǎn)為直線點(diǎn).這是因?yàn)橛邢蛎娣esi,i是通過計(jì)算pi和其相鄰兩個(gè)點(diǎn)pi-1、pi+1坐標(biāo)的行列式而得，該行列式的正負(fù)性能夠反映出由這三個(gè)點(diǎn)構(gòu)成的三角形的順、逆時(shí)針方向，而這種順、逆時(shí)針方向恰好對(duì)應(yīng)輪廓的凹凸性.用向量cc=(s1,1,s2,2,…,sn,n)T表示輪廓所有采樣點(diǎn)的si,i值集合，由于該向量表征了該點(diǎn)的凹凸性，因此本文稱其為凹凸向量(Concave-convex vector).三種不同凹凸性點(diǎn)的標(biāo)示如圖4(a)，圖4(b)為凹凸向量曲線，該曲線上點(diǎn)的幅值正負(fù)對(duì)應(yīng)輪廓采樣點(diǎn)的凹凸性，8個(gè)尖峰處的點(diǎn)對(duì)應(yīng)字母T中最明顯的角點(diǎn).

綜合上述分析表明，CBTA描述子向量不僅包含了輪廓點(diǎn)在形狀中的相對(duì)位置關(guān)系信息，還包含了輪廓的凹凸性信息，這說明該描述子用于輪廓形狀特征描述的能力強(qiáng).另一方面，由于CBTA表示方法描述的是采樣點(diǎn)內(nèi)部之間的相對(duì)的幾何位置關(guān)系，該屬性使得其具有平移、旋轉(zhuǎn)不變性.

3　局部平滑抗噪

當(dāng)輪廓因?yàn)樽冃萎a(chǎn)生一些變形點(diǎn)時(shí)，CBTA描述子會(huì)產(chǎn)生一定的偏差，如圖5所示，原先D點(diǎn)被變形點(diǎn)D'取代，所構(gòu)成的同底三角形面積變大.為了提高CBTA描述子的抗噪性，本文采用局部平均的方法來平滑CBTA描述子，使得該描述子對(duì)邊界變形具有一定的魯棒性.具體過程如下：

給定一個(gè)整數(shù)k，將輪廓采樣點(diǎn)數(shù)n，按[1,k],[k+1,2k],…,[mk-k+1,mk]形式等間隔分成m段，然后計(jì)算每一段中k個(gè)同底三角形面積的平均值φi,j，即：

(3)

其中j表示分段數(shù)的索引，令m=?n/k」，則j=1,…,m.用每一段中面積向量的平均值來代替原來k個(gè)面積，以平滑變形點(diǎn)帶來的偏差.經(jīng)過上述處理以后，輪廓上第i個(gè)采樣點(diǎn)的平滑描述子和形狀輪廓的平滑描述矩陣分別為：

ψi=(φi,1,φi,2,…,φi,m)T

(4)

Ψ=(ψ1,ψ2,…,ψn)

(5)

局部平滑后的描述子能夠使得輪廓點(diǎn)的原始描述子維數(shù)由n維降為m維，大大降低了形狀匹配代價(jià)矩陣的計(jì)算復(fù)雜度.另外，為了獲得CBTA描述子的尺度不變性，本文對(duì)描述矩陣的進(jìn)行局部歸一化，即：

(6)

算法復(fù)雜度分析：根據(jù)式(2)，獲得每個(gè)輪廓點(diǎn)的CBTA描述子要計(jì)算n個(gè)面積，計(jì)算復(fù)雜度為O(n)，因此獲得整個(gè)形狀的CBTA描述矩陣的時(shí)間復(fù)雜度為O(n×n)=O(n2).然后根據(jù)式(3)對(duì)CBTA描述子進(jìn)行局部平滑，使其從n維降為n/k維，該過程計(jì)算復(fù)雜度為O(n/k×n)=O(n2)/k.最后利用式(6)對(duì)描述矩陣進(jìn)行局部歸一化，該過程算法復(fù)雜度仍為O(n2)/k.因此構(gòu)造一個(gè)形狀的CBTA描述矩陣的算法復(fù)雜度為(1+2/k)O(n2).該算法復(fù)雜度要比IDSC(O(n3))低.幾種算法對(duì)蝴蝶形狀-1進(jìn)行構(gòu)造描述矩陣花費(fèi)時(shí)間測(cè)試結(jié)果如表1所示，在該形狀上CBTA所用時(shí)間較少.

表1　幾種算法的描述矩陣構(gòu)造時(shí)間

4　距離計(jì)算及形狀匹配

利用CBTA矩陣來度量?jī)蓚€(gè)形狀的距離通常有兩個(gè)問題要解決：第一，如何計(jì)算兩個(gè)形狀輪廓點(diǎn)的描述子之間的距離；第二，如何獲得兩個(gè)形狀的輪廓點(diǎn)序列的最優(yōu)對(duì)應(yīng)關(guān)系.對(duì)于第一個(gè)問題，由于每個(gè)輪廓點(diǎn)的CBTA描述子ψ是m維的向量，因此可采用加權(quán)L1距離來計(jì)算CBTA描述子之間的距離.假設(shè)pr，qc分別是兩個(gè)形狀S1，S2的第r個(gè)輪廓點(diǎn)和第c個(gè)輪廓點(diǎn)，則這兩個(gè)點(diǎn)的描述子距離或稱匹配代價(jià)c(pr,qc)：

(7)

其中ωt為不同分段的CBTA描述子的權(quán)重，考慮到pr，qc附近的點(diǎn)要比距離遠(yuǎn)的點(diǎn)在目標(biāo)識(shí)別中更重要，應(yīng)賦給更大的權(quán)重，令ωt=1/min{t,m-t}.從而兩個(gè)形狀S1,S2的匹配代價(jià)矩陣為：

C(S1,S2)=

r=1,…,n;c=1,…,n(8)

對(duì)于第二個(gè)問題，由于輪廓點(diǎn)的順序信息已知，因此可利用動(dòng)態(tài)規(guī)劃算法[14](Dynamic Programming，DP)處理匹配代價(jià)矩陣.動(dòng)態(tài)規(guī)劃算法主要目的在于獲得形狀S1,S2的輪廓點(diǎn)索引的最佳映射π:r→c，該映射應(yīng)使得式(9)右邊最小，最終的形狀距離為：

(9)d越小表示兩個(gè)形狀S1,S2越相似.由于兩個(gè)輪廓序列的最佳映射關(guān)系可以通過動(dòng)態(tài)規(guī)劃算法得到，這使得輪廓序列的起始點(diǎn)位置的不同并不會(huì)對(duì)最終的匹配結(jié)果產(chǎn)生影響，因此在建立CBTA匹配代價(jià)矩陣過程中也無(wú)需指定起始點(diǎn).CBTA形狀匹配算法的完整流程圖如圖6所示.

5　混合最小決策檢索方法

為了提高形狀檢索率，本文提出一種形狀信息融合的檢索方法，該方法將CBTA匹配算法與任意已知的基于輪廓點(diǎn)空間位置關(guān)系的形狀匹配算法融合，如SC匹配算法.然后利用最小決策公式來更新原始單一的形狀距離，即

d(S1,S2)=min(dCBTA(S1,S2),αdSC(S1,S2))

(10)

其中dCBTA為CBTA距離，dSC為SC距離，α為不同的形狀匹配距離的懲罰因子.參數(shù)α的最終取值應(yīng)保證混合后檢索精度達(dá)到最高，該參數(shù)的初始值可取兩個(gè)形狀距離矩陣所有元素之和的比值，即

(11)

6　實(shí)驗(yàn)與分析

實(shí)驗(yàn)參數(shù)設(shè)置：對(duì)輪廓進(jìn)行等間隔順時(shí)針采樣100個(gè)點(diǎn)，即n=100；輪廓局部平滑分為20段，即m=20，k=5.實(shí)驗(yàn)環(huán)境：操作系統(tǒng)Windows7，32位，處理器：Pentium(R)Dual-Core CPU E6700，內(nèi)存4G，使用軟件為Matlab R2011b.6.1MPEG-7形狀數(shù)據(jù)庫(kù)檢索

MPEG-7數(shù)據(jù)庫(kù)[15]主要用于測(cè)試基于相似度的算法的檢索精度，是目前衡量形狀描述子可靠性的最為重要的基準(zhǔn)數(shù)據(jù)庫(kù).該數(shù)據(jù)庫(kù)由70類圖像組成，每類包含20個(gè)形狀，共1400個(gè)形狀.圖7是部分MPEG-7形狀二值圖.通常該數(shù)據(jù)庫(kù)采用Bull-eye度量方法獲得算法的檢索率，即每個(gè)形狀都作為待匹配形狀，然后在剩余形狀中找到與待匹配形狀最相似的40個(gè)形狀，若其中包含了與待匹配形狀同類的所有20個(gè)形狀，則該形狀的檢索率100%，統(tǒng)計(jì)每個(gè)待匹配形狀的40個(gè)最相似形狀中與該形狀是同類的數(shù)目，最后再將每個(gè)形狀的匹配正確數(shù)目相加并除以28000(20*1400)，即得到形狀描述子的檢索率.本文提出的CBTA算法檢索率為89.45%，高于表2中其他算法.

圖8為每一類的檢索精度直方圖，觀察發(fā)現(xiàn)，第33類、36類形狀的檢索率較低，檢索率低于40%.這是因?yàn)檫@兩類形狀中大部分輪廓上都有一道或多道缺口(indentation)，包含了復(fù)雜的類內(nèi)信息[17]，導(dǎo)致構(gòu)造的CBTA描述子產(chǎn)生較大偏差，造成了誤匹配.

表2　部分重要算法在MPEG-7數(shù)據(jù)庫(kù)上的檢索率

為了提高M(jìn)PEG-7數(shù)據(jù)庫(kù)的形狀檢索率，本文將CBTA描述子與SC描述子相混合，并通過最小決策法來獲得新的形狀距離.首先通過實(shí)驗(yàn)獲得懲罰因子α的值：根據(jù)式(11)得到α的初始值為1.60，由該值向兩端計(jì)算檢索率，表3是α查找結(jié)果.由表可知當(dāng)α=1.56時(shí)，混合檢索結(jié)果最好，為93.65%，比不采用混合檢索的CBTA得到的檢索率高了4個(gè)百分點(diǎn).此外，利用協(xié)同傳導(dǎo)度量學(xué)習(xí)算法，可以將本文的CBTA特征描述子的檢索率進(jìn)一步提高到98.00%.

表3　懲罰因子α查找表

6.2Kimia形狀數(shù)據(jù)庫(kù)測(cè)試

Kimia[18]形狀數(shù)據(jù)庫(kù)包含Kimia25、Kimia99和Kimia216三個(gè)子數(shù)據(jù)庫(kù).本文選取最常用的Kimia99子數(shù)據(jù)庫(kù)進(jìn)行匹配精度測(cè)試，如圖9所示.Kimia99數(shù)據(jù)庫(kù)由9類圖像組成，每類有11個(gè)形狀，共99個(gè)形狀.在該數(shù)據(jù)庫(kù)上，評(píng)價(jià)算法檢索精度的方法為將數(shù)據(jù)庫(kù)中所有形狀依次作為待匹配形狀，計(jì)算剩余形狀到該形狀的相似度，把相似度最大的作為第一相似形狀，依次類推，然后統(tǒng)計(jì)所有與待匹配形狀同類的第一相似到第十相似的形狀數(shù)量.形狀檢索結(jié)果如表4所示，可以發(fā)現(xiàn)本文算法的檢索率與其他算法相比均最高.

表4　各種算法在Kimia99數(shù)據(jù)庫(kù)上的檢索結(jié)果

算法1st2nd3rd4th5th6th7th8th9th10th檢索率(%)SC[3]9791888584777566563776.36CDPH+EMD[19]9694948788828070625581.61Gen.Model[13]9997999896969483754889.39Efficientindexing[20]9997989697979691837593.84Pathsimilarity[21]9999999996979593897394.85CBTA9999999998989795957596.36

6.3形狀鉸接變形穩(wěn)定性測(cè)試

鉸接形狀數(shù)據(jù)庫(kù)[4]一般用于測(cè)試算法對(duì)變形形狀識(shí)別的穩(wěn)定性，該數(shù)據(jù)庫(kù)一共有40個(gè)形狀，分為8類，每類包含5個(gè)不同角度鉸接變形的形狀，如圖10所示.該數(shù)據(jù)庫(kù)上評(píng)價(jià)算法檢索精度的方法與Kimia99類似：將數(shù)據(jù)庫(kù)中所有形狀依次作為待匹配形狀，計(jì)算剩余形狀到該形狀的相似度，把相似度最大的作為第一相似形狀，依次類推，然后統(tǒng)計(jì)所有與待匹配形狀同類的第一相似到第四相似的形狀數(shù)量.由表5可知，本文提出的CBTA描述子對(duì)鉸接形狀具有較好的表示效果.

6.4抗噪測(cè)試

表5　各種算法在鉸接形狀數(shù)據(jù)庫(kù)上的檢索結(jié)果

為了論證CBTA算法的抗噪性能，本文對(duì)Kimia99數(shù)據(jù)庫(kù)中所有圖形輪廓的x坐標(biāo)，y坐標(biāo)加入均值μ=0、標(biāo)準(zhǔn)差由σ=0遞增到σ=1.0的高斯噪聲，然后在加噪的數(shù)據(jù)庫(kù)上進(jìn)行算法檢索對(duì)比實(shí)驗(yàn).加噪后的扳手形狀如圖11所示，檢索結(jié)果如表6所示.

表6　不同噪聲水平下的測(cè)試結(jié)果

σ1st2nd3rd4th5th6th7th8th9th10th檢索率(%)09999999998989795957596.360.29999989899989893937996.360.49999999898989994908096.360.69999989899979893877695.350.89999989997979493906694.141.09898989896969395836292.63

由表6可知，在噪聲水平0.2到0.6之間算法檢索精度幾乎不受邊界噪聲影響，即使在邊界變形較大情況下，該算法仍能保持較高的檢索精度，這是因?yàn)楸疚膶?duì)CBTA描述子進(jìn)行了局部平滑處理，從而提高了CBTA描述子的局部抗噪能力.

7　總結(jié)與展望

為了有效解決形狀檢索中數(shù)字圖像存在變形的問題，以及提高形狀匹配的檢索精度和算法運(yùn)算效率，本文提出了一種基于同底三角形面積的形狀描述方法.該方法基于輪廓點(diǎn)的空間位置關(guān)系，定義了輪廓點(diǎn)的同底三角形，并以該三角形的面積來描述輪廓點(diǎn)在形狀識(shí)別中的貢獻(xiàn)；然后對(duì)同底三角形面積描述子進(jìn)行局部平滑處理，有效提高了該描述子對(duì)噪聲的魯棒性，降低了描述子的維度；采用加權(quán)L1距離計(jì)算描述子之間的相似度，并利用動(dòng)態(tài)規(guī)劃算法獲得最終的匹配結(jié)果.在MPEG-7、Kimia以及鉸接形狀數(shù)據(jù)庫(kù)上的檢索測(cè)試表明，本文提出的算法能有效匹配出目標(biāo)，且檢索率高于部分重要算法.

本文提出的方法在具有復(fù)雜類內(nèi)信息的形狀上的檢索率較低，在后續(xù)研究中，我們將探索如何有效地提取該類目標(biāo)的特征信息，增強(qiáng)同底三角形面積描述子對(duì)該類形狀的區(qū)分能力以提高形狀檢索精度.

[1]呂玉增,彭啟民,黎湘.基于極值特征的不變性形狀識(shí)別[J].電子學(xué)報(bào),2008,36(4):679-684.

LuYu-Zeng,PengQi-Min,LiXiang.Shaperecognitionbasedontheinvariantofextremumfeatures[J].ActaElectronicaSinica,2008,36(4):679-684.(inChinese)

[2]周瑜,劉俊濤,白翔.形狀匹配方法研究與展望 [J].自動(dòng)化學(xué)報(bào),2012,38(6):889-910.

ZhouYu,LiuJun-tao,BaiXiang.Researchandperspectiveonshapematching[J].ActaAutomaticSinica,2012,38(6):889-910.(inChinese)

[3]BelongieS,MalikJ,PuzichaJ.Shapematchingandobjectrecognitionusingshapecontexts[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2002,24(4):509-522.

[4]LingH,JacobsDW.Shapeclassificationusingtheinner-distance[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2007,29(2):286-299.

[5]鄭丹晨,韓敏.基于改進(jìn)典型形狀上下文特征的形狀識(shí)別方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2013,25(2):215-220.

ZhengDan-chen,HanMin.Improvedshaperecognitionmethodbasedonrepresentativeshapecontext[J].JournalofComputer-AidedDesign&ComputerGraphics,2013,25(2):215-220.(inChinese)

[6]GrigorescuC,PetkovN.Distancesetsforshapefiltersandshaperecognition[J].IEEETransactionsonImageProcessing,2003,12(10):1274-1286.

[7]ElRubeI,AlajlanN,KamelM,etal.Robustmultiscaletriangle-arearepresentationfor2Dshapes[A].IEEEInternationalConferenceonImageProcessing[C].Piscataway,NJ,USA:IEEE,2005.1:I-545-8.

[8]AlajlanN,ElRubeI,KamelMS,etal.Shaperetrievalusingtriangle-arearepresentationanddynamicspacewarping[J].PatternRecognition,2007,40(7):1911-1920.

[9]TemlyakovA,MunsellBC,WaggonerJW,etal.Twoperceptuallymotivatedstrategiesforshapeclassification[A].IEEEConferenceonComputerVisionandPatternRecognition[C].Piscataway,NJ,USA:IEEE,2010.2289-2296.

[10]王斌.一種基于多尺度拱高形狀描述的圖像檢索方法[J].電子學(xué)報(bào),2013,41(9):1821-1825.

WangBin,Imageretrievalusingmulti-scalearchheightshapedescription[J].ActaElectronicaSinica,2013,41(9):1821-1825.(inChinese)

[11]BaiX,WangB,YaoC,etal.Co-transductionforshaperetrieval[J].IEEETransactionsonImageProcessing,2012,21(5):2747-2757.

[12]YangX,BaiX,K?knar-TezelS,etal.Densifyingdistancespacesforshapeandimageretrieval[J].JournalofMathematicalImagingandVision,2013,46(1):12-28.

[13]TuZ,YuilleAL.ShapeMatchingandRecognition-usingGenerativeModelsandInformativeFeatures[M].ComputerVision-ECCV2004,SpringerBerlinHeidelberg,2004.195-209.

[14]FelzenszwalbPF,ZabihR.Dynamicprogrammingandgraphalgorithmsincomputervision[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2011,33(4):721-740.

[15]LateckiLJ,LakamperR,EckhardtT.Shapedescriptorsfornon-rigidshapeswithasingleclosedcontour[A].IEEEConferenceonComputerVisionandPatternRecognition[C].LosAlamitos,CA,USA:IEEEComputSoc,2000.424-429.

[16]MokhtarianF,BoberM.CurvatureScaleSpaceRepresentation:Theory,Applications,andMPEG-7Standardization[M].SpringerPublishingCompany,Incorporated,2011.

[17]PremachandranV,KakaralaR.Perceptuallymotivatedshapecontextwhichusesshapeinteriors[J].PatternRecognition,2013,46(8):2092-2102.

[18]SebastianTB,KleinPN,KimiaBB.Recognitionofshapesbyeditingtheirshockgraphs[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2004,26(5):550-571.

[19]ShuX,WuXJ.Anovelcontourdescriptorfor2Dshapematchinganditsapplicationtoimageretrieval[J].ImageandvisionComputing,2011,29(4):286-294.

[20]BiswasS,AggarwalG,ChellappaR.Efficientindexingforarticulationinvariantshapematchingandretrieval[A].IEEEConferenceonComputerVisionandPatternRecognition[C].Piscataway,NJ,USA:IEEE,2007.1-8.

[21]BaiX,LateckiLJ.Pathsimilarityskeletongraphmatching[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2008,30(7):1282-1292.

胡大盟男，1990年生于江蘇淮安，碩士研究生，研究方向?yàn)橛?jì)算機(jī)視覺.

黃偉國(guó)(通信作者)男，1981年生于安徽休寧，副教授，博士，研究方向?yàn)閿?shù)字圖像處理.

E-mail:wghuang@suda.edu.cn

Common Base Triangle Area Representation Method for Shape Retrieval

HU Da-meng,HUANG Wei-guo,YANG Jian-yu,ZHU Zhong-kui

(School of Urban Rail Transportation,Soochow University,Suzhou,Jiangsu 215131,China)

Tosolvetheproblemofcontournoiseanddeformationinshapematching,anovelmethodbasedoncommonbasetriangleareaforimprovingretrievalaccuracyandcomputationalefficiencyisproposed.Firstly,acommonbasetriangleareadescriptorofeachsamplepointisdefinedbasedontheareafunctionsofthetrianglesformedbytheothersamplepointsanditstwoneighborpoints.Thenthedescriptorislocalsmoothedtokeepmorecompactandrobust.Secondly,amatchcostmatrixisobtainedbycomputingthecommonbasetriangleareadescriptorsofallthesamplepointsontwoshapes.Finally,thedistancebetweentwoshapesismeasuredbasedonthematchcostmatrixbyDPalgorithm.TheexperimentalresultsofMPEG-7,Kimiaandthearticulationshapedatabaseindicatethatthismethodisrobusttothecontourdeformation,andthecomputationalefficiencyandtheretrievalaccuracyareallessentiallyimproved.

commonbasetriangle;localsmoothing;dynamicprogramming;mixedretrieval;shapematching

2014-10-21;

2015-02-27；責(zé)任編輯：藍(lán)紅杰

國(guó)家自然科學(xué)基金(No.51405320,No.61305020);江蘇省科研基金(No.BK20130316)

TP391.4

A

0372-2112 (2016)05-1247-07

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.034