摘  要：迭代最近点（ICP）配准算法需要两点云处于良好的初始位置，否则在配准时容易陷入局部最优。针对该问题，提出了一种基于内部形状描述子（ISS）特征点与改进描述子的粗配准方法，使得低重叠度或无公共重叠部分的点云获取良好的初始位置。首先，利用ISS特征点提取点云的特征点;其次，基于特征点与其邻域点法向量夹角提出改进的描述子，根据描述子的欧氏距离将点云特征进行匹配;第三，通过单次最优变换进行粗配准;最后，对两点云进行精配准ICP迭代。实验表明，在点云模型完整的情况下，本文方法可为精配准提供良好的初始位置，且粗配准精度比传统点云配准精度高三个量级，配准效率提升23.7%。

关键词：点云粗配准;ISS特征点;改进描述子;ICP算法

中图分类号：TP391.1     文献标识码：A

文章编号：2096-1472（2022）-01-01-05

Abstract： Iterative closest point registration algorithm （ICP） requires two point clouds to be in a good initial position， otherwise it is easy to fall into a local optimum during registration. In view of this problem， this paper proposes a coarse registration method based on Intrinsic Shape Signatures （ISS） feature points and improved descriptors， which makes point clouds with low overlap or without common overlap obtain a good initial position. Firstly， ISS feature points are used to extract the feature points of the point cloud. Secondly， an improved descriptor is proposed based on the angle between the feature points and the normal vector of the neighboring points， and the point cloud features are matched according to the Euclidean distance of the descriptor. Then， rough registration is carried out by single optimal transformation. Finally， precision registration ICP iteration is conducted for the two-point clouds. Experimental results show that the proposed method provide a good initial position for fine registration under the condition of complete point cloud model; the coarse registration accuracy is three orders of magnitude higher than that of traditional point cloud registration， and the registration efficiency is improved by 23.7%.

Keywords： point cloud coarse registration; ISS feature points; improved descriptor; ICP algorithm

1   引言（Introduction）

隨着三维传感器设备的发展，点云配准广泛应用于三维重建、三维定位与姿态估计等方面。点云配准的目标在于获取待配准两点云的位姿变换关系，将不同角度下采集得到的点云变换到同一坐标系下。传统的点云配准算法是由BESL等[1]提出的迭代最近点（ICP）算法，该算法需要两点云具有良好的初始位置，即点云重叠度高，点云数据量相近。

针对该问题，许多学者对ICP算法进行了改进和创新，并提出了新的配准算法以解决位姿差异较大的点云匹配问题。钟莹等[2]使用主成分分析法（Principal Component Analysis， PCA）对点云进行粗配准以获取良好的初始位姿，避免ICP陷入局部最优。宋成航等[3]基于从法向量角度对特征点对的约束并结合快速点特征直方图（FPFH）[4]，提出了利用采样一致性改进ICP的配准算法。正态分布配准（Normal Distribution Transformation， NDT）算法[5]利用点云的正态分布，通过最优化方法求出使概率密度之和最大的变换参数。结合NDT算法，荆路等[6]提出了基于SAC和NDT融合的配准算法;王庆闪等[7]提出了基于NDT与ICP结合的配准算法。但是，上述算法运行时间较长或对参数的调节较多，需要重复地实验来确定理想的参数。

综上，本文提出一种基于内部形状描述子（ISS）[8]特征点检测与改进描述子匹配的点云配准算法。首先对下采样后的两点云提取ISS特征点;然后结合改进的描述子计算特征向量并匹配对应点对，对点云进行粗配准;最后，利用ICP算法进行精配准。本文实验验证了改进描述子的特征点对的匹配率为91.67%，同时与文献中的点云配准算法进行了对比试验。

2   算法介绍（Algorithm introduction）

针对传统ICP算法存在收敛速度慢，容易陷入局部最优且需要良好的初始位姿及较高的重叠度等问题，本文提出一种基于ISS特征点与改进描述子的点云配准方法，算法流程图如图1所示。首先，对两点云进行下采样以减小点云复杂度。其次，对点云进行ISS特征点检测并计算点云法向量，接着对特征点应用改进的描述子计算特征值向量，为提高特征点对的匹配准确度，设置并基于欧氏距离对特征向量进行匹配。第三，在匹配的对应特征点的基础上运用单次最优化变换求解粗配准变换矩阵。最后，采用K维树近邻搜索算法加速对应点的查找，对两点云应用ICP迭代算法，完成点云精配准。

3   点云粗配准（Coarse registration of point clouds）

3.1   ISS特征点提取

在传统点云配准ICP中，需要得到待匹配两点云的对应点对。由于点云数量较大，一般提取点云中几何特征明显的点来代表整体点云。常见的点云特征点检测算法有3D-Harris[9]关键点算法、3D-SIFT[10]算法、内部描述子（ISS）算法等。本文实验验证，ISS特征点检测算法与改进描述子对点云粗配准效果较好。内部描述子（ISS）是一种表示立体几何形状的方法，该算法具有丰富的几何信息，可以完成高质量的点云配准。ISS特征点算法检测原理如下。

设点云中含有n 个点，，ISS关键点算法具体流程如下：

Step 1：对点云中的每个点建立一个局部坐标系，如图2所示，并对每个点设定一个搜索半径r。

Step 2：利用KD树确定点云中每个以为中心、r为半径区域内的所有点，并计算这些点的权值，权值表达式为：

Step 3：计算每个点的协方差矩阵：

Step 4：计算每个点的协方差矩阵的特征值，将特征值按从大到小的顺序排列。

Step 5：设置阈值与，满足以下条件的点即为ISS特征点。

3.2   改进描述子

对两点云分别应用ISS特征点检测算法提取关键点后，需要将关键点进行匹配并形成两点云的特征点匹配对。本文基于2D-SIFT算法对特征点的描述提出改进特征点描述符算法，并采用描述符特征值向量的欧氏距离进行特征点对的匹配。为提高点云粗配准的精准度，设置一个阈值（本文设为0.3），对匹配点对的描述子欧式特征距离小于该值的进行删除。算法具体流程如下：

Step 1：计算点云的法向量，利用KD树搜索距离ISS特征点周围512 个3D点并存储其法向量。

Step 2：将ISS特征点周围512 个3D点划分为16 个三维空间并将其按距离排序，如图3所示。

Step 3：对每个三维子空间分配一个坐标系，该坐标系将360°分为32 个区段，每个区段的角度范围为11.25°。在每个三维子空间中计算每个点与ISS特征点的法线夹角并将其映射至坐标系中。注意，每个点的法向量是有正负差别的，需要在计算前对法线方向进行调整，使之朝向一致。

Step 4：统计落入坐标系每个区段的个数，则每个子坐标系为32 维向量，最后将16 个子空间进行合并，一共形成512 维向量的特征描述符。

Step 5：基于特征描述符之间的欧氏距离对ISS特征点进行匹配。预设阈值（本文预设为0.3），剔除两点云ISS特征点特征描述符之间的欧氏距离大于阈值的特征点对，提高点对配准的成功率。

该方法主要考虑了特征点邻域的法向量与特征点的法向量角度差。相较于其他算法只统计周围三维点与特征点的关系致使大部分角度差信息融合在一个区段，本文算法对特征点邻域的距离进行分类并排序，总共分为16 个子空间，结合距离与角度差的信息使得特征点的辨识度提高。在提高对应特征点对的配准率上，经过实验分析，预设了阈值来确保对应点对的正确性。

3.3   粗配准

基于ISS特征点检测与改进描述符特征点对的匹配，待配准的两点云对应点对已基本确定。ICP精配准需要良好的初始位置或重叠度较高的两点云，其目的在于確定基于欧氏距离的对应点对以进行迭代优化。本文基于ISS特征点检测与改进特征描述符确定了两点云中的对应点对，故在点云的粗配准阶段使用ICP的单次迭代以获取初始变换矩阵。对于点对点迭代最近点（Point-to-Point ICP）问题，求解点云的最优变换有封闭式解，变换矩阵可以借助SVD分解得到。算法具体计算过程如下：

Step 1：设两组点云和，点云数量分别为、。首先计算两组点云的中心、的坐标。

Step 2：对两点云进行归一化，并得到点云的协方差矩阵。

Step 3：对点云的协方差矩阵进行SVD分解得到，则Point-to-Point ICP的最优旋转矩阵如下：

Step 4：对矩阵作方向验证，以确保是一个旋转矩阵而不是一个映射矩阵，将优化结果确定一个的约束。

将上一步得到的刚体变换矩阵应用于源点云，得到新点云。粗配准阶段利用的是点云的对应点对进行匹配，本文算法允许点云零重叠即二者相距一定距离，相较于传统粗配准算法有一定优势，且由于对应点对的正确匹配，粗配准效果较好，点云重叠度高，利于接下来的点云精配准ICP的迭代优化。

4   ICP精配准（ICP fine registration）

经过ISS特征点检测、改进描述子匹配与点云粗配准，变换后的源点云与目标点云的重叠度已经较高，具有良好的初始位姿。ICP算法是利用KD树以点对间的欧氏距离为标准寻找对应点对，点云位姿差异过大会导致算法陷入局部最优从而无法匹配成功。而经过本文算法的处理，点云位姿基本保持一致，适用于ICP算法的精配准。精配准ICP主要流程如下。

Step 1：将粗配准后的点云与目标点云作为精配准的原始点集。

Step 2：基于点对间的欧氏距离，利用KD树搜索对应点对。

Step 3：求解点云的旋转矩阵与平移矩阵，其目标函数如下，其中和是源点云与目标点云中的匹配点对：

Step 4：设定阈值与迭代次数，如果两次迭代的矩阵变化量小于阈值或总迭代次数大于，则迭代结束。

5  实验结果与分析（Experimental results and analysis）

5.1   改进描述子辨识度实验

为验证本文提出的改进形状描述子对不同特征点检测算子的鲁棒性，分别选取3D-Harris、ISS、3D-SIFT-Z（Z方向梯度约束）和3D-SIFT-N（曲率不变特征约束）进行点云粗配准的匹配。本文采用的点云模型为斯坦福兔子（Bunny），将源点云模型旋转30°并平移0.3 m作为目标点云模型。实验在AMD Ryzen7-4800H@2.90 GHz、16 GB RAM、Windows 10 64 位家庭版操作系统、VS 2017开发平台、PCL 1.8.1版本环境下运行，采用C++编程语言。实验效果如图4所示。

经过对不同特征点检测算子的实验比较，发现ISS与改进的描述子契合度最高。如表1所示，ISS+改进描述子的粗配准算法时间最少且对应特征点对的匹配程度最高。为了单纯检测改进描述子的鲁棒性，在上述Bunny点云模型的对应点对匹配中未设置阈值。在实际点云配准整体算法中，由于点云数量较多而产生误匹配问题，对算法需要设置阈值以提高对应点对的匹配成功率。

5.2   基于ISS特征点+改进描述子的点云配准

基于以上实验，最终确定了ISS特征点+改进描述子+ICP的点云配准整体路线。为了体现算法对不同模型的适配性，分别选用Bunny、Armadillo、Buddha及Dragon四个点云模型，并在此基础上分别做旋转和平移以获取目标点云模型。实验结果如图5所示。

从实验结果可以看出，本文提出的算法较好地完成了点云配准，具体数据如表2所示。与传统ICP算法需要待匹配的两点云部分重叠且具有良好的初始位姿相比，本文算法可以在无重叠的情形下进行点云的配准且算法时间较短。

5.3   面向Bunny模型的不同配准算法实验比较

为了验证本文算法的运算时间与精度优势，将本文算法与以往的点云配准算法进行对比。对Bunny模型分别旋转45°和22.5°并同时移动0.4 m得到两组目标点云，分别为目标点云1（Bunny_R225_04）与目标点云2（Bunny_R45_04），如图6所示。实验分为两组，第一组点云输入Bunny和Bunny_R225_04，第二组点云输入Bunny和Bunny_R45_04。

将本文算法与“基于NDT与ICP结合的点云配准算法”“基于SAC-IA和NDT融合的点云配准方法”和“利用特征点采样一致性改进ICP算法点云配准方法”三种方法进行对比，分别输入上述两组点云。上算法与本文算法均在VS 2017、PCL 1.8.1及C++环境中运行，点云配准误差由均方根误差表征。实验结果如表3所示，实验结果可视化如图7所示。

通过实验结果可知，本文方法无论从配准时间还是精度方面都较其他配准方法有优势，与配准效果较好的SAC-IA+NDT算法相比，其配准效率提升了17.4%，配准精度提高了三个量级。由此可知，在两点云模型是经过旋转平移而得到的情况下，本文算法的特征点对匹配度相对较高，因此基于正确对应点对的配准迭代所取得的变换矩阵精度高，配准速度快。

6   结论（Conclusion）

针对传统点云配准ICP需要两点云具有相对良好的初始位姿，否则算法容易陷入局部最优而导致配准失败的问题，本文从两点云的对应特征点匹配对的思路出发，提出ISS特征点检测与改进形状描述子的配准。通过将ISS特征点与其周围空间三维点进行距离分区，并各自统计每个分区三维点与特征点的法向量角度差并形成512 维的特征向量来进行点云对应点对的匹配。通过特征向量阈值的约束，点云的特征点对匹配度较高，提高了点云的初始匹配度，为最终点云的ICP提供了良好的初始位姿。但仍需注意的是，本文提出的改进形状描述子匹配对点云的完整性要求较高，特征关键点处的点云缺失会影响特征点的特征向量匹配，进而带来配准误差。

参考文献（References）

[1] BESL P J， MCKAY N D. A method for registration of 3D shapes[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 1992， 14（2）：239-256.

[2] 钟莹，张蒙.基于改进ICP算法的点云自动配准技术[J].控制工程，2014，21（01）：37-40.

[3] 宋成航，李晋儒.利用特征点采样一致性改进ICP算法点云配准方法[J].北京测绘，2021，35（03）：317-322.

[4] RUSU R B， BLODOW N， BEETZ M. Fast point feature histograms （FPFH） for 3D registration[C]// IEEE. IEEE International Conference on Robotics and Automation. Kobe： IEEE， 2009：3212-3217.

[5] BIBER P， STRASSER W. The normal distributions transform： A new approach to laser scan matching[C]// IEEE/RSJ. Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas： IEEE， 2003：2743-2748.

[6] 荆路，武斌.基于SAC-IA和NDT融合的点云配准方法[J].大地测量与地球动力学，2021，41（04）：378-381.

[7] 王庆闪，张军.基于NDT与ICP结合的点云配准算法[J].计算机工程与应用，2020，56（07）：88-95.

[8] ZHONG Y. Intrinsic shape signatures： A shape descriptor for 3D object recognition[C]// ICCV. Proceedings of the 12th IEEE International Conference on Computer Vision Workshops（ICCV Workshops）. Kyoto： IEEE， 2009：689-696.

[9] HARRIS C， STEPHENS M. A combined corner and edge detector[C]// AVC. Proceedings of the Alvey Vision Conference. Heidelberg： Springer， 1988：147-151.

[10] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision， 2004， 60（2）：91-110.

作者簡介：

夏坎强（1996-），男，硕士生.研究领域：机器视觉，图像处理.