赵书芳

（西安工程大学电子信息学院，西安710600）

1 引 言

点云配准是指经由一定的算法或者统计学规律，通过计算机求解两块点云之间的错位，并由此计算出最佳转换矩阵，实现将两片点集云自动配准的过程。其技术是通过在源点云模型和目标点云模型之间构造一个三维空间变换，使源点云模型在此变换作用下能够最大限度地和目标点云模型重合。点云配准问题实质上是求解坐标变换矩阵和平移向量参数，使得两片三维点云的数据经坐标变换后的距离最小，直至实现两点云的配准。

目前最为经典和被普遍使用的点云配准算法是由Besl 和McKay 等人提出的迭代最近点（Iterative Closest Point， ICP）算法[1]。该算法虽然配准精度高，但存在计算效率低和初始位置要求高等缺点，对于数据量大的点云配准速度较慢，容易陷入局部极值的问题。因此许多学者对ICP 的改进算法进行了研究。赵夫群等人提出了基于文物点云模型的优化配准算法[2]，针对带有噪声的文物点云模型，采用一种由粗到细的方法来实现其断裂面的精确配准。杨军提出了一种基于自适应最优阈值的ICP 算法[3]，实现了整体与部分的3D 模型间的配准。钟莹以经典ICP算法为基础，根据主成分分析（Principal Component Analysis， PCA）算法[4]进行粗略配准，首先实现了两片大致重合的点云数据的快速获得，并在随后通过阈值改进的ICP 算法进行点云数据的精确配准。詹曙提出使用稀疏迭代最近点（SICP）来进行深度图的配准[5]，通过使用稀疏诱导准则去重新书写配准优化公式，从而提高配准的精度。张开兴提出了一种以三维模型为基础的数据点配准方法[6]，利用扫描数据生成三角网格模型， 并应用单纯形优化算法生成三维模型的最小包围盒， 然后通过坐标变换实现CAD 模型与三角网格模型上数据点的粗配准， 最后通过ICP 算法实现精配准。张志林使用Kinect v2获取包含物体所在场景的点云， 利用SAC-IA 算法对相邻两片点云进行粗配准，并将两两配准的ICP算法扩展到多片点云，算法策略配准精度高且适用性好[7]。

以上诸算法在点云配准的速度和精度等方面都有不同程度的提高，但应用在三维人体模型和服装模型的配准效果不佳，配准精度不高。为解决这一问题，在此提出一种基于ICP 算法的改进点云配准算法。此算法在初始配准时使用SAC-IA 算法，对两片点云集进行初始配准，将初始配准后得到的位姿作为ICP 配准算法的初始位姿，来避免ICP 算法在点云配准时因为初始位姿偏差过大时导致配准结果容易陷入局部极值的情况。

2 配准算法概述

一般情况下点云配准算法的实现可分为初始配准和精确配准。点云配准就是一片点云数据与另一片点云数据根据坐标变换矩阵进行整体分析并配准的过程[8]，其实质是求解坐标旋转矩阵和平移向量，使得在不同坐标系下测得的两片点云的三维数据经过坐标变换后的距离最小。

该算法首先对点云数据进行VoxelGrid 滤波处理，然后进行快速点特征直方图（Fast Point Feature Histogram， FPFH）特征提取，之后，再利用采样一致性初始配准算法（SAC-IA， Sample Consensus Initial Aligment）得到两片点云之间的对应关系，从而完成初始配准，使两片点云集获得一个相对较好的初始位姿[9]。最后，运用ICP 算法将点云的初始配准结果进行第二次精确配准，从而完成两片点云的精确配准，达到优化配准结果的目的。点云配准流程图如图1 所示。

图1 点云配准流程图

3 VoxelGrid 滤波

在点云处理时一般将滤波处理作为预处理的第一步，滤波处理的效果决定着后续的点云处理步骤的好坏，影响很大。为了更好完成配准、特征提取、曲面重建、可视化等后续步骤，必须在滤波处理时将离群点、空洞、噪声点等按照后续点云处理的需求进行定制的滤波预处理。

VoxelGrid（体素网格）滤波法具有很好的滤波效果。体素网格的概念类似于像素，使用AABB 包围盒将点云数据体素化。一般体素越密集的地方信息越多。体素网格可以去除噪音点和离群点。另一方面如果使用高分辨率相机等设备采集点云数据，那么得到点云数据通常会较为密集。过多的点云数量会对后续点云配准等工作带来困难。使用体素滤波器不仅可以达到向下采样的目的，同时也保持了点云数据本身的几何结构。

在此使用VoxelGrid 滤波[10]方法实现下采样，在减少了点云数据的同时也保持了点云的原始形状特征，适用于点云配准、曲面重建等三维点云算法中，以提高点云算法的运算速度。PCL 中的滤波函数VoxelGrid 类经由输入的点云数据创建了一种三维体素栅格（一般将体素栅格当做空间的微小三维立方体的集合），然后在每一个体素格内，体素中的其他点用其重心点来表示，因此经过体素格滤波后的点云数据，其所有点都可以用一个重心点来代替表示。通过上述下采样的方法达到点云滤波的效果，也可同时减少点云数据的处理量。将其作为点云配准和曲面重建等实验的预处理，能够在很大程度上提高点云处理的速度。

4 点特征直方图描述子

采样一致性初始配准（SAC-IA，Sample Consensus Initial Alignment）算法依赖特征直方图[11]，因此一般要先将点云的快速特征点直方图描述子（FPFH， Fast Point Feature Histogram）计算出来。FPFH 是根据已估计出的点云法线的特征值，计算出该点和它k 个邻域点之间的空间差异，其本质上是点特征直方图（PFH）的快速简化模型[12]。FPFH 很大程度上减少了计算复杂度，提高了计算效率，并且保留了PFH 的大部分特征和功能。

新算法利用了提高计算效率的FPFH 快速算法，同时保留了PFH 的主要特性。FPFH 特征描述子的求解方法如下：

1) 针对某个查询点Pr，求取它和邻域点之间的矩阵关系，将此计算关系称为简化的点特征直方图（SPFH，Simple Point Feature Histograms），记作S(Pr)；

2) 再次设定每个点k 邻域，然后通过邻域点计算出的SPFH 的值来求解点Pr的FPFH 特征值，记作H(Pr)为：

上式wl为第l 个邻域点SPFH 特征的权重，表示查询点Pr和它的邻近点Pm之间的距离，用于评定一组点对(Pr，Pm)的关系。FPFH 计算原理如图2 所示。

图2 FPFH 计算原理图

5 点云配准方法

5.1 初始配准

为了避免使点云配准陷入局部最优解从而导致配准失败，在精配准之前进行了点云的初始配准。在初始配准时采用的是SAC-IA 算法，其算法步骤如下所述：

1) 从待配准点云M 中选取k 个采样点，为了使每个采样点的FPFH 特征都不一样，每两个采样点之间的距离应该大于设置的最小距离阈值dmin。

2) 寻找目标点云N 中和待配准点云M 中的采样点具有相似FPFH 特征的所有的点，在这些相似点中任意选取一些点作为点云M 在目标点云N 中的相互对应点。

3) 求解对应点之间的刚体变换矩阵，然后再利用计算对应点云的度量误差来评价变换矩阵的质量。此处的距离误差多使用Huber 函数表示：

式中ur为预设值，ri为第i 组对应点变换之后的距离差。重复以上三个步骤直至取得最佳度量误差结果，即得到误差函数的最小值，此时刚体变换矩阵就是最优的，也是最终的点云配准变换矩阵[11]，通过此矩阵即可计算出点云配准结果。

5.2 IPC 算法

通过SAC-IA 算法得到的刚体变换矩阵使得两个点云数据大体上重合，得到一个较好的精确配准的初始位姿，还需在此基础上再做一次精确配准。ICP 算法作为经典的精确配准算法，实际上是基于最小二乘法的最优配准方法。该算法是通过重复选择满足对应关系的点对，计算出最优刚体变换，直到达到配准的收敛精度要求。ICP 算法的主要思想就是找到旋转矩阵和平移参数，将两个不同坐标系下的点云，以其中一个点云坐标系为全局坐标系，另一个点云经过旋转和平移后两组点云对应部分完全重叠。在每次进行ICP 算法时，一般先通过给定的规则找出对应点集C 与D，此处有：C∈⊂A， D∈⊂B，对应点对的个数设置为n。最后根据最小二乘法迭代计算出坐标变换矩阵，包括旋转矩阵Z 和平移向量T，使误差函数式达到最小，其式如下：

此式取得最小值时即达到满意的误差要求。

ICP 算法分为4 个主要步骤：

①针对目标点云中的每个点，求解源点云中与其匹配的最近点;

②计算出使上述对应点对令函数式(3)值最小的刚体变换，然后求取旋转矩阵和平移向量；

③使用获得的旋转矩阵和平移向量来配准原始点云和目标点云；

④重复上述三个步骤，直到满足终止迭代的条件（迭代次数或误差小于阈值）。此处的误差最小，可以是相邻两次均方根差的绝对值小于某一限差。

6 实验结果与分析

实验中的人体模型和服装模型来自Poser 6.0。Poser 是MetaCreation 公司开发的一款优秀的人体造型和动画制作软件，为用户提供了男性模型、女性模型等，且存储了很多的身体姿势、动作以及逼真的面部表情的三维人体模型和服装模型[13]。此外Poser还有较强的交互能力，具备了3ds、obj 等文件格式的接口，能和输出为上述文件格式的软件程序进行模型信息交互。在实验中，把Poser 6.0 中的三维模型数据导出为obj 格式的数据文件，然后利用程序将obj 格式的人体模型转化为pcd 的点云格式，最后再进行三维人体模型与服装的点云配准。

实验使用C++编程和PCL 开源数据库，一共进行了两组三维人体模型和服装模型数据的配准。在配准之前，在Maya 里对人体模型和服装模型的尺寸进行了调整，将服装变形到适合人体模型的尺寸大小。实验结果如图3 和图4 所示。实验使用的改进配准算法与传统ICP 算法配准所消耗的时间对比如表1 所示。

图3 男装点云配准结果比较

图4 女装点云配准结果比较

表1 改进算法与传统ICP 算法处理速度对比

图3(b)和图4(b)为ICP 算法配准后的数据。由图中可以看出此时两片点云数据没有完全重合。图3(c)和图4(c)为实验算法配准后的效果图，两片点云数据中的各个部位都得到了较好的融合，实现了人体模型和服装模型的配准。

7 结 束 语

针对ICP 算法收敛速度慢，容易陷入局部极值等问题，基于SAC-IA 对ICP 点云配准算法进行了改进。经过实验验证，新改进的算法适用于人体模型和服装模型等刚体的配准，当两点云重叠区域较少时依然有较高的配准精度。与传统ICP 算法相比，改进算法点云配准的精度和收敛速度都有了明显的改善，具有很好的实用价值。