作者：Frank
时间：2016-10-25

在SLAM系统中，当相机姿态被逐帧的计算出来之后，就可以通过对相机姿态的叠加得到相机在空间中的位姿。然而由于相机姿态中或多或少的存在噪声，因此当相机回到重复场景的时候，相机的姿态和重复帧所对应的姿态并不重合，从而导致三角化后得到的地图点出现错位。因此在SLAM系统中，需要利用算法对相机运动过程中可能出现的重复场景进行检测，即回环检测算法。在ORB-SLAM和Kintinuous中都使用了DBoW2作为回环检测算法，因此在本部分对DBoW2算法进行简要的介绍。

1. 理论基础

BoW(Bag of Words)是视觉词袋算法。而在DBoW2中是利用K-means++算法来建立关于词袋的K-D树。而K-means++算法是在K-means算法基础上进行的改进，因此首先对K-means算法进行介绍。

1.1. K-means算法

K-means算法是在聚类分析中使用最广泛的基本算法之一。它把n个对象根据他们自身的属性分为k个聚类，聚类形成的基本准则是：同一聚类中的对象相似度很高；而不同聚类中的对象相似度较小。聚类的基本形成过程如下所示：

K-means方法需要两个输入，一个是需要形成的聚类的数量，另一个是初始化的中心点。
算法的基本流程是随机选择K个初始点，计算所有数据点和中心点的最小距离，并按照该距离将所有的数据点归为距离最小的类中；在该次聚类结束后，计算每一类的中心点并将其作为新的初始点并重复前述步骤。这样不断的进行“划分–更新–划分–更新”，直到每个蔟的中心不再移动为止。
以上就是K-means算法，算法的过程比较简单，但算法存在以下两个缺陷：

1. 聚类中心的个数K需要事先给定，但在实际中这K值得选定是很难进行估计的。因此在很多时候，事先并不知道给定的数据集应该分成多少个类别才合适；

2. K-means需要人为的进行初始聚类中心的选取，而聚类中心不同的初始化过程对于聚类的最终划分结果是有很大影响的，可能会导致完全不同的分类结果。

针对上述第二个缺陷，可以使用K-means++算法来解决。

1.2. K-means++算法

K-means++算法相对K-means算法，其主要区别在于聚类中心的初始化算法不同，在K-means++中对初始聚类 中心选取的原则是：聚类中心之间的相互距离要尽可能的远。其初始化点选取的流程如下所示：

1. 从输入的数据点几何中随机选取一个点作为第一个聚类中心；
2. 对于数据集中的每一个点x,计算它与最近聚类中心的距离D(x);
3. 选择一个新的数据点作为新的聚类中心，选择的原则是，对于D(x)较大的点，其被选取作为聚类中心的概率较大；
4. 重复步骤2和3直到k个聚类中心被选出来；
5. 利用这k个初始的聚类中心来运行标准的K-meangs算法。

以上就是K-means++中初始聚类中心的选取算法，而从步骤中不难看出，在上述算法中最重要的就是步骤3中如何将D(x)反映到被选择的概率上，在DBoW2中使用的算法如下：

1. 先从数据库中随机挑K个随机点作为种子点；
2. 对弈每个点，首先计算其和最近的一个种子点的距离D(x)并保存在一个数组中，然后把这些距离加起来得到Sum(D(x))；

3. 然后再取一个随机值，用权重的方式来取计算下一个种子点，这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random-=D(x)，直到其$ \leq 0$，此时的点就是下一个种子点；

4. 重复步骤2和步骤3直到K个聚类中心被选出来；

5. 利用这k个初始的聚类中心来运行标准的K-means算法；

2. DBoW2算法原理

2.1. 算法基础

DBoW2是利用BoVW来表示图像，将图像进行结构化描述。BoVW的思想是将图像特征整合成视觉单词，将图像特征空间转化为离散的视觉词典，将新的图像特征映射到视觉字典中最近邻视觉词典，再通过计算视觉字典间距离计算图像的相似度，从而完成识别、图像分类、检索等任务。
基于图像的闭环检测系统，将当前采集的图像和之前数据集中所采集到的图像进行比较。每幅图像通过该图像的显著视觉特征描述，并用于图像相似性比较。描述符提取图像特征，将图像$I_u$表示为一个n维的描述符几何$D:I_u\rightarrow {d_1 \cdots d_n}$。 提取特征后，每幅图像由一系列的视觉单词组成，每个描述符提取的特征点$d_i$都关联到视觉字典中的一个视觉单词$\hat{d}_i$，视觉词典表示为：$V={\hat{d}_1 \cdots \hat{d}_n}$。视觉词典V通过BoVW建模方法，对相似描述符聚类进行构建。每一个视觉单词的描述符向量都被认为是一个关联的视觉词表。在构建好视觉词典之后，对群集进行中心化。通过在群集中心构建K-D树，并执行最近邻knn矢量对所有描述符量子化，实现对群集的简化。
为了测量两幅图像$I_u$和$I_v$之间的相似度，可以通过计算它们之间的余弦距离获得，每一幅图像$I_u$由不同权重$w_i$的词汇$\hat{d}_i$聚集而成，权重$w_i$是每个词汇在全部图像集中发生的频率。每个词汇的权重由式：
$$ w_i =log_{10}(N / n_i) \tag{1} $$
计算得到。式中，N是存储的所有图像，$n_i$是$d_i$中包含图像的数量。如果视觉词典中包含|V|个不同的词汇，可以形成图像的矢量为：
$$ \overrightarrow{I}_u=[u_1 \cdots u_{|V|}]^T \tag{2} $$
其中图像中包含的词汇权重如下：
$$ u_i = \left\{ \matrix{w_i & d_i \epsilon I_u \cr
0 & otherwise \cr } \right . \tag{3} $$
在得到每个词汇的权重后，即可求出整幅图像的权重，之后利用相似函数计算图像$I_u$和$I_v$间的相似度，相似度计算公式如下所示：
$$ S(I_u,I_v)={\sum _{i=0}^{|v|} {u_i v_i} \over \sqrt{\sum _{i=0}^{|v|} u_i^2}\sqrt{\sum _{i=0}^{|v|} v_i^2}} \tag{4} $$

2.2. 算法流程

2.2.1. Bag of Words 词典建立

在DBoW2中，首先需要建立视觉词典，其建立过程如下所示：

1. 从训练图像中离线抽取特征；
2. 将抽取的特征用K-means++算法聚类，将描述子空间划分为K类；
3. 将划分的每个子空间，继续利用K-means++算法做聚类；
4. 按照上述循环，将描述子建立树形结构，如下图所示：
   

字典树在建立过程中，每个叶子也就是每个word都记录了该word在所有训练图像中出现的频率。出现的频率越高，说明该word的区分度越小，频率计算公式如下所示：
$$ idf(i)=log{N \over n_i} \tag{5} $$

2.2.2. 在线更新字典树

当在字典树种需要插入一幅新图像$I_t$时，图像中提取的特征描述子按照汉明距离从字典树的根部节点开始逐级向下到达叶子节点，可以计算每个叶子节点也就是每个word在图像$I_t$中出现的频率：
$$ tf(i,I_t)={n_{iI_t} \over n_{I_t}} \tag{6} $$
其中$n_{iI_t}$表示word在图像中出现的次数，$n_{I_t}$表示图像中描述子的总数在树构建过程中每个叶子节点存储了inverse index(倒排序索引)，存储了到达叶子节点的图像$I_t$的ID和图像$I_t$描述子矢量中第i维的值：$v_{i,t}=tf(i,I_t) \times idf(i)$。
对于一幅图像中所有的描述子，做上述操作，可以得到每个word的值，将这些值构成图像的描述矢量$v_t$。对两幅图像比较计算其相似度时，两幅图像的相似度计算公式如下：
$$s(v_1,v_2)=1-{1 \over 2}\left| {v_1 \over |v_1|}-{v_2 \over |v_2|} \right| \tag{7} $$
两幅图像越相似得分越高。字典树出了存储了倒排序索引，还存储了直接索引。直接索引是为了方便两幅图像间的图像特征搜索，建立特征之间的对应，计算两帧间的位姿转换。

2.2.3. 数据库查询

由于在计算相似度时，相似度的大小和字典树、图像等有一定的关系，这里采用归一化的方式，消除这两种因素的影响，归一化相似度计算公式公式如下所示：
$$ \eta(v_t,v_{t_j})={s(v_t,v_{t_j}) \over s(v_t,v_{t-\Delta t})} \tag{8} $$
其中$v_{t-\Delta t}$表示上一帧图像，上式的含义是上一帧图像和当前帧图像是最为相似的，用和上一帧图像计算的相似度来归一化和字典树中图像计算的相似度。当$s(v_t,v_{t-\Delta t})$较小时（机器人做旋转时），会把总体的得分拉的很高，在DBoW2的论文中为了剔除这种因素，引入了阈值$\alpha$，当前帧和上一帧图像相似度小于$\alpha$时不做回环检测。

2.2.4. 相似度匹配组

假设图像$v_t$和图像$v_{n_i}$之间的相似度很大，那么和图像$v_{n_i}$周围的图像也会有很高的相似度，这里将相邻的得分都很高的图像组成一起构成一个集合，得分是这个集合中图像得分的总和。

2.2.5. 局部一致性

假设图像$v_t$ 和集合$V_{t_1}$之间的相似度很大，那么图像$v_{tk\Delta t}$和$V_{tk}$之间的相似度应该也很大，相当于两串图像之间会有重叠，利用这个条件作为图像局部一致性的约束。

2.2.6. 有效几何约束

对于一幅新图像$I_i$，用字典树建立对图像的描述，并且计算和字典树种以前存储的图像之间的得分。倒排序索引能加快待比较的图像的搜索速度。由于在倒排序索引中存储了哪些图像也到达该叶子节点，在选择待比较的图像时，只需要比较到达相同叶子节点的图像，不需要和存储的每幅图像进行比较，从而加快了比较速度。而直接索引能加快特征比较速度。假设图像$I_i$和图像$I_j$得分最高，在两幅图像特征匹配时，只需要比较直接索引中属于同一个节点的图像特征，节点指字典树的一层，如果是叶子节点层，那么选择的是同一个word的特征做匹配。

** 引用来源：

1. DBoW2 回环检测/重定位 算法解析;
2. 视觉slam闭环检测之-DBoW2 -视觉词袋构建;

论文来源：

1. Real-Time Loop Detection with Bags of Binary Words;
2. Bags of Binary Words for Fast Place Recognition in Image Sequences

总结

本节到此结束，因为DBoW本身的原理和算法都比较简单也比较固定，所以引用了较多其他大神博客上的内容，在此表示感谢。DBoW2在SLAM应用中作为回环检测部分的应用较为广泛，值得深入学习。

转载请注明出处