A new point matching algorithm for non-rigid registration

https://doi.org/10.1016/S1077-3142(03)00009-2Get rights and content

Abstract

Feature-based methods for non-rigid registration frequently encounter the correspondence problem. Regardless of whether points, lines, curves or surface parameterizations are used, feature-based non-rigid matching requires us to automatically solve for correspondences between two sets of features. In addition, there could be many features in either set that have no counterparts in the other. This outlier rejection problem further complicates an already difficult correspondence problem. We formulate feature-based non-rigid registration as a non-rigid point matching problem. After a careful review of the problem and an in-depth examination of two types of methods previously designed for rigid robust point matching (RPM), we propose a new general framework for non-rigid point matching. We consider it a general framework because it does not depend on any particular form of spatial mapping. We have also developed an algorithm—the TPS–RPM algorithm—with the thin-plate spline (TPS) as the parameterization of the non-rigid spatial mapping and the softassign for the correspondence. The performance of the TPS–RPM algorithm is demonstrated and validated in a series of carefully designed synthetic experiments. In each of these experiments, an empirical comparison with the popular iterated closest point (ICP) algorithm is also provided. Finally, we apply the algorithm to the problem of non-rigid registration of cortical anatomical structures which is required in brain mapping. While these results are somewhat preliminary, they clearly demonstrate the applicability of our approach to real world tasks involving feature-based 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 R2or in R3) consisting of points {va,a=1,2,…,K} and {xi,i=1,2,…,N}, 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)

  • P.J. Besl et al.

    A method for registration of 3-D shapes

    IEEE Trans. Pattern Anal. Mach. Intell.

    (1992)
  • R. Bhatia

    Matrix analysis

  • F.L. Bookstein

    Principal warps: thin-plate splines and the decomposition of deformations

    IEEE Trans. Pattern Anal. Mach. Intell.

    (1989)
  • V. Camion et al.

    Geodesic interpolating splines

  • H. Chui et al.

    Registration of cortical anatomical structures via robust 3Dpoint matching

  • H. Chui et al.

    Learning an atlas from unlabeled point-sets

  • H. Chui, L. Win, J. Duncan, R. Schultz, A. Rangarajan, A unified non-rigid feature registration method for brain...
  • A.D.J. Cross et al.

    Graph matching with a dual-step EM algorithm

    IEEE Trans. Pattern Anal. Mach. Intell.

    (1998)
  • J. Feldmar et al.

    Rigid, affine and locally affine registration of free-form surfaces

    Internat. J. Comput. Vision

    (1996)
  • D. Geiger et al.

    Parallel and deterministic algorithms from MRFs: surface reconstruction

    IEEE Trans. Pattern Anal. Mach. Intell.

    (1991)
  • S. Gold et al.

    A graduated assignment algorithm for graph matching

    IEEE Trans. Pattern Anal. Mach. Intell.

    (1996)
  • S. Gold et al.

    Softassign versus softmax: benchmarks in combinatorial optimization

  • E. Grimson

    Object Recognition by Computer: The Role of Geometric Constraints

    (1990)
  • Cited by (1404)

    View all citing articles on Scopus
    View full text