基于点特征直方图的点云拼接文献综述

1. 文献综述（或调研报告）：

20世纪80年代，开始有部分研究者将目光从二维图像的配准转向到三位图像的配准当中来，最初的三维配准采用了松弛迭代法和模糊松弛迭代法。

1992年，Besl和Mckay提出的最近点迭代（Iterative Closest Point，简称ICP）算法，奠定了图像配准的理论基础。文章采用四元数加上一个偏移向量来表达旋转平移变换，在已经拥有一个可靠初值的情况下，得到变换后点集与目标点集中欧式距离最小的点对作为对应点对，并得到新的旋转与平移参数，反复迭代，直到达到预设的迭代次数或达到迭代终止条件。但此算法需要一个已知可靠的旋转平移初值，因此在采用此算法前，需要进行初步配准。同时，由于源点集与目标点集的点的数目往往很大，采用原始的ICP算法的耗费极大。

点云拼接算法的研究现状：

Greenspan^【3】等采用基于KD-tree最近点搜索方法来提高对应最近点的搜索速度，该方法虽然时间效率上优于使用标准的 KD-tree 进行迭代搜索的方法，但该方法还是需要先建立点云的 KD 树结构，这额外增加的时间导致该方法加速效果依然欠佳。Gelfand^【4】等人为了提高 ICP 算法的稳定性，提出限制匹配点选择的方法，这种方法关键在于对输入网格的特征采样，这些特征采样使算法达到最佳收敛。Richard^【5】等人在进行初次 ICP 算法后，将点云模型表面细分为拟线性表面，轮廓细分为大量的拟线性曲线，再用 ICP 算法对各部分分别进行处理，采用分治的思想以达到更好的拼接效果，为加快准确找到对应点匹配。Radu^【6】等利用点云模型表面的特征来查找对应点集。葛宝臻^【7】等采用曲率图作为点云数据的特征描述，先采用曲率图特征粗配准，再用经典 ICP 算法精确配准的两步法，有效降低了 ICP 的迭代次数，且获得了满意的点云配准效果。张旭东^【8】等针对深度相机获取的三维点云，利用相机强度图像的梯度值与点云局部3D空间分解的KNN算法来寻找最邻近点作为匹配点，提高了配准精度。孙军华^【9】等采用一种分层块状全局搜索到邻近局部搜索的改进 ICP 算法，提高了 ICP 的速度及消除了点云缺失对配准的影响。涂志强^【10】等提出一种利用点云的曲率、法矢量等几何信息，计算出初次拼接换，并用几何哈希方法筛选出最优的变换，完成初次的拼接，再用ICP方法配准。

目前ICP算法是在配准三维点集领域中广泛使用的方法，并且为了提高时间效率或者在不同场合中使用，新的改进 ICP 算法也不断出现。

王永波^【11】等提出了以线状特征作为 LiDAR 点云配准的基元，利用四元数法来表达旋转矩阵，进而形成线状特征约束下基于四元数描述的 LiDAR 点云配准方法，改善了配准算法中方程线性化过程对配准精度的影响。 另外，特征描述子是对曲面局部共性的描述，利用特征描述子将曲面匹配问题转换为特征匹配的问题，从而提高匹配效率。选择特征描述子时需确保特征描述子具备旋转、平移、缩放不变性。将图像处理中的不变特征描述与分析方法引入三维曲面的处理中，加速 ICP 算法的点云曲面对应点搜索与匹配。Sharp^【12】等提出一种基于曲面不变特征 ICP 算法。此算法将点位置距离和形状特征距离相结合来完成点对应，这种方法可以权衡特征误差和距离误差，达到更好的点对应正确率，并且使用不变特征量能降低陷入局部极小值的可能性，是一种有效的配准方案 。

1. 方案（设计方案、或研究方案、研制方案）论证：

由于ICP算法对初始位置有一定要求，否则易陷入局部最优，所以当前的匹配方案大都采取先初始后精确的匹配步骤。本课题步骤为：关键点提取、特征描述、局部特征匹配、误匹配去除、获取旋转平移矩阵、ICP算法精细拼接。

4.1 采用ISS^【13】进行关键点提取

ISS算法利用协方差矩阵建立模型，通过奇异值分解得到形容改点特征程度的特征值。特征值的大小实际上是椭球轴的长度，椭球的形态则是对邻近点分布状态的抽象总结。如果临近点沿某个方向分布致密则该方向会作为椭球的第一主方向，稀疏的方向则是第二主方向，法线方向当然是极度稀疏（只有一层），那么则作为第三主方向。如果某个点恰好处于角点，则第一主特征值，第二主特征值，第三主特征值大小相差不会太大。如果点云沿着某方向致密，而垂直方向系数则有可能是边界。

（1）对点云中每个点，搜索半径r范围内的所有点，计算出权值：

（2）计算协方差矩阵:

（3）计算出上述协方差矩阵的特征值，按照从小到大依次为、

（4）设置两个阈值、，满足下列两个条件的点即为关键点：

4.2 利用点特征直方图（PFH）对点云中的关键点进行描述

PFH计算方式通过查询某点与其领域点之间的差异，形成一个多维的直方图来描述领域的几何特征。PFH表示法是基于点与其k领域之间的关系以及他们的法线间的关系。换句话说，它考虑发现之间的相互作用来描述点云的几何特征。

（1）如图，对于点集中的每个点，以为原点，半径为gamma;的球域内的点作为的邻近点，标为;

（2）为了计算两点 和以及他们的法线、之间的偏差，在其中一个点上定义一个局部坐标系

使用图中的uvw坐标系，选取如下特征：

其中d表示和之间的欧式距离，计算k领域内每一对点的()四组值，作为特征向量。

最后建立特征直方图，即首先把每个特征值范围划分成b个子区间，每个区间赋予一个数值，对于一个特征向量，确定每个特征值对应的区间，将数值乘以相应权重之后累加作为该点的特征量。这样确定点集所有点的特征量，以统计方式放进直方图中。

4.3关键点的匹配与误匹配去除

4.3.1 特征匹配

要将2个特征匹配起来，就是计算这2个特征的距离，若距离足够小，就判定这2个特征匹配，为一对特征点对。具体流程为：

以一个特征点集A为基准，选取某一点，计算这一点到另一个特征点集B中所有点的特征空间上的欧氏距离，选取最小距离的一个特征点作为匹配对，如此重复计算点集A中所有点在点集B中的匹配对，就得到了2个特征点集之间的对应关系。

4.3.2 错误剔除

采用RANSAC算法剔除错误匹配。首先选取一个特征点集为源，另外一个特征点集为目标，要完成从源到目标的变换。计算旋转平移矩阵至少需要3对点，首先从匹配好的匹配对中随机找出3对点，计算其旋转平移矩阵，然后该矩阵作用到源特征点集上，计算出此时所有匹配对的空间距离，距离小于设定阈值的判定为inliers，重复上述过程，每次迭代若inliers比上次多，则该次变换矩阵为最优。迭代结束时，最优的变换矩阵即为两个特征点集的最优变换矩阵，inliers中包含的事正确的配对，而inliers不包含的点即为错误点对，将其剔除。

4.4 求取旋转平移矩阵实现点云初始拼接

采用奇异值分解的办法求解旋转矩阵和平移矩阵

令目标函数为：

若满足最小二乘解为和，这样和有相同的质?

其中

使：

则目标函数可写成：

可分解为

为了使J最小，等价为使最大，其中H为3*3矩阵，定义为：

H经SVD分解得

令,则，可见XH是对称且正定的，对任意的3*3正交矩阵B，有成立，故X使最大，若，则X即为所求旋转矩阵R。

4.5 基于ICP的精确配准

（1）搜索最近点

以作为源点集，Q为目标点集，为第i次迭代的结果，搜索 中所有点到Q中的最近点作为匹配，采用欧式距离来度量。

（2）计算变换参数

采用奇异值分解计算出一组变换参数使得以下距离函数最小：

其中为第i次迭代的旋转矩阵，为第i次迭代的平移矩阵，

（3）将变换作用到源点云

将变换作用到得到，。

（4）检验迭代终止条件

设定阈值，当时，迭代结束，否则返回（1）继续迭代。

本算法主要消耗在计算对应点集上，拟对此优化以加快运算速度。

参考文献：

1. Rusu R B, Blodow N, Marton Z C, et al. Aligning point cloud views using persistent feature histograms[C]// Ieee/rsj International Conference on Intelligent Robots and Systems. IEEE, 2013:3384-3391.
2. PJ Besl，H D McKay.A method for registration of 3-D shapes [J].IEEE Transactions on Patern Analysis and Machine Inteligence，1992，14(2):239-256.

3. Greenspan M，Yurick M. Approximate kd tree search for efficient ICP[C]. Proceedings of the Fourth International Conference on 3D Digital Imaging and Modeling，2003: 442-448.

4. Gelfand N，Ikemoto L，Rusinkiewicz S，et al. Geometrically stable sampling for the ICP algorithm[C]. Proceedings of Fourth Interna- tional Conference on 3-D Digital Imaging and Modeling，Banff， Canada: IEEE Computer Society，2003: 260-267.
5. Bearee R，Dieulot J Y，Rabate P. An innovative subdivision-ICP registration method for tool-path correction applied to deformed air- craft parts matchining[J]. International Journal of Advanced Manu- facturing Technology，2011，53( 5-8) : 463-471.
6. Radu B R. Semantic 3D object maps for everyday manipulation in human living environ ments [D]. Munich: Technical University Munich ，2010 .
7. Ge Bao-zhen，Peng Bo，Tian Qing-guo. Registration of three-dimen- sional point-cloud data based on curvature map[J]. Journal of Tian- jin University( Science and Technology) ，2013，46( 2) : 174-180.
8. Zhang Xu-dong，Wu Guo-song，Hu Liang-mei，et al. Adjacent scat- ter point cloud registration technology research based on three-di- mensional camera of time of flight[J]. Journal of Mechanical Engi- neering，2013，49( 12) : 8-16.
9. Sun Jun-hua，Xie Ping，Liu Zhen，et al. Automatic 3D point cloud registration based on hierachical block global search[J]. Optical and Precision Engineering，2013，21( 1) : 174-180.
10. Tu Zhi-qiang，Zhang Ke，Yang Cheng-long，et al. Improved ICP registration in 3D model reconstruction[J]. Transactions of the China Welding Institution，2013，34( 1) : 97-100. 

11. Wang Yong-bo，Yang Hua-chao，Liu Yan-hua，et al. Linear-feature- constrained registration of LiDAR point cloud via quaternion[J]. 
 Geomatics and Information Science of Wuhan University，2013，38 ( 9) : 1057-1062.
12. Sharp G C，Lee S W，Wehe D C. ICP registration using invariant features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24( 1) : 90-102.Han X F, Jin J S, Wang M J, et al. A review of algorithms for filtering the 3D point cloud[J]. Signal Processing Image Communication, 2017, 57:103-112.
13. Zhong, Y.: Intrinsic shape signatures: A shape descriptor for 3d object recognition. In: ICCV - WS: 3dRR (2009)
14. 李选富. 散乱点云自动配准技术研究[D]. 哈尔滨工业大学, 2010.
15. 戴静兰, 陈志杨, 叶修梓. ICP算法在点云配准中的应用[J]. 中国图象图形学报, 2007, 12(3):517-521.
16. 王勇, 唐靖, 饶勤菲,等. 一种新的散乱点云快速去噪算法[J]. 计算机应用与软件, 2015, 32(7):74-78.
17. Rusu R B, Blodow N, Beetz M. Fast point feature histograms (FPFH) for 3D registration[C]// IEEE International Conference on Robotics and Automation. IEEE Press, 2009:1848-1853.
18. 伍梦琦, 李中伟, 钟凯,等. 基于几何特征和图像特征的点云自适应拼接方法[J]. 光学学报, 2015, 35(2):229-236.
19. 陶海跻, 达飞鹏. 一种基于法向量的点云自动配准方法[J]. 中国激光, 2013(8):179-184.
20. 王新, 刘永山, 朱代春,等. 三维点云配准算法的研究[J]. 燕山大学学报, 2016, 40(6):524-531.
21. Besl, P.J, McKay, Neil D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 14(2):239-256.
22. 李世飞, 王平, 沈振康. 迭代最近点算法研究进展[J]. 信号处理, 2009, 25(10):1582-1588.
23. 刘修国，王红平，等.基于激光扫描技术的三维模型重建 [J ] . 激光与光电子学进展 ，2011，48 (8 ) : 081201
24. 董富强，达飞鹏，黄昊.基于S变换的改进窗口傅里叶三维测量法 [J].光学学报，2012，32(5):0512008.
25. 路银北，张蕾，普杰信，等.基于曲率的点云数据配准算法 [J].计算机应用，2007，27(1):2766-2769.
26. 朱延娟，周来水，张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学学报，2006，18(4):475-481.
27. 左超，鲁敏，谭志国，等.一种新的点云拼接算法[J].中国激光，2012，39(12):1214004.
28. 谭志国，鲁敏，郭裕兰，等.基于投影分布熵的多视点三维点云场景拼接方法[J].中国激光，2012，39(11):1114003.

29. 秦绪佳 ，徐菲，王建奇，郑红波，陈胜男基于法向量直方图特征描述的点云ICP拼接小型微型计算机系统 2016，310032

30. Zaman F, Wong Y P, Ng B Y. Density-Based Denoising of Point Cloud[M]// 9th International Conference on Robotic, Vision, Signal Processing and Power Applications. Springer Singapore, 2017.