Bags of Binary Words | 词袋模型解析

Bags of Binary Words for Fast Place Recognition in Image Sequences

作者：Liam

原来论文中很详细的讲述了闭环和重定位过程中的操作，当看对应代码的时候，最好先看看这些过程的说明。

摘要

本文提出了一种利用FAST+BRIFE得到的单词包进行视觉位置重识别的新方法。首先离散化二进制描述符空间生成一个词汇树，然后利用这个树来加速匹配点的几何验证。本文的方法利用相同的参数在不同的数据集上做了测试都没有假阳性的结果。包括特征提取的整个过程在有26300张图片的序列中仅需要22ms/帧。

介绍

对于需要长时间运行的SLAM系统，鲁棒的重定位模块十分重要。在跑实验的时候如果没有闭环检测，如果系统长时间的运行后又到了先前到过的场景，这个时候传统的识别方法就会失效，闭环检测可以提供正确的数据关联来获得全局一致性的地图。同样的方法可以用在机器人由于突然的运动，遮挡或者运动模糊造成的轨迹丢失的重定位。在[1]中，作者证明了在小环境下map-to-image(寻找相机的最新帧与地图上的特征之间的对应。)的方法有着不错的效果。但是在大场景下，image-to-image（或appearance-based寻找来自相机的最新图像与之前看到的图像之间的对应关系）的方法表现的更好，比如快速的appearance-base（FAB-MAP）的大规模建图更好.基本的技术是利用机器人实时收集的图像来建立一个数据库，当进来新的图像的时候可以检索得到与之最相近的图像，如果他们足够的相似，就认为他们是一个闭环。最近几年，很多算法都利用这个方法实现[2][3][4][5][6],即基于图像匹配，将它们作为词袋空间中的数值向量进行比较.词袋模型可以进行非常有效和快速的图像匹配，但是它们并不是闭环检测的完美解决方案，这主要是由于perceptual aliasing(感知混淆)(我的理解是可能是相似的场景，比如同样的走廊)造成的。为此，我们在后面进行了检查匹配图像的几何一致性的验证步骤。闭环检测算法的瓶颈通常是特征提取，这在计算周期上比其他步骤要耗时十倍左右。这可能会导致SLAM算法在两个解耦的线程中运行:一个执行主要的SLAM功能，另一个只是进行闭环检测，就像[5]中的那样。

本文利用普通的CPU和单目相机可以实时的检测闭环，建立图像间的对应点的匹配。本文的方法基于词袋模型和几何检测（有几个重要的新特性使它比目前的方法快得多）。最重要的速度改善的原因是因为利用了版本修改后的BRIEF描述子和FAST。BRIEF描述子是一个二进制的向量，其中每个位是围绕关键点的给定像素对之间的强度比较的结果。虽然简短的描述符很难对比例和旋转保持不变，但我们的实验表明，它们对于平面摄像机运动的闭环是非常健壮的，这是移动机器人的常见情况，在特殊性和计算时间之间提供了一个很好的折中。本文引入了一组离散化二进制空间的单词，并使用一个直接索引(除了通常的反向索引之外)对其进行扩充。这是第一次利用二进制单词进行闭环检测。反向索引用于快速检索可能与给定图像相似的图像。提出了一种利用直接索引有效获取图像间点对应的新方法，加快了闭环验证的几何检验速度。为了验证是一个闭环，我们验证了图像匹配的时间一致性。本文的创新之处在于，它提供了一种技术，可以在查询数据库时防止在同一位置收集的图像相互竞争。我们通过将匹配过程中描述相同位置的图像分组来实现这一点。通过实验证明本方法可以在52毫秒内运行整个闭环检测过程，包括特征提取，其中包含26300张图像(平均22毫秒)，这比以前的技术要好一个数量级。

相关工作

基于外观的位置识别由于取得了优异的结果，在机器人领域引起了极大的关注,这方面的一个例子是fabmap系统，它使用一个全景相机来检测闭环，在轨迹为70公里和1000公里的序列中召回率分别为48.4%和3.1%，没有假阳性。FAB-MAP用词袋表示图像，并使用一个“Chow-Liu”tree来离线学习单词的共视概率。FAB-MAP已经成为闭环检测的黄金标准，但是当图像长时间在相似的场景中运行的时候，其鲁棒性会下降，这可能是使用前置相机时的情况。在Fast and incremental method for loop-closure detection using bags of visual words的工作中，两个视觉单词(外观和颜色)以增量的方式在线创建。这两个单词一起作为贝叶斯过滤器的输入，贝叶斯过滤器估计两个图像之间的匹配概率，考虑到以前的情况下的匹配概率。与这些概率方法相比，我们依靠时间一致性检查来考虑以前的匹配，提高了检测的可靠性。为了进行候选帧检验，我们通常利用几何验证。利用极线约束来检验最好的匹配候选帧。而且利用直接索引的方式更快的计算对应点。Robust place recognition with stereo sequences利用双目视觉里程计来得到实时的环境地图，利用词袋模型的方法检测闭环。它们的几何检查包括计算匹配图像之间的空间变换。但是，他们不考虑与以前匹配的一致性，这导致他们需要把几何检查应用在多个几个闭环检测的候选对象。在大多数闭环检测的系统中利用的是尺度不变的SIFT或者SUFT。因为他们对尺度光照和旋转具有不变性，而且在轻微的视角变化中表现出良好的行为，然而，这些特征通常需要100到700毫秒之间进行计算。还有其他类似的特征可以减少运算时间，例如SIFT描述子或者降低维度的SIFT。Konolige利用紧凑的随机树特征使工作有了质的变化。这个方法计算当前图像块和其他先前离线训练过的图像块的相似度。通过计算描述子来连接这些图像块中相似的值，最后利用random orthoprojections的方法降低维度。这就可以产生一个很快的描述子来满足实时性的要求。本文和[3]的相似之处就是也利用了高效的特征。BRIEF描述子或者是尺度不变的BRISK和旋转不变的FAST及BRIEF(orb)特征都是二进制、仅需要很少时间去计算的。作为一种优势，它们的信息非常紧凑，因此占用的内存更少，比较起来也更快。这允许更快地转换到单词空间。

二进制特征

在图像中提取特征和描述子是很耗时的，本文中利用FAST特征点和BRIEF描述子，FAST关键点的提取类似检测角点，在半径为3的圆中比较像素点的灰度值。因为只有很少一部分像素点需要比较（一般135）所以这些点可以很快得到。对于每一个FAST特征点，我们检测它周围一个连续的块状的BRIEF描述子。描述子是二进制的向量，其代表图像块中两个像素点灰度值的比较结果。图像块需要预先利用高斯核函数滤波。根据先前给定的图像块大小Sb，在图像块中利用离线的方法随机的选择像素点对。除了Sb，我们也要设置Lb：描述子的长度。对于一个点p，它的描述子向量B(p)根据下式决定：

BRIEF描述子速度很快，一个256位的描述子仅需要17.3μm因为每个描述子就是一个二进制的vector，所以可以直接比较两个向量不同的位来得到两个向量的距离(汉明距离)，即两个向量可以直接进行异或运算。SIFT和SUFT的描述子是由浮点数组成的，经常需要计算欧式距离。

图像数据库

为了检测闭环，我们利用分层的单词和直接及反向索引组成图像数据库。词袋是一种使用视觉词汇表将图像转换成稀疏的数字向量的技术，允许我们管理大量的图像。视觉词袋是通过离线的将描述符空间离散成W个视觉单词生成的。通过离散化二进制描述子空间，可以创建了更紧凑的词袋。对于有层次的词袋，词汇表的结构是树状的。为了得到词袋，我们从一些训练图像中提取丰富的特征，首先利用k-means++ seeding来执行k-medians clustering以离散化检测到的描述子。中值导致非二进制的描述子截断成0。这些簇构成词汇表树的第一级节点。通过使用与每个节点关联的描述符重复此操作创建后续级别，直到Lw次。最后，我们得到了一棵有W叶子节点的树，W个叶子节点就是词汇表中的单词。每个单词都根据其在训练集中的相关性赋予权重，减少那些频繁出现的单词的权重，因为他们辨别性很弱。我们在这里定义频率这个术语-inverse document frequency(tf-idf)。然后为了转换一个在t时刻得到的

两个结构(词袋和反向索引)通常是单词包方法中用于搜索图像的惟一结构。但是作为一种新颖的通用方法，我们还利用直接索引存储每个图像的特征。我们根据单词在树中的层数l对节点进行分离，从叶节点开始，层数为l = 0，直到根节点l = Lw。对于每个图像It，我们存储他的直接索引。l层的节点是其中出现的单词的祖先，以及与每个节点关联的本地特征ftj列表。我们利用直接索引和单词树的均值来在BRIEF空间中大概的找到图像的最近邻。直接索引只计算属于一个word或者在第l层有共同根节点的对应点的特征来加速之间的几何验证。当一个新的图像添加到数据库直接索引更新,当获得了候选的匹配而且进行了几何验证，则可以存取直接索引。

闭环检测算法

为了检测到闭环，本文用了作者以前的工作[5][6],主要包含以下这四个过程：

A.数据库查询

我们利用图像数据库来存储和检索和给定的图像相似的图像，当最新的图像进来了

B.Match Grouping（匹配分组）

C.时间一致性

当获得了最佳的匹配分组V_T'以后，我们检测他和之前序列的时间一致性。在本篇论文中，作者利用[5]和[6]扩展了时间一致性。(v_t,V_T')一定要和以前连续的k个分组得分连续，然后在V_T'分组中找到相似度得分最高的，然后把他看成一个候选帧，这个候选帧最后经过几何验证才可以被确定。

D.几何一致性检测

我们在两个匹配的闭环候选帧用几何检测。这个检验是通过它至少12个对应点利用随机样本一致性(RANSAC)找到I_t和I_t'之间的一个基础矩阵。为了计算这些对应点，我们必须将序列图像的局部特征与匹配图像的局部特征进行比较。有几种方法来得到这种比较：

暴力搜索：通过比较I_t和I_t'之间特征的描述子之间的距离，根据最近邻距离比例策略搜索对应点。每个图像的复杂度都是n^2

第二种技术是通过在k维(k-d)树中排列描述符向量来计算近似最近邻[7]

我们可以利用词袋加速特征匹配。因此，在向数据库添加图像时，我们在直接索引中存储节点和特征的列表。为了在I_t和I_t'获得对应点，直接查找I_t'帧的直接索引，仅对在词袋中l级的相同节点中的特征进行比较。这个条件加快了特征匹配的计算速度。参数l是预先确定的，需要在It和It'之间获得的特征点的数量和花费的时间之间进行权衡。当l=0时，只比较属于同一单词的特征(正如我们在[12]中所表示的那样)，这样可以达到最高的加速，但是只能获得很少的匹配点。这使得闭环检测过程的召回减少，因为一些正确的闭环由于缺乏对应点而被舍弃。另一方面，当l=Lw时，召回不受影响，但执行时间也没有提高（最后一层就和暴力匹配是一样的）。我们只需要基本矩阵进行验证，但注意，在计算之后，我们可以提供与下面运行的任何SLAM算法匹配的图像之间的数据关联，而不需要额外的成本(有了F矩阵就可以解算RT了)。

参考文献：

1.A comparison of loop closing techniques in monocular SLAM

2.FAB-MAP: Probabilistic localization and mapping in the space of appearance

3.Robust place recognition with stereo sequences

4.Fast and incremental method for loop-closure detection using bags of visual words

5.CI-graph SLAM for 3D reconstruction of large and complex environments using a multicamera system

6.Robust place recognition with stereo sequences

7.Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph

备注：作者系我们「3D视觉从入门到精通」特邀嘉宾：一个超干货的3D视觉学习社区

本文仅做学术分享，如有侵权，请联系删文。

下载1

在「计算机视觉工坊」公众号后台回复：深度学习，即可下载深度学习算法、3D深度学习、深度学习框架、目标检测、GAN等相关内容近30本pdf书籍。

下载2

在「计算机视觉工坊」公众号后台回复：计算机视觉，即可下载计算机视觉相关17本pdf书籍，包含计算机视觉算法、Python视觉实战、Opencv3.0学习等。

下载3

在「计算机视觉工坊」公众号后台回复：SLAM，即可下载独家SLAM相关视频课程，包含视觉SLAM、激光SLAM精品课程。