Point-set registration

In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation (e.g., scaling, rotation and translation) that…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 23 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation (e.g., scaling, rotation and translation) that aligns two point clouds. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model (or coordinate frame), and mapping a new measurement to a known data set to identify features or to estimate its pose.

Raw 3D point cloud data are typically obtained from Lidars and RGB-D cameras. 3D point clouds can also be generated from computer vision algorithms such as triangulation, bundle adjustment, and more recently, monocular image depth estimation using deep learning.

For 2D point set registration used in image processing and feature-based image registration, a point set may be 2D pixel coordinates obtained by feature extraction from an image, for example corner detection. Point cloud registration has extensive applications in autonomous driving, motion estimation and 3D reconstruction, object detection and pose estimation, robotic manipulation, simultaneous localization and mapping (SLAM), panorama stitching, virtual and augmented reality, and medical imaging.…

In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation (e.g., scaling, rotation and translation) that aligns two point clouds. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model (or coordinate frame), and mapping a new measurement to a known data set to identify features or to estimate its pose.

Raw 3D point cloud data are typically obtained from Lidars and RGB-D cameras. 3D point clouds can also be generated from computer vision algorithms such as triangulation, bundle adjustment, and more recently, monocular image depth estimation using deep learning.

For 2D point set registration used in image processing and feature-based image registration, a point set may be 2D pixel coordinates obtained by feature extraction from an image, for example corner detection. Point cloud registration has extensive applications in autonomous driving, motion estimation and 3D reconstruction, object detection and pose estimation, robotic manipulation, simultaneous localization and mapping (SLAM), panorama stitching, virtual and augmented reality, and medical imaging.

As a special case, registration of two point sets that only differ by a 3D rotation (i.e., there is no scaling and translation), is called the Wahba Problem and also related to the orthogonal procrustes problem. Let \lbrace\mathcal{M},\mathcal{S}\rbrace be two finite size point sets in a finite-dimensional real vector space \mathbb{R}^d , which contain M and N points respectively (e.g., d=3 recovers the typical case of when \mathcal{M} and \mathcal{S} are 3D point sets).

The problem is to find a transformation to be applied to the moving "model" point set \mathcal{M} such that the difference (typically defined in the sense of point-wise Euclidean distance) between \mathcal{M} and the static "scene" set \mathcal{S} is minimized. In other words, a mapping from \mathbb{R}^d to \mathbb{R}^d is desired which yields the best alignment between the transformed "model" set and the "scene" set.

The mapping may consist of a rigid or non-rigid transformation. The transformation model may be written as T , using which the transformed, registered model point set is: The output of a point set registration algorithm is therefore the optimal transformation T^\star such that \mathcal{M} is best aligned to \mathcal{S} , according to some defined notion of distance function \operatorname{dist}(\cdot,\cdot) : {{NumBlk|:| T^\star = \arg\min_{T \in \mathcal{T} } \text{dist}(T(\mathcal{M}),\mathcal{S}) | }} where \mathcal{T} is used to denote the set of all possible transformations that the optimization tries to search for.

The most popular choice of the distance function is to take the square of the Euclidean distance for every pair of points: {{NumBlk|:| \operatorname{dist}(T(\mathcal{M}), \mathcal{S}) = \sum_{m \in T(\mathcal{M})} \Vert m - s_m \Vert^2_2, \quad s_m = \arg\min_{s \in \mathcal{S} } \Vert s - m \Vert_2^2 | }} where \| \cdot \|_2 denotes the vector 2-norm, s_m is the corresponding point in set \mathcal{S} that attains the shortest distance to a given point m in set \mathcal{M} after transformation. Minimizing such a function in rigid registration is equivalent to solving a least squares problem.

Types of algorithms

When the correspondences (i.e., s_m \leftrightarrow m ) are given before the optimization, for example, using feature matching techniques, then the optimization only needs to estimate the transformation. This type of registration is called correspondence-based registration.

On the other hand, if the correspondences are unknown, then the optimization is required to jointly find out the correspondences and transformation together. This type of registration is called simultaneous pose and correspondence registration. Correspondence-based methods assume the putative correspondences m \leftrightarrow s_m are given for every point m \in \mathcal{M} .

Therefore, we arrive at a setting where both point sets \mathcal{M} and \mathcal{S} have N points and the correspondences m_i \leftrightarrow s_i,i=1,\dots,N are given. In the simplest case, one can assume that all the correspondences are correct, meaning that the points m_i,s_i \in \mathbb{R}^3 are generated as follows: where l > 0 is a uniform scaling factor (in many cases l=1 is assumed), R \in \text{SO}(3) is a proper 3D rotation matrix ( \text{SO}(d) is the special orthogonal group of degree d ), t \in \mathbb{R}^3 is a 3D translation vector and \epsilon_i \in \mathbb{R}^3 models the unknown additive noise (e.g., Gaussian noise).

Specifically, if the noise \epsilon_i is assumed to follow a zero-mean isotropic Gaussian distribution with standard deviation \sigma_i , i.e., \epsilon_i \sim \mathcal{N}(0,\sigma_i^2 I_3 ) , then the following optimization can be shown to yield the maximum likelihood estimate for the unknown scale, rotation and translation:{{NumBlk|:| l^\star, R^\star, t^\star = \arg\min_{l>0, R \in \text{SO}(3), t \in \mathbb{R}^3} \sum_{i=1}^N \frac{1}{\sigma_i^2} \left\Vert s_i - lRm_i - t \right\Vert_2^2 | }}Note that when the scaling factor is 1 and the translation vector is zero, then the optimization recovers the formulation of the Wahba problem. Despite the non-convexity of the optimization ( ) due to non-convexity of the set \text{SO}(3) , seminal work by Berthold K.P. Horn showed that ( ) actually admits a closed-form solution, by decoupling the estimation of scale, rotation and translation.

Similar results were discovered by Arun et al. In addition, in order to find a unique transformation (l,R,t) , at least N=3 non-collinear points in each point set are required. More recently, Briales and Gonzalez-Jimenez have developed a semidefinite relaxation using Lagrangian duality, for the case where the model set \mathcal{M} contains different 3D primitives such as points, lines and planes (which is the case when the model \mathcal{M} is a 3D mesh).

Interestingly, the semidefinite relaxation is empirically tight, i.e., a certifiably globally optimal solution can be extracted from the solution of the semidefinite relaxation.

M-estimation

M-estimation replaces the least squares objective function in ( ) with a robust cost function that is less sensitive to outliers. Formally, M-estimation seeks to solve the following problem:{{NumBlk|:| l^\star, R^\star, t^\star = \arg\min_{l>0, R \in \text{SO}(3), t \in \mathbb{R}^3} \sum_{i=1}^N \rho\left( \frac{1}{\sigma_i} \left\Vert s_i - lRm_i - t \right\Vert_2 \right) | }}where \rho(\cdot) represents the choice of the robust cost function.

Note that choosing \rho(x) = x^2 recovers the least squares estimation in ( ). Popular robust cost functions include \ell_1 -norm loss, Huber loss, Geman-McClure loss and truncated least squares loss. M-estimation has been one of the most popular paradigms for robust estimation in robotics and computer vision.

Because robust objective functions are typically non-convex (e.g., the truncated least squares loss v.s. the least squares loss), algorithms for solving the non-convex M-estimation are typically based on local optimization, where first an initial guess is provided, following by iterative refinements of the transformation to keep decreasing the objective function. Local optimization tends to work well when the initial guess is close to the global minimum, but it is also prone to get stuck in local minima if provided with poor initialization.

Graduated non-convexity (GNC) is a general-purpose framework for solving non-convex optimization problems without initialization. It has achieved success in early vision and machine learning applications. The key idea behind GNC is to solve the hard non-convex problem by starting from an easy convex problem.

Specifically, for a given robust cost function \rho(\cdot) , one can construct a surrogate function \rho_{\mu}(\cdot) with a hyper-parameter \mu , tuning which can gradually increase the non-convexity of the surrogate function \rho_{\mu}(\cdot) until it converges to the target function \rho(\cdot) . Therefore, at each level of the hyper-parameter \mu , the following optimization is solved:{{NumBlk|:| l_{\mu}^\star, R_{\mu}^\star, t_{\mu}^\star = \arg\min_{l>0, R \in \text{SO}(3), t \in \mathbb{R}^3} \sum_{i=1}^N \rho_{\mu}\left( \frac{1}{\sigma_i} \left\Vert s_i - l Rm_i - t \right\Vert_2 \right) | }}Black and Rangarajan proved that the objective function of each optimization ( ) can be dualized into a sum of weighted least squares and a so-called outlier process function on the weights that determine the confidence of the optimization in each pair of measurements.

Using Black-Rangarajan duality and GNC tailored for the Geman-McClure function, Zhou et al. developed the fast global registration algorithm that is robust against about 80\% outliers in the correspondences. More recently, Yang et al. showed that the joint use of GNC (tailored to the Geman-McClure function and the truncated least squares function) and Black-Rangarajan duality can lead to a general-purpose solver for robust registration problems, including point clouds and mesh registration.

Very recently, Yang et al. has developed the first certifiably robust registration algorithm, named Truncated least squares Estimation And SEmidefinite Relaxation (TEASER). For point cloud registration, TEASER not only outputs an estimate of the transformation, but also quantifies the optimality of the given estimate.

TEASER adopts the following truncated least squares (TLS) estimator:{{NumBlk|:| l^\star, R^\star, t^\star = \arg\min_{l >0, R \in \text{SO}(3), t \in \mathbb{R}^3} \sum_{i=1}^N \min \left( \frac{1}{\sigma_i^2} \left\Vert s_i - l Rm_i - t \right\Vert_2^2, \bar{c}^2 \right) | }}which is obtained by choosing the TLS robust cost function \rho(x) = \min (x^2, \bar{c}^2) , where \bar{c}^2 is a pre-defined constant that determines the maximum allowed residuals to be considered inliers. The TLS objective function has the property that for inlier correspondences ( \Vert s_i - l Rm_i - t \Vert_2^2 / \sigma_i^2 ), the usual least square penalty is applied; while for outlier correspondences ( \Vert s_i - l Rm_i - t \Vert_2^2 / \sigma_i^2 > \bar{c}^2 ), no penalty is applied and the outliers are discarded.

If the TLS optimization ( ) is solved to global optimality, then it is equivalent to running Horn's method on only the inlier correspondences. However, solving ( ) is quite challenging due to its combinatorial nature.

TEASER solves ( ) as follows : (i) It builds invariant measurements such that the estimation of scale, rotation and translation can be decoupled and solved separately, a strategy that is inspired by the original Horn's method; (ii) The same TLS estimation is applied for each of the three sub-problems, where the scale TLS problem can be solved exactly using an algorithm called adaptive voting, the rotation TLS problem can relaxed to a semidefinite program (SDP) where the relaxation is exact in practice, even with large amount of outliers; the translation TLS problem can solved using component-wise adaptive voting. A fast implementation leveraging GNC is open-sourced here.

In practice, TEASER can tolerate more than 99\% outlier correspondences and runs in milliseconds. In addition to developing TEASER, Yang et al. also prove that, under some mild conditions on the point cloud data, TEASER's estimated transformation has bounded errors from the ground-truth transformation. θ := θ 0 while not registered: θ := least_squares(X) return θ Here, the function least_squares performs least squares optimization to minimize the distance in each of the \langle m_i, \hat{s}_i \rangle pairs, using the closed-form solutions by Horn and Arun.

Because the cost function of registration depends on finding the closest point in \mathcal{S} to every point in \mathcal{M} , it can change as the algorithm is running. As such, it is difficult to prove that ICP will in fact converge exactly to the local optimum. In fact, empirically, ICP and EM-ICP do not converge to the local minimum of the cost function.

Nonetheless, because ICP is intuitive to understand and straightforward to implement, it remains the most commonly used point set registration algorithm. Many variants of ICP have been proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy.

For example, the expectation maximization algorithm is applied to the ICP algorithm to form the EM-ICP method, and the Levenberg-Marquardt algorithm is applied to the ICP algorithm to form the LM-ICP method. T(m) = \mathbf{A}m + \mathbf{t} The matrix \mathbf{A} in 2D is composed of four separate parameters \lbrace a, \theta, b, c\rbrace , which are scale, rotation, and the vertical and horizontal shear components respectively.

The cost function is then: subject to \forall j~\sum_{i=1}^M \mu_{ij} \leq 1 , \forall i~\sum_{j=1}^N \mu_{ij} \leq 1 , \forall ij~\mu_{ij} \in \lbrace0, 1\rbrace . The \alpha term biases the objective towards stronger correlation by decreasing the cost if the match matrix has more ones in it.

The function g(\mathbf{A}) serves to regularize the Affine transformation by penalizing large values of the scale and shear components: g(\mathbf{A}(a,\theta, b, c)) = \gamma(a^2 + b^2 + c^2) for some regularization parameter \gamma . The RPM method optimizes the cost function using the Softassign algorithm. The 1D case will be derived here.

Given a set of variables \lbrace Q_j\rbrace where Q_j\in \mathbb{R}^1 . A variable \mu_j is associated with each Q_j such that \sum_{j=1}^J \mu_j = 1 . The goal is to find \mathbf{\mu} that maximizes \sum_{j=1}^J \mu_j Q_j . This can be formulated as a continuous problem by introducing a control parameter \beta > 0 .

In the deterministic annealing method, the control parameter \beta is slowly increased as the algorithm runs. Let \mathbf{\mu} be: {{NumBlk|:| \mu_{\hat{j}} = \frac{\exp{(\beta Q_{\hat{j}})}}{\sum_{j=1}^J \exp{(\beta Q_j)}} | }} this is known as the softmax function. As \beta increases, it approaches a binary value as desired in Equation ( ).

The problem may now be generalized to the 2D case, where instead of maximizing \sum_{j=1}^J \mu_j Q_j , the following is maximized: where Q_{ij} = -(\lVert s_j - \mathbf{t} - \mathbf{A} m_i \rVert^2 - \alpha) = -\frac{\partial \operatorname{cost}}{\partial \mu_{ij}} This is straightforward, except that now the constraints on \mu are doubly stochastic matrix constraints: \forall j~\sum_{i=1}^M \mu_{ij} = 1 and \forall i~\sum_{j=1}^N \mu_{ij} = 1 . As such the denominator from Equation ( ) cannot be expressed for the 2D case simply.

To satisfy the constraints, it is possible to use a result due to Sinkhorn, which states that a doubly stochastic matrix is obtained from any square matrix with all positive entries by the iterative process of alternating row and column normalizations. Thus the algorithm is written as such: while has not converged: // update correspondence parameters by softassign {{nowrap| Q_{ij} := -\frac{\partial \operatorname{cost}}{\partial \mu_{ij}} }} // apply Sinkhorn's method {{nowrap| \hat{\mu}^1_{ij} := \frac{\hat{\mu}^0_{ij}}{\sum_{i=1}^{M+1} \hat{\mu}^0_{ij}} }} {{nowrap| \hat{\mu}^0_{ij} := \frac{\hat{\mu}^1_{ij}}{\sum_{j=1}^{N+1} \hat{\mu}^1_{ij}} }} // update pose parameters by coordinate descent update using analytical solution update using analytical solution update using Newton's method return and where the deterministic annealing control parameter \beta is initially set to \beta_0 and increases by factor \beta_r until it reaches the maximum value \beta_f . The summations in the normalization steps sum to M+1 and N+1 instead of just M and N because the constraints on \mu are inequalities.

As such the M+1 th and N+1 th elements are slack variables. The algorithm can also be extended for point sets in 3D or higher dimensions. The constraints on the correspondence matrix \mathbf{\mu} are the same in the 3D case as in the 2D case.

Hence the structure of the algorithm remains unchanged, with the main difference being how the rotation and translation matrices are solved. {{NumBlk|:| \operatorname{cost}(\mathcal{S}, \mathcal{M}, \theta) = -\sum_{m \in \mathcal{M}} \sum_{s \in \mathcal{S}} KC(s, T(m, \theta)) | }} Some algebraic manipulation yields: The expression is simplified by observing that KC(\mathcal{S}) is independent of \theta . Furthermore, assuming rigid registration, KC(T(\mathcal{M}, \theta)) is invariant when \theta is changed because the Euclidean distance between every pair of points stays the same under rigid transformation.

So the above equation may be rewritten as: The kernel density estimates are defined as: P_{\mathcal{M}}(x, \theta) = \frac{1}{M} \sum_{m \in \mathcal{M}} K(x, T(m, \theta)) P_{\mathcal{S}}(x) = \frac{1}{N} \sum_{s \in \mathcal{S}} K(x, s) The cost function can then be shown to be the correlation of the two kernel density estimates: {{NumBlk|:| \operatorname{cost}(\mathcal{S}, \mathcal{M}, \theta) = -N^2 \int_x P_{\mathcal{M}}\cdot P_{\mathcal{S}} ~ dx | }} Having established the cost function, the algorithm simply uses gradient descent to find the optimal transformation. It is computationally expensive to compute the cost function from scratch on every iteration, so a discrete version of the cost function Equation ( ) is used.

The kernel density estimates P_{\mathcal{M}}, P_{\mathcal{S}} can be evaluated at grid points and stored in a lookup table. Unlike the ICP and related methods, it is not necessary to find the nearest neighbour, which allows the KC algorithm to be comparatively simple in implementation.

Compared to ICP and EM-ICP for noisy 2D and 3D point sets, the KC algorithm is less sensitive to noise and results in correct registration more often. p(s|i) = \frac{1}{(2\pi \sigma^2)^{D/2}} \exp{\left(-\frac{\lVert s - m_i \rVert^2}{2\sigma^2}\right)} The membership probabilities P(i)=\frac{1}{M} is equal for all GMM components. The weight of the uniform distribution is denoted as w\in[0,1] .

The mixture model is then: The GMM centroids are re-parametrized by a set of parameters \theta estimated by maximizing the likelihood. This is equivalent to minimizing the negative log-likelihood function: where it is assumed that the data is independent and identically distributed.

The correspondence probability between two points m_i and s_j is defined as the posterior probability of the GMM centroid given the data point: P(i|s_j) = \frac{P(i)p(s_j|i)}{p(s_j)} The expectation maximization (EM) algorithm is used to find \theta and \sigma^2 . The EM algorithm consists of two steps.

First, in the E-step or estimation step, it guesses the values of parameters ("old" parameter values) and then uses Bayes' theorem to compute the posterior probability distributions P^{\text{old}}(i,s_j) of mixture components. Second, in the M-step or maximization step, the "new" parameter values are then found by minimizing the expectation of the complete negative log-likelihood function, i.e. the cost function: {{NumBlk|:| \operatorname{cost}=-\sum_{j=1}^N \sum_{i=1}^{M+1} P^{\text{old}}(i|s_j) \log(P^{\text{new}}(i) p^{\text{new}}(s_j|i)) | }} Ignoring constants independent of \theta and \sigma , Equation ( ) can be expressed thus: {{NumBlk|:| \operatorname{cost}(\theta, \sigma^2)=\frac{1}{2\sigma^2} \sum_{j=1}^N \sum_{i=1}^{M+1} P^{\text{old}}(i|s_j) \lVert s_j - T(m_i,\theta) \rVert^2 + \frac{N_\mathbf{P}D}{2}\log{\sigma^2} | }} where N_\mathbf{P} = \sum_{j=0}^N \sum_{i=0}^M P^{\text{old}}(i|s_j) \leq N with N=N_\mathbf{P} only if w=0 .

The posterior probabilities of GMM components computed using previous parameter values P^{\text{old}} is: {{NumBlk|:| P^{\text{old}}(i|s_j) = \frac {\exp \left( -\frac{1}{2\sigma^{\text{old}2}} \lVert s_j - T(m_i, \theta^{\text{old}})\rVert^2 \right) } {\sum_{k=1}^{M} \exp \left( -\frac{1}{2\sigma^{\text{old}2}} \lVert s_j - T(m_k, \theta^{\text{old}})\rVert^2 \right) + (2\pi \sigma^2)^\frac{D}{2} \frac{w}{1-w} \frac{M}{N}} | }} Minimizing the cost function in Equation ( ) necessarily decreases the negative log-likelihood function in Equation ( ) unless it is already at a local minimum. Thus, the algorithm can be expressed using the following pseudocode, where the point sets \mathcal{M} and \mathcal{S} are represented as M\times D and N\times D matrices \mathbf{M} and \mathbf{S} respectively: while not registered: // E-step, compute {{nowrap| p_{ij} := \frac {\exp \left( -\frac{1}{2\sigma^2} \lVert s_j - T(m_i, \theta)\rVert^2 \right)} {\sum_{k=1}^{M} \exp \left( -\frac{1}{2\sigma^2} \lVert s_j - T(m_k, \theta)\rVert^2 \right) + (2\pi \sigma^2)^\frac{D}{2} \frac{w}{1-w} \frac{M}{N}} }} // M-step, solve for optimal transformation return θ where the vector \mathbf{1} is a column vector of ones.

The solve function differs by the type of registration performed. For example, in rigid registration, the output is a scale , a rotation matrix \mathbf{R} , and a translation vector \mathbf{t} .

The parameter \theta can be written as a tuple of these: \theta = \lbrace a, \mathbf{R}, \mathbf{t}\rbrace which is initialized to one, the identity matrix, and a column vector of zeroes: \theta_0 = \lbrace 1, \mathbf{I}, \mathbf{0}\rbrace The aligned point set is: T(\mathbf{M}) = a\mathbf{M}\mathbf{R}^T + \mathbf{1}\mathbf{t}^T The solve_rigid function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 20101 paper. {{nowrap| \mu_s:=\frac{1}{N_\mathbf{P}}\mathbf{S}^T\mathbf{P}^T\mathbf{1} }} {{nowrap| \mu_m:=\frac{1}{N_\mathbf{P}}\mathbf{M}^T\mathbf{P}\mathbf{1} }} {{nowrap| \hat{\mathbf{S}}:=\mathbf{S} - \mathbf{1}\mu_s^T }} {{nowrap| \hat{\mathbf{M}}:=\mathbf{M} - \mathbf{1}\mu_m^T }} {{nowrap| \mathbf{A}:=\hat{\mathbf{S}^T}\mathbf{P}^T\hat{\mathbf{M}} }} // diag(ξ)is the diagonal matrix formed from vector ξ {{nowrap| a := \frac{\operatorname{tr}(\mathbf{A}^T\mathbf{R})}{\operatorname{tr}(\mathbf{\hat{\mathbf{M}}^T \operatorname{diag}(\mathbf{P}\mathbf{1})\hat{\mathbf{M}}})} }} // is the trace of a matrix {{nowrap| \sigma^2:=\frac{1}{N_\mathbf{P} D}(\operatorname{tr}(\mathbf{\hat{\mathbf{S}}^T \operatorname{diag}(\mathbf{P}^T\mathbf{1})\hat{\mathbf{S}}})-a\operatorname{tr}(\mathbf{A}^T\mathbf{R})) }} For affine registration, where the goal is to find an affine transformation instead of a rigid one, the output is an affine transformation matrix \mathbf{B} and a translation \mathbf{t} such that the aligned point set is: T(\mathbf{M}) = \mathbf{M}\mathbf{B}^T + \mathbf{1}\mathbf{t}^T The solve_affine function for rigid registration can then be written as follows, with derivation of the algebra explained in Myronenko's 2010 paper. {{nowrap| \mu_s := \frac{1}{N_\mathbf{P}}\mathbf{S}^T\mathbf{P}^T\mathbf{1} }} {{nowrap| \mu_m := \frac{1}{N_\mathbf{P}}\mathbf{M}^T\mathbf{P}\mathbf{1} }} {{nowrap| \hat{\mathbf{S}} := \mathbf{S} - \mathbf{1}\mu_s^T }} {{nowrap| \hat{\mathbf{M}} := \mathbf{M} - \mathbf{1}\mu_m^T }} {{nowrap| \mathbf{B} := (\hat{\mathbf{S} }^T\mathbf{P}^T\hat{\mathbf{M} })(\hat{\mathbf{M} }^T\operatorname{diag}(\mathbf{P}\mathbf{1})\hat{\mathbf{M} })^{-1} }} {{nowrap| \sigma^2 := \frac{1}{N_\mathbf{P} D}(\operatorname{tr}(\hat{\mathbf{S} }^T \operatorname{diag}(\mathbf{P}^T\mathbf{1})\hat{\mathbf{S} })-\operatorname{tr}(\hat{\mathbf{S} }^T\mathbf{P}^T\hat{\mathbf{M} }\mathbf{B}^T)) }} It is also possible to use CPD with non-rigid registration using a parametrization derived using calculus of variations. Sums of Gaussian distributions can be computed in linear time using the fast Gauss transform (FGT).

Consequently, the time complexity of CPD is O(M+N) , which is asymptotically much faster than O(MN) methods. \alpha_m=\frac{1-\exp\left(\lambda\left(3-\frac{1}{\kappa_m}\right)\right)}{1+\exp\left(\lambda\left(3-\frac{1}{\kappa_m}\right)\right)}\alpha_{max} | }} \Sigma_m is the anisotropic covariance matrix of the m-th point in the target set; \mathbf{n}_m is the normal vector corresponding to the same point; \mathbf{I} is an identity matrix, serving as a regularizer, pulling the problem away from ill-posedness. \alpha_m is penalization coefficient (a modified sigmoid function), which is set adaptively to add different levels of point-to-plane penalization depending on how flat the local surface is. This is realized by evaluating the surface variation \kappa_m within the neighborhood of the m-th target point. \alpha_{max} is the upper bound of the penalization.

The point cloud registration is formulated as a maximum likelihood estimation (MLE) problem and solve it with the Expectation-Maximization (EM) algorithm. In the E step, the correspondence computation is recast into simple matrix manipulations and efficiently computed on a GPU.

In the M step, an unconstrained optimization on a matrix Lie group is designed to efficiently update the rigid transformation of the registration. Taking advantage of the local geometric covariances, the method shows a superior performance in accuracy and robustness to noise and outliers, compared with the baseline CPD.

An enhanced runtime performance is expected thanks to the GPU accelerated correspondence calculation. An implementation of the LSG-CPD is open-sourced here.

Reference implementation of thin plate spline robust point matching Reference implementation of kernel correlation point set registration Reference implementation of coherent point drift Reference implementation of ICP variants Reference implementation of Bayesian coherent point drift Reference implementation of LSG-CPD

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374524676 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Point-set registration” revision 1374524676 · retrieved 2026-10-20 date of formation (×1) · confidence 0.95 revision URL