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
Items 601–677 of 677
Visual Perception System for Randomized Picking Task
Zhan, B., Wang, X., Wu, J., Wang, S., & Li, A. (2018) · doi:10.1109/hfr.2018.8633526
Reconstrução tridimensional para objetos de herança virtual.
de Miranda, H. J. S. (2018) · doi:10.11606/d.3.2018.tde-12122018-084757
Color-Guided Coarse Registration Method Based on RGB-D Data
Su, B., Han, W., Peng, Y., & Sheng, M. (2017) · International Conference on Virtual Reality and Visualization · doi:10.1109/icvrv.2017.00108
Hrinivich, W. T., Park, S., Le, Y., Song, D. Y., & Lee, J. (2019) · Medical Physics · doi:10.1002/mp.13667
Registration of Botanic Tree Point Cloud Based on Pseudo Feature Point
Geng, N., Xu, J., Feng, X., Hu, S., Yang, L., & Zhang, Z. (2019) · Nicograph International (NicoInt) · doi:10.1109/nicoint.2019.00026
Automatic marker-free registration of tree point-cloud data based on rotating projectionPreprint
Xu, X., Wang, P., Gan, X., Li, Y., Zhang, L., Zhang, Q., Zhou, M., Zhao, Y., & Li, X. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.11192
Output Sensitive Algorithms for Approximate Incidences and Their ApplicationsPreprint
Aiger, D., Kaplan, H. Y., & Sharir, M. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2017.5
Self-citationEvaluation of 3D Registration Deep Learning Methods using Iterative Transformation Estimations
BOJANIC, D., Bartol, K., Petković, T., D'Apuzzo, N., & Pribanić, T. (2020) · International Conference on 3D Body Scanning Technologies (3DBST) · doi:10.15221/20.31
Effective multi-view registration of point sets based on student's t mixture modelPreprint
Ma, Y., Zhu, J., Li, Z., Tian, Z., & Li, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.07002
Value added 3D modelling of Laser scanned and photogrammetric data
Oliveira, J., de Oliveira, A. Q., Boavida, J., Catarino, L., Araújo, B. M., Pereira, J. M., & Jorge, J. A. (2021) · Eurographics · doi:10.2312/pt.20091220
Robust and Fast Registration for Lidar Odometry and Mapping
Liu, W., & Sun, W. (2021) · Smart innovation, systems and technologies · doi:10.1007/978-981-16-4039-1_10
Laga, H., Guo, Y., Tabia, H., Fisher, R. B., & Bennamoun, M. (2018) · Wiley eBooks · doi:10.1002/9781119405207.refs
3D Real-Time Modeling Based on Lidar for Circular Coal Bunker of Coal-Fired Enterprise
Li, S., Huang, Y., Zhao, Y., Li, W., & Bi, X. (2022) · Chemistry and Technology of Fuels and Oils · doi:10.1007/s10553-022-01350-2
Coarse Registration of Point Cloud Base on Deep Local Extremum Detection and Attentive DescriptionPreprint
Lu, H., & Nie, J. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.4088388
Coarse Registration of Point Cloud Base on Deep Local Extremum Detection and Attentive DescriptionPreprint
Lu, H., & Nie, J. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.4106324
Identifying surface points based on machine learning algorithms: a comprehensive analysis
Bulut, V. (2022) · Data Technologies and Applications · doi:10.1108/dta-06-2022-0243
3D Point Cloud Registration Method Based on Structural Matching of Feature Points
Wang, K., Li, J., Chen, Z., & Wang, J. (2022) · Communications in computer and information science · doi:10.1007/978-981-19-9198-1_45
Tang, F., Shen, C., An, A., & Wan, Y. (2022) · IEEE International Geoscience and Remote Sensing Symposium (IGARSS) · doi:10.1109/igarss46834.2022.9884791
Automatic Pairwise Coarse Registration of Terrestrial Point Clouds Using 3D Line Features
Fu, Y., Li, Z., Xiong, F., He, H. W., Deng, Y. M., & Wang, W. (2022) · IEEE Access · doi:10.1109/access.2022.3217498
Point Cloud Alignment Method Based on Improved ISS-ICP Algorithm
Xiang, J., Fan, W., Liu, P., & Wang, M. (2022) · International Conference on Information Communication and Signal Processing (ICICSP) · doi:10.1109/icicsp55539.2022.10050688
Research on test method of point cloud registration based on joint replacement
Xia, M., Liu, W., & Zhou, D. (2023) · International Conference on Consumer Electronics and Computer Engineering (ICCECE) · doi:10.1109/iccece58074.2023.10135295
Improvement of iterative closest point with edges of projected image
Wang, C. (2023) · Virtual Reality & Intelligent Hardware · doi:10.1016/j.vrih.2022.09.001
The 3D Point Cloud Registration Algorithm Based on Harris-DLFS
Cong, Z., Liu, Z., Zhu, J., Xiao, C. R., & Huang, Z. (2023) · Advances in Computer Signals and Systems · doi:10.23977/acss.2023.070614
Zheng, Y., Liu, X., Zhang, Y., Du, J., Xiao, X., & Li, Z. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4625859
Fahrendholz, J. L., & Brell‐Çokcan, S. (2024) · Springer eBooks · doi:10.1007/978-3-658-42544-9_21
Research on Low Overlap 3D Point Cloud Reconstruction Algorithm Based on Kinect Camera
Lian, Z., Wang, X., Lin, J., Wei, Y., Liu, M., & Tang, M. (2023) · China Automation Congress (CAC) · doi:10.1109/cac59555.2023.10450296
Enhanced SDRSAC Algorithm for Robust Registration on Non-Cooperative Targets
Wang, Z., Yi, J., Su, L., & Pan, Y. (2024) · IEEE International Conference on Power, Electronics and Computer Applications (ICPECA) · doi:10.1109/icpeca60615.2024.10471103
A noval weighted distance and local density double histogram used in 3D local feature description
Li, X., Ji, S., & Zhao, J. (2024) · Multimedia Tools and Applications · doi:10.1007/s11042-024-19141-8
Artificial intelligence-assisted restoration and visualization of knapped stone tools
Yang, X., & Li, F. (2024) · Prehistoric Archaeology · doi:10.3724/2097-3063.20240016
Coarse-to-fine heterogeneous point clouds registration in vehicle-to-infrastructure collaboration
Wu, F., Song, S., Gong, Y., Chen, J., Qin, Q., Sun, X., & Miao, Z. (2024) · Journal of Applied Remote Sensing · doi:10.1117/1.jrs.18.047504
Zhang, X., Peng, C., & Qiu, C. (2024) · Tenth International Conference on Information Optics and Photonics · doi:10.1117/12.3047165
Planar Feature Constrained Point Cloud Registration Method with Minimal Overlap Structure
Guo, H., Sha, J., Tan, C., & Chen, Y. (2024) · International Conference on Signal Processing · doi:10.1109/icsp62129.2024.10846600
Multi-Level Feature Extraction Point Cloud Registration Model Based on Cross-Attention Matrix
Chen, P., Cui, J., Bai, Y., & Dai, W. (2024) · China Automation Congress (CAC) · doi:10.1109/cac63892.2024.10865364
Shemu, M., Roster, M., Cope, L., Waggoner, J., Crowley, R. W., & Richardson, R. (2025) · Shore & Beach · doi:10.34237/1009313
Review on Robotic Grasping Pose Generation Methods
Zhu, M., Chen, Y., & Xiao, J. (2025) · Lecture notes in electrical engineering · doi:10.1007/978-981-96-2256-6_40
High-Accuracy Fractured Object Reassembly Under Arbitrary Poses
Xu, Q., Cao, Y., Cheng, W., Mu, T., Shan, Y., Yang, Y., & Hu, S. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-5812-1_11
Wang, M., Yang, Y., Chen, H., Tang, Q., Peng, X., & Liu, X. (2025) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2025.3584500
An Efficient Global‐to‐Local Rotation Optimization Approach via Spherical Harmonics
He, Z., Yang, Y., Deng, C., Lu, J., Guibas, L. J., & Qi-xing Huang, A. (2025) · Computer Graphics Forum · doi:10.1111/cgf.70185
Evaluation of the K4PCS Global Registration Algorithm
Stilinović, R., Šekoranja, B., & Šuligoj, F. (2025) · Mechanisms and machine science · doi:10.1007/978-3-032-02106-9_64
Upright-Net+: Enhanced Learning of Upright Orientation for 3D Point Clouds
Pang, X., Li, F., Zhuang, H., Ding, N., Zhong, X., He, S., Liu, W., & Jiang, B. (2025) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2025.3605201
Chang, X., Gao, Z., Hou, M., & Nallbani, A. (2025) · Research Square · doi:10.21203/rs.3.rs-7581306/v1
An Improved ICP Point Cloud Registration Method Based on Boundary Constraint Algorithm
Wang, Y., Wang, Z., Lei, X., & Liu, S. (2025) · IEEE International Conference on Cyber Technology in Automation, Control, and Intelligent Systems · doi:10.1109/cyber67662.2025.11168375
Partial Point Cloud Registration Based on Overlapping Region Extraction Using Deep Fusion Features
Wu, Z., Fang, Q., Peng, W., Ye, J., & Wang, Y. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11179214
3-D Reconstruction and Trajectory Planning for Real-Time Shoe Upper Glue Spraying System
Wang, T., Feng, W., Li, J., & Gao, J. (2025) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2025.3623792
Head 3D Reconstruction Method Based on Selected Feature Point and Global Registration
高, 也. (2025) · Modeling and Simulation · doi:10.12677/mos.2025.1410632
Point Cloud Registration Method for Bulk Cargo Hold Material Surface Based on RPMNet
Shen, Y., Gao, Z., Man, X., He, M., Li, X., & Mi, C. (2025) · International Conference on Industry 4.0 Technology (I4Tech) · doi:10.1109/i4tech64670.2025.11277586
A multiparameter functional for rotation and translation estimation in point cloud registration task
Makovetskii, A., Воронин, С., Kober, V. I., & Voronin, A. V. (2025) · Computational Mathematics and Modeling · doi:10.1007/s10598-025-09632-0
CGReg: Classification-Guided Point Cloud Registration via Equivariant Learning
Wu, Q., Yang, C., Fang, L., Zhang, D., & Zhonglong, Z. (2026) · Lecture notes in computer science · doi:10.1007/978-981-95-5737-0_6
Large-Scale Point Cloud Completion Through Registration and Fusion of Object-Level Reconstructions
He, T., Fang, Y., Li, K., & Yang, L. (2026) · Applied Sciences · doi:10.3390/app16010554
Chen, S., Deng, H., Han, J., Liu, C., Peng, J., & Wang, L. (2026) · Multimedia Systems · doi:10.1007/s00530-025-02157-x
HR-HEC: Heuristic-to-Refined Hand-Eye Calibration via Congruent Matching Sets
Liu, L., Wu, H., Hua, L., & Zhu, D. (2026) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2026.3664531
A point cloud registration method based on RGB-D information and voting mechanism
Huang, Y., Chen, J., Liu, M., & Wang, Z. (2026) · Measurement · doi:10.1016/j.measurement.2026.120989
3D Digital Modeling of Power Transformers Based on Morphology-Aware Registration Network
Qiubing, S. H. E. N., Zhao, Y., Yang, C., Zhang, Y., & Chen, H. (2026) · IEEE Transactions on Industry Applications · doi:10.1109/tia.2026.3675169
Yang, R., Li, F., Bai, J., & Du, J. (2026) · Measurement Science and Technology · doi:10.1088/1361-6501/ae5e9c
Point Cloud Registration Based on Geometry Biased Attention*
Wang, H., & Liu, C. (2026) · International Conference on Electronic Information Engineering, Big Data and Computer Technology (EIBDCT) · doi:10.1109/eibdct69742.2026.11566978
Fu, S., Shen, Y., Wang, J., Jiang, J., & Huang, J. (2026) · Tunnelling and Underground Space Technology · doi:10.1016/j.tust.2026.107867
Liu, Y., Xu, H. G., & Fu, Y.-K. (2026) · Neurocomputing · doi:10.1016/j.neucom.2026.134442
Guan, X., Luo, J., & Zhang, H. (2026) · Drones · doi:10.3390/drones10080606
A Multiview LiDAR Measurement for Robust Wheel Localization in Low-Overlap Smart Garage Environments
Sun, C., Liang, J., Li, X., Shi, J., Zhang, C., & Ding, J. (2026) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2026.3720847
Xiong, Z., & Li, Y. (2026) · Discover Computing · doi:10.1007/s10791-026-10410-8
GNSS Precise Point Positioning Enhanced Mobile Laser Scanning Railway Point Cloud Registration
Xiang, G., Li, H., Su, X., Li, Y., & Huang, L. (2026) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2026.3723381
Partial-Overlap Point Cloud Registration Based on Hierarchical Reliable CorrespondencesPreprint
Zhao, F., & Cui, Z. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.7309962
Geometry-Constrained Bidirectional Point Cloud Registration for Thin, Sheet-Like Heritage Artifacts
Zhang, Y., Wei, L., Du, J., & Wan, S. (2026) · Journal on Computing and Cultural Heritage · doi:10.1145/3836772
Tian, M., He, K., Yang, Z., Yuan, S., & Huang, J. (2026) · Neurocomputing · doi:10.1016/j.neucom.2026.134965
Liu, H., Dong, J., & Liu, B. (2026) · Applied Sciences · doi:10.3390/app16178760
Nc5-PCS Based Heterogeneous Point Cloud Matching for Roads
Liu, L., Yu, K., Li, X., Sun, G., Zhao, X., Zhu, D., Fan, Y., & Guo, S. (2026) · SAE technical papers on CD-ROM/SAE technical paper series · doi:10.4271/2026-99-1533
Su, H., Wang, H., Qi, X., Liu, T., & Li, B. (2026) · International Conference on Intelligent Systems and Robotics (CISR) · doi:10.1109/cisr70722.2026.11680100
Liu, H., Tang, S., Yi, F., Xia, H., & Li, Z. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.7493403
Hand-Eye Calibration in Robotic Machining: A Review of Challenges, Solutions, and Applications
Wu, H., Ding, T., Shi, Z., Hua, L., & Zhu, D. (2026) · Chinese Journal of Mechanical Engineering · doi:10.1016/j.cjme.2026.100404
Contour Feature-Driven Deep Learning Method for Arch Dam Point Cloud Registration
李宜靜, Fan, J., Li, H., Li, Y., Chen, P., & Zhong, P. (2026) · Journal of Computing in Civil Engineering · doi:10.1061/jccee5.cpeng-7756
Multi-view Point Cloud Registration Using Affine Shape Distributions
Du, J., Xiong, W., Chen, W., Cheng, J., Wang, Y., Gu, Y., & Chia, S.-C. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-16808-1_11
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
