基于FPFH特征的点云配准技术

陈学伟++万韬阮++王祖全

摘要：点云配准是三维物体或场景模型重建的关键技术。针对传统的ICP算法的收敛速度较慢，且在两点云集初始位置较大时易陷入局部最优解的问题，该文提出了一种改进的点云配准算法。该算法首先计算点云的FPFH特征描述子，然后对点云的特征进行匹配，实现两片点云的初始变换，使两点云集有相对较好的初始位姿。在经典ICP基础上使用k-d tree（k-Dimension tree）近邻搜索加速对应点对的查找，并利用方向向量阈值去除错误点对，实验证明该算法具有相对较好的配准精度和收敛速度，提高了配准的效率。

关键词： 点云配准；ICP算法；FPFH；方向向量阈值

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）04-0207-03

The Point Cloud of Registration Technology Based on FPFH Feature

CHEN Xue-wei，WAN Tao-ruan，WANG Zu-quan

（Xi'an University of Electronic and Information Engineering，Xi'an 710048， China）

Abstract：The registration of Point cloud is the key technology in the of 3 d object or scene model reconstruction. As for the low convergence of classical ICP algorithm and the convergence to the global optimum not be guaranteed，a kind of improved ICP algorithm of point cloud registration is put forward. This algorithm firstly calculates the FPFH point cloud character description， and then to match the characteristics of point cloud， the realization of two pieces of the initial point cloud transform， make two gathered have relatively good initial position.Then it use the k-d tree （k-Dimension tree）based on classic ICP to accelerate the search speed of the corresponding point ， and use the direction vector to remove the error corresponding point to improve the efficiency of registration .

Key words：point cloud registration；ICP algorithm；FPFH；Direction vector threshold

三維重建是计算机视觉领域研究的一个重要研究方向，在虚拟现实、文物保护、逆向工程、人机交互等领域都有广泛的应用。在数据采集的过程中，由于受到环境和设备本身的限制，需要从多个角度去采集某一模型表面的数据。为了得到完整的三维数据模型，我们可以利用光学三维测量法[1-2]从不同视角采集点云数据并对采集的数据进行拼接，配准的精度会直接影响到后期模型重建的精度。

由Besl和McKay[3-4]提出的经典的ICP算法是目前应用最广泛的点云配准算法，它通过不断寻找目标点云和源点云之间对应点集和计算对应点集之间的最优刚体变换矩阵，寻找两点云之间的最优匹配。但传统的ICP算法[5]收敛速度较慢，且在点云数据集初始位置相差较大时，易陷入局部最优解。为了改善这一问题，本文提出一种改进的点云配准算法，该算法在初始配准过程中引入了点云的特征描述子FPFH[6-7]，通过匹配点云特征对两点云集进行初始配准，将所得到的变换矩阵[8]作为精配准阶段的初始估计，巧妙地解决了传统ICP算法在点云之间的初始位置偏差较大时易陷入局部最优解的问题。在精配准中，在传统ICP算法的基础上使用 k-d tree近邻搜索法[9]提高对应点对的查找速度，并利用方向向量阈值去除点云中错误的对应点对，提高了算法的鲁棒性。

1算法介绍

本文提出了一种改进的点云配准算法，有效地改善了ICP算法收敛速度慢、鲁棒性差等问题。该算法首先计算点云的FPFH特征，然后通过匹配点云之间的特征实现两点云的刚体变换，从而完成初始配准，使两片点云集获得一个相对较好的初始位置[10]，然后利用k-d tree近邻搜索加速对应点对的查找，并使用点云方向向量阈值去除错误的点对，估计对应点对的刚体变换关系实现点云的精确配准。流程图如下：

2点云的初始配准

当点云的初始位置较大时，点云的精配准易陷入错误的方向，因此需要进行点云的初始配准，为精配准提供一个良好的初值。本文在初始配准是基于快速点特征直方图FPFH。其算法原理如下：

1）从待配准点云P中选取n个采样点，采样点之间的距离应满足大于预先设定最小距离阈值d，这样可以保证所采样的点具有不同的FPFH特征，

2）在目标点云Q中查找与点云P中采样点具有相似 FPFH特征的一个或多个点，从这些相似点中随机选取一个点作为点云P在目标点云Q中的一一对应点。

3）计算对应点之间刚体变换矩阵，然后通过求解对应点变换后的“距离误差和”函数，来判断当前配准变换的性能。此处的距离误差和函数多使用Huber罚函数表示，记为[i=1nH（li）]，其中：

上式中，[ml]为一预先给定值。[li]为第[i]组对应点变换后的距离差。上述配准的最终目的是在所有变换中找到一组最优的变换，使得误差函数的值最小，此时的变换即为最终的配准变换矩阵[11]，进一步可得到配准结果。

2.1 快速点特征直方图（FPFH）

FPFH 是利用已估计出的点云法线特征，计算出改点与其k个领域点的空间差异，它实际上是改进的PFH（point features histograms）快速简化模型。点特征直方图（PFH）描述样本的几何特征的方式是估算点云法向量之间的相互作用。PFH的计算方法如图2。

[pq]为待计算PFH特征的点，确定一参考半径内（图中虚线圆中）的k个邻域点，计算k邻域内的所有点两两之间的欧式距离、法线的角度偏差。k个邻域点的计算复杂度为[O（k2）]。本文提出了降低计算的复杂度FPFH快速算法，该特征描述子的计算复杂度为[O（nk）]，同时保证了PFH的大部分特征。

FPFH特征描述子的计算过程如下：

1）对于每个查询点[pq]，计算出该待求点与其所有邻域点之间的相对关系，记作[SPFH（pq）]；

2）重新确定每个点k邻域，并通过SPFH特征， 来估计FPFH特征，如下式所示：

[FPFH（pq）=SPFH（pq）+1ki=1kwi?SPFH（pi）] （2）

其中，[wi]为第i个邻域点 SPFH 特征的加权值。[1wi]代表[pq]与其第i个邻域点的距离值，用于表示点对（[pq]，[pi]）的关系.

FPFH 的整个计算过程可用图3表示：

3点云的精确配准

经过粗配准后两片点云集具有较好的初始位姿，但两点云之间仍存在偏差，配准的精度也达不到实际的需要，因此还需要进行精配准。在精配准过程中，本文对传统ICP算法进行了优化，使用k-d tree近邻搜索法加速对应点对的查询，同时利用方向向量阈值去除错误点对，提高每次对应点对集之间变换矩阵的估计质量，提高配准的效率。

方向向量阈值：

在对应点对的查询过程中不可避免地会引入噪声点对，而噪声点对的引入会影响最后的配准结果。为了缩小这种影响，本文采用方向向量阈值法剔除引入的噪声点对。计算点云表面的每个点的法向量以及对应点对之间的法向量夹角。如果对应点对之间的法向量夹角小于预先设定的阈值 t，就认为是正确的点对。反之，则认为是错误点对，将之从对应点集中剔除，避免迭代朝着一个错误的方向进行，提高配准效率。

4实验结果与分析

为了验证本文算法的有效性，本文采用了斯坦福大学提供的开放数据源bunny和数据规模较大，曲面复杂度较高的Happy Buddha作为试验对比数据，bunny点云有40000左右个点。Happy Buddha数据点要稍大于bunny，约为75000个。

实验平台为：win8系统，CPU主频为2.6Ghz，内存8G，Vistual C++编程，进行了两组数据的配准试验，实验结果如下。

（a）配准前的Happy Buddha （b） 初始配准后的Happy Buddha

（c） 本文算法配准后的Happy Buddha

由上图可知，图（b）可知此时两片点云数据已大致重合，但是依然存在一定的偏差，此时两片点云配准误差分别为2.286e-5、3.307e-5，而工程上要求的标准是不大于e-5，因此还需要进行精确配准。

图（c）本文算法精配准后的点云数据，从图可见，两帧点云中兔子的各个部位均得到了较好的配准。由表1可知两组数据的精度分别为4.712e-6、6.448e-6，相比初始配准有了较大的改善。

[点云名称＼& 传统ICP算法＼& 本文配准算法＼& 点的个数＼& 配准时间（s）＼&配准误差（m）＼&配准时间（s）＼&配准误差（m）＼&Bunny＼&123＼& 4.045e-5＼& 66＼& 4.712e-6＼&40000个左右＼&Happy Buddha＼&147＼&5.746e-5＼& 84＼&6.448e-6＼&75000个左右＼&]

由表2分析可知，本文算法比传统ICP算法有相对较好的配准精度和收敛速度。当数据量较大时，点云配准误差会有所增大，收敛速度有所变缓，但依然能够满足实际的需要

5结束语

本文提出一种基于特征点描述子FPFH点云配准算法，该算法首先利用SAC-IA算法实现点云的初始刚体变换，使两片点云具有一个较好的初始位置，避免算法陷入局部最优解的问题。然后在经典ICP基础上提出k-d tree近邻搜索方法加速对应点对的查找，并利用方向向量阈值去除错误点对，提高算法的效率。实验表明，该算法的配准精度和收敛速度在一定程度上都有所提高，具有一定的实际应用价值。

参考文献 ：

[1] 呂江昭，达飞鹏，郑东亮. 基于 Sierra Lite 抖动算法的散焦投影光栅测量[J]. 光学学报，2014，34（3）：0312004.

[2]安东，盖绍彦，达飞鹏. 一种新的基于条纹投影的三维轮廓测量系统模型[J].

光学学报，2014，34（5）：0512004.

[3] Best PJ，McKay HD.A method for registration of 3-D shapes.IEEE Transactions on Pattern Analysis and Machine Intelligence 1992： 14（2）： 239-56.

[4] Besl P J，Mckay N D.A method for registration of 3-dshapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14（2）： 239-256.

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

[6] 陆军，彭仲涛，董东来，等.点云FPFH 特征提取优化配准算法[J].新型工业化，2014，4（7）：75-81.

[7]Radu Bogdan Rusu ，Nico Blodow，Michal Beetz.Fast Point Feature Histograms （FPFH） for 3D Registration [A].2009 IEEE International Conference On Robotics and Automation [C].Japan. 2009，3212-3217.

[8] 宋林霞. 三维点云配准方法的研究[D].济南大学，2013.

[9] 戴静兰，陈志扬，叶修梓.ICP 算法在点云配准中的应用[J].中国图象图形学报，2007，12（3）：517-521.

[10] 朱延娟，周来水. 散乱点云数据配准算法. 计算机辅助设计与图形学学报，2006，18（4）： 475-481.

[11] 涂志强，张珂，杨成龙，等.三维模型重建中点云ICP拼接算法的改进 [J].焊接学报，2013，34（1）：97-100.