ORB-SLAM3中的词袋模型BoW
作者丨卢涛@知乎
来源丨https://zhuanlan.zhihu.com/p/354616831
编辑丨3D视觉工坊
非完整版注释：https://github.com/smilefacehh/ORB-SLAM3-Note
orb-slam3与2的区别不大，本系列文章代码取自orb-slam3，但概念流程都一样，所以后面不加区分。这篇文章讲一下词袋模型BoW，它主要用于两帧2d-2d匹配加速，以及在历史关键帧中搜索最相近的帧（闭环检测）。本文内容包括kd树创建词典、单词的权重TF-IDF、词向量相似度计算、基于词典计算新帧的词向量和正逆向索引、正向索引和逆向索引的应用。如果有理解上的错误，请您指正。
kd树创建词典
BoW，Bag of Words，词袋。姑且认为word等同于一个特征点，它是若干特征点的聚类中心，当然还是一个特征点，只不过若干个接近的特征点，都映射到同一个特征点，给它起个新的名字叫做word。那么一帧图像，若干个特征点，可以映射得到若干个word，word集合就是BoW。
那么，如何将特征点映射得到word呢。上面说过word是局部范围内特征点的聚类中心，那么需要进行聚类操作。比如有N个特征点，希望聚类成M个word，M < N。通过K-means聚类，对N个特征点进行聚类，这些特征点来自大量图像提取的fast特征，数量庞大，一次聚类成M个中心，会很慢。那我们少次多量，一次聚类k个，k < M。得到k个簇之后，再对每个簇继续划分k个。执行d次，就得到了最终需要的word数量。
上面的过程是在创建词典，实际是一个kd树的过程。kd树一共d层，每层k个节点。叶子节点就是word，非叶子节点就是少量多次聚类操作的聚类中心，就是最具代表性的那个特征点。
词典创建完了，怎么用呢。新帧的特征点通过kd树查找得到对应的word，所有word构成BoW。除了计算BoW，还需要维护和更新两个信息，正向索引（Direct Index）、逆向索引（Inverse Index）。
kd数构建词典
结合上图对这两个概念进行说明。orb-slam3中维护了一个关键帧数据库，每次新增一个关键帧，都会通过kd树计算BoW，同时更新正向索引和逆向索引。每个单词拥有一个逆向索引表，记录包含该单词的帧，和权重。那么假设我要在关键帧数据库中，找到与当前帧最相似的一帧，只需要找与当前帧共享单词的这些帧（逆向索引表记录下来了），统计他们与当前帧共享单词的总数，取总数最大的那一帧即可。
正向索引则是针对每一帧而言，每帧图像有一个逆向索引表，记录在kd树某一层，命中的节点集合，以及节点中的特征点。如上图，在l=1层，图像1包含id为65、10、32的特征点，分别划分到了Node3、Node4节点中，记录这么一个关系。它主要用于加速两帧特征点匹配，显然两帧对应的匹配点会落入相同的节点中，这样的话，只需要对两帧相同节点中的特征点进行匹配即可。
单词的权重TF-IDF
首先说明一下，IDF是在构建词典的时候计算好，TF是在对新帧计算词向量的时候计算的，TF*IDF就是最终单词的权重，也就是单词的值。
IDF（Inverse Document Frequency），某个单词在词典中出现的频率越低，则辨识度越高，相应权重IDF会大一些。
template<class TDescriptor, class F>
void TemplatedVocabulary<TDescriptor,F>::setNodeWeights
(const vector<vector<TDescriptor> > &training_features)
{
const unsigned int NWords = m_words.size();
const unsigned int NDocs = training_features.size();
else if(m_weighting == IDF || m_weighting == TF_IDF)
{
// 遍历所有帧
for(mit = training_features.begin(); mit != training_features.end(); ++mit)
{
// 遍历一帧feature
for(fit = mit->begin(); fit < mit->end(); ++fit)
{
WordId word_id;
transform(*fit, word_id);
// 统计单词出现次数
if(!counted[word_id])
{
Ni[word_id]++;
counted[word_id] = true;
}
}
}
// 计算IDF = log(N/Ni)
for(unsigned int i = 0; i < NWords; i++)
{
if(Ni[i] > 0)
{
m_words[i]->weight = log((double)NDocs / (double)Ni[i]);
}
}
}
}TF（Term Frequency），指在单帧中某个单词的频次，频次高，权重大。（emm..）
对于新帧计算BoW，它的权重就是TF*IDF。DBoW2里面，TF设置为1了。
词向量相似度计算
词向量就是单词的集合，可以表示成one-hot向量的形式。但是因为给定词典，单词的id都是固定的，所以只存命中的单词id、权重即可。
class BowVector:public std::map<WordId, WordValue>计算两帧图像的相似度，等价于计算两个词向量的相似度。DBoW2库里面定义了6种计算词向量相似度的方法，具体实现可以看看代码，不是很难。
double L1Scoring::score(const BowVector &v1, const BowVector &v2) const；
double L2Scoring::score(const BowVector &v1, const BowVector &v2) const；
double ChiSquareScoring::score(const BowVector &v1, const BowVector &v2) const;
double KLScoring::score(const BowVector &v1, const BowVector &v2) const;
double BhattacharyyaScoring::score(const BowVector &v1, const BowVector &v2) const;
double DotProductScoring::score(const BowVector &v1, const BowVector &v2) const;基于词典计算新帧的词向量、正逆索引
正向索引加速两帧2d-2d匹配，逆向索引加速查找匹配帧，通常应用于闭环检测。
通过已经构建好的ORB词典，对一帧描述子，计算词向量和正向索引。
DBoW2::BowVector mBowVec;
DBoW2::FeatureVector mFeatVec;
class BowVector:public std::map<WordId, WordValue>
class FeatureVector:public std::map<NodeId, std::vector<unsigned int> >
// 根据已有词典，计算一帧的词向量、正向索引
void KeyFrame::ComputeBoW()
{
if(mBowVec.empty() || mFeatVec.empty())
{
vector<cv::Mat> vCurrentDesc = Converter::toDescriptorVector(mDescriptors);
mpORBvocabulary->transform(vCurrentDesc,mBowVec,mFeatVec,4);
}
}逆向索引。KeyFrameDatabase维护了一个逆向索引map，记录每个单词中落入的关键帧。
// 新增一帧关键帧，更新逆向索引
void KeyFrameDatabase::add(KeyFrame *pKF)
{
unique_lock<mutex> lock(mMutex);
for(DBoW2::BowVector::const_iterator vit= pKF->mBowVec.begin(), vend=pKF->mBowVec.end(); vit!=vend; vit++)
mvInvertedFile[vit->first].push_back(pKF);
}正向索引、逆向索引的应用
利用正向索引加速两帧匹配，假设在kd树的第4层（叶子节点是0层），事先统计好了特征点落入的节点，帧1 = {node1, node3, ..., node12}，帧2 = {node2, node3, ..., node11}。那么不需要逐一比较两帧的特征点，只需要先找到相同的节点，在节点里面再去逐一比较特征点。
优化效率：假设100个特征点，平均分配到20个节点中，节点的重合率是80%，那么优化后比较次数是(100/20)^2*20*0.8 = 400，优化前是100^2 = 10000。如果分配到50个节点中，优化后是(100/50)^2*50*0.8 = 160。优化还是比较明显的。
int ORBmatcher::SearchByBoW(KeyFrame* pKF,Frame &F, vector<MapPoint*> &vpMapPointMatches)
{
...
const DBoW2::FeatureVector &vFeatVecKF = pKF->mFeatVec;
...
DBoW2::FeatureVector::const_iterator KFit = vFeatVecKF.begin();
DBoW2::FeatureVector::const_iterator Fit = F.mFeatVec.begin();
DBoW2::FeatureVector::const_iterator KFend = vFeatVecKF.end();
DBoW2::FeatureVector::const_iterator Fend = F.mFeatVec.end();
// 遍历两帧对应的node集合
while(KFit != KFend && Fit != Fend)
{
// 相同的node里面，注意比较特征点
if(KFit->first == Fit->first)
{
const vector<unsigned int> vIndicesKF = KFit->second;
const vector<unsigned int> vIndicesF = Fit->second;
...
}
else if(KFit->first < Fit->first)
{
KFit = vFeatVecKF.lower_bound(Fit->first);
}
else
{
Fit = F.mFeatVec.lower_bound(KFit->first);
}
}
...
}利用逆向索引确定候选匹配闭环帧。遍历当前帧的单词集合，对于每个单词，它里面落入了许多历史关键帧，对这些帧计数+1，表示与当前帧共享一个单词，统计完当前帧的所有单词之后，取共享数量最多的那一帧，就是与当前帧最接近的一帧了。
vector<KeyFrame*> KeyFrameDatabase::DetectLoopCandidates(KeyFrame* pKF, float minScore)
{
set<KeyFrame*> spConnectedKeyFrames = pKF->GetConnectedKeyFrames();
list<KeyFrame*> lKFsSharingWords;
// 遍历当前帧的单词集合
for(DBoW2::BowVector::const_iterator vit=pKF->mBowVec.begin(), vend=pKF->mBowVec.end(); vit != vend; vit++)
{
// 落入该单词中的历史关键帧（通过逆向索引得到node里面的帧）
list<KeyFrame*> &lKFs = mvInvertedFile[vit->first];
// 遍历落入该单词中的历史关键帧
for(list<KeyFrame*>::iterator lit=lKFs.begin(), lend= lKFs.end(); lit!=lend; lit++)
{
KeyFrame* pKFi=*lit;
...
lKFsSharingWords.push_back(pKFi);
pKFi->mnLoopWords++;
}
}
// 统计历史关键帧中与当前帧共享单词数量最多的一帧
int maxCommonWords=0;
for(list<KeyFrame*>::iterator lit=lKFsSharingWords.begin(), lend= lKFsSharingWords.end(); lit!=lend; lit++)
{
if((*lit)->mnLoopWords>maxCommonWords)
maxCommonWords=(*lit)->mnLoopWords;
}
...
}参考
1.《视觉Slam十四讲》，高翔
2."Bags of Binary Words for Fast Place Recognition in Image Sequences"
http://doriangalvez.com/papers/GalvezTRO12.pdf
3.小葡萄：[ORB-SLAM2] 回环&DBoW视觉词袋
https://zhuanlan.zhihu.com/p/61850005
本文仅做学术分享，如有侵权，请联系删文。
下载1
在「3D视觉工坊」公众号后台回复：3D视觉，即可下载 3D视觉相关资料干货，涉及相机标定、三维重建、立体视觉、SLAM、深度学习、点云后处理、多视图几何等方向。
下载2
在「3D视觉工坊」公众号后台回复：3D视觉github资源汇总，即可下载包括结构光、标定源码、缺陷检测源码、深度估计与深度补全源码、点云处理相关源码、立体匹配源码、单目、双目3D检测、基于点云的3D检测、6D姿态估计源码汇总等。
下载3
在「3D视觉工坊」公众号后台回复：相机标定，即可下载独家相机标定学习课件与视频网址；后台回复：立体匹配，即可下载独家立体匹配学习课件与视频网址。