Comparison of ICP algorithms

Algorithm Selection of Points Matching Points Weighting and Rejecting Pairs Error Metric Minimizing Error Global Registration Notes
[Faugeras 86] Feature identification Corresponding feature finding   Point-to-point      
[Hanson 81],
[Arun 87],
[Horn 87],
[Horn 88]
[Walker 91],
[Eggert 97]
Assumed given Assumed given Constant or user-specified Point-to-point Closed-form solution for best transform given one set of correspondences   [Hanson 81] and [Arun 87] use SVD; [Horn 87] uses unit quaternions; [Horn 88] uses orthonormal matrices; [Walker 91] uses dual quaternions; [Eggert 97] is a comparison of these
[Chen 91] Uniform subsampling, smooth regions Normal shooting   Point-to-plane Iterative minimization New -> all previous Minimization equations not linear, but can be approximated as linear if transform is close to correct
[Stein 92]             Object identification with no initial xform estimates, using database of quantized patches
[Besl 92] All Closest point Constant Point-to-point Iterative minimization, accelerated by extrapolation    
[Szeliski 94]   Closest point   Point-to-point Iterative minimization   Nonrigid deformation with hierarchical splines
[Turk 94] Uniform subsampling Closest point Distance threshold; reject edge points; weight is normal dot camera vector Point-to-point Iterative minimization, accelerated by extrapolation Align all to cylindrical anchor scan Perform ICP on low-to-high resolution versions of meshes
[Godin 94] All in both meshes Closest point with compatible color Distance threshold; weighted by compatibility and distance Point-to-point Iterative minimization    
[Blais 95] Uniform subsampling Projection Distance threshold Point-to-point Search in transform space using simulated annealing Search for all transforms simultaneously  
[Stoddart 96] Assumed given Assumed given   Point-to-point Gradient descent Find all transforms simultaneously  
[Masuda 96] Random sampling Closest point, accelerated with k-d tree Distance threshold Point-to-point Iterative minimization; find transform that minimizes median of squared distances after several random subsamplings New to integration of all previous  
[Bergevin 96] Uniform subsampling, smooth regions Normal shooting Reject if dot product of normals is negative Point-to-plane Iterative minimization Iterated all-to-all ICP  
[Simon 96] All Closest point, accelerated with k-d tree and point cache Distance threshold Point-to-point Iterative minimization, accelerated by separate extrapolation of rotation and translation   Rerun ICP with perturbed starting positions to avoid local minima
[Dorai 96],[Dorai98] All Normal shooting, accelerated by projection plus search Rejection based on pair-to-pair compatibility Point-to-plane Iterative minimization    
[Dorai 97] All Normal shooting Weighted based on effect of scanner noise on normal Point-to-plane Iterative minimization    
[Benjemaa 97] All Closest point, accelerated using z buffer search   Point-to-point Iterative minimization Iterated all-to-all ICP  
[Johnson 97a]             Hashing of object shape to perform registration with no initial guesses for xform
[Johnson 97b] All Closest point in shape+color space, accelerated with k-d tree   Point-to-point, shape+color Iterative minimization    
[Neugebauer 97] Uniform subsampling Projection Reject points with distance greater than 3 sigma Point-to-plane Iterative minimization via Levenberg-Marquardt Align all scans simultaneously Terminate by statistically testing hypothesis delta=0
[Weik 97] Select points with high intensity gradient Projection followed by search for sample with similar image intensity and gradient Reject projected points that are occluded in the source mesh Point-to-point Iterative minimization    
[Pulli 97] All Like [Weik 97], but project complete images and do image alignment   Point-to-point Iterative minimization Scan-to-scan ICP, then global optimization of transforms using pre-computed point pairs  
[Chen 98],[Chen 99]   Closest point   Number of corresponding points within threshold Exhaustive search, starting with 3 control points on P, and considering all possible xforms that map these to plausible corresponding points on Q   Initial guess for alignment, given no starting xform. Refined using ICP.
[Pulli 99],[Levoy00] Random sampling in both meshes Closest point with compatible normals Distance threshold; reject edge points; reject some percentage of pairs with largest distances Point-to-plane Iterative minimization Like [Pulli 97], but process scans in order of how many others they overlap  
[Williams 00]       Point-to-point Iterative minimization Simultaneous alignment with error modeling