【泡泡机器人原创专栏】DBoW3 视觉词袋模型、视觉字典和图像数据库分析
【泡泡机器人原创专栏】DBoW3 视觉词袋模型、视觉字典和图像数据库分析
郭玉峰 泡泡机器人SLAM 2017-01-20
前言
图像数据库、视觉字典和视觉词袋向量是SLAM、计算机视觉、3D物体识别和卷积神经网络图像处理的重要基础工具。所谓“万丈高楼平地起”，在深刻理解这些基本工具的基础之上，根据开源项目构建自己的工程就可以做到游刃有余了。在工程实践中，开源代码往往不能满足业务需求，而对计算机视觉的应用直接上来裁剪代码是一件非常困难的事情。本文的初衷是用最浅显易懂的语言，帮助大家理解并不那么普及的技术，更重要是能够根据这些原理快速构建代码和应用。
无奈，本文作者码力有限，若要对算法上手即来，直接形成代码还是一件非常困难的事情。代码的实践性非常强，大量的工程实践是光明大道。纸上得来终觉浅，绝知此事要躬行。
DBoW3库介绍
DBoW3是DBoW2的增强版，这是一个开源的C++库，用于给图像特征排序，并将图像转化成视觉词袋表示。它采用层级树状结构将相近的图像特征在物理存储上聚集在一起，创建一个视觉词典。DBoW3还生成一个图像数据库，带有顺序索引和逆序索引，可以使图像特征的检索和对比非常快。
DBoW3与DBoW2的主要差别：
1、DBoW3依赖项只有OpenCV，DBoW2依赖项DLIB被移除；
2、DBoW3可以直接使用二值和浮点特征描述子，不需要再为这些特征描述子重写新类；
3、DBoW3可以在Linux和Windows下编译；
4、为了优化执行速度，重写了部分代码（特征的操作都写入类DescManip）；DBoW3的接口也被简化了；
5、可以使用二进制视觉词典文件；二进制文件在加载和保存上比.yml文件快4-5倍；而且，二进制文件还能被压缩；
6、仍然和DBoW2yml文件兼容。
DBoW3有两个主要的类：Vocabulary和Database。视觉词典将图像转化成视觉词袋向量，图像数据库对图像进行索引。
ORB-SLAM2中的ORBVocabulary保存在文件orbvoc.dbow3中，二进制文件在Github上：https://github.com/raulmur/ORB_SLAM2/tree/master/Vocabulary
逆序指针指向一个数据对<图像It, 视觉词袋向量vti>，可以快速获取图像上的视觉单词的权重。当新的图像It加入到图像数据库中的时候，逆序指针就会更新，也方便在数据库中查找图像。逆序索引用于提取与给定图像相似的图像。这个结构用于存储视觉单词，视觉单词组成视觉字典，视觉字典形成图像。检索图像、做比较操作时，就不会对比图像中相同的视觉单词，这对检索图像数据库非常有用。顺序索引有效地获取图像间的云点匹配，加快图像确认中的几何特征检验。顺序指针可以方便地存储每幅图像的特征。视觉字典中的节点是分层存储的，假如树一共有L层，从叶子开始为0层，即L=0，到根结束，l=Lw。对于每幅图像It，将l层的节点存储在顺序指针中，而l层的这些节点是图像It的视觉单词的父节点，局部特征ftj列表与每个节点关联。用顺序指针和词袋模型树估算BRIEF向量描述子空间中的最邻近的节点。对于那些特征属于相同的单词或具有第l层相同父节点的单词，计算特征的对应关系时，这些顺序指针可以加快几何验证过程。当获取一个将要匹配的候选特征时，几何验证非常必要，新图像加进数据库，顺序指针就会更新。
权重计算Weighting
单词在视觉字典和词袋向量中都有权重。
视觉单词有4种权重计算方法：
1. 词频Term Frequency (tf)：其中，
是单词 在图像d中出现的次数；
是图像d中单词的数量；
2. 逆向文件频率Inverse documentfrequency (idf):N是图像数量；Ni是图像包含单词的数量；
3. 词频-逆向文件频率Term frequency -inverse document frequency (tf-idf):
4. 二值：
注意：视觉词典创建之后，DBoW根据图像的数量计算N 和 Ni 。他们的值不会随图像数据库中的图像特征入口数量的变化而变化。
相似度度量 Scoring
如果是要对观测到的样品数据进行判别分类的问题，可以应用统计学中判别分析方法进行处理。判别分析方法主要有距离判别、贝叶斯判别和典型判别等几种常用方法。通常我们所说的距离是欧式距离，即欧式空间中两点之间的距离。但在统计学多元分析中，有时欧式距离不太合适。比如，某个数据点在两个正态分布中的距离。这样就会用到马哈拉诺比斯Mahalanobis距离，即马氏距离。
在分类中的相似度度量有两种方法---距离和相似系数，距离用来度量样品之间的相似性，相似系数用来度量变量之间的相似性。样品之间的距离和相似系数的定义不同，而这些定义与变量的类型有非常密切的关系。变量按照测量尺度的不同可以分为三类：
1） 间隔尺度变量：变量是连续的量。如长度、速度、重量、温度等。
2） 有序尺度变量：不明确的数量表示变量，而是用等级表示。如某产品分为一等品、二等品、三等品等有序关系。
3） 名义尺度变量：变量用一些类表示，无等级或数量关系。如性别、职业等。
可以通过词典Vocabulary或查询图像数据库Database计算两个向量的相似度。有好几种方法可以计算相似度。相似度的值的含义在于我们使用什么样的度量方式。然而，有些度量方法可以标准化到区间[0..1]中，0表示没有匹配，1表示完美匹配。如果需要修改计算相似度的代码，也要注意词典Vocabulary和图像数据库Database的执行速度。
计算两个向量v 和w的相似度有几种度量方法（这里v* 和w* 表示经过L1范数标准化后的向量）：
1、点积Dot product:
2、L1范数L1-norm:
3、L2范数L2-norm:
4、巴式系数Bhattacharyyacoefficient: 。巴式距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。
5、卡方距离 χ² distance:
6、KL散度 / 相对熵KL-divergence:
有些方法在使用前，要对向量进行标准化处理。向量通常都是稀疏的、包含了一些0值，卡方距离和KL散度并不能处理所有向量。因此，需要避免数值处理上的问题。在KL散度的计算中，ε 是计算机给出的epsilon 值（最小的浮点负数）。当计算计分的时候，可以使用一个标志位来指示这些值在线性范围[0..1]中, 其中1是最大值，0是最小之。用L1-范数,L2-范数和卡方距离时，**这个标志位。巴式系数Bhattacharyyacoefficient 总是在[0..1]内，并不依赖于变换标志位。
注意：为了计算效率，计算卡方距离的时候假定权重从来都不会为负数（使用tf, idf, tf-idf 和 binary 向量的时候，总是这样）。创建字典的时候，缺省使用tf-idf 和L1-范式。
DBoW3代码解读
DBoW3库主要类：
DBoW3视觉字典构建过程：
视觉字典树生成过程
DBoW3库中各类说明：
核心算法K-Means++聚类
聚类是机器学习、计算几何的经典问题。在最流行的k-means方法中，给定整数k和上的一组n个数据点。目标是选择k个聚类中心点，求每个数据点到最近的聚类中心距离平方和的最小值。
k-means算法原理简单、容易实现，计算时间短、速度快，但精度不够高。
定义k-means问题：
1、给定一个整数k表示聚类簇的数量和n个数据点
2、选择k个聚类中心点C，求函数的最小值：。
k-means聚类过程示意图：
k-means聚类算法原理：
1. 随机选取k个初始中心数据点，即k个簇的各自中心，记作
2. 对于每个簇当
时聚类簇
中的所有数据点χ到
的距离比它们到的距离更近；
3. 对于每个簇,设置
为这群数据点的中心:
4. 重复第2步和第3步，直到聚类簇C不再变化，数据点不会再被重新划分。
初始的中心数据是从χ中随机选择k个聚类中心。但初始聚类中心并不是最优化的，为了得到优化的聚类中心，k-means算法迭代地进行两步操作。对于上述第2步，只要方法是一致的，对比关系可以任意变换。第2步和第3步用于降低∅值，算法局部改进，自由聚类，直到它不能再循环计算为止。实际上是第3步降低了∅值，使用的是线性代数中的结果。
k-means聚类算法步骤：
有序属性的相似度可以采用闵可夫斯基距离直接计算距离，对无序属性可以采用VDM（Value Difference Metric）。
k-means算法以欧几里得距离作为距离或相似度测算，求对应的初始聚类中心数据的最优分类，使得评价结果最小。算法采用误差平方和准则函数作为聚类准则函数。
相关定义
k-means聚类过程中的数学模型分析：
其中，c为聚类簇χ的均值。
给定k聚类完成后，求一个类中所有样本点到该聚类中心距离的平方和，即：；所有的聚类簇加起来，记为：
，聚类算法就是要使Sum最小。系数r用于指示第n个数据点被聚类到第k个聚类簇的对应关系，如果归类成功，就记为1；否则为0。
直接根据Sum确定r和c来使Sum最小化并不容易，但可以采用迭代方法：先给一个初始c数据点，选择最优的一群r，可以直观看出只要将这n个数据点归类到离它最近的中心就能保证Sum最小。
然后，再固定r值，求最优的簇类中心点c。可以将Sum对c求导，导数为零时，Sum应为最小。
当数据点归类到聚类簇中时，r=1，c就是第k个聚类簇中所有数据点的平均值。每一次迭代都是取Sum的最小值，k-means最终会得到一个极小值。但不能保证能得到一个全局最优解。
k-means++聚类算法流程：
1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
2. 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3. 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
4. 重复2和3直到k个聚类中心被选出来
5. 利用这k个初始的聚类中心来运行标准的k-means算法
DBoW3库核心算法k-means++代码
这里重点代码是k-means++
备注：为了显示程序的关键字，采用截图形式贴出源码，如果图片不清晰，请阅读 ：
https://github.com/rmsalinas/DBow3/blob/master/src/Vocabulary.cpp 222至482行
参考文献
1. 《机器学习》周志华
2. 《应用多元分析》王学民
3. Bags of Binary Words for Fast Place Recognition in ImageSequences
4. Video Google: A Text Retrieval Approach to Object Matchingin Videos
5. Scalable Recognition with a Vocabulary Tree
6. Interactive learning of visual topological navigation
7. Fast and incremental method for loop-closure detection usingbags of visual words
8. Bag of visual wordmodel based on binary hashing and space pyramid
【版权声明】泡泡机器人SLAM的所有文章全部由泡泡机器人的成员花费大量心血制作而成的原创内容，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！
【注】商业转载请联系刘富强（[email protected]）进行授权。普通个人转载，请保留版权声明，并且在文章下方放上“泡泡机器人SLAM”微信公众账号的二维码即可。
↑长按上方免费订阅
【编辑】徐武民