基于輪廓分割的形狀匹配新方法

王愛平，余 江，江 麗，張芹芳

(安徽大學 計算機科學與技術學院，安徽 合肥230601)

最近幾年中，圖像在諸多領域的廣泛應用使得計算機視覺已成為一個主要的研究領域。計算機視覺圖像感性特征包括顏色、形狀、紋理和空間關系等。其中，形狀作為其最基本的特性之一，已成為人們的研究熱點。形狀匹配就是按照一定的準則來衡量形狀間的相似度，它一般由兩部分工作組成，首先是形狀描述和表示,其次是形狀匹配[1]。形狀描述是通過一些方法生成數值的描述子來表示形狀，這一表示要求在盡可能區別不同目標的基礎上對目標的平移、旋轉和縮小放大具有不變性。形狀匹配是在一定形狀描述方法基礎上計算兩目標相似性或相異性的算法。無論是傳統的屬性串匹配，還是傅里葉描述子以及小波描述子，都建立在形狀描述的基礎上，所以正確的形狀描述才能保證形狀匹配的正確性。

目前很多對于形狀描述的研究都指出，在彎曲很尖銳的地方對輪廓進行分割于形狀描述至關重要[2]。基于這種思想，本文基于輪廓離散曲線演化DCE(Discrete Curve Evolution)[3]提出了一種新的形狀描述子。

1 基于輪廓分割的形狀描述子

形狀的輪廓由若干連續的點構成，這些點通過DCE得到輪廓上的一些明顯的凸點后，選取每兩個凸點之間曲率最小值點或者是刪除的凹點進行輪廓分割，整個形狀被分成若干片段，這些片段被用來作為形狀輪廓的標識。

1.1 形狀描述

由于邊界上可能存在的小突起或者噪音，可能影響到凸點的選取。DCE是一個遞歸刪除對物體形狀信息貢獻最小的多邊形頂點(最有可能是物體邊界的噪聲點)的過程，因此，本文首先采取DCE的方法取得輪廓上的一些頂點。在這個由N個頂點形成的多邊形中存在著凸點和凹點，如果保留凹點，那么輪廓分段可能形成一些無效的片段，所以，最終通過去除凹點，得到形狀輪廓的凸點集合。如圖1所示，(a)中線段部分表示牛的形狀輪廓，(b)中線段表示通過DCE得到的具有10個頂點的多邊形，(c)中線段表示去除凹點之后得到的具有7個頂點的多邊形。

關于這些片段，除了用pk的曲率來表示其寬度外，還提取它們的空間取向特征。對于一個塊τk的取向θk通常表示為：在極坐標中，凸點pk相對于中間點mk、mk+1的連線計算出的矢量。

最終提取特征向量來表示一段輪廓片段的形狀特征，一個完整的形狀描述子由若干個輪廓片段的描述子組成，如式(1)所示：

圖2所示為一幅關于牛的形狀，通過DCE以及去除凹點后，分割成 7塊，其中(a)為原圖，(b)～(i)為分割后的 7個片段。

1.2 形狀匹配

利用上述方法得到形狀描述之后，接下來需要計算形狀描述子之間的相似度，相似度的計算方法如下：

(1)計算所有輪廓片段之間的距離矩陣 D={dij}，dij表示A中第i個塊與B中第j個塊的距離，其中，任意兩個片段 τi和 τj之間的距離公式為：

該公式采用曲率和方向的距離相結合的方法，參數α∈[0，1]在曲率和方向的距離的計算中起到權重作用。由于片段的距離滿足三角不等式，所以片段空間是一個度量空間。

(2)在得到的輪廓片段的距離矩陣的基礎上，可以進一步計算兩個形狀A和B的相似度。它們的距離矩陣D={dij}，需要找出輪廓片段的最優匹配關系，于是，形狀匹配問題轉化為典型的雙向圖的匹配問題。利用匈牙利算法[5]可以得到距離矩陣中的最小代價和，該代價和對應著形狀輪廓片段之間的最優匹配關系，計算出每對具有最優關系的片段之間的距離進而計算出兩個形狀之間的相似度。

1.3 時間復雜度分析

本文方法分為形狀描述和形狀匹配兩個階段，在形狀描述階段，基于DCE的輪廓分段的時間復雜度等價于DCE簡化一個頂點數為N的多邊形,其時間復雜度為O(NlgN)。計算出每個片段及其曲率和方向需要遍歷整個輪廓，該操作需要線性的時間O(N)，因此形狀描述階段時間復雜度為O(NlgN)。在形狀匹配階段，本文采取的是匈牙利算法，其時間復雜度最壞情況下為O(N3)。綜上所述，本文方法的總時間復雜度為O(N3)。

2 實驗結果與分析

為了驗證算法的有效性，本文在MPEG-7圖像庫中進行了形狀的聚類實驗。

在實驗中，選取兩類形狀，每類形狀選取10幅，共計20個形狀。采用本文方法計算這兩類形狀之間的距離矩陣,進而判斷形狀之間的相似性。其中，第一類形狀用數字 1～10標記，第二類形狀用數字 11～20標記。在實驗中，參數α在曲率和方向距離計算中設置為0.4，DCE簡化的多邊形頂點數為10。

多維尺度MDS(Multi-Dimensional Scaling)分析是一種有效的數據低維嵌入方法，該方法利用數據之間的距離矩陣關系進行低維嵌入。如圖3所示，利用MDS對實驗形狀距離矩陣進行低維嵌入。在對比圖中可以看到，傳統的輪廓分割方法可以將兩類形狀大致區分出來，但是分布比較分散。如圖，第1個形狀與第20個形狀距離就比較接近。本文的方法效果較好，不僅可以區分出兩類形狀，而且同類形狀分布比較緊湊，不同類形狀之間的距離較大。

用輪廓分割方法以及本文方法計算出形狀之間的距離矩陣，然后進行數據聚類實驗。

最小生成樹MST(Mininum Spanning Tree)聚類算法是一種穩定的聚類算法。表1是對兩類形狀的MST聚類結果。在該結果中可以看出傳統的輪廓分割方法形狀1被錯誤地聚類，而本文方法全部正確。這表明，本文的方法能更好地描述形狀的特征。

表1 不同方法下形狀MST聚類結果對比

本文提出了一種基于輪廓分割的形狀描述方法。與傳統的輪廓分割方法相比，本文方法采用了DCE對輪廓上的凸點進行選取，原理簡單，易于實現，具有平移、縮放等不變性。實驗證明文中的方法能很好地反映形狀之間的差別，具有較好的匹配效果。下一階段的工作主要是作進一步研究，使之具有仿射不變性。

[1]丁險峰，吳洪，張洪江，等.形狀匹配綜述[J].自動化學報，2001，27(5)：678-693.

[2]BERRETTI S，BIMBO A D，PALA P.Retrieval by shape similarity with perceptual distance and effective indexing[J].IEEE Transactions on Multimedia，2000，2(4)：225-239.

[3]Xiang Bai，LATECKI L J，Yu Liuwen.Skeleton pruning by contour partitioning with discrete curve evolution[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(3)：449-462.

[4]MOKHTARIAN F，ABBASI S，KITTLER J.Efficient and robust retrieval by shape content through curvature scale space[C].Amalfi：Workshop on Image Databases and Multi-Media Search，1996.

[5]PAPADIMITRIOU C，STIEGLITZ K.Combinational optimization：algorithm and complexity[M].New Jersey：Prentice Hall Inc.，1982.