“4-points congruent sets for robust pairwise surface registration” by Aiger, Mitra and Cohen-Or

We introduce 4PCS, 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(n2 + k) time, where n is the number of candidate points and k is the number of reported 4-points 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.

1. Agarwal, P. K., and Sharir, M. 2002. The number of congruent simplices in a point set. In Discrete Comput. Geometry, vol. 28, 123–150.Google ScholarDigital Library
2. Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., and Wu, A. Y. 1998. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. ACM 45, 6, 891–923. Google ScholarDigital Library
3. Ballard, D. H. 1987. Generalizing the hough transform to detect arbitrary shapes. Readings in computer vision: issues, problems, principles, and paradigms, 714–725. Google ScholarDigital Library
4. Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE Trans. on Pattern Analysis and Machine Intelligence 14, 2, 239–256. Google ScholarDigital Library
5. Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Trans. Graph. 26, 3, # 21. Google ScholarDigital Library
6. Callieri, M., Fasano, A., Impoco, G., Cignoni, P., Scopigno, R., Parrini, G., and Biagini, G. 2004. Roboscan: An automatic system for accurate and unattended 3d scanning. In 3DPVT, 805–812. Google ScholarCross Ref
7. Chen, Y., and Medioni, G. G. 1992. Object modelling by registration of multiple range images. In Image and Vis. Compt., vol. 10, 145–155. Google ScholarDigital Library
8. Chen, C.-S., Hung, Y.-P., and Cheng, J.-B. 1999. RANSAC-based DARCES: A new approach to fast automatic registration of partially overlapping range images. IEEE Trans. on Pattern Analysis and Machine Intelligence 21, 11, 1229–1234. Google ScholarDigital Library
9. Fischler, M. A., and Bolles, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6, 381–395. Google ScholarDigital Library
10. Frome, A., Huber, D., Kolluri, R., Bulow, T., and Malik, J. 2004. Recognizing objects in range data using regional point descriptors. In Proceedings of the European Conference on Computer Vision (ECCV).Google Scholar
11. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. Gr. 25, 1, 130–150. Google ScholarDigital Library
12. Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In Proc. Symp. Geometry Processing, 214–223. Google ScholarDigital Library
13. Gelfand, N., Mitra, N. J., Guibas, L. J., and Pottmann, H. 2005. Robust global registration. In Proc. Symp. Geometry Processing, 197–206. Google ScholarDigital Library
14. Germain, R. S., Califano, A., and Colville, S. 1997. Fingerprint matching using transformation parameter clustering. IEEE Comput. Sci. Eng. 4, 4, 42–49. Google ScholarDigital Library
15. Goodrich, M. T., Mitchell, J. S. B., and Orletsky, M. W. 1994. Practical methods for approximate geometric pattern matching under rigid motions. In Symp. on Computational Geometry, 103–112. Google ScholarDigital Library
16. Horn, B. K. 1987. Closed-form solution of absolute orientation using unit quaternions. In Journal of the Optical Society of America, vol. 4, 629–642.Google ScholarCross Ref
17. Huttenlocher, D. P., and Ullman, S. 1990. Recognizing solid objects by alignment with an image. Int. J. Comput. Vision 5, 2, 195–212. Google ScholarDigital Library
18. Huttenlocher, D. P. 1991. Fast affine point matching: An output-sensitive method. Tech. rep., Cornell, CS department.Google Scholar
19. Indyk, P., Motwani, R., and Venkatasubramanian, S. 1999. Geometric matching under noise: combinatorial bounds and algorithms. In Symposium on Discrete algorithms, 457–465. Google ScholarDigital Library
20. Irani, S., and Raghavan, P. 1996. Combinatorial and experimental results for randomized point matching algorithms. In Symp. on Computational Geometry, 68–77. Google ScholarDigital Library
21. Johnson, A. 1997. Spin-Images: A Representation for 3-D Surface Matching. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
22. Li, X., and Guskov, I. 2005. Multi-scale features for approximate alignment of point-based surfaces. In Proc. Symp. Geometry Processing, 217–226. Google ScholarDigital Library
23. Mitra, N. J., Gelfand, N., Pottmann, H., and Guibas, L. 2004. Registration of point cloud data from a geometric optimization perspective. In Proc. Symp. Geometry Processing, 23–31. Google ScholarDigital Library
24. Mitra, N. J., Guibas, L., Giesen, J., and Pauly, M. 2006. Probabilistic fingerprints for shapes. In Proc. Symp. Geometry Processing, 121–130. Google ScholarDigital Library
25. Mori, M.-G., Belongie, M.-S., and Malik, S. M.-J. 2005. Efficient shape matching using shape contexts. IEEE Trans. on Pattern Analysis and Machine Intelligence 27, 11, 1832–1837. Google ScholarDigital Library
26. Pauly, M., Mitra, N. J., Giesen, J., Gross, M., and Guibas, L. 2005. Example-based 3d scan completion. In Proc. Symp. Geometry Processing, 23–32. Google ScholarDigital Library
27. Pottmann, H., Wallner, J., Yang, Y.-L., Lai, Y.-K., and Hu, S.-M. 2007. Principal curvatures from the integral invariant viewpoint. Comput. Aided Geom. Des. 24, 8–9, 428–442. Google ScholarDigital Library
28. Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In Proc. of 3DIM, 145–152.Google Scholar
29. Wolfson, H. J., and Rigoutsos, I. 1997. Geometric hashing: An overview. IEEE Comput. Sci. Eng. 4, 4, 10–21. Google ScholarDigital Library