The DOI matches its Crossref record; 29 of the 30 references it cites were found in a registry or an index.
4-points congruent sets for robust pairwise surface registration
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(n 2 + 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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“[4] which can handle up to 40% outliers, and down to 40% overlap as demonstrated in their experiments.”
From Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013) · cites this paper as [4]
In the citing paper
“Given two surfaces P and Q in arbitrary initial poses, [4] randomly selects a 4-point tuple from P and another 4-point tuple from Q, and compares the affine ratios.If they form a correspondence, their affine ratio will match.”
From Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013) · cites this paper as [4]
In the citing paper
“These transformations are similar to the domain theory in analytical learning-a global rule, one reason why these techniques can be cast as optimization problems and solved using the Hough transform [17], [39] or RANSAC technique [4], [71] efficiently.”
From Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013) · cites this paper as [4]
Citations
Cites
Fischler, M. A., & Bolles, R. C. (1981) · Communications of the ACM · doi:10.1145/358669.358692 · Cited by 25,893
A Method for Registration of 3-D Shapes
Besl, P., & Mckay, N. D. (1992) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.121791 · Cited by 22,163
Generalizing the Hough transform to detect arbitrary shapes
Ballard, D. H. (1981) · Pattern Recognition · doi:10.1016/0031-3203(81)90009-1 · Cited by 4,434
Closed-form solution of absolute orientation using unit quaternions
Horn, B. K. P. (1987) · Journal of the Optical Society of America A · doi:10.1364/josaa.4.000629 · Cited by 4,165
Efficient variants of the ICP algorithm
Rusinkiewicz, S., & Levoy, M. (2002) · Proceedings Third International Conference on 3-D Digital Imaging and Modeling · doi:10.1109/im.2001.924423 · Cited by 3,945
Object modelling by registration of multiple range images
Chen, Y., & Medioni, G. G. (1992) · Image and Vision Computing · doi:10.1016/0262-8856(92)90066-c · Cited by 3,209
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,290
Recognizing Objects in Range Data Using Regional Point Descriptors
Frome, A., Huber, D., Kolluri, R. K., Bülow, T., & Malik, J. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24672-5_18 · Cited by 907
Geometric hashing: an overview
Wolfson, H. J., & Rigoutsos, I. (1997) · IEEE Computational Science and Engineering · doi:10.1109/99.641604 · Cited by 562
Gelfand, N., Mitra, N. J., Guibas, L., & Pottmann, H. (2005) · doi:10.2312/sgp/sgp05/197-206 · Cited by 545
Self-citation
Research works printed but not linked: 1
- 10.1109/3DPVT.2004.107 · DOI
Cited by
Sorted by citations
Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration
Yang, J., Li, H., Campbell, D., & Jia, Y. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2513405 · Cited by 1,212
Zhou, Q.-Y., Park, J., & Koltun, V. (2016) · European Conference on Computer Vision · doi:10.1007/978-3-319-46475-6_47 · Cited by 1,184
Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid
Tam, G. K. L., Cheng, Z.-Q., Lai, Y.-K., Langbein, F. C., Liu, Y., Marshall, D., Martin, R. R., Sun, X.-F., & Rosin, P. L. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2012.310 · Cited by 679
Robust reconstruction of indoor scenes
Choi, S., Zhou, Q.-Y., & Koltun, V. (2015) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2015.7299195 · Cited by 652
Super 4PCS Fast Global Pointcloud Registration via Smart Indexing
Mellado, N., Aiger, D., & Mitra, N. J. (2014) · Computer Graphics Forum · doi:10.1111/cgf.12446 · Cited by 628
Self-citation
Metadata
- Authors
- Aiger, D., Mitra, N. J., & Cohen-Or, D.
- Affiliations
- Ben-Gurion University of the Negev (IL)
- TU Wien (AT)
- Tel Aviv University
- ORCID
- Mitra, Niloy J.
- Venue
- ACM Transactions on Graphics
- Published
- 2008-08
- Volume
- 27
- Issue
- 3
- Pages
- 1-10
- ISSN
- 0730-0301 (ISSN-L)
- 1557-7368
- OpenAlex
- W2064499898
- Cited by
- 677
- References
- 30
- Citations by year
- 2026: 27 · 2025: 36 · 2024: 51 · 2023: 50 · 2022: 47 · 2021: 53 · 2020: 64 · 2019: 65 · 2018: 46 · 2017: 53 · 2016: 30 · 2015: 38 · 2014: 26 · 2013: 21 · 2012: 23
- FWCI
- 16.03
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- ACM Transactions on Graphics (publishedVersion)
- HAL (submittedVersion)
- UCL Discovery (University College London) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › 3D Shape Modeling and Analysis
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
- Keywords
- rigid transformation, outlier robustness, noise robustness, similarity transformation, affine transformation, range scans, local descriptors
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
