stabicp slides

Geometrically Stable Sampling for the ICP Algorithm: 

Geometrically Stable Sampling for the ICP Algorithm

Two Flavors of ICP: 

Two Flavors of ICP Point-point error Point-plane error faster to converge

Source of Failures: 

Source of Failures Complex error landscape Many local minima Usually have to start from a good guess Point selection and error metric in minimization are key to convergence Some shapes are particularly 'difficult' Noise

Requirements for Error Metric: 

Requirements for Error Metric Planar and spherical areas with no features should not contribute to distance metric 'Lock and key' features should pull the surfaces to correct relative pose Robust even as features get small and featureless regions noisy

Solution: 

Solution Detect when parts of the input patch are prone to sliding Use covariance analysis Concentrate samples in 'lock and key' areas to improve convergence Use geometrically stable point-selection strategy Similar to normal-space sampling [Rusinkiewicz andamp; Levoy] Detect when input has no 'lock and key' features Do not align that scan pair at all Improves convergence of global registration [Ikemoto et.al]

Minimization Equation: 

Minimization Equation Find (R, t) that minimize Linearizing rotations: find r=[rx ry rz]T, t=[tx ty tz]T that minimize pi qi

Analyzing the Metric (1): 

Analyzing the Metric (1) Change in error from each point-pair: For some transformations e=0: translation perpendicular to 'force'

Analyzing the Metric (2): 

Analyzing the Metric (2) Change in error from each point-pair: For some transformations e=0: rotation perpendicular to 'torque'

Covariance Matrix: 

Covariance Matrix Aligning transform is given by Cx=b, where C encodes the change in error when surfaces are moved from optimal alignment

Sliding Directions: 

Sliding Directions Eigenvectors of C with small eigenvalues correspond to sliding transformations 3 small eigenvalues 3 rotation 3 small eigenvalues 2 translation 1 rotation 2 small eigenvalues 1 translation 1 rotation 1 small eigenvalue 1 rotation 1 small eigenvalue 1 translation

Sample Selection: 

Sample Selection Goal of sampling is to produce covariance matrix C with a good condition number Equally constrain all eigenvectors Find points that well sample the small features on P Since P and Q are similar in the overlap region, use both points and normals from P to compute C

Implementation (1): 

Implementation (1) Estimate C from sparse uniform sampling of input mesh C = XLXT 6x6 matrix 6 eigenvectors form basis for the space of transforms

Implementation (2): 

Implementation (2) For each point form For each eigenvector x j compute Magnitude of the constraint pi exerts on x j Sort points in decreasing 'order of influence' for each eigenvector

Implementation (3): 

Implementation (3) Let be an estimate of how well eigenvector x j is constrained by already chosen points Choose next pi from from list with the smallest corresponding t j Most unconstrained eigenvector Compute closest point qi in Q Once enough points are chosen, solve for alignment and iterate

Sample Selection: 

Sample Selection Small eigenvalues

Sample Selection: 

Sample Selection Large eigenvalues

Results (Planar Patches): 

Results (Planar Patches) Without noise, any sampling works fine Similar to normal-space sampling for planar regions

Results (Planar Patches): 

Results (Planar Patches) 25 iterations to converge Naïve implementation about 3 times slower per iteration than uniform sampling

Results (Spherical Patches): 

Results (Spherical Patches) Normal-space sampling cannot align this

Conclusions: 

Conclusions Point-plane error metric can have shallow error landscape when registering shapes with small features Noise adds many small local minima These conditions can be detected by analyzing the covariance matrix of the minimization equation Eigenvectors with small eigenvalues give sliding directions Stable sampling improves these landscapes by equally constraining all eigenvectors Selects point samples inside the features Allows ICP to align 'difficult' input

Limitations: Noise: 

Limitations: Noise The algorithm can fail if input data is particularly noisy Smoothing can help

Limitations: Noise: 

Limitations: Noise Success depends on relative size of features

Extensions and Future Work: 

Extensions and Future Work Use stability analysis to weigh mesh pairs in global registration A hierarchical method for aligning warped meshes [Ikemoto et al] Stable sampling for global registration Simultaneous covariance analysis of the entire set of scans Weighing eigenvectors based on the area outside the overlap Large vs. small leverage on the entire scan

Extensions and Future Work: 

Extensions and Future Work Use of stability analysis as shape descriptor Segmentation into areas with similar sliding transformations