基于特征的点云配准

写在前面

点云配准的方法有很多，比如基于特征的方法、基于概率模型的方法、基于深度学习的方法等，基于特征的方法是较早提出的一种方法。

基于特征的点云配准方法常常作为点云的粗配准流程，得到粗略的点云变换后再使用ICP等算法求解更精确变换。值得注意的是：粗略和精确这两个词的定义都是相对的，是对应具体的使用场景的，如果一些场景精度要求不是很高，有时使用粗配准即能达到精度要求。

几何特征量可以分为全局特征和局部特征，全局特征是对整个三维点云的几何属性，进行编码形成一个特征集合，局部特征则只针对特征点的局部邻域的信息进行编码。在粗配准领域，使用基于特征的配准方法比使用基于 RANSAC 的配准方法，无论是在时间效率和精度方面，都更胜一筹；而且基于局部特征的配准方法比基于全局特征的配准方法在面对杂乱和遮挡的三维点云配准时，更具鲁棒性。(熊风光，2018)

采用的是“先粗后精”的配准思路。研究的重点是局部特征的相关技术，包括特征点的检测、特征点描述与特征匹配、误匹配对剔除，最后将这些技术应用到三维点云配准中，结合精细配准，实现三维点云自动化配准。

基于特征的点云配准

未包含误匹配删除的基于特征的点云配准流程：

特征点云配准流程

特征点检测与降采样

在早期对点云配准的研究中，通常对点云数据预先计算具有区分力和描述力的关键点，再进一步进行处理。但是最近有研究表明，现有关键点检测方法在实际的应用中不仅较为费时，且效果较差。而均匀采样和随机采样方法被证明是一种有效的方法，可以用于取代关键点检测算法。（李佳骏，2021）

实操试下来，在实时性要求高一点的应用里，特征检测算法确实是比较耗时的，现在也有一些开源的基于特征的配准算法使用降采样代替特征检测（open3d global registration）。

特征描述

这里的特征描述讲得是局部的特征描述子。比较熟知的有(点特征直方图)PFH&FPFH、3DSC&USC等，主要以PFH和FPFH为例介绍。最主要的是要明白算法的原理和输出是什么。输出的是一个n维的向量。

PFH&FPFH

介绍的文章和链接其实也很多，给出一些链接然后简要介绍。

知乎链接;PCL源链接

描述的几个特征为下面几个值，d在最后时限的时候没怎么管，主要看前面3个角度。

image-20220210134934978

问题来了，是如何把这几个特征值的变为一个n维的向量的呢？规则是：（图源: PCL作者Rusu Dissertation： Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments. 2009.）

image-20220210140743057

即将每个角度均匀划分为5个区间，那么3个角度将产生125个区间，并且每一个bin都将完全对应一个唯一的代表三个角度特征的值（即为图中所述fully correlated）。由此可以生成一个直方图，横轴是0-125，纵轴则是统计在该点的邻域内有多少个点出现在了对应区间。于是就产生了一个125维的向量，每一维代表的是——特征位于该区间内的点的数量。（直方图如下所示，可以发现，这样做很多地方都是0值）

img

FPFH做出了改进，公式上有少许改进不详细说，主要是将特征抽象为特征向量时有改变：不再是b^d^个区间，而是b*d个区间，相当于是单独给每个特征做一个直方图，然后在水平方向上把直方图拼起来。PCL给出的实现不是分的5个区间，分的11个区间（区间多，分辨率高），所以总共33维。

image-20220210150814873

3DSC&USC

描述的局部特征不同，但是抽象特征的思路是一样的。

统计每个网格内的点数加权值即为 3DSC 描述子。描述子是高维向量，特征向量长度为总的格子数。

image-20220210152014344

小结

所以，局部特征的描述有很多的切入点，有描述角度的，有描述点分布的，但是最终都把这些特征抽象成了一个特征向量或者特征矩阵（也有用矩阵的，匹配的时候比较矩阵的相似度），方便后续进行对应的特征匹配。

特征匹配

目的是研究如何对两个特征描述子集合中的特征描述子进行匹配，建立特征描述子间的对应关系，从而确立特征点之间的对应关系。确定了匹配关系，就可以使用SVD求解空间变换。

注意：特征匹配不是匹配的特征点的坐标值，而是匹配的特征点的特征描述子，通过描述子的匹配，得出对应的点对。

所以很多文献在特征匹配时都会说，计算两个特征值之间的距离，这里的距离不是指的特征点三维坐标的距离，而是代表高维特征向量之间的高维距离。

在机器学习中，常用的距离公式有闵可夫斯基距离[92]、欧几里得距离[93]、曼哈顿距离[94]、切比雪夫距离[95]、马氏距离[96]、余弦相似度[97]、汉明距离[98]等。(熊风光，博，2018) 这里的距离应该直接用的欧式距离。

匹配的方法也不多介绍了，博士论文里有说，要么小于距离阈值的都配对上，要么只配对一个距离最小的。

误匹配剔除

上一部特征匹配中肯定存在一部分误匹配，这些结果将会影响计算的空间变换的准确性，可以视作是噪声，需要被剔除。

主要介绍基于RANSAC和基于k-means聚类的方法。

RANSAC

随机采样一致性算法，太熟悉了，是一种有效的对抗噪声的方法。每次随机采用m组匹配对，计算出变换关系，统计满足该变换关系的特征点匹配对的数量；重复该过程，直到迭代上限或是满足设定要求。现在open3d给出的基于局部特征的点云配准就是使用的RANSAC。open3d 全局粗配准

k-means聚类

聚类方法认为当模型点云与场景点云正确匹配时，得到的大部分变换关系应聚集在真实矩阵附近。进而对这些变换关系进行聚类形成 k个聚类，并将包括元素最多的聚类作为正确的聚类结果，其中的特征匹配对为正确的匹配对，其它聚类中的匹配对则认为是错误的匹配对而被剔除掉。

对应点求解空间变换

也是熟悉的内容了，直接使用SVD是较为流行的一种方法。

FINDING OPTIMAL ROTATION AND TRANSLATION BETWEEN CORRESPONDING 3D POINTS

使用ICP进行精配准

常规步骤，使用ICP达到精确解。

参考文献

  1. 熊风光. 三维点云配准技术研究 [D]; 中北大学, 2018.

  2. 李佳骏. 基于局部特征的图像与点云配准研究 [D]; 大连理工大学, 2021.

  3. 知乎链接：https://zhuanlan.zhihu.com/p/192343758

  4. PCL源链接：https://pcl.readthedocs.io/projects/tutorials/en/latest/pfh_estimation.html?highlight=PFH

  5. Rusu Dissertation： Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments. 2009.

  6. open3d 全局粗配准：http://www.open3d.org/docs/release/tutorial/pipelines/global_registration.html

  7. 对应点求解空间变化：http://nghiaho.com/?page_id=671