图像序列中快速地点识别的二进制词袋方法

文章：Bags of Binary Words for Fast Place Recognition in Image Sequences

作者：Dorian Galvez-L ´ opez and Juan D. Tard ´ os

编辑：点云PCL

欢迎各位加入知识星球，获取PDF论文，欢迎转发朋友圈。文章仅做学术分享，如有侵权联系删文。

公众号致力于点云处理，SLAM，三维视觉，高精地图等领域相关内容的干货分享，欢迎各位加入，有兴趣的可联系dianyunpcl@163.com。未经作者允许请勿转载，欢迎各位同学积极分享和交流。

摘要

本文提出了一种使用FAST+BRIEF特征的二进制词袋进行视觉地点识别的新方法，首次构建了一个离散化二进制描述子空间的词袋树，并使用该树加速对几何验证的对应关系。在非常不同的数据集中呈现了无误报的良好结果，使用完全相同的词袋和配置。整个技术，包括特征提取，在一个包含26300张图像的序列中每帧需要22ms，比以前的方法快一个数量级。

主要贡献

本文提出了一种新颖的算法，可以使用传统的CPU和单个相机实时检测循环并建立图像之间的点对应关系，该方法基于词袋和几何验证，具有几个重要的新颖性，使其比当前的方法快得多。主要的速度提升来自于使用稍微修改过的BRIEF描述子和FAST关键点的方法。

BRIEF描述子是一个二进制向量，其中每个位是关键点周围给定一对像素之间强度比较的结果，虽然BRIEF描述子几乎不具有尺度和旋转不变性，但我们的实验证明它们对于具有平面相机运动的闭环检测非常稳健，这是移动机器人的通常情况，提供了辨别性和计算时间之间的良好折衷。同时引入了一个离散化二进制空间的词袋，并增加了一个直接索引，除了通常的反向索引，据我们所知，这是首次使用二进制词袋表进行回环检测，反向索引用于快速检索与给定图像可能相似的图像，展示了一种新颖的使用直接索引来有效地获取图像之间的点对应关系的方法，在回环验证期间加快了几何检查的速度。

主要内容

二进制特征

在比较图像时，提取局部特征（关键点及其描述子向量）通常需要大量的计算时间，这经常成为实时场景应用这些技术时的瓶颈，为了解决这个问题，在本文中我们使用FAST关键点和最先进的BRIEF描述子，FAST关键点是通过比较半径为3的Bresenham圆周上一些像素的灰度强度来检测的类似角的点，由于只检查了少量的像素，这些点很容易获得，从而在实时应用中取得成功。对于每个FAST关键点，我们在它们周围绘制一个正方形区域并计算BRIEF描述子，图像区域的BRIEF描述子是一个二进制向量，其中每个位是正方形区域中两个像素之间的强度比较的结果，这些区域事先用高斯核进行平滑处理以减少噪声。对于图像中的点p，其BRIEF描述子向量B(p)由以下公式给出：

BRIEF描述子的主要优点是它们非常快速，且计算和比较的速度都非常快，由于这些描述子只是一组比特的向量，因此计算两个向量之间的距离可以通过计算它们之间的不同比特数（海明距离）来实现，这可以用异或运算来实现。这比使用由浮点值组成的SIFT或SURF描述子通常使用的欧几里得距离更合适。

图像数据库

为了检测重访地点，我们使用一个由分层词袋和直接索引以及反向索引组成的图像数据库，如图1所示。

图1，词袋树示例以及构成图像数据库的直接和反向索引，词袋词是树的叶节点，反向索引存储单词在它们出现的图像中的权重，直接索引存储图像的特征及其在词袋树某个层级上的关联节点。

图像数据库由分层词袋模型和直接和反向索引组成，用于检测重复访问的地点，如图1所示，词袋模型是一种技术，它使用视觉词袋将图像转换为稀疏数值向量，允许管理大量的图像，视觉词袋通过将描述子空间离散化为W个视觉词来离线创建，与其他特征（如SIFT或SURF）不同，本文离散化了一个二进制描述子空间，创建了一个更紧凑的词袋表，在分层词袋模型的情况下，词袋表结构化为一棵树，要构建它，我们从一些训练图像中提取丰富的特征，独立于之后在线处理的图像，首先将提取的描述子通过k-means++种子进行k-mean聚类，将其离散化为kw个二进制簇,结果为非二进制值的中位数被截断为0，这些簇形成了词袋树的第一层节点。通过对与每个节点关联的描述子进行此操作，重复进行多次以创建后续层，最终得到一棵具有W个叶子节点的树，它们是词袋表的单词。

回环检测算法

A. 数据库查询

使用图像数据库来存储和检索与任何给定图像相似的图像。当最后一个图像 It 被获取时，它被转换成词袋向量 vt，然后搜索数据库中的 vt，得到一系列匹配候选项，并与它们的得分 s(vt, vtj ) 相关联，这些得分的范围非常依赖于查询图像和它所包含的单词的分布，我们将这些分数与我们在此序列中期望获得的最佳分数进行归一化，得到归一化的相似度分数 η。

这里，我们用s（vt，vt−∆t）近似表示vt的预期分数，其中vt−∆t是上一图像的词袋向量，当s（vt，vt−∆t）较小（例如，当机器人正在转弯时）时，可能会错误地导致高分。因此，我们跳过那些未达到最小s（vt，vt−∆t）或所需特征数量的图像。该最小分数在检测环路的图像数量和结果分数η的正确性之间进行折衷。我们使用一个小值来防止有效图像被丢弃。然后，我们拒绝那些η（vt，vtj）未达到最小阈值α的匹配。

B. 匹配分组

为了防止在查询数据库时，接近时间的图像相互比较，我们将它们分组并将它们视为一次匹配，根据一个得分H进行排名：

C.时间一致性检查

在获得最佳匹配之后，对其进行与先前查询的时间一致性检查。

D. 高效的几何一致性检查

对于每一对可能的闭环候选图像对进行几何一致性检查，这个检查需要使用 RANSAC 算法在两个图像之间找到至少 12 个对应点支持的基础矩阵，为了计算这些对应点，必须比较查询图像的局部特征与匹配图像的局部特征，有几种方法可以执行此比较，最简单且最慢的方法是穷举搜索，它包括在描述子空间中测量值的每个特征与候选帧的特征的距离，然后根据最近邻距离比策略选择对应点。

实验

方案

评估回环检测结果的方面通常被认为是一般性知识，然而，文献中很少给出详细的说明，本文解释了用于评估系统的方案。

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

2）真值比较：这里使用的大多数数据集不直接提供关于回环闭合的信息，因此我们手动创建了一个实际环路闭合的列表，此列表由时间间隔组成，其中列表中的每个条目都编码了与匹配间隔相关联的查询间隔。

3）正确性度量：使用精确度和召回率度量回环检测结果的正确性，精确度定义为正确检测的数量与所有检测触发的数量之比，召回率定义为正确检测的数量与基本事实中所有回环事件的数量之比。

4）系统参数的选择：通常的做法是根据评估数据来调整系统参数，但我们认为使用不同的数据来选择算法的配置并对其进行评估可以展示我们方法的鲁棒性。因此，我们将表I中显示的数据集分成两组。我们使用其中三个具有许多困难的异构环境的数据集（NewCollege、Bicocca25b和Ford2）作为训练数据集，以找到我们算法的最佳参数集，另外两个数据集（CityCentre和Malaga6L）用作评估数据，以验证我们的最终配置。

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

描述子的有效性

BRIEF 描述子编码的信息比 SURF 描述子要少得多，因为 BRIEF 不具有尺度或旋转不变性，为了检查 BRIEF 是否足够可靠以执行循环检测，我们将其有效性与 SURF 进行了比较。选择了两个版本的 SURF 特征：具有旋转不变性的 64 维描述子（SURF64）和不具有旋转不变性的 128 维描述子（U-SURF128）。关闭了几何验证，将所需的时间一致匹配 k 设为 3，并改变了规范化相似度阈值 α 的值，以获得如图 2 所示的精确度-召回率曲线。

图2. 在训练数据集中，BRIEF、SURF64和U-SURF128在没有几何验证的情况下实现的精度-召回率曲线。

为了更好地说明BRIEF和SURF64发现对应点的不同能力，从先前的实验中选择了一些回环事件，在图3中，与我们的词汇表的相同单词相关联的特征用线连接起来。这些是唯一用于计算标准化相似度分数的匹配。在大多数情况下，尽管存在轻微的透视变化，BRIEF获得了与SURF64相同数量的正确单词对应关系，如第一个示例所示。在图3的第三个示例中，相机倾斜，使图像在某些区域中呈现旋转，这以及尺度变化阻止了BRIEF获得单词对应关系，在这种情况下，SURF64克服了这些困难并检测到了循环， 我们的结果表明，使用BRIEF描述子的FAST特征在平面相机运动的循环检测问题上几乎与SURF特征一样可靠。作为优势，它们不仅速度更快（每个图像13ms而不是100-400ms），而且占用的内存更少（32MB而不是256MB来存储1M词汇表），并且比较速度更快，从而加速了分层词袋的使用。

图3. 使用BRIEF（左侧）和SURF64（右侧）描述子匹配的单词示例。

图4中展示了通过改变参数α在Bicocca25b数据集上获得的精确度-召回率曲线；为了清晰起见，仅显示了k = 0和3。

图4：在Bicocca25b数据集上，对于几个相似性阈值α，固定了几个连续匹配次数k和处理频率f，没有进行几何检查的精度-召回率曲线。可以看到，连续匹配次数k=3在不同频率下都表现良好，因此我们可以认为这个参数是稳定的。

在表II中展示了每个查询的几何检查执行时间以及回环检测器在每种情况下的召回率，所有情况下的精确度均为100％，该时间包括计算对应点，RANSAC循环以及计算基本矩阵，当达到最大的RANSAC迭代次数时，所有方法中的执行时间最长，穷举搜索比其他方法（是近似方法）获得更高的召回率，但也表现出最高的执行时间。

每个图像所消耗的执行时间如图5所示，这是在一台Intel Core i7 @ 2.67GHz的计算机上测量得到的。

在表III中还显示了每个阶段所需的时间，特征时间涉及计算FAST关键点并在角点响应过低时删除过多的角点，以及使用高斯核对图像进行平滑处理和计算BRIEF描述子。

表格IV总结了算法和词袋表的参数。

在图6中展示了在这些数据集上使用这些参数、以f = 2 Hz处理序列所得到的精度-召回曲线。

在表V中展示了这些曲线的具体数据，在三个数据集中实现了高召回率，且没有误报。

如表VI所示，使用默认参数的算法能够在两个评估数据集中实现大量的召回，而且没有误报，我们的召回率与FAB-MAP 2.0相似，且执行时间更短。

在图7的右侧展示了在训练和评估数据集中，正确的回环检测示例以及相应的最终特征，这些示例显示了BRIEF描述子的有限尺度不变性。

图7. 该系统在五个数据集（从上到下：NewCollege、Bicocca25b、Ford2、Malaga6L、CityCentre）中检测到的回环，其中包括在存在运动模糊和轻微尺度和透视变化的场景中正确检测到的一些示例，右侧的线条描绘了最终对应的特征，左侧的轨迹以细黑线表示新的位置，在重复的区域以粗红线表示，在任何情况下都没有误报。

总结

该论文提出了一种用于图像序列中快速地地点识别的算法，该算法基于字典学习方法，将图像序列转换为二进制的视觉单词表示，并使用快速搜索技术进行匹配。该算法的优点在于可以在实时性要求较高的应用中实现快速的地点识别，例如移动机器人的导航系统。为了构建二进制视觉单词表示，该算法首先使用SIFT算法提取关键点，并计算出每个关键点的局部特征向量。然后，使用k-means算法将所有的特征向量分成不同的聚类中心，并将每个聚类中心作为一个单词。对于每个图像，将其中的局部特征向量投影到聚类中心上，并将其编码成二进制编码。这样，每个图像就可以表示为一系列的二进制编码。为了进行地点识别，将每个图像的二进制编码序列称为一个词袋。使用倒排索引技术，将每个单词映射到包含该单词的所有图像的词袋中。这样，当要识别某个地点时，只需要在倒排索引中查找与当前图像词袋相似的词袋，并选择其中最相似的图像作为匹配结果，实验结果表明，该算法可以在实时性要求较高的情况下实现快速的地点识别，并且在不同场景下表现出较好的性能。