基于轮廓分割的形状匹配新方法

王爱平，余 江，江 丽，张芹芳

(安徽大学 计算机科学与技术学院，安徽 合肥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.