基于局部尺度特征描述和改进DTW技术的局部轮廓匹配算法

徐贵力，赵　妍，姜　斌，王正盛，李开宇，郭瑞鹏

(南京航空航天大学自动化学院，江苏南京210016)



基于局部尺度特征描述和改进DTW技术的局部轮廓匹配算法

徐贵力，赵妍，姜斌，王正盛，李开宇，郭瑞鹏

(南京航空航天大学自动化学院，江苏南京210016)

摘要：基于轮廓的图像匹配是计算机视觉领域中的重要问题，但是目前尚未有较成熟的算法能够很好地解决局部轮廓匹配问题及非相似变换和非刚体变换引起的轮廓形变问题.根据局部轮廓结构在产生形变时具有相对稳定性的规律及融合轮廓局部信息和全局信息的轮廓描述思想，本文提出了一种具有尺度、旋转、平移不变性，形变鲁棒性和初始点无关性的局部尺度轮廓描述算法.在此基础上，针对线性匹配方法效果不佳以及传统DTW技术约束路径的线性度不满足轮廓采样特性要求的问题，提出一种基于改进DTW技术的轮廓匹配算法，即结合轮廓采样特性设置九宫格的路径约束条件，以旋转角度为参数，计算全局最佳匹配路径.实验结果表明，对于存在尺度、平移、旋转及形变关系的两轮廓，该方法能较好地实现轮廓间的局部匹配，并且其匹配准确率平均约为92%，较HD算法提高了30%，较传统DTW算法提高了26%.

关键词：计算机视觉;轮廓描述;局部尺度;局部轮廓匹配;动态时间规整;形变

1　引言

不同于纹理、颜色等其它基本特征，轮廓形状是红外、雷达和可见光等异源图像间的共性特征，且具有较好的不变性［1］，因此，轮廓匹配在导航制导、目标跟踪、医疗诊断等领域得到广泛的应用.轮廓匹配算法通常由两部分组成:轮廓描述和轮廓匹配.

基于轮廓点空间位置关系的轮廓描述方法是近年来比较重要的轮廓描述方法，它通过对轮廓点序列的空间位置分布关系的统计来描述轮廓，取得了很好的描述效果，学者们围绕着该方法所涉及的统计范围、统计方法和统计信息这三个问题展开研究，设计出了多种基于空间位置关系的轮廓描述方法.Xin Shu等［2］根据轮廓点在极坐标下的分布关系提出了一种轮廓点分布直方图(CPDH)的描述算法; TU等［3，4］定义一组信息特征，分别在小的局部范围内和整个形状轮廓上考察目标轮廓点及其全局邻域轮廓点之间夹角的统计关系.这类算法的描述符设计简单有效，具有较好的几何不变性和准确的轮廓描述能力，是研究界的重点，但是基本上只能处理简单闭合的轮廓.基于多尺度理论的轮廓描述方法主要通过曲线的凹凸特性来判定轮廓的性质，代表性方法有Felzenszwalb等［5］提出的轮廓树描述方法，采用层次化的描述方法表示不同分辨率上获得的轮廓信息; Bartolini等［6］提出了一种基于傅里叶变换的描述子WARP，它结合傅里叶系数的相位信息和振幅信息来描述轮廓，使得描述更加精确;牛庆肖等［7］提出一种基于八方向链码和快速傅里叶变换的轮廓描述方法，该描述具有旋转、尺度和平移不变性.轮廓的简单几何变换只是关系到轮廓频域描述子的简单操作，但是不能很好地描述出现遮挡情况的轮廓.总体来看，较好的轮廓描述方法必须要融合轮廓的全局信息和局部信息，这也将是本文研究的重点.

轮廓匹配的过程可以认为是在解空间中寻求最优解使得目标函数最小的过程，代表性方法有Chui等［8，9］在迭代最近点(ICP)算法［10］的基础上提出基于薄板样条的鲁棒点匹配算法(TPS-RPM).该算法由两部分组成:更新匹配关系和根据匹配关系更新形变参数，TPSRPM用确定性模拟退火算法多次迭代计算全局最优解，以取得更好的匹配效果，但是由于退火算法的固有限制，所以收敛速度慢，另外，由于缺少轮廓空间信息，故在多条复杂轮廓的情况下匹配精度不高.Van等［11］采用蚁群算法搜索最佳匹配，但是匹配效果依赖于蚁群算法的寻优能力，有时得不到较好的结果.Liu等［12］先对轮廓进行采样，并对采样点进行特征描述，然后用动态规划求最佳匹配，该方法减小了搜索空间，但是性能受特征点提取算法的制约.

目前轮廓匹配主要存在以下两个问题:不同视角变换所引起的轮廓形变问题;局部遮挡所导致的局部轮廓匹配的问题.针对以上问题，根据局部轮廓结构在产生形变时具有相对稳定性的规律及一个好的轮廓描述方法需融合轮廓局部信息和全局信息的主流思想，本文提出了一种具有尺度、旋转、平移不变性，形变鲁棒性和初始点无关性的局部尺度轮廓描述算法:采用保持轮廓局部结构的特征描述符表示轮廓，根据局部尺度进行非均匀采样，每个采样点的特征矢量描述的是一段轮廓的局部信息，一系列顺序采样点的特征构成轮廓的全局信息;在此基础上，提出一种基于改进DTW技术的轮廓匹配算法，即结合轮廓采样特性设置九宫格的路径约束条件，在该约束条件下通过逐步判断和迭代来优化出最佳匹配路径;最后，以旋转角度为参数，计算全局最短路径.

2　基于局部尺度的轮廓描述算法

2.1保持轮廓局部结构的描述符

研究发现当轮廓发生形变时，其轮廓上某一点处的特征信息会发生一定的变化，但是轮廓上其它点相对于该点的位置，即该点之外的轮廓局部结构，相对保持稳定，例如图1(a)中点A和其局部轮廓上的点B～F，当发生形变时，如图1(b)，点A处的特征信息，如曲率、坐标、到质心的距离等，明显产生了变化，相比而言，顺序用线段AB～AF的长度构成特征矢量来描述轮廓中A点会更加稳定，即A处的特征描述可以表示为矢量(|AB|，|AC|，|AD|，|AE|，|AF|)，即使轮廓发生一定程度的形变，相应A'处的特征描述矢量变为(|A'B'|，|A'C'|，| A'D'|，| A'E'|，| A'F'| )，但该矢量变化并不是很大，该特征描述反映的是点A附近的局部结构信息.

表1中以A和A'处的曲率和局部结构矢量为例，定量地说明了反映局部结构的矢量描述稳定性更好(0.12＜＜0.98)，对于标量曲率值，其计算方法如式(1)所示，对于局部结构矢量，其矢量计算公式结合式(1)和式(2)，其中变量a和b分别表示形变前后的标量特征元素，变量a和b分别表示形变前后的矢量特征，变量ai和bi分别表示形变前后的矢量特征中的第i个特征元素，变量k表示特征矢量中元素的个数;另外，当进行局部轮廓匹配时，不仅需要轮廓的整体信息，更需要结合其局部信息，将二者融合在描述算法中.

考虑以上两种情况，并且参考文献［13］中的轮廓描述方法，本文最终采用保持轮廓局部结构的描述符表示轮廓.已知轮廓曲线q，设轮廓上一点qi，该点的前一个相邻点为qi -1，后一个相邻点为qi +1，其中轮廓末点的下一个点被认为是首点.在点qi处定义k条线段，线段qiqi -1和qiqi +1分别是第一条线段和最后一条线段，为了清楚地看到并区分边界线段和其它线段，分别对点qi和其相邻点qi -1，qi +1之间的间隔做了放大处理，并对它们形成的两条边界线段进行延长和加粗处理，如图2所示，其余k -2条线段是通过在两条边界线段间等角度划分，并且分别延划分角度方向第一次与轮廓相交得到.

表1　定量验证形变对描述特征的影响

θ1(qi)和θk(qi)分别是第一条和最后一条线段的方向角，这里的方向角定义为水平轴正半轴逆时针指向该线段所形成的角度，θj(qi)∈［0，2π］，其中，j∈［1，k］.为了使所获得的线段均能够与轮廓发生相交，定义两边界线段之间的角度为

其余k -2条线段划分间隔为Δθ1k(qi)/(k -1).故这k条线段长度组成的k维矢量，构成了点qi处的特征描述，即v(qi)=［di1，di2，…，dik］，其中，dij是第j个线段的长度，如图2所示.

可见点qi处的特征描述v(qi)反映的是一段轮廓的局部结构，即轮廓局部信息.若轮廓为开轮廓，则从轮廓上点qi发出的k条线中有可能存在不能与轮廓相交的线，相应的dij被标记为d∞，如图2(b)中虚线所示.

2.2基于局部尺度进行非均匀采样

点qi处的局部尺度定义为其特征描述矢量中所有有限长度的平均值［14］，即

其中，Ci= { dij∈v(qi)|dij≠d∞}，|Ci|表示Ci这个集合中元素的个数.局部尺度值的大小和该点特征矢量所能描述的轮廓信息的多少成正比.因此，可以根据局部尺度值对轮廓进行非均匀采样，即若该点的特征矢量所能描述的轮廓信息较多，那么在此处的采样就比较稀疏，反之，比较稠密，如图3所示.

已知轮廓上任意一点qi，其局部尺度值Scale(qi)，则该点与下一个即将被采样的点之间采样间隔offset(qi)=∂＊Scale(qi)，∂∈(0，1］，其中∂控制着采样点密度，综合时间和效果两个因素，本文以下的实验中∂均取0.7.迭代此过程，直至整个轮廓采样结束，结果如图3所示.一系列顺序采样点的特征描述矢量组成了整个轮廓的全局描述.

即归一化后特征矢量v1(qi)=［d1i1，d1i2，…，d1ik］.对于存在缩放关系的两轮廓，尤其是缩放倍数较大时，如缩小4倍时，本文算法的匹配效果明显会优于文献［14］算法，在下面的实验部分将得以验证.

由于每个点的特征描述反映的并不只是该点的信息，而是其相对保持稳定的邻域局部结构，故其对轮廓变形具有一定的鲁棒性;由于结合了轮廓的局部信息

2.3特征描述符的归一化研究

对于存在缩放关系的两轮廓需要对前文特征矢量中的每一个元素进行归一化处理，即用特征矢量中每一个元素除以所有有效元素的平均值，它反映每一个元素与平均值的相对大小关系，与轮廓尺度无关.和全局信息，故适合于局部轮廓匹配;此外，由于一系列顺序采样点的特征描述能够构成轮廓的全局信息，与起始点的选择无关，故该算法不受初始点的影响.

3　基于改进DTW的轮廓匹配算法

由于本文中两个待匹配轮廓上的采样点之间并不存在一一对应的线性关系，因此，将DTW非线性规整技术应用于轮廓匹配中，为了减少计算量和放宽对轮廓采样点位置一致性的要求，本文结合轮廓描述特点，在九宫格中设置局部路径约束条件，在该约束条件下通过逐步判断和迭代来优化出最佳匹配路径;最后，以旋转角度为参数，计算全局最短路径，以提高匹配的正确率.

局部路径约束的DTW算法原理图如图5(a)所示.本文将详细地以闭合轮廓和开轮廓(闭合轮廓的一部分)之间的匹配为例，重点阐述其匹配算法的原理:把开轮廓上的每个采样点n =1～N在二维直角坐标系中的横轴标出，把闭合轮廓上的每个采样点在纵轴上标出，为了避免起始点的影响在纵轴上对闭合轮廓取两个采样周期m =1～2* M.通过这些整数坐标画出网格线，网格中的每个交叉点(i，j)表示开轮廓上的某一采样点与闭合轮廓上某一采样点的对应.

该算法主要分两步实现:一是计算两个轮廓各采样点之间的特征矢量距离;二是通过求得的特征矢量距离矩阵，优化出一条最佳匹配路径，即沿该路径的积累距离达到最小值.

已知开轮廓q和闭合轮廓r，则开轮廓上任意采样点qi和闭合轮廓上任意采样点rj之间的特征矢量距离为:

根据上述两式可见，D(qi，rj)的取值范围是［0，1)，值越接近1表示越不匹配，越接近0表示越匹配.

优化最佳路径的过程是逐步判断和递推的过程.对于网格中任意格点(m，n)，到达该格点的积累距离等于该点的特征矢量距离加其前续格点的积累距离.但是前续格点是如何选择的，前续格点的选择是由路径的局部约束条件确定的.

根据第二部分特征描述的特点，如图4所示，两个轮廓中的采样点并不是呈一对一的线性对应关系，因此，线性匹配算法在这里是行不通的.另外，约束条件的设置使得路径约束的非线性度必须要和该采样特性相匹配，文献［14］设置了三条路径，如图5(b)中路径①，②，③所示，但是根据图4中两轮廓采样点特性发现，本文采样点的对应关系达到了一对三，其非线性度大于文献［14］中的路径设置，二者非线性度不匹配，故文献［14］中的路径设置在这里不合适.综合考虑采样特性和计算复杂度两个因素本文提出在该点左下方的九宫格内设置路径约束条件，如图5(b)所示，每条路径反应了不同的线性关系，其中路径⑥，⑦即反映了一对三的非线性关系，所以格点(m，n)的前续格点为图5(b)中九个标注格点中积累距离最小的那个格点，即

所求得的积累距离矩阵中第N列元素的最小值，即min(Cost(:，N))所对应的行数为开轮廓末点对应在闭合轮廓上的位置，这个最小值所对应的网格交叉点即是优化出来的最佳路径的末端，如图5(a)中B点.根据该路径在纵轴上所跨越的长度，可获得该路径的端点A，即得到开轮廓首点对应在闭合轮廓上的位置，从而获得两个轮廓之间的最优匹配.

另外，对于开轮廓之间的匹配(本文只针对包含关系的两开轮廓间的匹配，即其中一个开轮廓是另一个开轮廓一部分的情况)，同样地，本算法主要分为两大块，首先基于局部尺度进行非均匀采样，对采样点采用保持轮廓局部结构的描述符进行轮廓描述，对特征描述矢量进行归一化处理;其次采用基于九宫格路径约束的DTW算法就行优化匹配.针对以上这两部分，现从理论的角度分析该算法在开轮廓间匹配的有效性:首先，一系列顺序采样点的特征描述矢量组成了整个轮廓的全局信息，即使是开轮廓，另外，某一点的特征描述反映了该点的局部轮廓信息，适合于局部之间的匹配;其次，在DTW算法第一步计算特征矢量距离时，对于从开轮廓上的点发出的k条线中存在不能与轮廓相交的情况，将对应特征的距离定为0(越接近0表示越匹配)，如式(2)所示，从而去除开轮廓对匹配的影响.为了进一步说明，本文在实验部分将给出对应的实验用例进行验证.

为了使算法的普适性更好，精确性更高，避免局部最优化导致错误匹配，本文引入待匹配轮廓之间的旋转角度参数β，此时的积累距离矩阵为Cost(m，n，β)，

4　实验结果对比和分析

为了验证该算法能够一定程度上地解决局部轮廓匹配问题及非相似变换和非刚体变换引起的轮廓形变问题，本文设计以下两组实验:开轮廓和闭合轮廓之间的匹配以及开轮廓与开轮廓之间的匹配.

实验所用的轮廓均是由图6(MPEG7数据库)这些原始形状变换得到的，其中，图(a1)尺寸为图(a2)是的4倍，图(a3)尺寸与(a1)相近但产生了一定程度的形变;图(b1)尺寸为图(b2)的4倍，图(b3)尺寸与(b2)相近但产生了一定程度的形变;同样的，图(c1)尺寸为图(c2)2倍，图(c3)尺寸与(c2)相近但产生了一定的形变;图(d1)尺寸为图(d2)2倍，图(d3)尺寸与(d2)相近但存在一定的形变.

4.1实验可视化结果

4.1.1开轮廓和闭合轮廓的匹配

为了验证本文算法在开-闭轮廓匹配方面的有效性，本文以图6(a1)～(a3)中的三幅图像和图6(b1)～(b3)中的三幅图像为原型进行轮廓提取［15］，两组图均采用文献［14］中的局部Hausdorff Distance(HD)算法［14］，文献［13］中的基于局部尺度和传统DTW的算法，以及本文算法进行匹配，匹配结果如图7和图8所示.其中，第一行是存在4倍缩放且发生旋转的开-闭轮廓之间的匹配结果，第二行是存在缩放、形变以及旋转的开-闭轮廓匹配结果.为了说明算法不受起始点的限制，本实验将轮廓分别按顺时针和逆时针两个方向旋转一定角度.

4.1.2开轮廓和开轮廓的匹配

本文以图6(c1)～(c3)中的三幅图像和图6(d1)～(d3)中的三幅图像为原型，进行两组实验验证该算法适用于开轮廓之间的匹配.实验结果如图9、10所示.其中，第一行是发生旋转的开轮廓-开轮廓之间的局部匹配结果，第二行是存在2倍缩放、一定形变以及旋转关系的开轮廓-开轮廓局部匹配结果.

4.2实验定量化结果

从三个因素来定量化评价轮廓匹配算法的有效性［16］:错匹配率ef，漏匹配率em和准确率P.

其中，Af表示错误匹配轮廓点的集合; Am表示漏匹配轮廓点的集合; Az1是指匹配出来所有轮廓点的集合; Az2是指理想匹配所有轮廓点的集合; A表示正确匹配轮廓点的集合; card(X)表示集合X中元素的个数.对于上述实验图片，分别计算三种算法的上述三个因素，如表2可见，本文方法的匹配准确率平均约为0.92，较HD算法提高了30%，较文献［14］算法提高了26%.

4.3结果分析

由以上实验结果可知，对于存在缩放、任意角度旋转以及一定程度形变的两轮廓，无论是开轮廓-闭合轮廓匹配，还是开轮廓-开轮廓匹配，本文算法都能取得较好的匹配结果，但是，被学者认可的局部Hausdorff距离匹配算法以及文献［13］中的传统DTW算法在这里却产生了错误匹配.分析其原因:采用本文的非均匀采样方法进行采样，虽然对所有采样点的特征描述构成了整条轮廓的全局信息，并且每个采样点的特征描述能够反映小段轮廓的局部信息，但是，两个轮廓上对应采样点的位置并不一致，对于本文及现有的采样方法所获得的采样点非一致的情况，本文算法得到了较好的匹配结果(如4.1可视化结果和4.2定量化结果所示)，实验证明本文算法一定程度上不受采样点非一致的影响，但是基于局部Hausdorff距离的轮廓匹配方法对采样点位置一致性要求较严格，因此，在轮廓发生旋转之后，其轮廓点位置会发生变化，则其匹配结果变差，如图9第一行样本图像逆时针旋转60度和不发生旋转的结果所示，因此，此处采用Hausdorff距离算法的话，随机性较大;另外，采用文献［13］算法，其中的传统DTW技术属于非线性匹配方法，其实验结果仍然不是很理想，主要是因为约束条件的设置问题，约束条件的设置反映着非线性匹配的非线性度，该文献中约束条件设置的是图5中①、②、③三条路径约束，而本文中两轮廓采样点特征描述之间对应关系的非线性度更大，二者非线性度不匹配，因此其实验结果不是很理想，另外文献［14］轮廓描述中并没有对特征矢量进行归一化处理，所以对于存在较大缩放的两轮廓，其匹配结果较差，如图7第一行所示，其缩放关系为4倍;因此，将本文的轮廓描述算法和与之相匹配的九宫格路径DTW技术结合，得到了较好的匹配结果，如图7～10(d)所示.

表2　匹配精度的定量化分析

5　结论

(1)本文提出了一种基于保持局部结构描述符和改进DTW的轮廓匹配算法，一定程度上解决了存在几何变换关系的两轮廓间的局部匹配问题及非相似变换和非刚体变换引起的轮廓较小形变问题，且不受起始点的限制.

(2)基于保持局部结构的轮廓描述符较好地融合了轮廓的全局信息和局部信息，具有旋转、尺度不变性，并且对一定程度的形变具有鲁棒性.

(3)针对线性匹配方法效果不佳以及传统DTW技术约束路径的线性度不满足轮廓匹配特性要求，提出一种基于改进DTW技术的轮廓匹配算法.即结合轮廓采样特性设置九宫格的路径约束条件，在该约束条件下通过逐步判断和迭代来优化出最佳匹配路径.

(4)本文算法的匹配准确率平均约为92%，较HD算法提高了30%，较文献［13］算法提高了26%.

参考文献

［1］曹传东，徐贵力，陈欣等.基于力场转换理论的图像粗大边缘检测方法［J］.航空学报，2011，32(5): 891 -899.Cao C D，Xu G L，Chen X，et al.Image edge detection al-gorithm based on force field transformation［J］.Acta Aeronoutica et Astronautica Sinica，2011，32(5): 891 -899.(in Chinese)

［2］Xin Shu，Xiaojun Wu.A novel contour descriptor for 2D shape matching and its application to image retrieval［J］.Image and Vision Computing，2011，(29): 286 -294.

［3］Tu Z W，Yuille A.Shape matching and recognition: using generative models and informative features［A］.Proceedings of the 8th European Conference on Computer Vision(ECCV)［C］.Prague，Czech Republic: Springer，2004.195 -209.

［4］Tu Z W，Zheng S F，Yuille A.Shape matching and registration by data-driven EM［J］.Computer Vision and Image Understanding，2008，109(3): 290 -304.

［5］Felzenszwalb P F，Schwartz J D.Hierarchical matching of deformable shapes［A］.Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition(CVPR)［C］.Minneapolis，MN，USA: IEEE，2007.1 -8.

［6］Bartolini I，Ciaccia P，Patella M.Warp: accurate retrieval of shapes using phase of Fourier descriptors and time warping distance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(1): 142 -147.

［7］牛庆肖，张桦，徐光平，薛彦兵.基于链码和快速傅里叶变换的轮廓描绘方法［J］.光电子激光，2011，22(12): 1857 -1861.Niu Q X，Zhang H，Xu G P，et al.A contour description method based on chain and fast Fourier transform［J］.Journal of Optoelectronics Laser，2011，22(12): 1857 - 1861.(in Chinese)

［8］Chui H，Rangarajan A.A new point matching algorithm for non-rigid point matching［A］.IEEE International Conference on Computer Vision and Pattern Recognition［C］.USA: IEEE，2000.44 -51.

［9］Chui H，Rangarajan A.A new point matching algorithm for non-rigid registration［J］.Computer Vision and Image Understanding，2003，89(2): 114 -141.

［10］Besl P J，Mckay N D.A method for registration of 3-D shapes［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14(4): 239 -256.

［11］Van K O，Hamarneh G，Zhang H，et al.Contour correspondence via ant colony optimization［A］.Proceedings of the 15th Pacific Conference on Computer Graphics and Applications［C］.USA: IEEE，2007.271 -280.

［12］Liu L，Wang G，Zhang B，et al.Perceptually based approach for planar shape morphing［A］.Proceedings of the 12th Pacific Conference on Computer Graphics and Applications［C］.USA: IEEE，2004.111 -120.

［13］Damien Michel，Iasonas Oikonomidis，Antonis Argyros.Scale invariant and deformation tolerant partial shape matching［J］.Image and Vision Computing，2011，29: 459 -469.

［14］高晶，孙继银，刘婧.基于邻域灰度信息的Hausdorff距离图像匹配方法［J］.计算机应用，2011，31(3): 741 -744.Gao J，Sun J Y，Liu J.Image matching method based on normalized grayscale variance Hausdorf distance［J］.Journal of Computer Applications，2011，31(3): 741 - 744.(in Chinese)

［15］陈青，刘金平，唐朝晖，李建奇，吴敏.基于分数阶微分的图像边缘细节检测与提取［J］.电子学报，2013，41(10): 1873 -1880.Chen Qing，Liu JinPing，，Tang ZhaoHui，Li JianQi，Wu Min.Detection and extraction of image edge curves and detailed features using fractional differentiation［J］.Acta Electronica Sinica，2013 41(10): 1873 - 1880.(in Chinese)

［16］Grigorescu C，Petkov N，Westenberg M A.Contour detection based on nonclassical receptive field inhibition［J］.IEEE Transactions on Image Processing，2003，12(7):729 -739.

徐贵力男，1972年生，黑龙江佳木斯人.现为南京航空航天大学博士生导师，从事光电检测、计算机视觉方面的研究.

E-mail: guilixu@163.com

赵妍女，1989年生，河南人新乡人.硕士研究生，从事机器视觉方面的研究.

E-mail: zhao.yan109@163.com

Partial Contour Matching Algorithm Based on Local Scale Description and Improved DTW

XU Gui-li，ZHAO Yan，JIANG Bin，WANG Zheng-sheng，LI Kai-yu，GUO Rui-peng
(Institute of Automation，Nanjing University of Aeronautics and Astronautics，Nanjing，Jiangsu 210016，China)

Abstract:Image matching based on contour is an important issue in computer vision，but now there is no mature algorithm that can solve the problems of partial contour matching and deformation caused by non-similar transformation and non-rigid transformation.According to the conclusions that partial contour structure has relative stability and a good description need to merge the contour’s local and global information，a local scale description method is proposed which is scale，rotation invariant，deformation tolerant and initial point independence.On this basis，a contour matching algorithm is proposed based on improved DTW.Experimental results show that the proposed method can realize the partial matching between open contour and open contour as well as closed contour.Its matching precision is 92%on average，and improves 30%compared with HD method，improves 26%compared with traditional DTW.

Key words:machine vision; contour description; local scale; partial matching; dynamic time warping; deformation

作者简介

基金项目:国家自然科学基金(No.61473148)

收稿日期:2014-05-26;修回日期: 2014-11-13;责任编辑:孙瑶

DOI:电子学报URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.020

中图分类号：TP391

文献标识码：A

文章编号：0372-2112(2016)01-0135-08