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

150

PDF (PC)

1533

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] Xu YANG,Hui CHEN,Yousi LIN,Changhe TU. Automatic landmarks identification and tracking of bat flight [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 67-73.
[2] Jiachen WANG,Xianghong TANG,Jianguang LU. Research onfeature selection technology in bearing fault diagnosis [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 80-87, 95.
[3] Lizhao LI,Guoyong CAI,Jiao PAN. A microblog rumor events detection method based on C-GRU [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 102-106, 115.
[4] Tong LI,Ran MA,Honghe ZHENG,Ping AN,Xiangyu HU. An error sensitivity model based on video statistical features [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 116-121.
[5] Yunyang YAN,Huizhen ZHANG,Yi′an LIU,Shangbing GAO. Video flame detection based on GMM and 3D-LBP feature [J]. Journal of Shandong University(Engineering Science), 2019, 49(1): 1-9.
[6] Jun FAN,Qiaolin YE,Ning YE. Face recognition based on improved prameter-free supervised localitypreserving projections [J]. Journal of Shandong University(Engineering Science), 2019, 49(1): 10-16.
[7] Rongxiang ZHOU,Xiuyi JIA. Features analysis for Chinese irony detection [J]. Journal of Shandong University(Engineering Science), 2019, 49(1): 41-46.
[8] Wenwen QUAN,Mingxing LIN. Algorithm of underwater target recognition based on CNN features with BOF [J]. Journal of Shandong University(Engineering Science), 2019, 49(1): 107-113.
[9] Hong CHEN,Xiaofei YANG,Qing WAN,Yingcang MA. Multi-label feature selection algorithm based on correntropy andmanifold learning [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 27-36.
[10] Xing LI,Zhenjie HOU,Jiuzhen LIANG,Xingzhi CHANG. Multi-node human behavior recognition based on linear acceleration [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 56-66.
[11] Dongbo ZHANG,Tao KOU,Haixia XU. Fast scene recognition based on LDB descriptor and local spatial structure matching [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 16-23.
[12] Lianming MOU. Weighted k sub-convex-hull classifier based on adaptive feature selection [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 32-37.
[13] Pu ZHANG,Chang LIU,Yong WANG. Suggestion sentence classification model based on feature fusion and ensemble learning [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 47-54.
[14] Guoxin WANG,Fengdong CHEN,Guodong LIU. Feature extraction method of color pseudo-random coded structured light [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 55-60.
[15] Jianping HU,Xin LI,Qi XIE,Ling LI,Daochang ZHANG. An unconstrained optimization EMD approach in 2D based on Delaunay triangulation [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 9-15, 37.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WANG Su-yu,<\sup>,AI Xing<\sup>,ZHAO Jun<\sup>,LI Zuo-li<\sup>,LIU Zeng-wen<\sup> . Milling force prediction model for highspeed end milling 3Cr2Mo steel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 1 -5 .
[2] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[3] LI Liang, LUO Qiming, CHEN Enhong. Graph-based ranking model for object-level search
[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 15 -21 .
[4] 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 .
[5] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 27 -32 .
[6] 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 .
[7] LIU Wen-liang, ZHU Wei-hong, CHEN Di, ZHANG Hong-quan. Detection and tracking of moving targets using the morphology match in radar images[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 31 -36 .
[8] SUN Guohua, WU Yaohua, LI Wei. The effect of excise tax control strategy on the supply chain system performance[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 63 -68 .
[9] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
[10] SUN Dianzhu, ZHU Changzhi, LI Yanrui. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 84 -86 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd