关键词: 形状匹配, 仿射变换, 角点, 凸壳

Abstract: An improved algorithm of estimating the affine transformation aligninga known 2D shape and its distorted observation is proposed in this paper,as existing algorithms have difficulty of finding correspondences and the high computational complexity in solving this kind of registration problem.The conceptof corner points and the convex hull of point set are introduced to set up a group of leaner equations in the proposed approach.The corner points of the template image and observation are detected firstly,then the feature point sets are determined and the convex hulls are constructed.It is a principle in computational geometry that the convex hulls are correspondent before and after the affine transformation.An affine transformation includes six unknown parameters,which needsix equations to solve the six parameters.When there are interior points inside the convex hull,the points on convex hull,the centroid of the hull and the interior points can be used to construct six equations with the horizontal and vertical coordinates.When there are no interior points inside convex hull,a pair of extra quadratic equations should be built with horizontal and vertical coordinates using the polynomial theory to solve the six parameters.The main advantage of the proposed algorithm is that only the correspondence of point sets instead of the one-to-one correspondence of feature points between the template imageand observation are needed to be found.Experimental results show that the proposed algorithm is more accurate in parametric estimation,and its computational complexity is much lower than that of the region-based approach.

Key words: shape matching, affine transformation, corner, convex hull