1 Introduction
Shape matching or image registration is often encountered in image analysis, computer vision, and pattern recognition. It is typically formulated as a point matching problem since point representations are general and easy to extract. In this paper, we focus on point-pattern-based shape matching. Shapes can be roughly categorized as rigid or nonrigid, and they may undergo deformation in captured images. With a small number of transformation parameters, rigid shape matching is relatively easy. Rigid shape matching under the affine or projective transformation has been widely studied [1]. Recently, point matching for nonrigid shapes has received a great deal of attention. There are two unknowns in a shape matching problem: the correspondence and the transformation [2]. Since solving for either without information regarding the other is quite difficult, most approaches to nonrigid shape matching use an iterated estimation framework. Given an estimate of the correspondence, the transformation may be estimated and used to update the correspondence. The iterated closest point (ICP) algorithm, a well-known heuristic approach proposed by Besl and McKay, is one example [3]. Assuming two shapes are roughly aligned, for each point in one shape, the closest point in the other shape is taken as the current estimate of the correspondence. Recently, Chui and Rangarajan [2] proposed an optimization-based approach, the TPS-RPM algorithm, in which two unknown variables (transformation and correspondence) are combined into an objective function. The soft assignment technique and deterministic annealing algorithm are used to search for an optimal solution. Belongie et al. [4] proposed another method for nonrigid point matching. In this approach, the shape context is assigned to each point, which describes the distribution of the remaining points relative to this point. The solution that minimizes the overall shape context distances is the optimal match between two point sets. One drawback of this approach is that neighboring points in one shape may be matched to two points far apart in the other shape.