向 敏 王軍偉

（1.海軍裝備部信息系統(tǒng)局 北京 100071）（2.武漢數(shù)字工程研究所 武漢 430205）

1 引言

形狀上下文（shape contexts）是一種經(jīng)典的輪廓描述子，許多研究工作是在它基礎(chǔ)之上的改進(jìn)或推廣。然而，這些方法中的平面分割、區(qū)域點(diǎn)統(tǒng)計(jì)等處理去除了輪廓順序關(guān)系這一全局形狀特征，而且會造成量化誤差以及參數(shù)不易選取等問題。針對這些問題，本文提出一種新的上下文描述子，直接根據(jù)輪廓點(diǎn)的順序?qū)⑸舷挛南鄬ξ恢眯畔⑥D(zhuǎn)化為特征向量。這樣不僅避免了計(jì)算直方圖時(shí)額外的計(jì)算量、可能造成的量化誤差以及參數(shù)不易選取等問題，同時(shí)還通過輪廓的順序關(guān)系顯著增強(qiáng)了描述子中所含有的全局形狀信息。

2 研究現(xiàn)狀

形狀上下文（shape contexts，SC）［1］是一種經(jīng)典的輪廓描述子。它從輪廓點(diǎn)之間的空間位置關(guān)系出發(fā)，幾何意義明確，直觀、簡單、易于計(jì)算、描述性強(qiáng)，能夠取得較好的形狀匹配效果。由于其優(yōu)異的性能，它已經(jīng)成為形狀描述子研究工作的一個(gè)里程碑，是近二十年來該領(lǐng)域所取得的最重要和最具影響力的研究成果之一。

不少研究工作試圖在原始的形狀上下文描述子的基礎(chǔ)之上做出優(yōu)化、改進(jìn)或推廣，進(jìn)一步挖掘這種形狀特征在性能上的潛力。內(nèi)距離形狀上下文描述子（IDSC）［3］就是在SC基礎(chǔ)上做出的經(jīng)典推廣性工作。文獻(xiàn)［3］認(rèn)為，對于非剛性物體（如人或其他動(dòng)物）來說，在肢體變化（articulation）下，輪廓點(diǎn)之間的歐氏距離會發(fā)生顯著變化，不是一種穩(wěn)定的形狀特征。為此，文獻(xiàn)［3］提出一種新的輪廓點(diǎn)距離計(jì)算方式：內(nèi)部距離（inner-distance），其定義為從物體的內(nèi)部連接輪廓上兩個(gè)點(diǎn)之間最短路徑的長度。用內(nèi)部距離代替歐氏距離，發(fā)明了一種新的描述子：內(nèi)部距離形狀上下文（inner-distance shape contexts，IDSC），該描述子最突出的性能優(yōu)勢是能夠取得肢體不變性（articulat ioninvariance）。此外，IDSC在復(fù)雜形變下的區(qū)分能力也比較突出。

還有人注意到SC在統(tǒng)計(jì)各個(gè)區(qū)域所包含的輪廓點(diǎn)數(shù)時(shí)，將某個(gè)輪廓點(diǎn)賦予某個(gè)區(qū)域，這個(gè)過程本質(zhì)上是對輪廓點(diǎn)在平面上的位置信息進(jìn)行量化，即位置不同但都被某個(gè)區(qū)域所包含的點(diǎn)，它們的處理結(jié)果是完全相同的。假如某個(gè)輪廓點(diǎn)位于兩個(gè)相鄰區(qū)域的分界線附近，則輪廓點(diǎn)位置微小的擾動(dòng)或誤差就會得到完全不同的量化結(jié)果，這顯然是不合理的。為此，Liu和Chen對SC進(jìn)行軟化改造，提出了軟形狀上下文描述子（soft shape contexts，SSC）［4］，其基本思路是利用概率式的軟判決思想來計(jì)算兩個(gè)SC描述子之間的相似度，相當(dāng)于對原始的SC特征進(jìn)行低通平滑濾波，可從一定程度上克服直方圖相鄰區(qū)域的量化誤差。韓敏和鄭丹晨提出模糊形狀上下文特征（fuzzy shape context）［5］，該方法利用軟判決思想，定義直方圖每個(gè)柵格的中心，并根據(jù)一個(gè)隸屬度函數(shù)計(jì)算每個(gè)輪廓點(diǎn)位于不同區(qū)域的概率，在此基礎(chǔ)上獲得一個(gè)模糊的直方圖特征，相對于SC二值的量化方法能夠更加精確地描述采樣點(diǎn)的空間分布情況。Ling和Okada基于填土距離（earth mover's distance，EMD）提出了一種直方圖距離度量的新方法［6］，可有效改善特征距離計(jì)算和形狀匹配的效果。

另外，還有不少研究是在上下文思想基礎(chǔ)之上的推廣。Mori等［7］提出了一種廣義的形狀上下文特征（generalized shape context），用輪廓點(diǎn)的切向量代替采樣點(diǎn)，進(jìn)而用每個(gè)區(qū)域內(nèi)切向量的主方向而不是輪廓點(diǎn)的數(shù)量來表示輪廓的空間分布。Roman-Rangel等［8］提出方向直方圖形狀上下文特征（histogram of orientation shape context），借鑒自然圖像中經(jīng)典的SIFT算法［9］的思想改進(jìn)SC描述子，通過一個(gè)高維度的直方圖來準(zhǔn)確地表示目標(biāo)形狀的特征。Daliri和Torre［10］提出了一種將形狀上下文描述子與符號串表示（string of symbols）相結(jié)合的方法，使用Procrustes分析方法來校準(zhǔn)兩個(gè)形狀的對應(yīng)關(guān)系，提高了形狀匹配的效果。Kirkegaard和Moeslund［11］利用形狀上下文的思想來表示三維物體的表面特性，提出了一種稱為調(diào)和形狀上下文（harmonic shape contexts）的描述子。Huang和Trivedi［12］將SC描述子推廣到三維情況下對人體進(jìn)行表示，提出了一套人體姿勢分析和跟蹤方法。Grundmann等［13］結(jié)合二維空間和時(shí)間信息，提出了一種三維形狀上下文描述子，并結(jié)合距離變換技術(shù)（distance transform）進(jìn)行行為識別。Kholgade和Savakis［14］針對視頻中的人體行為識別問題，提出了一種四維的時(shí)空形狀上下文描述子（spatiotemporal shape context）。

3 改進(jìn)的形狀上下文描述子

3.1 問題分析與改進(jìn)思路

SC將輪廓點(diǎn)分配到各個(gè)區(qū)域中去，這種處理方式造成形狀信息分散，破壞了輪廓原本具有的全局形狀特征。針對SC的大部分改進(jìn)方法或者是將二維直方圖推廣至更高維，或者是在原有直方圖的基礎(chǔ)之上進(jìn)行一些后處理操作。這些改進(jìn)方法不能從根本上解決問題，描述子性能的提升有限，而且還使得上下文描述子的計(jì)算變得更加復(fù)雜。

本文方法的基本思想是：在獲取了所有輪廓點(diǎn)的相對空間位置信息（即上下文）后，直接通過輪廓的順序關(guān)系，將這些上下文信息組合起來，轉(zhuǎn)化為一個(gè)特征序列。這樣做的優(yōu)勢在于：1）對于輪廓采樣點(diǎn)來說，輪廓的順序關(guān)系是原本就存在的信息，容易加以使用，而且可以與輪廓點(diǎn)之間的上下文特征有機(jī)相融合。2）上下文信息組合在一起的思想與SC描述子中區(qū)域分割的思想正好相反，組合的思想可以有效地保留輪廓的全局特征，體現(xiàn)形狀整體上的信息。3）組合比分割簡單，將局部組合成整體基本上不需要參數(shù)控制，將整體分割為局部卻需要確定分割的粗細(xì)粒度，也就是確定形狀上下文控制分割的那些參數(shù)。

3.2 改進(jìn)的上下文描述子及其性質(zhì)

設(shè)輪廓采樣點(diǎn)序列為P=｛pi｝（i=1，2，…，N），其中N為采樣點(diǎn)序列的長度（即輪廓采樣點(diǎn)的數(shù)量）。假設(shè)pi為目前的參考點(diǎn)（referencepoint）。與SC描述子一致，以參考點(diǎn)pi為坐標(biāo)原點(diǎn)，以形狀輪廓P在參考點(diǎn)pi位置處的切線li為x軸，建立一個(gè)相對的坐標(biāo)系，并計(jì)算除參考點(diǎn)pi以外的其他N-1個(gè)輪廓點(diǎn)在該坐標(biāo)系中的相對坐標(biāo)：

這樣，就得到了其他N-1個(gè)輪廓點(diǎn)相對于參考點(diǎn)pi的相對坐標(biāo)數(shù)據(jù)。與SC不同，本文使用一種全新的策略對這些相對坐標(biāo)數(shù)據(jù)進(jìn)行處理。由于除參考點(diǎn)pi以外的其他N-1個(gè)輪廓點(diǎn)在形狀輪廓P上存在自然的先后順序關(guān)系，我們直接根據(jù)它們在輪廓上的順序關(guān)系，將式（1）所示的相對坐標(biāo)數(shù)據(jù)fi，j排列成一個(gè)序列的形式，如以下式（2）所示：

需要注意的是，式（2）所定義的特征序列的每一個(gè)分量fi，j都是一個(gè)二元坐標(biāo)數(shù)據(jù)，并非標(biāo)量。

定義1 式（2）所定義的相對坐標(biāo)序列Fi是在形狀輪廓P上的、針對參考點(diǎn)pi所定義的保持輪廓順序關(guān)系的形狀上下文描述子（contoursequential order-preservedshapecontexts，CSOSC）。

圖1給出了本文所定義的上下文描述子的示意圖。

圖1 保持輪廓順序關(guān)系的上下文描述子

本文提出的描述子仍然建立在上下文信息基礎(chǔ)之上，這使得它繼承了SC描述子的線性變換不變性。為了使得所定義的上下文描述子滿足尺度不變性，采用局部歸一化（localnormalization）操作。將形狀輪廓P上每一個(gè)輪廓點(diǎn)對應(yīng)的上下文描述子Fi按照順序排列，組成一個(gè)尺寸為（N-1）×N的矩陣：

則對矩陣E的每一行分別進(jìn)行歸一化：

其中，‖‖fjt表示二元的上下文坐標(biāo)數(shù)據(jù)的模，即。

式（2）所定義的上下文相對坐標(biāo)序列Fi中包含了除參考點(diǎn)pi以外的所有其他N-1個(gè)輪廓點(diǎn)的相對坐標(biāo)數(shù)據(jù)。如果采納所有輪廓點(diǎn)的數(shù)據(jù)，會導(dǎo)致序列Fi對形狀輪廓P的描述過于精確和細(xì)致，從而對形狀的局部變形過于敏感。為了在描述的準(zhǔn)確性和對局部形變的不敏感性之間取得一個(gè)很好的折中，有效提高描述子對于噪聲和局部形變的魯棒性，對式（2）所定義的描述子的精確性上進(jìn)行一定程度的弱化。

具體的，采用平滑化（smoothing）處理技術(shù)。具體過程如下。

根據(jù)式（2），原始的輪廓描述子可表示為

它是一個(gè)包含N-1個(gè)元素的序列，其中的任意一個(gè)分量 fij（j=1，2，…，N-1）是特征向量Fi中的第j個(gè)分量。將從1到N-1的正整數(shù)序列1，2，…，N-1均勻的劃分為若干個(gè)互不相交的子序列［1，k］、［k+1，2*k］、［2*k+1，3*k］、…，其中k為一個(gè)預(yù)設(shè)的正整數(shù)。對于每一個(gè)子序列，分別計(jì)算特征向量中相應(yīng)的一段分量的均值：

其中j=1，2，…，M，j表示所劃分出來的M個(gè)子序列的標(biāo)號，M的值由N和k的值確定，。這M個(gè)均值按順序構(gòu)成一個(gè)新的序列：

特征向量Gi就是對原始的描述子Fi經(jīng)過平滑化技術(shù)處理以后的結(jié)果。經(jīng)過平滑化處理，不僅使得原始描述子的特征維度得以降低，而且還有效提高了描述子對于輪廓噪聲和局部形變的魯棒性。

對于形狀輪廓P上的每一個(gè)采樣點(diǎn)pi（i=1，2，…，N），我們都可以將其作為參考點(diǎn)，基于相同的定義方式計(jì)算出一個(gè)由式（7）所表示的輪廓描述子Gi（i=1，2，…，N）。將這N個(gè)描述子對應(yīng)的特征向量按照輪廓點(diǎn)的順序排列起來，可以得到一個(gè)M×N尺寸的矩陣：

該矩陣是針對形狀P定義的總的特征，矩陣Γ的第i列對應(yīng)著輪廓P上某一點(diǎn)pi的形狀描述子。

4 形狀匹配與相似性度量

設(shè)兩個(gè)形狀P、Q對應(yīng)的輪廓采樣點(diǎn)序列為P=｛pi｝（i=1，2，…，N）和Q=｛qj｝（j=1，2，…，N）。在匹配這兩個(gè)序列之前，首先計(jì)算任意一對分別來自不同形狀P、Q上的采樣點(diǎn)之間的不相似度或匹配代價(jià)c（pi，qj）（i=1，2，…，N；j=1，2，…，N）。該匹配代價(jià)定義為兩個(gè)點(diǎn)pi、qj對應(yīng)的描述子特征Gi與Gj之間的距離。由于式（7）定義的特征向量中的每一個(gè)分量不是標(biāo)量值，而是二元的上下文坐標(biāo)數(shù)據(jù)，這里采取一種直觀的方式來比較兩個(gè)坐標(biāo)序列之間的差異：

計(jì)算獲得任意一對輪廓點(diǎn)之間的匹配代價(jià)后，使用動(dòng)態(tài)規(guī)劃算法（DP）來求解尋找輪廓點(diǎn)序列P、Q之間對應(yīng)關(guān)系的優(yōu)化問題。

在基于動(dòng)態(tài)規(guī)劃算法所求得的成對形狀相似性度量值基礎(chǔ)上，進(jìn)一步使用形狀復(fù)雜性（shape complexity）因子進(jìn)行調(diào)整。對于形狀輪廓P=｛pi｝（i=1，2，…，N），假設(shè)已經(jīng)獲得了如式（8）所示的尺寸為M×N的特征矩陣Γ（且已經(jīng)經(jīng)過了式（4）的尺度歸一化處理），則形狀P的形狀復(fù)雜性C（P）可由如下公式定義：

其中，xˉt與 yˉt分別表示 N個(gè)二元坐標(biāo)的 x坐 標(biāo) 與 y坐 標(biāo) 的 均 值 ，即，。

5 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文所提出的保持輪廓順序關(guān)系的上下文描述子的有效性，在兩個(gè)標(biāo)準(zhǔn)形狀測試集：MPEG-7［15］和 Kimia99［16］上進(jìn)行了形狀檢索實(shí)驗(yàn)。在相關(guān)實(shí)驗(yàn)中，每個(gè)形狀輪廓采樣點(diǎn)數(shù)N的取值均為100。

5.1MPEG-7數(shù)據(jù)庫

表1給出了CSOSC描述子和其他描述子在MPEG-7數(shù)據(jù)庫上的檢索精度。從結(jié)果來看，同樣是基于上下文信息，本文描述子的檢索性能明顯超過了已有基于上下文信息的描述子。即使不使用形狀復(fù)雜性因子改善形狀相似性度量結(jié)果，CSOSC也能夠取得最高的檢索準(zhǔn)確率，檢索精度（88.75%）遙遙領(lǐng)先。準(zhǔn)確率排在第二的方法是方面形狀上下文描述子［17］，該方法相當(dāng)于把SC和IDSC兩種經(jīng)典而有效的形狀特征進(jìn)行了信息融合，但即使如此，其結(jié)果也與本文的方法存在一定差距。

表1 不同的上下文方法在MPEG-7數(shù)據(jù)庫［15］上的檢索精度（bull'seye）

5.2 Kimia99數(shù)據(jù)庫

表2列出了CSOSC描述子與一些典型的形狀描述子在Kimia99數(shù)據(jù)庫上的檢索結(jié)果。從表中可以看出，本文的方法能夠取得極其優(yōu)異的檢索精度，與最近的一些方法相當(dāng)，與目前最好的方法——符號化表示［10］相比，僅僅在最后兩位數(shù)字上存在一定差距。

5.3 噪聲環(huán)境下的形狀匹配與檢索

為了驗(yàn)證本文的方法在噪聲環(huán)境下的性能，本節(jié)開展帶有噪聲的形狀輪廓檢索實(shí)驗(yàn)。在Kimia99數(shù)據(jù)庫的基礎(chǔ)上，人為地對該數(shù)據(jù)庫中的形狀輪廓添加一些高斯噪聲，然后對這些帶有噪聲的形狀進(jìn)行匹配與檢索。檢索精度的計(jì)算方式與在原始的Kimia99數(shù)據(jù)庫上的評價(jià)方式一致。檢索結(jié)果如表3所示。從表中可以看出，隨著噪聲變得越來越嚴(yán)重，檢索準(zhǔn)確率有一定下降，但仍可以接受，表明本文的方法對于輪廓噪聲具有較高的魯棒性。

表2 不同方法在Kimia99數(shù)據(jù)集［16］上的檢索結(jié)果

表3 本文的方法在受到噪聲污染的Kimia99數(shù)據(jù)集上的檢索結(jié)果

本文的方法對輪廓噪聲具有較高的魯棒性。造成這一性能優(yōu)勢的原因有兩個(gè)：1）本文的方法有效融合了輪廓順序關(guān)系，而輪廓順序信息是一種全局性的形狀特征，對噪聲和局部輪廓形變具有魯棒性；2）本文的方法采用了平滑化處理技術(shù)，在降低特征向量維度的同時(shí)，也有效提高了本文的描述子對于輪廓噪聲和局部形變的魯棒性。

6 結(jié)語

針對經(jīng)典的形狀上下文描述子在特征定義與計(jì)算過程中存在的缺陷，本文抓住問題的本質(zhì)——平面分割與區(qū)域點(diǎn)數(shù)統(tǒng)計(jì)，通過一種全新的方式組織上下文信息，不僅簡化了描述子的定義和計(jì)算過程，而且將輪廓的順序關(guān)系自然的添加進(jìn)描述子中，增強(qiáng)了描述子的全局形狀信息，有效提高了上下文描述子的表達(dá)和描述能力。實(shí)驗(yàn)表明，本文提出的輪廓描述子在各大、小型標(biāo)準(zhǔn)形狀測試集上均能夠取得優(yōu)異的形狀檢索效果，檢索精度不僅顯著高于已有的上下文式的描述符，而且與目前效果最好的形狀描述子接近。