本文栏目——图形算法与技术分层平面曲线的部分匹配算法张春莹1潘荣江11山东大学计算机科学与技术学院济南(250101)E-mail:yingzc@hotmail摘要：在基于曲线匹配的检索系统中，提高曲线的匹配速度和精度具有重要的研究意义。本文给出一种平面曲线的部分匹配算法，该算法分为整体搜索和局部匹配两个阶段。首先，整体搜索确定候选的匹配区间。然后，在局部进行精确匹配和验证。对于特征点较少的曲线，根据曲率极值点将曲线划分为多条曲线段，采用局部线性搜索法实现曲线的部分匹配。本算法减少了曲线匹配的搜索区间，提高了曲线的匹配速度。关键字：平面曲线，部分匹配，子矩阵，曲率：TP391ApartialmatchingalgorithmforplanarcurveZhangChunyingPanRong激angSchoolofComputerScienceandTechnology,ShandongUniversity,激’nan(250101)AbstractSufficientlyhighspeedandaccuracyisacentralimportantprobleminthefieldsofcurvematchingbasedretrievalsystem.Weproposedapartialmatchingalgorithmforplanarcurve.Thealgorithmdividecurvematchingintoglobalsearchandlocalmatching.Intheglobalsearchsection,thecandidatepartialmatchesbetweencurvesaredetermined.Inlocalmatching，matchingaccuracyisguaranteed.Forcurveswithfewfeaturepoints,wedividethemintosmallcurvesegmentsaccordingtocurvaturemaximaandmakeuseofalocallinesearchmethodtofindthematches.Experimentalresultsshowthatthemethodcanefficientlyfindcorrectpartialmatchesbetweencurvesunderrigidbodytransformation.KeyWords：planarcurve,partialmatching,sub-matrix,curvature平面曲线的部分匹配在计算机视觉和模式识别等领域都有着广泛的应用，例如在文物碎片的拼接和检索中，通过旋转体母曲线的部分匹配可以查找属于同类旋转体的碎片［1］。在基于曲线匹配的检索系统中，如何提高曲线的匹配速度和精度具有重要的研究意义。曲线的部分匹配是指一条曲线中的一部分与另一条曲线的某一部分存在匹配关系。目前，关于曲线匹配存在多种方案。如文献［2］综合考虑弧长和曲率两种属性比较曲线。文献［3］利用动态规划的方法对相应特征点进行匹配。文献［4］通过重新参数化待匹配曲线实现对n条自由参数曲线的匹配。文献［5］通过提取特征点并在相对应的特征点间插值实现曲线匹配，适用于工业设计。文献［6］中对一些匹配算法进行了总结。具体到部分匹配主要有以下几种算法：文献［7］［8］［9］［10］首先获得曲线的特征串表示，然后利用特征串的最长公共子序列给出曲线间最长的匹配部分。该类方法受最长公共子序列算法的限制，经常出现错误的匹配关系。最近点迭代法ICP［11］是点集匹配和对齐中一种常用的方法。但该方法在选择对应点时，仅考虑曲线点之间的距离，没有考虑曲线上点的顺序和连续性。ICP方法的每次运行结果是一个局部最优解，为了得到全局最优解，需要选择不同的初始位置重复执行。文献［12］［13］利用线性搜索的方法寻找最佳匹配区域。文献［12］在曲线匹配中采用阈值搜索法，提高了基于曲线匹配的检索速度。这种线性搜索方法只适用于一条曲线完全包含于另一条曲线中的情况，而且由于算法对曲线进行精细采样比较，计算量较大。基于概率的方法是实现部分匹配的另一种方法［14］，利用变换空间中的概率分布实现曲线的部分匹配。计算量与所要求的精度呈指数关系，要求的匹配精度越高，计算量越大。文献［15］中提出一种平面曲线的部分匹配算法，通过搜索特征点间的距离矩阵，得到匹配的子矩阵，确定匹配区域。该算法能够快速确定匹配区域，但不能保证匹配结果的正确性。1.由整体到局部的匹配算法本文在上述算法的基础上给出由整体到局部的平面曲线部分匹配算法，整体匹配阶段采用子矩阵算法［15］，在局部匹配中采用比较曲率图［12］的方法。在保证准确性的基础上，提高了曲线匹配的速度。给定两条曲线和曲线,首先提取曲线的特征点，获取曲线的整体信息，利用特征点之间的距离矩阵进行匹配，确定候选的匹配区间。然后，通过比较曲线段的曲率进行精确匹配。最后，根据匹配的对应点集计算变换矩阵。对于特...