{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:16:45Z","timestamp":1760235405918,"version":"build-2065373602"},"reference-count":56,"publisher":"MDPI AG","issue":"16","license":[{"start":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T00:00:00Z","timestamp":1628812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Remote Sensing"],"abstract":"<jats:p>With the acceleration in three-dimensional (3D) high-frame-rate sensing technologies, dense point clouds collected from multiple standpoints pose a great challenge for the accuracy and efficiency of registration. The combination of coarse registration and fine registration has been extensively promoted. Unlike the requirement of small movements between scan pairs in fine registration, coarse registration can match scans with arbitrary initial poses. The state-of-the-art coarse methods, Super 4-Points Congruent Sets algorithm based on the 4-Points Congruent Sets, improves the speed of registration to a linear order via smart indexing. However, the lack of reduction in the scale of original point clouds limits the application. Besides, the coplanarity of registration bases prevents further reduction of search space. This paper proposes a novel registration method called the Super Edge 4-Points Congruent Sets to address the above problems. The proposed algorithm follows a three-step procedure, including boundary segmentation, overlapping regions extraction, and bases selection. Firstly, an improved method based on vector angle is used to segment the original point clouds aiming to thin out the scale of the initial point clouds. Furthermore, overlapping regions extraction is executed to find out the overlapping regions on the contour. Finally, the proposed method selects registration bases conforming to the distance constraints from the candidate set without consideration about coplanarity. Experiments on various datasets with different characteristics have demonstrated that the average time complexity of the proposed algorithm is improved by 89.76%, and the accuracy is improved by 5 mm on average than the Super 4-Points Congruent Sets algorithm. More encouragingly, the experimental results show that the proposed algorithm can be applied to various restrictive cases, such as few overlapping regions and massive noise. Therefore, the algorithm proposed in this paper is a faster and more robust method than Super 4-Points Congruent Sets under the guarantee of the promised quality.<\/jats:p>","DOI":"10.3390\/rs13163210","type":"journal-article","created":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T09:22:38Z","timestamp":1628846558000},"page":"3210","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Super Edge 4-Points Congruent Sets-Based Point Cloud Global Registration"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8314-4610","authenticated-orcid":false,"given":"Shikun","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematics & Statistics, Shandong University, Weihai 264209, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruodan","family":"Lu","sequence":"additional","affiliation":[{"name":"Darwin College, University of Cambridge, Cambridge CB3 9EU, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianya","family":"Liu","sequence":"additional","affiliation":[{"name":"Data Science Institute, Shandong University, Jinan 250100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liang","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Mathematics & Statistics, Shandong University, Weihai 264209, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,13]]},"reference":[{"key":"ref_1","first-page":"586","article-title":"Method for registration of 3-d shapes. Sensor Fusion IV: Control Paradigms and Data Structures","volume":"1611","author":"Besl","year":"1992","journal-title":"Int. Soc. Opt. Photonics"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Aiger, D., Mitra, N.J., and Cohen-Or, D. (2008). 4-Points Congruent Sets for Robust Pairwise Surface Registration, Association for Computing Machinery. ACM SIGGRAPH 2008 Papers.","DOI":"10.1145\/1399504.1360684"},{"key":"ref_3","first-page":"5","article-title":"Super 4pcs fast global pointcloud registration via smart indexing","volume":"33","author":"Nicolas","year":"2014","journal-title":"Comput. Graph. Forum"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1115\/1.4037477","article-title":"V4pcs: Volumetric 4pcs algorithm for global registration","volume":"139","author":"Huang","year":"2017","journal-title":"J. Mech. Des."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/358669.358692","article-title":"Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography","volume":"24","author":"Fischler","year":"1981","journal-title":"Commun. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s12518-020-00308-5","article-title":"A framework for registration of multiple point clouds derived from a static terrestrial laser scanner system","volume":"12","author":"Miola","year":"2020","journal-title":"Appl. Geomat."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.isprsjprs.2019.02.015","article-title":"Pairwise coarse registration of point clouds in urban scenes using voxel-based 4-planes congruent sets","volume":"151","author":"Xu","year":"2009","journal-title":"ISPRS J. Photogramm. Remote. Sens."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"045024","DOI":"10.1117\/1.JRS.10.045024","article-title":"Improved algorithm for point cloud registration based on fast point feature histograms","volume":"10","author":"Li","year":"2016","journal-title":"J. Appl. Remote Sens."},{"key":"ref_9","first-page":"3614","article-title":"Fast descriptors and correspondence propagation for robust global point cloud registration","volume":"26","author":"Lei","year":"2017","journal-title":"IEEE Trans. Image Process."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3261","DOI":"10.1109\/TIP.2017.2695888","article-title":"A systematic approach for cross-source point cloud registration by preserving macro and micro structures","volume":"26","author":"Huang","year":"2017","journal-title":"IEEE Trans. Image Process."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Makovetskii, A., Voronin, S., Kober, V., and Voronin, A. (2020). A regularized point cloud registration approach for orthogonal transformations. J. Glob. Optim., 1\u201323.","DOI":"10.1007\/s10898-020-00934-8"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/j.isprsjprs.2006.09.006","article-title":"An integrated approach for modelling and global registration of point clouds","volume":"61","author":"Rabbani","year":"2007","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.patrec.2015.07.019","article-title":"A modified icp algorithm based on dynamic adjustment factor for registration of point cloud and cad model","volume":"65","author":"Li","year":"2015","journal-title":"Pattern Recognit. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Prokop, M., Shaikh, S.A., and Kim, K. (2020). Low overlapping point cloud registration using line features detection. Remote Sens., 12.","DOI":"10.3390\/rs12010061"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Zhang, X., Yang, B., Li, Y., Zuo, C., Wang, X., and Zhang, W. (2018). A method of partially overlapping point clouds registration based on differential evolution algorithm. PLoS ONE, 13.","DOI":"10.1371\/journal.pone.0209227"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.isprsjprs.2007.05.012","article-title":"A method for automated registration of unorganised point clouds","volume":"63","author":"Bae","year":"2008","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"100120","DOI":"10.1109\/ACCESS.2020.2995369","article-title":"A local feature descriptor based on rotational volume for pairwise registration of point clouds","volume":"8","author":"Fengguang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.isprsjprs.2013.02.019","article-title":"Towards 3d lidar point cloud registration improvement using optimal neighborhood knowledge","volume":"79","author":"Gressin","year":"2013","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"04017076","DOI":"10.1061\/(ASCE)CP.1943-5487.0000720","article-title":"Automated point cloud registration using visual and planar features for construction environments","volume":"32","author":"Kim","year":"2018","journal-title":"J. Comput. Civil Eng."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1016\/j.autcon.2013.01.004","article-title":"Development of optimized point cloud merging algorithms for accurate processing to create earthwork site models","volume":"35","author":"Kwon","year":"2013","journal-title":"Autom. Constr."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1016\/j.autcon.2013.01.005","article-title":"Fully automated registration of 3d data to a 3d cad model for project progress monitoring","volume":"35","author":"Kim","year":"2013","journal-title":"Autom. Constr."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0262-8856(92)90066-C","article-title":"Object modelling by registration of multiple range images","volume":"10","author":"Chen","year":"1992","journal-title":"Image Vis. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/rob.21490","article-title":"Mapping, planning, and sample detection strategies for autonomous exploration","volume":"31","author":"Das","year":"2014","journal-title":"J. Field Robot."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/MRA.2015.2432331","article-title":"Registration with the point cloud library: A modular framework for aligning in 3-d","volume":"22","author":"Holz","year":"2015","journal-title":"IEEE Robot. Autom. Mag."},{"key":"ref_25","first-page":"435","article-title":"Generalized-icp","volume":"2","author":"Segal","year":"2009","journal-title":"Robotics Sci. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Agamennoni, G., Fontana, S., Siegwart, R.Y., and Sorrenti, D.G. (2016, January 9\u201314). Point clouds registration with probabilistic data association. Proceedings of the 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, Korea.","DOI":"10.1109\/IROS.2016.7759602"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10514-013-9327-2","article-title":"Comparing icp variants on real-world data sets","volume":"34","author":"Pomerleau","year":"2013","journal-title":"Auton. Robot."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2241","DOI":"10.1109\/TPAMI.2015.2513405","article-title":"Go-icp: A globally optimal solution to 3d icp point-set registration","volume":"38","author":"Yang","year":"2015","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Stechschulte, J., Ahmed, N., and Heckman, C. (2019, January 20\u201324). Robust low-overlap 3-d point cloud registration for outlier rejection. Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada.","DOI":"10.1109\/ICRA.2019.8793857"},{"key":"ref_30","unstructured":"Rusinkiewicz, S., and Levoy, M. (June, January 28). Efficient variants of the icp algorithm. Proceedings of the Proceedings Third International Conference on 3-D Digital Imaging and Modeling, Quebec City, QC, Canada."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1111\/cgf.12178","article-title":"Sparse iterative closest point","volume":"Volume 32","author":"Bouaziz","year":"2013","journal-title":"Computer Graphics Forum"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/LGRS.2018.2872353","article-title":"Multiscale sparse features embedded 4-points congruent sets for global registration of tls point clouds","volume":"16","author":"Xu","year":"2018","journal-title":"IEEE Geosci. Remote. Sens. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"73637","DOI":"10.1109\/ACCESS.2019.2919989","article-title":"Point cloud registration based on mcmc-sa icp algorithm","volume":"7","author":"Liu","year":"2019","journal-title":"IEEE Access"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"699","DOI":"10.14358\/PERS.71.6.699","article-title":"Photogrammetric and lidar data registration using linear features","volume":"71","author":"Habib","year":"2005","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"ref_35","first-page":"57","article-title":"Comparison of 3d interest point detectors and descriptors for point cloud fusion","volume":"2","author":"Weber","year":"2014","journal-title":"ISPRS Ann. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Rosten, E., and Drummond, T. (2006). Machine learning for high-speed corner detection. European Conference on Computer Vision, Springer.","DOI":"10.1007\/11744023_34"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/j.cviu.2007.09.014","article-title":"Speeded-up robust features (surf)","volume":"110","author":"Bay","year":"2008","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Rublee, E., Rabaud, V., Konolige, K., and Bradski, G. (2011, January 6\u201313). Orb: An efficient alternative to sift or surf. Proceedings of the 2011 International Conference on Computer Vision, Barcelona, Spain.","DOI":"10.1109\/ICCV.2011.6126544"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.isprsjprs.2014.05.012","article-title":"Automated registration of dense terrestrial laser-scanning point clouds using curves","volume":"95","author":"Yang","year":"2014","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_40","first-page":"1091","article-title":"Automatic matching of terrestrial scan data as a basis for the generation of detailed 3d city models","volume":"35","author":"Dold","year":"2004","journal-title":"Int. Arch. Photogramm. Remote Sens."},{"key":"ref_41","first-page":"84","article-title":"Automatic relative orientation of terrestrial laser scans using planar structures and angle constraints","volume":"200","author":"Brenner","year":"2007","journal-title":"ISPRS Workshop Laser Scanning"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.aei.2011.08.009","article-title":"Plane-based registration of construction laser scans with 3d\/4d building models","volume":"26","year":"2012","journal-title":"Adv. Eng. Informatics"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.autcon.2012.04.011","article-title":"Coregistration of terrestrial lidar points by adaptive scale-invariant feature transformation with constrained geometry","volume":"25","author":"Dam","year":"2012","journal-title":"Autom. Constr."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2270","DOI":"10.1109\/TPAMI.2014.2316828","article-title":"3d object recognition in cluttered scenes with local surface features: A survey","volume":"36","author":"Guo","year":"2014","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.autcon.2018.01.014","article-title":"4-plane congruent sets for automatic registration of as-is 3d point clouds with 3d bim models","volume":"89","author":"Bueno","year":"2018","journal-title":"Autom. Constr."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"7539","DOI":"10.1109\/ACCESS.2020.2963984","article-title":"Global adaptive 4-points congruent sets registration for 3d indoor scenes with robust estimation","volume":"8","author":"Sun","year":"2020","journal-title":"IEEE Access"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Mohamad, M., Rappaport, D., and Greenspan, M. (2014, January 8\u201311). Generalized 4-points congruent sets for 3d registration. Proceedings of the 2014 2nd International Conference on 3D Vision, Tokyo, Japan.","DOI":"10.1109\/3DV.2014.21"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Mohamad, M., Ahmed, M.T., Rappaport, D., and Greenspan, M. (2015, January 19\u201322). Super generalized 4pcs for 3d registration. Proceedings of the 2015 International Conference on 3D Vision, Lyon, France.","DOI":"10.1109\/3DV.2015.74"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.isprsjprs.2014.06.015","article-title":"Keypoint-based 4-points congruent sets\u2013automated marker-less registration of laser scans","volume":"96","author":"Theiler","year":"2014","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/j.isprsjprs.2017.06.011","article-title":"Automatic markerless registration of point clouds with semantic-keypoint-based 4-points congruent sets","volume":"130","author":"Ge","year":"2017","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_51","unstructured":"Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D. (2001, January 7\u201311). Matching 3d models with shape distributions. Proceedings of the Proceedings International Conference on Shape Modeling and Applications, Genova, Italy."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Wohlkinger, W., and Vincze, M. (2011, January 7\u201311). Ensemble of shape functions for 3d object classification. Proceedings of the 2011 IEEE International Conference on Robotics and Biomimetics, Karon Beach, Thailand.","DOI":"10.1109\/ROBIO.2011.6181760"},{"key":"ref_53","unstructured":"(2021, April 20). The Dataset of Super 4pcs Algorithm. Available online: http:\/\/geometry.cs.ucl.ac.uk\/projects\/2014\/super4PCS\/."},{"key":"ref_54","unstructured":"(2021, April 20). The Stanford 3d Scanning Repository. Available online: http:\/\/graphics.stanford.edu\/data\/3Dscanrep\/."},{"key":"ref_55","unstructured":"(2021, April 20). Autonomous Systems Lab Datasets. Available online: https:\/\/projects.asl.ethz.ch\/datasets."},{"key":"ref_56","unstructured":"(2021, April 20). The Datasets of Princeton University. Available online: http:\/\/modelnet.cs.princeton.edu\/."}],"container-title":["Remote Sensing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2072-4292\/13\/16\/3210\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:45:32Z","timestamp":1760165132000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2072-4292\/13\/16\/3210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,13]]},"references-count":56,"journal-issue":{"issue":"16","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["rs13163210"],"URL":"https:\/\/doi.org\/10.3390\/rs13163210","relation":{},"ISSN":["2072-4292"],"issn-type":[{"type":"electronic","value":"2072-4292"}],"subject":[],"published":{"date-parts":[[2021,8,13]]}}}