结合特征点提取的点云配准算法.pdf

Operations Research and Fuzziology 运筹与模糊学运筹与模糊学,2024,14(1),673-679 Published Online February 2024 in Hans.https:/www.hanspub.org/journal/orf https:/doi.org/10.12677/orf.2024.141063 文章引用文章引用:龙纪安,陆安江,杨教,杨承.结合特征点提取的点云配准算法J.运筹与模糊学,2024,14(1):673-679.DOI:10.12677/orf.2024.141063 结合特征点提取的点云配准算法结合特征点提取的点云配准算法 龙纪安，陆安江龙纪安，陆安江*，杨，杨 教，杨教，杨 承承 贵州大学大数据与信息工程学院，贵州 贵阳 收稿日期：2023年12月5日；录用日期：2023年12月25日；发布日期：2024年2月29日 摘摘 要要 在点云配准技术中，粗、精配准的策略被用作点云配准的常用手段，本文针对普通配准策略配准耗时长，在点云配准技术中，粗、精配准的策略被用作点云配准的常用手段，本文针对普通配准策略配准耗时长，配准精度有待提高的问题，提出了一种耗时更短、精度更高的点云配准算法。首先，使用配准精度有待提高的问题，提出了一种耗时更短、精度更高的点云配准算法。首先，使用SIFT算法提取算法提取源、目标点云的特征点，将这些特征点作为配准算法的输入；然后，使用源、目标点云的特征点，将这些特征点作为配准算法的输入；然后，使用SAC-IA算法进行点云粗配准，算法进行点云粗配准，为后续精配准提供一个大致对齐的位姿；最后，使用带法向量约束的点到面为后续精配准提供一个大致对齐的位姿；最后，使用带法向量约束的点到面ICP算法进行点云精配准，算法进行点云精配准，得到最终的配准位姿。实验表明，本文所提算法在配准耗时上相比于得到最终的配准位姿。实验表明，本文所提算法在配准耗时上相比于SAC-IA+ICP算法提升了算法提升了96.2%、相比于相比于NDT+ICP算法提高算法提高了了81.0%，在配准的均方根误差上相比于，在配准的均方根误差上相比于SAC-IA+ICP算法提高了算法提高了43.6%、相、相比于比于NDT+ICP算法提高了算法提高了24.7%，证明了本文算法在计算时间和配准精度上的有效性。，证明了本文算法在计算时间和配准精度上的有效性。关键词关键词 机器视觉，点云配准，特征提取，迭代最近点，法线估计机器视觉，点云配准，特征提取，迭代最近点，法线估计 Point Cloud Registration Algorithm Combined with Feature Points Extraction Jian Long,Anjiang Lu*,Jiao Yang,Cheng Yang School of Big Data and Information Engineering,Guizhou University,Guiyang Guizhou Received:Dec.5th,2023;accepted:Dec.25th,2023;published:Feb.29th,2024 Abstract In view of the problem that the registration of ordinary registration strategies takes a long time and the registration accuracy needs to be improved,this paper proposes a point cloud registra-tion algorithm with shorter time and higher accuracy.Firstly,the SIFT algorithm is used to ex-tract the feature points of the source and target point clouds,and these feature points are used *通讯作者。龙纪安 等 DOI:10.12677/orf.2024.141063 674 运筹与模糊学 as the input of the registration algorithm,then the SAC-IA algorithm is used for the rough regis-tration of the point cloud to provide a roughly aligned pose for the subsequent fine registration,and finally,the point-to-surface ICP algorithm with normal vector constraint is used for the point cloud fine registration to obtain the final registration pose.Experiments show that the proposed algorithm is 96.2%longer than the SAC-IA+ICP algorithm in terms of registration time,81.0%higher than the NDT+ICP algorithm,43.6%higher than the SAC-IA+ICP algorithm and 24.7%higher than the NDT+ICP algorithm in the root mean of registration square error,which proves the effectiveness of the proposed algorithm in terms of calculation time and regis-tration accuracy.Keywords Machine Vision,Point Cloud Registration,Feature Extraction,Iterative Nearest Point,Normal Estimation Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 近年来，机器视觉技术快速发展，在三维领域的机器视觉技术包括三维重建、SLAM(simultaneous ocalization and mapping)、目标识别等技术被广泛研究，使得三维机器视觉技术在逆向工程、无人驾驶、增强现实等领域受到广泛应用1。在点云三维重建过程中，由于受到采集条件的限制，3D 相机在一次采集中只能获得采集目标一个视角的点云数据，所以采集过程需要重复多次，得到采集目标多个视角下的点云数据，将这些不同视角的点云数据变换到统一坐标系下的操作被称为点云配准。点云配准是将不同视角下的点云数据转换到同一坐标系下的技术，目前使用最广泛的配准技术是粗配准后精配准的配准策略。常用于粗配准的算法如正态分布变换(Normal Distributions Transform,NDT)算法2和采样一致性初始配准(Sample Consensus Initial Aligment,SAC-IA)算法3，用于精配准的常用算法如迭代最近点(Iterative Closest Point,ICP)算法4及其各种变式算法5 6 7。王文博等人8提出了改进的 ICP 点云配准方法，使用点云分块并从分块点云中提取尺度不变特征变换(Scale Invariant Feature Transform,SIFT)特征点的思想，将特征点用于 SAC-IA+ICP 的配准策略，大幅提升了配准的效率和精度，但点云分开的阈值选择较为麻烦。刘雷等人9提出了基于 SIFT 结合二进制直方图描述子的点云配准方法，可以有效提升重叠率较低的两个点云配准的效率和精度，但在一般情况下配准精度仍有提升的空间。范林林等人10提出一种基于区域均值特征描述符的部分点云与整体点云配准方法，与现有的基于局部特征描述符的点云配准方法相比，有效提高了配准的速度和准确度，但点云的密度对其特征描述造成的影响较大，存在局限性。张赵良等人11提出用内部描述子(Intrinsic Shape Signa-ture,ISS)特征点结合改进 ICP 的配准算法，将配准精度和配准效率进一步提高，但该算法的参数设置较为复杂，通用性较差。针对以上配准算法存在的问题，本文提出基于 SIFT 关键点提取结合改进 ICP 的点云配准算法，采用SIFT 计算点云特征点，在保证配准精度的条件下减少点云配准过程的计算量，对提取的特征点计算其快速点特征直方图(Fast Point Feature Histograms,FPFH)局部描述子，得到对应点对，再利用 SAC-IA 算法完成粗配准，最后使用带法向向量约束的点到平面的 ICP 算法完成精配准。Open AccessOpen Access龙纪安 等 DOI:10.12677/orf.2024.141063 675 运筹与模糊学 2.算法原理算法原理 2.1.SCI-IA 粗配准粗配准 SAC-IA算法基于随机采样一致性(Random sample consensus,RANSAC)算法，不同之处在于RANSAC算法是随机采样点，而 SAC-IA 算法的采样点数量更多，采样点之间的关系有距离限制，在对应点查找时，通过 FPFH 来匹配而不是点与点之间的距离，特征描述符考虑了点的领域结构，增加了寻找匹配点的精度。SAC-IA 的算法步骤如下：(1)分别计算源点云和目标点云的 FPFH 特征描述子；(2)寻找两组点云中有相似 FPFH 的匹配点；(3)随机选择 n 对(n 3)匹配点；(4)通过 SVD 求解该匹配情况下的旋转位移矩阵，并计算配准误差；(6)重复步骤(3)(5)，直到满足误差条件，输出最终的旋转位移矩阵。2.2.ICP 精配准精配准 ICP 算法本质上是基于最小二乘法的思想，配准精度高，不需要提供特征点，但对于点云的初始位姿敏感，需要在 ICP 算法之前进行点云粗配准，否则容易陷入局部最优，其核心是通过一定的约束关系找到源点云和目标点云之间的对应点，利用对应点构建目标函数并进行迭代优化，直至目标函数收敛或达到最大迭代次数。设源点云为 P，目标点云为 Q，ICP 算法可描述为：()()()min,2,1,argminpqnniiR TiR TRpTq=+(1)其中，R 为点云旋转变换矩阵；T 为点云平移向量；np、nq分别为源点云和目标点云中点的数量。pi、qi分别为源点云和目标点云中的一点；ICP 算法步骤如下：(1)计算源点云 P 中的每一个点 pi与目标点云 Q 中的对应点 qi。(2)通过欧式距离去除错误匹配点对。(3)通过 SVD 分解计算使得对上述对应点对平均距离最小的刚体变换，求得旋转平移矩阵 R 和 T；(4)使用旋转平移矩阵对 P 进行空间变换，得到新的点云 P：PR PT=+(2)(5)计算 P与 Q 的距离误差，若满足收敛条件或达到最大迭代次数，则停止迭代，否则将点集 P作为新的 P 继续迭代计算旋转平移矩阵，直到满足目标函数要求。3.改进算法原理改进算法原理 Figure 1.The overall flow chart of the algorithm in this paper 图图 1.本文算法总体流程图 为了提高 ICP 算法配准的效率，减少迭代次数，本文使用 SAC-IA 进行粗配准，为 ICP 算法提供较龙纪安 等 DOI:10.12677/orf.2024.141063 676 运筹与模糊学 好的初始位姿，并在粗配准之前，使用 SIFT 算法提取源、目标点云的关键点，在保留点云特征的同时减少配准计算量。另外，使用点到面的距离误差作为 ICP 算法的目标函数，并且添加法向量夹角阈值来剔除配准时引入的噪声点对，提高配准精度。本文算法的总体流程如图 1 所示。3.1.SIFT 特征点提取特征点提取 SIFT 算法是 David G.Lowe 在 1999 年提出的高效区域检测算法，在 2004 年得以完善，在 2007 年由Flint 等人应用于 3D 数据上12，该方法提取的特征点具有对噪声、旋转和平移等因素保持较好的不变性的特点。其主要原理是在目标点集的不同尺度空间上搜索那些对于尺度和旋转不变的特征点。对于有 N个点的点云数据 P，任意一点 pi的坐标为(xi,yi,zi)，i=1,2,N，SIFT 特征点提取算法步骤如下：(1)构建尺度空间：将点云与三维高斯函数进行卷积，计算尺度空间 L(x,y,z,)。()()(),L x y zG x y z kp x y z=(3)其中，G(x,y,z,k)为高斯卷积核函数，p(x,y,z)为点云坐标，为空间尺度参数，k 为尺度空间大小调整参数。三维空间中的高斯卷积核函数如下：()()()()222321,exp22xyzG x y z kkk+=(4)(2)计算高斯差分模型：设 s 为高斯金字塔每组的层数，将高斯金字塔中相邻的两层点云相减，构成点云的高斯差分图 DoG，如式：()()1o,iiiD GL x y z kLx y z k=(5)其中，DoGi为相邻尺度层的差分模型，i(0,s+2)。(3)特征点检测：计算 DOGi在本层内的极值点，并与其上下 2 个尺度层内的极值点对比仍为最值时，则认为该点为特征点。3.2.带法向约束的点到面带法向约束的点到面 ICP 算法算法 如式(1)所示，普通 ICP 算法的以点到点之间的距离误差作为目标函数进行迭代求解，而点到平面的ICP 算法以最小化源点云中的点到目标点云对应点所在平面的距离作为配准准则，如式(6)：()()()min,2,1,argminpqnniiiR TiR TnRpTq=+(6)其中，ni为 qi处的单位法向量。如图 2 所示为点到点(point to point)ICP 与点到平面(point to plane)ICP 的示意图，P 和 Q 分别代表源点云和目标点云。相较于点到点的 ICP 算法，点到平面的 ICP 算法更能体现点云的空间结构，能更好地抵抗错误对应点对，迭代收敛的速度更快。Figure 2.Schematic diagram of distance calculation 图图 2.ICP 距离计算示意图 龙纪安 等 DOI:10.12677/orf.2024.141063 677 运筹与模糊学 在 ICP 获取匹配点云对时，容易引入噪声，使得特征点不能完全的一一对应，对配准结果产生影响。对此，参考文献13的方法，通过设置法向量约束条件来剔除误匹配点。具体方法为：对于特征点对 A和 B，其法向量分别为 nA和 nB，当 nA和 nB差距越大，其夹角的余弦值越小，通过设置夹角余弦阈值 F，将法向量 nA和 nB的夹角余弦值小于 F 的点视为误匹配点，并将其剔除。4.实验结果与分析实验结果与分析 本文使用斯坦福大学提供的标准点云扫描数据 bunny、Armadillo 和 happy 作为实验对象，将同一点云模型在两个不同视角下的数据作为配准实验的源点云与目标点云，以本文算法作为实验组，SAC_IA+ICP 算法和 NDT+ICP 算法作为对照组进行实验，通过比较三种算法的配准结果和性能指标，来验证本文算法的可行性。4.1.实验结果实验结果 如图 3 中(a)所示为 3 个待配准点云对象的源点云和目标点云，将这 3 个点云模型经过本文算法、SAC-IA+ICP 算法和 NDT+ICP 算法后，得到其后(b)、(c)、(d)所示的配准结果。Figure 3.The experimental results of the three groups.(a)Point cloud to be registered;(b)Pro-posed algorithm.(c)SAC-IA+ICP algorithm;(d)NDT+ICP algorithm 图图 3.三组实验结果(a)待配准点云；(b)本文算法；(c)SAC-IA+ICP 算法(d)NDT+ICP 算法 通过图 3 可以直观地看出，在三组实验中，本文算法的配准结果均比其余两个算法的配准效果好，配准后的源点云和目标点云能更加贴合在一起，说明本文算法在配准精度上更优于传统的 SAC-IA+ICP算法和 NDT+ICP 算法。龙纪安 等 DOI:10.12677/orf.2024.141063 678 运筹与模糊学 4.2.算法性能分析算法性能分析 为了更直观地分析本文算法的性能，通过统计 3 个算法的耗时与配准结果的均方根误差(MSE)，如表 13 所示，来比较 3 个算法的性能。为保证算法的可比性，在保证配准精度变化不大的情况下，使用体素网络下采样的方法对 SAC-IA+ICP 算法和 NDT+IC 算法的数据进行下采样操作，得到下采样后的精简点，再使用此精简点集执行后续配准操作。Table 1.Algorithm performance in this paper 表表 1.本文算法性能 实验对象 源/目标点集数量 特征点数量 算法耗时/s MSE bunny 40256/40097 526/558 1.986 5.00847e-06 Armadillo 28476/26941 514/514 1.723 7.14344e-06 happy 59544/51266 336/288 1.591 1.97183e-06 Table 2.Algorithm performance of SAC-IA+ICP 表表 2.SAC-IA+ICP 算法性能 实验对象 源/目标点集数量 精简点数量 算法耗时/s MSE bunny 40256/40097 17255/16628 68.430 7.92295e-06 Armadillo 28476/26941 12456/11911 42.100 1.03013e-05 happy 59544/51266 21745/19937 29.224 6.83866e-06 Table 3.Algorithm performance of NDT+ICP 表表 3.NDT+ICP 算法性能 实验对象 源/目标点集数量 精简点数量 算法耗时/s MSE bunny 40256/40097 17255/16628 7.826 7.09696e-05 Armadillo 28476/26941 12456/11911 12.354 8.77107e-06 happy 59544/51266 21745/19937 7.762 2.89486e-06 从表 1表 3 可以看出，本文算法使用了 SIFT 关键点提取算法后，可以将原始点集的数量大幅缩减，减少到原来点数的 1.5%左右，而 SAC-IA+ICP 算法和 NDT+ICP 算法由于使用的是传统的下采样来精简点云数量，在保证精度的条件下精简后的点云数量为原来的 40%左右，使得用于粗配准和精配准的点云数目较多，所以算法更加耗时。另外，从配准的 MSE 上可以看出，本文算法相比于另外两种算法拥有更加小的 MSE，说明本文算法配准结果更加精细。通过统计平均数据可知，本文算法在算法耗时上相比于 SAC-IA+ICP 算法提高了 96.2%、相比于 NDT+ICP 算法提高了 81.0%，在 MSE 上相比于 SAC-IA+ICP 算法提高了 43.6%、相比于 NDT+ICP 算法提高了 24.7%。5.总结总结 本文针对传统配准方法中的粗配准后精配准的策略耗时长、精度低的问题，提出使用 SIFT 提取原始点云的特征点，在保留原始点云关键特征的条件下尽可能低降低了配准过程的数据量，再将这些特征点经过 SAC-IA 粗配准后，通过结合了法向约束的点到面 ICP 算法进行精配准，大大提高了配准的效率，相较于传统配准策略在算法耗时和配准精度上均有明显的提升，证明了本文算法的有效性。参考文献参考文献 1 杨佳琪,张世坤,范世超,等.多视图点云配准算法综述J.华中科技大学学报(自然科学版),2022,50(11):16-34+43.https:/doi.org/10.13245/j.hust.221102 龙纪安 等 DOI:10.12677/orf.2024.141063 679 运筹与模糊学 2 刘畅文,李波,潘江涛,等.基于ISS-3DSC的NDT三维点云配准算法研究J.激光与红外,2023,53(5):777-783.3 Rusu,B.R.,Blodow,N.and Beetz,M.(2009)Fast Point Feature Histograms(FPFH)for 3D Registration.IEEE Inter-national Conference on Robotics and Automation,Kobe,12-17 May 2009,3212-3217.https:/doi.org/10.1109/ROBOT.2009.5152473 4 Besl,P.J.and Mckay,H.D.(1992)A Method for Registration of 3-D Shapes.IEEE Transactions on Pattern Analysis and Migence,14,239-256.https:/doi.org/10.1109/34.121791 5 Low,K.L.(2004)Linear Least-Squares Optimization for Point-To-Plane ICP Surface Registration.Technical Report TR04-004,University Olina,Chapel Hill,1-3.6 Rusinkiewicz,S.(2019)A Symmetric Objective Function for ICP.ACM Transactions on Graphics,38,1-7.https:/doi.org/10.1145/3306346.3323037 7 Serafin,J.and Grisetti,G.(2015)NICP:Dense Normal Based Point Cloud Registration.2015 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS),Hamburg,28 September 2015-2 October 2015,742-749.https:/doi.org/10.1109/IROS.2015.7353455 8 王文博,田茂义,俞家勇,等.改进的迭代最近点点云配准方法J.激光与光电子学进展,2022,59(2):390-399.9 刘雷,柏艳红,王银,等.基于 3DSIFT 和 BSHOT 特征的点云配准方法J.激光与红外,2021,51(7):848-852.10 范林林,王军义,徐志刚,等.大型工件部分点云与整体点云的配准方法J.计算机辅助设计与图形学学报,2023,35(9):1323-1332.11 张赵良,董一鸣,朱菊香,等.基于 ISS 特征点结合改进ICP 的点云配准算法J.应用激光,2023,43(6):124-131.https:/doi.org/10.14128/ki.al.20234306.124 12 贾雯晓,张贵仓,汪亮亮,等.基于 SIFT 和改进的 RANSAC 图像配准算法J.计算机工程与应用,2018,54(2):203-207.13 孙培芪,卜俊洲,陶庭叶,等.基于特征点法向量的点云配准算法J.测绘通报,2019(8):48-53.https:/doi.org/10.13474/ki.11-2246.2019.0250