PaperlayerView exact revision on arXiv

Source-linked AI summary

Point-Set Registration: Coherent Point Drift

Andriy Myronenko, Xubo Song

arXiv:0905.2635v1cs.CV

TL;DR

Point-set registration must recover correspondences and transformations despite non-rigid deformation, high dimensionality, noise, outliers, and missing points. CPD treats alignment as GMM probability-density estimation, enforcing coherent centroid motion for rigid and non-rigid registration. It reports robust and accurate performance across these degradations and introduces a linear-complexity implementation.

  • Problem

    Point-set registration must recover correspondences and transformations while handling unknown non-rigid transformations, high dimensionality, noise, outliers, and missing points.

  • Method

    CPD fits GMM centroids to data by likelihood maximization, using coherent motion constraints, EM, rigid re-parameterization, and non-rigid displacement-field regularization.

  • Results

    CPD shows robust and accurate performance with respect to noise, outliers, and missing points in tests against LM-ICP and TPS-RPM.

  • Takeaways & Limitations

    CPD provides a registration framework for both rigid and non-rigid transformations, with a fast implementation whose computational complexity can be reduced to linear.

  • Takeaways & Limitations

    With FGT, CPD becomes unstable after aligning to 0.1 degree rotation error as σ2 becomes small and approximation error grows.

Abstract

from arXiv · show

Point set registration is a key component in many computer vision tasks. The goal of point set registration is to assign correspondences between two sets of points and to recover the transformation that maps one point set to the other. Multiple factors, including an unknown non-rigid spatial transformation, large dimensionality of point set, noise and outliers, make the point set registration a challenging problem. We introduce a probabilistic method, called the Coherent Point Drift (CPD) algorithm, for both rigid and non-rigid point set registration. We consider the alignment of two point sets as a probability density estimation problem. We fit the GMM centroids (representing the first point set) to the data (the second point set) by maximizing the likelihood. We force the GMM centroids to move coherently as a group to preserve the topological structure of the point sets. In the rigid case, we impose the coherence constraint by re-parametrization of GMM centroid locations with rigid parameters and derive a closed form solution of the maximization step of the EM algorithm in arbitrary dimensions. In the non-rigid case, we impose the coherence constraint by regularizing the displacement field and using the variational calculus to derive the optimal transformation. We also introduce a fast algorithm that reduces the method computation complexity to linear. We test the CPD algorithm for both rigid and non-rigid transformations in the presence of noise, outliers and missing points, where CPD shows accurate results and outperforms current state-of-the-art methods.

1 INTRODUCTION

Point-set registration supports correspondence and transformation recovery across computer-vision tasks, but must handle complex transformations, dimensionality, and data degradations. CPD addresses these challenges with a robust probabilistic framework for rigid and non-rigid registration.

  • 1 INTRODUCTION: Point-set registration assigns correspondences and recovers the transformation mapping one point set to another.Applications include stereo matching, image retrieval, image registration, and shape recognition.
  • 1 INTRODUCTION: Practical methods must model transformations accurately while remaining computationally tractable and robust to high dimensionality, noise, outliers, and missing points.These degradations can arise from imperfect image acquisition and feature extraction.
  • 1 INTRODUCTION: Rigid transformations allow translation, rotation, and scaling, whereas non-rigid transformations include broader deformations such as affine changes and deformable motion.The underlying non-rigid model is often unknown, making simple piecewise-affine or polynomial approximations inadequate.
  • 1 INTRODUCTION: CPD presents a robust probabilistic registration algorithm for both rigid and non-rigid transformations.The method frames alignment as probability density estimation and fits GMM centroids to data points.

2 PREVIOUS WORK

Earlier registration methods include iterative, probabilistic, spectral, and shape-based approaches, each addressing correspondence or transformation estimation with different assumptions. CPD builds on probabilistic registration while targeting multidimensional rigid and non-rigid settings.

  • 2 PREVIOUS WORK: ICP alternates closest-distance correspondence assignment with least-squares rigid transformation estimation until reaching a local minimum.Its main limitation is the requirement that the initial point sets be adequately close.
  • 2 PREVIOUS WORK: Probabilistic methods replace binary correspondence assignments with soft assignments over point combinations.RPM is a prominent example and connects alternating correspondence and transformation updates to EM.
  • 2 PREVIOUS WORK: Spectral and shape-context methods exploit Gaussian proximity or neighborhood structure, but their performance can degrade for non-rigid or complex transformations.The cited spectral approach performs poorly with non-rigid transformations.
  • 2 PREVIOUS WORK: For rigid registration, the paper identifies the absence of an exact closed-form EM maximization solution for general multidimensional cases as a prior gap.Rotation orthogonality and positive-determinant constraints complicate estimation.
  • 2 PREVIOUS WORK: Prior non-rigid methods include contour-specific GMM models, TPS-based registration, and distance-transform methods suited to relatively simple data.These approaches impose particular parameterizations or data restrictions.
  • 2 PREVIOUS WORK: CPD extends probabilistic registration by regularizing displacement fields, connecting CPD and TPS-RPM as special cases, and reducing computation to linear complexity.The paper also estimates GMM width without deterministic annealing.

3 GENERAL METHODOLOGY

CPD formulates registration as GMM-based probability density estimation and uses EM to estimate transformation parameters and variance. Coherent centroid motion preserves point-set topology while posterior probabilities provide correspondences.

  • 3 GENERAL METHODOLOGY: The first point set is modeled as GMM centroids, while the second is modeled as data generated by the mixture.The transformation T(Y, θ) maps centroid locations using transformation parameters θ.
  • 3 GENERAL METHODOLOGY: CPD obtains correspondences from posterior probabilities of GMM components given each data point.The correspondence probability is P(m|x_n) = P(m)p(x_n|m)/p(x_n).
  • 3 GENERAL METHODOLOGY: Coherent centroid motion preserves the topological structure of the point sets.Rigid and affine cases use explicit re-parameterization, while smooth non-rigid motion uses displacement-field regularization.
  • 3 GENERAL METHODOLOGY: A uniform mixture component accounts for noise and outliers, with equal isotropic covariances and equal membership probabilities for GMM components.The uniform-distribution weight w satisfies 0 ≤ w ≤ 1.
  • 3 GENERAL METHODOLOGY: The framework assumes independently and identically distributed data when defining and optimizing the likelihood.The point-set dimensions and sizes are represented by D, N, and M.
  • 3 GENERAL METHODOLOGY: EM alternates an E-step that computes posterior component probabilities with an M-step that updates θ and σ2 by minimizing the expected complete negative log-likelihood.Iterations continue until convergence, and minimizing Q decreases the negative log-likelihood unless it is already at a local minimum.

4 RIGID & AFFINE POINT SET REGISTRATION

The rigid formulation parameterizes centroids with rotation, translation, and scaling and derives a constrained closed-form rotation update. The affine case is unconstrained and reduces to solving a linear system.

  • 4 RIGID & AFFINE POINT SET REGISTRATION: Rigid CPD transforms each centroid as T(y_m; R,t,s) = sRy_m + t, with R constrained to be a rotation matrix.The constraints are R^T R = I and det(R) = 1.
  • 4 RIGID & AFFINE POINT SET REGISTRATION: The rigid objective generalizes weighted absolute orientation by including weighted differences across all point combinations.The correspondence-weight matrix P supplies the weights.
  • 4 RIGID & AFFINE POINT SET REGISTRATION: SVD yields the optimal multidimensional rotation, after which translation, scale, and σ2 are solved in the M-step.The solution uses R = UCV^T with the determinant correction specified by C.
  • 4 RIGID & AFFINE POINT SET REGISTRATION: The rigid M-step centers the point sets and reduces rotation estimation to maximizing tr(A^T R) under orthogonality and positive-determinant constraints.The matrix A is formed from centered point sets and posterior correspondence weights.
  • 4 RIGID & AFFINE POINT SET REGISTRATION: The rigid algorithm has one free parameter, w, representing the assumed amount of noise in the point sets.The rotation solution is general in D dimensions.
  • 4 RIGID & AFFINE POINT SET REGISTRATION: Affine registration uses T(y_m;B,t) = By_m + t and solves the unconstrained optimization by setting partial derivatives to zero.The resulting linear system determines B, t, and σ2.
  • 4.1 Related Rigid Point set Registration Methods: Compared with related rigid methods, CPD avoids deterministic annealing and provides an exact multidimensional M-step, while some alternatives use approximate minimization.The paper discusses limitations of deterministic annealing and prior approximate objectives.

5 NON-RIGID POINT SET REGISTRATION

CPD treats non-rigid registration as probabilistic alignment with a smooth displacement field, using regularization to preserve coherent motion among points. Variational optimization yields a kernel-based transformation, while Gaussian smoothing controls spatial coherence.

  • Problem: Unknown non-rigid transformations make point-set registration potentially ill-posed, motivating regularization of the displacement field.The paper defines the transformation as the initial position plus displacement v and regularizes its norm to enforce smoothness.
  • Formulation: CPD adds a regularization penalty to the negative log-likelihood and estimates the displacement function using variational calculus.The regularization term is weighted by λ, and the resulting optimal function is expressed through kernel functions.
  • Optimization: The optimal displacement is a linear combination of kernel functions centered at the point set, plus a null-space term.The kernel is a Green’s function of the self-adjoint operator associated with the regularizer.
  • Regularization: A Gaussian regularizer provides a positive-definite kernel and controls the range of filtered frequencies, thereby determining spatial smoothness.The Gaussian choice is also equivalent to the regularization used in Motion Coherence Theory.
  • CPD algorithm: The regularization equivalence with Motion Coherence Theory enforces coherent motion among points, motivating the name Coherent Point Drift.The transformation is represented using kernel coefficients, with transformed positions obtained as T(Y,W)=Y+GW.
  • Algorithm: The non-rigid algorithm uses EM optimization, correspondence probabilities, coefficient updates, and parameterized smoothness and noise controls.Its free parameters are w for assumed noise and λ and β for smoothness regularization.

6 FAST IMPLEMENTATION

CPD accelerates its bottleneck computations with the fast Gauss transform and low-rank kernel approximations, reducing complexity while preserving useful non-rigid structure.

  • Fast Gauss transform: FGT computes bottleneck products P1, P^T1, and PX, reducing Gaussian-sum computation from O(MN) to O(M+N).For dimensions higher than three, the improved fast Gauss transform can be used.
  • Fast Gauss transform: FGT approximates Gaussian matrix-vector products through truncated Hermite expansions, with a truncated Gaussian alternative available when narrow final-iteration Gaussians reduce approximation accuracy.The method switches approximations because small σ^2 requires many Hermite terms for a fixed precision.
  • Low-rank approximation: Low-rank approximation replaces the Gaussian kernel with its leading eigencomponents and reduces the inner matrix inversion to O(K^3), where K ≪ M.Choosing K = M^1/3 largest eigenvalues yields linear computational complexity.
  • Low-rank approximation: The low-rank approximation constrains the non-rigid transformation space and can be accurate with very few eigenvalues for large, well-clustered point sets.The approximation may therefore serve both computational and transformation-regularization roles.

7 RESULTS

Experiments evaluate CPD on rigid and non-rigid point sets under missing data, noise, outliers, and deformation, including comparisons with LM-ICP and TPS-RPM. CPD is reported as robust and accurate, while its accelerated implementations reduce runtime with some accuracy and memory limitations.

  • Rigid registration: CPD registers rigid fish and bunny point sets accurately despite missing points, outliers, noise, large initialization errors, and challenging outlier distributions.The bunny experiments include 50-degree rotation and scaling equal to 2; the fish experiments include missing parts and biased outliers.
  • Rigid registration: CPD outperforms LM-ICP in rigid registration under added noise and outliers, including noise applied separately to either point set.For noise tests, the rotation-matrix error was averaged over 25 independent runs at each noise level.
  • Fast implementation: FGT makes rigid CPD significantly faster, but its approximation becomes unstable after alignment reaches approximately 0.1 degree rotation error.The authors suggest stopping at that accuracy or continuing with ICP or truncated-Gaussian CPD.
  • Non-rigid registration: Non-rigid CPD accurately handles clean fish data, missing points, outliers, 3D face deformations, and left-ventricle contours from ultrasound images.The fish experiments use λ = 2 and β = 2, with w = 0.5 for missing points and outlier cases.
  • Non-rigid registration: CPD outperforms TPS-RPM on non-rigid fish registrations, particularly as outliers increase and for complex deformations.TPS-RPM is also reported to require significantly more iterations and time because of deterministic annealing.
  • Fast implementation: FGT and low-rank approximations provide further speed-ups with moderate accuracy loss, while solving the linear system remains the main computational bottleneck.Without low-rank approximation, the largest 35947 × 3 bunny test could not construct the kernel matrix because of RAM requirements.
  • Fast implementation: A 100-eigenvector approximation for the 1889 × 3 bunny kernel has Frobenius-norm error 10^-8.The eigenspectrum drops below 10^-5 after about 100 eigenvalues.

8 DISCUSSION AND CONCLUSION

CPD provides a probabilistic framework for rigid and non-rigid registration that jointly estimates transformations and correspondences while enforcing coherent motion. Its implementations support multidimensional data, robustness to degradations, and reduced computational complexity.

  • CPD models registration probabilistically by fitting GMM centroids to data and using posterior probabilities as correspondence probabilities.The centroids are fitted by likelihood maximization.
  • Coherent group motion preserves point-set topology and lets CPD estimate transformations and correspondences without assuming a specific non-rigid transformation model.The non-rigid formulation uses a motion-coherence constraint and regularized maximum-likelihood estimation.
  • Rigid CPD has a closed-form multidimensional EM maximization solution, while non-rigid CPD yields an elegant kernel-form solution through variational calculus.Both formulations are applicable to arbitrary-dimensional data sets.
  • Fast Gauss transform and low-rank matrix approximation reduce CPD complexity to as low as linear and improve stability when matrix G is poorly conditioned.The fast implementation is intended to support large data sets.
  • Estimating σ2 within maximum likelihood reduces free parameters and significantly decreases iterations and processing time.The authors report no observed performance decrease compared with deterministic annealing.
  • A uniform noise-and-outlier component with weight w provides flexible robustness control, and experiments show robust, accurate performance with noise, outliers, and missing points.Experiments compare rigid CPD with LM-ICP and non-rigid CPD with TPS-RPM.
Loading 0905.2635v1…