于 洋,鄭 偉,宋建輝,劉硯菊

(沈陽理工大學(xué)自動化與電氣工程學(xué)院,遼寧 沈陽 110159)

1 引言

目標(biāo)識別與匹配作為計算機(jī)視覺領(lǐng)域的研究熱點(diǎn),廣泛應(yīng)用于圖像檢索、人臉識別、醫(yī)學(xué)影像分析等領(lǐng)域。因?yàn)槲矬w的形狀具有十分穩(wěn)定和重要的視覺特征,所以形狀一直是目標(biāo)匹配中一項(xiàng)有效且利用率較高的特征[1]。形狀表示方法可以大體上分為三類:基于輪廓的形狀表示、基于區(qū)域的形狀表示和基于骨架的形狀表示[2]?；谳喞谋硎痉椒ㄊ窃谔崛D像輪廓的基礎(chǔ)上對其外部邊緣進(jìn)行描述。國內(nèi)外學(xué)者對基于輪廓特征的目標(biāo)識別方法展開了廣泛研究,提出了大量描述輪廓特征的方法[3]。

Belongie等[4]提出的形狀上下文描述符,作為近年來最具有代表性的輪廓描述方法,因識別效果良好、抗干擾性強(qiáng)等優(yōu)勢被廣泛應(yīng)用于形狀檢索領(lǐng)域,但該描述符不具有旋轉(zhuǎn)不變性。吳曉雨等[5]提出一種具有旋轉(zhuǎn)不變性的形狀上下文識別算法,通過尋找采樣點(diǎn)最多的角度區(qū)間的方法改變圖像角度,為形狀上下文描述符加入旋轉(zhuǎn)不變性。張桂梅等[6]將內(nèi)部距離代替歐氏距離,提出內(nèi)距離形狀上下文描述符,對于存在非剛性和肢體變化的目標(biāo)取得了較好的識別效果,但描述符構(gòu)建復(fù)雜,計算量大。Mokhtarian等[7]提出曲率尺度空間描述符,對于邊界噪聲以及尺度變化具有良好的魯棒性,但需要對輪廓進(jìn)行進(jìn)一步演化,增加了特征提取的工作量,且識別精度較低。Alajlan等[8]提出基于三角形區(qū)域表示的形狀描述符,有效的獲取了目標(biāo)的全局以及局部信息,但該方法識別魯棒性差,對相似形狀的區(qū)分能力較低。

為解決傳統(tǒng)目標(biāo)識別算法識別準(zhǔn)確率低、復(fù)雜度高等問題,本文提出基于質(zhì)心高度增量特征的目標(biāo)識別算法,根據(jù)輪廓點(diǎn)相對于質(zhì)心高度的變化構(gòu)建質(zhì)心高度增量形狀描述符,該描述符對于目標(biāo)形狀的平移、旋轉(zhuǎn)、縮放以及翻轉(zhuǎn)具有很好的不變性,引入輪廓順序這一全局特征和平滑化處理降低描述符對噪聲和非線性形變的敏感性。最后引入動態(tài)規(guī)劃和形狀復(fù)雜度分析相結(jié)合的方法實(shí)現(xiàn)目標(biāo)的匹配識別。實(shí)驗(yàn)結(jié)果證明,與形狀上下文等傳統(tǒng)算法相比,本文算法能獲得更穩(wěn)定、準(zhǔn)確的識別效果。

2 質(zhì)心高度增量描述符

對于目標(biāo)圖像,首先選用Canny分割算法提取其邊緣輪廓,對提取的輪廓均勻采樣,得到輪廓部分點(diǎn)集記為P={pi}(i=1,2,…,N),其中N為采樣點(diǎn)的個數(shù),pi為輪廓第i個采樣點(diǎn)。設(shè)采樣點(diǎn)pi(xi,yi),輪廓質(zhì)心W(x0,y0)的計算公式如下

(1)

目標(biāo)輪廓提取及采樣結(jié)果如圖1所示,圖1中(a)表示目標(biāo)圖像;(b)表示提取的目標(biāo)輪廓;(c)表示輪廓采樣點(diǎn)及質(zhì)心分布。

圖1 輪廓提取及采樣效果圖

要計算輪廓的質(zhì)心高度增量,最重要的是求出采樣點(diǎn)與質(zhì)心的距離,即質(zhì)心高度值,該值表征了采樣點(diǎn)在輪廓上的位置,對于采樣點(diǎn)pi(xi,yi),定義質(zhì)心高度gi為該點(diǎn)與質(zhì)心W(x0,y0)的歐氏距離,即

(2)

這樣可以得到輪廓N個采樣點(diǎn)的質(zhì)心高度值,定義任一采樣點(diǎn)pj(j=1,2,…N)與當(dāng)前采樣點(diǎn)pi的質(zhì)心高度的差值為質(zhì)心高度增量hi,j,即

hi,j=gj-gi(j=1,2,…N)

(3)

質(zhì)心高度增量有正有負(fù),正負(fù)號可以精確地表示點(diǎn)與點(diǎn)相對于質(zhì)心的位置關(guān)系。由于輪廓順序是一種自然存在的全局特征,可以與質(zhì)心高度增量這一局部特征融合使用,因此將所有采樣點(diǎn)相對于點(diǎn)pi的質(zhì)心高度增量按輪廓點(diǎn)順序排列,得到采樣點(diǎn)pi的質(zhì)心高度增量序列Hi,如式(4)所示

Hi=(hi,i,hi,i+1,..hi,N,hi,1,..hi,i-1)T

(4)

圖2給出了不相似輪廓采樣點(diǎn)的質(zhì)心高度增量特征提取效果圖,其中圖(a)、(b)表示心形輪廓和蝙蝠輪廓均勻采樣,分別標(biāo)記了3個輪廓點(diǎn)A、B以及C;圖(c)、(e)、(g)分別為心形輪廓A、B、C三點(diǎn)對應(yīng)的質(zhì)心高度增量特征,圖(d)、(f)、(h)分別為蝙蝠輪廓A、B、C三點(diǎn)對應(yīng)的質(zhì)心高度增量特征。從圖2可以看出,輪廓上的不同采樣點(diǎn),其質(zhì)心高度增量特征具有唯一性,可以用來描述輪廓信息。將形狀輪廓P上每個點(diǎn)對應(yīng)的質(zhì)心高度增量序列Hi按照輪廓點(diǎn)順序排列,得到一個尺寸為N×N的矩陣:

圖2 不同形狀采樣點(diǎn)的質(zhì)心高度增量描述符

L(P)=(H1,H2,…,HN-1,HN)

(5)

式中L(P)表示輪廓的質(zhì)心高度增量矩陣,矩陣的第i列表示輪廓P上采樣點(diǎn)pi的質(zhì)心高度增量描述符。該描述符描述了輪廓點(diǎn)與點(diǎn)之間的相對高度關(guān)系,不隨輪廓的旋轉(zhuǎn)和平移而變化,為使該描述符具有縮放不變性,對矩陣的每一行進(jìn)行歸一化處理

(6)

式(4)定義了采樣點(diǎn)pi相對于輪廓所有采樣點(diǎn)的質(zhì)心高度增量,這樣雖然有效的描述了輪廓信息,但對噪聲引起的輪廓局部變形過于敏感,同時特征維數(shù)過高、計算復(fù)雜,在此采用文獻(xiàn)[9]中的策略,在描述符的精確性、抗噪性、簡潔性之間取得一個很好的折中,具體過程如下:

對于pi點(diǎn)的質(zhì)心高度增量可表示為

(7)

該序列包含了N個元素,對應(yīng)N個采樣點(diǎn)相對于該點(diǎn)的質(zhì)心高度增量,加入正整數(shù)系數(shù)k(1

(8)

式中t=1,2,…M。把M個均值數(shù)據(jù)進(jìn)行有序排列,得到點(diǎn)pi經(jīng)過平滑化處理后的特征序列Gi,即

Gi=(gi,1,gi,2,….gi,M-1,gi,M)T

(9)

經(jīng)過平滑處理后,不僅提高了描述符對輪廓變形以及噪聲干擾的魯棒性,同時降低了特征向量的維度,方便后續(xù)的匹配。將所有采樣點(diǎn)平滑后的描述符按序排列,得到輪廓P的質(zhì)心高度增量特征矩陣E(P):

E(P)=(G1,G2,…,GN-1,GN)

(10)

3 形狀相似性度量

在獲取形狀的特征描述符后,計算兩個形狀的相似程度,由于質(zhì)心高度增量描述符包含輪廓點(diǎn)集順序這一全局特征,本文選取了動態(tài)規(guī)劃算法對得到的形狀特征進(jìn)行匹配。

3.1 基于動態(tài)規(guī)劃算法的相似度匹配

質(zhì)心高度增量描述符刻畫的是輪廓點(diǎn)與點(diǎn)之間的特征關(guān)系,首先計算兩個形狀上采樣點(diǎn)間的匹配代價,不同輪廓采樣點(diǎn)之間的特征越相似,匹配代價越小。假設(shè)采樣點(diǎn)pi和qj分別屬于形狀P和Q,定義匹配代價為pi、qj兩點(diǎn)對應(yīng)的質(zhì)心高度增量特征Gi和Gj之間的距離。考慮到接近采樣點(diǎn)pi和qj的質(zhì)心高度增量的作用更大,為此設(shè)計權(quán)重系數(shù)wt突出輪廓的局部特征,計算公式如式(11)

(11)

在此基礎(chǔ)上,得到匹配代價c(pi,qj)的計算公式如式(12)

(12)

式中d(gi,t,gj,t)表示pi、qj兩點(diǎn)在其質(zhì)心高度增量第t個分量上的數(shù)據(jù)差值。

在獲得了任意兩個點(diǎn)的匹配代價后,進(jìn)行輪廓點(diǎn)集間的匹配,采用動態(tài)規(guī)劃算法進(jìn)行匹配,確定對應(yīng)關(guān)系使得輪廓間每對輪廓點(diǎn)的匹配代價的總和最小,設(shè)形狀P的采樣點(diǎn)pi與形狀Q中的采樣點(diǎn)τ(pi)相匹配,則兩個形狀的距離差異定義為:

(13)

其中c(pi,τ(pi))為采樣點(diǎn)pi和τ(pi)之間的匹配代價。由于形狀的復(fù)雜度越高,對輪廓局部變形的敏感度越低,識別出的結(jié)果越具有可信性,因此引入形狀復(fù)雜度進(jìn)一步提升輪廓的匹配效果,定義形狀輪廓的復(fù)雜度為:

(14)

式中std表示標(biāo)準(zhǔn)差.通過引入形狀復(fù)雜度最終得到兩個形狀之間的距離S(P,Q):

(15)

式中C(P)和C(Q)分別為形狀P和Q的復(fù)雜度,η為調(diào)整分母大小的參數(shù),根據(jù)經(jīng)驗(yàn)可適當(dāng)調(diào)整。

此外實(shí)際識別過程中,往往會出現(xiàn)待識別目標(biāo)存在翻轉(zhuǎn)的情況,容易造成誤匹配,因此采取一個簡單的策略:將待檢測目標(biāo)P進(jìn)行翻轉(zhuǎn)得到形狀PF,將形狀P和PF分別與形狀Q匹配,取兩者中匹配的最小距離作為形狀P和Q的最終匹配結(jié)果。

本文算法的結(jié)構(gòu)框圖如圖3所示。

圖3 算法框圖

4 仿真與分析

為驗(yàn)證本文提出的目標(biāo)識別算法的有效性,分別在MPEG-7和Kimia99這兩種常用測試集上進(jìn)行圖像的匹配實(shí)驗(yàn),并對算法的抗噪性能進(jìn)行測試。在實(shí)驗(yàn)中,輪廓的采樣點(diǎn)數(shù)取N=100,式(8)中的平滑系數(shù)取k=5,式(15)中調(diào)整分母的參數(shù)取η=0.45。

4.1 MPEG-7測試集識別測試

MPEG-7測試集包含70類形狀,每類20張圖片共1400張圖片,涵蓋動物、物體等多種形狀,包括了形狀的各種線性變換以及肢體變化、遮擋等非線性形變。采用Bull-eye得分獲取本文算法在MPEG-7測試集上的檢索識別性能,檢索率定義為:對測試集中的每一個形狀,識別出與其最相似的40個形狀,統(tǒng)計這些形狀中屬于待識別形狀類別的數(shù)目,對所有形狀的統(tǒng)計數(shù)據(jù)求和之后除以28000(1400 × 20),即得檢索率。表1所示為本文算法和其它部分算法在該測試集上的識別結(jié)果。從中可以看出,本文算法可以取得較好的識別效果,檢索率達(dá)到了93.05%,優(yōu)于表中提出的幾種常用目標(biāo)識別算法,較SC和CSS算法的優(yōu)勢尤為明顯。

表1 MPEG-7測試集檢索精度

表2給出了本文算法在MPEG-7測試集上的部分目標(biāo)匹配結(jié)果,其中第1列為待測目標(biāo),第2～9列為匹配結(jié)果以及對應(yīng)的形狀距離值,待測目標(biāo)1st～8th的形狀距離值從小到大,表示與其第1到第8相似的識別結(jié)果,可以看出本文提出的算法能夠較好的實(shí)現(xiàn)目標(biāo)形狀的識別。

表2 MPEG-7測試集部分目標(biāo)匹配示例

4.2 Kimia99測試集匹配測試

Kimia99測試集包含9類形狀,每類11張圖片共99張,如圖4所示。該測試集同樣包含了形狀的旋轉(zhuǎn)、平移以及縮放等幾何變換,被廣泛應(yīng)用于目標(biāo)識別與分類中。對于測試集中的每個形狀,統(tǒng)計出與其第1到第10相似的識別結(jié)果中識別正確的形狀數(shù)目(不包含待識別目標(biāo)本身),將所有形狀的統(tǒng)計合計結(jié)果作為本文算法在Kimia99測試集上的檢索表現(xiàn),因?yàn)闇y試集共有99個形狀,所以每組數(shù)值的最佳結(jié)果便為99。

圖4 Kimia99圖像測試集

表3給出了不同方法在該測試集上的識別結(jié)果,從中可以看出相較于其它算法,本文算法識別效果最佳,優(yōu)于SC和IDSC等常見目標(biāo)識別算法。

表3 多種方法在Kimia99測試集上的檢索結(jié)果

本文算法在MPEG-7和Kimia99測試集上均取得優(yōu)異的識別效果,這取決于以下原因:1)質(zhì)心高度增量描述符對輪廓特征表達(dá)精確,這種輪廓點(diǎn)之間精細(xì)的描述提高了相似形狀的類間區(qū)分度;2)無論是形狀上下文還是內(nèi)距離形狀上下文,都是將輪廓點(diǎn)分散到各個區(qū)域,破壞了輪廓順序這一全局特征,而本文方法則是將這一全局特征與質(zhì)心高度增量特征有機(jī)的結(jié)合起來,有效的提升了識別準(zhǔn)確率;3)本文將形狀復(fù)雜度分析與動態(tài)規(guī)劃相結(jié)合進(jìn)行匹配識別,在動態(tài)規(guī)劃求得形狀相似度的基礎(chǔ)上,通過評價輪廓的復(fù)雜度進(jìn)一步提升了匹配結(jié)果的可信度。

4.3 噪聲干擾下的檢索效果測試

為測試本文算法的抗噪性能,本節(jié)對帶有噪聲的形狀輪廓進(jìn)行識別,獲得帶噪輪廓的方式如下:對Kimia99測試集的所有圖片輪廓點(diǎn)的橫縱坐標(biāo)加入均值μ=0,標(biāo)準(zhǔn)差由σ=0.2到σ=0.8的高斯噪聲,分別統(tǒng)計出與其第1到第10相似的識別結(jié)果中識別正確的形狀數(shù)目(不包含待識別目標(biāo)本身),將所有形狀的統(tǒng)計合計結(jié)果作為本文方法在受到噪聲干擾的Kimia99測試集上的檢索結(jié)果,表4給出了本文方法在噪聲環(huán)境下的檢索結(jié)果。

表4 本文方法在受到噪聲干擾的Kimia99測試集上的檢索結(jié)果

由表4可以看出,噪聲水平在0-0.4之間時,檢索表現(xiàn)受噪聲影響不大,噪聲水平在0.6-0.8之間時,檢索效果出現(xiàn)了較大程度下降,但仍能保持較高的識別精度。由此驗(yàn)證,本文方法對于輪廓噪聲干擾的魯棒性較強(qiáng),這得益于本文算法引入輪廓順序信息這一全局特征,對噪聲干擾的敏感性降低,同時采用平滑技術(shù)處理特征向量,也有效提高了本文算法對于輪廓噪聲的魯棒性。

4.4 算法空間復(fù)雜度分析

目標(biāo)識別算法的空間復(fù)雜度主要體現(xiàn)在形狀特征描述符對應(yīng)的數(shù)據(jù)量上,在形狀數(shù)量S和輪廓采樣點(diǎn)N一致的情況下,描述符的特征維度決定了算法的空間復(fù)雜度,根據(jù)本文實(shí)驗(yàn)對參數(shù)的最優(yōu)設(shè)定,采樣點(diǎn)數(shù)取N=100,平滑系數(shù)取k=5,本文描述符特征維度為M=[N/k]=20。表5給出了選取相同輪廓時,在輪廓采樣點(diǎn)數(shù)均為N=100的情況下不同描述符的特征維度:SC描述符[4]直方圖距離量化等級和角度量化等級分別為5和12,特征維度為60;IDSC描述符[6]中取直方圖距離量化等級和角度量化等級分別為8和12,其特征維度為96;TAR描述符[8]特征維度為M=[(N-1)/2]=44;CSOPT描述符[14]中平滑系數(shù)取k=3,特征維度為M=[(N-1)/k]=33。通過分析可以看出,本文描述符的特征維度(20)明顯低于上述經(jīng)典描述符,由此可以看出,本文算法相較于其它常見算法在空間復(fù)雜度上有著顯著的優(yōu)勢。

表5 不同描述符特征維度比較

5 結(jié)論

本文提出了基于質(zhì)心高度增量特征的目標(biāo)識別算法,在特征提取階段,構(gòu)造質(zhì)心高度增量形狀描述符,該描述符有效的描述了輪廓的全局以及局部信息,不僅計算簡單,具有旋轉(zhuǎn)、平移、縮放不變性,而且對于噪聲和輪廓局部形變具有良好的魯棒性。在目標(biāo)匹配階段選用動態(tài)規(guī)劃算法進(jìn)行形狀匹配,同時引入形狀復(fù)雜度分析提升了識別效果。通過對MPEG-7和Kimia99測試集進(jìn)行仿真,證明了本文算法能取得良好的識別效果,且在復(fù)雜度、抗噪聲干擾、識別準(zhǔn)確率等方面的性能優(yōu)于常見的目標(biāo)識別算法。