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

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

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

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

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

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

1.1 形狀描述

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

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

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

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

1.2 形狀匹配

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

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

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

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

1.3 時間復雜度分析

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

2 實驗結(jié)果與分析

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

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

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

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

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

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

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

[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.