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 |