A new point matching algorithm for non-rigid registration
Introduction
Feature-based registration problems frequently arise in the domains of computer vision and medical imaging. With the salient structures in two images represented as compact geometrical entities (e.g., points, curves, and surfaces), the registration problem is to find the optimum or a good suboptimal spatial transformation/mapping between the two sets of features. The point feature, represented by feature location is the simplest form of feature. It often serves as the basis upon which other more sophisticated representations (such as curves, surfaces) can be built. In this sense, it can also be regarded as the most fundamental of all features. However, feature-based registration using point features alone can be quite difficult.
One common factor is the noise arising from the processes of image acquisition and feature extraction. The presence of noise means that the resulting feature points cannot be exactly matched. Another factor is the existence of outliers—many point features may exist in one point-set that have no corresponding points (homologies) in the other and hence need to be rejected during the matching process. Finally, the geometric transformations may need to incorporate high dimensional non-rigid mappings in order to account for deformations of the point-sets. Consequently, a general point feature registration algorithm needs to address all these issues. It should be able to solve for the correspondences between two point-sets, reject outliers and determine a good non-rigid transformation that can map one point-set onto the other.
The need for non-rigid registration occurs in many real world applications. Tasks like template matching for hand-written characters in OCR, generating smoothly interpolated intermediate frames between the key frames in cartoon animation, tracking human body motion in motion tracking, recovering dynamic motion of the heart in cardiac image analysis and registering human brain MRI images in brain mapping, all involve finding the optimal transformation between closely related but different objects or shapes. It is such a commonly occurring problem that many methods have been proposed to attack various aspects of the problem. However, because of the great complexity introduced by the high dimensionality of the non-rigid mappings, all existing methods usually simplify the problem to make it more tractable. For example, the mappings can be approximated by articulated rigid mappings instead of being fully non-rigid. Restricting the point-sets to lie along curves, the set of correspondence can be constrained using the curve ordering information. Simple heuristics such as using nearest-neighbor relationships to assign correspondence (as in the iterated closest point algorithm [5]) have also been widely used. Though most methods tolerate a certain amount of noise, they normally assume that there are no outliers. These simplifications may alleviate the difficulty of the matching problem, but they are not always valid. The non-rigid point matching problem, in this sense, still remains unsolved. Motivated by these observations, we feel that there is a need for a new point matching algorithm that can solve for non-rigid mappings as well as the correspondences in the presence of noise and outliers.
Our approach to non-rigid point matching closely follows our earlier work on joint estimation of pose and correspondence using the softassign and deterministic annealing [9], [18], [31]. This work was developed within an optimization framework and resulted in a robust point matching (RPM) algorithm which was restricted to using affine and piecewise-affine mappings. Here, we extend the framework to include spline-based deformations and develop a general purpose non-rigid point matching algorithm. Furthermore, we develop a specific algorithm—TPS–RPM—wherein we adopt the thin-plate spline (TPS) [7], [43] as the non-rigid mapping. The thin-plate spline is chosen because it is the only spline that can be cleanly decomposed into affine and non-affine subspaces while minimizing a bending energy based on the second derivative of the spatial mapping. In this sense, the TPS can be considered to be a natural non-rigid extension of the affine map.
The rest of the paper is organized as follows. A detailed review of related work is presented in the following section. The optimization approach culminating in the TPS–RPM algorithm is developed in Section 3. This is followed by validation experiments using synthetic examples and a preliminary evaluation of the algorithm in the field of brain mapping. We then conclude by pointing out possible extensions of the present work.
Section snippets
Previous work
There are two unknown variables in the point matching problem—the correspondence and the transformation. While solving for either variable without information regarding the other is quite difficult, an interesting fact is that solving for one variable once the other is known is much simpler than solving the original, coupled problem.
A binary linear assignment-least squares energy function
Suppose we have two point-sets V and X (in or in ) consisting of points and , respectively. For the sake of simplicity, we will assume for the moment that the points are in 2D.
We represent the non-rigid transformation by a general function f. A point va is mapped to a new location ua=f(va). The whole transformed point-set V is then U or {ua}. We use a smoothness measure to place appropriate constraints on the mapping. To this end, we introduce an operator L and
The thin-plate spline and the TPS–RPM algorithm
To complete the specification of the non-rigid point matching algorithm, we now discuss a specific form of non-rigid transformation—the thin-plate spline [7], [43]. The generation of a smoothly interpolated spatial mapping with adherence to two sets of landmark points is a general problem in spline theory. Once non-rigidity is allowed, there are an infinite number of ways to map one point-set onto another. The smoothness constraint is necessary because it discourages mappings which are too
A simple 2D example
We noticed that the algorithm demonstrates a very interesting scale-space like behavior. Such behavior can be seen from a simple 2D point matching example demonstrated here in Figs. 2 and 3.
In the beginning, at a very high temperature T, the correspondence M is almost uniform. Then the estimated corresponding point-set {ya=∑i=1Nmaixi}is essentially very close to the center of mass of X. This helps us recover most of the translation needed to align the two point-sets. This can be seen from the
Discussion and conclusions
There are two important free parameters in the new non-rigid point matching algorithm—the regularization parameter λ and the outlier rejection parameter ζ. Below, we discuss ways of reducing the dependence on these free parameters.
Recall that the development of the TPS–RPM algorithm naturally lead to the regularization parameter value essentially being driven by the temperature. In the beginning, at high temperature, the regularization is very high and the algorithm focuses on rigid mappings.
Acknowledgements
We acknowledge support from NSF IIS-0196457. We thank Larry Win, Jim Rambo, Bob Schultz and Jim Duncan for making available the sulcal data used in the brain mapping experiments and Colin Studholme for providing us with his implementation of UMDS. A reference MATLAB implementation of TPS–RPM (with many of the 2D examples used here) is available under the terms of the GNU General Public license (GPL) at http://www.cise.ufl.edu/~anand/students/chui/research.html.
References (47)
Generalized Hough transform to detect arbitrary patterns
IEEE Trans. Pattern Anal. Mach. Intell.
(1981)- et al.
Active shape models: their training and application
Comput. Vision Image Understanding
(1995) - et al.
New algorithms for 2-D and 3-D point matching: pose estimation and correspondence
Pattern Recognition
(1998) - et al.
Automatic labelling of the human cortical surface using sulcal basins
Med. Image Anal.
(2000) - et al.
Feature-based correspondence: an eigenvector approach
Image Vision Comput.
(1992) Object recognition and localization via pose clustering
Comput. Vision Graph. Image Process.
(1987)Aligning pictorial descriptions: an approach to object recognition
Cognition
(1989)- et al.
Graphical templates for model recognition
IEEE Trans. Pattern Anal. Mach. Intell.
(1996) Model-based Image Matching Using Location
(1984)- et al.
Shape matching and object recognition using shape contexts
IEEE Trans. Pattern Anal. Mach. Intell.
(2002)
A method for registration of 3-D shapes
IEEE Trans. Pattern Anal. Mach. Intell.
Matrix analysis
Principal warps: thin-plate splines and the decomposition of deformations
IEEE Trans. Pattern Anal. Mach. Intell.
Geodesic interpolating splines
Registration of cortical anatomical structures via robust 3Dpoint matching
Learning an atlas from unlabeled point-sets
Graph matching with a dual-step EM algorithm
IEEE Trans. Pattern Anal. Mach. Intell.
Rigid, affine and locally affine registration of free-form surfaces
Internat. J. Comput. Vision
Parallel and deterministic algorithms from MRFs: surface reconstruction
IEEE Trans. Pattern Anal. Mach. Intell.
A graduated assignment algorithm for graph matching
IEEE Trans. Pattern Anal. Mach. Intell.
Softassign versus softmax: benchmarks in combinatorial optimization
Object Recognition by Computer: The Role of Geometric Constraints
Cited by (1404)
GO: A two-step generative optimization method for point cloud registration
2024, Computers and Graphics (Pergamon)A robust and interpretable deep learning framework for multi-modal registration via keypoints
2023, Medical Image AnalysisTwo-view correspondence learning using graph neural network with reciprocal neighbor attention
2023, ISPRS Journal of Photogrammetry and Remote SensingA full-body transcription factor expression atlas with completely resolved cell identities in C. elegans
2024, Nature Communications