Scan Context 由韩国KAIST大学的 Giseop Kim, Ayoung Kim 于2018年发表在IROS(International Conference on Intelligent Robots and Systems).Scan Context 应用于基于3D点云的重定位和场景识别,主要思想是将场景3维信息压缩,将笛卡尔坐标系的信息转换到极坐标系下计算。优势是高效利用场景点云分布特征,引入"旋转不变性"描述子,快速搜索。

$\mathrm{Scan Context}$:用于 3D 点云地图中地点识别的以自我为中心的空间描述子

摘要

与用于视觉场景的各种特征检测器和描述子相比,使用结构信息描述地点的研究相对较少。同时定位和建图 (SLAM) 的最新进展提供了环境的密集 3D 地图,并且定位是由不同的传感器提出的。针对基于结构信息的全局定位,我们提出了 $\mathrm{Scan Context}$,这是一种来自 3D 光检测和测距(激光雷达) (Light Detection and Ranging ,LiDAR) 扫描的基于非直方图的全局描述子。与先前研究的方法不同,所提出的方法直接从传感器记录可见空间的 3D 结构,而不依赖于直方图或先前的训练。此外,该方法提出了使用相似度分数来计算两个$\mathrm{Scan Context}$之间的距离,以及一种两阶段搜索算法来有效地检测回环。$\mathrm{Scan Context}$及其搜索算法使回环检测不受激光雷达视点变化的影响,从而可以在重新访问同一个地点和拐角等地方检测到闭环。$\mathrm{Scan Context}$性能已经通过 3D激光雷达扫描的各种基准数据集进行了评估,并且所提出的方法显示出充分改进的性能。

Ⅰ.引言

在许多机器人应用中,位置识别是重要的问题。特别是对于 SLAM,这种识别为闭环提供了候选项,这对于纠正漂移误差和构建全局一致的地图至关重要 [1]。虽然闭环对机器人导航至关重要,但错误的匹配可能是灾难性的,需要仔细匹配。视觉识别随着相机传感器的广泛使用而流行,然而,由于光照变化和短期(例如,移动的物体)或长期(例如,季节)的变化,它本质上是困难的。因此,最近的文献集中在通过检查表示 [2] 和弹性后端 [3] 的鲁棒位置识别。

与这些视觉传感器不同,激光雷达最近因其对感知方差的强不变性而受到关注。早期,传统的局部关键点描述子 [4, 5, 6, 7] 最初是为计算机视觉中的 3D 模型设计的,尽管它们容易受到噪声的影响,但已被用于位置识别。基于激光雷达的位置识别方法已在机器人文献中广泛提出 [8, 9, 10]。这些工作侧重于从结构信息(例如点云)中以局部 [8] 和全局方式 [10] 开发描述子。

现有的基于 LiDAR 的位置识别方法一直试图克服两个问题。首先,无论视点变化如何,都需要描述子来实现旋转不变性。其次,噪声处理是这些空间描述子的另一个主题,因为点云的分辨率随距离而变化,并且法线是有噪声的。现有方法主要使用直方图[9,11,12]来解决上述两个问题。然而,由于直方图方法只提供场景的随机索引,描述场景的详细结构并不简单。这种限制使得描述子对于地点识别问题的可识别性降低,从而导致潜在的误匹配。

image-20220429164041335

image-20220429164059389

图 1. 两步$\mathrm{Scan Context}$创建。使用来自 3D 扫描的点云的俯视图 (a),我们将地面区域划分为 bin,根据方位角(在 LiDAR 框架内从 0 到 2π)和径向(从中心到最大感应范围)进行划分方向。我们将黄色区域称为一个环,将青色区域称为一个扇区,将黑色填充区域称为一个 bin。$\mathrm{Scan Context}$是(b)中的矩阵,它明确地保留了点云的绝对几何结构。 (a) 中描述的环和扇区在 (b) 中分别由相同颜色的列和行表示。从位于每个 bin 中的点中提取的代表值用作 (b) 的对应像素值。在本文中,我们使用 bin 中点的最大高度。

在本文中,我们提出了 $\mathrm{Scan Context}$,这是一种具有匹配算法的新型空间描述子,专门针对使用单个 3D 扫描的户外地点识别。我们的表示将 3D 扫描中的整个点云编码为矩阵(图 1)。所提出的表示描述了以自我为中心的 2.5D 信息。该方法的贡献点是:

  • 高效的 bin 编码功能。与现有的点云描述子 [7, 10] 不同,所提出的方法不需要计算 bin 中的点数,而是提出了一种更有效的用于位置识别的 bin 编码函数。这种编码对点云的密度和法线具有不变性。
  • 保留点云的内部结构。如图 1 所示,矩阵的每个元素值仅由属于 bin 的点云确定。因此,与将点的相对几何描述为直方图并丢失点的绝对位置信息的[9]不同,我们的方法通过有意避免使用直方图来保留点云的绝对内部结构。这提高了判别能力,还可以在计算距离时将查询扫描与候选扫描(在我们的实验中,6°方位角分辨率)进行视点对齐。因此,也可以通过使用$\mathrm{Scan Context}$来检测反向闭环。
  • 有效的两相匹配算法。为了实现可行的搜索时间,我们为第一个最近邻搜索提供了一个旋转不变的子描述子,并将其与成对相似度评分分层结合,从而避免搜索所有数据库进行闭环检测。
  • 针对其他最先进的空间描述子进行彻底验证。与其他现有的全局点云描述子相比,例如 M2DP [8]、形状函数集合 (ESF) [11] 和 Z 投影 [12],所提出的方法具有实质性的改进。

Ⅱ.相关工作

移动机器人的位置识别方法可以分为基于视觉和基于激光雷达的方法。视觉方法已普遍用于 SLAM 文献中的地点识别 [13, 14, 15]。 FAB-MAP [13] 通过学习视觉词袋的生成模型,使用概率方法提高了鲁棒性。然而,视觉表示具有局限性,例如易受光照条件变化的影响[16]。已经提出了几种方法来克服这些问题。 SeqSLAM [17] 提出了基于道路的方法,并显示出比 FAB-MAP 大大提高的性能。 SRAL [2] 融合了几种不同的表示,例如颜色、GIST [18] 和 HOG [19],用于长期视觉位置识别。

LiDAR 对上述这些感知变化具有很强的鲁棒性。基于 LiDAR 的方法被进一步分类为局部和全局描述子。局部描述子,例如 PFH [4]、SHOT [5]、shape context[7]或 spin image [6],首先找到一个关键点,将附近的点分成 bin,并将周围 bin 的模式编码为直方图。Steder 等人提出了以词袋的方式利用点特征和完形描述子(gestalt descriptor) [20] 的位置识别方法[8]。

然而,这些关键点描述子显示出局限性,因为它们最初是为 3D 模型部分匹配而不是为位置识别而设计的。例如,与 3D 模型不同,3D 扫描(例如,来自 VLP-16)中的点云密度会随着与传感器的距离而变化。此外,由于现实世界中的非结构化对象(例如树),点的法线比模型噪声更大。因此,局部方法通常需要关键点的法线,因此不太适合户外的地点识别。

全局描述子不包括关键点检测阶段。 GLARE [9] 及其变体 [21, 22] 将点之间的几何关系编码为直方图,以代替搜索关键点和提取描述子。 ESF [11] 使用了由形状函数制成的直方图的串联。 Muhammad 和 Lacroix 提出了 Z 投影 [12],它是法向量的直方图,以及具有两个距离函数的双阈值方案。Heet 等人提出了 M2DP [10],它将扫描的整个 3D 点云投影到多个 2D 平面并提取 192 维紧凑的全局表示。M2DP 表现出比现有点云描述子更高的性能以及对噪声和分辨率变化的鲁棒性。如本段所述,全局描述子通常使用直方图。最近,SegMatch [23] 引入了一种基于分段的匹配算法。这是一种高级感知,但需要一个训练步骤,并且需要在全局参考框架中表示点。

在本文中,我们提出了一种新的位置描述子,称为$\mathrm{Scan Context}$,它将 3D 扫描的点云编码为矩阵。$\mathrm{Scan Context}$可以被认为是Shape Context [7] 的扩展,用于定位 3D LiDAR 扫描数据的位置识别。具体来说,$\mathrm{Scan Context}$包含三个组成部分:在每个 bin 中保留点云的绝对位置信息的表示、高效的 bin 编码函数和两步搜索算法。

Ⅲ.$\mathrm{Scan Context}$进行地点识别

在本节中,我们描述了给定来自 3D 扫描的点云的$\mathrm{Scan Context}$创建,并提出了一种计算两个$\mathrm{Scan Context}$之间距离的度量。接下来,介绍两步搜索过程。使用$\mathrm{Scan Context}$进行位置识别的整体流程如图 2 所示。$\mathrm{Scan Context}$的创建和验证也可以在 scancontext.mp4 中找到。

A.$\mathrm{Scan Context}$

我们为户外地点识别定义了一个名为 $\mathrm{Scan Context}$ 的地点描述子。

图 2. 算法概述。首先,将单个 3D 扫描中的点云编码到$\mathrm{Scan Context}$中。然后,从$\mathrm{Scan Context}$中对 $N_t$(环数)维向量进行编码,并用于检索最近的候选项以及 KD 树的构造。最后,将检索到的候选与查询$\mathrm{Scan Context}$进行比较。满足接受阈值并最接近查询的候选被认为是闭环。

$\mathrm{Scan Context}$的关键思想受到 Belongie 等人提出的 Shape Context [7] 的启发,它将局部关键点周围的点云的几何形状编码为图像。然而他们的方法只是简单地计算点的数量来总结点的分布,我们的方法与他们的不同之处在于我们使用每个 bin 中点云的高度。使用高度的原因是为了有效地总结周围结构的垂直形状,而不需要大量的计算来分析点云的特征。此外,最大高度表示从传感器可以看到周围结构的哪一部分。这种以自我为中心的可视化在城市设计文献中一直是一个众所周知的概念,用于分析一个地方的身份[24, 25]。

与Shape Context [7] 类似,我们首先将 3D 扫描划分为传感器坐标中的方位角和径向 bin,但采用等间距的方式,如图 1(a) 所示。扫描的中心充当全局关键点,因此我们将$\mathrm{Scan Context}$称为以自我为中心的位置描述子。$N_s$ 和 $N_r$ 分别是扇区和环的数量。也就是说,如果我们将 LiDAR 传感器的最大感应范围设置为 $L_{max}$,则环之间的径向间隙为 $\frac{L_{max} }{N_r}$,扇形的中心角等于$\frac{2\pi}{N_s}$。在本文中,我们使用 $N_s= 60$ 和 $N_r = 20$。

因此,制作$\mathrm{Scan Context}$的第一个过程是将 3D 扫描的整个点划分为相互排斥的点云,如图 1(a) 所示。$\mathcal{P}_{ij}$是属于第$ i $个环和第 $j$ 个扇区重叠的 bin 的点集。符号 $[N_s]$ 等于$ \{1, 2, ..., N_{s-1}, N_s\}$。因此,分区在数学上是

$$ \mathcal{P}=\underset{i\in[N_r],j\in[N_s]}{\cup}\mathcal{P}_{ij}\tag{1} $$

因为点云是按固定间隔划分的,所以远离传感器的 bin 的物理面积比近的 bin 更宽。但是,两者都被同等地编码到$\mathrm{Scan Context}$的单个像素中。因此,$\mathrm{Scan Context}$补偿了由于远点稀疏导致的信息量不足,并将附近的动态对象视为稀疏噪声。

在点云分区之后,使用该 bin 中的点云为每个 bin 分配一个实数值:

$$ \phi:\mathcal{P}_{ij}\rightarrow\mathbb{R}\tag{2} $$

我们使用最大高度,其灵感来自城市能见度分析 [24, 25]。因此,bin 编码函数为:

$$ \phi(\mathcal{P}_{ij})=\underset{p\in\mathcal{P}_{ij}}{\max}z(p)\tag{3} $$

其中 $z(\cdot ) $是返回点 $p$ 的$ z $坐标值的函数。我们为空的bin分配零。例如,如图 1(b) 所示,$\mathrm{Scan Context}$中的蓝色像素意味着与其 bin 对应的空间是空闲的,或者由于遮挡而未观察到。

通过上述过程,最终将$\mathrm{Scan Context}$ $I$ 表示为$ N_r\times N_s$ 矩阵:

$$ I=(a_{ij})\in\mathbb{R}^{N_r\times N_s},a_{ij}=\phi(\mathcal{P}_{ij})\tag{4} $$

为了对变换进行鲁棒的识别,我们通过$\mathit{ root\ shifting}$ 来增强 $\mathrm{Scan Context}$。通过这样做,在轻微运动扰动下从原始扫描中获取各种$\mathrm{Scan Context}$变得可行。

在重新访问到过的地方时,单个$\mathrm{Scan Context}$可能对平移运动下的扫描中心位置敏感。例如,当重新访问不同通道中的相同位置时,可能不会保留$\mathrm{Scan Context}$的行顺序。为了克服这种情况,我们根据水平间隔将原始点云转换为 $N_{trans}$ 个邻居(本文中使用$N_{trans}=8$ ),并将从这些$\mathit{ root\ shifting}$ 点云获得的$\mathrm{Scan Context}$存储在一起。我们假设即使在实际移动的位置也能获得类似的点云,这是有效的,除了少数情况下,比如一个新空间突然出现的交叉点。

B. $\mathrm{Scan Context}$之间的相似度得分

给定一个$\mathrm{Scan Context}$对,我们需要一个距离度量来衡量两个地方的相似性。$I^q$ 和$ I^c $分别是从查询点云和候选点云获取的$\mathrm{Scan Context}$。它们以列方式进行比较。也就是说,距离是同一索引处的列之间的距离之和。余弦距离用于计算相同索引处的两个列向量 $c^q_j $和 $c^c_j $之间的距离。此外,我们将总和除以总列数$N_s$用于归一化。因此,距离函数为:

$$ d(I^q,I^c)=\frac{1}{N_s}\sum^{N_s}_{j=1}(1-\frac{c^q_j\cdot c^c_j}{\parallel c^q_j \parallel \parallel c^c_j \parallel}).\tag{5} $$

考虑到贯穿扇区的一致性,基于列的比较对动态物体特别有效。然而,候选$\mathrm{Scan Context}$的列甚至可以在相同的地方移动,因为激光雷达的视角对于不同的地方是不同的(例如,在相反的方向或角落重新访问一个地方)。图3说明了这种情况。由于$\mathrm{Scan Context}$是依赖于传感器位置的表示,因此行顺序始终是一致的。但是,如果 LiDAR 传感器相对于全局坐标的坐标发生变化,则列顺序可能会有所不同。

image-20220429201446582

图 3. 具有时间间隔的同一地点的$\mathrm{Scan Context}$示例。重新访问时传感器视点的变化导致$\mathrm{Scan Context}$的列移位,如 (a) 所示。但是,这两个矩阵包含相似的形状并显示相同的行顺序。

为了解决这个问题,我们使用所有可能的列移位后的$\mathrm{Scan Context}$来计算距离,并找到最小距离。$I^c_n$ 是一个$\mathrm{Scan Context}$,它的第$n$列是从原始的$\mathrm{Scan Context}$偏移过来的。这与以$\frac{2\pi}{N_s}$分辨率粗略对齐两个点云以获取旋转分量中的偏航角的任务相同。然后,我们确定最佳对齐的列移位数量$(7)$和对应的距离$(6)$:

$$ \begin{align*} D(I^q,I^c)&=\underset{n\in[N_s]}{\min}d(I^q,I^c_n),\tag{6}\\ n^*&=\underset{n\in[N_s]}{\arg\min}\ d(I^q,I^c_n),\tag{7} \end{align*} $$

请注意,此附加移位信息可以作为进一步定位细化的良好初始值,例如迭代最近点 (ICP),如第 IV-C 节所示。

C. 两阶段搜索算法

当在位置识别的ScanContext搜索时,有三个主要的典型工作流:成对相似性评分、最近邻搜索和稀疏优化[26]。我们的搜索算法将成对评分和最近邻搜索分层融合,以获得可接受的搜索时间。

由于我们在(6)中的距离计算比其他全局描述子如[12,10]更加耗时,我们通过引入ring key提供了一个两阶段分层搜索算法。Ring key是一个具有旋转不变性的描述子,它是从$\mathrm{Scan Context}$中提取的。$\mathrm{Scan Context}$的每一行,$r$,都通过环形编码函数$\psi$编码成一个实数值。矢量$k$的第一个元素来自距离传感器最近的环,随后的元素来自下一个环,如图4所示。因此,ring key成为一个 $N_r$ 维向量,如 (8):

$$ k=(\psi(r_1),...,\psi(r_{N_r})),\mathrm{where}\ \psi:r_i\rightarrow\mathbb{R}\tag{8} $$

我们使用的环编码函数$\psi$是使用 $L_0$范数的环的占用率:

$$ \psi(r_i)=\frac{\parallel r_i \parallel_0}{N_s}\tag{9} $$

由于占用率与视点无关,因此ring key实现了旋转不变性。

image-20220429203142763

图 4. 快速搜索的ring key生成。

虽然不如$\mathrm{Scan Context}$信息丰富,但ring key支持快速搜索,以找到可能的候选闭环。向量$k$用作构建KD树的key。同时,要查询扫描的ring key用于查找相似的key及其对应的扫描索引。将被检索的相似key的数量由用户决定。使用距离(6)将这些恒定数量的候选$\mathrm{Scan Context}$与要查询的$\mathrm{Scan Context}$进行比较。最接近的满足给定阈值的候选项被选为重新访问的位置:

$$ c^*=\underset{c_k\in\mathcal{C} }{\arg\min}\ D(I^q,I^c),s.t. \ D<\tau\tag{10} $$

其中 $\mathcal{C}$ 是从 KD 树中提取的一组候选索引,$\tau$ 是给定的接受阈值。 $c^∗ $是确定为闭环的位置的索引。

Ⅳ.实验评估

略.......

Ⅴ.结论

在这篇文章中,我们提出了一个空间描述子——$\mathrm{Scan Context}$,将一个地方概括为一个矩阵,这个矩阵明确描述了以自我为中心的环境的2.5D结构信息。与使用点云的现有全局描述子相比,$\mathrm{Scan Context}$在各种数据集上显示出更高的闭环检测性能。

在未来的工作中,我们计划通过引入额外的层来扩展$\mathrm{Scan Context}$。也就是说,其他bin编码函数(例如,bin的语义信息)可被用于提高性能,即使对于具有高度重复结构的数据集,如复杂城市激光雷达数据集。

Lidar定位:Scan Contexthttps://zhuanlan.zhihu.com/p/359523177

Scan Context 介绍及理解https://zhuanlan.zhihu.com/p/393353116

从零开始做自动驾驶定位(二): 数据集https://zhuanlan.zhihu.com/p/104875159

🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/46.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 06 月 10 日
赏杯咖啡