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

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.

相关文章 15

[1]	唐杰烽,张佳,龙锦益. 基于全局冗余最小的快速多标签特征选择方法[J]. 山东大学学报 (工学版), 2025, 55(6): 21-34.
[2]	王禹鸥,苑迎春,何振学,何晨. 融合多特征和多头自注意力机制的高校学业命名实体识别[J]. 山东大学学报 (工学版), 2025, 55(6): 35-44.
[3]	周遵富,张乾,石计亮,岳诗琴. 基于纹理和结构交互的人脸图像修复[J]. 山东大学学报 (工学版), 2025, 55(4): 18-28.
[4]	吴秋兰,尚素雅,张家辉,孙守鑫,张峰,周波,高峥,史文宠. 基于多尺度特征融合的马铃薯疮痂病图像语义分割方法[J]. 山东大学学报 (工学版), 2025, 55(4): 1-8.
[5]	索大翔,李波. 细粒度特征增强与尺寸匹配的光伏缺陷检测[J]. 山东大学学报 (工学版), 2025, 55(4): 9-17.
[6]	李连祥,郭龙德,王锟毅,王培琰,车秀熙,邱叶凡. 非饱和土空间分布与城市地铁基坑支护设计方法[J]. 山东大学学报 (工学版), 2025, 55(4): 84-92.
[7]	李丰,文益民. 融合多尺度视觉和文本语义特征的图像描述生成算法[J]. 山东大学学报 (工学版), 2025, 55(3): 80-87.
[8]	吴正健,吾尔尼沙·买买提,杨耀威,阿力木江·艾沙,库尔班·吾布力. 基于DRCoALTP的印刷体文档图像多文种识别方法[J]. 山东大学学报 (工学版), 2025, 55(1): 51-57.
[9]	南艺婷,张鑫,龚安保,解欢,李皎,陈姝芮,李丽,管旭,张庆竹,王文兴. 山东省食用植物油加工行业VOCs排放特征、环境影响及其健康风险评价[J]. 山东大学学报 (工学版), 2025, 55(1): 125-137.
[10]	刘全金,嵇文,胡浪涛,黄汇磊,杨瑞,李翔,高泽文,魏本征. 基于双解码器的医学图像分割模型[J]. 山东大学学报 (工学版), 2024, 54(6): 8-18.
[11]	薛健,赵琳,张浩,杨璐,郝凡昌. 改进Faster R-CNN的交通标志检测算法[J]. 山东大学学报 (工学版), 2024, 54(5): 34-41.
[12]	林振宇,邵蓥侠. 基于盖根堡多项式最佳平方近似的谱图网络[J]. 山东大学学报 (工学版), 2024, 54(5): 93-100.
[13]	李岩,张子毅,王建柱. 基于特征点提取的RANSAC-ICP三维点云配准方法[J]. 山东大学学报 (工学版), 2024, 54(5): 144-154.
[14]	刘真光,朱玉佳,王勇,傅湘玲,赵一姣,陈晋鹏. 基于点云处理网络的三维颜面正中矢状面预测模型[J]. 山东大学学报 (工学版), 2024, 54(3): 30-35.
[15]	马翔悦,徐金东,倪梦莹. 基于多尺度特征模糊卷积神经网络的遥感图像分割[J]. 山东大学学报 (工学版), 2024, 54(3): 44-54.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed