research-article
Authors: Dror Aiger, Niloy J. Mitra, and Daniel Cohen-Or
ACM Transactions on Graphics (TOG), Volume 27, Issue 3
Pages 1 - 10
Published: 01 August 2008 Publication History
- 460citation
- 2,743
- Downloads
Metrics
Total Citations460Total Downloads2,743Last 12 Months144
Last 6 weeks31
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
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.
Supplementary Material
MOV File (a85-aiger.mov)
- Download
- 16.79 MB
References
[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.
Digital 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.
Digital 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.
Digital 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.
Digital Library
[5]
Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Trans. Graph. 26, 3, # 21.
Digital 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.
[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.
Digital 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.
Digital 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.
Digital 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).
[11]
Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. Gr. 25, 1, 130--150.
Digital Library
[12]
Gelfand, N., and Guibas, L. J. 2004. Shape segmentation using local slippage analysis. In Proc. Symp. Geometry Processing, 214--223.
Digital Library
[13]
Gelfand, N., Mitra, N. J., Guibas, L. J., and Pottmann, H. 2005. Robust global registration. In Proc. Symp. Geometry Processing, 197--206.
Digital 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.
Digital 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.
Digital 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.
[17]
Huttenlocher, D. P., and Ullman, S. 1990. Recognizing solid objects by alignment with an image. Int. J. Comput. Vision 5, 2, 195--212.
Digital Library
[18]
Huttenlocher, D. P. 1991. Fast affine point matching: An output-sensitive method. Tech. rep., Cornell, CS department.
[19]
Indyk, P., Motwani, R., and Venkatasubramanian, S. 1999. Geometric matching under noise: combinatorial bounds and algorithms. In Symposium on Discrete algorithms, 457--465.
Digital Library
[20]
Irani, S., and Raghavan, P. 1996. Combinatorial and experimental results for randomized point matching algorithms. In Symp. on Computational Geometry, 68--77.
Digital Library
[21]
Johnson, A. 1997. Spin-Images: A Representation for 3-D Surface Matching. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
[22]
Li, X., and Guskov, I. 2005. Multi-scale features for approximate alignment of point-based surfaces. In Proc. Symp. Geometry Processing, 217--226.
Digital 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.
Digital Library
[24]
Mitra, N. J., Guibas, L., Giesen, J., and Pauly, M. 2006. Probabilistic fingerprints for shapes. In Proc. Symp. Geometry Processing, 121--130.
Digital 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.
Digital 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.
Digital 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.
Digital Library
[28]
Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In Proc. of 3DIM, 145--152.
[29]
Wolfson, H. J., and Rigoutsos, I. 1997. Geometric hashing: An overview. IEEE Comput. Sci. Eng. 4, 4, 10--21.
Digital Library
Cited By
View all
- YANG XLI F(2024)Artificial intelligence-assisted restoration and visualization of knapped stone toolsPrehistoric Archaeology10.3724/2097-3063.20240016Online publication date: 25-Jun-2024
- Meng QKang HLiu XYu H(2024)Dynamic Path Planning Based on 3D Cloud Recognition for an Assistive Bathing RobotElectronics10.3390/electronics1307117013:7(1170)Online publication date: 22-Mar-2024
- Zhang YZhang LZhao XFu HYu D(2024)Automatic Point Cloud Registration for 3D Virtual-to-Real Registration Using Macro and Micro StructuresIEEE Transactions on Multimedia10.1109/TMM.2024.335457026(6566-6581)Online publication date: 2024
- Show More Cited By
Index Terms
4-points congruent sets for robust pairwise surface registration
Computing methodologies
Artificial intelligence
Computer vision
Computer vision problems
Computer vision representations
Shape representations
Image and video acquisition
Epipolar geometry
Computer graphics
Image manipulation
Machine learning
Learning paradigms
Unsupervised learning
Cluster analysis
Modeling and simulation
Model development and analysis
Model verification and validation
Recommendations
- Robust registration of 3D point sets for free-form surface inspection
2017 IEEE International Conference on Mechatronics and Automation (ICMA)
The problem of robust registration of 3D point sets disturbed by noise for free-form surface inspection is considered. In this research, M-estimation methods are used to eliminate the effects of outliers, and a robust extension of tangent-squared distance ...
Read More
- A robust similarity measure for volumetric image registration withźoutliers
Image registration under challenging realistic conditions is a very important area of research. In this paper, we focus on algorithms that seek to densely align two volumetric images according to a global similarity measure. Despite intensive research ...
Read More
- Multi-attribute statistics histograms for accurate and robust pairwise registration of range images
A distinctive, robust and efficient 3D local shape descriptor called MaSH is proposed.A novel 3D transformation estimation algorithm named 2SAC-GC is proposed.An accurate and robust range image registration method is presented.The proposed registration ...
Read More
Comments
Information & Contributors
Information
Published In
ACM Transactions on Graphics Volume 27, Issue 3
August 2008
844 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1360612
Issue’s Table of Contents
Copyright © 2008 ACM.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 2008
Published inTOGVolume 27, Issue 3
Permissions
Request permissions for this article.
Check for updates
Author Tags
- affine invariant ratio
- computational geometry
- largest common pointset (LCP) measure
- pairwise surface registration
- partial shape matching
- scan alignment
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
460
Total Citations
2,743
Total Downloads
- Downloads (Last 12 months)144
- Downloads (Last 6 weeks)31
Other Metrics
View Author Metrics
Citations
Cited By
View all
- YANG XLI F(2024)Artificial intelligence-assisted restoration and visualization of knapped stone toolsPrehistoric Archaeology10.3724/2097-3063.20240016Online publication date: 25-Jun-2024
- Meng QKang HLiu XYu H(2024)Dynamic Path Planning Based on 3D Cloud Recognition for an Assistive Bathing RobotElectronics10.3390/electronics1307117013:7(1170)Online publication date: 22-Mar-2024
- Zhang YZhang LZhao XFu HYu D(2024)Automatic Point Cloud Registration for 3D Virtual-to-Real Registration Using Macro and Micro StructuresIEEE Transactions on Multimedia10.1109/TMM.2024.335457026(6566-6581)Online publication date: 2024
- Shao JYao WWang PHe ZLuo L(2024)Urban GeoBIM Construction by Integrating Semantic LiDAR Point Clouds With as-Designed BIM ModelsIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.335837062(1-12)Online publication date: 2024
- Liu SWang TZhang YZhou RLi LDai CZhang YWang LWang H(2024)Deep Semantic Graph Matching for Large-Scale Outdoor Point Cloud RegistrationIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.335570762(1-12)Online publication date: 2024
- Wu YDing HGong MQin AMa WMiao QTan K(2024)Evolutionary Multiform Optimization With Two-Stage Bidirectional Knowledge Transfer Strategy for Point Cloud RegistrationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321574328:1(62-76)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TEVC.2022.3215743
- Zhang JXie FSun LZhang PZhang ZChen JChen FYi M(2024)Multi-View Point Cloud Registration Based on Improved NDT Algorithm and ODM Optimization MethodIEEE Robotics and Automation Letters10.1109/LRA.2024.34080869:8(6816-6823)Online publication date: Aug-2024
- Xu ZZhang YChen JMa FHuang K(2024)VMB Module for Low-Overlap Point Cloud RegistrationIEEE Geoscience and Remote Sensing Letters10.1109/LGRS.2023.333630321(1-5)Online publication date: 2024
- Tao WXiao YWang RLu TXu S(2024)A Fast Registration Method for Building Point Clouds Obtained by Terrestrial Laser Scanner via 2-D Feature PointsIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2024.339292717(9324-9336)Online publication date: 2024
- Chung KChang W(2024)Centralized RANSAC-Based Point Cloud Registration With Fast Convergence and High AccuracyIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2024.336551617(5431-5442)Online publication date: 2024
- Show More Cited By
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Article
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
