Background

Iterative Most-Likely Point (IMLP) Algorithm

The probabilistic framework of IMLP incorporates a generalized noise model that accounts for anisotropic errors in both the source- and target-point positions. The errors on the measurements of these points are assumed to be independent, zero-mean, multivariate, Gaussian distributed. Thus, treating correspondence as a parameter to be estimated, the likelihood that a transformed source point $(R\overrightarrow{x}+\overrightarrow{t})$ corresponds to a specific target point $\overrightarrow{y}$ is defined as (3) where M_x and M_y are known covariance matrices describing the noise-model distributions of the source point $\overrightarrow{x}$ and target point $\overrightarrow{y}$ , respectively. We refer to (3) as the “match-likelihood function”.

The match-likelihood function establishes the probabilistic foundation for IMLP. In the correspondence phase of the algorithm, a match for each source point is selected from the target shape to maximize the match-likelihood function while considering the transformation parameters R and $\overrightarrow{t}$ as known. In the registration phase of the algorithm, the transformation parameters R and $\overrightarrow{t}$ are then updated to maximize the total likelihood over all matched points while considering the matches as known. It is interesting to note that for the case of uniform, isotropic covariances then maximizing the match-likelihood function reduces to minimizing the square match distances, which is the criteria used by standard ICP. Algorithm 2 provides a summary of the IMLP algorithm, to which we refer back repeatedly in the discussion that follows.

Algorithm 2. Iterative Most-Likely Point (IMLP)

 input: Source shape as point cloud: $X=\left\{{\vec{x}}_i\right\}$

    Target shape: Ψ

    Measurement-error covariances: M_X = {M_Xi}, M_Ψ

    Surface-model covariances: M_SX = {M_Sxi}, M_SΨ

    Initial transformation estimate: $[R_0,{\overrightarrow{t}}_0]$

    Upper bound on match uncertainty: ${\sigma }_{\text{max}}^2$       (default: ∞)

    Chi-square threshold value for outliers: ${\chi }_{\text{thresh}}^2$     (default: 7.81)

 output: Final transformation $[R,\overrightarrow{t}]$ that aligns the shapes X and Ψ

1 Initialize transformation: $[R,\overrightarrow{t}]\leftarrow [R_0,{\overrightarrow{t}}_0]$

2 Initialize noise model: σ² ← 0

3 Compute initial correspondences (Equ. 8):

   $[{\overrightarrow{y}}_i,M_{\text{y}}{}_i,{\text{M}}_{\text{S}}{}_{\text{y}i}]\leftarrow {\text{C}}_{\text{mlp}}({\overrightarrow{x}}_i,\Psi ,I,I,R,\overrightarrow{t},)$

4 Skip to Step 6

5 Compute most-likely correspondences (Equ. 8):

   $[{\overrightarrow{y}}_i,M_{\text{y}}{}_i,M_{\text{S}}{}_{\text{y}i}]\leftarrow {\text{C}}_{\text{mlp}}({\overrightarrow{x}}_i,\Psi ,M_{\text{x}}{}_i+M_{\text{S}}{}_{\text{x}i}+{\sigma }^{2}I,M_{\Psi }+M_{\text{S}\Psi },R,\overrightarrow{t},)$

6 Update the match-uncertainty noise-model term (Equ. 4):

   ${\sigma }^2\leftarrow \min (\frac{1}{N_{\mathrm{\text{inlier}}}}{\sum }_{i\in \mathrm{\text{inliers}}}\Vert {\vec{y}}_i-R{\vec{x}}_i-\vec{t}{\Vert }_2^2,{\sigma }_{\mathrm{\text{max}}}^2)$

7 Identify outliers using a chi-square test (Equ. 6):

   $({\vec{x}}_i,{\vec{y}}_i){\text{is}\text{outlier}\text{if}\text{E}}_{\text{SqrMahalDist}}({\vec{x}}_i,{\vec{y}}_i,M_{\text{x}i},M_{\text{y}i}+{\sigma }^{2}I,R,\vec{t})>{\chi }_{\text{thresh}}^2$

 and update the outlier noise-model terms (Equ. 7):

   $\begin{array}{c}\hfill {\phi }_i=\left\{\begin{array}{cc}9\parallel {\vec{y}}_i-R{\vec{x}}_i-\vec{t}{\parallel }_2^2\hfill & \text{if}({\vec{x}}_i,{\vec{y}}_i)\text{is}\text{an}\text{outlier}\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}\right.\end{array}$

8 Set the noise-model covariances for the registration phase:

   $M_{\mathrm{\text{x}}i}^{*}\leftarrow M_{\mathrm{\text{x}}i}+M_{\mathrm{\text{Sx}}i}+\frac{{\phi }_i}{2}I$, $M_{\mathrm{\text{y}}i}^{*}\leftarrow M_{\mathrm{\text{y}}i}+M_{\mathrm{\text{Sy}}i}+\frac{{\phi }_i}{2}I+{\sigma }^{2}I$

9 Update the transformation to align the corresponding point sets by GTLS (Equ. 20):

   $[R,\vec{t}]\leftarrow \underset{[R,\vec{t}]}{\text{argmin}}{\displaystyle \sum _{i=1}^n}{({\vec{y}}_i-R{\vec{x}}_i-\vec{t})}^T{(R{M}_{\text{x}i}^{*}{R}^T+M_{\text{y}i}^{*})}^{-1}({\vec{y}}_i-R{\vec{x}}_i-\vec{t})$

10 if not converged then goto Step 5

The measurement-error noise models for the source point set and for a corresponding target point set are defined using two sets of covariance matrices M_X = {M_xi} and M_Y = {M_yi}, where M_Y is drawn from a larger set of covariances, M_Ψ, that represents the entire target shape. M_Ψ may be either a superset of covariances or a rule for computing a covariance given any point on the target shape.

In addition to the covariances used to model measurement error, IMLP includes explicit support for a second set of noise-model covariances M_SX = {M_Sxi} and M_SY = {M_Syi}, which are useful for modeling the locally-linear surface patches surrounding each point of a point-cloud shape model. These “surface-model” covariances are added to the measurement-error covariances to obtain the complete noise model for each point. The idea behind the surface-model covariances is to increase the noise-model variance in the surface-parallel directions in order to encourage match errors to be directed along the surface rather than perpendicular to the surface, thereby achieving closer alignment of the underlying surfaces being represented by the point-cloud shape models. This idea forms the basis of the GICP algorithm [11] and was also investigated in [12]. The IMLP algorithm treats the surface-model covariances separately from the measurement-error covariances in order to exclude the surface model from the outlier detection stage, which was found to improve the algorithm’s ability to reject outliers.

As indicated in the algorithm summary, IMLP’s noise model includes additional dynamically computed terms besides the input covariances. The “match-uncertainty” term (σ²) attempts to account for uncertainty in the match process by adding an isotropic variance to the noise model with a magnitude equal to the estimated amount of misalignment between the source and target shapes. In the initial iterations of the algorithm, the residual error between corresponding points is largely due to shape misalignment; thus, the input covariances may not accurately represent the underlying distribution of match errors at first. As the algorithm iterates and the misalignment is reduced, the input covariances are expected to more accurately represent the distribution of match errors. To account for this effect, we follow a similar approach to Estépar et al. [10] and model the match uncertainty as an isotropic noise term having variance equal to the average square residual distance between the corresponding points. However, unlike [10], which includes all match errors in the estimate, we only include match errors from the current set of inliers when computing the match-uncertainty term (4) which has an intuitive appeal and which we found to improve IMLP’s performance with respect to outlier rejection. Note that N_inlier represents the number of matches forming the current set of inliers. A detailed justification of this model for estimating match uncertainty is addressed in [6].

Because the match-uncertainty term is isotropic, it may be added to the noise-model covariances of either the source or target points with the same effect. Since the match uncertainty intuitively affects the choice of correspondences, for the registration phase we choose to add this term to the covariances of the target points in Step 8 of Algorithm 2. However, for the correspondence search phase in Step 5, the match-uncertainty term is added to the covariances of the source points, rather than the target points, because this reduces computation in the correspondence phase. Note that because computing σ² requires having a set of correspondences in-hand, a fully isotropic noise model is used for the initialization of correspondences in Step 3.

The match-uncertainty term described above has importance for the chi-square outlier detection test in Step 7 of Algorithm 2. The match-uncertainty term enables the algorithm to converge robustly and quickly in the case of large initial misalignment by accounting for this misalignment in the noise model and preventing an overabundance of matches from being flagged as outliers based on the measurement-error covariances alone. In the case of registering a source and target shape having only partial overlap, it could happen that the average square match distance remains large even at the properly registered alignment. In this case, it may be desirable to prevent the match-uncertainty term from growing too large. To address this issue, we define a maximum threshold (${\sigma }_{\mathrm{\text{max}}}^2$) on the match uncertainty as an optional input to the IMLP algorithm. If no value is specified by the user, then the maximum threshold is disabled by setting it to a very large value.

Robustness to outliers is enabled via a chi-square test, which is used to identify outlier matches in Step 7 of Algorithm 2. Under an assumption of correspondence and of generalized Gaussian noise, the square Mahalanobis distance between matched points in 3D space is distributed as the sum of squares of three independent normalized Gaussian distributions, each representing a distribution along a different eigenvector of the noise-model covariance matrix. Thus, under the stated assumptions, the square Mahalanobis match distance has a chi-square distribution with three degrees of freedom [33]. Outliers are therefore detected by comparing each square Mahalanobis match distance (5) to the value of the inverse cumulative density function (CDF) of a chi-square distribution with three degrees of freedom evaluated at some probability p. If a square Mahalanobis match distance exceeds this chi-square inverse CDF value (${\chi }_{\mathrm{\text{thresh}}}^2$) then that match is considered an outlier. Thus, a matched point-pair, $(\overrightarrow{x},\overrightarrow{y})$, with corresponding noise covariances, M_x and M_y, is an outlier if (6) where chi2inv(p, 3) is the chi-square inverse CDF function with three degrees of freedom evaluated at probability p. The chi-square inverse CDF threshold (${\chi }_{\mathrm{\text{thresh}}}^2$) is specified as an optional input parameter to the IMLP algorithm, which enables the user to adapt the algorithm to different percentages of outliers present in the shape data. Setting this threshold to a very large value effectively disables outlier detection. Disabling outlier detection in this manner may be useful in cases where the data is known to be free from outliers or possibly cases where a large initial misalignment is present, although the match-uncertainty term (σ²) already functions as an automatic mechanism to account for large initial misalignment. When no chi-square inverse CDF threshold is specified by the user, the default threshold of 7.81 is used, which corresponds to a chi-square inverse CDF probability of p = 0.95.

To reduce the influence of outliers on the computed registration, a set of outlier noise-model terms ({φ_i}) are used to bring additional isotropic variance into the noise models of the matches identified to be outliers. The effect of this added variance is to reduce the influence of the outliers in the registration phase [10], which occurs at Step 9 in Algorithm 2. If a match is determined to be an outlier then the outlier noise term, φ_i, corresponding to that match is set equal to the square Euclidean distance between the matched points times some factor; otherwise, the outlier term is set to zero (7). (7)

While we have used the factor 9 in our implementation (which brings the outlier match errors within approximately 1/3 standard deviation relative to their noise models), this factor could be reduced or increased to give respectively more or less weight to the outliers if desired.

Alternatively, to completely remove all outlier influence from the registration phase, any matches identified as outliers could be simply removed from the set of matches used to compute the registration in Step 9 of Algorithm 2. This strategy is preferred for cases such as registering shapes having only partial overlap, since the systematic tug from the large body of non-overlapping points could then be significant enough to affect the final accuracy of the registration. For small to moderate percentages of random outliers, our experience has been that inflating the variance works just as well as disregarding the matches entirely.

In our implementation of IMLP, we terminate the algorithm when the magnitudes of change in the transformation parameters R and $\overrightarrow{t}$ remain below some termination threshold values for two consecutive iterations or when a maximum number of iterations has been reached. For translation $(\overrightarrow{t})$, the magnitude of change is simply computed as the norm of the change in the translation vector. For rotation (R), the Rodrigues form for the change in rotation is computed [34] and the angular component (the norm of the Rodrigues vector) is extracted as the magnitude of angular change. The threshold values used in the studies reported for this paper were 0.001 degrees rotation and 0.001 millimeters translation. We note that alternative termination criteria could also be used as substitute for our own.

Due to modifying the underlying noise models during each iteration, the IMLP algorithm cannot be guaranteed to converge. A similar scenario is encountered for many related ICP-based methods, with an in-depth discussion being found in [4]. Because of the possibility for non-convergence, we have added cycling detection as a further termination condition for IMLP. Cycling is detected by monitoring the value of the cost function being minimized within the registration phase. If the minimal cost computed by the registration phase increases twice within a period of four iterations and if the cost following the second increase is within a small tolerance of the cost following the first increase, then a cycle has been detected. In such cases, the algorithm terminates and returns the registration corresponding to the last iteration in which the cost function decreased. This termination condition is primarily a precaution to ensure computational efficiency, as a cycling condition would terminate at the maximum iteration count in any case.

Concerning IMLP’s ability to converge to the correct global solution, we note that, like other ICP-based methods, it is important to begin the registration close enough to the optimal solution in order to prevent converging to an incorrect solution created by local minima.

IMLP Correspondence Phase: An Efficient PD-Tree Search Strategy for Computing Most-Likely Correspondences

In this subsection we describe our approach to efficiently compute the most-likely matches from the target shape, being those matches that maximize the match-likelihood function previously defined in (3) as indicated by the most-likely-point operator (8)

Maximizing the match-likelihood function of (3) simplifies to minimizing the “match-error function” (9)

It is important to not disregard the log term within the match-error function when computing the most-likely match, since the noise-model covariances may vary substantially over the target shape in general. Note that both the magnitude of the target covariances (i.e. the eigenvalues) and the orientation of the target covariances (i.e. the directions of the eigenvectors) may significantly alter the value of the log term. Thus, even if the covariance magnitude is fixed for all target noise models, the log term still has an impact for anisotropic distributions that have different orientations at different points on the target surface. If both the magnitudes and orientations of the noise-model covariances are constant across the entire target shape, then minimizing the match-error function reduces to that of minimizing the square Mahalanobis distance term in (9).

Algorithms 3 and 4 provide a summary of our efficient strategy for computing the most-likely correspondences. Note that in order to simplify the expressions in the summary we represent the noise-model of a target point by the single covariance M_y. However, as previously noted, for the IMLP algorithm a target-point noise model is actually represented by two covariances, M_y and M_Sy, in order to distinguish between components for the measurement error and for the local surface model. For the purposes of this subsection, no distinction between the noise-model components is required, and we will consider M_y to represent the total noise-model of a target point, i.e. (M_y + M_Sy) as defined in the algorithm summary for IMLP. In an actual implementation having both types of noise-model components defined over the target shape, each type of covariance would be stored and returned separately along with the most-likely match.

Algorithm 3. PD-Tree Search for Most-Likely Correspondence

 input: Source point: $\overrightarrow{x}$

   Source-point noise model: M_x

   PD tree containing target shape (Ψ) and target noise model (M_Ψ): T

   Current transformation: $[R,\overrightarrow{t}]$

   Prior most-likely match for this source point: $({\overrightarrow{y}}_{\text{pre}},M_{\text{y}\_\text{pre}})$

 output: Most-likely match and its corresponding noise model: $(\overrightarrow{y},M_{\text{y}})$

1 Initialize most-likely match to the prior match:

   $[\overrightarrow{\text{y}},{\text{M}}_{\text{y}},E_{\text{best}}]\leftarrow [{\overrightarrow{y}}_{\text{prev}},M_{\text{y}\_\text{prev}},E_{\text{match}}(\overrightarrow{x},{\overrightarrow{y}}_{\text{prev}},M_{\text{x}},M_{\text{y}\_\text{prev}},R,\overrightarrow{t})]$

2 Search for more-likely match in the left child of the PD-tree root node:

   $[{\overrightarrow{\text{y}}}_{\text{LChild}},M_{\text{y}\_\text{LChild}},E_{\text{LChild}}]\leftarrow \text{NodeSearch}(T.Root.LChild,{\text{E}}_{\text{best}},\overrightarrow{x},M_{\text{x}},R,\overrightarrow{t})$

3 if E_LChild < E_best then update most-likely match:

   $[\overrightarrow{y},M_{\text{y}},E_{\text{best}}]\leftarrow [{\overrightarrow{y}}_{\text{LChild}},M_{\text{y}\_\text{LChild}},E_{\text{LChild}}]$

4 Search for more-likely match in the right child of the PD-tree root node:

   $[{\overrightarrow{\text{y}}}_{\text{RChild}},M_{\text{y}\_\text{RChild}},E_{\text{RChild}}]\leftarrow \text{NodeSearch}(T.Root.RChild,{\text{E}}_{\text{best}},\overrightarrow{x},M_{\text{y}\_\text{RChild}},R,\overrightarrow{t})$

5 if E_RChild < E_best then update most-likely match:

   $[\overrightarrow{y},M_{\text{y}},E_{\text{best}}]\leftarrow [{\overrightarrow{y}}_{\text{RChild}},M_{\text{y\_RChild}},E_{\text{RChild}}]$

Our search strategy for computing the most-likely correspondences is based on a modified PD tree formed around the target shape. The distinguishing element of a PD-tree data structure, in comparison to the standard KD-tree data structure, is that each node of the tree has its own unconstrained local coordinate system rather than requiring the local coordinate frame of each node to be axis-aligned with a common global coordinate system.

A node of the PD-tree is constructed by first computing the covariance of the positions of all datums assigned to the node. A datum is defined to be one of the smallest principle elements comprising the target shape, such as a point from a point cloud or a triangle from a mesh. After the covariance of datum positions is computed, the local coordinate system of the node is defined by aligning the coordinate axes of the node with the eigenvectors of the covariance matrix and positioning the node origin at the mean datum position. It is customary to align the x-axis along the direction of greatest variance (i.e. along the eigenvector associated with the largest eigenvalue). Finally, a bounding box of minimal size is constructed that is axis-aligned with the local coordinate system of the node and that fully contains all datums within the node. The node is then split along the local x-axis (along the direction of greatest variance) in order to form the left and right child nodes, and the process continues down the tree until either the number of datums within the node or the size of the node’s bounding box falls below a threshold value. To begin this process, the root node of the PD tree is formed by assigning to it all datums comprising the entire target shape.

Algorithm 4. NodeSearch Function for the PD-Tree Search

 input: Node of PD tree being search: 𝓝

   Source point: $\overrightarrow{x}$

   Source-point noise model: M_x

   Current transformation: $[R,\overrightarrow{t]}$

   Current best match error: E_best

 output: Best match within node: ${\overrightarrow{y}}_{\text{node}}$

   Noise model of best match within node: M_{y_node}

   Updated best match error: E_node

1 Initialize the best match within this node:

   $[E_{\text{node}},{\overrightarrow{y}}_{\text{node}},M_{\text{y\_node}}]\leftarrow [E_{\text{best}},0,0]$

2 Compute an ellipsoid bound (𝓔) centered at the transformed source point $(R\overrightarrow{x}+\overrightarrow{t})$ within which candidates for a better match may be found:

   $𝓔=\left\{\overrightarrow{z}\right|{(\overrightarrow{z}-R\overrightarrow{x}-\overrightarrow{t})}^T{(M_{\text{sub}})}^{-1}(\overrightarrow{z}-R\overrightarrow{x}-\overrightarrow{t})\le E_{\text{best}}-lo{g}_{\text{min}}\}$

   See Equations (13) and (14, 15, or 17)

3 if 𝓔 intersects 𝓝.OBB then

4   if 𝒩 is a leaf node then

5    foreach datum_i ∈ 𝒩 do

6      Compute the most-likely match on datum_i to get:

        $[{\overrightarrow{y}}_{\text{datum}},M_{\text{y\_datum}},E_{\text{datum}}]$ (S1 Appendix)

7      if E_datum < E_node then update best match in node:

        $[{\overrightarrow{y}}_{node},M_{\text{y\_node}},E_{\text{node}}]\leftarrow [{\overrightarrow{y}}_{\text{datum}},M_{\text{y\_datum}},E_{\text{datum}}]$

8    end

9   else

10    Search left child node:

      $[{\overrightarrow{y}}_{\text{LChild}},M_{\text{y\_LChild}},E_{\text{LChild}}]\leftarrow \text{NodeSearch}\text{(}𝓝.LChild,E_{\text{node}},\overrightarrow{x},M_{\text{x}},R,\overrightarrow{t})$

11    if E_LChild < E_node then update the most-likely match for this node:

      $[{\overrightarrow{y}}_{\text{node}},M_{\text{y\_node}},E_{\text{node}}]\leftarrow [{\overrightarrow{y}}_{\text{LChild}},M_{\text{y\_LChild}},E_{\text{LChild}}]$

12    Search right child node:

      $[{\overrightarrow{y}}_{\text{RChild}},M_{\text{y\_RChild}},E_{\text{RChild}}]\leftarrow \text{NodeSearch}\text{(}𝓝.RChild,E_{\text{node}},\overrightarrow{x},M_{\text{x}},R,\overrightarrow{t})$

13    if E_RChild < E_node then update most-likely match for this node:

      $[{\overrightarrow{y}}_{\text{node}},M_{\text{y\_node}},E_{\text{node}}]\leftarrow [{\overrightarrow{y}}_{\text{RChild}},M_{\text{y\_RChild}},E_{\text{RChild}}]$

14   end

15 end

 Node Object Parameters:

  Datums and corresponding noise-model covariances in this node: {datum_i, M_yi}

  Oriented bounding box bounding all datums in this node: OBB

  Node noise model used to form a lower bound on match errors within this node:

    {λ_{node_min, i}} and either M_node or λ_{node_max}

    (depends on the bounding method chosen in Step 2 of NodeSearch)

To illustrate the process of computing a most-likely match, suppose that we are given a source point $\overrightarrow{x}$ having noise covariance M_x and that we are given a current candidate for the most-likely match on the target shape having match error E_best. The search for the most-likely correspondence begins at the root node of the PD tree and progressively makes it way down the tree until reaching the leaf nodes. Whenever a leaf node is encountered then match errors are computed for every datum within the leaf node and the current candidate for most-likely match is updated whenever a match error smaller than E_best is found. When the search that began at the root node is complete then the final candidate for most-likely match will be the most-likely match.

In order to perform the PD-tree search efficiently, the problem to consider before searching deeper within a given node is whether or not it is possible for a target point located anywhere within the node boundary to produce a match error that is lower than the current best match error, E_best. If a lower match error is not possible within the bounds of the node, then that node and all nodes below it may be safely skipped. Consider testing a match for which all inputs of the match-error equation (9) are known, except the position of the target point $\overrightarrow{y}$. Our goal then is to determine whether any point located within the node bounds can produce a match error less than E_best. Introducing this inequality into (9) and shifting the log term to the opposite side defines the equation of an ellipsoid centered at the position of the transformed source point $(R\overrightarrow{x}+\overrightarrow{t})$ as given by (10)

Any target point $\overrightarrow{y}$ that produces a match error lower than E_best will be located within this ellipsoid boundary. The task now is to determine whether the ellipsoid so defined intersects the oriented bounding box (OBB) of the node. If intersection exists, then it is possible that the node may contain a better match. If intersection does not exist, then the given node and all nodes below it cannot contain a better match and may be skipped in the continuing search. To compute the ellipsoid-OBB intersection test, we employ the efficient method described in [35].

The problem of bounding the match error of a node is actually more complicated than indicated above, because different points on the target shape may have different noise-model covariances. Thus, the covariance M_y is not static within a node. To address this issue, a substitute (M_sub) for the match covariance (RM_x R^T + M_y) is required that produces a lower bound on the match error for any target point within the node relative to the match error obtained when using the target point’s true noise-model covariance. In other words, the ellipsoid bound that results from applying the substitute covariance M_sub in (10) must fully contain all ellipsoid bounds that result from using any covariance in the set {(RM_x R^T + M_yi)} for all {M_yi} represented within the node. Note that the covariance expression (RM_x R^T + M_y) appears twice in (10), within both a log and a square Mahalanobis-distance term. In the discussion that follows, we will consider independent replacements for the covariance expressions within each term.

IMLP Registration Phase: Aligning Corresponding Point Sets by Generalized Total Least Squares

In this section, we present our approach for computing the rigid-body alignment of two corresponding point sets such that the total match likelihood is maximized as defined by (18) where the match-likelihood function for a single match (L_match) was previously defined in (3). Maximizing the total match likelihood is equivalent to minimizing the total match error defined as (19)

Unlike in the correspondence phase, the covariance matrices of the target points {M_yi} are now fixed. Although the value of the log term may still be affected by a change in rotation, the impact of rotation on the square Mahalanobis-distance term is far more pronounced. Thus, we may disregard the log term in this phase, which simplifies the optimization considerably to that of minimizing a sum of square Mahalanobis distances (20) which has the form of a nonlinear generalized total-least-squares problem. This optimization is the same GTLS problem for registering corresponding point sets as found in prior ICP-based algorithms involving anisotropic noise models [10–12]. As mentioned in the introduction, methods of solution for this type of problem follow an iterative approach.

To derive our approach, we first express the problem in alternate form. It can be shown (S2 Appendix) that the unconstrained optimization of (20) is equivalent to the following constrained optimization (21) where $\{{\vec{x}}_i^{*}\}$ and $\{{\vec{y}}_i^{*}\}$ represent the optimizer’s estimates of the unknown, noise-free positions of the source and target point-pairs, which, due to the correspondence assumption, are constrained to have perfect alignment. Thus, our goal is to solve the transformation parameters, R and $\overrightarrow{t}$, that minimize (21) subject to a perfect alignment constraint on the unknown, noise-free point positions. The derivation of our strategy was particularly aided by the works of [38, 39] regarding the topic of total-least-squares estimation.

The first step in the derivation is to re-express the constraints of (21) as (22) and then to linearize these constraints using a first-order Taylor-series expansion centered at the known values ${\overrightarrow{y}}_i$, ${\overrightarrow{x}}_i$, R₀, and ${\overrightarrow{t}}_0$, where R₀ and ${\overrightarrow{t}}_0$ are initial estimates of the transformation. Note that we define R_k and ${\overrightarrow{t}}_k$ to be the estimates of the transformation parameters that are computed at each iteration k. Performing a linearization of the rotation matrix leads to the skew approximation form for an incremental rotation as defined by (23) (24)

This parameterization enables representing small-angle rotations as a 3D vector, $\Delta \overrightarrow{\alpha }={[\Delta {\alpha }_{\text{x}},\Delta {\alpha }_{\text{y}},\Delta {\alpha }_{\text{z}}]}^T$. We also note that using Lie algebra and exponential maps to parameterization the rotation, rather than the skew-approximation form described here, may also be a very effective approach for solving this problem. Note that skew$(\overrightarrow{x})\overrightarrow{y}$ is simply matrix notation for the cross product $(\overrightarrow{x}\times \overrightarrow{y})$; thus, the positions of $\overrightarrow{x}$ and $\overrightarrow{y}$ may be interchanged by negation, which is implicitly used in forming the Taylor-series expansion of the constraint equations below. Using $\Delta \overrightarrow{\alpha }$ to represent change in rotation and defining $\Delta \overrightarrow{t}$ to be change in translation, with some algebraic manipulation the constraints of (22) may be linearized to the approximate form (25) which is linear with respect to change in rotation $\Delta \overrightarrow{\alpha }$ and change in translation $\Delta \overrightarrow{t}$. Here we define ${\mathrm{\text{F}}}_i^0({\vec{x}}_i,{\vec{y}}_i,R_k,{\vec{t}}_k)={\vec{y}}_i-R_k{\vec{x}}_i-{\vec{t}}_k$, $r_{\mathrm{\text{y}}i}={\vec{y}}_i-{\vec{y}}_i^{*}$, $r_{\mathrm{\text{x}}i}={\vec{x}}_i-{\vec{x}}_i^{*}$, $R_{k+1}=(\Delta R)R_k\approx (I+\text{skew(}\Delta \overrightarrow{\alpha }))R_k$, and ${\overrightarrow{t}}_{k+1}={\overrightarrow{t}}_k+\Delta \overrightarrow{t}$, where k denotes an iteration of the optimization procedure.

The next step in the derivation is to apply the method of Lagrange multipliers to enforce the linearized constraints while minimizing the cost function. The Lagrange function becomes (26) where λ = {λ_i} represents the set of Lagrange multipliers with each λ_i being a 3-vector. Next is solving for the zero derivatives of the Lagrange function with respect to the residuals {r_xi} and {r_yi}, the change in transformation parameters $\Delta \overrightarrow{\alpha }$ and $\Delta \overrightarrow{t}$, and the Lagrange multipliers. After making substitutions between these differential equations, we finally obtain (27) for computing an incremental update of the transformation parameters $\Delta p={[\Delta \overrightarrow{\alpha },\Delta \overrightarrow{t}]}^T$. (27)

Here F⁰ is defined as a stacked vector of match residuals, J is the Jacobian matrix of the constraints relative to the transformation parameters, and M is the complete covariance matrix for all matches. Since the match errors are assumed to be independent between matches, M has a 3 x 3 symmetric, positive-definite, block-diagonal structure for points in 3D. Simplifying this solution for registrations in 2D is trivial.

The resulting expression in (27) is a linear system of six equations having the recognizable form Ax = b, where A is 6 x 6 symmetric. This expression is further recognized to have the form of an update equation from the nonlinear Gauss-Newton method of nonlinear optimization. The solution to (21) is computed by iteratively solving (27) using standard least squares, with each solution providing an incremental update (Δp) for the current transformation parameter estimates R_k and ${\overrightarrow{t}}_k$, which are updated as (28) where $R(\Delta \overrightarrow{\alpha })$ is as defined in the following paragraph. The linear system of (27) is re-solved following each update until the transformation estimates converge. This approach is nearly equivalent to the standard Gauss-Newton method, with a modification being that the covariance matrices are updated at each iteration.

In (28) we define $R(\Delta \overrightarrow{\alpha })$ to be a rotation matrix computed using the Rodrigues rotation formula [34] about an axis oriented along $\Delta \overrightarrow{\alpha }$ and having a rotation angle of $\left|\right|\Delta \overrightarrow{\alpha }\left|\right|$ radians. Using the Rodrigues form $R(\Delta \overrightarrow{\alpha })$ rather than the skew approximation form $(I+\text{skew(}\Delta \overrightarrow{\alpha }))$ ensures that R_k+1 always satisfies the conditions for being a valid rotation matrix.

Since the linear system of (27) is symmetric, an efficient and stable approach for solving the least-squares iterates is to use Cholesky or LDL^T decomposition. In our implementation we employ the more general SVD decomposition, since the symmetric decompositions were not supported by the numerical libraries used in our implementation. Because the linear system is small, SVD also provides reasonable efficiency. Note that, in the interest of efficiency, it is important to take advantage of the sparse structure of M when computing the matrix operations required to form this linear system.

We define the termination condition to be when the magnitude of incremental change in the transformation parameters fall below threshold values. In our implementation, we use convergence thresholds of 0.001 mm translation and 0.001 degrees rotation, but this may be defined by the user.

A summary of the approach described above for solving the GTLS problem of aligning two corresponding point sets is provided below as Algorithm 5.

Algorithm 5. GTLS Registration of Corresponding Point Sets

 input: Corresponding source and target point sets: $X=\left\{{\vec{x}}_i\right\},Y=\left\{{\vec{y}}_i\right\}$

    Noise-model covariances for the source and target points:

      M_x = {M_xi, M_Y = {M_yi}

    Initial transformation estimate: $[R_0,{\vec{t}}_0]$

 output: Final transformation that aligns the corresponding point sets: $[R,\vec{t}]$

1 Initialize the transformation: $[R_k,{\vec{t}}_k]\leftarrow [R_0,{\vec{t}}_0]$

2 Compute F⁰ using X, Y, R_k, and ${\vec{t}}_k$

3 Compute J using R_k and X

4 Solve incremental transformation $\Delta p={[\Delta \vec{\alpha },\Delta \vec{t}]}^T$ by standard least squares (27)

5 Update the transformation parameters: $[R_k,{\vec{t}}_k]\leftarrow [\text{R}(\Delta \vec{\alpha })R_k,{\vec{t}}_k+\Delta \vec{t}]$

6 if $\Vert \Delta \vec{\alpha }\Vert \le \Delta {\alpha }_{\text{threshold}}\mathit{and}\Vert \Delta \vec{t}\Vert \le \Delta t_{threshold}$ then

7  Goto Step 2

8 end

9 Return the final transformation: $[R,\vec{t}]\leftarrow [R_k,{\vec{t}}_k]$

Experiment 1: Generalized Total-Least-Squares Methods for Registering Corresponding Point Sets

In this study, we evaluate the proposed Gauss-Newton-based approach for computing the optimal rigid-body alignment that registers two corresponding point sets under anisotropic measurement error, which was described in the IMLP Registration Phase subsection of the Methods section. As previously stated, this problem forms a GTLS optimization problem that must be solved in the registration phases of the IMLP algorithm and of closely related prior works. We evaluate the proposed GTLS method on the basis of efficiency, accuracy, and stability relative to the prior methods proposed for solving this problem by Estepar et al. [10] and Balachandran and Fitzpatrick [31]. These results are also compared to the closed-form, least-squares solution for the isotropic noise case [26], which constitutes the registration phase of the standard ICP algorithm.

Each method was evaluated using a Matlab-based implementation. For the method of Balachandran and Fitzpatrick, we use the Matlab source code included in their paper [31]. For the other methods we have created our own Matlab implementations, including an implementation of the rotation estimation method of Ohta and Kanatani [28], which is a sub-component of the method by Estepar et al.

A high degree of instability was initially encountered when using the method of Estepar et al. with large translational offsets. We found that a small modification sufficed to fix the issue, which involved applying their translation estimate prior to the first estimate for rotation. This modification was used throughout our study.

As previously noted, one limitation of the method by Balachandran and Fitzpatrick is that this method employs a single noise covariance that remains fixed as the algorithm iterates, due to the assumption of anisotropic noise in only one point set. Although noise in both point sets may be initially considered by combining the noise models to form a single covariance prior to calling their method (as in the covariance expressions of (9) for example), in this case the accuracy of the method still diminishes relative to the magnitude of rotational misalignment because the effective noise covariance is not updated as the method iterates.

Because of this limitation, we conduct a two-part study. The first study (Experiment 1A) investigates anisotropic noise present in both the source and target point sets. The second study (Experiment 1B) investigates anisotropic noise present in only the target point set with isotropic noise present in the source point set. For the second study, the assumption of a fixed effective covariance becomes correct, since a change in the orientation of the source points has no impact. We have included the method of Balachandran and Fitzpatrick in the evaluation of both studies, while computing an effective noise covariance as described in the foregoing paragraph.

The method of Balachandran and Fitzpatrick specifies initializing the anisotropic registration with the isotropic-noise solution before optimizing with respect to the GTLS cost function. We have performed a portion of the experiments both with and without isotropic initialization applied prior to each GTLS method. In order to better investigate the merit of the numerical machinery behind each GTLS approach, isotropic initialization was not used in Experiment 1A. In order to investigate the impact of initialization on each GTLS method, experiments were conducted both with and without isotropic initialization in Experiment 1B.

In order to compare all methods on level ground, several concerns had to be addressed. The first concern regards the termination criteria used by each method, which was defined (or modified) to be when the magnitude of change in the estimated transformation parameters falls below 0.0001 mm and 0.0001 degrees or when the number of iterations exceeds 60. For the method of Estepar et al., a maximum iteration threshold of 20 was applied to the inner loop (i.e. to the rotation estimation component employing the method of Ohta and Kanatani) while the full outer loop was assigned the same maximum iteration threshold as the other GTLS methods. In practice, we found that these maximum iteration thresholds were only reached under the condition of instability; thus, the iteration threshold was also used to automatically detect and count the occurrence of instability for each method.

The next concern regards the form of input afforded to each method. Every GTLS method compared requires some form of decomposition to be performed on the covariance matrices that define the anisotropic noise model, and these decompositions differ between the methods. To provide equal treatment, we use the noise covariances as base-line input for each GTLS method. Since the implementation by Balachandran and Fitzpatrick was programmed to use pre-computed decompositions (i.e. the inverse square root) of the covariance matrices as input, we have added the required calculation to their method and changed the input to use the covariance matrices directly.

Another concern affecting runtime performance regards the style of Matlab coding. To obtain the best possible runtime performance from each method, all matrix operations were fully vectorized in Matlab code, with the only exception being that a loop over the number of points-pairs was required in order to compute the inverse square root of the covariance matrices for the method of Balachandran and Fitzpatrick, as no solution was identified to fully vectorize this operation across all point-pairs. We have normalized for the runtime impact of this loop in Experiment 1B, which compares the method of Balachandran and Fitzpatrick on its own turf (i.e. with anisotropic noise in only one point set), by using a loop to compute the covariance decompositions required by the other GTLS methods as well. This loop-normalization was not performed for Experiment 1A, however, as the runtime comparison with Balachandran and Fitzpatrick is already largely incongruent for that study due to their assumption of a fixed covariance (i.e. anisotropic noise in only one point set), whereas the other GTLS methods re-compute the covariance decompositions in every iteration. Another reason that fully vectorized implementations are used in Experiment 1A is in order to assess the full potential of the other methods.

As a final leveling of the playing field, a runtime normalization was applied in Experiment 1B for the assumption of a fixed covariance (i.e. anisotropic noise in only one point set). This was accomplished by creating variants of the implementations of the proposed Gauss-Newton-based method and of the method by Estepar et al. that assume, like the method of Balachandran and Fitzpatrick, that the effective noise covariance remains fixed for any orientation of the source point set. This test therefore provides a reasonable relative comparison of the runtimes that can be expected from each of the various GTLS optimization schemes.

Experiments for the various studies comprising Experiment 1 were conducted by first generating two noisy point sets with known correspondence and known ground-truth alignment, second applying a random misalignment between the point sets, and third registering the point sets using each registration method. To form a pair of corresponding point sets, a set of 50 points was randomly generated being uniformly distributed within the interval [-100, 100] mm along each dimension in 3D space. These points served as the ground-truth points and also provided the ground-truth alignment of the two point sets. From this single set of ground-truth points, two different noisy point sets were generated by addition of zero-mean, multivariate, Gaussian noise, while using a different covariance for each point set. The two points generated from each ground-truth point were assigned as correspondences between the two point sets. The covariances were generated at random by forming a diagonal matrix of eigenvalues and multiplying on either side by a random rotation and its transpose (29)

In Experiment 1A, involving anisotropic noise in both point sets, the eigenvalues of the noise covariances were set equal to [0.5, 0.5, 2] mm², with different random rotations being used for each set of points. In Experiment 1B, involving anisotropic noise in only one (the target) point set, these same eigenvalues were used for noising the target points, whereas isotropic noise was generated for the source points by setting all eigenvalues equal to 0.25 mm².

For each study, the randomized trials were divided into several bins according to the magnitude of initial misalignment in translation and rotation. For each bin, 1000 randomized trials were performed and the results were averaged. For every trial, different sets of points, noise models, and misalignment were randomly generated and identically applied to each registration method. Registration accuracy was evaluated by computing the average distance between the un-noised point correspondences following each registration. We report this value as the registration error (RE).

The results of Experiment 1A, which incorporates anisotropic noise in both point sets, are presented in Table 1. In this study, two levels of translational misalignment were investigated on the intervals [10, 20] mm and [90, 100] mm, along with five cases of rotational misalignment, which as a group covered the entire interval of [0, 180] degrees.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Rigid-body registration results for corresponding point sets with anisotropic noise present in both sets of points. (Experiment 1A).

https://doi.org/10.1371/journal.pone.0117688.t001

As seen in the results, the proposed Gauss-Newton-based method achieves lower registration error than all compared methods across all test cases. The proposed method also maintains consistent registration error across all misalignments studied, achieving significant improvement with respect to the isotropic solution in every case. In contrast, the prior anisotropic methods of Estepar et al. and of Balachandran and Fitzpatrick worsen in accuracy as rotational misalignment increases and tend to provide larger registration errors than even the isotropic solution for rotational misalignments on the interval [45, 90] degrees and beyond.

The proposed method’s runtime is also several times more efficient than the other anisotropic solutions; computing a solution requires much fewer iterations (4–9) compared to the methods of Estepar et al. (15–28) and Balachandran and Fitzpatrick (28–45). Note that the iteration count for the method of Estepar et al. is reported as the total number of evaluations of its inner loop, which is where the vast majority of computation takes place for that method.

Another significant observation regarding the results of Experimant 1A is that the proposed method and that of Balachandran and Fitzpatrick are stable under all conditions tested, whereas the method of Estepar et al. encounters frequent instability for large rotational misalignment, with the portion of unstable trials reaching 60% for the largest rotation interval of [150, 180] degrees.

For the method of Balachandrian and Fitzpatrick, the increase in registration error with respect to rotation is understood to result from the assumption of a constant noise covariance as described earlier. However, it is not clear why the method of Estepar et al. exhibits a similar issue. To shed more light on this and on the issue of instability we include a third study (Experiment 1C) in this section.

Table 2 presents the results of Experiment 1B, which incorporates anisotropic noise in only one point set and isotropic noise in the other. In this study, translational misalignment is limited to a large interval of [90, 100] mm, while the test cases for rotational misalignment remain unchanged. The trials for this experiment are conducted twice: once with and once without initializing the anisotropic methods to the isotropic noise solution; other test conditions (the exact point sets, noise, etc.) remain identical between the two types of trials.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Rigid-body registration results for corresponding point sets with anisotropic noise present in one set of points and isotropic noise present in the other. (Experiment 1B).

https://doi.org/10.1371/journal.pone.0117688.t002

As seen in Table 2, the outcome is similar to the earlier study, with the most notable difference being that the method of Balachandran and Fitzpatrick computes an equally accurate registration as the proposed method, which confirms that the high registration errors encountered for this method in the prior study resulted from its assumption of anisotropic noise in only one point set. Concerning the method of Estepar et al., the increase in registration error with respect to rotational misalignment remains, which indicates a different source of error for this method.

It is also interesting to note, concerning the method of Estepar et al., that although the occurrence of unstable trials is reduced by initialization to the isotropic solution, the problem of instability does not go away at the largest range of rotational misalignment.

The proposed method remains largely more efficient than the other anisotropic methods, both with and without initialization to the isotropic solution. It is interesting to note that initialization to the isotropic solution approximately halves the runtime of the method by Balachandran and Fitzpatrick whereas the runtime for the proposed method is reduced by much less, even though the relative decrease in the number of iterations for each method is more similar. This observation indicates that the proposed method has low computational complexity beyond that of computing the initial covariance decompositions (recall for this study that the effective covariances are assumed to be constant), whereas the method of Balachandran and Fitzpatrick retains significantly more overhead per iteration following the initial covariance decompositions. Isotropic initialization also significantly reduces the runtime of the method by Estepar et al. to a little more than half its value otherwise.

Table 3 presents the results of the final study in this series, Experiment 1C, which is intended to further investigate the registration error and instability issues encountered by the method of Estepar et al. relative to increases in rotational offset. This study evaluates only the rotational component of their method. That is, comparison is made concerning the GTLS rotational estimation method of Ohta and Kanatani [28] relative to the proposed Gauss-Newton-based GTLS method and relative to the rotation computed under an isotropic noise assumption. For this comparison, the proposed method and the isotropic solution were modified to estimate only parameters of rotation, assuming translation to be zero. This study was conducted in similar fashion as Experiment 1A, except that only rotational misalignment was applied between the two point sets.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. Rotation-only registration results for corresponding point sets with anisotropic noise present in both sets of points. (Experiment 1C).

https://doi.org/10.1371/journal.pone.0117688.t003

As seen in Table 3, the method of Ohta and Kanatani exhibits the same increase in registration error relative to rotational misalignment as encountered by the method of Estepar et al. Further, the rotation estimation exhibits similar instability under large rotational misalignment. This indicates that a source of error and instability for the method of Estepar et al. lies in the rotation estimation component.

The rotation estimation method in this case uses a quaternion parameterization for rotation that is optimized by applying the renormalization method of Kanatani [29]. Matei and Meer [30] have presented a technique called heteroscedastic errors-in-variables (HEIV) estimator, which is closely related to the renormalization method of Kanatani, in which they present a similarly parameterized method for computing the full rigid-body alignment of two point sets under anisotropic noise. In their work, they point out a discontinuity in the quaternion representation for rotation that produces instability for rotational misalignments close to +/- 180 degrees. It is possible that the rotation estimation method of Kanatani suffers from a similar issue, though we have not verified this further.

Experiment 2: Registering a Mesh Target

In this study, we evaluate the performance of the IMLP algorithm for registering a target shape represented by a triangular mesh. The experiment is divided into two sub-experiments (Experiments 2A and 2B) in order to evaluate the algorithm’s performance under different magnitudes of shape misalignment. The shape being registered in both cases is a human hip model segmented from CT imaging to form a surface mesh (Fig. 1A).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Human hip- and femur-bone meshes used in the registration studies.

The red points represent a typical randomly generated source shape as sampled from the mesh surface. (A): The hip mesh is used in registration Experiments 2–5. (B): The femur mesh is used for the sub-shape registration study of Experiment 6, where points for the source shape are sampled from the shaded region of the mesh.

https://doi.org/10.1371/journal.pone.0117688.g001

The experiments are conducted by randomly generating a set of 100 noisy points from the mesh surface to form a source shape and applying a random misalignment between the source shape and the mesh. The source points are then registered back to the mesh, which forms the target shape. This approach enables accurate assessment of the registration error under varying noise conditions, since both the ground-truth alignment and the generative noise models are known.

Nine different test cases were conducted to evaluate each of the nine different noise models defined in Table 4, which specifies the variance of multivariate Gaussian noise generated in the surface-normal vs. surface-parallel directions at each source point. Thus, the noise applied to each source point was conditioned relative to the orientation of the surface at that point. The first three test cases apply isotropic noise, the next three tests cases apply anisotropic noise of high surface-normal variance, and the final three test cases apply anisotropic noise of high surface-parallel variance, each in order of increasing magnitude of variance and increasing anisotropy. Within each of the nine test cases, 300 randomized registration trials were conducted, each involving new randomly generated points, noise, and misalignment. All compared algorithms were executed once per trial under identical test conditions (i.e. identical shape, noise, and misalignment) as generated for that trial.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 4. Generative noise models (test cases) used in the randomized registration trials of Experiments 2–5.

https://doi.org/10.1371/journal.pone.0117688.t004

Registration errors were measured by randomly sampling a set of 100 non-noisy points from the mesh surface to be used in validation. Following registration, the average distance between the registered and known ground-truth positions of the validation points is measured and recorded as the target registration error (TRE). The average TRE is then reported within each test case for each algorithm. To prevent TRE outliers from skewing the averages, only successful registrations are included in the reported TRE averages. A registration trial is considered successful if the TRE is within 10 mm. The number of registration failures for each algorithm is also counted and reported within each test case. This procedure is followed for all the registration studies that follow in this paper.

The entire experiment was conducted twice for two different intervals of random initial misalignment: once for the misalignment interval of [15, 30] mm translation and [15, 30] degrees rotation (Experiment 2A) and again for the misalignment interval of [30, 60] mm translation and [30, 60] degrees rotation (Experiment 2B). These random misalignments were generated along random translational directions and random rotational axes.

This experiment compares the algorithms of standard ICP [1], IMLP, and the two variants IMLP-CP and IMLP-MD, which, as described in the introduction to the Results and Discussion section, provide near comparison to the GTLS-ICP [10] and A-ICP [12] algorithms, respectively. For IMLP (and variants), the measurement-noise covariances of the source points were set to correspond with the generative noise models defined in Table 4, while the measurement covariances for the target shape were set to zero, since no noise was added to the mesh. Because the mesh fully represents the continuous surface of the target, IMLP’s (and variants’) surface-model covariances were set to zero, as these are intended for registering non-continuous (i.e. point-cloud) surface representations. Outlier detection was disabled by setting IMLP’s (and variants’) chi-square inverse CDF threshold (${\chi }_{\mathrm{\text{thresh}}}^2$) to a large value.

Results for Experiments 2A and 2B are presented in Figs. 2A and 2B for each range of misalignment. Similar results are obtained in both cases. As expected, the average TREs for the first three test cases are identical among all algorithms since, in this case, the noise model of IMLP reduces to the Euclidean-distance computations of standard ICP. For the anisotropic-noise test cases, the IMLP algorithm consistently achieves slightly improved or approximately equivalent registration accuracy compared to ICP. For this study, the Mahalanobis distance matching variant (IMLP-MD) computes approximately the same registration errors as IMLP, whereas the closest-point matching variant (IMLP-CP) generally performs worse, even performing worse than standard ICP for the test cases involving high variance of noise in the surface-normal direction.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Registration errors for registering a mesh target shape. (Experiment 2).

Source shapes were randomly generated from a mesh model of a human hip (Fig. 1A), misaligned by (A): [15, 30] mm / degrees and (B): [30, 60] mm / degrees, and registered back to the mesh. The test cases represent the different noise models used to generate noise on the source shape (Table 4). For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1] and relative to near-comparisons of GTLS-ICP [10] and A-ICP [12] using IMLP-CP and IMLP-MD, which modify IMLP’s most-likely match criteria to that of closest-point and Mahalanobis-distance matching, respectively.

https://doi.org/10.1371/journal.pone.0117688.g002

The error bars displayed in Fig. 2 (and in other figures throughout this section) are approximations for the standard deviations of each displayed TRE average. They are calculated by computing the standard deviation of the TREs for a given average and dividing by the square root of the number of trials used to compute that average. This is the procedure for calculating the standard deviation of a sample mean for independent identically distributed (iid) Gaussian data [33]. We have verified that the histograms of TREs for successful trials reasonably resemble those of Gaussian distributions, in general; thus, the displayed standard deviations may be considered as close approximations.

Table 5 lists the percentage of registration failures for each algorithm and test case in Experiment 2B. For Experiment 2A, the failure rates were 0% in all cases. As seen in the table, the algorithms performed near equally with a maximum overall failure rate of 2%.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 5. Registration failure rates for registering a mesh target shape. (Experiment 2B).

https://doi.org/10.1371/journal.pone.0117688.t005

Table 6 presents a runtime analysis for the successful registrations within each experiment. Due to its greater complexity, IMLP has a runtime of approximately 3.5x that of ICP on average.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 6. Runtimes for registering a mesh target shape. (Experiment 2).

https://doi.org/10.1371/journal.pone.0117688.t006

Experiment 3: Registering a Mesh Target with Outliers

Experiment 3 follows the same procedure as Experiment 2, using the same target shape and equivalent test cases (noise models) and numbers of trials. However, in this study the source shape is corrupted with additional points added as outliers. This experiment is again divided into two studies (Experiments 3A and 3B), one for each range of misalignment. Each study is further divided into sub-studies with varying percentages of outliers including 5%, 10%, 20%, and 30% outliers, which we refer to as sub-experiments i-iv, respectively. Since the purpose of this study is to evaluate the merit of IMLP’s outlier mechanism, the IMLP variants (which have the same outlier mechanism) are not evaluated. Robust ICP [4] is also added to the set of compared algorithms.

The additional outlier samples were generated for each trial by randomly selecting points on the mesh surface and projecting each point outward from the mesh by a random distance on the interval [10, 20] mm.

IMLP’s outlier detection was enabled by setting its chi-square inverse CDF threshold (${\chi }_{\mathrm{\text{thresh}}}^2$) to the values of {7.81, 6.25, 4.64, 3.66} for sub-experiments i-iv, respectively. These values correspond to chi-square inverse CDF probabilities of {0.95, 0.9, 0.8, 0.7}, which were chosen to directly correspond to the percentage of outliers in each test case.

For Robust ICP we follow the suggestion of its author and relate the user parameter D, which is used to determine when a registration is good, to the resolution of the shape data. This was accomplished by computing the average distance between a triangle center point and that of its neighbors in the mesh (in this case approximately 1.8 mm). We also set the user parameter $D_{\mathrm{\text{max}}}^0$, which controls the maximum tolerable match distance of the first iteration, to a large value in order to take all matches into consideration in the first iteration, which afforded the algorithm the best chance at computing a successful registration.

The registration accuracy for this study is presented in Figs. 3 and 4 for Experiments 3A and 3B, respectively. Figs. 3 and 4 are each divided into four sub-figures (A-D) corresponding to sub-experiments (i-iv) of Experiments 3A and 3B, respectively, for each level of outliers. The analysis to produce these results was conducted in the same manner as described for Experiment 2. As seen in the figures, IMLP widely outperforms ICP in terms of TRE for all test cases and performs marginally better overall than Robust ICP for 5% and 10% outliers and much better than Robust ICP at higher levels of outliers, where the TRE for Robust ICP approaches and even surpasses that of standard ICP. In contrast, IMLP’s TRE remains fairly stable up to 20% outliers and begins to increase at the 30% level.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Registration errors for registering a source shape containing outliers to a mesh target under moderate misalignment. (Experiment 3A).

Source shapes were randomly generated from the hip mesh (Fig. 1A), misaligned by [15, 30] mm / degrees, and registered back to the mesh. The test cases represent the different noise models used to generate noise on the source shape (Table 4). Outliers were added to the source shape constituting (A): 5%, (B): 10%, (C): 20%, and (D): 30% of the source points. For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1] and relative to a robust variant of ICP [4].

https://doi.org/10.1371/journal.pone.0117688.g003

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. Registration errors for registering a source shape containing outliers to a mesh target under large misalignment. (Experiment 3B).

Source shapes were randomly generated from the hip mesh (Fig. 1A), misaligned by [30, 60] mm / degrees, and registered back to the mesh. The test cases represent the different noise models used to generate noise on the source shape (Table 4). Outliers were added to the source shape constituting (A): 5%, (B): 10%, (C): 20%, and (D): 30% of the source points. For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1] and relative to a robust variant of ICP [4].

https://doi.org/10.1371/journal.pone.0117688.g004

The registration failure rates shown in Table 7 for this study indicate that although standard ICP is the worst algorithm in terms of TRE, it has the highest registration success rate. At the lesser misalignment range, the failure rates of all algorithms are below 1% for up to 10% outliers, with IMLP having marginally higher failure rates at the 20% outlier level. At 30% outliers, the failure rate of IMLP increases significantly, accompanied by a marginal increase in the failure rate of Robust ICP. For the large misalignment range a different pattern emerges with Robust ICP exhibiting high failure rates across all outlier levels, whereas IMLP maintains low failure rates for up to 10% outliers. The failure rate of standard ICP increases marginally at this offset range yet still remains quite low.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 7. Registration failure rates for registering a mesh target shape with outliers. (Experiment 3).

https://doi.org/10.1371/journal.pone.0117688.t007

Experiment 4: Registering a Point-Cloud Target

In this study, we investigate the performance of the IMLP algorithm for registering a target shape represented by a point cloud. Because the registration only involves point-cloud shapes, several additional algorithms can be compared. In this experiment, we evaluate standard ICP [1], GICP [11], CPD [20], IMLP, and the two variants IMLP-CP and IMLP-MD.

A dense point cloud formed from the center points of every triangle in the human hip mesh (Fig. 1A) is used as the target shape. Besides this change, the test conditions remain as described for Experiment 2. This study is likewise divided into two parts representing different random misalignment intervals: [15, 30] mm / degrees (Experiment 4A) and [30, 60] mm / degrees (Experiment 4B).

In contrast to Experiment 2, the surface-model covariances of IMLP (and variants) are enabled in this study and defined to have standard deviations of 0.5 mm in the surface-normal direction and 5 mm in the surface-parallel directions. Recall that these covariances provide a linear local approximation of the unmeasured surface surrounding each sampled point in order to improve registration accuracy. The measurement-error covariances remain as defined in Experiment 2.

The GICP algorithm also employs a local surface model surrounding each sampled point and uses its covariance matrices for this sole purpose. The covariance scaling parameter (ϵ) of GICP is set to 0.01, which is equal to the ratio of surface-normal vs. surface-parallel variances defined for IMLP. The surface-model used to evaluate GICP is therefore equivalent to the surface-model used by IMLP, because the optimizations performed by GICP do not change with respect to a global scaling of its covariances. We also tested GICP’s default ε value of 0.001, but found 0.01 to provide higher accuracy in this study.

Outlier detection is disabled by setting the chi-square inverse CDF threshold of IMLP to a large value and setting the outlier weight of CPD to zero. The maximum match search distance of GICP is also set to a large value in order to not exclude any matches from consideration. Rigid-body transformation without scaling was selected as the CPD registration method, with the target point cloud being used as the GMM centroids and the source point cloud being used as the data points. This choice of roles was found to be important, as reversing the roles of the source and target points produced substantially higher registration errors.

The registration accuracies achieved by each algorithm for this experiment are presented in Fig. 5. Similar results were obtained for both ranges of initial misalignment. As seen in the figure, IMLP achieves significantly better registration accuracy than any other algorithm across all test cases for both ranges of misalignment, with exception of CPD for which IMLP achieves comparatively better accuracy in more than half of the test cases considered. Note that unlike Experiment 2A, in this experiment IMLP strongly outperforms ICP even for the initial test cases involving isotropic measurement noise. The reason for this stems from the surface-model covariances used to model unmeasured surface regions surrounding each sample point.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 5. Registration errors for registering a point-cloud target shape. (Experiment 4).

Source shapes were randomly generated from a mesh model of a human hip (Fig. 1A), misaligned by (A): [15, 30] mm / degrees and (B): [30, 60] mm / degrees, and registered back to a point-cloud representation of the mesh. The test cases represent different noise models used to generate noise on the source shape (Table 4). For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1], GICP [11], and CPD [20], as well as relative to near-comparisons of GTLS-ICP [10] and A-ICP [12] using the two variants IMLP-CP and IMLP-MD, which modify IMLP’s most-likely match criteria to that of closest-point and Mahalanobis-distance matching, respectively.

https://doi.org/10.1371/journal.pone.0117688.g005

The advantage of IMLP’s most-likely-point matching criteria is particularly highlighted in comparison to the two variants of IMLP that evaluate modifications of its match criteria, i.e. closest-point matching (IMLP-CP) and Mahalanobis-distance matching (IMLP-MD). IMLP achieves significantly, and in some cases substantially, higher accuracy than either of these variants for all test cases considered. Compared to GICP, IMLP also attains a notable accuracy improvement in all test cases, which further underscores the advantage of IMLP’s most-likely-point matching criteria and of its modeling of measurement error.

It is remarkable that the Mahalanobis-distance matching criteria (IMLP-MD) has worse accuracy in this experiment than closest-point matching (IMLP-CP) and, for some test cases, shows no improvement over standard ICP. This result is surprising, especially given that the reverse was true in Experiment 2A, which involved registering to a mesh rather than a point-cloud target.

Table 8 lists the registration failure rates of each algorithm for the large misalignment range of Experiment 4B. For Experiment 4A, no registration failures were indicated except for standard ICP, which had one failure in the second test case. As shown in the table, all algorithms achieve very low failure rates, with GICP being marginally higher than the others and CPD having the best performance with no registration failures.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 8. Registration failure rates for registering a point-cloud target shape. (Experiment 4B).

https://doi.org/10.1371/journal.pone.0117688.t008

Table 9 presents a runtime comparison of each algorithm. Standard ICP is the most efficient algorithm, with IMLP-CP coming second at approximately twice the runtime on average. While not shown in the table, the runtime of GICP is also on-par with that of IMLP-CP. The runtime of GICP is excluded from the table because it was executed within a Live Linux distribution running on a USB flash drive with persistent storage, which occasionally stuttered during execution causing inflated runtime averages. Although IMLP’s runtime is approximately 9 times that of standard ICP in this study, IMLP is up to 60 times more efficient than CPD and 45 times more efficient on average. Using the input settings applied to CPD in this study, it was observed that CPD utilized 100% of both cores on the dual-core test platform, unlike the other algorithms which ran single-threaded. Thus, after normalizing for multithreading, IMLP is approximately two orders of magnitude more efficient than CPD.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 9. Runtimes for registering a point-cloud target shape. (Experiment 4).

https://doi.org/10.1371/journal.pone.0117688.t009

In this study, the runtime difference between ICP and IMLP is greater than observed in Experiment 2A regarding a mesh target. This happens because the node search of the correspondence phase is simplified in this study by not having to compute the closest point on a triangle when computing the distance to a single datum in the PD tree. Although this provides a performance boost to both algorithms, the effect on ICP is much more pronounced since this computation occupies a greater percentage of ICP’s overall runtime.

Experiment 5: Registering a Point-Cloud Target with Outliers

Experiment 5 follows a similar test scenario as Experiment 4, except that the source point set is corrupted with additional points added as outliers. These outliers are generated in the same manner as Experiment 3. Likewise, this experiment is divided into two studies (Experiments 5A and 5B) corresponding to each range of misalignment and further sub-divided for different percentages of outliers including 5%, 10%, 20%, and 30%, which are referred to as sub-experiments i-iv, respectively. As in Experiment 3, the two variants on IMLP are not included in this outlier study, whereas Robust ICP is added.

For IMLP the chi-square inverse CDF threshold is set according to the percentage of outliers as previously described in Experiment 3. Both the surface-model and measurement-error covariances are used in this study in the same manner as was described in Experiment 4. The user-defined parameters for Robust ICP are also configured as in Experiment 3. Following the lead of CPDâs authors, we set the outlier weight to 0.5. In this case, the target point cloud is assigned as the data points and the source point cloud as the GMM centroids, which is the reverse of Experiment 3, as it was observed that this setting produced substantially lower registration error for the case of non-zero outlier weighting. Concerning the GICP algorithm, although a user-defined parameter is provided for limiting the match-search distance, this mechanism is intended for partial-shape registration rather than outlier handling. Although limiting the match-search distance to 10 mm (to eliminate the outliers positioned between 10 and 20 mm from the surface) improves the registration accuracy for some trials, this also causes registration failure in most cases. Thus, GICP is compared in this study by setting its maximum search distance to a large value and considering it to be a non-robust algorithm.

The TRE achieved by each algorithm in this study is presented in Fig. 6 for the range of small misalignments (Experiment 5A) and in Fig. 7 for the range of large misalignments (Experiment 5B). Figs. 6 and 7 are each divided into four sub-figures (A-D) corresponding to sub-experiments (i-iv) of Experiments 5A and 5B, respectively, for each level of outliers. As in the prior studies, the TRE outcomes for each misalignment range are very similar. As seen in the figures, IMLP achieves large improvement in registration accuracy relative to the other algorithms for up to 20% outliers, even in comparison to CPD, which has a very effective outlier rejection capability. For the 30% outlier case, IMLP continues to provide accurate results and compares approximately equal to CPD. Compared to Robust ICP, IMLP is substantially more accurate in all test cases and frequently achieves less than half the registration error and below. As expected, standard ICP and GICP perform poorly, since they are non-robust techniques and do not include mechanisms to account for outliers. Robust ICP fairs much better than the non-robust methods for outlier compositions of 10% and below, but produces higher registration error than standard ICP for the outlier percentages above 10%.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. Registration errors for registering a source shape containing outliers to a point-cloud target under moderate misalignment. (Experiment 5A).

Source shapes were randomly generated from a mesh model of a human hip (Fig. 1A), misaligned by [15, 30] mm / degrees, and registered back to a point-cloud representation of the mesh. The test cases represent different noise models used to generate noise on the source shape (Table 4). Outliers were added to the source shape constituting (A): 5%, (B): 10%, (C): 20%, and (D): 30% of the source points. For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1], GICP [11], a robust variant of ICP [4], and CPD [20].

https://doi.org/10.1371/journal.pone.0117688.g006

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 7. Registration errors for registering a source shape containing outliers to a point-cloud target under large misalignment. (Experiment 5B).

Source shapes were randomly generated from a mesh model of a human hip (Fig. 1A), misaligned by [30, 60] mm / degrees, and registered back to a point-cloud representation of the mesh. The test cases represent different noise models used to generate noise on the source shape (Table 4). Outliers were added to the source shape constituting (A): 5%, (B): 10%, (C): 20%, and (D): 30% of the source points. For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1], GICP [11], a robust variant of ICP [4], and CPD [20].

https://doi.org/10.1371/journal.pone.0117688.g007

Table 10 shows the rate of registration failure for both ranges of misalignment. For small misalignment (Experiment 5A) all algorithms achieve very low failure rates for outlier compositions up to 20%, with exception of GICP which has high failure rate at 20% outliers and beyond. At 30% outliers, the failure rates of Robust ICP and IMLP moderately increase whereas the failure rates of ICP and CPD remain low with CPD achieving no registration failure. For large misalignment, the failure rates of all algorithms are increased, with CPD again providing the best performance. IMLP is approximately on-par with CPD for outliers up to 10%. At 20% outliers, the failure rate of IMLP increases to a moderate 2–6.7%; at 30% outliers, the failure rate increases significantly to 12% and beyond. In contrast, the Robust ICP algorithm performs poorly across the board with an average failure rate above 10% for all percentages of outliers.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 10. Registration failure rates for registering a point-cloud target shape with outliers. (Experiment 5).

https://doi.org/10.1371/journal.pone.0117688.t010

Experiment 6: Sub-Shape Registration

This study investigates the more challenging problem of registering sub-shape data to a complete-shape model, which arises when measurements are taken from a sub-region of a shape to be registered. This scenario is investigated by simulating random measurements from a sub-region of a proximal human femur that has been segmented from CT imaging to form a mesh of the bone surface (Fig. 1B).

The experimental procedure for this study parallels that of Experiment 4, except that the area sampled for the source shape is confined to a sub-region of the target, which is represented by the darkly shaded region of the mesh in Fig. 1B. Random misalignments for this study are generated on the interval [10, 20] mm translation and [10, 20] degrees rotation. The same algorithms as in Experiment 4 are evaluated using identical settings except that the maximum iteration count for CPD was increased to 200, as 100 iterations was insufficient (other algorithms did not require this increase).

In order to diversify the range of noise conditions considered overall, a different set of noise conditions was investigated for this study. Table 11 defines the seven noise models investigated, which includes the zero-noise case, two magnitudes of isotropic noise, two cases of surface-oriented noise to test high variance in both surface-normal and surface-parallel directions, and two test cases involving randomly oriented noise models applied at a global and at a per-point scale. For the test cases involving randomly oriented noise models, different covariances were randomly generated for each trial. As in the prior experiments, 300 randomized trials were conducted for each test case.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 11. Generative noise models (test cases) used in the randomized registration trials of Experiment 6.

https://doi.org/10.1371/journal.pone.0117688.t011

Fig. 8 shows the registration errors and Table 12 presents the registration failure rates achieved by each algorithm in this study. The standard ICP algorithm turns out poor performance across the board in terms of both registration error (above 3.5 mm) and failure rate (approximately 11–19%). CPD has the best success rate with almost no failures overall. The failure rates of other anisotropic methods are approximately on-par with the IMLP failure rate of 3–7%, with the IMLP-CP variant being marginally lower than the others. As seen in the figure, IMLP achieves the lowest registration error in every test case. Compared to CPD the improvement in registration error by IMLP is often substantial, especially for the zero-noise case where IMLP achieves nearly zero registration error and CPD has an average TRE near 1 mm. Again, we find that the Mahalanobis-distance match criterion, as assessed by IMLP-MD, computes substantially worse registration error than the closest-point match criterion, as assessed by IMLP-CP and as also used by GICP; on the other hand, the most-likely match criterion of IMLP achieves the lowest registration error in every case.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 8. Registration errors for registering a sub-shape. (Experiment 6).

Source shapes were randomly generated from a sub-region of a mesh model of a human proximal femur (Fig. 1B), misaligned by [10, 20] mm / degrees, and registered back to a point-cloud representation of the mesh. The test cases represent the different noise models used to generate noise on the source shape (Table 11). For each test case, 300 randomized trials were conducted, with successful registrations being used to compute an average target registration error (TRE). The error bars provide approximate standard deviations of the reported average TRE values. The proposed IMLP algorithm was evaluated relative to standard ICP [1], GICP [11], and CPD [20], as well as relative to near-comparisons of GTLS-ICP [10] and A-ICP [12] using the two variants IMLP-CP and IMLP-MD, which modify IMLP’s most-likely match criteria to that of closest-point and Mahalanobis-distance matching, respectively.

https://doi.org/10.1371/journal.pone.0117688.g008

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 12. Registration failure rates for sub-shape registration. (Experiment 6).

https://doi.org/10.1371/journal.pone.0117688.t012

Experiment 7: Registering Shapes with Partial Overlap

This study investigates a yet more challenging problem of registering two shapes that have only partial overlap, meaning there are regions of both the source and target shape that do not have any true correspondence with the other shape. To investigate this scenario, we use a model of the statue Laurana (Fig. 9A) provided by the Institute of Science and Technologies (ISTI-CNR), Pisa, Italy, which was downloaded under a Creative Commons License from http://vcg.isti.cnr.it/downloads/3dgallery/form_laurana.htm. A decimation was applied to the original mesh using the Quadric Edge Collapse Decimation in MeshLab [42] to reduce the model to 50,000 triangles, and the coordinate system was adjusted to position the origin at the mesh centroid. Two divisions of the mesh were then performed to extract the front (Fig. 9B) and right (Fig. 9C) half-sections of the model. A dense point cloud for the source shape was formed from the vertices of the right half-section, and a dense point cloud for the target shape was defined from the center points of the triangles of the front half-section. Thus, the region of overlap between the source and target shapes comprised 50% of each shape (Fig. 9D).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 9. Registration of shapes having partial overlap. (Experiment 7).

(A): The statue Laurana sub-divided into (B): front and (C): right half-sections, such that (D): a 50% overlap exists between the two sub-shapes. The sub-shapes were (E): misaligned by 10 mm and 10 degrees in a random direction and then registered using (F): CPD [20], (G): GICP [11], and (H): the proposed IMLP algorithm. Sub-figures (E-H) show the initial misalignment and the final registered alignments of the two shapes for the 6th randomized trial of Experiment 7, which involved 10 randomized trials in total.

https://doi.org/10.1371/journal.pone.0117688.g009

Ten randomized registration trials were performed by applying 0.5 mm standard deviation of isotropic Gaussian noise to the source points and applying misalignments of 10 mm and 10 degrees in random directions. Validation points for computing the TRE were selected randomly from the target shape, not being confined to the region of overlap.

The algorithms evaluated in this study were GICP [11], CPD [20], and IMLP. Various values were experimentally tested for the match threshold distance of GICP, with 3 mm finally selected as having the lowest TRE. For CPD, various outlier weights were tested with poor results obtained in every case; we therefore applied the standard outlier weight of 0.5. For IMLP, we used the default chi-square inverse CDF threshold (${\chi }_{\mathrm{\text{thresh}}}^2$) value of 7.81. To minimize bias from the non-overlapping region, matches identified as outliers were configured to be completely disregarded in the registration phase of the IMLP algorithm (rather than inflating their variances), as suggested in the Methods section for this type of application. The measurement-error covariances of IMLP were set to zero in this study in order to, as much as possible, enable the noise model to adapt to the region of overlap based on the match uncertainty term. To restrict “good” matches to the region of overlap, the max threshold for the match uncertainty parameter (${\sigma }_{\mathrm{\text{max}}}^2$) was set to 0.1 mm². The surface-model covariances for both GICP and IMLP were set to the same values as used in Experiment 4.

Table 13 shows the TREs computed by each algorithm for each of the 10 randomized trials. As indicated in the table, CPD is unable to properly register any of the trials in this scenario, whereas both IMLP and GICP register all of them nearly perfectly, with GICP having a moderate to slight accuracy advantage. The bottom row of Fig. 9 provides a visualization of the initial shape misalignment (Fig. 9E) and of the registered alignments computed by each algorithm, including CPD (Fig. 9F), GICP (Fig. 9G), and IMLP (Fig. 9H). The visualizations of Figs. 9E-H represent the 6th randomized registration trial of this experiment.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 13. Registration errors for registering shapes having partial overlap. (Experiment 7).

https://doi.org/10.1371/journal.pone.0117688.t013

Experiment 8: Runtime Comparison of Methods for Computing the Most-Likely Matches

As a final study, an investigation is made concerning the speedup afforded by the PD-tree search technique used to compute the most-likely matches for IMLP. We compare the runtime of a naive exhaustive search to that of the proposed PD-tree method using both the spherical (14) and simple ellipsoidal (15) bounding techniques, as described in the Methods section.

Table 14 shows the average runtimes obtained from running IMLP over all 300 trials of Test Case 1 from Experiment 4B for each method of computing the most-likely matches. As seen in the table, the proposed PD-tree strategy achieves more than 140x speedup over the naive search when using the simple ellipsoidal bounding technique. Comparing the two alternative PD-tree bounding methods indicates that the more compact simple ellipsoidal bound achieves approximately 10% greater runtime efficiency than the spherical bound, even though its computations are significantly more complex.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 14. IMLP runtime comparison using different PD-tree bounding methods for computing the most-likely matches.

https://doi.org/10.1371/journal.pone.0117688.t014

We note that the most compact ellipsoidal bound (17), which is not evaluated here, may enable even further speedup over the simple ellipsoidal bound evaluated above. This is a likely outcome, since the runtime computations performed for each ellipsoidal bounding technique are very similar; thus, the most compact bound should provide the best performance.