基于局部特征的点云配准算法

赵夫群，周明全，耿国华



基于局部特征的点云配准算法

赵夫群1,2，周明全2,3，耿国华2

(1. 咸阳师范学院教育科学学院，陕西 咸阳 712000；2. 西北大学信息科学与技术学院，陕西 西安 710127；3. 北京师范大学信息科学与技术学院，北京 100875)

针对覆盖率较低的点云，提出一种基于局部特征的点云配准算法。首先提取点云的局部深度、法线偏角和点云密度等局部特征，得到局部特征描述子；然后计算局部特征集的相关性，得到相关候选点集；再次通过删减外点达到点云粗配准的目的；最后采用基于旋转角约束和动态迭代系数的改进迭代最近点(ICP)算法，实现点云的细配准。实验结果表明，基于局部特征的点云配准算法可以实现覆盖率较低点云的精确配准，是一种精度高、速度快的点云配准算法。

点云配准；局部特征；迭代最近点；旋转角约束；动态迭代系数

点云配准研究已久，其应用领域涉及曲面匹配[1-2]、3D建模[3-4]、目标识别[5-7]以及姿态估计[8]等多个方面。点云配准就是将同一物体不同视角下的点云数据变换到同一坐标系统下的过程。点云配准中应用最多的是基于特征的配准算法，包括基于全局特征的配准和基于局部特征的配准。全局特征描述的是整个点云模型，局部特征只对特征点的邻域特征进行描述，与全局特征相比，局部特征更适用于部分覆盖的点云配准。

目前的点云配准算法中，应用最为广泛的是由BESL和MCKAY[9]提出的ICP算法，该算法对于覆盖率较高的点云有精确的配准效果，但是对点云的初始位置要求较高，而且对于数据量较大的点云的配准速度较慢。目前，国内外出现了很多改进的迭代最近点算法(iterative closest point, ICP)及其应用，如HAN等[10]提出了一种加强的ICP算法，能够快速准确地实现点云配准；王森等[11]将Sparse ICP算法应用到了三维耳廓识别中，得到了较高的识别精度和识别效率；LI和SONG[12]提出了一种基于动态调整因子的ICP算法，在不影响配准精度和收敛方向的情况下，大大提高了算法的配准速度；MAVRIDIS等[13]提出了一种基于混合优化系统的稀疏ICP算法，提高了点云配准的精度和速度；DU等[14]提出了概率迭代最近点(probability iterative closest point, PICP)算法，提高了点云配准的抗噪性；DU等[15]提出了尺度迭代最近点（scaling iterative closest point, SICP）算法，解决了点云的尺度配准问题。以上这些算法在点云的配准精度、速度、抗噪性以及尺度因素等方面有了一定程度的改进，但都是基于全局特征的配准，因此对部分覆盖的点云配准效果并不十分理想。

针对覆盖率较低的点云，本文提出了一种基于局部特征的点云配准算法。该算法分为4个实现步骤：①提取点云局部特征，包括局部深度、法线偏角和点云密度，并生成局部特征描述子；②计算局部特征集的相关性，建立点云的候选相关点集；③删减候选相关点集中的外点，以实现点云的粗配准；④通过加入旋转角约束和动态迭代系数等参数来改进ICP算法，并用改进的ICP算法实现点云的细配准，到达最终精确、快速配准的目的。

1 局部特征描述子

本文所指的局部特征是一种快速、鲁棒的点云特征描述子，包括局部深度、法线的偏角和点云密度等，其都具有旋转和平移不变的特性。

1.1 局部深度特征

1.2 法线的偏角

1.3 点云密度

计算了点的3个局部几何特征后，可以得到3个子直方图，然后将其合成为1个直方图，即可得到局部特征的描述子。

2 粗配准算法

采用一种基于局部特征描述子的配准算法实现点云粗配准，主要包含3个步骤：局部特征提取、相关性计算和外点删减。

图1 局部特征示意图

2.1 局部特征提取

2.2 相关性计算

2.3 外点删减

3 细配准算法

以上步骤实现了点云的粗配准，接下来的细配准采用一种改进的ICP算法来实现。即在ICP算法的基础上添加旋转角约束和动态迭代系数。

3.1旋转角约束

旋转角约束是指为刚体变换中的旋转角设置边界（即上界和下界），可以降低因旋转角变化过大而引起的配准效果不佳的问题。

3.2 动态迭代系数

3.3 改进的ICP算法

加入旋转角约束和动态迭代系数后，改进的ICP算法的具体实现步骤如下：

4 实验结果与分析

实验采用的3D点云数据源于Stanford 3D Scanning Repository[19]，如图2所示。图2(a)为初始兔子点云数据模型，图2(b)为初始龙点云数据模型。采用本文点云配准算法，首先通过局部特征提取、相关性计算和外点删减等步骤后，得到的粗配准的结果如图3(a)所示，然后采用本文提出的改进ICP算法进细配准，细配准结果如图3(b)所示。

图2 待配准点云

图3 点云配准结果

从图3的配准结果可见，本文提出的基于局部特征的点云配准算法具有良好的配准效果。为了进一步验证本文算法的良好性能，在细配准阶段，分别采用ICP算法、文献[20]中特征改进的ICP算法和本文改进的ICP算法进行细配准，其点云类型、初始点云大小、采用算法、配准点数、配准误差（均方根）、迭代次数和耗时等参数见表1。

从表1的配准结果可见，ICP算法、文献[20]算法和改进的ICP算法均能实现点云的细配准，但是文献[20]算法和改进的ICP算法的配准精度明显提高、耗时明显缩短。特别是改进的ICP算法，其配准精度比ICP算法和文献[20]算法分别提高了约50%和40%，配准速度比ICP算法和文献[20]算法分别提高了约65%和50%。这是由于在ICP算法中引入了旋转角约束，可以降低点云因旋转角变化过大而引起的配准效果不佳的问题，由此大大提高了算法的配准精度。此外，在ICP算法中还引入了动态迭代系数，可以在不影响算法的配准精度和收敛方向的情况下，大大提高算法的迭代速度，降低耗时。因此说，本文的基于局部区域的点云配准算法是一种精度更高、速度更快的点云配准算法。

表1 细配准算法的配准参数

5 结 论

通过描述点云局部特征的方式，本文提出了一种快速、高精度的低覆盖率点云配准算法。该算法利用局部深度、法线偏角和点云密度等局部特征生成特征描述子，并据此建立点的相关性，进而通过改进的ICP算法实现点云的快速、精确配准，对低覆盖率的点云具有良好的配准效果。在将来的点云配准算法研究中，要综合考虑多种因素，做进一步的深入研究，比如进一步完善特征描述子，融入更多的空间信息；在算法的抗噪性方面做进一步的研究，提高算法的配准精度；将算法应用到特殊刚体曲面的配准中，如兵马俑碎块的断裂面匹配，以扩大算法的应用范围。

[1] ALBARELLI A, RODOLÀ E, TORSELLO A. Fast and accurate surface alignment through an isometry-enforcing game [J]. Pattern Recognition, 2015, 48 (7): 2209-2226.

[2] GONG M G, WU Y, CAI Q, et al. Discrete particle swarm optimization for high-order graph matching [J]. Information Sciences, 2016, 328: 158-171.

[3] LIU A A, WANG Z Y, NIE W Z, et al. Graph-based characteristic view set extraction and matching for 3D model retrieval [J]. Information Sciences, 2015, 320: 429-442 .

[4] 林晓, 王燕玲, 朱恒亮, 等. 基于自适应权值的点云三维物体重建算法研究[J]. 图学学报, 2016, 37(2): 143-148.

[5] ALHAMZI K, ELMOGY M, BARAKAT S. 3D object recognition based on local and global features using point cloud library [J]. International Journal of Advanced Computer Science. 2015, 7(3): 43.

[6] GUO Y L, SOHEL F, BENNAMOUB M, et al. A novel local surface feature for 3D object recognition under clutter and occlusion [J]. Information Sciences, 2015, 293: 196-213.

[7] LIANG R, SHEN W, LI X X, et al. Bayesian multi-distribution-based discriminative feature extraction for 3d face recognition [J]. Information Sciences, 2015, 320: 406-417.

[8] GUO Y, BENNAMOUN M, SOHEL F, et al. An integrated framework for 3-d modeling, object detection, and pose estimation from point clouds [J]. IEEE Transactions on Instrumentation and Measurement. 2015, 64(3): 683-693.

[9] BESL P J, MCKAY N D. A method for registration of 3-Dshapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(3): 239-256.

[10] HAN J D, YIN P, HE Y Q. Enhanced ICP for the registration of large scale 3D environment models: an experimental study [J]. Sensors, 2016, 16(2): 228.

[11] 王森, 王璐, 洪靖惠, 等. 基于 Sparse ICP 的三维点云耳廓识别[J]. 图学学报, 2015, 36(6): 862-867.

[12] LI W M, SONG P F. A modified ICP algorithm based on dynamic adjustment factor for registration of point cloud and CAD model [J]. Pattern Recognition Letters, 2015, 65: 88-94.

[13] MAVRIDIS P, ANDREADIA A, PAPAIOANNOU G. Efficient sparse ICP [J]. Computer Aided Geometric Design, 2015, 35-36: 16-26.

[14] DU S Y, LIU J, ZHANG C J, et al. Probability iterative closest point algorithm for-D point set registration with noise [J]. Neurocomputing, 2015, 157: 187-198.

[15] DU S Y, ZHENG N N, XIONG L, et al. Scaling iterative closest point algorithm for registration of-D point sets [J]. Journal of Visual Communication and Image Representation, 2010, 21(5-6): 442-452.

[16] MITRA N J, NGUYEN A. Estimating surface normals in noisy point cloud data [C]//SCG´03 Proceeding of the 19thACM Annual Symposium on Computational Geometry. New York: ACM Press, 2003: 322-328.

[17] KAMMERL J, BLODOW N, RUSU R B, et al. Real-time compression of point cloud streams [C]// IEEE International Conference on Robotics and Automation (ICRA), New York: IEEE Press, 2012: 778-785 .

[18] WIKIPEDIA. Rotation matrix [EB/OL]. [2017-1-15]. http://en.wikipedia.org/w/index.php?title=Rotation_matrix&oldid=624815514.

[19] Stanford University Computer Graphics Laboratory. The stanford 3D scanning repository [EB/OL]. [2017-1-14]. http://graphics.stanford.edu/data/3Dscanre.

[20] 贺永兴, 欧新良, 匡小兰. 邻域特征在点云配准中的应用[J]. 计算机应用, 2012, 32(3): 762-765, 769.

Point Cloud Registration Algorithm Based on Local Features

ZHAO Fuqun1,2, ZHOU Mingquan2,3, GENG Guohua2

(1. School of Education Science, Xianyang Normal University, Xianyang Shaanxi 712000, China; 2. School of Information Science and Technology, Northwest University, Xi’an Shaanxi 710127, China; 3. School of Information Science and Technology, Beijing Normal University, Beijing 100875, China)

Aiming at low-coverage-rate point clouds, a registration algorithm was proposed based on local features in the paper. Firstly, local features including the local depth, deviation angle between normals and point cloud density are extracted, and the local feature descriptor is obtained. Secondly, the correspondence of local feature sets is calculated and the corresponding candidates are gained. Thirdly, the outliers are eliminated and coarse registration is achieved. Lastly, an improved iterative closest point (ICP) algorithm based on the rotation angle constraint, and the dynamic iterative coefficient is employed to complete fine point cloud registration. The experiment results reveal that the point cloud registration algorithm could achieve the precise registration of low-coverage-rate point cloud, based on local features, a high-precision and fast one.

point cloud registration; local feature; iterative closest point; rotation angle constraint; dynamic iterative coefficient

TP 391

10.11996/JG.j.2095-302X.2018030389

A

2095-302X(2018)03-0389-06

2017-02-14；

2017-03-16

国家自然科学基金项目(61731015)；咸阳发展研究院服务地方经济社会发展项目(2018XFY007)

赵夫群(1982-)，女，山东临沂人，博士研究生。主要研究方向为图形图像处理。E-mail：fuqunzhao@126.com

周明全(1954-)，男，陕西西安人，教授，博士，博士生导师。主要研究方向为图形图像处理。E-mail：354449904@qq.com