（回环检测）Scan Context++: Structural Place Recognition Robust to Rotation and Lateral Variations ...

识别以前访问过的各种机器人任务的地方 (例如，同时定位和构图 (SLAM) 闭环检测[1]、绑架机器人的全球定位[2]或多机器人建图[3] 是重要的。在计算机视觉和机器人领域，用一组紧凑的表达来描述一个位置已经得到了深入的解决，产生了许多最先进的视觉位置识别方法[4、5、6、7]。与视觉位置识别研究的蓬勃发展相反，距离传感器的研究仍然缺乏对整体定位问题的坚实解决方案。

最近的研究指出，结构信息可能比外观更有效，尤其是在户外环境中。这些研究试图克服传感器数据无结构、无序、稀疏范围造成的主要瓶颈，使得距离传感器的输入数据比像素图像数据更难使用。现有的方法侧重于对位置结位置，但在结构化位置识别中很少实现不变性。

我们在[1]中提出的论文的初步版本试图捕获水平不严重的水平 (例如，低于 $10^{?}$) 建立这种紧凑的表示，如轮式机器人或缓慢移动的手持系统。这种策略使我们能够瞄准LiDAR 潜在的结构变化(如动态物体和季节变化) 尽管我们实现了鲁棒性。之前的 Scan Context 它显示了有意义的性能，但该算法无法实现横向不变性，而且使用暴力搜索效率低下。 [1] 在这些限制中，我们完成了一种常见的结构化位置识别方法，包括旋转和横向鲁棒算法，从而引入了距离传感器。其次，改进了算法使用子描述子，改进了以往的蛮力搜索方法，提高了搜索速度的数量级。总之，我们的新贡献是：

• 鲁棒的横向/旋转变化:在车道水平变化不可避免的城市环境中，缺乏水平不变性可能是一个关键问题。为了解决这个问题，我们总结了以前的描述子，包括水平和旋转鲁棒。这是基于城市道路的假设 Scan Context 实现增强。
• 半度量定位:结合位置检索和测量定位，我们的整体位置识别方法弥补了拓扑定位和测量定位之间的差距。该方法不仅提供了检索到的地图位置索引，而且还迭代了最近的点 (ICP) 等度量改进提供了1-DOF (偏航或横向) 初始猜测。
• 轻量级和模块独立性:提出的方法作为一种全球定位器，不需要先验知识或任何几何约束 (例如，里程计)。这种实现是轻量级的，只需要一个 C 可以实现文件和相应的头文件，并且很容易集成到现有文件中 SLAM 框架中。
• CPU实时性能：通过引入紧凑的子描述子和键，我们实现了计算资源的急剧下降。基于树搜索的键检索取代了简单的逐像素比较，然后是基于预对齐的键对齐。我们的方法可以在没有 GPU 支持高达100赫兹的运行频率 (例如，在 KITTI 00[12] 中平均需要 7.4ms)。
• 广泛验证：为了验证单任务和多任务场景，我们评估了在各种具有挑战性的测试场景中提出的方法。我们注意到SLAM 缺乏对匹配分布的评估，现有的精度召回曲线可能无法完全捕捉闭环检测性能。我们建议使用它 DR (distribution-recall) 用曲线来衡量有意义的闭环召回率及其分布。

在这部分中，我们从视觉和结构两个方面总结了位置识别文献。我们简要回顾了最近的位置识别工作，重点是传感器形式、全局和局部描述。

A. 位置识别用于视觉感知

A. 术语和问题定义

我们首先定义我们的位置识别问题。当机器人穿越环境时，一组距离传感器测量结果会随着时间戳的增加而被流式传输。我们将在时间 $t$ 的某一空间位置 $l_t$ 处获取的每个单个传感器测量值 $z_t$ 视为一个位置。地图是一个数据库，是机器人开始执行任务后所有被流式传输的测量数据的集合。然后，我们的位置识别问题就可以定义为在地图中查找待查询地点的重新访问的地点。同样重要的是要可信地决定地图上是否没有重新访问的地方。如果两个位置的空间位置之间的欧几里德距离小于某个阈值 (即，$|l_a-l_b|<{\delta }_l$)，则时间上大于特定窗口尺寸 (即，$|t_a-t_b|>{\delta }_t$) 的两个位置 $a$ 和 $b$ 满足重新访问的定义。

为了构建这样的位置识别系统，需要两个子模块。第一个是描述函数 $f(\cdot )$。为了便于处理有噪声或大量的原始测量值，原始测量值 $z_t$ 被编码为更紧凑的形式，称为描述子 $f_t=f(z_t)$。二是定义相似度函数 $sim(\cdot ,\cdot )$ 或距离函数 $D(\cdot ,\cdot )$ 的检索。它接受两个描述子，并返回描述子空间中的相似性或距离标量值。然后，利用描述函数和相似度函数，在给定待查询测量值 $z$ 和地图的情况下，位置识别问题可以被简化为最近邻搜索问题。如果描述子距离 $D(f_a,f_b)$ 低于阈值 $\tau$，人们可以得出结论，两个位置 $a$ 和 $b$ 的是相同的。

B. 不变性

大多数 LiDAR 位置识别方法 [25，28，32，31] 已经在几乎没有动态物体或者视角变化的较不复杂的环境 [12，39] 上进行了测试。现有的研究主要集中在提高描述子的区分性，而不是定义和克服结构的多样性。我们对结构化位置识别的潜在危害进行了分类分析，如表 I 所示。

表I

视觉和结构位置识别所需的不变性。

在与视觉位置识别问题的比较中，我们对每一种不变性进行了分类，对于每一种相应的不变性类型，视觉位置识别问题都得到了广泛的研究。

1. 内部因素：测量结果的变化可能源于机器人本身，我们称之为内部因素。这包括主要由自我运动引起的传感器坐标的旋转、平移和尺度变化 (表 I 中的 R、T 和 SP)。图1说明了在旋转和平移变化下的样本测量差异。在尺度上，由于感知距离引起的点云密度的变化，相同的对象看起来非常不同。

图1

经历旋转（例如，反向重访）和平移（例如，横向车道改变）运动的样本点云。 红色表示查询扫描，蓝色表示数据库中的经验。 与全局坐标（即，世界坐标，顶行）中的视图不同，测量在局部坐标（即，传感器坐标，底行）中看起来不同。 另外，请注意，两次扫描中都存在许多动态对象。

2. 外部因素：与视觉领域的光照变化 (短期变化) 和天气变化 (长期变化) 类似，结构可能在短期内通过动态对象的遮挡，在长期内通过建造或拆除造成的永久性的结构改变来经历类似的变化。当我们部署机器人进行长期导航时，这种外部因素变得至关重要。

3. 传感器特性：最后一个因素，传感器特性，也许更适合于距离传感器。与相机获取的高度结构化的传感器数据不同，LiDAR 点云是非结构化的，感知会根据传感器的规格 (例如，范围、线数和依赖于视场 (FOV) 的点云分辨率) 发生巨大的改变。因此，一个通用的位置识别系统应该不受传感器规格的限制。

C. 概述

本文中提出方法由两部分组成：(i) 位置描述和 (ii) 位置识别。整个流程如图 2 所示。位置识别模块包括位置检索、半度量定位和验证。在接下来的两节中，我们将详细介绍每个模块。

图2

整体框架。 给定原始范围测量，所提出的方法从地图中的一组地点中寻找相应的地点索引。

在这一部分中，我们描述了一种新的空间描述子 — Scan Context 描述子 (SCD)。该工作流首先将原始测量数据分区，然后使用鸟瞰图视角 (BEV) 将其投影到离散的 bin 中。当划分到 BEV bin 中时，考虑两种类型的垂直基底 (极坐标和笛卡尔坐标)。在分区和坐标选择之后，使用二进制编码函数将测量的子集编码到其关联的离散化 bin。如上所述，本文提出的位置识别模块的不变性源于 bin 编码函数和距离函数。

A. 动机

我们的描述子和搜索引擎强烈地受到城市环境中的重新访问模式的推动。我们发现了由于车辆的非完整运动遵循交通规则 (例如，车道保持) 导致的典型的模式。车辆主要运动是局部二维的，并且运动发生在最多两个可能不相交的方向上。这些典型的模式推动了极坐标和笛卡尔坐标的选择，以及相关的匹配算法。

B. 描述子轴和分辨率

我们假设输入是 3D LiDAR 的单次扫描结果。生成描述子的第一阶段是在感兴趣区域 (ROI) 内划分下采样后的点云。ROI 的上界和分区分辨率决定了 SCD 的格式。给定分区后的原始测量值，我们将它们投影到 2D 描述子空间上；即，该方法首先 (i) 将每个 3D 点投影到 2D 点，(ii) 在极坐标或笛卡尔坐标中对 2D 点进行参数化，以及 (iii) 通过离散 2D 空间来获得每个 bin 的标量值 (详细信息见 IV-C )。

如图 2 所示，我们将水平轴命名为对齐轴 (A轴) ，将垂直轴命名为检索轴 (R轴)。沿 A 轴的变化对应于列方向的移动；因此，沿 A 轴的预对齐将允许我们推断出粗略的度量级相对位姿，克服了相应的方向的变化。对齐/检索轴的选择决定了 SCD 的类型，即 Polar Context (PC) 和 Cart Context (CC)。

1. 极坐标：如我们前面的工作 [1] 所介绍的，PC 采用以方位角 $\theta$ 为 A 轴、以半径 r 为 R 轴的极坐标。由于方位角在 A 轴上，因此 PC 对旋转变化具有很强的鲁棒性
2. 笛卡尔坐标：CC 利用笛卡尔坐标，以横向 ($y$) 作为 A 轴。纵向 (或行进方向，$x$) 为R轴。自然，描述子对横向平移具有不变性。
3. 描述子分辨率：轴的分辨率决定了描述子的分辨率，它是我们所提出方法的用户参数。用户参数表示为

$$({\Delta }_R,{\Delta }_A,[R_{min},R_{max}],[A_{min},A_{max}])\text{\hspace{1em}(1)}$$

其中每个分量表示了由 R 轴的分辨率、A 轴的分辨率、R 轴的范围和 A 轴的范围组成的有序集合。样本参数集及其 SCD 如图 3(b) 所示。正如将在 VIII-A 中讨论的，粗略的离散化隐式地减少了动态对象、局部结构噪声和计算代价的影响。

图3

(a) 样本点云和 (b) 相关的 SCD。 在 (a) 中，黄色和灰色填充的实体分别描绘了 PC 和 CC 的 bin。 红色箭头表示对齐轴。 绿色箭头代表检索轴。 在 (b) 中，每个 bin 颜色表示 bin 中的最大高度； 红色高（例如 10 m），蓝色低（例如 0 m）。 在（b）中，PC（顶部）具有参数（20, 60, [0, 80] m, [0, 360]◦），CC（底部）具有参数（40, 40, [-100 , 100] 米, [-40, 40] 米)。

4. 输入模式的独立性：分区独立于测量值的分布或数据类型 (例如，BEV图像、体素或 3D 点)。因此，我们的描述子对于距离范围测量值都是通用的。通过在 IV-C 中选择适当的 bin 编码函数，描述子表示不仅可以处理 3D 点云，而且还可以处理其他距离传感器，例如 radar[34]。

C. Bin 编码函数

我们将由对齐轴和检索轴划分的单个不相交的部分表示为 bin。单个 bin 包括机器人传感器测量 ($Z_{ij}\in Z$) 的子集，其中 $i$ 和 $j$ 分别表示 A 轴和 R 轴索引。当没有范围数据落入 bin 中时，bin可以是空的，$Z_{ij}=\varnothing$，在这种情况下，我们为该 bin 赋值 0。

对于 $bin(i，j)$ 的每个测量子集 $Z_{ij}$，我们使用 bin 编码函数 $\psi (\cdot )$ 来分配代表值。bin 编码函数应该能够封装原始数据的子集，以便使描述子可辨别并且对干扰 (表I) 具有鲁棒性。

要求 1。bin 编码函数 $\psi :Z_{ij}\to R$ 对内部因素具有不变性，而且与传感器规格无关。

在我们以前的工作 [1] 的基础上，我们建议指定使用一个 bin 内 3D 点的最大高度。这种选择背后的直觉源于一个被称为 isovist 的城市规划概念[40，41]。在这个概念中，最大可见的结构及其可见体积的多边形形状决定了一个地方的使用，使一个地方变得可以区分。聚焦于最大高度而不是结构形状，消除了由传感分辨率、距离和物体尺寸引起的稀疏性变化。值得注意的是，满足上述要求的任何其他函数都可以用作编码函数。以 FMCW radar [34] 为例，使用了原始 radar 的强度值。我们之前工作的一些后续研究 [1] 利用了 Li DAR 的强度[42]、内插强度 [34] 和三维点的高度差 [10]。我们注意到在建图器和定位器不同的情况下 (例如，LiDAR 的安装高度不同)，异类 LiDAR 的位置识别问题超出了本文的范围，因为它不符合上述要求。

D. Scan Context 描述子

在 ROI 划分 (IV-B) 和 bin 编码 (IV-C) 之后，每个 bin 包含 bin 内数据的j具有代表性特征概括 (即,最大高度)。我们将这些 bin 值累加成矩阵形式，以完成位置的 2D 描述子；矩阵的行和列对应于检索轴和对齐轴。由此得到的描述子可以理解为周围结构的天际线的轮廓。根据坐标选择，我们将生成的 2D 描述子命名为 Polar Context (PC) 或 Scan Context (CC)。

1. Polar Context (PC)：当使用极坐标 ROI 时，我们将得到的 SCD 命名为PC。PC 被设计用于旋转不变的位置识别 (例如，反向重新访问)，因为旋转变化对应于列偏移。

2. Cart Context (CC)：类似地，使用笛卡尔 ROI 划分产生称为 CC 的 SCD。在 CC 中，横向平移反映为列偏移；因此 CC 可以处理横向变化，包括当车道更改时重新访问。

每一个 SCD 在应对内部因素方面都有自己的不变性。PC 和 CC 各处理 A 轴的一个维度，并且当旋转和平移同时发生时可能受到限制。为了应对这一问题，我们建议 hallucinating R 轴，以实现两个方向的鲁棒性 (V-D)。

E. SCD 之间的距离

接下来，我们通过对应的的 SCD的 相似度分数来定义两个位置之间的接近程度。

1. 对齐分数：如图 4 所示，如果从同一位置获取两个 SCD，则两个描述子应在矩阵中包含一致的内容，但可能表现出列顺序不同。因此，为了衡量相似性，我们应该使用两个描述子之间的余弦相似性来检查列范围共现项的总和。这种逐列比较对于动态对象或分区噪声特别有效。余弦距离用于计算在相同列索引 $j$ 处的两个列向量 $C_Q^j$ 和 $C_M^j$ 之间的距离。

$$d({f\text{f}f}_Q,{f\text{f}f}_M)=\frac{1}{N_A}\sum _{j=1}^{N_A}(1-\frac{c}{||c_Q^j|||||c_M^j|}$$