第41 卷第8 期自动化学报Vol. 41, No. 82015 年8 月ACTA AUTOMATICA SINICA August, 2015一种基于多尺度轮廓点空间关系特征的形状匹配方法杨亚飞1 郑丹晨1 韩敏1摘要针对使用三角形区域表示描述子对相似形状进行匹配时, 对微小形变比较敏感以及区分剧烈变化的不相似形状时判别能力较弱的问题, 提出一种结合轮廓点空间关系特征的多尺度形状特征描述子. 通过分析不同尺度下参考点与其他采样点之间的位置关系, 利用对应角度信息来对形状进行表示, 并在此基础上构造出一种新的形状特征描述子. 本文所提特征提取方法能对形状的局部及全局信息更准确地描述, 具有较好的鲁棒性和判别能力. 在形状特征匹配阶段, 利用轮廓点集顺序关系已知这一优势, 引入动态规划及形状复杂度分析的方法, 分析形状间的匹配结果, 能够得到较好的形状匹配精度. 通过对不同形状数据集行仿真实验, 证明本文方法能够有效地实现形状识别和检索.关键词多尺度, 三角形区域表示, 轮廓点空间关系特征, 形状特征匹配引用格式杨亚飞, 郑丹晨, 韩敏. 一种基于多尺度轮廓点空间关系特征的形状匹配方法. 自动化学报, 2015, 41(8):1405¡1411DOI 10.16383/j.aas.2015.c140896A Shape Matching Method Using Spatial Features of Multi-scaled ContoursYANG Ya-Fei1 ZHENG Dan-Chen1 HAN Min1Abstract In order to improve the sensibility and discrimination power of triangle-area representation, a shape matchingmethod using multi-scaled contour space relationship is proposed. The angle information in multi-scales, which is usedto represent shape contours, can be obtained by analyzing the spatial relationship of di®erent points, and a new shapedescriptor is further constructed. With the proposed descriptor, the multi-scaled information of contours can be expressedaccurately, and the cost for descriptors of the corresponding points from similar shapes can be e®ectively decreased. Asthe orders of all the contour points are already known, a dynamic programming method and shape complexity can beused to guarantee the matching accuracy during the feature matching step. The proposed algorithm has been tested ondi®erent shape databases, and the performances are superior to many other methods.Key words Multi-scale, triangle-area representation, spatial features of multi-scaled contours, shape feature matchingCitation Yang Ya-Fei, Zheng Dan-Chen, Han Min. A shape matching method using spatial features of multi-scaledcontours. Acta Automatica Sinica, 2015, 41(8): 1405¡1411形状是人类辨别物体的重要参考依据, 在计算机视觉中常使用形状对物体进行描述, 对形状的表示和匹配是计算机视觉中的关键问题[1¡2]. 形状匹配方法按照一定的衡量标准判别形状间的相似程度,已成功应用于图像检索、人脸识别、医学影像分析等领域[3].形状匹配主要包含两个步骤: 形状特征提取和形状特征匹配[4]. 形状特征提取是形状匹配的关键步骤, 对形状的描述愈准确详尽, 形状的匹配结果也收稿日期2014-12-29 录用日期2015-04-08Manuscript received December 29, 2014; accepted April 8, 2015国家重点基础研究发展计划(973 计划) (2013CB430403), 国家自然科学基金(61374154), 中央高校基本科研业务费专项资金(DUT14RC(3)128) 资助Supported by National Basic Research Program of China (973Program) (2013CB430403), National Natural Science Founda-tion of China (61374154) and Fundamental Research Funds forthe Central Universities (DUT14RC(3)128)本文责任编委刘跃虎Recommended by Associate Editor LIU Yue-Hu1. 大连理工大学电子信息与电气工程学部大连1160231. Faculty of Electronic Information and Electrical Engineer-ing, Dalian University of Technology, Dalian 116023会愈加准确, 因此众多学者的研究集中于形状特征的提取. 形状表示方法可以分为基于轮廓的表示方法和基于区域的表示方法[5]. 其中, 基于轮廓的形状表示方法计算复杂度较低、识别效果良好而得到更多学者的青睐. 结合多尺度理论构造形状特征是一种较为常见的基于轮廓的形状表示方法[6], 该类方法在描述形状时引入一个连续变化的尺度参数, 由此获得多个尺度下的形状信息, 以期能够充分挖掘形状从局部细节到全局概貌的信息.在构造多尺度形状特征描述子的过程中,Mokhtarian 等[7] 使用曲率尺度空间(Curvaturescale space, CSS) 图作为形状描述子, Adamek 等[8]提出一种多尺度凹凸(Multi-scale convexity con-cavity, MCC) 描述子, Latecki 等[9] 提出基于视觉部分(Vision part) 的描述子. 上述几种方法都需要对轮廓进行演化才能进一步描述形状特征, 增加特征提取的工作量. 为简化特征提取步骤, Donoser等[10] 提出一种基于多尺度弦长的形状匹配方法, 在形状轮廓上任取两点, 通过分析它们与轮廓上其他1406 自动化学报41 卷点的关系来构造形状描述子, 通过调整两点间的弦长来控制特征尺度值的大小. 以上方法在形状进行检索和识别过程中均取得了较好的效果.Alajlan 等[11¡12] 提出一种三角形区域表示(Triangle-area representation, TAR) 的形状描述方法. 以轮廓上一点为参考, 分别在其两侧依次选取采样点, 利用这三个点构成的有向三角形的面积作为形状描述子, 并通过改变三个点之间距离的大小控制三角形区域的尺度, 实现对轮廓局部及全局信息的描述. Alajlan 等[13] 在之后的研究中又提出动态空间规整(Dynamic space warping, DSW) 的方法对提取的特征进行匹配.使用三角形区域表示方法对一些相似形状进行识别时, 鲁棒性较弱, 导致相似形状对应位置处采样点匹配不准确; 区分形状上一些不相似点时, 判别能力较弱, 导致形状上的不相似点发生误匹配. 为解决上述问题, 本文提出了一种基于多尺度轮廓点空间关系特征(Spatial features of multi-scaled con-tours, SFMC) 的形状匹配方法, 提取的轮廓特征具有更好的鲁棒性及更强的判别能力. 此外, 考虑到本文所使用形状的轮廓点集顺序关系均已知, 在特征提取之后使用动态规划(Dynamic programming,DP) 的匹配方法进行特征匹配, 进一步保证了形状识别和检索的精度.1 三角形区域表示法形状匹配三角形区域表示(TAR) 假设轮廓由N 个采样点表示, 由采样点(xn; yn)、(xn¡t; yn¡t) 和(xn+t; yn+t) 所构成的有向三角形面积可表示为TAR(n; t) =12¯¯¯¯¯¯¯xn¡t yn¡t 1xn yn 1xn+t yn+t 1¯¯¯¯¯¯¯(1)其中, 1 · n · N, 1 · t · T, T = N=2 ¡ 1. 进一步对TAR(n; t) 进行归一化:TAR(n; t) =1max TARtTAR(n; t) (2)max TARt = max1·n·NTAR(n; t) (3)式中, TAR(n; t) 为三角形区域特征. 假设A, B 分别表示两个形状, A 中第n 个点和B 中第m 个点间的匹配损失函数为D(m; n) =1TXTt=1¯¯TARA(n; t) ¡ TARB(m; t)¯¯(4)其中, 1 · n · N, 1 · m · N.图1 对三种类型的三角形区域特征进行了说明,形状上采样点个数为N, 其中点n1、n2、n3 分别代表凸区域、凹区域与直线.图1 三角形区域表示方法示意图Fig. 1 The sketch of triangle-area representation图2 给出了图1 形状对应的三角形区域特征的示例, 其中, 图2 (a) 为全部采样点各尺度下的特征示意图. 图2 (b) 给出了各采样点在t = 1 下对应的(a) 多尺度轮廓特征示意图(a) The values of features in multi-scales(b) t = 1 时, 轮廓特征示意图(b) The values of features when t = 1图2 图1 中形状对应的三角形区域特征Fig. 2 Triangle-area features of the shape in Fig. 18 期杨亚飞等: 一种基于多尺度轮廓点空间关系特征的形状匹配方法1407形状特征, 横坐标为采样点的索引值, 纵坐标为TAR(n; t).2 多尺度轮廓点空间关系特征使用三角形区域表示方法可以在多个尺度下对形状特征进行较好的描述, 但是, 其对细微形变比较敏感, 可能导致相似形状对应采样点不匹配的问题;另外, 一些情形下其区别能力较弱, 也可能致使产生错误的匹配结果.图3 中给出了一组利用三角形区域表示可能造成形状匹配错误的示例. 图3 (a) 给出了一对相似形状, 当尺度值t 较小时, p 和q 分别被判定为凸点和凹点, 即TAR(p; t) 和TAR(q; t) 分别为较大正值和绝对值较大的负值, 两点间匹配损失函数值较大, 影响匹配结果. 图3 (b) 给出了包含剧烈凸起部分和剧烈凹陷部分的一对不相似形状, TAR(u; t)和TAR(v; t) 分别为较小的正值和绝对值较小的负值, 对应匹配损失函数值较小, 可能将这两点判定为相似点, 造成错误的匹配结果.(a) 相似形状对应采样点处特征比较(a) Comparison of corresponding points on similar shapes(b) 不相似形状采样点处特征比较(b) Comparison of points on dissimilar shapes图3 三角形区域表示及多尺度轮廓点空间关系的示例Fig. 3 An example of triangle-area representation andspatial features of multi-scaled contours为解决上述问题, 考虑以不同尺度下的角度对形状进行描述, 图3 中给出了以角度作为形状描述子分析形状匹配的示例. 在图3 (a) 中相似形状对应采样点处, 角度值µp 和µq 的差值较小, 更有利于将左右两图判定为相似形状; 而在图3 (b) 中, µu 和µv差值较大, 可以更好地区分不相似的形状. 鉴于此,本文利用不同尺度下的角度构造形状特征, 其能够更好地分析形状采样点间的关系.同样假设轮廓由N 个采样点表示, 以第n 个采样点(xn; yn) 为参考点, 其与两侧点(xn¡t; yn¡t) 和(xn+t; yn+t) 所构成的角度定义为µ(n; t).µ(n; t) =(arccos z (n; t); Abs(n; t) ¸ 02¼¡arccos z (n; t); Abs(n; t) < 0(5)z(n; t) =(xn¡t¡xn; yn¡t¡yn)(xn+t¡xn; yn+t¡yn)k(xn¡t¡xn; yn¡t¡yn)k2k(xn+t¡xn; yn+t¡yn)k2(6)Abs(n; t)=¯¯¯¯¯¯¯xn¡t yn¡t 1xn yn 1xn+t yn+t 1¯¯¯¯¯¯¯(7)利用采样点表示形状信息过程中, 需要更精确地描述局部信息, 而对全局信息仅需要粗略描述. 例如形状上下文方法建立对数极坐标直方图就是这种思路. 基于此, 考虑增加较小尺度下角度对应权重来突出局部信息的作用. 因此, 引入e 的负指数函数从多个尺度下对特征值进行加权. 又由于µ(n; t) 在0、¼ 和2¼ 附近时, 不同形状匹配损失函数值差别较小, 为了构造判别能力较强的形状描述子, 将多尺度轮廓点空间关系特征定义为SFMC(n; t) = e¡®t ¢ sin(µ(n; t)) (8)对于形状A 中的第n 个点和形状B 中的第m个点, 两点间的匹配损失函数表示为D(m; n) =1TXTt=1jSFMCA(n; t) ¡ SFMCB(m; t)j (9)其中, SFMCA(n; t) 和SFMCB(m; t) 分别为形状A 和B 对应的形状特征1 · n · N, 1 · m · N,1 · t · T, ® 为权重系数. 当尺度值t 较大时,SFMC(n; t) 趋于零, 易造成误匹配, 故对尺度值的上界T 进行限定, 不仅能消除较大尺度特征的不利影响, 且在一定程度上降低计算复杂度. 本文通过交叉检验后设置T =25, ® = 0:25.图4 对本文所提特征进行了说明, 其中点n1、n2、n3 分别代表形状上的三个采样点.图5 为使用本文方法对图4 中形状进行特征提取后得到的结果. 图5 (a) 为全部采样点各尺度下的形状特征. 图5 (b) 为尺度值t = 1 时, 所有采样点对应的特征, 横坐标为采样点的索引值, 纵坐标为特征值.1408 自动化学报41 卷图4 本文所提特征提取方法示意图Fig. 4 The sketch of the proposed feature extractionmethod(a) 多尺度轮廓特征示意图(a) The values of features in multi-scales(b) t = 1 时, 轮廓特征示意图(b) The values of features when t = 1图5 图4 中形状对应的多尺度轮廓点空间关系特征Fig. 5 Spatial features of multi-scaled contours of theshape in Fig. 43 形状特征匹配在得到形状特征之后, 需要对其进行进一步匹配. 由于形状轮廓上点集序列的顺序关系已知, 本文结合动态规划算法对得到的形状特征进行匹配.3.1 基于动态规划的形状特征匹配给定一对形状A 和B, 通过式(9) 可以得到一个N £ N 的距离矩阵D. 使用动态规划算法分析形状A 和B 上对应点间的最佳匹配关系, 初始化一个N £ N 的矩阵DT.DTinitial(m; n) =(D(m; n); m = 1; n = 11; 其他(10)并利用下式更新:DT(m; n) =min fDT(m ¡ 1; n ¡ 1) + D(m; n);DT(m ¡ 1; n) + ¢;DT(m; n ¡ 1) + ¢g (11)其中, 1 · m · N, max(1;m ¡ w) · n ·min(N;m + w). 参数¢ 是由形状特征间的匹配损失函数确定的, 对于多尺度轮廓点空间关系特征,设置¢ 2 [0:9; 1:3]. 参数w 与数据集中的形状差异有关, 通常设置其为一个远小于N 的整数. A 和B间距离可表示为Dis (A;B) = DT(N;N). 引入参数w 可以对采样点间对应关系进行约束, 既避免错误匹配也能降低匹配过程的消耗时间.Dg(m; n) =(D(m; n ¡ ng); ng+1 · nD(m;N + n ¡ ng); 1 · n · ng(12)其中, 1 · g · G, ng=g £ ceil (N=G), 在利用动态规划匹配过程中, 通常设定G 是一个较小的整数[14],本文实验过程中设置G=10. 进一步分析得到对应的DTg(N;N), 形状间距离Dis (A;B) 更新为Dis (A;B) = min1·g·GDTg(N;N) (13)由于形状轮廓的复杂性越低, 轮廓的变形越敏感, 使用形状复杂度对距离进行归一化可以提升形状匹配效果[3; 8]. 因此, 进一步引入形状复杂度分析(Shape complexity). 定义形状的复杂度为C =1NXNn=1¯¯¯¯max1·t·TSFMC(n; t) ¡ min1·t·TSFMC(n; t)¯¯¯¯(14)最终得到形状A 和B 间的距离S(A;B):S(A;B) = Dis (A;B)¯ + CA + CB(15)8 期杨亚飞等: 一种基于多尺度轮廓点空间关系特征的形状匹配方法1409其中, CA 和CB 分别表示A 和B 的复杂度. 参数¯ 可以防止式(15) 中分母值过小. 文献[3] 中的参数取值范围, 本文设置0:1 · ¯ · 1.3.2 形状匹配流程综合此前的分析, 已知形状A 和B, 下面给出形状匹配的流程:1) 提取形状A 和B 的轮廓边界, 分别利用N个采样点对A 和B 进行表示;2) 利用式(8) 计算形状A、B 对应的多尺度轮廓点空间关系特征SFMCA(n; t)、SFMCB(m; t);3) 分析形状特征之间的匹配损失函数, 求取形状A 和B 之间的距离矩阵D, 并利用式(13) 计算Dis (A;B);4) 通过式(15) 计算得到S(A;B) 作为形状A和B 之间的最终距离.此外, 在形状匹配过程中, 有时需要考虑物体翻转对匹配结果造成影响, 本文实验过程中固定形状A, 分别与形状B 以及翻转后得到的形状B0 进行匹配, 取其中的最小值作为最终结果.4 数据仿真为验证本文所提方法的有效性, 对不同数据集进行仿真分析. 实验过程中, 分别将数据集中每一样本视为查询形状, 余下样本视为目标形状, 将得到的形状距离结果按照升序排列. 如果匹配结果显示查询形状与目标形状属于相同类别, 则匹配结果正确;否则, 匹配错误.首先, 选择两组包含形状样本较少的数据集,Kimia-25 形状数据集[15] 和Kimia-99 形状数据集[16] 进行仿真实验, 并对结果进行分析和比较.Kimia-25 数据库中包含6 个类别共25 个样本, 样本示例如图6 (a) 所示. Kimia-99 数据库包含了9个类别各11 个样本, 样本示例如图6 (b) 所示.在本文的所有实验中, 为确保与其他方法比较时的公平性, 设置各形状轮廓的采样点数目均为N = 100. 在Kimia-25 数据集和Kimia-99 数据集的测试过程中, 设置窗口宽度w = 18.在Kimia-25 数据集上仿真实验时, 设置¢ =1:2, ¯ = 0:2. 表1 列出了不同方法在Kimia-25数据集下的检索结果, 给出了与查询形状最相似的1»3 组目标形状中分类正确的具体数目. 从表1 的结果中可以看出, 与其他文献中的方法相比, 本文方法在Kimia-25 数据集下得到了较好的形状检索结果.在选择本文方法进行Kimia-99 数据集仿真实验时设置¢ = 1, ¯ 取0.7. 表2 列出了Kimia-99数据集的检索结果, 分别给出了与查询形状最相似的1»10 组目标形状分类正确的具体数目及合计结果. 相比于表2 中其他方法, 本文方法可以得到更好的匹配结果. 通过以上两组数据集的仿真, 说明本文方法在小样本数据集下有较好的形状检索和识别精度.表1 Kimia-25 数据在不同方法下检索结果比较Table 1 Comparison of retrieval rates for di®erentalgorithms tested on the Kimia-25 database方法1st 2nd 3rdSharvit et. al[15] 23 21 20Gdalyahu et. al[17] 25 21 19SC[18] 25 24 22MDS+SC+DP[14] 23 20 19IDSC+DP[14] 25 24 25IS-Match[10] 25 25 24SFMC 25 25 24表2 Kimia-99 数据在不同方法下检索结果比较Table 2 Comparison of retrieval rates for di®erent algorithms tested on the Kimia-99 database方法1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th 全部SC[18] 97 91 88 85 84 77 75 66 56 37 756Hierarchical parts[10] 99 99 98 98 98 97 96 94 93 82 954TAR[13] 99 99 99 98 98 97 98 95 96 80 956IDSC+DP[14] 99 99 99 98 98 97 97 98 94 79 958MDS+SC+DP[14] 99 98 98 98 97 99 97 96 97 85 964Shape tree[19] 99 99 99 99 99 99 99 97 93 86 969Two strategies[20] 99 99 99 98 99 99 99 97 96 84 969GM + SC[21] 99 99 99 99 99 99 99 97 93 86 969Height functions[3] 99 99 99 99 98 99 99 96 95 88 971Symbolic representation[22] 99 99 99 98 99 98 98 95 96 94 975SFMC 99 99 98 99 98 98 99 99 94 93 9761410 自动化学报41 卷(a) Kimia-25 形状数据集(a) Images in Kimia-25 database(b) Kimia-99 形状数据集(b) Images in Kimia-99 database图6 两组形状数据集的剪影Fig. 6 Images in two databases为验证本文所提方法在大数据集下的效果, 选用MPEG-7 数据集[23] 进行仿真实验, 该数据集共1400 个形状剪影, 均分为70 个类别, 每个类别中有20 个样本. 使用Bull-eye 方法确定检索精度: 每个待检索形状都要与数据集中所有形状比较, 取实验结果中与每个待检索形状最相似的40 个形状, 统计这40 个形状中与待检索形状同类别的数目, 并计算对应的查全率.实验过程中, 取w = 14, ¢ = 1:1, ¯ = 0:4. 表3 列出了不同方法在该数据集下进行检索和识别测试的结果, 从表3 中数据可以看出, 本文所提方法在检索和识别过程中都可以达到较好的效果. 近年来,MPEG-7 数据集上很多方法的检索精度达到95%以上[24¡25], 甚至达到100%[26], 但是这些结果是在逐对匹配的基础上又引入形状距离学习的分析后得到的. 而本文方法及本文中的其他对比方法是针对基本的逐对形状匹配方法进行的研究, 并未引入距离学习, 因此在表3 中未列出与距离学习相关的方法.5 结论通过分析TAR 方法的不足, 本文提出了一种基于多尺度轮廓点空间关系特征的形状匹配方法. 在描述形状信息时, 相比于TAR 方法, 本文方法能够较好地反映不同尺度下的形状轮廓信息, 形状特征既具有较好的鲁棒性也具有较强的区别能力. 同时本文引入动态规划及形状复杂度分析的方法可以更准确地进行形状匹配. 通过对不同数据集上的样本进行仿真, 证明本文所提方法能够更好地进行形状特征描述且具有更高的形状匹配精度.表3 MPEG-7 数据在不同方法下的结果比较Table 3 Comparison of results for di®erent algorithmstested on the MPEG-7 database方法检索精度(Bullseye)SC[18] 76.51%CSS[7] 75.44%MDS+SC+DP[14] 84.35%IDSC+DP[14] 85.40%MCC[8] 84.93%Symbolic representation[22] 85.92%TAR[13] 87.23%Shape tree[19] 87.70%Hierarchical parts[10] 88.30%Aspect shape context[27] 88.30%Two strategies[20] 88.39%Variational shape matching[28] 89.05%Contour °exibility[29] 89.31%Locally a±ne invariant[30] 89.62%Height functions[3] 89.66%SFMC 89.36%References1 Loncaric S. A survey of shape analysis techniques. PatternRecognition, 1998, 31(8): 983¡10012 Bai X, Rao C, Wang X G. Shape vocabulary: a robustand e±cient shape representation for shape matching. IEEETransactions on Image Processing, 2014, 23(9): 3935¡39493 Wang J W, Bai X, You X G, Latecki L J. Shape matchingand classi¯cation using height functions. Pattern Recogni-tion Letters, 2012, 33(2): 134¡1434 Han Min, Zheng Dan-Chen. Shape recognition based onfuzzy shape context. Acta Automatica Sinica, 2012, 38(1):68¡75(韩敏, 郑丹晨. 基于模糊形状上下文特征的形状识别算法. 自动化学报, 2012, 38(1): 68¡75)5 Hu R X, Jia W, Ling H B, Zhao Y, Gui J. Angular pat-tern and binary angular pattern for shape retrieval. IEEETransactions on Image Processing, 2014, 23(3): 1118¡11276 Zhou Yu, Liu Jun-Tao, Bai Xiang. Research and perspectiveon shape matching. Acta Automatica Sinica, 2012, 38(6):889¡910(周瑜, 刘俊涛, 白翔. 形状匹配方法研究与展望. 自动化学报, 2012,38(6): 889¡910)7 Mokhtarian F, Abbasi S, Kittler J. E±cient and robustretrieval by shape content through curvature scale space.In: Proceedings of the 1996 International Workshop on Im-age Databases and Multi-Media Search. Amsterdam, theNetherlands: IAPR, 1996. 35¡428 Adamek T, O0Connor N E. A multiscale representationmethod for nonrigid shapes with a single closed contour.IEEE Transactions on Circuits and Systems for Video Tech-nology, 2004, 14(5): 742¡7538 期杨亚飞等: 一种基于多尺度轮廓点空间关系特征的形状匹配方法14119 Latecki L J, Lakamper R. Shape similarity measure basedon correspondence of visual parts. IEEE Transactions onPattern Analysis and Machine Intelligence, 2000, 22(10):1185¡119010 Donoser M, Riemenschneider H, Bischof H. E±cient partialshape matching of outer contours. In: Proceedings of the 9thAsian Conference on Computer Vision. Berlin, Heidelberg:Springer-Verlag, 2009. 281¡29211 Alajlan N, Kamel M S, Freeman G. Multi-object image re-trieval based on shape and topology. Image Communication,2006, 21(10): 904¡91812 Alajlan N, El Rubeb I, KamelbMS, Freeman G H. Shape re-trieval using triangle-area representation and dynamic spacewarping. Pattern recognition, 2007, 40(7): 1911¡192013 Alajlan N, Kamel M S, Freeman G H. Geometry-based im-age retrieval in binary image databases. IEEE Transactionson Pattern Analysis and Machine Intelligence, 2008, 30(6):1003¡101314 Ling H B, Jacobs D W. Shape classi¯cation using the inner-distance. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, 2007, 29(2): 286¡29915 Sharvit D, Chan J, Tek H, Kimia B B. Symmetry-basedindexing of image databases. Journal of Visual Communica-tion and Image Representation, 1998, 9(4): 366¡38016 Sebastian T B, Klein P N, Kimia B B. Recognition of shapesby editing their shock graphs. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2004, 26(5): 550¡57117 Gdalyahu Y, Weinshall D. Flexible syntactic matching ofcurves and its application to automatic hierarchical classi¯-cation of silhouettes. IEEE Transactions on Pattern Analy-sis and Machine Intelligence, 1999, 21(12): 1312¡132818 Belongie S, Malik J, Puzicha J. Shape matching and ob-ject recognition using shape contexts. IEEE Transactionson Pattern Analysis and Machine Intelligence, 2002, 24(4):509¡52219 Felzenszwalb P F, Schwartz J D. Hierarchical matching ofdeformable shapes. In: Proceedings of the 2007 IEEE Con-ference on Computer Vision and Pattern Recognition. Min-neapolis, USA: IEEE, 2007. 1¡820 Temlyakov A, Munsell B C, Waggoner J W, Wang S. Twoperceptually motivated strategies for shape classi¯cation. In:Proceedings of the 2010 IEEE Conference on Computer Vi-sion and Pattern Recognition. San Francisco, USA: IEEE,2010. 2289¡229621 Egozi A, Keller Y, Guterman H. Improving shape retrievalby spectral matching and meta similarity. IEEE Transac-tions on Image Processing, 2010, 19(5): 1319¡132722 Daliri M R, Torre V. Robust symbolic representation forshape recognition and retrieval. Pattern Recognition, 2008,41(5): 1782¡179823 Latecki L J, Lakamper R, Eckhardt T. Shape descriptorsfor non-rigid shapes with a single closed contour. In: Pro-ceedings of the 2000 IEEE Conference on Computer Visionand Pattern Recognition. Hilton Head, USA: IEEE, 2000.424¡42924 Yang X W, Prasad L, Latecki L J. A±nity learning with dif-fusion on tensor product graph. IEEE Transactions on Pat-tern Analysis and Machine Intelligence, 2013, 35(1): 28¡3825 Hu R X, Jia W, Zhao Y, Gui J. Perceptually motivatedmorphological strategies for shape retrieval. Pattern Recog-nition, 45(9): 3222¡323026 Donoser M, Bischof H. Di®usion processes for retrieval revis-ited. In: Proceedings of the 2013 IEEE Computer SocietyConference on Computer Vision and Pattern Recognition.Portland, USA: IEEE, 2013. 1320¡132727 Ling H B, Yang X W, Latecki L J. Balancing deformabilityand discriminability for shape matching. In: Proceedings ofthe 11th European Conference on Computer Vision. Crete,Greece: Springer, 2010. 411¡42428 Nasreddine K, Benzinou A, Fablet R. Variational shapematching for shape classi¯cation and retrieval. PatternRecognition Letters, 2010, 31(12): 1650¡165729 Xu C J, Liu J Z, Tang X O. 2D shape matching by con-tour °exibility. IEEE Transactions on Pattern Analysis andMachine Intelligence, 2009, 31(1): 180¡18630 Wang Z Z, Liang M. Locally a±ne invariant descriptorsfor shape matching and retrieval. Signal Processing Letters,2010, 17(9): 803¡806杨亚飞大连理工大学电子信息与电气工程学部硕士研究生. 主要研究方向为模式识别.E-mail: yangyafei@mail.dlut.edu.cn(YANG Ya-Fei Master student atthe Faculty of Electronic Informationand Electrical Engineering, Dalian Uni-versity of Technology. His main re-search interest is pattern recognition.)郑丹晨大连理工大学电子信息与电气工程学部讲师. 主要研究方向为计算机视觉和模式识别.E-mail: dcjeong@dlut.edu.cn(ZHENG Dan-Chen Lecturer atthe Faculty of Electronic Informationand Electrical Engineering, Dalian Uni-versity of Technology. His research in-terest covers computer vision and pattern recognition.)韩敏大连理工大学电子信息与电气工程学部教授. 主要研究方向为模式识别, 复杂系统建模与分析及时间序列预测. 本文通信作者.E-mail: minhan@dlut.edu.cn(HAN Min Professor at the Facultyof Electronic Information and ElectricalEngineering, Dalian University of Tech-nology. Her research interest covers pattern recognition,modeling and analysis of complex system, and time seriesprediction. Corresponding author this paper.)