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

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

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

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

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

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

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

1.1 形狀描述

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

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

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

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

1.2 形狀匹配

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

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

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

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

1.3 時(shí)間復(fù)雜度分析

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

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

為了驗(yàn)證算法的有效性，本文在MPEG-7圖像庫中進(jìn)行了形狀的聚類實(shí)驗(yàn)。

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

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

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

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

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

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

[1]丁險(xiǎn)峰，吳洪，張洪江，等.形狀匹配綜述[J].自動(dòng)化學(xué)報(bào)，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.