基于RANSAC的点云配准优化算法

谢德芳，陈丛桂，周 聪，马亮华，黎鑫泽

（广州大学机械与电气工程学院，广州 510006）

0 引言

图1 算法流程图

1 滤波去噪

点云在特征提取、配准、曲面重建之前要进行预处理，预处理对点云处理有着重要意义，主要采用滤波去噪。

VoxelGrid[9]（体素网格）滤波有着很好的滤波效果，使用此滤波不仅能达到减少点云点集数目，也能保持点云的几何形状，维持原始形状特征，对于点云配准是一种理想的滤波方式。

VoxelGrid 滤波工作原理：三维点云中的体素是三维空间中的最小分割单位，即相当于二维图像中的像素。在输入点云数据上创建一个个体素网格（将体素网格视为一组空间中的微小三维空间）。然后，在每个体素中，所有存在的点将用它们的质心近似。因此VoxelGrid滤波可以保持三维点云的宏观几何形状。

2 RANSAC拟合

RANSAC 算法从一组数据集中，通过反复随机选择点集中的子集，达到拟合目标数学模型的效果。RANSAC 算法基本思想如下：假定目标数学模型，随机选择n个点，通过这n个点确定数学模型方程；在数据集选取点代入此数学模型方程，并计算误差；找出所有在误差范围内的点——局内点，剔除局外点。在设定的迭代次数命令下重复上述过程，局内点最多的模型为最优数学模型。

迭代次数推导如下：

式中：n为假定模型需要选取点的数目；p为迭代过程中从数据集内随机选取的点都为局内点的概率；ω为每次从数据集中选取一个局内点的概率，ω= 局内点数目/ 数据集数目，1-ωn是n个点中至少有1个点为局外点的概率；k为迭代次数。

形容词的意动用法，是指主语主观上断定宾语拥有某种状况，可以按照“认为宾语谓语”的格式来解释。如:“不耻下问”的意思是一个人不认为请教比自己地位低下的人是可耻的。“耻”是形容词的意动用法，解释为:认为……是耻辱的事情。

对式（1）左右两边取对数得：

考虑到迭代过程中每个点的选取都是独立的，某个点被选取之后，也可能会被选定，因此修正式（2），得修正后的迭代次数

3 粗配准

3.1 PFH和FPFH特征描述子

点云粗配准通过点的几何特征进行，如法向量、曲率等。但点周围的几何特征数量多且相似度高，无法得到点云的全局特征信息，因此有了点特征直方图PFH[10]（point feature histogram）。PFH 通过点和临近点的空间差异作出几何描述，PFH 提供的信息具有旋转不变性，对于点云而言十分稳健。

如图2 所示，Pq的PFH计算的影响区域，Pq用深色标注并放在圆球的中间位置，半径为r，(Pq)的所有k邻元素（即与点Pq的距离小于半径r 的所有点）全部互相连接在一个网络中。

FPFH（fast point feature histograms）在保持了PFH大部分特性的前提下，降低了算法的时间复杂度，提高了计算效率，本质上是PFH 的快速简化模型。只需要计算Pq（查询点）和紧邻点（图3）之间的特征元素。可知复杂度有所降低，称之为SPFH（simple point feature histograms）。

图2 查询点Pq的计算PFH的影响区域

图3 查询点Pq的计算FPFH的影响区域

确定点的k领域，得出最终Pq直方图公式如下：

3.2 SAC-IA配准

SAC-IA 配准（采样一致性初始配准：Sample Consensus Initial Aligment,SAC-IA），通过FPFH特征配准点云可得到一个大致的位姿，达到粗配准的效果。

配准算法步骤如下。

（1）源点云B中选取n个点，为了保证选取的点具备不同的FPFH特征，选取点的距离必须小于给定的最小阈值。

（2）目标点云A查找与源点云B满足相似条件的点，并保持一一对应关系。

（3）计算对应点的旋转矩阵和平移矩阵，并根据Huber函数进行评判：

式中：m为给定阈值；li为第i组对应点变换后的距离差。

重复上述步骤直至结果最优，即误差函数取最小值，得到最终的平移矩阵和旋转矩阵。

4 精配准

粗配准后仅仅得到一个较好的位姿，为了使两期点云尽可能重合，需要进行精配准。ICP算法的基本原理如下：两期点云 A 和 B，点集为 A={a1, a2, a3, …, an}、B={b1, b2, b3…, bm}，通过旋转平移变换后，点云A、B中的点一一对应。

式中：R为旋转矩阵；T为平移矩阵。

ICP配准的步骤如下。

（1）目标点云A中取点集ai，并在源点云B中找到对应点bi，使。

（2）计算旋转矩阵和平移矩阵，使目标函数取最小值。

（3）对目标点云A 进行旋转平移变换，更新得到新点云数据集A′。

（4）计算已更新点云A′和源点云B 中所有对应点的距离，做归一化处理，得。

（5）给定阈值，若平均距离d 小于给定的阈值，重复以上步骤，否则视为收敛。

通过上述步骤得到的旋转矩阵和平移矩阵，用于原点云坐标转换，完成配准过程。

5 实验结果和分析

本文实验在cpu 主频2.4 GHz， 内 存 为 4 G 的windows10系统下进行实验平台的搭建，使用C++进行编程，实验中选用的是PCL 开源库中的milk_cartoon_all_small_clorox 数据文件，点云数据中大约有240 000个点，实验结果如图4所示。

图4 配准结果

由实验结果可知，本文提出的配准优化算法可以满足点云配准的重合精度。此外，本文提出的配准优化算法和传统的配准算法相比较，配准速度有明显的提升，在保证配准精度的前提下，算法效率提高了29.5%。实验使用改进的配准算法和传统配准算法所消耗的时间如表1所示。

表1 传统算法和改进算法的比较

6 结束语

针对传统配准算法耗时不足的问题，本文提出了一种基于RANSAC算法的点云配准算法。首先，对点云使用RANSAC算法提取可以代替原点云的关键面，接着，使用FPFH特征进行粗配准，在粗配准的基础上使用ICP算法得到旋转矩阵和平移矩阵，达到精配准的效果。经实验证明，该方法可应用于点云的配准过程。与传统配准算法相比，收敛稳定，速度快，具有很好的实用价值。