文章快速检索     高级检索
  大地测量与地球动力学  2020, Vol. 40 Issue (12): 1303-1307  DOI: 10.14075/j.jgg.2020.12.019

引用本文  

陈强, 岳东杰, 陈健. 基于特征空间匹配的激光雷达点云配准算法[J]. 大地测量与地球动力学, 2020, 40(12): 1303-1307.
CHEN Qiang, YUE Dongjie, CHEN Jian. Laser LiDAR Point Cloud Registration Algorithm Based on Feature Space Matching[J]. Journal of Geodesy and Geodynamics, 2020, 40(12): 1303-1307.

第一作者简介

陈强,硕士生,主要从事三维激光扫描点云数据处理研究,E-mail:1182695648@qq.com

About the first author

CHEN Qiang, postgraduate, majors in 3D laser scanning point cloud data processing, E-mail:1182695648@qq.com.

文章历史

收稿日期:2020-03-09
基于特征空间匹配的激光雷达点云配准算法
陈强1     岳东杰1     陈健1     
1. 河海大学地球科学与工程学院,南京市佛城西路8号,211100
摘要:针对传统基于特征的粗配准效率低、误匹配较多的不足,提出一种基于特征空间匹配的配准方法。利用简化的PointNet模型实现特征空间的提取,以优化的点云PPF信息作为输入,根据提取的特征空间向量计算欧氏距离以筛选匹配点,通过RANSAC剔除误匹配点对完成粗配准,利用ICP实现精配准。实验结果表明,本文算法相比FPFH和SHOT算法与ICP结合可有效提升配准效率,且配准结果的均方根误差较小。
关键词三维扫描点云配准PointNet模型随机采样一致性迭代最近点算法

受测量条件限制,激光扫描技术往往需要架设多站点进行扫描,并对获取的点云数据进行配准以消除不同站点的相对位置变化。目前点云配准算法主要分粗配准和精配准2个阶段。迭代最近点算法(iterative closest point, ICP)[1]为目前应用最广泛且十分有效的一种精配准方法,但计算成本大、易陷入局部最小值。高效且鲁棒性优良的粗配准方法可为ICP提供较好的初始值[2-3],但传统的基于特征的粗配准方法效率低、误匹配点对较多。本文基于PointNet模型[4]提取点云深度特征的优点,将一种改进的点对特征(point pair feature, PPF)信息[5]作为输入,通过模型直接提取点云局部信息的特征空间而无需训练,提取的特征空间经实验验证具有较优的局部表达能力,然后与传统算法相结合依次完成粗配准与精配准。

1 基于特征空间匹配的配准算法

基于特征空间匹配的配准算法的主要步骤为:首先计算源点云与目标点云的内部形态描述子(intrinsic shape signatures,ISS)关键点,求取关键点k邻域内优化的PPF信息,并用改进的PointNet模型进行特征提取;然后根据特征空间向量的欧氏距离完成匹配点对的筛选,通过随机采样一致性(random sample consensus,RANSAC)剔除误匹配点对;最后利用k-d树加速ICP精配准。

1.1 ISS特征点提取

首先由ISS算法计算源点云A与目标点云B(以下称两站点云)的关键点,该步骤阈值的选取较为关键,阈值过大会导致特征点数目多而不利于计算,阈值过小会使得局部信息缺失。阈值选取依赖于经验值,主要原则为调整阈值大小及邻域半径得到适合于算法的关键点数量。本文将关键点数控制在10 000左右,阈值ε1ε2采用点云库(point cloud library, PCL)官方文档的参数0.975,提取的关键点直接进入下一步计算,特征点提取步骤如下:

1)为点云中每个点pi建立局部坐标系,设定每个点的搜索半径r

2)以搜索半径r建立k-d树,计算其范围内所有点的权值:

$ {\mathit{\boldsymbol{w}}_{ij}} = 1/\left| {{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_j}} \right|, \left| {{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_j}} \right| < r $ (1)

式中,pjpi半径r内的邻域点坐标。

3)计算所有点pi的协方差矩阵:

$ \begin{array}{*{20}{c}} {{\mathop{\rm cov}} \left( {{\mathit{\boldsymbol{p}}_i}} \right) = }\\ {\sum\limits_{\left| {{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_j}} \right| < r} {{\mathit{\boldsymbol{w}}_{ij}}} \left( {{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_j}} \right){{\left( {{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_j}} \right)}^{\rm{T}}}/\sum\limits_{\left| {{\mathit{\boldsymbol{p}}_i} - {\mathit{\boldsymbol{p}}_j}} \right| < r} {{\mathit{\boldsymbol{w}}_{ij}}} } \end{array} $ (2)

4)计算各点pi协方差矩阵的特征值{λi1λi2λi3},由大到小进行排列。

5)设置阈值ε1ε2,满足式(3)则认为该点为ISS特征点:

$ \lambda _i^2/\lambda _i^1 \le {\varepsilon _1}, \lambda _i^3/\lambda _i^2 \le {\varepsilon _2} $ (3)
1.2 改进的PointNet模型

PointNet为一种新型的处理点云数据的深度学习模型,可直接在点云数据上应用。该模型在点云分类和任务分割中具有重要作用,但所获取的点云特征未充分考虑邻域点的信息,因此难以直接应用于点云配准。图 1为PointNet主要架构,关键流程包括:输入为点云数据的坐标集合;通过网络得到转换矩阵,将原始点云与转换矩阵相乘进行点云对齐;再通过多层感知器(multilayer perceptron, MLP)提取点云数据特征,对特征进行对齐并升维;执行最大池化操作来获取各组点云数据的全局特征;最后针对点云分类或任务分割,分别对特征进行MLP处理。

图 1 PointNet简略架构图 Fig. 1 Simple architecture diagram of PointNet

PointNet处理点云数据具有可提取深度信息的优点,但其在点云配准上仍具有一定挑战:PointNet对于姿态错位较为敏感,旋转不变性的前提是点云相对于规范坐标框架错位较小;需要大量的训练数据来提高抗噪性;原始模型针对不同样本需要等量点数等。

针对PointNet模型无法获取纯粹局部信息的缺陷,将模型输入的点云数据改变为优化的PPF信息,点云PPF信息计算公式为:

$ {\mathit{\boldsymbol{F}}_{12}} = \left( {{{\left\| \mathit{\boldsymbol{d}} \right\|}_2}, \angle \left( {{\mathit{\boldsymbol{n}}_1}, \mathit{\boldsymbol{d}}} \right), \angle \left( {{\mathit{\boldsymbol{n}}_2}, \mathit{\boldsymbol{d}}} \right), \angle \left( {{\mathit{\boldsymbol{n}}_1}, {\mathit{\boldsymbol{n}}_2}} \right)} \right) $ (4)

式中,d为两点间的坐标差向量,n1n2分别为两点的法向量,‖d2为欧氏距离,角度计算公式为:

$ \angle \left( {{\mathit{\boldsymbol{n}}_1}, {\mathit{\boldsymbol{n}}_2}} \right) = \arccos \left( {{\mathit{\boldsymbol{n}}_1} \cdot {\mathit{\boldsymbol{n}}_2}/\left( {\left| {{\mathit{\boldsymbol{n}}_1}} \right| \times \left| {{\mathit{\boldsymbol{n}}_2}} \right|} \right)} \right) $ (5)

由于PPF信息中d含坐标信息,而匹配点对依赖的局部信息应与坐标无关,故只保留PPF中欧氏距离与法向量夹角,优化的PPF信息如下:

$ {\mathit{\boldsymbol{F}}_{12}} = \left( {{{\left\| \mathit{\boldsymbol{d}} \right\|}_2}, \angle \left( {{\mathit{\boldsymbol{n}}_1}, {\mathit{\boldsymbol{n}}_2}} \right)} \right) $ (6)

将PPF信息由两点扩展至k个点即可获得局部范围的特征表达,文中模型的输入即为关键点在其k邻域内的优化PPF信息,如第r个关键点的优化PPF信息为:

$ \begin{array}{*{20}{c}} {{\mathit{\boldsymbol{F}}_r} = \left( {{{\left\| {{\mathit{\boldsymbol{d}}_{1r}}} \right\|}_2}, \angle \left( {{\mathit{\boldsymbol{n}}_1}, {\mathit{\boldsymbol{n}}_r}} \right), {{\left\| {{\mathit{\boldsymbol{d}}_{2r}}} \right\|}_2}, } \right.}\\ {\angle \left( {{\mathit{\boldsymbol{n}}_2}, {\mathit{\boldsymbol{n}}_r}} \right) \cdots {{\left\| {{\mathit{\boldsymbol{d}}_{kr}}} \right\|}_2}, \left( {\angle \left( {{\mathit{\boldsymbol{n}}_k}, {\mathit{\boldsymbol{n}}_r}} \right)} \right)} \end{array} $ (7)

PointNet模型首先采用训练网络学习从输入的点云坐标中得到转换矩阵,将原始点云与转换矩阵相乘进行对齐,以保证整块点云空间变换的旋转不变性,但无法在配准中提取局部特征,因此将模型中该处的训练网络去除以提高运行效率。PointNet模型中最后获得的特征为1 024维,研究结果表明,当维度取128和256时可获得与1 024维相当甚至更优的效果[6],故本文将提取特征由1 024维改为256维,可提高后续计算的效率。改进后的模型架构如图 2所示。

图 2 改进的PointNet架构图 Fig. 2 Architecture diagram of improved PointNet

根据模型得到的特征空间向量计算两站点云间关键点的特征空间向量欧氏距离,设置阈值后可初步筛选出匹配点对。将初步筛选的匹配点对集合记为M(AnBn),然后通过RANSAC作进一步筛选,求取的内点即为最终的粗匹配点对。根据上述点对计算旋转和平移矩阵,作用于原始两站点云即可得到粗配准结果。RANSAC过程的计算时间与匹配点对集合M的数量正相关,因此需要综合考虑效率与准确度2个因素,本文将点对集合M控制在原始点数的1/30左右,RANSAC迭代上限设置为10 000次。

1.3 k-d树加速的ICP精配准

粗配准的结果主要是为后续的精配准作准备,因此将本文算法与传统算法粗配准进行对比后,仍需对精配准的结果作进一步比较。考虑到效率因素,选取k-d树加速的ICP算法进行精配准,通过精配准的实验结果反映不同粗配准算法提供的初始化条件的优劣。ICP算法通过最小二乘原理实现最优匹配进行精配准,主要流程为寻找源点云与目标点云间的旋转和平移矩阵,重复寻找点集和计算刚体变换,当2次迭代的目标函数值差异小于设定的阈值或迭代达到一定次数时停止迭代,目标函数为:

$ f\left( {{\mathit{\boldsymbol{R}}^k}, {\mathit{\boldsymbol{T}}^k}} \right) = \frac{1}{N}\mathop \sum \limits_{i = 1}^N {\left\| {{{\mathit{\boldsymbol{\overline a}} }_i} - {\mathit{\boldsymbol{R}}^k}\mathit{\boldsymbol{\overline b}} _i^{k - 1} - {\mathit{\boldsymbol{T}}^k}} \right\|^2} $ (8)

式中,Rk为旋转矩阵,Tk为平移矩阵,aibi分别为源点云和目标点云坐标与各自质心差值后的坐标。

传统ICP算法在确定对应点对,即在目标点云中搜索源点云相应最近点时,每次迭代都需遍历一次目标点云,导致效率低下,因此可采用k-d树对ICP算法进行加速。在迭代之前,预先对两站点云建立k-d树,进而一次性计算源点云中各点在目标点云中相应的最近点。

2 实验与分析 2.1 实验数据及环境

实验数据分为3组:第1组为Stanford 3D Scanning Repository下载的Lucy点云模型,用来测试算法在不同噪声水平及参数下的粗配准效果;第2组为实测的汉武大帝雕像数据,数据由Z+F 5016三维激光扫描仪获取,命名为Han,目的是对实测轮廓性较好的对象进行配准实验;第3组为Robotic 3D Scan Repository下载的实测数据,由Riegl VZ-400扫描仪获取,命名为Street,用来测试大规模室外场景下该算法的有效性。

实验笔记本电脑处理器为AMD A10-5745M、内存8 GB、Windows 10操作系统,算法基于Python3.6、Tensorflow2.0,FPFH和SHOT算法在Visual Studio2013、PCL点云库1.8中实现。

2.2 Lucy数据粗配准实验

Lucy数据实验仅测试粗配准效果,将从2个方面对该组数据的配准结果进行评价:1)模型在不同噪声水平下的配准均方根误差(root mean square error, RMSE);2)与传统配准方法的效率和精度的比较。均方根误差通过查询源点云各点至目标点云中最近点获得,计算公式为:

$ {\mathop{\rm RMSE}\nolimits} = {\left( {\frac{1}{{{N_p}}}\sum\limits_{i = 1}^{{N_p}} {\left\| {\mathit{\boldsymbol{R}}{\mathit{\boldsymbol{p}}_i} + \mathit{\boldsymbol{T}} - {\mathit{\boldsymbol{q}}_i}} \right\|_2^2} } \right)^{\frac{1}{2}}} $ (9)

式中,Np为源点云点数,pi为源点云,qi为目标点云对应pi中的最近点集。

Lucy模型原始数据点云个数为1 300万,通过曲率压缩后为20万,再通过ISS检测出9 166个关键点,在此数据基础上随机删除1/100、1/50并进行刚性变换,添加递增的高斯白噪声以分成多组数据,得到的待配准点云个数分别为9 075和8 983。由图 3(a)可知,本文算法在随机删除1/100和1/50点的情况下,添加1~20 dB强度噪声时均能完成配准,且精度均在2.5 mm以内,噪声增强及缺失点数增多均会使配准误差变大。采用本文算法选择不同邻域点数计算法向量夹角及欧氏距离时,最终配准误差会产生约0.1 mm的差异,当点数为9 075和8 983时,选取20个邻域点的配准效果较好(图 3(b))。从表 1表 2可以看出,在Lucy数据中添加不同强度噪声时,本文算法平均配准时间比FPFH减少61.1 s,提高73.2%,比SHOT算法减少53.3 s,提高70.4%;平均配准精度比FPFH算法提高89.9%,比SHOT算法提高89.9%。图 4(a)为原始点云,4(b)、4(c)、4(d)为本文算法、FPFH算法、SHOT算法对Lucy模型添加1 dB噪声并删除1/50点的配准效果。从图中可以看出,本文算法配准后的点云重叠度优于FPFH、SHOT算法。

图 3 多组实验配准误差对比图 Fig. 3 Comparison of registration error of several experiments

表 1 不同噪声配准误差对比 Tab. 1 Comparison of registration error of different noise

表 2 不同噪声配准时间对比 Tab. 2 Comparison of registration time of different noise

图 4 Lucy配准图 Fig. 4 Registration diagrams of Lucy
2.3 Han数据精配准实验

Han两个站点曲率压缩和去噪后均约为20万点云,经ISS特征检测得到关键点数分别为11 249和11 890,站点间重叠度约为70%,计算PPF信息时选择20个邻域点。从图 5(a)5(b)可以看出,本文算法粗配准相比于FPFH算法能够提供更好的初始状态,以满足后续精配准的需求;图 5(c)5(d)为FPFH算法与本文算法在ICP精配准后的效果,两者在视觉上无明显区别。由表 3可知,本文算法配准过程相比于FPFH与ICP算法,运行时间减少100.5 s,提高68.6%,RMSE减小3.588 2 mm,提高28.1%,具有一定的优势。

图 5 Han配准图 Fig. 5 Registration diagrams of Han

表 3 Han配准时间及误差对比 Tab. 3 Comparison of registration time and error of Han
2.4 Street数据精配准实验

Street两个站点曲率压缩和去噪后均约为30万点云,经ISS特征检测得到关键点数分别为9 005和8 512,站点间重叠度约为80%,计算PPF信息时选择20个邻域点。从图 6(b)可以看出,ISS关键点的分布位置在边缘处较为集中,能够较好地表达场景特征。从图 6(c)6(d)可以看出,本文算法的粗配准效果优于FPFH算法,能保持较好的初始配准姿态。

图 6 Street配准图 Fig. 6 Registration diagrams of Street

图 6(e)6(f)为2种方法的精配准效果,两者差异不明显,需采用表 4中的量化结果进行比较。由表 4可知,本文算法相比于FPFH算法,运行时间减少74.4 s,提高65.6%,RMSE减少1.242 9 mm,提高7.8%。

表 4 Street配准时间及误差对比 Tab. 4 Comparison of registration time and error of Street
3 结语

本文对点云配准算法进行深入研究,针对基于特征的配准方法存在误匹配点对多且计算成本高的问题,提出一种改进的PointNet模型代替传统的特征提取和匹配方法,相对于传统方法可大幅提高处理效率,同时由于提取过程中信息利用率较大,可在一定程度上减少误匹配问题。

研究结果表明,本文算法在粗配准过程与FPFH、SHOT算法相比,可减少配准时间,同时提高匹配点对的正确率,为后续的精配准提供更好的初始状态,有效减少精配准匹配失败的情况。实验数据表明,本文算法相比于FPFH与ICP算法,运行时间平均减少67.1%,均方根误差平均减小17.95%,能够高速且有效地完成物体配准。

该算法的不足之处在于整个配准流程涉及多种算法的融合,其中参数和邻域点的选择较为关键,需要一定的人工干预,因此对算法的自适应性作出改进将是下一步的研究重点。

参考文献
[1]
Besl P J, McKay H D. A Method for Registration of 3-D Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256 DOI:10.1109/34.121791 (0)
[2]
Yang J L, Li H D, Campbell D, et al. Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(11): 2 241-2 254 DOI:10.1109/TPAMI.2015.2513405 (0)
[3]
张崇军, 许烨璋, 郑善喜, 等. 改进权重的迭代最近点算法在点云配准中的应用[J]. 大地测量与地球动力学, 2019, 39(4): 417-420 (Zhang Chongjun, Xu Yezhang, Zheng Shanxi, et al. Improved Weight Iterative Closet Point Algorithm Applied in Point Cloud Registration[J]. Journal of Geodesy and Geodynamics, 2019, 39(4): 417-420) (0)
[4]
Charles R Q, Su H, Kaichun M, et al. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation[C]. 2017 IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, 2017 (0)
[5]
Deng H W, Birdal T, Ilic S, et al. PPFNet: Global Context Aware Local Features for Robust 3D Point Matching[C]. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, 2018 (0)
[6]
白静, 司庆龙, 秦飞巍. 轻量级实时点云分类网络LightPointNet[J]. 计算机辅助设计与图形学学报, 2019, 31(4): 612-621 (Bai Jing, Si Qinglong, Qin Feiwei. Lightweight Real-Time Point Cloud Classification Network LightPointNet[J]. Journal of Computer-Aided Design and Graphics, 2019, 31(4): 612-621) (0)
Laser LiDAR Point Cloud Registration Algorithm Based on Feature Space Matching
CHEN Qiang1     YUE Dongjie1     CHEN Jian1     
1. School of Earth Science and Engineering, Hohai University, 8 West-Focheng Road, Nanjing 211100, China
Abstract: Aiming at the shortcomings of traditional feature-based coarse registration with low efficiency and many mismatches, we propose a registration method based on feature space matching. We extract the feature space using a simplified PointNet model. We take optimized point cloud PPF information as input and calculate the Euclidean distance according to the extracted feature space vector to filter out matching points. We eliminate the mismatched points to complete the coarse registration through RANSAC, and use ICP to realize fine registration. The results show that the proposed algorithm combined with ICP greatly improves the registration efficiency compared with FPFH and SHOT algorithm, and RMSE of the registration result is smaller.
Key words: 3D scanning; point cloud registration; PointNet model; random sample consensus; iterative closest point algorithm