[attachment=15323]
Efficient Variants of the ICP Algorithm
Problem
Align two partially-overlapping meshesgiven initial guessfor relative transform
Aligning 3D Data
If correct correspondences are known,it is possible to find correct relative rotation/translation
Aligning 3D Data
How to find corresponding points?
Previous systems based on user input,feature matching, surface signatures, etc.
Aligning 3D Data
Alternative: assume closest points correspond to each other, compute the best transform…
Aligning 3D Data
… and iterate to find alignment
Iterated Closest Points (ICP) [Besl & McKay 92]
Converges if starting position “close enough“
Outline
Enumeration and classification ofICP variants
Performance comparisons
High-speed ICP algorithm recombines previously-introduced variants
Suitable for real-time range scanning
ICP Variants
Variants on the following stages of ICPhave been proposed:
Performance of Variants
Can analyze various aspects of performance:
Speed
Stability
Tolerance of noise and/or outliers
Basin of convergence (maximum initial misalignment)
Comparisons in paper focus mostly on speed
Today: summarize conclusions about a few categories of ICP variants
ICP Variants
Selecting Source Points
Use all points
Uniform subsampling
Random sampling
Normal-space sampling
Ensure that samples have normals distributedas uniformly as possible
Normal-Space Sampling
Normal-Space Sampling
Conclusion: normal-space sampling better for mostly-smooth areas with sparse features
Selection vs. Weighting
Could achieve same effect with weighting
Hard to ensure enough samples in features except at high sampling rates
However, have to build special data structure
Preprocessing / run-time cost tradeoff
ICP Variants
Point-to-Plane Error Metric
Using point-to-plane distance instead of point-to-point lets flat regions slide along each other [Chen & Medioni 91]
ICP Variants
Matching
Matching strategy has greatest effect on convergence and speed
Closest point
Normal shooting
Closest compatible point
Projection
Closest-Point Matching
Find closest point in other mesh
Normal Shooting
Project along normal, intersect other mesh
Closest Compatible Point
Can improve effectiveness of both of the previous variants by only matching to compatible points
Compatibility based on normals, colors, etc.
At limit, degenerates to feature matching
Projection to Find Correspondences
Finding closest point is most expensive stage ofthe ICP algorithm
Idea: use a simpler algorithm to find correspondences
For range images, can simply project point [Blais 95]
Projection-Based Matching
Slightly worse performance per iteration
Each iteration is one to two orders of magnitude faster than closest-point
Requires point-to-plane error metric
High-Speed ICP Algorithm
ICP algorithm with projection-based correspondences, point-to-plane matchingcan align meshes in a few tens of ms.(cf. over 1 sec. with closest-point)
Application
Given:
A scanner that returns range images in real time
Fast ICP
Real-time merging and rendering
Result: 3D model acquisition
Tight feedback loop with user
Can see and fill holes while scanning
Our Implementation
Real-time structured-light range scanner[Hall-Holt & Rusinkiewicz, ICCV01]
Off-the-shelf camera and DLP projector
Range images at 60 Hz.
Photograph
Real-Time Result
Conclusions
Classified and compared variants of ICP
Normal-space sampling for smooth meshes with sparse features
Overall speed depends most on choice of matching algorithm
Particular combination of variants can align two range images in a few tens of ms.
Real-time range scanning
Model-based tracking
Future Work
More work on examining robustness and stability of variants
Real-time global registration
Other selection / weighting criteria?
Select in regions of high curvature
Continuum between ICP with fancy selection(or weighting) and feature matching