Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of 'shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model, prior to shape inspection. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces. > <s> BIB001 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> Investigates the use of Euclidean invariant features in a generalization of iterative closest point (ICP) registration of range images. Pointwise correspondences are chosen as the closest point with respect to a weighted linear combination of positional and feature distances. It is shown that, under ideal noise-free conditions, correspondences formed using this distance function are correct more often than correspondences formed using the positional distance alone. In addition, monotonic convergence to at least a local minimum is shown to hold for this method. When noise is present, a method that automatically sets the optimal relative contribution of features and positions is described. This method trades off the error in feature values due to noise against the error in positions due to misalignment. Experimental results suggest that using invariant features decreases the probability of being trapped in a local minimum and may be an effective solution for difficult range image registration problems where the scene is very small compared to the model. <s> BIB002 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> The ICP (Iterative Closest Point) algorithm is widely used for geometric alignment of three-dimensional models when an initial estimate of the relative pose is known. Many variants of ICP have been proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy. We enumerate and classify many of these variants, and evaluate their effect on the speed with which the correct alignment is reached. In order to improve convergence for nearly-flat meshes with small features, such as inscribed surfaces, we introduce a new variant based on uniform sampling of the space of normals. We conclude by proposing a combination of ICP variants optimized for high speed. We demonstrate an implementation that is able to align two range images in a few tens of milliseconds, assuming a good initial guess. This capability has potential application to real-time 3D model acquisition and model-based tracking. <s> BIB003 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> We present a modification to the iterative closest point algorithm which improves the algorithm's robustness and precision. At the start of each iteration, before point correspondence is calculated between the two feature sets, the algorithm randomly perturbs the point positions in one feature set. These perturbations allow the algorithm to move out of some local minima to find a minimum with a lower residual error. The size of this perturbation is reduced during the registration process. The algorithm has been tested using multiple starting positions to register three sets of data: a surface of a femur, a skull surface and a registration to hepatic vessels and a liver surface. Our results show that, if local minima are present, the stochastic ICP algorithm is more robust and is more precise than the standard ICP algorithm. <s> BIB004 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> Automatic range image registration and matching is an attractive but unresolved problem in both the machine vision and pattern recognition literature. Since automatic range image registration and matching is inherently a very difficult problem, the algorithms developed are becoming more and more complicated. In this paper, we propose a novel practical algorithm for automatic free-form surface matching. This method directly manipulates the possible point matches established by the traditional ICP criterion based on both the collinearity and closeness constraints without any feature extraction, image pre-processing, or motion estimation from outliers corrupted data. A comparative study based on a large number of real range images has shown the accuracy and robustness of the novel algorithm. <s> BIB005 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> We investigate in this article the rigid registration of large sets of points, generally sampled from surfaces. We formulate this problem as a general Maximum-Likelihood (ML) estimation of the transformation and the matches. We show that, in the specific case of a Gaussian noise, it corresponds to the Iterative Closest Point algorithm(ICP) with the Mahalanobis distance.Then, considering matches as a hidden variable, we obtain a slightly more complex criterion that can be efficiently solved using Expectation-Maximization (EM) principles. In the case of a Gaussian noise, this new methods corresponds to an ICP with multiple matches weighted by normalized Gaussian weights, giving birth to the EM-ICP acronym of the method.The variance of the Gaussian noise is a new parameter that can be viewed as a "scale or blurring factor" on our point clouds. We show that EMICP robustly aligns the barycenters and inertia moments with a high variance, while it tends toward the accurate ICP for a small variance. Thus, the idea is to use a multi-scale approach using an annealing scheme on this parameter to combine robustness and accuracy. Moreover, we show that at each "scale", the criterion can be efficiently approximated using a simple decimation of one point set, which drastically speeds up the algorithm.Experiments on real data demonstrate a spectacular improvement of the performances of EM-ICP w.r.t. the standard ICP algorithm in terms of robustness (a factor of 3 to 4) and speed (a factor 10 to 20), with similar performances in precision. Though the multiscale scheme is only justified with EM, it can also be used to improve ICP, in which case the performances reaches then the one of EM when the data are not too noisy. <s> BIB006 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> Abstract This paper describes the design, implementation and results of a unified non-rigid feature registration method for the purposes of anatomical MRI brain registration. An important characteristic of the method is its ability to fuse different types of anatomical features into a single point-set representation. We demonstrate the application of the method using two different types of features: the outer cortical surface and major sulcal ribbons. Non-rigid registration of the combined feature point-sets is then performed using a new robust non-rigid point matching algorithm. The point matching algorithm implements an iterative joint clustering and matching (JCM) strategy which effectively reduces the computational complexity without sacrificing accuracy. We have conducted carefully designed synthetic experiments to gauge the effect of using different types of features either separately or together. A validation study examining the accuracy of non-rigid alignment of many brain structures is also presented. Finally, we present anecdotal results on the alignment of two subject MRI brain data. <s> BIB007 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> Motivated by the problem of retinal image registration, this paper introduces and analyzes a new registration algorithm called Dual-Bootstrap Iterative Closest Point (Dual-Bootstrap ICP). The approach is to start from one or more initial, low-order estimates that are only accurate in small image regions, called bootstrap regions. In each bootstrap region, the algorithm iteratively: 1) refines the transformation estimate using constraints only from within the bootstrap region; 2) expands the bootstrap region; and 3) tests to see if a higher order transformation model can be used, stopping when the region expands to cover the overlap between images. Steps 1): and 3), the bootstrap steps, are governed by the covariance matrix of the estimated transformation. Estimation refinement [Step 2)] uses a novel robust version of the ICP algorithm. In registering retinal image pairs, Dual-Bootstrap ICP is initialized by automatically matching individual vascular landmarks, and it aligns images based on detected blood vessel centerlines. The resulting quadratic transformations are accurate to less than a pixel. On tests involving approximately 6000 image pairs, it successfully registered 99.5% of the pairs containing at least one common landmark, and 100% of the pairs containing at least one common landmark and at least 35% image overlap. <s> BIB008 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> This paper investigates the use of a total least squares approach in a generalization of the iterative closest point (ICP) algorithm for shape registration. A new Generalized Total Least Squares (GTLS) formulation of the minimization process is presented opposed to the traditional Least Squares (LS) technique. Accounting for uncertainty both in the target and in the source models will lead to a more robust estimation of the transformation. Robustness against outliers is guaranteed by an iterative scheme to update the noise covariances. Experimental results show that this generalization is superior to the least squares counterpart. <s> BIB009 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> The computation of a rigid body transformation which optimally aligns a set of measurement points with a surface and related registration problems are studied from the viewpoint of geometry and optimization. We provide a convergence analysis for widely used registration algorithms such as ICP, using either closest points (Besl and McKay, 1992) or tangent planes at closest points (Chen and Medioni, 1991) and for a recently developed approach based on quadratic approximants of the squared distance function (Pottmann et al., 2004). ICP based on closest points exhibits local linear convergence only. Its counterpart which minimizes squared distances to the tangent planes at closest points is a Gauss---Newton iteration; it achieves local quadratic convergence for a zero residual problem and--if enhanced by regularization and step size control--comes close to quadratic convergence in many realistic scenarios. Quadratically convergent algorithms are based on the approach in (Pottmann et al., 2004). The theoretical results are supported by a number of experiments; there, we also compare the algorithms with respect to global convergence behavior, stability and running time. <s> BIB010 </s> Deformable Medical Image Registration: A Survey <s> 4) Methods That Infer Both the Correspondences and the Transformation: <s> Since its introduction in the early 1990s, the Iterative Closest Point (ICP) algorithm has become one of the most well-known methods for geometric alignment of 3D models. Given two roughly aligned shapes represented by two point sets, the algorithm iteratively establishes point correspondences given the current alignment of the data and computes a rigid transformation accordingly. From a statistical point of view, however, it implicitly assumes that the points are observed with isotropic Gaussian noise. In this paper, we show that this assumption may lead to errors and generalize the ICP such that it can account for anisotropic and inhomogenous localization errors. We 1) provide a formal description of the algorithm, 2) extend it to registration of partially overlapping surfaces, 3) prove its convergence, 4) derive the required covariance matrices for a set of selected applications, and 5) present means for optimizing the runtime. An evaluation on publicly available surface meshes as well as on a set of meshes extracted from medical imaging data shows a dramatic increase in accuracy compared to the original ICP, especially in the case of partial surface registration. As point-based surface registration is a central component in various applications, the potential impact of the proposed method is high. <s> BIB011
The last class of methods aims to estimate the correspondences and the transformation at the same time. This is usually performed in an iterative way. First, one component is estimated, and then the other component is refined based on this estimation. One of the most well-known approaches is the iterative closest point (ICP) method proposed by Besl and McKay BIB001 . Simplicity and speed are the main characteristics of this method. Correspondences are defined based on a closest (in a geometric sense) neighbor principle. Based on this estimation, the transformation is calculated. Then, a new closest neighbor is assigned to each key-point and the process continues until convergence. ICP has drawn a lot of attention and a number of researchers have tried to improve the method over the years. Rusinkiewicz and Levoy reviewed different variants of ICP BIB003 . Liu has reported an overview of the improvements over ICP BIB005 . Pottmann et al. presented a study of the convergence properties of the ICP algorithm BIB010 . Penney et al. BIB004 proposed to add Gaussian noise to the positions of the points in one set before each iteration of the original ICP. The magnitude of the noise was decreased as the process advanced. The motivation behind this strategy was to improve the precision and robustness of the algorithm. Granger and Pennec BIB006 proposed an approach named multi-scale EM-ICP. The method is similar to standard ICP with a Mahalanobis distance. The principal difference lies in the estimation of the transformation step where multiple matches weighted by Gaussian weights were considered. The problem was solved in an expectation-maximization fashion. Sharp et al. BIB002 investigated the use of shape features in addition to the positional information when estimating the correspondences. Stewart et al. BIB008 proposed a dual-bootstrap ICP method to register retinal images. The method operated initially on small regions where accurate correspondences could be obtained. Based on these correspondences low order transformations were estimated. In the subsequent steps, the size of the regions as well as the order of the transformation model were refined. The region refinement was based on the uncertainty of the transformation. Liu BIB005 used collinearity and closeness constraints in order to increase the robustness and accuracy of the algorithm for free form deformation. Estepar et al. BIB009 allowed for anisotropic noise in both target and source point sets in order to render the algorithm more robust. The problem was cast in the form of a Generalized Total Least Square problem. Maier-Hein et al. BIB011 recently proposed a related work that accounts for localization error. Let us note that ICP method, as well as its variants presented here, estimate a global linear transformation. An important extension to nonrigid scenarios was proposed by Chui et al.  . The proposed thin-plate spline robust point matching (TPS-RPM) algorithm iterates between estimating the correspondence with the softassign method and computing the transformation with a TPS model. Chui et al. BIB007 further refined the latter approach by iteratively solving a clustering and matching problem.