一种新的形状描述与识别方法

吴建立，刘宏申

(安徽工业大学 计算机科学与技术学院,安徽 马鞍山 243000)

一种新的形状描述与识别方法

吴建立，刘宏申

(安徽工业大学 计算机科学与技术学院,安徽 马鞍山 243000)

在形状上下文基础上，提出一种新的形状描述符。该形状描述符以形状质心为参考坐标原点建立对数极坐标，并由质心与边界样本点之间的距离及其内角两维构成，其中内角采用质心与边界点连线与轮廓切线之间的切角。这种新的形状描述子计算简单，能较好地区分不同的形状，且具有平移、缩放和旋转不变性，适合使用神经网络来作为识别分类器。最后以神经网络算法作为分类器，在MNIST手写数字数据库和Kimia图像数据库进行了实验验证。实验结果显示：该方法在单目标形状图像检索中取得了较好的检索效果，同时显著地减少了检索所需的时间，适用于较大型图像数据库的检索任务。

形状匹配；形状上下文；形状检索；神经网络；手写数字识别

随着科技的发展，形状相似性检索与图像识别成为图像处理领域中最为主要的研究问题。近些年来，形状检索与识别方法在图像处理领域有着较为广泛的应用。用于形状描述的方法有很多[1-2]。形状描述方法主要分为基于图像区域和基于图像轮廓的描述方法。基于图像区域的描述方法使用图像的全部信息来对图像进行描述，这类方法主要有几何不变矩法，由Hu在1962年提出[3]；基于图像轮廓的描述方法使用图像的外部边缘信息对图像进行描述，这类方法主要有小波轮廓描述符(wavelet descriptor)[4]、Freeman链码[5]、形状上下文描述子(shape contexts)[6-7]等。其中，形状上下文描述子是近年来提出的性能较为优秀的描述符，在形状相似性检索领域获得了较为广泛的应用，但其也存在着不足之处。

形状上下文描述符由Serge Belongie等在2000年提出[6-7]，主要利用对数极坐标来统计边界样本点相对于参考坐标原点的位置关系对图像进行描述，取得了相对较好的检索准确率，且在图像检索和匹配领域有着广泛地应用[8-10]。它属于基于形状轮廓的描述子，主要统计边界样本点相对于其他边界样本点的相对位置关系。其中，两个边界样本点之间的相似程度可以通过比较形状上下文距离来衡量。为了实现两个形状之间的相似性匹配，形状上下文算法使用薄板样条函数(TPS)[11-12]和匈牙利算法[10]来寻找两个形状之间样本点的最佳匹配，以此来最小化形状间的距离，从而达到匹配的目的。但是薄板样条函数的匹配属于强力匹配，在比较形状相似度的过程中需要寻找两个待匹配形状边界样本点之间的最佳对应关系，从而最小化形状上下文距离，故在匹配过程中耗时大，限制了形状上下文描述符在较大型图像数据库检索任务中的应用。

针对传统形状上下文描述符在形状匹配过程中的耗时等问题，Greg Mori等[13]提出了一种快速剪枝的方法。该算法先使用传统形状上下文对形状进行描述，之后对得到的形状上下文描述子进行聚类(一般使用K-means算法进行聚类)，并将聚类得到的类别作为新的形状描述子。这些改进虽然降低了检索过程中的时间消耗，但由于是对得到的形状上下文进行聚类，降低了匹配的精度。文献[16]将传统形状上下文描述符与神经网络相结合，提出了一种结合神经网络的形状上下文描述符，但该算法为了减少算法的复杂度，仅选取较少的边界样本点的形状上下文作为神经网络的输入，虽然降低了算法检索所需的时间，却牺牲了算法匹配的精度。针对现有描述方法在检索中比较耗时。而改进算法虽然提高了检索速度，但是损失了准确性的问题。本文提出了一种新的形状描述符，并将其作为神经网络分类器的输入特征，以此来进行形状相似性检索。使用MNIST手写数字数据库[14]和Kimia99图像数据库[15]来测试本文提出的方法，对比实验结果显示本文提出的方法较传统形状上下文算法的准确率虽有所降低，但检索所需时间远低于传统形状上下文。相较文献[16](记为SC+BP)中的方法，检索需要的时间基本相同，但是检索准确率有所提高。本文方法减少了相似性检索所需的时间，适用于较大型图像数据库的检索任务。

1 改进的形状描述符

1.1 形状及切角表示

对于给定的形状，边界样本点与其质心的空间位置关系反映了形状的某些特征，因此可以用边界样本点相对于形状质心的空间位置关系来对形状进行描述。对于一个给定的形状，用canny轮廓分割算法提取其边界轮廓，并采用均匀采样算法对获得的形状轮廓进行均匀采样，得到轮廓样本点集合P={p1,p2,…,pn}，其中n表示采样的样本点数目。这些边界样本点基本可以对形状轮廓进行描述(见图1，表示图像轮廓及样本点提取效果图)，并计算形状的质心坐标p0(x0,y0)。质心的计算方法如式(1)所示，其中S表示待计算目标；I(i,j)表示目标的灰度值。图1中(a)表示原始图像；(b)表示形状轮廓提取结果；(c)表示轮廓均匀采样结果，*表示形状质心。

(1)

图1 图像轮廓提取效果图

然而，图像的形状千变万化，并不是所有形状的轮廓都是连续的或者只有单个目标。对于图像中只有一个目标形状，但是轮廓不连续的情况(如图2(a)所示)，由于本文方法只是选取部分边界样本点来计算新的形状描述符，因此对于这种边界不连续的情况，按照上述方法进行边界样本点提取即可。对于一个图像中有多个目标的形状(如图2(b)所示)，若只计算整个图像的质心，则不会获得更好的效果。针对这种情况，分别获取每个子形状的轮廓及其对应的质心(如图2(c)和(d)所示)，对于多个目标的复杂形状，采用分割法将其分割成不同的子形状来进行考虑。假设Q表示多目标形状，则其对应的边界样本点及质心可以表示为：

Q={[α1,α2,…,αn],[β1,β2,…,βm],…}

P={p1,p2,…,pn}

其中：α和β分别表示子形状的边界样本点；P={p1,p2,…,pn}表示子形状的质心。

图2 多目标图像示例

传统形状上下文使用对数极坐标来统计边界样本点之间的相对位置关系，但是其不具备旋转不变性。文献[16]使用传统形状上下文作为神经网络的输入特征，使得其对形状之间的旋转缺少鲁棒性。分析边界样本点和形状质心之间的关系，发现边界样本点及其轮廓切线、形状质心之间的夹角具有旋转不变性。对于给定的形状边界样本点集合P={p1,p2,…,pn}和形状质心p0(x0,y0)，选取边界样本点ρ∈P，它与形状质心之间的欧式距离记为Γ(ρ,p0)，ρ点处的轮廓切线记为T，则T和Γ之间的夹角记为β，将该夹角称为切角(tangent-angle)，如图3所示。对同一形状进行相应的旋转并计算旋转之后的切角，发现其角度并没有发生变化，如图4所示。

图3 切角示意图

图4 旋转后的切角示意

1.2 构建描述符

hi(k)=#{q≠pi:(q-pi)∈bin(k)}

(2)

半径角度15°30°45°60°75°90°105°120°135°150°165°1800.1250000000000000.250000000000000.52200121200211177660370085209978098111078

图6 图1中人形图像对应的新描述符

Fig.6 New descriptor of human image in Figure 1

2 形状相似性匹配

形状之间的相似性度量直接影响识别和检索的有效性和准确性，同时匹配算法的选择也影响着匹配效率及所需时间。研究者一直致力于研究如何有效地表示形状在特征上的相似度。Serge Belongie等[6-7]提出的形状上下文算法在匹配过程中使用匈牙利算法[10]结合薄板样条函数(TPS)对形状进行迭代匹配。这种匹配方法虽然能够较好地进行形状间相似性的匹配，但是需要寻找形状样本点之间的最佳对应关系，以此来最小化匹配形状之间的形状距离，从而达到形状匹配的目的。虽然这种方法能匹配形状之间的相似程度，也具有较好的准确性和鲁棒性，但是属于强力匹配，且匹配的过程十分耗时，使得该方法只适于小型图像数据库的检索任务，很难应用于较大型图像数据库的检索任务。

对形状上下文相关算法的匹配过程进行深入的研究，发现它们都是先进行样本点与样本点之间的匹配，再计算形状之间的距离，这极大增加了相似性匹配的时间。为了减少形状匹配的时间消耗，本文采用被广泛使用的神经网络算法来度量形状之间的相似性。神经网络在处理分类相关问题时有着很好的分类效果，且所需要的时间性能较匈牙利等算法有着较大的提高。本文将新的形状特征描述符作为神经网络的输入特征来进行形状相似性检索，将神经网络的输出作为形状的类别。虽然使用神经网络失去了相似性度量的一些精度，但是却极大缩短了匹配过程中所消耗的时间。简单地说，新的形状描述符可以被看作统计样本点落入栅格中个数的直方图，可以将这些直方图作为神经网络的特征输入来进行形状相似度匹配。这种新的方法可用于较大型图像数据库的检索任务，极大提高了算法的实用性。

为了减少输入特征的数目，对每个形状提取100个样本点，在距离方向上进行5等分(分别为0.125,0.25，0.5，1，2)，角度方向进行12等分，这样每个形状可以得到60个特征(栅格)。过多的特征对形状匹配的精确度提升不大，也会增加神经网络的特征输入和匹配的时间，影响算法的效率。

3 仿真实验及结果分析

为了验证本文提出方法的鲁棒性和其在检索时间方面的提升效果，使用MNIST手写数字数据库[14]、Kimia99图像数据库[15]进行实验验证。实验中原始形状上下文算法记为SC+TPS。由于形状上下文算法中样本点数目过多，为了减少神经网络算法的复杂度，选取固定间隔的6个形状上下文(因为形状上下文对相近点比较敏感)，记为SC+BP。实验中使用到的神经网络为BP神经网络，具有1个隐藏节点，输出特征数为图像的类别数目。

3.1 MNIST手写数据库匹配

MNIST数据库[14](mixed national institute of standards and technology database)是一个大型的用于训练不同图像处理系统的手写数字数据库。MNIST数据库包含60 000个训练图像和10 000个测试图像。训练集和测试集的一半来自MNIST训练数据库，另一半来自MNIST测试数据库。为了减少实验的复杂度，从MNIST手写数字数据库中选取600幅手写数字图像作为测试数据集，其中共有10类手写数字图像，每类60幅图像，共计600幅图像。使用其中的300幅图像作为训练数据集，剩下的300幅作为测试数据集。神经网络算法使用反向神经网络(back propagation neural network)。对于BP神经网络的配置，输入层的大小由输入特征的数目决定，输出层的大小由字符类别的数目决定(此处为10)，隐藏层的大小由输入层和输出层的大小共同决定。使用1个隐藏层的BP神经网络，其隐藏层的节点数为100，这些配置信息一般由验证图像数据集来决定。图8展示了部分手写数字。

表1为SC+TPS(传统形状上下文算法)、SC+BP(文献[16]方法)和本文方法在MNIST手写数字数据集中检索的结果。可以看出：虽然本文所述方法识别的准确率略微低于SC+TPS算法，但在检索时间方面远低于SC+TPS算法。这是因为：SC采样的Hungarian+TPS方法属于强力匹配，匹配过程十分耗时，而使用BP神经网络的本文方法不需要寻找两个待匹配形状之间点的对应关系，这极大地缩短了匹配过程需要的时间。因此，本文方法适用于较大型图像数据库的检索任务。

表1 MNIST手写数字数据库检索示例Table 1 Retrieval example of MNIST handwritten number

图7 MNIST匹配速度对比

图8 部分MNIST手写数字

3.2 Kimia数据库匹配测试与分析

Kimia图像数据库[15]由Kimia25、Kimia99和Kimia216 等图像数据库组合而成。为了减少实验复杂度和所需时间，仅选取其中的Kimia99数据库来进行匹配准确性和匹配时间的相关测试。Kimia99 图像数据库中共有9种不同类别的图像，每种不同的类别主要有11个不同的图像，该图像数据库共有99个不同的形状图像，如图9所示。将图像数据库中的每种形状依次作为待匹配的图像，检索图像数据库中与它相似的图像，并对查询到的相似图像进行准确度统计。改进的方法与SC+TPS算法、文献[16]方法(记为SC+BP)对Kimia99数据库的形状检索结果及检索速度如表2、图10所示，其中横坐标对应图10中9个不同类别形状标号，纵坐标为检索每一类所需时间。从图10可以看出：本文算法的检索率与SC+TPS相当，但是检索速度有了较大的提升；SC+BP算法和本文算法在检索时间方面不相上下，但是检索准确率低于本文算法。

表2 Kimia99数据库检索结果

图9 Kimia99图像数据库

图10 匹配速度对比

4 结束语

为了减少大型图像数据库检索任务所需时间，提高匹配算法的运算速率，本文提出了一种新的结合神经网络的匹配算法。实验结果显示本文算法不仅具有一定的鲁棒性，且极大地缩短了检索时间，使得算法能应用于较大型图像数据库的检索任务，提高了算法的实用性。本次实验中使用的是BP神经网络，未来计划进行与其他神经网络算法的结合实验，进一步增加算法的鲁棒性和有效性。

[1] ZHANG D,LU G.Review of shape representation and description techniques[J].Pattern Recognition,2004,37(1):1-19.

[2] 丁险峰，吴洪，张宏江，等.形状匹配综述[J].自动化学报，2001,27(5):678-694.

DING Xianfeng,WU Hong,ZHANG Hongjiang,et al.Review on Shape Matching[J].Acta Automatica Sinica,2001,27(5):678-694.

[3] HU M K.Visual pattern recognition by moment invariants[J].IRE Transactions on Information Theory,1962(8):179-187.

[4] YADAV R B,NISHCHAL N K,GUPTA A K,et al.Retrieval and classification of shape-based objects using Fourier,generic Fourier,and wavelet-Fourier descriptors technique:A comparative study[J].Optics and Lasers in engineering,2007,45(6):695-708.

[5] FREEMAN H.Computer Processing of Line Drawing Images[J].ACM Computing Surveys,1974,6(1):57-97.

[6] BELONGIE S,MALIK J,PUZICHA J.Shape Matching and Object Recognition Using Shape Contexts[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2010,24(4):509-522.

[7] BELONGIE S,MALIK J,PUZICHA J.Shape Context:A New Descriptor for Shape Matching and Object Recognition[C]//Advances in Neural Information Processing Systems 13:Proc.2000 Conf.USA:[s.n.],2000:831-837.

[8] 吴晓雨,何彦,杨磊,等.基于改进形状上下文特征的二值图像检索[J].光学精密工程,2015,23(1):302-309.

WU Xiaoyu,HE Yan,YANG Lei,et al.Binary image retrieval based on improved shape context algorithm[J].Optics and Precision Engineering,2015,23(1):302-309.

[9] 郑丹晨,韩敏.基于改进典型形状上下文特征的形状识别方法[J].计算机辅助设计与图形学学报,2013,25(2):215-220.

ZHENG Danchen,HAN Min.Improved Shape Recognition Method Based on Representative Shape Context[J].Journal of Computer-Aided Design and Computer Graphics,2013,25(2):215-220.

[10]PAPADIMITRIOU C,STIEGLITZ K.Combinatorial Optimization:Algorithms and Complexity[M].[S.l.]:Prentice Hall,1982.

[11]DUCHON J.Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces[J].Lecture Notes in Mathematics,1977,571:85-100..

[12]MEINGUET J.Multivariate Interpolation at Arbitrary Points Made Simple[J].ZAMP,1979(5):439-468.[13]MORI G,BELONGIE S,MALIK J.Efficient shape matching using shape contexts[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005(11):1832-1837.[14]LECUN Y,BOTTOU L,BENGIO Y,et al.Gradient-based learning applied to document recognition[J].Proceedings of the IEEE,1998,86(11):2278-2324.

[15]XIANG B,YANG X,LATECKI L J,et al.Learning Context-Sensitive Shape Similarity by Graph Transduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(5):861-874.

[16]JULCA-AGUILAR F,VIARD-GAUDIN C,MOUCHèRE H,et al.Integration of Shape Context and Neural Networks for Symbol Recognition[C]//Colloque International Francophone sur l’écrit et le Document 2014(CIFED).France:[s.n.],2014.

(责任编辑 杨黎丽)

A New Method of Shape Description and Recognition

WU Jian-li, LIU Hong-shen

(School of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243000, China)

Based on the shape context, a new shape descriptor was proposed. The shape descriptor was based on the shape of the center of mass to establish the polar coordinates of the reference point, and was formed by the distance and inner-angle between the centroid and boundary samples, and the inner-angle used the tangent-angle between the centroid and the boundary line and contour tangent angle. This new shape descriptor is simple to calculate, and can be good to distinguish between different shapes, and are invariant to translations and scaling, and is very suitable for using neural networks as recognition classifier. At last, the neural network algorithm was used as the classifier, and experimental results in MNIST handwritten numerals database and Kimia databases were shown that the method has achieved good results in single object shape image retrieval, and significantly reduces the search time, and is suitable for large image databases retrieval tasks.

shape matching; shape context; shape retrieval; neural network; handwritten digit recognition

2016-10-28

吴建立(1991—)，男，安徽池州人，硕士研究生，主要从事数字图像处理与模式识别研究，E-mail:wujianli1991@163.com。

吴建立，刘宏申.一种新的形状描述与识别方法[J].重庆理工大学学报(自然科学)，2017(2):110-116.

format：WU Jian-li, LIU Hong-shen.A New Method of Shape Description and Recognition[J].Journal of Chongqing University of Technology(Natural Science)，2017(2):110-116.

10.3969/j.issn.1674-8425(z).2017.02.019

TP391.4

A

1674-8425(2017)02-0110-07