一種基于順序形狀上下文的輪廓匹配方法

向 敏 王軍偉

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

1 引言

形狀上下文（shape contexts）是一種經典的輪廓描述子，許多研究工作是在它基礎之上的改進或推廣。然而，這些方法中的平面分割、區域點統計等處理去除了輪廓順序關系這一全局形狀特征，而且會造成量化誤差以及參數不易選取等問題。針對這些問題，本文提出一種新的上下文描述子，直接根據輪廓點的順序將上下文相對位置信息轉化為特征向量。這樣不僅避免了計算直方圖時額外的計算量、可能造成的量化誤差以及參數不易選取等問題，同時還通過輪廓的順序關系顯著增強了描述子中所含有的全局形狀信息。

2 研究現狀

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

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

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

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

3 改進的形狀上下文描述子

3.1 問題分析與改進思路

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

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

3.2 改進的上下文描述子及其性質

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

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

需要注意的是，式（2）所定義的特征序列的每一個分量fi，j都是一個二元坐標數據，并非標量。

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

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

圖1 保持輪廓順序關系的上下文描述子

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

則對矩陣E的每一行分別進行歸一化：

其中，‖‖fjt表示二元的上下文坐標數據的模，即。

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

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

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

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

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

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

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

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

4 形狀匹配與相似性度量

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

計算獲得任意一對輪廓點之間的匹配代價后，使用動態規劃算法（DP）來求解尋找輪廓點序列P、Q之間對應關系的優化問題。

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

其中，xˉt與 yˉt分別表示 N個二元坐標的 x坐 標 與 y坐 標 的 均 值 ，即，。

5 實驗結果與分析

為了驗證本文所提出的保持輪廓順序關系的上下文描述子的有效性，在兩個標準形狀測試集：MPEG-7［15］和 Kimia99［16］上進行了形狀檢索實驗。在相關實驗中，每個形狀輪廓采樣點數N的取值均為100。

5.1MPEG-7數據庫

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

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

5.2 Kimia99數據庫

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

5.3 噪聲環境下的形狀匹配與檢索

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

表2 不同方法在Kimia99數據集［16］上的檢索結果

表3 本文的方法在受到噪聲污染的Kimia99數據集上的檢索結果

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

6 結語

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