SegMatch: Segment based place recognition in 3D point clouds

R. Dube, D. Dugas, E. Stumm, et al. SegMatch: Segment based place recognition in 3D point clouds. IEEE International Conference on Robotics and Automation, 5266-5272, 2017.

摘要

Dube等人首次提出基于分割的3D点云场景识别方法。与局部（基于关键点）和全局（基于全局描述子）的场景识别方法不同，基于分割的场景识别方法既考虑了局部特征，又包含了“类别“这种高维特征，并且不依赖于物体级别的完美分割方法，是一种折中的场景识别方案。具体地，首先将当前帧点云通过特定的聚类方法分割成若干块点云簇。接着，SegMatch从每一块点云簇中提取一个特征向量。特征向量提取混合了特征值和直方图两种方法，鲁棒性更强。接着匹配当前帧的点云簇集合和地图中的点云簇集合。具体做法是，提取当前帧点云簇在地图邻域范围内的点云簇集合，然后通过随机森林预测两两点云簇的相似度，最终得到一系列候选点云簇关联对。最终，利用RANSAC方法进行集合验证测试，寻找最少数量的几何一致性较强的点云簇关联对集合，并利用点云簇中心的相对位置关系估计相对位姿变换，从而完成场景识别任务。

1. 介绍

场景识别代表准确SLAM的关键任务之一。由于在没有全局位姿信息的前提下，执行状态估计时漂移不可避免，可靠的回环检测对于许多机器人平台来说是一项关键的能力。许多使用图片执行场景识别的成功策略在文献中被提出。但是，基于图片的场景识别可能变得不可靠当大光照变化或者大的视角变化发生时。基于激光雷达的定位，另一方面，不受外部光照的影响，并且由于它以非常好的分辨率捕捉了几何信息，不受视角变化影响。本文因此考虑3D激光扫描仪，由于其具有提供室外环境鲁棒定位的潜力。

当前3D激光数据中的场景识别策略主要基于关键点检测和匹配。在图片的场景识别执行过程中，Lowry等人[2]之初使用分割活着物体层次的描述子能够同时提供局部和全局特征方法的好处。物体或分割地图也在尺度和拓扑方面提供几个好处。与其他地图相比，这些地图能够更好地表示什么时候静态物体变成动态，并且更接近人类感知环境的方式。

虽然在物体级别工作是非常理想的，它也有两方面的假设。首先，我们能够得到完美的物体分割技术，其次，在环境中有实际的“物体”，在[4]的定义下。这些假设在一般情况下并不满足，由于不完美的分割，以及在常见的现实世界情形中没有可区分的物体。该工作因此介绍了SegMatch，一种基于分割的方法利用可描述的形状而不是基于关键点的特征，且不需要基于物体方法的较强假设。换句话说，我们通过匹配属于部分或者全部物体的分割或者更大结构的部分（窗户，弧，外墙）来识别地点。这种分割的例子可以在图1中看到，其数据在市区中收集。

图1. 提供的场景识别框架的图示。参考点云在下面展示（白色），局部点云在上面对齐。颜色被用于展示点云分割，分割匹配被用绿色线条展示。

我们的系统展示了一个模块设计。它首先提取和描述了来自3D点云的分割，将它们和已经访问过的地点的分割进行匹配，并使用几何验证步骤来提出地点识别候选。这个基于分割的技术的优势之一是它压缩点云到一组不同和可分辨的元素用于场景识别。我们展示了这个不仅减少了需要匹配的时间，而且减少了得到虚假匹配的可能性。

当它到达分割描述时，即使大量的3D点云描述子已经存在[5-7]，仍没有明显的证据表明它们之间的相对表现，例如泛化能力或者对于实例几何对称的鲁棒性。因此，我们选择一种机器学习方法来匹配大量基于分割的标准描述子。尽管如此，

由于提供框架的模块化性质，为了在3D分割，识别和描述上的提高可以被用于代替对应的流程中的成分。

据我们所知，这是首篇文章来提供一个实时算法来基于分割执行3D激光数据的回环检测和定位。更细节地，本文提供了如下贡献：

• SegMatch，一个基于分割的算法来执行3D点云的场景识别。
• 一个SegMatch的开源应用用于在线，实时回环检测和定位。
• 一个在现实世界应用的完整的算法表现评估。

本文结构如下：第2节提供了3D点云场景识别领域的相关工作。提出的算法然后再第3节中被描述，并在第4节中被评估。第5节最终通过一个小讨论进行总结。

2. 相关工作

从3D数据中检测回环在机器人定位中仍然是一个开放问题。该问题通过不同方法解决。我们已经分成了三种趋势：（i）基于局部特征的方法（ii）全局描述子（iii）基于平面或物体。

[3,8-11]中的工作提出从关键点中提取局部特征，并基于这些特征执行匹配。Bosse和Zlot[3]直接从点云中提取关键点，并使用3D Gestalt描述子描述。关键点然后对最近邻投票在一个投票矩阵中，其最终通过阈值法识别地点。一个类似方法在[11]中被使用。除了Gestalt描述子，大量替代局部特征描述子方法存在，其可以通过类似的框架被使用。包括快速点特征直方图（FPFH）[7]，其在后续会被应用到本工作中。替代地，Zhuang等人[8]变换局部扫描到方向-角图片并从图片中提取加速鲁棒特征（SURFs）。一种基于3D空间信息的策略被应用在匹配描述子之前对场景进行排序。一个类似的技术被Steder等人[9]采用，首先变换局部扫描到距离图片。局部描述子然后被提取并和数据库中的描述子比较，应用欧氏距离用于匹配关键点。该工作在[10]中扩展通过使用法向量对齐径向特征（NARF）描述子和词袋方法用于匹配。Zhang和Singh[12]能够使用范围数据实时估计里程计。回环检测被提及但是依赖离线算法。

使用局部点云用于场景识别的全局描述子也被提出[13-15]。Rohling等人[13]提出用点云高度的一维直方图描述每个局部点云，假设传感器与地面距离保持不变。该直方图然后使用Wasserstein尺度进行比较用于场景识别。Granstrom等人[14]使用旋转不变的特征，例如体素，名义范围和范围直方图来描述点云。对标量特征计算距离，对直方图特征计算交叉相关，同时一个AdaBoost分类器被训练用于匹配地点。最终ICP被用于计算点云间的相对位姿。在另一个方法中，Magnusson等人[15]分割点云为重叠的栅格，并计算每个栅格的形状性质（球形，线性和若干平面），并组合它们成一个表面形状直方图的矩阵。类似其他工作，该描述子被比较用于识别场景。

虽然局部关键点特征经常缺乏描述能力，全局描述子可能不具有不变性。因此其他工作也提出使用3D形状或者物体来进行场景识别任务。Fernandez-Moral等人[16]，例如，提出执行场景识别通过检测3D环境中的平面。该平面在图中被累积，一个解释树被用于匹配子图。一个最终的几何一致性检测在所有匹配子图的平面中被执行。该工作在[17]中被扩展，使用平面参数的协方差矩阵而不是平面中点的数量用于匹配。该策略只应用到较小的室内环境，并假设平面模型，这在非结构环境中不再保持。一个类似的，开创性的，室内环境中使用RBG-D相机进行基于物体的回环检测工作被Finman等人[18]提出。即使提出了有趣的想法，他们的工作只在小尺度环境中处理了少量分割物体。

我们因此致力于一种方法，不仅不依赖环境由简单几何实体，如平面或者丰富物体组成。它还允许更一般的，可扩展的解决方案。启发来自Douillard等人[19]和Nieto等人[20]，其提出不同的基于分割的SLAM技术。一种基于分割的用于对齐Velodyne扫描的技术在[19]中被提出，其中对称形状距离被用于比较和匹配在[21]中定义的分割。类似地，[20]提出了一种扩展卡尔曼滤波器解决方案，其使用分割作为路标，而不是点特征。

3. SegMatch算法

在本节，我们描述了我们用于3D点云的场景识别方法。提出的系统在图2中展示，并由四个不同模块组成：点云分割，特征提取，分割匹配和几何验证。模块化在设计过程中是一个驱动因素。在后续，我们为系统的每个模块提出一种实例应用，可以被简单地更改用于在不同环境中的操作。

图2. SegMatch的模块示意图，一个模块化的场景识别算法。目标地图可以从硬盘中载入（用于定位）或者在线计算（用于回环检测）。

A. 分割

SegMatch的第一个模块，分割点云为不同的元素用于匹配。对于每个在一个给定全局参考系中的到达点云  ，我们首先提取一个局部点云通过定义一个半径为  的圆柱近邻，以当前机器人的位置为中心。一个体素栅格然后被应用到源点云为了滤除提速中的噪声，其中没有足够的占据证据。滤除后的点云最终使用[22]中的“分类所有方法”被分割为一组点云簇  。该分割需要地面平面被提前剔除，其可以被达到通过基于竖直均值和方差聚类临近的体素[22]。一旦地面被剔除后，欧式聚类然后被用于生长分割。对于类别  ，中心  被计算为所有点的均值。

B. 特征提取

一旦我们已经分割了点云，我们对每个分割提取特征。该特征提取步骤被用于压缩原始数据，并建立适合识别和分类的分割签名。由于没有3D数据的黄金标准描述子，我们使用一些不同的描述子。

给定一组  ，描述子被计算为特征向量  。其中该特征向量可能被扩展来包含大量描述子，两个提供有趣结果的描述子被展示。

 基于特征值：在该描述子中，分割点云的特征值被计算并组成一个1x7维特征向量，我们计算[23]中提出的线性，平面性，散射性，omnivariance，各向异性，特征熵和曲率变化。

 形状直方图的聚合：1x640维特征由10个直方图得到，其编码了[6]中提到的D2，D3和A3形状函数。D2形状函数是随机选取点对的距离，D3编码了随机选取点三元组的区域，A3形状函数描述了从这些三元组中得到的两直线间的角度。

C. 分割匹配

使用这些特征，我们希望识别来自源点云和目标点云间的匹配。对于这个操作，我们选择一个学习方法，因为选择合适的距离尺度和阈值经常很困难，特别是当多个特征形状被涉及时。一个分类器被用于做出最终决策关于是否两个分类表示相同的物体或者物体部分。为了维护高效性，我们首先通过在特征空间中执行一个k-d树搜索来检索候选匹配，其接着被喂入分类器。

特别地，我们采用随机森林由于它的分类和时间表现。分类后的想法是构建大量不同的决策树，并为投票得到最终类别。在学习阶段，每棵树使用一个训练数据集的bootsrapped子集和特征的一个随机子集被训练。随机森林提供类似AdaBoost算法的分类表现，但是对输出编号的噪声不敏感（例如错编号候选）因为它们不集中精力到错分类候选中[24]。

对于用来决定类  和  是否表示相同物体的随机森林分类器，我们计算基于特征值特征向量的绝对差异  。特征向量  和  也被喂入分类器得到一个完整的基于特征值的1x21维组合向量。对于形状特征的组合的10个直方图，直方图交被计算，导致一个1x10维的特征。给定这组特征，随机森林分类器分配一个得分  给该匹配。一个在  上的阈值被应用来构建候选匹配的最终类别，传送给下一个模块。该阈值依赖被用于匹配的特征的子集，在表1中被定义。

表1. 三个分割匹配策略的参数

D. 几何验证

候选匹配使用RANSAC被喂入几何验证测试[25]。变换使用分割中心被验证。一个几何一致的类别簇最终被接受基于最小分割数量，从而得到一个6DOF变换和一组匹配分割，其表示一个场景识别候选。