基于词袋模型的图像匹配
看orb-slam的时候发现它在回环检测的时候使用了基于视觉词袋的图像匹配，现在有了一点心得，虽然还有些东西没有完全吃透，但最近比较忙，可能不会有时间在这里死磕，所以先将目前所得写下来，省的忘了。以后有时间完全吃透了会继续完善这篇文章。
Bag-of-words模型简介
词袋模型在信息检索领域使用的比较多，以前上课时就听老师讲过，是很常见的算法。在信息检索中，Bow忽略一个文档中单词出现的顺序、语法、句式等信息，仅仅将文档看成一个集合，集合的元素是单词。如下两个文档：
- Bob likes to play basketball, Jim likes too.
- Bob also likes to play football games.
基于上面两个文档，我们可以为其创建一个词典:
{1:"Bob", 2:"likes", 3:"to", 4:"play", 5:"basketball", 6:"also", 7:"football", 8:"games", 9:"Jim", 10:"too"}依据上面这个词典，我们可以将例子中的两个文档表示成如下两个向量:
- [1, 2, 1, 1, 1, 0, 0, 0, 1, 1]
- [1, 1, 1, 1, 0, 1, 1, 1, 0, 0]
向量中每个元素表示词典中相关元素在文档中出现的次数。我们可以通过度量文档向量之间的相似程度来衡量文档之间的相似程度。
orbslam中的应用
在局部特征点的视觉词典中，每一个单词是具有某一类特征的特征点。在orbslam中使用了DBoW2这个库，这个库的作者提供的ORB特征的词典是其在很大的图像数据集上离线训练好的，我们可以假设任何一个orb特征点都可以在这个词典里找到自己所属的单词类。
在Vocabulary文件夹下的
ORBvoc.txt文件就是词典，大概有150M大小
构造离线词典
在构造离线词典时，使用了分层K-means树的存储结构，这个结构在快速寻找k近邻里面也会经常用到。大概流程如下（构造必须参数有聚类个数k与深度d）
从训练图像中提取大量特征
将抽取的特征描述子使用
k-means聚类算法进行聚类(使用汉明距离)，将整个特征空间划分为k类在上一步中划分的每个子空间中，继续利用
k-means聚类算法进行聚类重复上述第三步，将描述子空间通过一个k叉树（深度为d）进行划分
单词查找与构造Bag-of-Word
对每一副图片，提取orb特征点
对每个orb特征点从词典树的根节点往下遍历，每次进入汉明距离最小的节点，直到抵达叶节点。此时得到这个特征点所属的单词
通过上述步骤得到输入图片的向量表示，可以使用这个向量进行图片的搜索、匹配等。
从上述构造与查找的过程中，我们发现仍然是在叶子层构建了单词，而树结构中的中间节点仅供快速查找时使用。一支深度为d的kmeans的分层聚类树可以容纳\(k^{d}\)个单词。在查找某个给定特征对应的单词时，在每一层上只需要与k个聚类中心进行距离度量，一共d层，可以保证对数级别的查找效率。
Bag-of-Word的构造与相似性度量
我们此处需要讨论一下匹配中的相似度计算的问题。首先考虑的是每个单词的权重应该是不同的，因为我们知道在一个句子中比如“的”、“是”这样的词可能出现的频率非常高，我们无法根据他们判断句子的类型。但是类似“足球”、“壁画”这样的单词对判别句子的作用就更大。所以上面的简单的确定的词袋向量其实是可以改进的。
在文本检索中，常用的一种做法是TF-IDF(Term Frequency-Inverse Document Frequency，频率-逆文档频率)。其中，\(TF\)部分的思想是单词在一副图像中出现的频率越高，他的区分度就越高。\(IDF\)部分的思想是单词在字典中出现的频率越高，那他的区分度就越低。
这种方法在建立字典时就可以统计出\(IDF\)的值，比如某个叶子节点\(w_{i}\)中的特征数量相对于所有特征数量的比例，就是次叶子节点的\(IDF\)值。假设所有特征数量为\(n\)，\(w_{i}\)中的特征数量为\(n_{i}\)，那么该单词的\(IDF\)为：
\[ \operatorname{IDF}_{i}=\log \frac{n}{n_{i}} \]
此外，\(TF\)部分是指某个特征在单个图像中出现的频率。假设图像\(A\)中，单词\(w_{i}\)出现了\(n_{i}\)次，而一共出现的单词次数为\(n\)，那么\(TF\)为：
\[ \mathrm{TF}_{i}=\frac{n_{i}}{n} \]
最后，对于单词\(w_{i}\)在这幅图像中的权重等于\(TF\)与\(IDF\)的乘积：
\[ \eta_{i}=\mathrm{TF}_{i} \times \operatorname{IDF}_{i} \]
在考虑权重之后，对于某个图像\(A\)，它的特征点可对应到许多个单词，组成它的\(Bag-of-Words\)：
\[ A=\left\{\left(w_{1}, \eta_{1}\right),\left(w_{2}, \eta_{2}\right), \ldots,\left(w_{N}, \eta_{N}\right)\right\} \triangleq v_{A} \]
由于一般字典会比较大，一副图像中包含的单词种类有限，因此\(v_{A}\)中会存在大量的零。不过通过词袋向量我们还是可以描述一个图像，只不过这个词袋向量是稀疏的。
相似性对量
接下来便是如何表示两个词袋向量之间的差异，这个问题其实可以使用很多种方法，在\(DBoW\)库中如果不指定会默认是\(L_{1}\)范数形式：
\[ s\left(\boldsymbol{v}_{A}-\boldsymbol{v}_{B}\right)=2 \sum_{i=1}^{N}\left|\boldsymbol{v}_{A i}\right|+\left|\boldsymbol{v}_{B i}\right|-\left|\boldsymbol{v}_{A i}-\boldsymbol{v}_{B i}\right| \]
代码实例
下面代码都是基于\(DBoW3\)库，这时一个\(cmake\)工程，直接默认方式编译安装即可，使用\(cmake\)使用它时与其他库一样。，\(github\)地址是https://github.com/rmsalinas/DBow3
参考文献
- [1] https://www.cnblogs.com/zjiaxing/p/5548265.html
- [2] https://blog.csdn.net/hzwwpgmwy/article/details/83477990
- [3] Mur-Artal R, Montiel J M M, Tardos J D. ORB-SLAM: a versatile and accurate monocular SLAM system[J]. IEEE transactions on robotics, 2015, 31(5): 1147-1163.