【论文阅读6】SCAN CONTEXT:用于场景识别的空间点云描述符

scan context是一种用于场景识别点云全局描述符,可以用在SLAM的回环检测。本篇文章发表在2018年IROS上,目前代码已开源。论文题目是Scan Context: Egocentric Spatial Descriptor for Place Recognition within 3D Point Cloud Map。目前基于此,已经出现了一些增强版,比如发表在2020 ICRA上的intesity scan context(ISC)描述符,其repo地址:https://github.com/irapkaist/scancontext.git

点云的全局描述符一般需要解决以下两个核心问题:

  1. 旋转不变性,而不管视角如何变化。

  2. 噪声处理能力,因为点云的分辨率随距离变化,并且法线有噪声。

image-20200907110501074

概述

基于此,本文的创新点主要有以下几个:

  • 基于扇形区块的高效编码方式,不需要逐个计算点云中点的数量而能够部分展现点云的密度和法线特征。
  • 不使用直方图统计的方式(传统方法),也能够做到保留点云的内部结构。这样对不同的视角场景的识别能力更强。
  • 高效的搜索方式。近设计了一种速度更快的、具有旋转不变性的子描述符(ring key)用于第一步的近邻搜索。将它与后续的相似性评分进行组合,避免搜索所有数据库以进行循环检测。

其算法的结构图如下:

image-20200907191904376

首先是将点云帧编码成scan context图像,第二步进入两步搜索流程,在图像中提取ring key,构建kd tree,在候选帧中筛选最相近的多帧scan context图像,然后分别计算相似性评分,最终选取评分最高的,即为检测到回环。

核心算法

特征编码

以扇形区块的方式来组织点云,半径方向按距离均匀划分,为ring,在角度上也均匀划分,为sector,那么即形成有序的扇形区域,称作bin,如图a。一帧点云就投影成的一张scan context图像,其像素值为当前区块内所有点的最大z值。image-20200913192231501)分别代表着sc图像的行数和列数。如果传感器的最远测量距离为L_max,那么半径方向上一共有image-20200913192402536)个ring,即为sc图像的列数。水平方向上每一个sector之间的角度为image-20200913192545249

image-20200907191645994

论文中,作者的ring (Nr)为20,sector (Ns)为60,一帧点云即可用公式1表示。

image-20200907193320000

某一个区块image-20200907193439886处的像素值用公式3来表示。

image-20200907193359254

在特征图像中,一行即代表距离当前雷达位置N米处360度的高度情况,基本上能够粗略的描述出周围的空间结构。一帧scan context图像矩阵即表示为公式4,这个图像即为scan context描述符。

image-20200907193735799

这里为了避免在同一个位置的点云因为路面坑洼原因导致车辆垂直方向的扰动,导scan context出现行向量平移的情况,

作者给出了一个root shifting的技巧,这里不太理解,代码里面也没有体现,先贴出来

image-20200913191118883

相似性评分

给定两帧Scan context图像I_q和I_c,如何进行相似性评分?由于sc图像的尺寸一致,可以计算对应第j列向量cj_q和cj_c的差值,将所有的列向量差值相加并归一化,即为衡量标准。这里两个列向量的差值采用余弦相似度来表示。这里为什么比较列向量,作者的理由是:考虑到整个行业的共识,按列比较对于动态对象特别有效

image-20200913192923814

单纯的计算列向量的差值可能存在一些问题,如下图在revisit场景下(同一位置,但朝向和上次相反),a、b图是同一位置不同视角的点云提取而来的scan context图像,可以看到由于传感器视角的变化导致了scan context的列偏移,但是它们具有相同的行次序和相似的形状。image-20200913191403642

针对列向量平移的现象,计算两个scan context的所有列向量之间的距离,并取最小值作为最终的距离,那么那么列平移的最佳匹配关系就可以定义为

image-20200914155145633

最小距离就可以定义为:

image-20200914155123463两步搜索

场景识别问题中经典的三步:相似性评分、近邻搜索和稀疏优化。这里把第一步和第二步进行了合并。因为上一步中相似性计算比其他全局描述符要复杂,这里引入ring key来进行两阶段的分层搜索。ring key是定义的一种旋转不变性的描述符,它将sc中的每一行通过下面的函数image-20200913202504793编码成一个数值(L0范数),这里就是每一行的平均高度,可以粗略代表距离传感器中心多少米的一个高度分布情况。

image-20200913202450045

那么一个sc特征图像就可以用一个N_r维向量k来表示(继续降维),即为ring key

image-20200913202619905

这里继续构建一个N_r维的KD Tree,后续搜索候选帧的时候,先计算ring key,然后搜索ring key最相似的一些帧。这里使用前文提到的距离计算公式计算当前场景和候选场景的scan context距离以算出最临近历史场景,满足以下阈值的候选场景被认为是重访问场景。其中 image-20200914155514107是从KD树中搜索出来的候选场景的scan context矩阵,τ 是设定的判断两个场景是否相似的距离阈值,image-20200914155532262是最终检测出来的和当前场景一致的历史场景索引。

image-20200913203152810

实验

实验部分我认为是一篇文章的核心部分,从实验设计上可以看出作者的思路,以及算法是否存在漏洞,哪里还有改进空间。

这里实验设计,对比的对象主要是以下M2DP, Z- projection, and ESF三种全局描述符,选取了不同的场景数据集,KITTI(00, 02, 05, and 08)和NCLT以及Complex Urban

image-20200914155835855

以下三个数据集典型特点如下:

  • KITTI:存在大量反向回环的场景,可以有效检测出描述子的旋转不变性。

  • NCLT:存在大量不同季节、不同时段的同一地点的场景,检测其对环境变化的敏感性。

  • Complex Urban:存在多种复杂的城市环境场景。

此外,作者将scan context的ring key候选帧分为10和50帧两种来进行实验。

精准率和召回率评估

image-20200914161212495

精准率(Precision)的公式是image-20200914161257885),表示正确被检索的样本占实际被检索到的(TP+FP)的比例,针对预测结果而言,即预测为正的样本中有多少是真正的正样本。召回率(recall)的公式是image-20200914161453968, 它计算的是所有”正确被检索的结果(TP)”占所有”应该检索到的结果(TP+FN)”的比例,针对实际样本而言,即样本中的正例有多少被预测正确了。

在各数据集上,其PR曲线如下,我们希望能够做到精准率和召回率同时高,由以下实验结果可以得出结论。

  • 基于直方图的ESF和Z-projection方法在所有数据集上的表现都比scan context差。
  • scan context-50的结果始终好于scan context-10。

image-20200914162001203

image-20200914162338238

image-20200914162359099

存在以下问题:

  • scan context在室内场景下表现很差(NCLT)。

  • 在一些周围高度近似,具有垂直形状的道路结构场景下表现差。(Urban 02)如下图,在一些很窄的道路上,各方向的信息很有限。

    image-20200914170735489

定位精度评估

下图展示了scan context能够处理一些反向回环的情况(其他两种描述符均失败),同时可以作为ICP匹配的初值,显著提高匹配的速度,甚至于在一些非结构化的环境中也能顺利匹配成功。

image-20200914171321167

在下图中KITTI数据集中,对比了是否利用sc的结果作为初值,来进行ICP匹配,最终得到的匹配时间以及RMSE结果。可以看到以sc匹配作为初值能够显著提高ICP的匹配速度和鲁棒性。

image-20200914191252830

计算量

在计算量的对比上,scan context需要更多的时间,主要是提取sc特征比较耗时。其搜索时间包括KD树的创建和距离的计算。

image-20200914191909976

总结

在未来的工作中,我们计划通过引入其他层来扩展扫描上下文。 也就是说,即使对于具有高度重复结构的数据集(例如Complex Urban LiDAR数据集),也可以使用其他bin编码功能(例如bin的语义信息)来提高性能。

-------------    本文结束  感谢您的阅读    -------------
胡想成 wechat
欢迎关注个人公众号!
您的支持,是我装逼的最大动力!

本文标题:【论文阅读6】SCAN CONTEXT:用于场景识别的空间点云描述符

文章作者:胡想成

发布时间:2020年09月07日 - 10:09

最后更新:2020年09月14日 - 19:09

原始链接:xchu.net/2020/09/07/3SC/

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0许可协议,转载请注明出处!