淦ORB-SLAM2源码 03--DBow词袋

词袋模型介绍

Bag of words模型最初被用在文本分类中，将文档表示成特征矢量。它的基本思想是假定对于一个文本，忽略其词序和语法、句法，仅仅将其看做是一些词汇的集合，而文本中的每个词汇都是独立的。
如果文档中猪、马、牛、羊、山谷、土地、拖拉机这样的词汇多些，而银行、大厦、汽车、公园这样的词汇少些，我们就倾向于判断它是一篇描绘乡村的文档，而不是描述城镇的。

举例说明
文档一：Bob likes to play basketball, Jim likes too.
文档二：Bob also likes to play football games.
基于这两个文本文档，构造一个词典：Dictionary = {1:”Bob”, 2. “like”, 3. “to”, 4. “play”, 5. “basketball”, 6. “also”, 7. “football”，8. “games”, 9. “Jim”, 10. “too”}。

基于上述的词典可以构造出一个两个直方图向量
1：[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]
2：[1, 1, 1, 1 ,0, 1, 1, 1, 0, 0]
这两个向量共包含10个元素, 其中第i个元素表示字典中第i个单词在句子中出现的次数. 因此BoW模型可认为是一种统计直方图 (histogram).

DBoW的原理

DBoW就是一种从词袋思想中走出来的算法。在视觉SLAM中它已经成为了回环检测和重定位必不可少的工具。它在SLAM中不但可以用来做回环检测，还能用来加快特征点的匹配。

它和我们上面的例子步骤是一样的，也是先创建字典，然后进行查找。

创建词汇树

DBoW创建的字典方式是通过树型结构来完成的。如下图：

实际上真实使用的词汇树比这个大很多，为了方便只是用一棵小树进行示意！
下面来看一下这棵树是怎么得到的：


然后对这1000个点进行聚类(你竟然不知道聚类是啥！？)，将其聚类为3类，然后分别将它们分配给根节点下一级的三个节点，根据聚类结果，它们分别获得了200、300和500个描述子。

然后继续对这些点分别进行聚类，对于中间层最左边的200个描述子，再进行聚类，其又被分配到了下一级节点，分别被分配了50、100、50个描述子。以此类推，就得到了整个词汇树。

这个过程就是词汇树的训练过程，当然真实的词汇树分支多，层数更深。

有一点儿还需要注意，其中每一个节点都有一个值用来表示聚类中心。例如根节点有1000个描述子，就会根据这些描述子计算一个聚类中心。类似的最下面那一层，也会根据其中被分配到的描述子计算聚类中心，而这个聚类中心就是单词(words)。因此对于这种分支为3，深度为2的词汇树，一共可以获得9个单词。

以上过程用更加规范的句子描述：

step1.在根节点将样本聚为k类
step2.对第一层的每个节点，把属于该节点的样本再聚为k类
step3.重复step2，最后得到叶子层，每个叶子对应一个word，最终得到的树就是vocabulary tree

使用词汇树

训练好了词汇树，下面就是如果使用它了。

例如，我们现在有一个分支为10，层数为5的词汇树，那么其共有单词（word）数量为100000个

例如现在有一张图像，我们对其提取了2000个特征点（关键点+描述子），然后将其每一个描述子通过词汇树找到对应的单词。

步骤为：

step1：先将描述子放在根节点处；
step2：然后将描述子与第一层聚类进行比较，找到与自己最相似的那个子节点，然后将其放入当前子节点；
step3：重复step2，直到该描述子被分配了叶子节点中。
那么叶子节点在训练时得到聚类中心（其实也相当于是描述子），就是当前描述子对应的单词，然后将对每一个描述子都执行这样的操作，那么就会得到每一个描述子对应的单词。

注意：如果从图像中提取的2000个描述子，全部都落入某一个叶子节点中，那么当前图像经过词袋模型转换之后，就只有一个单词。如果2000个描述子经过词袋树之后，落入了不相同的叶子节点中，那么这张图片就有2000个单词。

这就是转换描述子为单词的过程！

在很多视觉SLAM系统中，它对每一个KeyFrame都进行了如上述的描述子转word的过程，所以每一个KeyFrame都有一个词汇向量（BowVector），当我们需要回环检测时，只需要从这些KeyFrame中找到与当前单词数最多的那个KayFrame。

每个单词(words)都一样重要吗？

在上面的介绍过程中，实际上忽略了一个问题，那就是每一个单词都一样重要吗？试想一下上面那个查找句子的例子，如果给你一个单词’I’你能确定是哪个句子吗？我想你不行！但是给你一个’apple’你就确定了是第二个句子。所以’I’和’apple’虽然都是单词，但是其重要程度是不一样的。

对于DBoW，它采用了一些方法量化单词的重要性。当我们拿到一棵已经建好的树，当我们进行描述子的单词匹配时，发现大量的描述子都被分配到了某一个叶子节点中，那么当前叶子节点的word权重就比较低。

DBoW算法一共提供了三种权重计算方法，其计算方法如下：

1.词频Term Frequency（TF）：某个词在文章中出现的次数。为了归一化，词频也可以定义成，某个词在文章中出现的次数 / 文章的总词数。如果一个词比较少见，那么区分度就大。
2.逆向文件频率Inverse document frequency（IDF）：需要一个语料库，来模拟语言的使用环境。IDF定义为，log（语料库的文档总数 / 包含该词的文档数 +1 ）。如果一个词越常见，那么分母就越大，逆文档频率就越小，越接近0。
3.TF-IDF：词频（TF）* 逆向文件频率（IDF）。如果某个词比较少见，但是它在这篇文章中多次出现，那么它很可能就反映了这篇文章的特性，正是我们所需要的关键词。某个词对文章的重要性越高，它的TF-IDF值就越大。

ORBSLAM2 中的DBow

Binary features

1. 使用FAST特征点和BRIEF描述子。
2. FAST和BRIEF特征点计算速度快。
3. 使用二进制的BRIEF描述子计算二进制距离可以使用位运算符（xor），计算hamming距离。

Image database

1. 预先离线收集图像，建立vocabulary。主要包括Inverse index 和Direct index。Inverse index是针对每一个词袋的单词，并且记录每个单词在每个关键帧的权重。Direct index是对每个层的记录，记录了在一张图片在当前层有哪些节点包含了图片中的特征word。每个单词也会记录那些帧能看见当前单词。
2. 使用k means和k medians clustering。使用tf-idf作为权重。
3. Inverse index是为了以后计算中更快的访问每个单词的权重。
4. Direct index是为了更加方便的存储每张图片的每个节点的特征信息。
5. 对于一张新图片，对每个特征点在词袋中寻找hamming距离最近的word。最终encoding成一个t维的向量（t为单词的数量）。

Loop detection

A. Data base query
简单的来说就是寻找队列中距离最近的一个关键帧。
文章中使用一个归一化的score。具体定义可以参见原文章。
B. Matching grouping
如果当前的图片和候选人X很“接近”，那么当前图片和X邻近的的一些关键帧也会同样接近。这不是我们想要的。
所以文章提出讲候选图片先grouping据类成一个个island。每个island中只会有一个最终的结果。
C. Temporal consistency
如果当前图片和某一个候选人很接近，那么上一帧应该和这个候选人很接近才对。
所以下一步的检验是候选人帧和上一帧的匹配检测。
最终得到最终候选人。
D. Efficient geometrical consistency
在获取最终的候选人之后要进行几何验证。
首先是使用之前的Direct index找到可能相似的特征匹配候选。
使用RANSAC fundament matrix匹配。

参考文章
https://blog.csdn.net/weixin_44492024/article/details/92631744.
https://blog.csdn.net/u011341856/article/details/109405181.