一种平面曲线的部分匹配算法

《一种平面曲线的部分匹配算法》由会员分享，可在线阅读，更多相关《一种平面曲线的部分匹配算法（9页珍藏版）》请在装配图网上搜索。

1、本文栏目一一图形算法与技术分层平面曲线的局部匹配算法张春莹1潘荣江11山东大学计算机科学与技术学院济南(250101)E-mail:yingzchotmail 摘要：在基于曲线匹配的检索系统中， 提高曲线的匹配速度和精度具有重要的研究意义。本文给出一种平面曲线的局部匹配算法，该算法分为整体搜索和局部匹配两个阶段。 首先，整体搜索确定候选的匹配区间。然后，在局部进行精确匹配和验证。对于特征点较少的曲线，根据曲率极值点将曲线划分为多条曲线段，采用局部线性搜索法实现曲线的局部匹配。本算法减少了曲线匹配的搜索区间，提高了曲线的匹配速度。关键字：平面曲线，局部匹配，子矩阵，曲率中图分类号:TP391A

2、partial matching algorithm for planar curveZhang Chunying Pan RongjiangSchool of Computer Science and Technology, Shandong University, Ji nan (250101)AbstractSufficiently high speed and accuracy is a central important problem in the fields of curve matching based retrieval system. We proposed a part

3、ial matching algorithm for planar curve. The algorithm divide curve matching into global search and local matching. In the global search section, the candidate partial matches between curves are determined. In local matching , matching accuracy is guaranteed. For curves with few feature points, we d

4、ivide them into small curve segments according to curvature maxima and make use of a local line search method to find the matches. Experimental results show that the method can efficiently find correct partial matches between curves under rigid body transformation.Key Words : planar curve, partial m

5、atching, sub-matrix, curvature平面曲线的局部匹配在计算机视觉和模式识别等领域都有着广泛的应用，例如在文物碎片的拼接和检索中，通过旋转体母曲线的局部匹配可以查找属于同类旋转体的碎片七在基于曲线匹配的检索系统中，如何提高曲线的匹配速度和精度具有重要的研究意义。曲线的局部匹配是指一条曲线中的一局部与另一条曲线的某一局部存在匹配关系。目前，关于曲线匹配存在多种方案。如文献综合考虑弧长和曲率两种属性比拟曲线。文献：3：利用动态规划的方法对相应特征点进行匹配。文献通过重新参数化待匹配曲线实现对n条自由参数曲线的匹配。 文献通过提取特征点并在相对应的特征点间插值实现曲线匹配，

6、适用于工业设计。文献6中对一些匹配算法进行了总结。具体到局部匹配主要有以下几种算法：文献78910首先获得曲线的特征串表示，然后利用特征串的最长公共子序列给出 曲线间最长的匹配局部。该类方法受最长公共子序列算法的限制，经常出现错误的匹配关系。最近点迭代法ICPm是点集匹配和对齐中一种常用的方法。但该方法在选择对应点时，仅考虑曲线点之间的距离，没有考虑曲线上点的顺序和连续性。ICP方法的每次运行结果是一个局部最优解，为了得到全局最优解，需要选择不同的初始位置重复执行。文献：12：13：利用线性搜索的方法寻找最正确匹配区域。文献怯在曲线匹配中采用阈值搜索法，提高了基于曲线匹配的检索速度。这种线性搜

7、索方法只适用于一条曲线完全包含于另一条曲线中的情 况，而且由于算法对曲线进行精细采样比拟，计算量较大。基于概率的方法是实现局部匹配的另一种方法，利用变换空间中的概率分布实现曲线的局部匹配。计算量与所要求的精度呈指数关系，要求的匹配精度越高， 计算量越大。文献中提出一种平面曲线的局部匹配算法，通过搜索特征点间的距离矩阵，得到匹配的子矩阵，确定匹配区域。该算法能够快 速确定匹配区域，但不能保证匹配结果的正确性。1.由整体到局部的匹配算法本文在上述算法的根底上给出由整体到局部的平面曲线局部匹配算法，整体匹配阶段采用子矩阵算法 *，在局部匹配中采用比拟曲率图12:的方法。在保证准确性的根底上，提高了曲

8、线匹配的速度。给定两条曲线T和曲线Q,首先提取曲线的特征点，获取曲线的整体信息，利用特征点之间的距离矩阵进行匹配，确定候选的匹配区间。然后，通过比拟曲线段 的曲率进行精确匹配。最后，根据匹配的对应点集计算变换矩阵。对于特征点较少的曲线， 采用局部线性搜索法实现曲线的局部匹配。本文算法所求得匹配曲线段至少包含两个特征 点，不考虑特征点间子曲线段的短距离局部匹配。图 1给出了算法的整个流程。曲线T曲线Q局部线性搜索整体搜索局部匹配J 比拟曲率差的平方和扩展和对齐图1算法流程图1.1曲线预处理首先，对输入的数字曲线进行拟合，使其成为光滑曲线二次可导1。然后，分别对输入的曲线T和曲线Q离散采样，计算采

9、样点曲率。本次采样主要为了提取曲线特征点， 以此确定曲线可能匹配的大概区域，因此，采样频率应当足够大， 能够保证寻找到曲线的特征点。本文中曲线均以准均匀三次B样条形式表示，采用等参数间隔采样法采样点数为200。最后，提取特征点。特征点的提取是模式识别研究领域中一项重要的根底性研究课题， 特征点的准确提取对曲线的匹配起着至关重要的作用，一般取大曲率点。目前，关于特征点的提取有很多方法 6亿。本文中算法提取曲率绝对值极大值点为特征点。对于曲线上任一点t,曲率k(t)=x(t)y -x。当曲线变化过于平缓，特征点处曲率绝对值极小3(x2(t) +y，2(t)2时，可忽略该特征点。后的光滑参数曲线，用

10、于本文算法。1.2整体搜索当曲线为开曲线时，两个端点也视为特征点。由于输入曲线均为拟合无需估计曲率以及平滑滤波等处理，其他文献中特征点的检测方法也适设化社.上：为曲线T上的n个特征点，tQ,tQ.tQ为曲线Q上的m个特征点。首先，分 别建立特征点距离矩阵 Dt和Dq。对曲线上的一组特征点 t1 ,t2.tn，距离矩阵D代表了特 征点间的接近程度，定义如下：dnd12.dd21d22.d._dn1.dn2. .d2nD 二nn1 n I其中 dki =J(x(t、)x(tl)2 十(y(tQy(tl)2 , k,l =1,2,., n。当曲线为闭曲线时，距离矩阵依赖于起始特征点的选择。例如对于上

11、述特征点集，选择(x(t) y(t1)为起始特征点，得到距离矩阵 矩阵D 。选择(x(tk), y(tk)为起始特征点，得到距离dkkdk(k+).dk1. dk(kW)d(k 书)kd(k+)(k41).d(k-n)1. d(k*)(k.d1k.d1(k +).d11. .d1(k). .d(k J.)kd(k 4-)(k+). d(k)1.d(k4)(k)O(k-1)行、列循环左移(k-1)列得到。因此, 选择任意特征点为起始特征点，采用循环移位进行搜索，显然矩阵D可以通过将D中的行循环上移如果曲线T和曲线Q存在匹配局部，且特征点曲线T和曲线Q的匹配局部。那么，一定存在子矩阵所得匹配结果均

12、相同。tT t TT Trt t Q i. Q i. Q口Hr.p+,tpH2.tp.和 tq 书,tq42.tq* 分力 U 位于R和子向量使得R =T d(p+)(p+) TQ d(q+)(q 相d( p 史)(p 守) d(q 专)(q +)d(p 1)(p，2) dQ d(q 1)(q 2)d(p 2)( p 2)d(q 2)(q 2)d(p 1)(p k) dQ d(q 1)(q k)d(p 2)( p k) Qd(q 2)(q，k)11d(p k)(p 1)d(p k)(p 2) Qd(q k)(q 2)d(p*)( p+)d(q*)(q*) _QILd(q k)(q 1)在子矩阵

13、的计算中，定义0/0=1。通常子矩阵中各因子并不等于常数1,而是在1周围上下浮动的变量。为了反映子矩阵中各因子的偏离程度，定义Spq =F (rij 1)2,i, j =1,2,.,k , Spq越小，特征点对应的距离矩阵越接近。从曲线起始特征点开始，沿主对角线比拟距离矩阵dt和Dq中每k对连续特征点所对应的子矩阵，并计算 Spq。其中k为固定数值，本文中取 k=3。当曲线为闭曲线时，沿矩 HM阵主对角线环绕取值。考虑到对其中一条曲线做镜像后的匹配，将曲线两端分别取为起始特征点进行匹配。为了获得所有可能匹配的特征点集，我们取Sm值最小的前K组特征点集为PM匹配点集，并定义阈值 在。当Spq&时

14、，认为对应的曲线段不存在匹配。&1要根据待匹配曲线的情况和对匹配结果的要求而定。如果&1取值过小，将会影响匹配结果的准确性，排除一些可能匹配的曲线。反之，会增加局部匹配过程的计算量。如果不存在匹配点集使Sqq 0时，倾向于选择弧长较长的曲线段作为 最终匹配结果。当 a0时，左图中曲线对对应的戋值要小于右图中的 S4值；当a=0时，& = S4;当aS4。参数a要根据数据库中曲线的情况和对匹配结果的要求而定，本文试验中取a =0.00012 。图3左图中匹配曲线段长于右图中匹配曲线段利用式(1),分别计算整体搜索阶段确定的每对候选匹配曲线段的S值，并定义阈值 如。在一对多的曲线匹配中，采用阈值搜

15、索法12可以提高曲线的匹配速度。对每对候选匹配曲线段，在计算过程中，只保存S值小于公的候选匹配曲线段，一旦 S值大于&2就退出该候选匹配曲线段的计算。如果所有候选匹配曲线段的S都大于 如，那么认为曲线T与Q不存在匹配局部。2.特征点少于3个时的匹配方法当匹配曲线中存在特征点少于 3个的曲线时，采用子矩阵算法匹配一般准确性较差。这时可以利用曲率极大值点将另一条曲线划分为小的曲线段，在子曲线段内采用线性搜索法比较曲率图。由于每个子曲线段内不含有曲率极大值点， 特征点较少的曲线与另一曲线的匹配区域一定落在该曲线的某一子曲线段内。图4匹配曲线Q和曲线段T如上图所示，匹配曲线中曲线T含有2个特征点，曲线

16、 Q中特征点数目大于 3个。按照特征点将曲线 Q划分为一些小的曲线段，每一段内都不含有曲率极大值点，而任意相邻 的两个子曲线段间必有一个曲率极大值点。因此，如果曲线段T与曲线Q存在匹配，匹配区域一定落在曲线 Q的某一子曲线段内。利用线性搜索法分别匹配曲线段T与曲线Q的每一子曲线段图5。设Q为曲线Q中的任一子曲线段，在曲线段T和Q上分别按等弧长间 距e采样，并使a足够小以反映曲线的细小变化。设曲线段 T上有m个采样点t1T,tT .tTT , Q上有n个采样点tQltQLtQ，且m?n。将长度较短的曲线段 Q在曲线段T上线性移动n比拟曲率图，寻找参数 b 使 b=argmnS(b)。其中 S(x

17、) = LE k(t%) k(tQ )/n , L jm为曲线Q的弧长。il 11I1I Ql.il、图5分别匹配曲线段T与曲线Q的每一子曲线段图6 T与Q的匹配结果比拟曲线段T与曲线Q中每一个子曲线段 Q相匹配所得的S(b)值。如果不存在曲线段 使得S(b)&2,那么曲线T与曲线Q间不存在匹配。否那么选择S(b)最小的曲线段为最终匹 配结果，如上图6所示，红色区域即为曲线段 T与曲线Q的最终匹配结果。相对于整体线性搜索法，局部线性搜索法利用曲率极大值点将曲线划分为不含极大值点 的子曲线段，排除了包含曲率极大值点的搜索区间，减少了计算量。当两条匹配曲线特征点数都少于3个时，局部线性搜索法退化为

18、整体线性搜索法。3. 扩展与对齐采用由整体到局部的匹配算法时，所得匹配曲线段，起始匹配点和结束匹配点均在特征点处。为了进一步扩展匹配曲线段，在获得相匹配的子曲线段后，分别在起始匹配点和结束匹配点处向外等弧长采样，并重新计算S值，如果S值不大于现有值，那么将起始匹配点或结束匹配点扩展至采样点。重复上述过程，直至S值大于现有值。由于匹配曲线的坐标系是相互独立的，为了变换到同一个公共的坐标系中，需要确定两个坐标系之间的刚体变换。在匹配区域确定后，我们采用文献8中基于单位四元数的绝对 定位方法，计算出刚体变换矩阵，对匹配后的采样点集进行变换和对齐。4. 实验结果及总结基于最长公共子序列的曲线匹配算法，

19、时间复杂度依赖于所选择的最长公共子序列算 法，不精确匹配时，可以到达线性时间复杂度8。ICP算法和基于概率的曲线匹配等算法，因为需要迭代求解，匹配速度较慢。如果待匹配的两条曲线分别含有m和n个采样点(mn),采用线性搜索算法比拟曲率图，需要 (m-n)* n次曲率比拟。本文中采用由整体到局部的匹配算法 ，设匹配曲线分别含有M和N个特征点，在整体搜索局部，至多需要2MN +min(M,N)-k次子矩阵比拟。在局部，只对候选匹配区域进行采样比拟。一般情况下，M和N远远小于m和n。线性搜索算法将一条曲线的曲率图沿另一条曲线的曲率图线性移动，搜索整体最优解， 以求得两条曲线的最正确匹配局部，只适用于一

20、条曲线完全包含于另一条曲线中的情况。本文算法将整体搜索与局部匹配两种算法相结合。整体搜索不仅较少了局部匹配的计算量，而且解决了线性搜索算法只适用于一条曲线完全包含于另一条曲线的缺乏。整体搜索阶段的松散阈值及多个候选区域确实定进一步保证了匹配的准确性。实验证明本文算法能准确获得曲线间的匹配局部。下列图所示的一些曲线，为应用本文算法匹配并对齐后的结果。第一栏和第二栏为输入曲线，第三栏为匹配的结果，图中红色区域为两曲线间的匹配局部。图7局部曲线匹配结果(81 = 1.0002, &2=8.0e-4 )图8和图9为应用该算法对中国省区地图轮廓线匹配的结果。图9四川和云南地图轮廓线与匹配结果以下所示为应

21、用局部线性搜索法的匹配结果，其中红色区域为两曲线间的匹配局部O本文算法通过整体搜索，有效地减少了曲线匹配的计算量，通过局部匹配的曲率比拟， 保证了匹配结果的准确性。对特征点较少的曲线，局部线性搜索算法通过曲率极大值点将曲 线划分为小的搜索区域，提高了匹配速度。本算法通过比拟特征点距离矩阵和曲率对曲线进 行匹配，可以实现刚体变换下曲线的局部匹配。由于在局部通过比拟曲率进行匹配，本文算法不适用于缩放变换下的曲线匹配。本文算法在判断曲线匹配时依赖于选择的阈值。阈值确实定与匹配的精度，曲线控制顶点数量级等有密切联系， 同一类型的曲线库可采用同一阈值标准。 如何确定适当的阈值， 需 要进一步的研究和改良

22、。参考文献1 Zhang Chunying, Pan Rongjiang. Fitting open B-spline curve to planar point clouds based on principalcurveC. Proceedings of CSIAM Geometric Design & Computing2007. Gansu,2007,165-169(in Chinese)(张春莹，潘荣江.基于主曲线的平面点云B样条开曲线拟和方法C.中国几何设计与计算新进展C.甘肃,2007,165-169)2 Sebastian T B, Klein P N, and Kimia B

23、 B. On aligning curvesJ. IEEE Transactions on Pattern Recognitionand Machine Intelligence, 2003,25(1):116 T25.3 Liu Ligang, Wang Guopu, Zhang Bo, et al. Perceptually Based Approach for Planar Shape MorphingC.Proceedings of Pacific Graphics, Seoul, Korea, 2004,111-1204 Cohen S, Elber G, and Yehuda R

24、B. Matching of freeform curvesJ. Computer-Aided Design, 1997,29(5):369 书78.5 K. C. Hui and Y. D. Li. A feature-based shape blending technique for industrial designJ. Compute-Aided Design, 30(10):823 书34, 1998.6 Veltkamp R C.Shape matching: Similarity measures and algorithms C. Proceedings of Interna

25、tionalConference on Shape Modeling and Application. Genova, Italy, 2001:128-201.7 Pan Rongjiang, Meng Xiangxu, Tu Changhe. Fragment Re-Assembly Based on LCS MatchingJ. Journal ofComputer-Aided Design & Computer Graphics, 2005 , 28 (3): 350-356 (in Chinese)(潘荣江，孟祥旭，屠长河.一种基于LCS的物体碎片自动拼接方法J.计算机学报，2005,

26、28(3):350-356)8 Wolfson H J. On curve matching J. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1990, 12(5):483-489.9 Ucoluk G , Toroslu I H. Automatic reconstruction of broken 3-D surface objects J. Computers and Graphics.1999, 23(4):573-582.10 Kong Weixi, Kimia B B. On solving 2D

27、 and 3D puzzles using curve matching C.Proceedings of the IEEEConference on Computer Vision and Pattern Recognition. Hawaii, USA, 2001,583-590.11 Paul J B, McKay N D.A method for registration of 3-d shapes J.IEEE Transactions on Pattern Analysis andMachine Intelligence, 1992, 14(2):239-256.12 John C

28、.Femiani, Anshuman Razdan, Gerald Farin. Curve Shapes: Comparison and Alignment.TPAMI November (2004).13 Cohen S D, Guibas L G. Partial Matching of Planar Polylines under Similarity Transformations C.Proceedings of the 8th Annual Symposium on Discrete Algorithms. New Orleans, Louisiana, 1997,777-786

29、.14 Alt H, Scharf L, Scholz S. Probabilistic matching of sets of polygonal curves C. Proceedings of the 22nd European Workshop on Computational Geometry. Delphi, Greece, 2006, 107-110.15 Saber E, Xu Yang, Tekalp A M, Partial Shape Recognition by sub-matrix matching for partial matching guided image

30、labeling J. Pattern Recognition, 2005, 38(10):1560-1573.16 Mehrotra R, Nichani S, Ranganathan N. Corner detectionJ. Pattern Recognition, 23(11):12231233, 1990.17 Zhu Pengfei and Chirlian P. On critical point detection of digital shapesj. IEEE Transactions on Pattern Recognition and Machine Intelligence, 17(8):737 亍48, 1995.18 Horn B.K.P.Closed-form solution of absolute orientation using quaternions J. Journal of the Optical Societyof America, 1987, 4(4):629-642.作者简介：张春莹 女，1984年生，山东大学硕士研究生，主要研究方向为计算机图形学。潘荣江 男，1968年生，博士，副教授，硕士生导师，主要研究方向为计算几何、计算机图形学、图像处 理。