4-Points Congruent Sets for Robust Pairwise Surface Registration
- Project number: 202-08-04
- Students: Dror Aiger
- Supervisor: Klara Kedem
We introduce a fast and robust alignment scheme for 3D point sets that uses wide bases, which are known to be resilient to noise and outliers. The algorithm allows registering raw noisy data, possibly contaminated with outliers, without pre-filtering or denoising the data. Further, the method significantly reduces the number of trials required to establish a reliable registration between the underlying surfaces in the presence of noise, without any assumptions about starting alignment.
Our method is based on a novel technique to extract all coplanar 4-points sets from a 3D point set that are approximately congruent , under rigid transformation, to a given set of coplanar 4-points. This extraction procedure runs in roughly O(n^2 + k) time, where n is the number of candidate points and k is the number of reported 4-point sets. In practice, when noise level is low and there is sufficient overlap, using local descriptors the time complexity reduces to O(n+k). We also propose an extension to handle similarity and affine transforms. Our technique achieves an order of magnitude asymptotic acceleration compared to common randomized alignment techniques. We demonstrate the robustness of our algorithm on several sets of multiple range scans with varying degree of noise, outliers, and extent of overlap.
This is joint work with Niloy J. Mitra and Daniel Cohen-Or.
