编者序：本文是ETH大牛们 2016年提出的3D激光闭环检测方法，通过点云分割及匹配，获得远优于基于关键点的检测方法，在KITTI上能够实现高于1Hz的实时定位，在局部和全局描述之间做了很好的折衷。本文的开源算法可应用于激光定位或激光SLAM中。
推荐指数 ☆☆☆☆☆☆☆
1 引言
闭环检测是SLAM的一个难点，由于没有全局定位信息时状态估计漂移在所难免，可靠闭环检测时很多机器人平台的一种至关重要的能力。基于图像的闭环检测有很多较成功的策略，但基于图像的闭环检测在光照或视角剧烈变化时不可靠。基于Lidar的定位并不受外部光照的变化，且不像视觉那样对视角变化那么敏感，因为Lidar能够以极高分辨率获得环境几何信息。本文主要关注3D Lidar室外稳健定位。
现有的3D Lidar数据闭环检测策略主要时基于关键点检测和匹配。Lowry等人证明使用分割或目标级别的描述子兼具局部和全局特征的优点，目标或分割地图与拓扑地图或metric地图相比也有一定优势，可以更好的描述运动目标，更接近人类感知环境所使用的方式。
本文算法首先从3D点云中分割并描述分割，然后使用几何确认方法与已访问位置进行匹配。这种基于分割的闭环检测方法优点在于能够显著压缩点云为一系列明显易于区分的元素，不仅减少了匹配所需的耗时，而且降低了错误匹配的概率。
至于分割描述子，尽管目前已有很多3D点云描述子，但并没有明显的性能高低之分，没有证据表明其中一种在泛化能力或对几何对称对稳健性等方面优于其它描述子，因此我们采用一种机器学习方法匹配多种标准分割描述子。然而，由于算法框架的模块化设计，将来在3D分割、识别、描述的研究进展可以很方案的替换目前处理流程中对应部分。
据我们所知，本文首次提出了基于分割的3D Lidar实时闭环检测和定位算法，并通过实际应用进行了算法评估，而且开源了部署代码。
2 相关工作
从3D数据中检测闭环在机器人定位中仍是个开放问题，现有方法可分为三类：基于局部特征、基于全局描述子和基于平面或目标。Bosse等人直接从点云提取关键点并使用3D Gestalt描述子，然后使用vot矩阵描述关键点的最近临关系，根据门限值识别位置。除了Gestalt描述子，一些其它局部特征描述子也可以用于该框架，如FPFH等。Zhuang等人将局部scan变换为方位角图像并提取SURF特征，然后在匹配描述子之前使用基于3D空间信息的方法对场景进行排序。Steder等人首先将局部scan变换为距离图像，提取特征并于数据库中的特征使用欧式距离进行匹配；后来有学者将该方法改为使用NARF描述子和词带方法进行匹配。Loam使用距离数据实时估计离成绩，闭环检测依赖离线算法。
Rohling等人提出了一种使用1D高度直方图描述局部点云的方法，假设传感器高度固定，然后根据直方图和Wasserstein指标识别位置。Granström等人使用体积、距离直方图等旋转不变特征描述点云，计算标量特征距离和直方图特征互相关，使用adaboost分类器匹配位置，最后使用ICP计算点云相对位姿。Magnusson等人将点云分割为重叠网格并计算每个网格的形状特性（如线性、球形等），组成表面形状直方图，然后进行描述子匹配检测闭环。
局部关键点特征描述性不强，已有学者使用3D分割或目标进行位置识别。Fernandez-Moral等人通过检测3D环境中的平面识别位置；Finman等人使用基于目标的RGBD相机室内闭环检测，但仅能在较小空间使用，仅能处理很少的分割良好的目标。
本文旨在提出一种不依赖于类似于环境由平面等几何元素组成或包含丰富目标库等假设的更通用的闭环检测方法。Douillard等人提出的基于分割的SLAM方法，基于分割将velodyne scan对齐，使用Symmetric Shape Distance匹配分割。Analogously等人在EKF SLAM框架中使用分割而非点特征作为路标。本文受上述两种方法启发。
3 SegMatch算法
本文算法包括点云分割、特征提取、分割匹配和几何确认四个模块，如下图所示。
3.1 分割
SegMatch分割模块将点云分割为一些易于匹配的明显元素，首先进行点云体素滤波降噪，然后使用"cluster-all"方法将点云分割为一系列点集C-i。分割前需要移除地面，可以通过基于高度均值和方差的相邻体素聚类实现；移除地面后，使用欧式聚类进行分割，聚类中心通过所有点平均获得。
3.2 特征提取
点云分割后，提取每个分割的特征，特征提取用于压缩原始数据并建立适合识别和分类的目标特性。由于目前没有明确的gold-standard 3D描述子，我们使用一些不同的描述子。对于聚类C-i，描述子为特征向量[f1 f2 … fm]，尽管该特征向量可以包含大量描述子，本文使用两种描述子。f1为基于特征值的描述子：计算点云分割特征值形成1✖7的特征向量，具体包括linearity、 planarity,、scattering,、omnivariance,、anisotropy、 eigenentropy和curvature 变化。f2为形状直方图组合：维数为1✖640，包括D2、D3和A3形状函数编码的10个直方图。D2时随机选取两个点的直方图；D3是随机选择3个点的区域编码；A3描述了这些3点中两条线间的夹角。
3.3 分割匹配
由于很难选择合适的距离指标和门限，尤其是包括多个特征类型时，所以本部分采用机器学习方法进行匹配。使用分类器决定两个分割是否代表同一个目标或部分目标，为了提高效率，首先在特征空间进行kd树搜索，然后再分类。
考虑到分类效果和时间消耗，本文采用随机森林进行分类，随机森林性能与adaboost类似，但是对输出标记噪声（如错误标记）不敏感，原因在于it does not concentrate its efforts on misclassified candidates。随机森林同时可提供关于特征相对重要性的信息（权值）。
为区分C-i和C-j是否代表同一个目标，我们计算了特征值向量fi和fj差的绝对值abs(fi-fj)，和fi、fj组成1✖21的特征输入随机森林；对于10个直方图组合特征，计算直方图交叉形成1✖10特征。随机森林根据这些特征计算出得分w，过门限检测后将候选匹配送入下一个模块。
3.4 几何确认
使用RANSAC对候选匹配进行几何确认，使用分割中心估计变换，基于最少分割数接受几何一致性聚类分割，得到6DOF变换和匹配分割列表。
4增量分割
为执行闭环检测，需要在线实时构建目标分割地图。对于每一全局参考帧中的点云，首先以当前位置为中心、半径为R的圆柱邻域提取局部点云。分割和特征提取仅执行一次，生成的source segment用于匹配和构建目标地图。在向目标地图添加source segment时需要考虑两种特殊情况：（1）不完整分割，对点云进行圆柱滤波不可避免会产生不完整分割，对目标地图造成干扰，需要检测并丢弃不完整分割以使得地图包括尽可能多的完整分割，可使用更小半径r=R-b对source cloud 进行滤波，其中b为外部区域厚度。（2）重复分割，通过比较最近分割中心间距检测重复分割，去除相对较老的分割。
5评估
5.1数据集
采用KITTI的00、05和06序列进行评估，06共1.2km用于训练分类器；00共3.7km并且包含500米的闭环重访，用于定位实验；05共2.2km用于框架实时在线测试。为实时生成全局地图，对Velodyne原始点云进行均匀降采样去除一半扫描点，当车辆至少移动1m时才将scan加入全局地图。为提取source点云，设置圆柱半径邻域R为60米，体素网格设为0.1米，当网格中至少有2个点时才认为被占据。分割时，当两个占据体素网格欧式距离不超过0.2米时认为是同一个聚类。我们认为分割大小为100个点到15000个点之间。
5.2训练和测试
首先提取并描述分割组成target地图，当重访出现时，对于局部点云的每个分割，使用knn基于特征空间在target地图中提取200个近邻，组成分割间的正确匹配和错误匹配样本。基于该策略，在06序列上生成了2000个正样本和800000个反样本，训练随机森林时，我们使用的正负样本比例为1:50，训练集共包含102000个样本。
5.3分割匹配性能
本部分评估三种分割匹配方式：L2是指基于分割特征向量之间的欧式距离进行匹配；RF_eigen是仅仅采用特征值特征的随机森林分类；RF_eigen shapes是指采用特征值和形状特征的随机森林分类。不同方式的参数如下表所示。采用00序列测试的ROC曲线如下图所示，后续实验采用FPR（false positive rate）为0.2，以便限制错误分割匹配和错误闭环检测。
RF_eigen shapes分类器的一些匹配分割结果如下图所示，上面一行为target，下面一行为source。
5.4定位性能
使用序列00进行本部分测试，前半部分用于建图，重访部分用于定位测试。对比算法选为基于关键点的算法：首先使用0.3m的半径计算经滤波后的每个点的法线，然后提取Harris 3D关键点；然后进行关键点滤波使得它们最小间距为0.5米，以便保证每个区域不被重复描述，从而降低几何确认环节的模糊；然后使用半径0.4米的FPFH进行关键点描述；最后匹配75个最近邻并使用RANSAC进行确认，输出闭环检测结果。
运行50次，在target分割地图上定位所需运动距离概率如下图所示，其中基于关键点方法和L2方法检测到错误闭环次数分别为292和14，而基于随机森林的两种方法没有错误检测。可见，基于分割的方法远远优于基于关键点的方法。
在主频为2.8GHz的Intel i7 CPU上，各模块耗时如下表所示。值得注意的是，形状特征提取、直方图交叉和随机森林分类都可以并行处理。
5.5闭环性能
在05序列上实时闭环检测如下图a所示，正确检测到12个闭环；然后使用位姿图优化后如b所示。
本文算法可以很方便的替换子模块以适用于其它环境。下图给出了带平滑约束基于区域生长分割方法的闭环检测，下方是参考点云，上方是局部点云，绿色代表分割匹配。
英文名称：SegMatch: Segment based loop-closure for 3D point clouds
源码：https://github.com/ethz-asl/segmap/tree/master/segmatch
本公众号专注于提供计算机视觉、机器学习、深度学习、智能传感器技术等人工智能、机器人、无人车、无人机相关领域省时的知识转述，敬请各位看官关注、评论、转发、分享。
关注该公众号，一起创造奇迹。
,
