Journal of Shandong University(Engineering Science) ›› 2019, Vol. 49 ›› Issue (2): 1-7.doi: 10.6040/j.issn.1672-3961.0.2018.244

• Machine Learning & Data Mining •     Next Articles

Fast 4-points congruent sets for coarse registration of 3D point cloud

Shiguang LIU1,2(),Hairong WANG1,Jin LIU1   

  1. 1. Division of Intelligence and Computing, Tianjin University, Tianjin 300350, Tianjin, China
    2. Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300350, Tianjin, China
  • Received:2018-06-07 Online:2019-04-20 Published:2019-04-19
  • Supported by:
    国家自然科学基金项目(61672375);国家自然科学基金项目(61170118);天津市自然科学基金项目(14JCQNJC00100)

RichHTML

155

PDF (PC)

3390

Abstract:

In order to solve the problem that the 4-points congruent sets (4 PCS) method suffered from low computational efficiency and high registration errors when the overlap rate of two pieces of input point clouds was low, fast 4-points congruent sets (F-4PCS) was put forward. A new method for selecting four-point basis was presented. The source point cloud and target point cloud were given, their boundaries were separately extracted and extended as the boundary feature bands, and then a consistent four-point basis set was chosen from the boundary feature bands. This method could avoid some unnecessary iterations. By limiting the characteristics of the four-point basis, the invalid four-point basis was removed, it could reduce the verification time of the algorithm and improve the computational efficiency. Experiments results carried out on the relevant data sets showed that the F-4PCS method was more efficient than conventional 4PCS method in the case of low overlap rate of input point clouds and the registration success rate was higher than state-of-the-arts.

Key words: point cloud, registration, feature, 4-point basis, 4PCS, F-4PCS

CLC Number: 

  • TP391.41

Fig.1

The 4-point basis and its representation"

Fig.2

Illustration of boundary extraction process"

Fig.3

Illustration of boundary extension to boundary feature belt"

Fig.4

Illustration of PFH feature calculation]"

Fig.5

The point cloud model of original input"

Fig.6

The point cloud registration results of the algorithm"

Fig.7

The point cloud registration results of Super-4PCS"

Fig.8

Comparison of running time among K-4PCS, Super-4PCS and the algorithm in this research"

Fig.9

Comparison of SR and RMSE between the paper algorithm and 4PCS"

Fig.10

The point cloud registration results of different noise points"

Fig.11

Registration results under noise interference"

1 伍龙华, 黄惠. 点云驱动的计算机图形学综述[J]. 计算机辅助设计与图形学学报, 2015, 27 (8): 1341- 1353.
doi: 10.3969/j.issn.1003-9775.2015.08.001
WU Longhua , HUANG Hui . Survey on points-driven computer graphics[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27 (8): 1341- 1353.
doi: 10.3969/j.issn.1003-9775.2015.08.001
2 韩宝昌, 曹俊杰, 苏志勋. 一种区域层次上的自动点云配准算法[J]. 计算机辅助设计与图形学学报, 2015, 27 (2): 313- 319.
HAN Baochang , CAO Junjie , SU Zhixun . Automatic point clouds registration based on regions[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27 (2): 313- 319.
3 孙家泽, 陈皓, 耿国华. 三维文物点云模型配准优化算法[J]. 计算机辅助设计与图形学学报, 2016, 28 (7): 1068- 1074.
doi: 10.3969/j.issn.1003-9775.2016.07.005
SUN Jiaze , CHEN Hao , GENG Guohua . Registration optimization algorithm for 3D cultural relics point clouds model[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28 (7): 1068- 1074.
doi: 10.3969/j.issn.1003-9775.2016.07.005
4 BESL P J , MCKAY N D . A method for registration of 3-D shapes[J]. IEEE Transactions Pattern Analysis Machine Intelligence, 1992, 14 (2): 239- 256.
doi: 10.1109/34.121791
5 CHEN Y , MEDIONI G . Object modelling by registration of multiple range images[J]. Image & Vision Computing, 1992, 10 (3): 145- 155.
6 BERGEVIN R , SOUCY M , GAGNON H , et al. Towards a general multi-view registration technique[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1996, 18 (5): 540- 547.
7 BEA K H. Automated registration of unorganized point cloudsfrom terrestrial laser scanners[D]. Perth, Australia: Curtin University of Technology, 2006.
8 MINGUEZ J , MONTESANO L , LAMIRAUX F . Metric-based iterative closest point scan matching for sensor displacement estimation[J]. IEEE Transactions on Robotics, 2006, 22 (5): 1047- 1054.
doi: 10.1109/TRO.2006.878961
9 CENSI A. An ICP variant using a point-to-line metric[C]//IEEE International Conference on Robotics and Automation. Pasadena, USA: IEEE, 2008: 19-25.
10 杨玲, 谯舟三, 陈玲玲, 等. 结合Procrustes分析法和ICP算法的PICP配准算法[J]. 计算机辅助设计与图形学学报, 2017, 29 (2): 337- 343.
doi: 10.3969/j.issn.1003-9775.2017.02.016
YANG Ling , QIAO Zhousan , CHEN Lingling , et al. PICP Registration method based on procrustes analysis and ICP algorithm[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29 (2): 337- 343.
doi: 10.3969/j.issn.1003-9775.2017.02.016
11 POTTMANN H , HUANG Q X , YANG Y L , et al. Geometry and convergence analysis of algorithms for registration of 3D shapes[J]. International Journal of Computer Vision, 2006, 67 (3): 277- 296.
12 YANG J , LI H , CAMPBELL D , et al. Go-ICP: a globally optimal solution to 3D ICP Point-Set registration[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2016, 38 (11): 2241- 2254.
13 ZHOU Q Y, PARK J, KOLTUN V. Fast global registration[C]//European Conference on Computer Vision. Springer International Publishing. Amsterdam, Netherlands: Springer, 2016: 766-782.
14 JOHNSON A. Spin-Images: a representation for 3-D surface matching[D]. Pittsburgh, USA: Carnegie Mellon University, 1997.
15 LI X, GUSKOV I. Multi-scale features for approximate alignment of point-based surfaces[C]//Eurographics Symposium on Geometry Processing. Vienna, Austria: Eurographics Association, 2005: 217.
16 CHUA C S, HAN F, HO Y K. 3D human face recognition using point signature[C]//Proceedings of IEEE International Conference on Automatic Face and Gesture Recognition, 2000. Grenoble, France: IEEE, 2000: 233-238.
17 KAICK O V , ZHANG H , HAMARNEH G , et al. A survey on shape correspondence[J]. Computer Graphics Forum, 2011, 30 (6): 1681- 1707.
doi: 10.1111/cgf.2011.30.issue-6
18 HORN B K P . Closed-form solution of absolute orientation using unit quaternions[J]. Journal of the Optical Society of America A, 1987, 5 (7): 1127- 1135.
19 IRANI S , RAGHAVAN P . Combinatorial and experimental results for randomized point matching algorithms[J]. Computational Geometry, 1999, 12 (1/2): 17- 31.
20 FISCHLER M A , BOLLES R C . Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Comm of the Acm, 1987, 24 (6): 726- 740.
21 AIGER D , MITRA N J , COHENOR D . 4-points congruent sets for robust pairwise surface registration[J]. Acm Transactions on Graphics, 2011, 27 (3): 1- 10.
22 THEILER P W , WEGNER J D , SCHINDLER K . Keypoint-based 4-points congruent sets: automated marker-less registration of laser scans[J]. Isprs Journal of Photogrammetry & Remote Sensing, 2014, 96 (11): 149- 163.
23 THEILER P W , WEGNER J D , SCHINDLER K . Markerless point cloud registration with keypoint-based 4-points congruent sets[J]. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2013, 1 (2): 283- 288.
24 MELLADEO N , AIGER D , MITRA N J . Super 4PCS fast global pointcloud registration via smart indexing[J]. Computer Graphics Forum, 2015, 33 (5): 205- 215.
25 MOHAMAD M, RAPPAPORT D, GREENSPAN M. Generalized 4-Points congruent sets for 3D registration[C]//International Conference on 3d Vision. Tokyo, Japan: IEEE, 2015: 83-90.
26 SILVA J P D J, BORGES D L, FLAVIO D B V. A dynamic approach for approximate pairwise alignment based on 4-points congruence sets of 3D points[C]//IEEE International Conference on Image Processing. Brussels, Belgium: IEEE, 2011: 889-892.
27 RUSU R B, COUSINS S. 3D is here: point cloud library (PCL)[C]//IEEE International Conference on Robotics and Automation. Shanghai, China: IEEE, 2011: 1-4.
[1] TANG Jiefeng, ZHANG Jia, LONG Jinyi. Fast multi-label feature selection method based on global redundancy minimization [J]. Journal of Shandong University(Engineering Science), 2025, 55(6): 21-34.
[2] WANG Yuou, YUAN Yingchun, HE Zhenxue, HE Chen. University academic named entity recognition based on the fusion of multi-feature and multi-head self-attention mechanism [J]. Journal of Shandong University(Engineering Science), 2025, 55(6): 35-44.
[3] ZHOU Zunfu, ZHANG Qian, SHI Jiliang, YUE Shiqin. Face image inpainting based on texture and structure interaction [J]. Journal of Shandong University(Engineering Science), 2025, 55(4): 18-28.
[4] WU Qiulan, SHANG Suya, ZHANG Jiahui, SUN Shouxin, ZHANG Feng, ZHOU Bo, GAO Zheng, SHI Wenchong. Semantic segmentation method for potato common scab images based on multiscale feature fusion [J]. Journal of Shandong University(Engineering Science), 2025, 55(4): 1-8.
[5] SUO Daxiang, LI Bo. Photovoltaic defect detection based on fine-grained feature enhancement and scale matching [J]. Journal of Shandong University(Engineering Science), 2025, 55(4): 9-17.
[6] LI Feng, WEN Yimin. Multi-scale visual and textual semantic feature fusion for image captioning [J]. Journal of Shandong University(Engineering Science), 2025, 55(3): 80-87.
[7] Ying LI,Jiankun WANG. The classification of mild cognitive impairment based on supervised graph regularization and information fusion [J]. Journal of Shandong University(Engineering Science), 2023, 53(4): 65-73.
[8] Caihui LIU,Qi ZHOU,Xiaowen YE. An intrusion detection model based on improved ReliefF algorithm [J]. Journal of Shandong University(Engineering Science), 2023, 53(2): 1-10.
[9] FU Guixia, ZOU Guofeng, MAO Shuai, PAN Jinfeng, YIN Liju. Small sample person re-identification combining Gabor features and convolution features [J]. Journal of Shandong University(Engineering Science), 2021, 51(3): 22-29.
[10] Chunhong CAO,Hongxuan DUAN,Ling CAO,Lele ZHANG,Kai HU,Fen XIAO. Real-time semantic segmentation of high-resolution remote sensing image based on multi-level feature cascade [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 19-25.
[11] LIN Xiaowei, CHEN Lifei. Community detection using nonnegative matrix factorization with structure extension [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 57-64.
[12] ZHENG Zijun, FENG Xiang, YU Huiqun, LI Xiuquan. Dynamic prediction of spatiotemporal big data based on relationship transfer and reinforcement learning [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 105-114.
[13] WU Zhengjian, MUTALLIP Mamut, HORNISA Mamat, ALIM Aysa, KURBAN Ubul. Script identification of Central Asian document images based on LTP and HOG texture feature fusion [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 115-121.
[14] Zhuoyu XIAO,Pei HE,Guo CHEN,Yunbiao XU,Jie GUO. Design pattern classification mining with feature metrics constraints [J]. Journal of Shandong University(Engineering Science), 2020, 50(6): 48-58.
[15] Yan PENG,Tingting FENG,Jie WANG. An integrated learning approach for O3 mass concentration prediction model [J]. Journal of Shandong University(Engineering Science), 2020, 50(4): 1-7.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] ZHANG Yong-hua,WANG An-ling,LIU Fu-ping . The reflected phase angle of low frequent inhomogeneous[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 22 -25 .
[2] KONG Xiang-zhen,LIU Yan-jun,WANG Yong,ZHAO Xiu-hua . Compensation and simulation for the deadband of the pneumatic proportional valve[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 99 -102 .
[3] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[4] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[5] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[6] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
[7] QIN Tong, SUN Fengrong*, WANG Limei, WANG Qinghao, LI Xincai. 3D surface reconstruction using the shape based interpolation guided by maximal discs[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 1 -5 .
[8] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[9] SUN Dianzhu, ZHU Changzhi, LI Yanrui. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 84 -86 .
[10] HU Tian-liang,LI Peng,ZHANG Cheng-rui,ZUO Yi . Design of a QEP decode counter based on VHDL[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 10 -13 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd