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会大一些。

代码语言：javascript复制

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、权重即可。

代码语言：javascript复制

class BowVector:public std::map<WordId, WordValue>

计算两帧图像的相似度，等价于计算两个词向量的相似度。DBoW2库里面定义了6种计算词向量相似度的方法，具体实现可以看看代码，不是很难。

代码语言：javascript复制

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词典，对一帧描述子，计算词向量和正向索引。

代码语言：javascript复制

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，记录每个单词中落入的关键帧。

代码语言：javascript复制

// 新增一帧关键帧，更新逆向索引
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。优化还是比较明显的。

代码语言：javascript复制

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，表示与当前帧共享一个单词，统计完当前帧的所有单词之后，取共享数量最多的那一帧，就是与当前帧最接近的一帧了。

代码语言：javascript复制

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视觉工坊」公众号后台回复：相机标定，即可下载独家相机标定学习课件与视频网址；后台回复：立体匹配，即可下载独家立体匹配学习课件与视频网址。

重磅！3DCVer-学术论文写作投稿交流群已成立扫码添加小助手微信，可申请加入3D视觉工坊-学术论文写作与投稿微信交流群，旨在交流顶会、顶刊、SCI、EI等写作与投稿事宜。同时也可申请加入我们的细分方向交流群，目前主要有3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、多传感器融合、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流、ORB-SLAM系列源码交流、深度估计等微信群。一定要备注：研究方向学校/公司昵称，例如：”3D视觉上海交大静静“。请按照格式备注，可快速被通过且邀请进群。原创投稿也请联系。

图像处理数据挖掘 node.js

0 人点赞