<a target="_blank" href="http://www.cnblogs.com/jian-li/p/5664559.html">dbow2算法原理介绍</a>
本篇介绍dbow2算法原理介绍，下篇介绍dbow2的应用。
dbow2是一种高效的回环检测算法，dbow2算法的全称为bags of binary words for fast place recognition in image sequence，使用的特征检测算法为fast，描述子使用的是brief描述子，（todo:和dbow的区别在哪里？）是一种离线的方法。
二进制特征（orb特征）：fast特征点+brief描述子
（hamming distance） 256bits的二进制描述符
基本的数学知识
brief使用的距离描述算子为hamming距离，定义如下：
算法流程
bag of words字典建立方法（最终得到的就是每一层的不同类的median，每一个叶节点对应的就是一个词汇）：
建树流程
kmeans++方法
输入：（a）聚类数目；（2）初始化中心点（这里使用kmeans++的方法）
算法流程：
迭代：
（1）每个点分类到最近的中心点；
（2）用每一类点的中心点更新中心点。
中心点初始化方法：
-（1）从输入的点集合中随机选择一个点作为第一个聚类中心；
-（2）对于数据集中的每一个点，计算它与已选择的最近的聚类中心的距离d(x)；
-（3）选择一个新的数据点作为新的聚类中心，选择的原则是：d(x)较大的点，被选为聚类中心的概率较大；
-（4）重复2和3的步骤直到k个聚类中心被选出来；
d(x)到概率上的反应：
先从数据库随机挑个随机点当“种子点”
对于每个点，计算其和最近的一个“种子点”的距离d(x)并保存在一个数组里，然后把这些距离加起来得到sum(d(x))。
然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在sum(d(x))中的随机值random，然后用random -= d(x)，直到其<=0，此时的点就是下一个“种子点”。
k-median方法在聚类方法的第二步使用每一个类的中值作为新的中心；
dbow2创建节点代码：
权重设置用的是idf，意思是词汇在训练过程中出现的频率越高，区分度越低，因此权重越低。
每一个节点包括（只列出了部分信息）
[说明]：上面的方法是分层聚类的，每一次聚类得到的多个节点，都有median v表示该类，可以用来判断新的词汇是否属于该类。最终建立的树包括w个叶节点，也就是w个视觉词汇，词汇也用median表示。
转载出处：http://www.cnblogs.com/jian-li/p/5664559.html
鸣谢：感谢原作者的创作，转载文章是为了学习并防止文章删除，绝不做商业用途。