一种结合随机采样一致性与主成分分析的点云配准方法

苏 宇，刘海燕*，李国勇

（1.广西科技大学 机械与汽车工程学院，广西 柳州 545616；2.河池职业教育中心学校 机电系，广西 河池 547000）

0 引言

点云配准是以两片点云数据为输入，通过计算输出一个表示位姿变换，包含旋转以及平移的变换矩阵，以尽可能地对齐输入的两个点云数据。常见于物体的三维重建、三维建图、目标定位等技术中，如模型和场景重建、自动驾驶汽车、机器人智能识别抓取等领域。对近三年在“计算机视觉与模式识别国际会议（CⅤPR）”上发表论文的关键词进行统计，发现“3D”和“配准（registration）”可以进入论文关键词排名的前七名，且呈逐年上升的趋势；因此，三维点云配准研究有着非常重要的意义。

从目前研究现状分析，点云配准方法主要包括基于局部特征的点云配准、基于全局匹配的配准方法。基于局部特征的点云配准是通过源点云和目标点云在局部关键点（特征点）以及其对应的特征描述子进行计算配对，然后利用对应的特征点求解位姿变换矩阵。传统计算点云关键点的方法主要包括从二维图像特征点计算方法演变的Harris 特征点检测、最小核值相似区角点检测（SUSAN）、尺度不变特征变换检测（SIFT），以及从3D 数据处理中源生的内部形状描述子（intrinsic shape signatures，ISS）特征点检测。特征点的特征描述常见方法主要从点的空间几何关系进行计算，其代表方法包括点特征直方图PFH、快速点特征直方图FPFH、基于方位签名直方图SHOT等，还有引用图像轮廓识别进行特征点配准的方法。但基于局部特征的配准由于其特征点描述数据缺乏全局信息等因素，因此并不包含对全部点整体最优的求解。

基于全局点云匹配的配准方法包括基于全局特征的配准，如提取平面进行两片点云的平面位姿变换，但该方法需要进行点云分割，易受配准模型表面特征影响。全局配准更多以源点云和目标点云在所有重合部分尽可能匹配的思路，利用数值计算优化方法进行循环迭代求出最优解，即求出旋转平移矩阵为主。主要有迭代最近点法（ICP）和基于最大似然的正态分布变换（normal distribution transform，NDT）。相较于NDT，ICP 实现简单、稳定，且发展较为成熟。但基于全局匹配配准方法需要源点云与目标点云的位姿不能相差太大，否则容易陷入局部最优解。

由于以上2 种点云配准方法自身的优点与缺点，局部+全局配准作为点云配准主框架是一个很重要的研究方向。其中，在局部配准中，利用随机采样一致性（RANSAC）多次迭代可有效避免特征点对应关系误差，在应用中较为常见，但其稳定性受迭代次数影响，需要足够的迭代次数保证稳定性。本文的研究重点是如何在RANSAC 局部配准中，保证稳定性的同时，降低运行时间。与只针对相同类型的点云进行实验不同，本文使用了3 种不同类型的点云数据作为实验对象，基于局部特征配准后全局精配准的主框架，采用ISS关键点检测，增加非最大抑制（NMS）以避免关键点在某些局部特征点过多的情况；利用FPFH进行特征数据描述与匹配，提出基于随机采样一致性（RANSAC）和主成分分析（PCA）进行局部配准，并利用ICP 方法进行优化配准的点云配准方法。整体基本框架如图1所示。

图1 点云配准基本框图

1 局部关键点配准

点云配准的关键是计算出一个空间变换矩阵，利用所求得的变换矩阵对源点云进行坐标变换，使得坐标变换后的点与目标点云有尽量多的重合点，但点云数据的点数据量较大。由于运算量大和陷入局部最优等问题，在迭代优化计算过程求初始解时，使用所有点云点计算优化求解会导致计算时间过长，所求解可能为局部最优解；因此，传统处理方法主要利用点云中的部分局部关键特征点来求初值，即局部关键点配准。由于关键特征点的特征计算方法、对应点选取方法以及计算两片点云的变换矩阵方法不同，其整体效果在运算时间以及稳定性等方面有所区别；因此，对局部关键点配准问题的研究包括了点云特征关键点提取、关键点描述子计算与对应关系确定和配准方法的选取与优化。本文主要通过实验对比分析点云特征关键点提取方法，提出了利用RANSAC 结合PCA 方法计算两片点云变换矩阵，对应了上文点云配准基本框图中的前3个模块。

1.1 关键点检测提取

ISS 内部形态描述子主要检测点云中在其空间邻域内点的分布有较大变化的点，即能代表物体立体几何形状的点，它通过计算每个点及其邻域内的点组成的协方差矩阵特征值去检测。基本计算步骤如下：

1）假设点云数据共个点，对于点云中的第点，需要找出以该点为中心，半径为邻域内的所有点（为设定的超参数）。以欧式距离的倒数计算所有这些点与第点的连接权重位，与第点越远，其权重越小：

2）利用第点半径为邻域内所有点与中心点在空间3 个维度上的相对偏移量，建立第点在半径为邻域内的带权协方差矩阵：

根据以上步骤，在遍历完点云所有个点后，即可得ISS关键点集。

1.2 非最大抑制（NMS）选取关键点

为避免在物体每个特征处聚集太多关键点，影响后续的配准计算效率，增加对初步计算的ISS关键点集的非最大抑制处理：

1）集中关键点，根据每一个点S的第三个ISS特征值，由大到小进行关键点排序，形成队列；

2）取出队列的第一个关键点（队列中最大的点）放入新的关键点集，在中计算查找以为中心，半径为的邻域内其他关键点S，并把所有S、移除出队列。

3）重复第二步，直至为空，为最终的关键点集。

1.3 计算关键点特征描述子

关键点特征描述子以数据的形式表达关键点特征。本文采用在PFH 基础上改进的FPFH，其基本原理是通过捕捉一个点及其邻近点在物体表面的差异，通过直方图进行统计描述，计算简单、有效，具有旋转不变的特性。其关键计算包括：

1）计算给出点p，查找出在其半径为的邻域内的所有邻近点p，分别与p连接对子，对每个p查找其半径邻域内的所有邻近点，并与每个邻近点连接对子（不包括已经存在的连接对子）。

2）计算每对连接对子2 个点的法向量（，）和三元组数据[，，]的直方图统计值SPFH（图2）。

图2 三元组示意图

3）基于加权统计，计算每个点的FPFH。

4）循环遍历每个关键点，计算所有关键点FPFH。

每个关键点FPFH 直方图向量有33 维（三元组数据、、共3类数据，每类数据按11个区域划分，共3×11维）；因此，本文采取对源点云关键点直方图数据建立KD 树的方式，以KD 树进行最近邻搜索，搜索到离目标点云最近的关键点FPFH，建立关键点对应关系组，加快了计算效率。

1.4 RANSAC+PCA粗配准

由于一个物体、场景在不同的地方可能存在相似的特征，或者由于待配准点云误差、噪声影响等因素，关键点描述子对应关系组会存在错误的配对。RANSAC 即是在有部分错误配对的对应关系组中随机选取3 对对应关系，形成三角形到目标三角形的位姿变换求解问题，并通过SⅤD 求解出旋转矩阵和偏移量，在多次随机选取迭代中优化计算两片点云的变换矩阵。RANSAC 可以有效应对数据噪声，理论上只要对应关系组中有3组以上的正确配对，在足够多次的迭代条件下都可以求出正确解；因此适用于两片点云的配准，但稳定性及计算时间易受关键点对应关系正确配对率影响。针对此问题，本文根据3 个采样点的几何特性，提出随机采样过滤方法，以降低迭代次数，并利用点云主成分分析设置计算变换矩阵条件，降低无效变换矩阵求解次数，提高粗配准的稳定性和运算时间。

1.4.1 随机采样过滤

依据随机选取的3对关键点对应关系，在源点云和目标点云中分别提出3个关键点进行SⅤD求解变换矩阵，理想的采样点是能反映在两片点云中同一个地方的3 组点（图3）。为避免无法求解和无效解，、、和、、不能处于同一直线，尽量避免有接近0°的3点组。基于物体几何特性，3个采样点之间的欧氏距离应与另一片点云的3个采样点之间的欧氏距离相似，且角度相似；因此，利用这些特征可进行过滤随机采样，降低无效计算。

图3 采样点示意图

本文设计以下过滤条件：

1）（，，）、（，，）、（，，）为非共线约束点，即3点不在同一直线上：

2）在两片点云中采样的3个点的相互距离及形成的角度应大致相当：

其中：为最大边长比例参数，为角度差参数。

对每一对对应3 点组，根据普鲁克变换定理，利用SⅤD 求解即可求出该对3 点组对应的变换矩阵，在此基础上即可对多个对应3 点组进行RANSAC计算。

1.4.2 基于投票机制的PCA过滤

原始的RANSAC 需要多次的迭代计算。为降低迭代次数与计算量，本文提出了基于投票机制的PCA 过滤，以降低迭代次数与计算量。PCA 是一种以特征向量分析多元统计分布的方法，点云是由多个表示三维坐标系统中多个位置的向量组成的集合。利用PCA 对点云进行处理，可找出点云在三维空间坐标中的3 个分布方差最大的方向，即3个主要分布方向。两片点云需要有一定的重合比例才能进行配准，比如在前后2个时刻的场景点云有相似的点分布主方向。且在一些有较大部分对称的物体中，点云存在对称性问题；姿态求解可能存在镜像问题；所求变换矩阵与正确值对称，仍能计算出较高配准率。针对以上特性及问题，本文提出了在RANSAC 求位姿变换矩阵中融合PCA 主方向分析，以降低过滤随机取样中出现的无效取样计算，在高对称点云配准中避免镜像解。在较大重合点云配准中提前终止RANSAC迭代，降低迭代次数。

1）计算点云分布协方差矩阵。为避免点云中较远分布点对PCA 处理中的过多影响导致误差，增加距离权重计算点云分布协方差矩阵，以点空间位置平均值作为中心点，以为半径内的点P计算协方差矩阵（或以与最近的个点），越靠近点，其权重越大：

其中：d为p到的欧式距离。

2）对进行SⅤD 求解，求出特征值及特征向量，并根据特征值从大到小排序，求出的3个特征向量、、，对应3 个点云分布PCA 主轴方向。再利用中心点邻域内所有点的分布统计进行PCA主轴正方向修正。

同理，修正的正方向，并以与的叉乘修正正方向。

3）根据RANSAC 中求解出的旋转平移矩阵进行源点云旋转平移后，与目标点云进行以下PCA过滤（为方向向量偏移量参数）：

|·| ≥∧|·| ≥∧|·| ≥.（19）

在过滤结果的基础上进行RANSAC 局内点统计迭代。针对较大重合率的点云配准可增加配准率判断，设置提前退出RANSAC 迭代的条件，最终经过多次迭代，选出局内点最多的一次即为粗配准的结果。

2 全局ICP配准（精配准）

粗配准的结果保证了一个较好的初始配准，但其优化过程只针对关键点进行；因此，需在此基础上进行全部点全局配准。本文采用比较成熟的迭代最近点法（ICP）进行优化，即对两片点云中重叠部分的点进行欧氏距离均值最小迭代求解。每次迭代后，更新一次点云的配准位置，当达到终止迭代条件后即可得所求解，该方法属于数值优化求解方法。终止迭代条件为当前计算值与上一轮迭代计算值的差值少于设定阈值，迭代结束时的计算值即为最终的求解配准变换矩阵。

3 实验结果及分析

为验证算法，本文选用3 类点云作为实验数据。第一类选用三维数据库Modelnet 中的飞机物体点云，源点云与目标点云中的点分布重合率较高，点的数量比为8.3∶10，属于重合点云的配准。第二类选用自动驾驶领域KITTI 数据集中的道路激光雷达点云，源点云与目标点云分属前后时段获取的场景点云，属于有较大部分接近重合，其他部分完全不一样的点云配准。第三类选用斯坦福大学的三维扫描模型Bunny 兔子点云，目标点云为完整物体点云，待配准点云为45°获取的物体部分点云，属于部分重合点云配准。

以ubuntu16.04 系统和python 编程语言的Jupyter Notebook开发环境搭建实验平台。在实验结果测试中，选用了开源点云库open3D中的点云配准率估计方法作为配准率计算方法，该方法基于配准后点（重合部分）在目标点一定阈值半径内的数量比例。结合算法的流程主要对2个方面进行实验、分析。

3.1 关键点提取与对应关系组计算

以提取约350 个关键点作为参数设置，使用2种不同类型的关键点检测方法，以激光雷达扫描道路点云进行实验：ISS 关键点检测与基于法向量投影变化的关键点检测（RR 关键点）。实验结果如图4（a）所示，ISS关键点检测的点云关键点分布都具有物体的轮廓特征；基于法向量投影变化关键点检测的点云关键点，实验结果如图4（b）所示，关键点主要聚集在一些“特征”区域。

图4 (网络版彩图)关键点分布图

对以上关键点计算FPFH，建立对应关系组并进行RANSAC粗配准，利用2种特征检测方法，以相同的迭代次数（5万次）循环重复运行20次程序进行实验。在计算时间上，RR 关键点检测平均用时7.01 s，而ISS 关键点检测只需0.73 s。以0.01 为配准率检测阈值，实验结果如图5所示。

图5 (网络版彩图)不同关键点检测方法粗配准结果

在实验中，ISS 关键点比RR 关键点的RANSAC 粗配准有更稳定和更高的配准率。从RANSAC 粗配准计算原理分析，其变换矩阵是通过2组3个对应关键点进行SⅤD计算。如果在较小区域内取样进行一致性计算，由于尺度放大的原因，较小的误差会导致所求变换矩阵应用到整个点云上的大误差。当两片点云的关键点对应关系有较高精度时才能保证重合点的配准。在应用中，较难获取高精度的点云数据，结合运行时间，本文选用ISS关键点检测方法。

图6为3个点云数据利用ISS和FPFH建立的关键点对应关系图。从关键点对应关系图以及实验结果分析，不管是高度重合的飞机点云数据，还是高分辨率的兔子点云建立的关键点对应关系都存在一定比例的错误配对，这也验证了利用RANSAC 进行粗配准的合理性。其中有较高重合率的飞机点云所建立的关键点对应关系准确率最高，后2个配对点云在点分布和点数量上有不少差异，其对应关系准确率相对较低。

图6 (网络版彩图)关键点对应关系

3.2 配准结果及对比分析

点云配准效果主要包括配准稳定性、配准率以及配准运行时间。针对这3 个指标，对以上3 个点云分别进行了测试，具体参数如表1所示，并以单独ICP 与纯RASAC+ICP 进行比较。结果表明，仅使用ICP进行配准的方法全部失败，本文的配准方法都成功配准，源点云的整体姿态与目标点云的整体姿态基本一致，其结果如图7 所示（红色点为配准点云，灰色点为目标点云）。

表1 主要参数表

图7 (网络版彩图)本文点云配准方法的配准结果

为进一步比较分析，设置相同的迭代次数和配准率阈值，分别利用RANSAC+ICP与本文提出的点云配准方法（RANSAC+PCA+ICP）对3种点云数据进行配准计算，其运行时间对比如表2所示，结果如图8所示。在图8中，还增加了无ICP情况下RANSAC和RANSAC+PCA 这2 种配准方法的测试比较，目的是比较有无ICP精配准情况下的测试结果。

图8 (网络版彩图)不同配准方法配准率曲线图

图8 (续)

表2 2种方法运行时间对比单位：s

从2种方法运行时间分析，本文方法的总运行时间比RANSAC+ICP 方法有一定的提升，对3 种点云数据的运行时间分别降低7.60%、13.49%、15.64%，实验中也表明，随着迭代次数的增加，本方法在计算时间上提升越多。从每个模块运行时间分析，2种方法中各模块的运行时间占比基本一致。以本文方法运行道路点云为例，计算特征点并建立对应关系时间占7%，粗配准时间占68%，精配准时间占24%，可见粗配准耗时占主要比例，粗配准迭代次数增加会明显提高运行时间。实验结果也表明，尽管ICP 的初始姿态会影响运行时间，但只要能保证通过粗配准可提供一个能保证ICP 成功配准的粗姿态，则并不一定要求一个配准率很高的粗配准。在粗配准中增加迭代次数，可以提升配准率，但也意味着运算成本提高，且相对ICP 迭代，运算时间增加的幅度更大，这也验证了本文提出的PCA 主方向过滤的合理性。利用PCA 主方向的限制，保证粗配准后与目标点云有接近的主方向，确保经过RANSAC 后有一个“合格”的粗配准。

从配准率结果分析，在相同的迭代次数下，RANSAC+ICP 方法在飞机、道路点云实验中都能稳定实现配准，但在兔子点云中，出现一次低于稳定正确配准10%的配置，而本文方法在3种数据中都能稳定实现正确配准。由于是基于随机采样，在一定迭代次数条件下，粗配准的配准率在每一次实验中并不稳定，但在飞机点云上，本方法的粗配准模块几乎达到了ICP配准后的配准率，这表明在源点云和目标点云点分布相似的情况下，即主成分向量接近相同的两片点云配准，在配准精度要求一般的情况下，本文提出的RANSAC+PCA粗配准可直接应用而不需ICP精配准。在有一定差异度的两片点云配准中，也可有效控制配准稳定性，减少RANSAC粗配准的耗时。

4 结语

本文提出的RANSAC+PCA+ICP 点云配准方法，解决了ICP 算法在位姿相差较大的点云配准中无法计算全局最优解的问题。结合条件过滤与PCA，在RANSAC 粗配准中降低迭代次数和减少在点要求不高的情况下可省去ICP 精配准。可应用于机器人智能抓取目标位姿定位、多张三维扫描点云配准物体重建、激光雷达道路点云配准建图。在重合度较少导致点云分布有较大差别的情况下，如何建立高准确度的对应关系，以及计算两片点云主分布方向向量差异度与关键点的关系将是下一步的研究方向。