平面点匹配的一点校准算法

The One Point Alignment Algorithm for 2D Point Pattern Matching

点模式匹配是一项重要的视觉课题。对于一个平面点集,由平移和旋转并伴有一定噪声作用产生另一点集,提出一个基于一点校准的点模式快速匹配算法,并推广到带有属性点的匹配问题中。基于一点校准的点模式匹配算法,其计算复杂性为O(mn),其中m,n分别是两个点集所含点的个数,比基于两点距离近似相等的校准匹配算法,其计算复杂性为O(m2nl)(其中l为第二个点集中与第一个点集中任两个点的距离近似相等的平均个数),极大地减少了计算量。

Point pattern matching is an important problem in c omputer vision.Given two sets of points in the plane,the first set contains m points.The second set has n points and is transformed by a translation and rot ation from the first one,besides that some of the points from the first set ar e missing and some new points,not in the first set,are present.The one point alignment algorithm is addressed and its computation complexity is O(mn ). But the computation complexi-ty for two points alignment algorithm is O(m 2 nl),where l is the average number of equal distances for each distance of two points.The one point alignment algorithm is generalized to attributed po int matching problem.