D. Galvez-López and J. D. Tardos, “Bags of Binary Words for Fast Place Recognition in Image Sequences,” in IEEE Transactions on Robotics, vol. 28, no. 5, pp. 1188-1197, Oct. 2012, doi: 10.1109/TRO.2012.2197158.

摘要

我们提出了一种使用从 FAST+BRIEF 特征中获得的词袋进行视觉位置识别的新方法。我们第一次构建了一个离散化二进制描述符空间的词汇树，并使用该树来加速几何验证的对应关系。我们使用完全相同的词汇和设置，在非常不同的数据集中呈现没有错误的优胜结果。包括特征提取在内的整个技术在包含 26300 张图像的序列中每帧需要 22ms，比以前的方法快一个数量级。

索引词——地点识别、词袋、SLAM、计算机视觉。

一、介绍

视觉 SLAM（同时定位和地图构建）最重要的要求之一是鲁棒的位置识别。经过一段探索期后，当重新观察长期未观察到的区域时，标准匹配算法就会失败。当它们被稳健地检测到时，闭环提供正确的数据关联以获得一致的地图。由于突然运动、严重遮挡或运动模糊等原因，可以使用与循环检测相同的方法进行机器人在轨道丢失后的重新定位。在 [1] 中，我们得出结论，对于小型环境，map-to-image 方法可以实现良好的性能，但对于大型环境，image-to-image（或基于外观的）方法（如 FAB-MAP [2]）可以更好地扩展。基本技术包括从机器人在线收集的图像中建立一个数据库，以便在获取新图像时可以检索到最相似的图像。如果它们足够相似，则检测到闭环。

近年来，出现了许多利用这一思想的算法[2]-[6]，基于将它们作为词袋空间中的数值向量进行比较来进行图像匹配[7]。词袋导致非常有效和快速的图像匹配器[8]，但它们并不是闭环的完美解决方案，主要是由于感知混叠[6]。出于这个原因，稍后通过检查匹配图像在几何上是否一致来执行验证步骤，这需要特征对应。闭环算法的瓶颈通常是特征的提取，这在计算周期上是其余步骤的十倍左右。这可能会导致 SLAM 算法在两个解耦线程中运行：一个执行主要的 SLAM 功能，另一个仅用于检测闭环，如 [5] 中所示。

在本文中，我们提出了一种新的算法来检测循环并实时建立图像之间的点对应关系，使用传统的CPU 和单个摄像头。 我们的方法基于词袋和几何检查，有几个重要的新颖性使其比当前方法快得多。如第 III 节所述，主要的速度改进来自使用带有 FAST 关键点 [10] 的简要描述符 [9] 的略微修改版本。 Brief 描述子是一个二进制向量，其中每个位是关键点周围给定像素对之间强度比较的结果。虽然BRIEF 描述子几乎是不变的。为了缩放和旋转，我们的实验表明它们对于平面相机运动的闭环非常稳健，这是移动机器人中的常见情况，在独特性和计算时间之间提供了很好的折衷。

我们引入了一个离散二进制空间的词袋，并用一个直接索引来扩充它，除了通常的逆索引，如第 IV 节所述。据我们所知，这是第一次使用二进制词汇表进行循环检测。逆索引用于快速检索可能与给定图像相似的图像。我们展示了直接索引的一种新颖用途，可以有效地获取图像之间的点对应关系，从而加快循环验证期间的几何检查。

完整的循环检测算法在第 V 节中详细介绍。与我们之前的工作 [5,6] 类似，为了确定闭环，我们验证获得的图像匹配的时间一致性。本文的一个新颖之处是一种防止在同一地点收集的图像在查询数据库时相互竞争的技术。我们通过将匹配期间描绘同一地点的那些图像组合在一起来实现这一点。

第六节包含对我们工作的实验评估，包括对我们算法中不同部分的相对优点的详细分析。我们比较了 Brief 的有效性和两个版本的 SURF 特征 [11]，最常用于闭环的描述子。我们还分析了循环验证的时间和几何一致性测试的性能。在对 5 个 0.7-4 公里长轨迹的公共数据集进行评估后，我们最终展示了我们的技术所取得的结果。实验证明我们可以在 520 毫秒内对 26300 张图像（平均 22 毫秒）运行整个循环检测过程，包括特征提取，比以前的技术高出一个数量级以上。

[12] 中介绍了这项工作的初步版本。在当前的论文中，我们增强了直接索引技术并扩展了我们方法的实验评估。我们还报告了新数据集的结果，并与最先进的 FABMAP 2.0 算法 [13] 进行了比较。

二、相关工作

基于外观的位置识别由于取得了优异的成绩而在机器人界获得了极大的关注[4,5,13,​​14]。这方面的一个例子是 FAB-MAP 系统 [13]，它使用全向摄像头检测环路，在 70 公里和 1000 公里长的轨迹中获得 48.4% 和 3.1% 的召回率，没有误报。 FAB-MAP 用一袋单词表示图像，并使用 Chow Liu 树离线学习单词的共可见概率。 FAB-MAP 已成为环路检测的黄金标准，但当图像长时间描绘非常相似的结构时，其鲁棒性会降低，使用前置摄像头时可能会出现这种情况 [5]。在 Angeli 等人的工作中。 [4]，以增量方式在线创建了两个视觉词汇表（外观和颜色）。这两个词袋表示一起用作贝叶斯滤波器的输入，该滤波器估计两个图像之间的匹配概率，同时考虑到先前案例的匹配概率。与这些概率方法相比，我们依靠时间一致性检查来考虑先前的匹配并提高检测的可靠性。 这种技术在我们之前的工作中已经证明是成功的 [5,6]。我们的工作与上述工作的不同之处还在于，我们首次使用了一袋二进制词，并提出了一种技术来防止及时收集并描绘同一地点的图像在匹配过程中相互竞争，以便我们可以工作在更高的频率。

为了验证闭环候选，通常执行几何检查。我们将极线约束应用于 [4] 中所做的最佳匹配候选，但我们利用直接索引来更快地计算对应点。 Konolige 等人 [3] 使用带有立体相机的视觉里程计来实时创建环境视图地图，并使用词袋方法检测闭环。他们的几何检查包括计算匹配图像之间的空间变换。但是，他们不考虑与先前匹配的一致性，这导致他们将几何检查应用于几个循环关闭候选者。

在大多数闭环作品 [4]-[6,14] 中，使用的特征是 SIFT [15] 或 SURF [11]。它们很受欢迎，因为它们不受光照、比例和旋转变化的影响，并且在轻微的透视变化时表现出良好的行为。 然而，正如上述出版物所报道的，这些特征通常需要 100 到 700 毫秒来计算。除了 GPU 实现 [16]，还有其他类似的功能试图通过例如逼近 SIFT 描述符 [17] 或降低维度 [18] 来减少计算时间。 Konolige 等人的工作[3] 提供了质的变化，因为它使用紧凑的随机树签名 [19]。这种方法计算图像块与之前在离线阶段训练的其他块之间的相似度。通过连接这些相似值来计算补丁的描述符向量，并最终通过随机正射投影降低其维数。这产生了一个非常快速的描述符，适用于实时应用程序[19]。我们的工作与 [3] 的相似之处在于我们还通过使用高效的特性来减少执行时间。简述描述符以及其他最近的描述符如 BRISK [20] 或 ORB [21] 是二进制的，需要很少的时间来计算。作为一个优势，它们的信息非常紧凑，因此它们占用的内存更少，比较起来也更快。这允许更快地转换到词袋空间。

三、二进制特征

在比较图像时，就计算时间而言，提取局部特征（关键点及其描述符向量）通常非常昂贵。当这些技术应用于实时场景时，这通常是瓶颈。为了克服这个问题，在这项工作中，我们使用 FAST 关键点 [10] 和最先进的Brief描述符 [9]。 FAST 关键点是通过比较半径为 3 的 Bresenham 圆中的一些像素的灰度强度来检测的角状点。由于只检查了几个像素，因此这些点非常快地获得证明对于实时应用来说是成功的。

对于每个 FAST 关键点，我们在它们周围绘制一个正方形补丁并计算一个Brief描述符。图像块的Brief描述符是二进制向量，其中每个位是块的两个像素之间的强度比较的结果。补丁先前使用高斯内核进行平滑以减少噪声。预先给定补丁的大小 Sb，在离线阶段随机选择要测试的像素对。除了 Sb 之外，我们还必须设置参数 Lb：要执行的测试次数（即描述符的长度）。对于图像中的点 p，其简要描述向量 B§ 由下式给出：

测试点 ai 和 bi 根据正态分布 N (0, 1 25 S2b )。然而，我们发现使用紧密的测试对会产生更好的结果 [12]。我们通过对分布 aj i∼ N (0, 1 25 S2b ) 和 bj i∼ N (aj i , 4 625 S2b ) 进行采样来选择这些对中的每个坐标 j。请注意，[9] 也提出了这种方法，但没有在他们的最终实验中使用。对于描述符长度和补丁大小，我们选择 Lb = 256 和 Sb = 48，因为它们在独特性和计算时间之间取得了很好的折衷 [12]。

Brief 描述符的主要优点是它们的计算速度非常快（Calonder 等人 [9] 报告了当 Lb = 256 位时每个关键点需要 17.3µs）和比较。由于这些描述符中的一个只是位向量，因此可以通过计算它们之间的不同位的数量（汉明距离）来测量两个向量之间的距离，这是通过异或运算实现的。 在这种情况下，这比计算欧几里得距离更合适，就像通常使用 SIFT 或 SURF 描述符所做的那样，由浮动点值组成。

四、图像数据库

为了检测重新访问的地方，我们使用了一个由单词分层包 [7,8] 和直接和反向索引组成的图像数据库，如图 1 所示。

词袋是一种使用视觉词汇将图像转换为稀疏数字向量的技术，允许管理大量图像。通过将描述符空间离散化为 W 个视觉词来离线创建视觉词汇表。 与 SIFT 或 SURF 等其他特征不同，我们离散化二进制描述符空间，创建更紧凑的词汇表。在分层词袋的情况下，词汇表结构为树。为了构建它，我们从一些训练图像中提取了一组丰富的特征，独立于稍后在线处理的那些。提取的描述符首先通过使用 k-means++ 播种 [22] 执行 k-median 聚类离散成 kw 个二进制簇。导致非二进制值的中位数被截断为 0。这些簇形成词汇树中的第一级节点。通过使用与每个节点关联的描述符重复此操作来创建后续级别，最多 Lw 次。我们最终得到一棵有W叶的树，即词汇表中的单词。每个单词根据其在训练语料库中的相关性被赋予一个权重，从而降低那些非常频繁的单词的权重，从而降低判别力。为此，我们使用 [7] 提出的术语频率 - 逆文档频率 (tf-idf)。然后，为了将在时间 t 拍摄的图像 It 转换为词袋向量 vt∈ RW ，其特征的二进制描述符从根到叶子遍历树，在每个级别上，最小化汉明距离的中间节点。

为了测量两个词袋向量 v1 和 v2 之间的相似性，我们计算了一个 L1 分数 s(v1, v2)，其值位于 [0…1] 中：

除了词袋，还维护了一个逆索引。该结构为词汇表中的每个单词 wi 存储它出现的图像列表。这在查询数据库时非常有用，因为它只允许对那些与查询图像有一些共同词的图像进行比较。我们扩充逆索引以存储对 <It, vit> 以快速访问图像中单词的权重。逆索引在新图像添加到数据库时更新，并在数据库中搜索某些图像时访问。

这两种结构（词袋和反向索引）通常是词袋方法中用于搜索图像的唯一结构。然而，作为这种通用方法的新颖之处，我们还利用直接索引来方便地存储每个图像的特征。我们根据它们在树中的级别 l 来分离词汇表的节点，从叶子开始，级别 l = 0，到根结束， l = Lw。对于每个图像 It，我们在直接索引中存储作为 It 中存在的单词的祖先的级别 l 的节点，以及与每个节点相关联的局部特征 ftj 的列表。我们利用直接索引和词袋树将它们用作在Brief描述符空间中逼近最近邻的一种方法。直接索引允许通过仅计算属于相同单词的那些特征之间的对应关系来加速几何验证，或者与在级别 l 具有共同祖先的单词之间的对应关系。直接索引在向数据库添加新图像时更新，并在获得候选匹配并且需要进行几何检查时访问。

五、回环检测算法

为了检测闭环，我们使用了一种基于我们之前工作 [5,6] 的方法，该方法遵循接下来详述的四个阶段。

A. 数据库查询

我们使用图像数据库来存储和检索与任何给定图像相似的图像。 当获取最后一张图像时，将其转换为词袋向量 vt。在数据库中搜索 vt，得到匹配的候选列表 < vt, vt1 >, < vt, vt2 > ，与他们的分数 s(vt, vtj ) 相关联。这些分数的变化范围很大程度上取决于查询图像及其包含的单词的分布。然后，我们用我们期望在该序列中为向量 vt 获得的最佳分数对这些分数进行归一化，获得归一化的相似度分数η [6]：

在这里，我们用 s(vt, vt−Δt) 来近似 vt 的预期分数，其中 vt−Δt 是前一张图像的词袋向量。那些 s(vt, vt−Δt) 很小的情况（例如，当机器人转动时）可能会错误地导致高分。因此，我们跳过未达到最小值 s(vt, vt−Δt) 或所需特征数量的图像。这个最小分数权衡了可用于检测循环的图像数量与结果分数η的正确性。我们使用一个较小的值来防止有效图像被丢弃。然后我们拒绝那些 η(vt, vtj ) 没有达到最小阈值的匹配，记为α。

B. 匹配分组

为了防止在查询数据库时时间相近的图像相互竞争，我们将它们分组为孤岛，并将它们视为只有一个匹配。我们使用符号 Ti 来表示由时间戳 tni 组成的区间。 . . 、 tmi 和 VTi 用于将匹配项与条目 vtni 、 . 组合在一起的岛。 . . , vtmi 。因此，有几个匹配 < vt, vtni >, . . . , < vt, vtmi > 如果在 tni , . . . , tmi 很小。这些岛屿也根据分数 H 进行排名：

选择得分最高的岛作为匹配组并继续进行时间一致性步骤。除了避免连续图像之间的冲突外，这些岛屿还可以帮助建立正确的匹配。如果 It 和 It’ 代表一个真正的闭环，它很可能也类似于 It’±Δt, It’±2Δt, 。 . . ，产生长岛。由于我们将 H 定义为分数 η 的总和，因此 H 分数也有利于与长岛匹配。

C. 时间一致性

在获得最佳匹配岛 VT’ 后，我们检查它与先前查询的时间一致性。在本文中，我们将 [5,6] 中应用的时间约束扩展到支持岛屿。匹配 < vt, VT′ > 必须与 k 个之前的匹配 < vt−Δt, VT1 >, 一致。 . . , < vt−kΔt, VTk >，使得区间 Tj 和 Tj+1 接近重叠。如果一个岛通过了时间约束，我们只保留匹配< vt, vt′ >，对于使分数η最大化的t′∈T′，并认为它是一个闭环候选，它必须最终被几何验证阶段接受。

D. 有效的几何一致性

我们在闭环候选的任何一对图像之间应用几何检查。该检查包括使用 RANSAC 查找 It 和 It’ 之间的基本矩阵，该矩阵由至少 12 个对应关系支持。为了计算这些对应关系，我们必须将查询图像的局部特征与匹配图像的局部特征进行比较。有几种方法可以进行这种比较。最简单和最慢的一种是穷举搜索，它包括在描述符空间中测量 It 的每个特征与 It’ 的特征的距离，以便稍后根据最近邻距离比 [15] 策略选择对应关系。这是每张图像特征数量的aΘ(n2) 操作。第二种技术包括通过在 k-d 树中排列描述符向量来计算近似最近邻居 [27]。

遵循后一种想法，我们利用我们的词袋词汇表并重用它来近似最近的邻居。出于这个原因，当将图像添加到数据库时，我们将节点和特征对的列表存储在直接索引中。为了获得 It 和 It’ 之间的对应关系，我们在直接索引中查找 It’ 并仅在与词汇树中 l 级相同节点相关联的那些特征之间进行比较。这个条件加快了对应计算。参数 l 是预先固定的，需要在 It 和 It’ 之间获得的对应关系的数量和为此目的所消耗的时间之间进行权衡。当 l = 0 时，只比较属于同一个词的特征（如我们在 [12] 中提出的），这样可以实现最高的加速，但可以获得更少的对应关系。由于缺少对应点，一些正确的循环被拒绝，这使得整个循环检测过程的召回率降低。在另一方面，当 l = Lw 时，召回不受影响，但执行时间也没有提高。

我们只需要基本矩阵进行验证，但请注意，在计算它之后，我们可以提供与将在下面运行的任何 SLAM 算法匹配的图像之间的数据关联，而无需额外成本。

六、实验评估

我们在以下部分评估我们提案的不同方面。在 VI-A 中，我们介绍了评估算法所遵循的方法。接下来，我们在 VI-B 系统中比较了 Brief 和 SURF 的可靠性。在 VI-C 中，我们分析算法的时间一致性的影响，在 VI-D 中，我们基于直接索引检查几何验证的效率。最后，我们在 VI-E 和 VI-F 中评估了我们整个系统的执行时间和性能。

A.方法论

评估环路检测结果的方面通常被假定为具有一般知识。然而，文献中几乎没有给出细节。在这里，我们解释了我们评估系统所遵循的方法。

1. 数据集：我们在五个公开可用的数据集中测试了我们的系统（见表 I）。这些呈现独立的室内和室外环境，并由多个平台以不同的速度收集，具有平面内的相机运动。 CityCentre 是以低频收集的图像集合，几乎没有重叠。其他的以高频（8-20 Hz）提供图像。

2. 基本事实：为了衡量我们结果的正确性，我们将它们与基本事实参考进行比较。这里使用的大多数数据集都没有提供有关闭环的直接信息，因此我们手动创建了实际闭环的列表。该列表由时间间隔组成，其中列表中的每个条目编码与匹配间隔关联的查询间隔。

3. 正确性度量：我们用准确率和召回率来衡量循环检测结果的正确性。准确率定义为正确检测的数量与所有触发的检测之间的比率，而召回率定义为正确检测与真实情况中所有闭环事件之间的比率。闭环检测器触发的匹配是一对查询和匹配时间戳。为了检查它是否为真阳性，在基本事实中搜索包含这些时间戳的间隔。基础实况中的闭环事件数计算为基础实况中所有查询间隔的长度乘以处理数据集图像的频率。当由于多次遍历而使查询时间戳与基本事实中的多个匹配时间戳相关联时，仅考虑其中一个来计算闭环事件的数量。

4. 统参数的选择：根据评估数据调整系统参数是常见的做法，但我们认为使用不同的数据来选择我们的算法配置并对其进行评估证明了我们方法的鲁棒性。 然后我们将表 I 中显示的数据集分成两组。我们使用其中三个存在许多困难的异构环境（NewCollege、Bicocca25b 和 Ford2）作为训练数据集，以找到我们算法的最佳参数集。其他两个数据集（CityCentre 和 Malaga6L）用作评估数据来验证我们的最终配置。在这些情况下，我们仅将我们的算法用作具有预定义配置的黑盒。

5. 设置：我们的算法在所有实验中都使用相同的设置。相同的词汇树用于处理所有数据集。这是用 kw = 10 个分支和 Lw = 6 个深度级别构建的，产生一百万个单词，并使用从独立数据集的 10K 图像中获取的 9M 特征进行训练（Bovisa 2008-09-01 [24]）。我们在 FAST 的响应函数中使用了 10 个单位的阈值，在 SURF 的 Hessian 响应中使用了 500 个单位。对于每个处理过的图像，我们只保留了响应最高的 300 个特征。

B. 描述符有效性

Brief 描述符比 SURF 描述符编码的信息少得多，因为 Brief 不是尺度或旋转不变的。 为了检查BRIEF是否足够可靠以执行闭环检测，我们将其有效性与SURF进行了比较。我们选择了两个版本的 SURF 特征：具有旋转不变性的 64 维描述符（SURF64）和不具有旋转不变性的 128 维描述符（U-SURF128）。我们之所以选择它们，是因为它们是解决闭环检测问题的常用选择 [5,13]。

我们为 SURF64 和 U-SURF128 创建词汇树的方式与为 Brief 构建的方式相同，并在 Bicocca25b 和 NewCollege 上运行我们的系统，以 f = 2 Hz 处理图像序列。我们停用了几何验证，将所需的时间一致性匹配 k 固定为 3，并改变归一化相似度阈值α的值以获得图 2 所示的精确召回曲线。第一点是 SURF64 的曲线优于 U 的曲线-SURF128 在两个数据集上。我们还可以看到，与 SURF 相比，BRIEF 提供了非常出色的性能。在 Bicocca25b 中，BRIEF 优于 U-SURF128，略好于 SURF64。在 NewCollege 中，SURF64 取得了比BRIEF 更好的结果，但BRIEF 仍然提供了非常好的准确率和召回率。


为了更好地说明 Brief 和 SURF64 寻找对应关系的不同能力，我们从之前的实验中选择了一些循环事件。在图 3 中，与我们词汇表中相同单词相关联的特征用线条连接起来。这些是计算归一化相似度得分时考虑的唯一匹配。在大多数情况下，BRIEF 获得与 SURF64 一样多的正确单词对应，尽管有轻微的透视变化，如第一个示例（第一行）所示。在第二个例子中，只有 Brief 能够关闭闭环，因为 SURF64 没有获得足够的词对应。这两个示例表明，BRIEF 在中距离或远距离的对象中找到对应关系，例如墙上的标志或背景中的树木。一般来说，遥远的物体存在于我们数据集的大部分图像中。由于从远处物体中提取的关键点的尺度几乎没有变化，BRIEF 适合匹配它们的补丁。在物体靠近相机的情况下，SURF64 更适合，因为它对尺度变化的不变性。但是，我们观察到发生这种情况的案例很少。在图 3 的第三个示例中，相机倾斜，使图像在某些区域出现旋转。这与比例变化一起阻止了BRIEF 获得单词对应。在这种情况下，SURF64 克服了这些困难并检测到了环路。

我们的结果表明，对于平面内相机运动的闭环检测问题，具有简要描述符的 FAST 特征几乎与 SURF 特征一样可靠。作为优势，它们不仅获取速度快得多（每张图像 13 毫秒而不是 100-400 毫秒），而且占用内存更少（存储 1M 单词词汇表时使用 32MB 而不是 256MB）并且比较速度更快，加快了使用速度的层次词汇。

C.时间一致性

选择特征后，我们测试了接受闭环候选所需的时间一致匹配的数量 k。为此，我们在 f = 2 Hz 的训练数据集中运行我们的系统，针对 k 和 α 的几个值，并且没有任何几何约束。我们测试了 k 值在 0（即禁用时间一致性）和 4 之间的值。我们观察到所有工作频率的 k = 0 和 k > 0 之间有很大的改进。随着 k 的增加，以 100% 的准确率获得更高的召回率，但这种行为不适用于非常高的 k 值，因为只会找到非常长的闭包。我们选择 k = 3，因为它在三个训练数据集中表现出良好的准确召回平衡。我们在 Bicocca25b 中针对频率 f = 1 和 3 Hz 重复了这个测试，以检查参数 k 对处理频率的依赖程度。我们在图 4 中显示了通过改变参数α 在 Bicocca25b 中获得的准确召回曲线；为清楚起见，仅显示了 k = 0 和 3。这表明时间一致性是避免不匹配的一种有价值的机制，如先前在 [12] 中所见。我们还可以看到，即使对于不同的频率值，k = 3 也表现良好，因此我们可以认为这个参数是稳定的。

D. 几何一致性

根据图 4，我们可以选择一个限制性的α 值来获得 100% 的精度，但这需要为每个数据集调整这个参数。相反，我们设置一个通用值并验证与几何约束的匹配，该几何约束包括在两个图像It和It’之间寻找闭环候选的基本矩阵。计算It和It’之间的对应点是这个阶段最耗时的步骤。我们将使用直接索引来计算对应关系的提议（即 DIl）与穷举搜索和基于 Flann 的方法 [27] 进行了比较。参数 l 代表词汇树中检查祖先节点的级别。在 Flann 方法中，Flann 库 [27]（在 OpenCV 库中实现）用于构建一组具有 It 的特征描述符的 kd-trees。这允许为 It’ 的描述符获得 It 中的近似最近邻居。在使用这些方法中的任何一种计算距离后，应用最近邻距离比，阈值为 0.6 个单位。尽管 Flann 和词汇树方法都可用于近似最近邻，但它们在概念上有所不同：我们的词汇树是使用训练数据创建的，因此邻域搜索基于独立数据，而 kd-trees 是针对每个It’。


我们以 f = 2 Hz, k = 3,α = 0.3 运行 NewCollege 数据集中的每种方法。我们选择这个数据集是因为它呈现了最长的重访轨迹和许多感知混叠情况。在表 II 中，我们显示了每个查询的几何检查的执行时间，以及每种情况下循环检测器的召回。在所有情况下，精确度都是 100%。时间包括对应点的计算、RANSAC 循环和基本矩阵的计算。当达到最大RANSAC迭代次数时，获得所有方法的最高执行时间。穷举搜索比其他近似方法实现更高的召回率，但也表现出最高的执行时间。我们看到 Flann 方法花费的时间几乎与穷举搜索方法一样长。计算对应关系时获得的加速不值得为每个图像构建一个 Flann 结构的成本。另一方面，DI0 的执行时间最短，但召回级别最低。正如我们之前注意到的[12]，当词汇量很大（一百万个单词）时，仅从属于同一单词的特征中选择对应关系是非常严格的。我们最终选择了方法 DI2 进行几何检查，因为它在召回和执行时间之间取得了很好的平衡。


E. 执行时间

为了测量执行时间，我们在 NewCollege 数据集中运行我们的系统，其中 k = 3，α = 0.3 和 DI2。通过将工作频率设置为 f = 2 Hz，总共处理了 5266 张图像，平均每张图像的系统执行时间为 16 毫秒，峰值小于 38 毫秒。但是，为了测试系统的可扩展性，我们将频率设置为 f = 10 Hz，得到 26292图片。即使 k = 3，系统也没有产生误报。这表明时间一致性参数 k 的行为即使对于高频也是稳定的。

在这种情况下，每个图像消耗的执行时间如图 5 所示。这是在 Intel Core i7 @ 2.67GHz 机器上测量的。我们还在表 III 中显示了这个数量的图像每个阶段所需的时间。特征时间包括计算 FAST 关键点并在有太多时移除具有低角响应的那些，以及使用高斯核平滑图像和计算简要描述符。 bag-of-words时间分为四个步骤：将图像特征转换为bagof-words向量、数据库查询检索相似图像、岛的创建和匹配以及将当前图像插入数据库（这还涉及更新直接和反向索引）。验证时间包括通过直接索引计算匹配图像之间的对应关系，以及计算基本矩阵的 RANSAC 循环。

我们看到所有步骤都非常快，包括提取特征和维护正反索引。这允许获得每张图像以 22 毫秒运行的系统，峰值小于 52 毫秒。特征提取阶段的执行时间最长；其中大部分是由于功能太多而产生的开销，因此必须考虑最好的 300 个。即便如此，相对于其他特征（例如 SIFT 或 SURF），我们已经实现了超过一个数量级的减少，从而消除了这些回环检测算法的瓶颈。在词袋阶段，管理岛屿和索引所需的时间可以忽略不计，将图像特征转换为词袋向量所需的时间与数据库查询的时间一样长。它的执行时间取决于特征的数量和词汇的大小。我们可以通过使用较小的词汇来减少它，因为我们使用的是相对较大的词汇（1M 单词，而不是 10-60K [5,14]）。但是，我们发现大词汇表会产生与单词相关的更稀疏的逆索引。因此，查询时，只需遍历较少的数据库条目即可获得结果。查询时显着减少了执行时间，到目前为止，转换新图像所需的时间。我们得出结论，在使用大型图像集合时，大词汇表可以提高计算时间。此外，请注意，查询包含超过 26K 图像的数据库仅需要 9 毫秒，这表明此步骤可以很好地扩展数万张图像。几何验证在最坏的情况下表现出很长的执行时间，但正如我们在上一节中看到的，这种情况很少发生，而 75% 的情况需要不到 1.6 毫秒。


我们的结果表明，我们可以在 52 毫秒（平均 22 毫秒）内可靠地检测针对 26K 图像的数据库的闭环。相对于基于 SIFT 或 SURF [4]-[6,13,14] 的算法所需的 300-700 毫秒，这代表了一个数量级的改进。 例如，最先进的算法 FAB-MAP 2.0 [13] 提取 SURF 需要 423 毫秒，转换成词袋需要 60 毫秒，针对 25K 图像检索匹配候选者需要 10 毫秒，而 RANSAC 需要 120 毫秒（最坏情况）几何验证。 我们的算法也优于 Konolige 等人开发的极其高效的环路检测器。 [3]，基于紧凑的随机树签名。根据他们的图 6，该方法需要大约 300 毫秒才能对具有 4K 图像的数据库执行完整的循环检测。

F. 最终系统的性能

在前面的部分中，我们展示了系统参数对结果正确性的影响。对于我们的算法，我们选择了通用参数 k = 3，α = 0.3，以及用于计算对应关系的 DI2 方法，因为它们在训练数据集中的多种环境下被证明是有效的。表IV中显示了算法参数和词汇表的摘要。在图 6 中，我们展示了使用这些参数在这些数据集中获得的精确召回曲线，处理 f = 2 Hz 的序列。在表 V 中，我们展示了具有最终配置的曲线图。我们在三个数据集中实现了高召回率，没有误报。


为了使用新数据集检查我们算法的可靠性，我们使用 Malaga6L 和 CityCentre 作为评估数据集。对于这些，我们使用我们的算法作为黑盒，上面给出了默认配置和相同的词汇表。对于 Malaga6L，我们以 f = 2 Hz 的频率处理序列，对于 CityCentre，我们使用了所有图像，因为这些图像已经相距甚远。我们还将我们的算法与最先进的 FAB-MAP 2.0 算法 [13] 进行了比较，该算法默认配置为在其作者的网站上可用1。给定一个查询图像，FAB-MAP 返回一个向量，其概率为 p 与之前的某个图像位于同一位置。只有那些 p 高于阈值的匹配才会被接受。该参数必须由用户设置。我们选择 p≥ 98% 是因为它在这些数据集中显示了 100% 准确率的最高召回率。表 V 和表 VI 显示了评估数据集中的结果。为了公平起见，我们评论一下这种比较是如何进行的：FABMAP 2.0 软件默认情况下不对返回的匹配项应用任何几何约束，因此我们应用了与我们类似的验证阶段，包括通过穷举搜索计算基本矩阵方法。 FAB-MAP 2.0 的输入必须是一系列不相交的图像。对于 Malaga6L，我们给它提供了频率为 1 Hz 的图像。我们还尝试了 0.25 和 0.5 Hz，但 1 Hz 产生了更好的结果。对于 CityCentre，我们使用了所有可用的图像。最后，FAB-MAP 2.0 提供了 11K 个 128float 值的词表，由室外不相交的图像构建而成，而我们的词汇表包含 1M 个 256 位的词，由一系列图像创建。

如表 V 所示，我们的默认参数算法能够在两个评估数据集中实现大召回率而没有误报。我们的召回级别与 FAB-MAP 2.0 产生的召回级别相似，但执行时间较短。在 Malaga6L 数据集中，尽管有照明困难和视图深度，所有循环都是正确的。我们的方法和 FAB-MAP 2.0 在 CityCentre 中的结果不同，因为闭环图像之间的变化比其他数据集中的变化大。这阻碍了 DI2 技术的工作，因为特征通常更加明显，并且在词汇树的早期级别中被分开。请注意，这突出了 Brief 的小不变性，因为其他 SURF 可能能够在图像之间产生更多相似的特征。无论如何，我们看到我们的方法仍然能够在这个数据集中找到大量的循环事件。该测试表明，我们的方法可以在许多环境和情况下开箱即用，并且只要它们重叠，它就能够处理以低频或高频拍摄的图像序列。我们还可以指出，相同的词汇表足以处理所有数据集。这表明当词汇量足够大时，词汇的来源并不那么重要。

我们在图 7 中显示了每个数据集中检测到的循环，没有出现错误的检测。 NewCollege 中的轨迹基于部分校正的 GPS 数据，因此某些路径的描绘不准确。请注意，安装摄像头的车辆部分出现在 Ford2 的所有图像中；我们删除了它上面的功能。我们看到，检测到 55.92% 的循环事件就足以，例如，像 NewCollege 一样广泛覆盖长轨迹中的所有循环区域。在图 7 的右侧，我们展示了训练和评估数据集中正确循环检测的示例，以及最终对应的特征。这些例子使BRIEF描述符的有限尺度不变性变得明显。正如我们在第 VI-B 节中注意到的那样，大多数匹配的特征都是遥远的。 BRIEF 容忍的比例变化显示在 NewCollege 和 Bicocca25b 中靠近相机的对应关系中，以及 Malaga6L 中汽车上的对应关系中。然而，BRIEF 无法处理像 CityCentre 中汽车上产生的如此大规模的变化，其中所有的对应关系都是从远处的特征中获得的。另一方面，只要背景对象中的特征匹配，尽管有中等翻译，也可以检测到循环。这在 CityCentre 和 Ford2 中可见，车辆沿着道路的不同车道行驶。

七、结论

我们提出了一种新技术来检测单目序列中的环。我们工作的主要结论是二进制特征在词袋方法中非常有效且极其高效。 特别是，我们的结果表明，FAST+BRIEF 特征与 SURF（64 维或 128 维且无旋转不变性）一样可靠，用于解决移动机器人中常见的平面内摄像机运动的循环检测问题。执行时间和内存需求小了一个数量级，无需特殊硬件。

我们的建议的可靠性和效率已经在五个非常不同的公共数据集上得到证明，这些数据集描述了室内、室外、静态和动态环境，带有正面或侧面摄像头。与大多数以前的工作不同，为了避免过度调整，我们限制自己使用从独立数据集获得的相同词汇表和从一组训练数据集获得的相同参数配置来呈现所有结果，而无需查看评估数据集。因此，我们可以声称我们的系统在各种实际情况下都提供了强大而高效的性能，而无需任何额外的调整。

我们技术的主要限制是使用缺乏旋转和尺度不变性的特征。对于室内和城市机器人中的位置识别来说已经足够了，但对于全地形或飞行器、人形机器人、可穿戴相机或物体识别来说肯定是不够的。然而，我们对二元词袋方法有效性的演示为使用新的和有前途的二元特征（如 ORB [21] 或 BRISK [20]）铺平了道路，它们的计算时间优于 SIFT 和 SURF，保持旋转和尺度不变性。

作为对社区的最终贡献，我们算法的实现是在线公开的。