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

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