快速四点一致性点云粗配准算法

doi:10.6040/j.issn.1672-3961.0.2018.244

摘要/Abstract

摘要：

为了解决四点全等集合(4-points congruent sets, 4PCS)在两片点云重叠率较低的情况下算法耗时长且配准容易失败的问题,提出快速四点一致性集合(fast 4-points congruent sets, F-4PCS)解决点云配准问题。给出一种新的选择四点基的方法,给定源点云和目标点云,分别提取出它们的边界,将边界扩展为边界特征带,在边界特征带中选取具有一致性的四点基集合,从而避免一些不必要的迭代。通过对四点基的特征限制,去除无效的四点基,减少算法的验证时间,提高计算效率。在相关数据集上的试验表明,在点云重叠率较低等情况下F-4PCS方法比4PCS方法更加高效且配准成功率较高。

关键词: 点云, 配准, 特征, 四点基, 4PCS, F-4PCS

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

中图分类号:

TP391.41

刘世光,王海荣,刘锦. 快速四点一致性点云粗配准算法[J]. 山东大学学报 (工学版), 2019, 49(2): 1-7.

Shiguang LIU,Hairong WANG,Jin LIU. Fast 4-points congruent sets for coarse registration of 3D point cloud[J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 1-7.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

参考文献 27

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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	杨煦,陈辉,林游思,屠长河. 飞行蝙蝠标记自动提取与追踪算法[J]. 山东大学学报 (工学版), 2019, 49(2): 67-73.
[2]	汪嘉晨,唐向红,陆见光. 轴承故障诊断中特征选取技术[J]. 山东大学学报 (工学版), 2019, 49(2): 80-87, 95.
[3]	李力钊,蔡国永,潘角. 基于C-GRU的微博谣言事件检测方法[J]. 山东大学学报 (工学版), 2019, 49(2): 102-106, 115.
[4]	李童,马然,郑鸿鹤,安平,胡翔宇. 基于视频统计特征的差错敏感度模型[J]. 山东大学学报 (工学版), 2019, 49(2): 116-121.
[5]	严云洋,张慧珍,刘以安,高尚兵. 基于GMM与三维LBP纹理的视频火焰检测[J]. 山东大学学报 (工学版), 2019, 49(1): 1-9.
[6]	范君,业巧林,业宁. 基于改进的有监督无参局部保持投影算法的人脸识别[J]. 山东大学学报 (工学版), 2019, 49(1): 10-16.
[7]	周荣翔,贾修一. 中文反语识别特征分析[J]. 山东大学学报 (工学版), 2019, 49(1): 41-46.
[8]	陈红,杨小飞,万青,马盈仓. 基于相关熵和流形学习的多标签特征选择算法[J]. 山东大学学报 (工学版), 2018, 48(6): 27-36.
[9]	李兴,侯振杰,梁久祯,常兴治. 基于线性加速度的多节点人体行为识别[J]. 山东大学学报 (工学版), 2018, 48(6): 56-66.
[10]	张东波,寇涛,许海霞. 基于LDB描述子和局部空间结构匹配的快速场景辨识[J]. 山东大学学报 (工学版), 2018, 48(5): 16-23.
[11]	牟廉明. 自适应特征选择加权k子凸包分类[J]. 山东大学学报 (工学版), 2018, 48(5): 32-37.
[12]	张璞,刘畅,王永. 基于特征融合和集成学习的建议语句分类模型[J]. 山东大学学报 (工学版), 2018, 48(5): 47-54.
[13]	王国新,陈凤东,刘国栋. 基于彩色伪随机编码结构光特征提取方法[J]. 山东大学学报 (工学版), 2018, 48(5): 55-60.
[14]	胡建平,李鑫,谢琪,李玲,张道畅. 基于Delaunay三角化的二维无约束优化EMD方法[J]. 山东大学学报 (工学版), 2018, 48(5): 9-15, 37.
[15]	江珊珊,杨静,范丽亚. 基于PDEs的图像特征提取方法[J]. 山东大学学报(工学版), 2018, 48(4): 27-36.