劉望舒 鄭丹晨 韓敏

形狀是一種高層次的視覺(jué)特征,其對(duì)應(yīng)物體中不受位置、尺度、旋轉(zhuǎn)因素影響的幾何信息[1],形狀分析在目標(biāo)檢測(cè)[2]、醫(yī)療分析[3]、古文字研究等[4]領(lǐng)域都發(fā)揮著重要的作用.在形狀分類(lèi)、形狀聚類(lèi)、形狀識(shí)別和形狀檢索等研究中,如何選擇有效的形狀匹配方法來(lái)分析形狀間距離都是需要解決的首要問(wèn)題.

在眾多的形狀匹配研究中,基于輪廓點(diǎn)空間位置關(guān)系特征的形狀匹配方法能夠較好地分析形狀間距離,是近年來(lái)最為重要的一類(lèi)方法[5].形狀上下文(Shape context,SC)是二十一世紀(jì)初由Belongie等[6]提出的一種形狀描述符,其通過(guò)分析輪廓上采樣點(diǎn)的分布情況而生成,可以兼顧形狀的局部信息和全局信息.形狀上下文作為最重要的形狀描述符之一,自提出以來(lái)得到廣泛的關(guān)注.廣義形狀上下文(Generalized shape context)[7]、骨架形狀上下文(Skeletal shape context)[8]、方向直方圖形狀上下文(Histogram of orientation shape context)[4]、實(shí)心形狀上下文(Solid shape context)[9]等都是在其基礎(chǔ)上改進(jìn)得到的形狀描述符,對(duì)應(yīng)形狀匹配方法都表現(xiàn)出了很好的識(shí)別和檢索效果.

在對(duì)形狀上下文進(jìn)行改進(jìn)的諸多方法中,Ling等[10]提出的內(nèi)距離形狀上下文(Inner-distance shape context,IDSC)是一種形狀匹配效果較好的描述符.該方法引入對(duì)連接不敏感的內(nèi)距離(Innerdistance,ID)替代歐幾里得距離(Euclidean distance,ED),進(jìn)而可以得到更合理的采樣點(diǎn)間距離.考慮到形狀上下文和內(nèi)距離形狀上下文分別具有不同的適用范圍,文獻(xiàn)[11]結(jié)合兩種形狀描述符的各自特點(diǎn),進(jìn)一步提出了地貌形狀上下文(Aspect shape context,ASC),該描述符能夠更好地平衡形狀描述符的魯棒性和區(qū)別能力.

雖然地貌形狀上下文能夠較好地結(jié)合形狀區(qū)域信息描述輪廓采樣點(diǎn)空間關(guān)系,但該方法依然存在一些不足.在形狀特征提取時(shí),計(jì)算測(cè)地距離(Geodesic distance,GD)的時(shí)間復(fù)雜度較高,使得形狀描述符構(gòu)造緩慢,影響了形狀匹配的效率;此外,在特征匹配過(guò)程中,原始方法僅選擇一個(gè)地貌空間對(duì)應(yīng)的形狀距離作為最終結(jié)果,難以綜合不同地貌空間的信息來(lái)解決形狀匹配問(wèn)題.

鑒于目前存在的問(wèn)題,本文提出了一種基于改進(jìn)地貌形狀上下文的形狀匹配方法.通過(guò)引入最短路徑算法對(duì)地貌空間下輪廓采樣點(diǎn)間的測(cè)地距離進(jìn)行快速計(jì)算,進(jìn)而提升形狀特征提取的效率.通過(guò)生成模糊直方圖來(lái)提升形狀描述符的表達(dá)能力,構(gòu)造出地貌模糊形狀上下文(Aspect fuzzy shape context,AFSC),其能夠更好地描述輪廓采樣點(diǎn)分布情況.考慮到輪廓點(diǎn)集順序關(guān)系已知,結(jié)合動(dòng)態(tài)規(guī)劃方法獲取不同地貌空間下形狀采樣點(diǎn)間準(zhǔn)確的對(duì)應(yīng)關(guān)系,進(jìn)而獲得準(zhǔn)確的形狀匹配結(jié)果.相比于傳統(tǒng)的形狀匹配方法,改進(jìn)后的方法能夠在較高的運(yùn)算效率下有效提升形狀匹配的結(jié)果,并獲得較好的形狀識(shí)別和檢索結(jié)果.

1 地貌形狀上下文

地貌形狀上下文是將地貌空間中測(cè)地距離引入對(duì)數(shù)極坐標(biāo)直方圖而得到的形狀描述符.地貌空間的測(cè)地距離是對(duì)歐氏距離和內(nèi)距離的折衷,其能夠更好地分析采樣點(diǎn)間的位置關(guān)系.因此,地貌形狀上下文可以更好地反映輪廓采樣點(diǎn)分布情況.

1.1 地貌空間下的測(cè)地距離

歐氏距離和內(nèi)距離是分析形狀采樣點(diǎn)間關(guān)系的兩種不同距離度量,在形狀匹配問(wèn)題中,二者表現(xiàn)出了不同的特點(diǎn).歐氏距離能有效地克服噪聲和局部形變所帶來(lái)的干擾,而內(nèi)距離可以較好地解決非剛性物體運(yùn)動(dòng)所產(chǎn)生的變化問(wèn)題.圖1給出了一組相似形狀的示例,對(duì)二者對(duì)應(yīng)輪廓采樣點(diǎn)間的距離進(jìn)行分析,分別利用ED(·,·) 和ID(·,·) 表示歐氏距離和內(nèi)距離.從圖中可以看出,內(nèi)距離對(duì)連接不敏感,能更準(zhǔn)確地表示圖1(b)中相似形狀對(duì)應(yīng)采樣點(diǎn)間的距離關(guān)系;歐氏距離則能消除噪聲干擾,更準(zhǔn)確地反映圖1(c)中相似形狀對(duì)應(yīng)采樣點(diǎn)間的距離關(guān)系.

圖1 以不同距離度量分析相似形狀對(duì)應(yīng)采樣點(diǎn)關(guān)系的示例Fig.1 An example of analyzing the distances between corresponding points from two similar shapes with different measures

為了平衡歐氏距離和內(nèi)距離,文獻(xiàn)[12]選擇地貌空間(Aspect space)中的測(cè)地距離來(lái)分析形狀上采樣點(diǎn)間位置關(guān)系.對(duì)于圖像I(·,·):Λ→[0,1],Λ?R2為圖像的區(qū)域,其對(duì)應(yīng)的地貌空間A?R3,(x,y)∈Λ,z=ηI(x,y),參數(shù)η∈[0,∞).給定η,地貌空間中兩點(diǎn)si與sj對(duì)應(yīng)的測(cè)地線Li,j,則測(cè)地線可以定義為

利用GD(·,·)表示測(cè)地線距離,進(jìn)一步可以得到

以二值圖像所表示的形狀為例,當(dāng)η=0時(shí),GD(i,j)對(duì)應(yīng)歐氏距離;當(dāng)η→∞時(shí),GD(i,j)對(duì)應(yīng)內(nèi)距離.因此,隨著參數(shù)η的變化,可以構(gòu)造出不同的地貌空間,得到對(duì)應(yīng)的測(cè)地距離,進(jìn)而更好地反映相似形狀對(duì)應(yīng)采樣點(diǎn)間的關(guān)系.

1.2 形狀上下文

形狀上下文是一種基于輪廓點(diǎn)位置關(guān)系的形狀描述符,其基本假設(shè)是形狀信息可以利用輪廓上有限數(shù)目的采樣點(diǎn)進(jìn)行表示,通常在輪廓上均勻采樣生成對(duì)應(yīng)的點(diǎn)集合[6].

假設(shè)集合P={p1,p2,···,pλ}中包含形狀輪廓上λ個(gè)采樣點(diǎn),分別以每個(gè)點(diǎn)為參考建立對(duì)數(shù)極坐標(biāo)直方圖.pi∈R2處對(duì)應(yīng)的對(duì)數(shù)極坐標(biāo)直方圖Hi={hi(m,n):1≤m≤M,1≤n≤N}可表示為

其中,1Bmn為特征函數(shù),Bmn為二維子集.(q?pi)∈Bmn時(shí),1Bmn(q)=1;否則,1Bmn(q)=0.由于對(duì)數(shù)極坐標(biāo)直方圖結(jié)構(gòu)比較特殊,兼顧了形狀的局部信息和全局信息,能夠很好地描述輪廓點(diǎn)分布情況.將Hi歸一化即可得到pi處對(duì)應(yīng)的形狀上下文.

假設(shè)P和Q分別為不同目標(biāo)輪廓上得到的采樣點(diǎn)集合,則匹配損失函數(shù)Dij可以表示為χ2距離

其中,pi∈P和qj∈Q所對(duì)應(yīng)的對(duì)數(shù)極坐標(biāo)直方圖分別為Hi和Hj.

構(gòu)造標(biāo)準(zhǔn)的形狀上下文和內(nèi)距離形狀上下文的過(guò)程中,分別引入歐氏距離和內(nèi)距離來(lái)分析形狀輪廓采樣點(diǎn)間關(guān)系,二者分別適用于表示不同類(lèi)型的形狀特征.地貌形狀上下文引入測(cè)地距離來(lái)建立對(duì)數(shù)極坐標(biāo)系下的直方圖,由于地貌空間中的測(cè)地距離可以同時(shí)兼顧歐氏距離和內(nèi)距離兩種度量標(biāo)準(zhǔn)的自身特點(diǎn),其對(duì)應(yīng)生成的形狀描述符能夠更準(zhǔn)確地描述形狀信息.

2 改進(jìn)的地貌形狀上下文特征提取方法

在構(gòu)造形狀描述符的過(guò)程中,測(cè)地距離能夠較為準(zhǔn)確地描述形狀信息,但分析計(jì)算測(cè)地距離的方法速度較慢,如Fast marching算法等,導(dǎo)致形狀特征提取效率較低.考慮到二值圖像對(duì)應(yīng)的地貌空間結(jié)構(gòu)比較特殊,本文將特征提取過(guò)程中的測(cè)地距離計(jì)算問(wèn)題近似為求解最短路徑問(wèn)題,可以有效提升效率.同時(shí)引入模糊直方圖更加合理地描述輪廓采樣點(diǎn)的分布情況.

2.1 快速計(jì)算地貌空間測(cè)地距離

由于形狀通常由目標(biāo)范圍的二值圖像進(jìn)行表示,即I(x,y)=1或I(x,y)=0,對(duì)應(yīng)生成的地貌空間結(jié)構(gòu)相對(duì)簡(jiǎn)單,其可視作由三個(gè)面所圍成:分別為平行于x,y軸的平面α,γ,及母線平行于z軸,準(zhǔn)線為形狀輪廓方程f(x,y)=0的柱面β.其中,α對(duì)應(yīng)z=η,即I(x,y)=1;β對(duì)應(yīng)形狀輪廓方程f(x,y)=0;γ對(duì)應(yīng)z=0,即I(x,y)=0.三個(gè)面之間有如下關(guān)系,α∩β=Γ,β∩γ=H,Γ和H分別表示兩條閉合曲線.圖2給出了一幅二值圖像和對(duì)應(yīng)地貌空間的示例,圖2(a)是一幅200像素×230像素二值圖像,圖2(b)是η=260時(shí)對(duì)應(yīng)生成的地貌空間.

圖2 一個(gè)二值圖像對(duì)應(yīng)生成的地貌空間示例Fig.2 An example of the aspect space obtained from a binary image

對(duì)于地貌空間A中的測(cè)地線Li,j,對(duì)應(yīng)的起點(diǎn)和終點(diǎn)分別為si∈A和sj∈A,參數(shù)方程定義為L(zhǎng)i,j(t)=(x(t),y(t),ηI(x,y)),t∈[0,1]. 當(dāng)滿足Li,j?α或Li,j?γ時(shí),可知,進(jìn)而由式(2)可得

圖3(a)給出了分別位于γ平面和α平面的兩條測(cè)地線片段Lb,c,Ld,e的示例.

圖3 地貌空間中測(cè)地線路徑示例Fig.3 An example of geodesic in the aspect space

當(dāng)測(cè)地線片段滿足Li,j?β,且Li,j與曲線Γ和曲線H分別交于兩點(diǎn)si和sj,由于柱面β為可展曲面,可將其所在面β展成平面,則經(jīng)過(guò)柱面β的測(cè)地線片段可對(duì)應(yīng)為平面中連接兩點(diǎn)的直線,由式(2)可得

對(duì)于形狀輪廓上任意兩點(diǎn)p1和pK,將其映射至地貌空間A中可以得到兩點(diǎn)s1∈Γ和sK∈Γ,其在A中對(duì)應(yīng)的測(cè)地線為L(zhǎng)1,K,曲線依次經(jīng)過(guò)點(diǎn)s1,s2,···,sK.根據(jù)測(cè)地線L1,K經(jīng)過(guò)曲面的不同,將其劃分為數(shù)個(gè)首尾相接的測(cè)地線片段,可得到分別經(jīng)過(guò)α平面,β柱面和γ平面的測(cè)地線片段,對(duì)應(yīng)集合{Li,i+1:1≤i≤K?1,Li,i+1?A}.圖3(a)給出了一個(gè)地貌空間上測(cè)地線劃分的示例.進(jìn)一步可利用式(5)和式(7)直接求解Li,i+1的長(zhǎng)度.測(cè)地線L1,K的長(zhǎng)度即為集合中各測(cè)地線片段Li,i+1長(zhǎng)度之和,1≤i≤K?1,即

已知形狀輪廓上采樣點(diǎn)集合P={pi:1≤i≤λ},pi=(xi,yi),將P映射至地貌空間A中曲線 Γ上得到集合SΓ={si:1≤i≤λ},si=(xi,yi,ηI(xi,yi));同時(shí)將P映射到地貌空間A中曲線H上得到集合SH={sj:λ+1≤j≤2λ},sj=(xj?λ,yj?λ,0). 進(jìn)而可以得到地貌空間A中的點(diǎn)集S=S?！萐H.對(duì)于任意si∈S和sj∈S,當(dāng)|i?j|=1或|i?j|=λ?1時(shí),GD(i,j)=‖si?sj‖2.

進(jìn)一步針對(duì)S建立對(duì)應(yīng)的圖模型G={S,E},其中eij∈E可通過(guò)下式得到

其中,ED(i,j)表示si和sj之間的歐氏距離.

形狀上下文特征的基本假設(shè)是利用有限數(shù)目采樣點(diǎn)描述形狀信息,本文也同樣設(shè)置固定數(shù)目采樣點(diǎn)對(duì)形狀進(jìn)行表示.對(duì)于任意輪廓上點(diǎn)pi∈P和pj∈P,分析地貌空間中二者間測(cè)地距離的過(guò)程,可以近似視作在集合S=S?！萐H中分析解決si和sj間最短路徑的問(wèn)題.當(dāng)采樣點(diǎn)個(gè)數(shù)λ→∞時(shí),求得的si與sj之間最短路徑即為測(cè)地距離,即

其中,k1,···,k?為最優(yōu)路徑上中間節(jié)點(diǎn)對(duì)應(yīng)的索引.

對(duì)于原始的測(cè)地距離計(jì)算方法,如Fast marching算法等,其是在均勻致密的網(wǎng)格劃分下求取測(cè)地距離.而對(duì)于本文方法而言,其可視作經(jīng)過(guò)化簡(jiǎn)后僅保留輪廓采樣點(diǎn)的結(jié)果,進(jìn)而利用最短路徑方法求取測(cè)地距離.對(duì)于Nb×Nb的二值圖像,Fast marching算法時(shí)間復(fù)雜度為,

其隨圖像尺寸Nb的增大顯著增加.此外,該算法底層運(yùn)算是求解二次方程的最大值,其過(guò)程復(fù)雜耗時(shí).本文利用Bellman-Ford算法時(shí)間復(fù)雜度為O(λ×2λ×EG),算法的底層運(yùn)算是比較求和,分析計(jì)算簡(jiǎn)單,其中EG為圖模型G邊的數(shù)目.可見(jiàn),本文方法的算法復(fù)雜度不受圖像尺寸影響.此外,由于E中已包含了很多最短路徑,也能有效減少算法迭代次數(shù).第4.1節(jié)將通過(guò)實(shí)驗(yàn)對(duì)比兩種方法的計(jì)算效率,說(shuō)明本文方法的優(yōu)勢(shì).

2.2 地貌模糊形狀上下文

為了更好地描述采樣點(diǎn)的分布情況,本文在特征提取過(guò)程中引入模糊直方圖[13],進(jìn)而構(gòu)造出了地貌模糊形狀上下文.

分別對(duì)logr和θ均勻劃分得到M個(gè)模糊子集和N個(gè)模糊子集,進(jìn)而可得模糊隸屬度函數(shù)和如式(10)和(11)所示.

進(jìn)一步可得二維模糊子集Fm,n.二維模糊子集Fm,n對(duì)應(yīng)的模糊隸屬度函數(shù)為

在構(gòu)造模糊直方圖的過(guò)程中,本文以地貌空間中測(cè)地距離分析表示采樣點(diǎn)間距離.為了更好地反映采樣點(diǎn)之間的空間關(guān)系,引入不同參數(shù)η下地貌空間的測(cè)地距離分別構(gòu)造形狀描述符.

在地貌參數(shù)η取值逐漸增大的過(guò)程中,采樣點(diǎn)間測(cè)地距離發(fā)生改變的情況越來(lái)越少,因而提取的形狀特征也逐漸趨于不變.參照文獻(xiàn)[12]在形狀特征提取過(guò)程中選擇8組地貌空間,本文結(jié)合η與形狀特征變化的關(guān)系,設(shè)置;當(dāng)k=8時(shí),ηk=∞,其中EDavg表示采樣點(diǎn)間歐氏距離的均值.

將在ηk對(duì)應(yīng)的地貌空間中,以采樣點(diǎn)pi∈P為參考生成的:1≤m≤M,1≤n≤N}定義為地貌模糊形狀上下文.對(duì)于不同形狀上兩點(diǎn)pi∈P和qj∈Q,在ηk對(duì)應(yīng)地貌空間中的匹配損失函數(shù)可表示為

相對(duì)框架下構(gòu)造對(duì)數(shù)極坐標(biāo)直方圖過(guò)程中,不同采樣點(diǎn)對(duì)應(yīng)的全局信息通常比較接近,難以起到判別作用.因此在形狀特征提取過(guò)程中,選擇距離參考點(diǎn)較近的直方圖片段分析匹配損失函數(shù).因而本文選擇在logr方向下均勻劃分8個(gè)模糊子集,選取前6個(gè)模糊子集構(gòu)造對(duì)數(shù)極坐標(biāo)模糊直方圖,并沿θ方向劃分12個(gè)模糊子集,即式(15)中設(shè)置M=6,N=12.

3 基于地貌模糊形狀上下文的特征匹配

在基于輪廓點(diǎn)集的形狀匹配方法中,特征匹配對(duì)應(yīng)了分析采樣點(diǎn)間對(duì)應(yīng)關(guān)系的過(guò)程.在構(gòu)造地貌模糊形狀上下文形狀特征的基礎(chǔ)上,本節(jié)進(jìn)一步結(jié)合動(dòng)態(tài)規(guī)劃方法分析不同形狀輪廓采樣點(diǎn)間對(duì)應(yīng)關(guān)系,進(jìn)而得到形狀匹配的結(jié)果.

傳統(tǒng)方法選擇一個(gè)合適的地貌空間分析兩形狀間距離,通過(guò)選擇折衷的測(cè)地距離代替內(nèi)距離或歐氏距離.但是對(duì)于一對(duì)相似的形狀而言,很多情況下輪廓上不同位置片段在相同的地貌空間下難以很好地匹配,往往需要在不同地貌空間下分析各輪廓片段間距離,在此基礎(chǔ)上進(jìn)一步整合得到采樣點(diǎn)間對(duì)應(yīng)關(guān)系.

因此在形狀特征匹配過(guò)程中,本文首先篩選出不同地貌空間下地貌模糊形狀上下文最優(yōu)的匹配結(jié)果,而后在得到對(duì)應(yīng)距離矩陣的基礎(chǔ)上進(jìn)一步分析采樣點(diǎn)對(duì)應(yīng)關(guān)系.對(duì)于以λ個(gè)采樣點(diǎn)表示的形狀P和Q,分別得到對(duì)應(yīng)的形狀特征集合和,不同地貌空間下形狀描述符匹配的最優(yōu)結(jié)果構(gòu)成的λ×λ矩陣D可由下式得到

輪廓采樣點(diǎn)順序關(guān)系已知的基礎(chǔ)上,使用動(dòng)態(tài)規(guī)劃算法分析P和Q上各點(diǎn)間對(duì)應(yīng)關(guān)系.對(duì)于λ×λ維的矩陣DT,初始化以下的元素

并利用下式更新其他元素

其中,τ是懲罰參數(shù),1≤i≤λ,1≤j≤λ.形狀間距離可以表示為Dis(P,Q)=DT(λ,λ).

為克服目標(biāo)旋轉(zhuǎn)對(duì)形狀匹配造成的影響,進(jìn)一步將矩陣D進(jìn)行G次循環(huán)移位,第g次循環(huán)移位對(duì)應(yīng)矩陣Dg

從本節(jié)的分析可知,由形狀特征計(jì)算得到矩陣D的時(shí)間復(fù)雜度為O(K×λ2),在此基礎(chǔ)上分析采樣點(diǎn)間對(duì)應(yīng)關(guān)系的算法復(fù)雜度為O(G×λ2).由于參數(shù)K和G均取值較小,可知形狀特征匹配時(shí)間復(fù)雜度為O(λ2).

4 數(shù)據(jù)仿真

為了驗(yàn)證本文所提方法的有效性,將分別從形狀特征提取效率和形狀檢索結(jié)果精度兩個(gè)角度進(jìn)行設(shè)計(jì)實(shí)驗(yàn)并加以分析.為了對(duì)比公平,本文參考文獻(xiàn)[10,13]的工作,實(shí)驗(yàn)中均設(shè)置形狀輪廓的采樣點(diǎn)數(shù)目為100,即λ=100.

4.1 形狀特征提取效率

首先,通過(guò)設(shè)計(jì)實(shí)驗(yàn)對(duì)不同方法下測(cè)地距離計(jì)算時(shí)間進(jìn)行分析比較.對(duì)于不同尺寸下三幅相同的二值圖像,分別分析計(jì)算采樣點(diǎn)間的測(cè)地距離.

圖4(a)給出了實(shí)驗(yàn)所用的三幅具有不同特點(diǎn)的二值圖像,包含簡(jiǎn)單邊界、復(fù)雜邊界和不規(guī)則邊界的情形,實(shí)驗(yàn)過(guò)程中設(shè)圖幅大小為Nb像素×Nb像素,Nb=50,100,150,···,500.實(shí)驗(yàn)在相同環(huán)境下運(yùn)行,計(jì)算機(jī)配置是3.60GHz和8G內(nèi)存,兩種方法均通過(guò)Matlab與VC混合編程實(shí)現(xiàn).選擇文獻(xiàn)[11]中的Fast marching算法和本文提出了最短路徑方法進(jìn)行對(duì)比,本文最短路徑方法通過(guò)Bellman-Ford算法實(shí)現(xiàn).不同方法下對(duì)同一幅圖像分別進(jìn)行100次實(shí)驗(yàn),取平均時(shí)間作為最終結(jié)果.

圖4 分析不同方法計(jì)算測(cè)地距離效率Fig.4 Efficiency comparison of computing geodesic distances by using different methods

圖4(b)給出了用這兩種方法分別計(jì)算各采樣點(diǎn)之間的測(cè)地距離所需時(shí)間的比較,橫坐標(biāo)表示圖幅的大小Nb,縱坐標(biāo)表示計(jì)算時(shí)間的對(duì)數(shù)log(t).從圖中可以看出,無(wú)論目標(biāo)的輪廓邊界為何種情況,Fast marching算法計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)大于本文提出方法,且Fast marching算法的計(jì)算時(shí)間隨圖像大小的增大而顯著增加,而本文方法對(duì)于不同大小的二值圖像均能得到較高的計(jì)算效率.

為了更好地說(shuō)明不同方法下的形狀特征提取效率,進(jìn)一步選擇一個(gè)完整的形狀數(shù)據(jù)集分析比較.這里選擇Kimia-99數(shù)據(jù)集[14]進(jìn)行仿真實(shí)驗(yàn),該數(shù)據(jù)集包含9個(gè)類(lèi)別各11個(gè)樣本,部分樣本的示例如圖5所示.分別用兩種方法對(duì)該數(shù)據(jù)集下的全部99個(gè)樣本進(jìn)行形狀特征提取,特征提取過(guò)程中按照第2.2節(jié)的分析進(jìn)行參數(shù)設(shè)置,表1給出了兩種方法特征提取時(shí)間的結(jié)果比較.從表中可以看出本文所提方法能夠有效改善形狀特征提取過(guò)程的計(jì)算速度.

圖5 Kimia-99數(shù)據(jù)集中形狀樣本示例Fig.5 Examples of shapes in Kimia-99 database

表1 Kimia-99數(shù)據(jù)形狀特征提取時(shí)間比較(s)Table 1 Comparison of the time used for shape feature extraction on Kimia-99 database(s)

4.2 形狀檢索精度

為了驗(yàn)證本文所提形狀匹配方法的性能,此部分給出對(duì)不同數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)的結(jié)果,并與其他文獻(xiàn)中方法進(jìn)行詳細(xì)地分析比較.在實(shí)驗(yàn)過(guò)程中,按照第2.2節(jié)和第3節(jié)給出的參數(shù)設(shè)置規(guī)則對(duì)本文所提方法參數(shù)進(jìn)行設(shè)置.為了確定懲罰參數(shù)τ,對(duì)Kimia-99數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)并做對(duì)比分析.在固定其他參數(shù)取值不變的基礎(chǔ)上,分別取τ=0.8,1.2,···,4.0,可以得到如圖6所示的PR曲線.從圖中可以看出,本文方法對(duì)特征匹配過(guò)程中的懲罰參數(shù)并不敏感,τ取值在1.2～3.2之間均能得到較好的匹配結(jié)果,本文后續(xù)試驗(yàn)中設(shè)置τ=2.0.

在Kimia-99數(shù)據(jù)集和Kimia-216數(shù)據(jù)集[15]兩個(gè)樣本數(shù)較少的數(shù)據(jù)集下進(jìn)行形狀匹配實(shí)驗(yàn).Kimia-99數(shù)據(jù)集在第4.1節(jié)用于進(jìn)行了形狀特征提取實(shí)驗(yàn),Kimia-216數(shù)據(jù)集包含18個(gè)類(lèi)別各12個(gè)樣本,部分示例如圖7所示.表2和表3分別列出了不同形狀匹配方法在Kimia-99和Kimia-216數(shù)據(jù)集上得到的形狀檢索結(jié)果.表2和表3中各列分別表示與查詢樣本近鄰的檢索結(jié)果所屬類(lèi)別正確與否,其中包含了最接近的1～10組相關(guān)樣本數(shù)目及合計(jì)相關(guān)樣本數(shù)目.由表中結(jié)果可以看出,對(duì)于Kimia-99和Kimia-216兩個(gè)包含樣本數(shù)較少的數(shù)據(jù)集,本文所提方法能夠較好地分析得到形狀間的距離關(guān)系,對(duì)比其他方法可以得到更準(zhǔn)確的形狀檢索結(jié)果.

圖6 參數(shù)τ變化對(duì)應(yīng)的PR曲線Fig.6 Precision-recall curves for different τ

圖7 Kimia-216數(shù)據(jù)集中形狀樣本示例Fig.7 Examples of shapes in Kimia-216 database

為驗(yàn)證本文方法在不同數(shù)據(jù)集下的有效性,這里選擇樣本數(shù)較多的Tari-1000[23]數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn).Tari-1000數(shù)據(jù)集中包含50個(gè)類(lèi)別各20個(gè)樣本,圖8給出了部分樣本的示例.實(shí)驗(yàn)中選用Bull′s eye score作為檢索精度的評(píng)價(jià)指標(biāo):在一次形狀檢索過(guò)程中,選擇與查詢形狀最相似的40個(gè)形狀樣本,統(tǒng)計(jì)其中與查詢形狀屬于相同類(lèi)別的樣本數(shù)目,計(jì)算對(duì)應(yīng)的查全率.

表2 Kimia-99數(shù)據(jù)在不同方法下檢索結(jié)果比較Table 2 Comparison of retrieval rates for different algorithms tested on Kimia-99 database

表3 Kimia-216數(shù)據(jù)在不同方法下檢索結(jié)果比較Table 3 Comparison of retrieval rates for different algorithms tested on Kimia-216 database

圖8 Tari-1000形狀樣本示例Fig.8 Examples of shapes in Tari-1000 database

表4列出了不同形狀匹配方法在Tari-1000數(shù)據(jù)集上的形狀檢索結(jié)果,可以看出對(duì)比其他文獻(xiàn)中給出的形狀匹配方法,本文所提方法能夠得到更好的形狀檢索結(jié)果.通過(guò)給出的實(shí)驗(yàn)結(jié)果可以看出,本文所提形狀匹配方法在不同規(guī)模的形狀數(shù)據(jù)集下均能夠獲得較好的形狀檢索結(jié)果.

[3,9,12]的做法,本文方法引入了輪廓點(diǎn)順序關(guān)系作為先驗(yàn)信息,能夠更好地反映形狀全局信息.對(duì)于包含順序關(guān)系的輪廓點(diǎn)集,可以在提取目標(biāo)邊緣的基礎(chǔ)上采樣得到.

表4 Tari-1000數(shù)據(jù)在不同方法下的結(jié)果比較Table 4 Comparison of results for different algorithms tested on Tari-1000 database

5 結(jié)論

鑒于地貌形狀上下文存在的不足,本文提出了一種基于改進(jìn)地貌形狀上下文的形狀匹配方法.將地貌空間測(cè)地距離的求解近似為最短路徑問(wèn)題,相比于經(jīng)典算法,本文方法有效地提高了形狀特征提取效率.通過(guò)引入對(duì)數(shù)極坐標(biāo)模糊直方圖,構(gòu)造地貌模糊形狀上下文形狀特征,其能夠更好地描述形狀輪廓信息.進(jìn)一步引入動(dòng)態(tài)規(guī)劃方法分析不同地貌空間下形狀間采樣點(diǎn)對(duì)應(yīng)關(guān)系,能夠準(zhǔn)確地計(jì)算得到形狀距離.通過(guò)對(duì)不同數(shù)據(jù)集樣本進(jìn)行仿真實(shí)驗(yàn),證明了本文所提方法具有良好的形狀檢索效果.

1 Kendall D G.Shape manifolds,procrustean metrics,and complex projective spaces.Bulletin of the London Mathematical Society,1984,16(2):81?121

2 Su Y Q,Liu Y H,Cuan B N,Zheng N N.Contour guided hierarchical model for shape matching.In:Proceedings of the 15th IEEE International Conference on Computer Vision.Santiago,Chile:IEEE,2015.1609?1617

3 Janan F,Brady M.Shape description and matching using integral invariants on eccentricity transformed images.International Journal of Computer Vision,2015,113(2):92?112

4 Roman-Rangel E,Pallan C,Odobez J M,Gatica-Perez D.Analyzing ancient maya glyph collections with contextual shape descriptors.International Journal of Computer Vision,2011,94(1):101?117

5 Zhou Yu,Liu Jun-Tao,Bai Xiang.Research and perspective on shape matching.Acta Automatica Sinica,2012,38(6):889?910(周瑜,劉俊濤,白翔.形狀匹配方法研究與展望.自動(dòng)化學(xué)報(bào),2012,38(6):889?910)

6 Belongie S,Malik J,Puzicha J.Shape matching and object recognition using shape contexts.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(4):509?522

7 Mori G,Belongie S,Malik J.Efficient shape matching using shape contexts.IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(11):1832?1837

8 Xie J,Heng P A,Shah M.Shape matching and modeling using skeletal context.Pattern Recognition,2008,41(5):1756?1767

9 Premachandran V,Kakarala R.Perceptually motivated shape context which uses shape interiors.Pattern Recognition,2013,46(8):2092?2102

10 Ling H B,Jacobs D W.Shape classi fi cation using the innerdistance.IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(2):286?299

11 Ling H B,Yang X W,Latecki L J.Balancing deformability and discriminability for shape matching.In:Proceedings of the 11th European Conference on Computer Vision.Crete,Greece:Springer,2010.411?424

12 Ling H B,Jacobs D W.Deformation invariant image matching.In:Proceedings of the 10th IEEE International Conference on Computer Vision.Beijing,China:IEEE,2005.1466?1473

13 Han Min,Zheng Dan-Chen.Shape recognition based on fuzzy shape context.Acta Automatica Sinica,2012,38(1):68?75(韓敏,鄭丹晨.基于模糊形狀上下文特征的形狀識(shí)別算法.自動(dòng)化學(xué)報(bào),2012,38(1):68?75)

14 Sebastian T B,Klein P N,Kimia B B.Recognition of shapes by editing their shock graphs.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(5):550?571

15 Sebastian T B,Klein P N,Kimia B B.On aligning curves.IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(1):116?125

16 Donoser M,Riemenschneider H,Bischof H.Efficient partial shape matching of outer contours.In:Proceedings of the 9th Asian Conference on Computer Vision.Xi'an China:Springer,2010.281?292

17 Egozi A,Keller Y,Guterman H.Improving shape retrieval by spectral matching and meta similarity.IEEE Transactions on Image Processing,2010,19(5):1319?1327

18 Wang J W,Bai X,You X G,Liu W Y,Latecki L J.Shape matching and classi fi cation using height functions.Pattern Recognition Letters,2012,33(2):134?143

19 Daliri M R,Torre V.Robust symbolic representation for shape recognition and retrieval.Pattern Recognition,2008,41(5):1782?1798

20 Tu Z W,Yuille A L.Shape matching and recognition-using generative models and informative features.In:Proceedings of the 8th European Conference on Computer Vision.Prague,Czech Republic:Springer,2004.195?209

21 Siddiqi K,Shokoufandeh A,Dickinson S J,Zucker S W.Shock graphs and shape matching.International Journal of Computer Vision,1999,35(1):13?32

22 Bai X,Latecki L J.Path similarity skeleton graph matching.IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(7):1282?1292

23 Baseski E,Erdem A,Tari S.Dissimilarity between two skeletal trees in a context.Pattern Recognition,2009,42(3):370?385

24 Wang Z,Ouyang J.Shape classes registration and retrieval based on shape parts matching.Journal of Computational Information Systems,2013,9(4):1493?1499

25 Zhou Y,Wang J W,Zhou Q,Bai X,Liu W Y.Shape matching using points co-occurrence pattern.In:Proceedings of the 6th International Conference on Image and Graphics.Hefei,China:IEEE,2011.344?349

26 Wang J W,Zhou Y,Bai X,Liu W Y.Shape matching and recognition using group-wised points.In:Proceedings of the 5th Paci fi c Rim Symposium on Image and Video Technology.Gwangju,Korea:Springer,2012.393?404