心血来潮的想看看回环检测，然后发现词袋模型是怎么产生的都不会（这真是一个悲伤的故事），所以就仔细看了一下它的代码，除此之外还问了问做自然语言处理的室友，室友说这个方法已经很老了（不禁泪目，只能解释传统的才是优秀的），但最起码还是问明白了一些。以下内容都是我自己的理解，如果有人看到觉得不对的请批评指正。

词袋模型的生成

总的来说，如果要用DBoW3产生一本字典，首先需要对一幅图像提取特征并且生成描述子，在ORBSLAM中，使用的是BREIF描述子，这样一幅图像就可以使用描述子来表示了。之后训练一个字典则需要调用以下函数：

DBOW3:Vocabulary vocab;
vocab.create(descriptors);
vocab.save("vocabulary.yml.gz");

以上代码的descriptors是从多幅图像中提取的描述子，他的类型可以是vector<cv::Mat>或者是vector<vector<cv::Mat>>。create函数就是具体生成词袋模型的函数，下面可以具体看一下create函数。源码中重载了多种create函数，但是最核心的部分还是void Vocabulary::create (const std::vector<std::vector<cv::Mat> > &training_features )。在该函数中主要的算法有以下几个部分，下面会根据不同的部分来进行分析。

// create root
    m_nodes.push_back ( Node ( 0 ) ); // root

    // create the tree
    HKmeansStep ( 0, features, 1 );

    // create the words
    createWords();

    // and set the weight of each node of the tree
    setNodeWeights ( training_features );

K叉树节点的形式

为了提升查找效率，DBoW使用了K叉树的方式来对描述子进行存储并且查找。对于树结构来说，最重要的是需要保存他的父节点和子节点，除此之外，它的id值也可以进行存储。所以DBoW3中，每个节点的形式代码所示，整个K叉树如图所示：

 /// Tree node
  struct Node 
  {
    /// Node id
    NodeId id;   //unsigned int
    /// Weight if the node is a word
    WordValue weight;  //double
    /// Children 
    std::vector<NodeId> children;
    /// Parent node (undefined in case of root)
    NodeId parent;
    /// Node descriptor
    cv::Mat descriptor;

    /// Word id if the node is a word
    WordId word_id;

    /**
     * Empty constructor
     */
    Node(): id(0), weight(0), parent(0), word_id(0){}
    
    /**
     * Constructor
     * @param _id node id
     */
    Node(NodeId _id): id(_id), weight(0), parent(0), word_id(0){}

    /**
     * Returns whether the node is a leaf node
     * @return true iff the node is a leaf
     */
    inline bool isLeaf() const { return children.empty(); }
  };

K叉树.png

在树中，根据根节点个数以及层数的不同，树的节点共有个，而id值就是从0开始一共有这个多个，而最底层叶子节点是存储了每个描述子的信息，而上面的每一层中的节点值都代表他们的聚类中心，根据每一类中心的不同，找单词的时候就比原来效率提高了许多。word_id指的是单词的id值，他从0开始共有个，只有叶子节点才会有这个word id值。
聚类主要是使用了KMeans++算法，它相较于KMeans多了一个自主选择初始聚类中心的过程，他们的算法如下所示。

Kmeans++

该算法主要是为了选出合适的聚类中心，因为对于Kmeans来说，聚类中心的选取是随机的并不能很好的表现出数据的特点，所以使用KMeans++可以得到合适的聚类中心，它主要的算法流程为：

1、从数据点中均匀随机选取一个数据作为中心点。
2、对于每一个中心点x，计算其他点与x之间的最短距离D(x)。
3、如果D(x)越大，则证明他被选取为中心点的可能性越大，使用轮盘法选出下一个聚类中心。
4、重复步骤2和3，直到得到k个聚类中心。
5、至此，就得到了出事的聚类中心

初始化聚类中心的代码在Vocabulary::initiateClustersKMpp中，我觉得最核心的代码就是通过轮盘法计算聚类中心的过程。

double cut_d;
do
{
    cut_d = ( double ( rand() ) / double ( RAND_MAX ) ) * dist_sum;   //randomly choose one value between the sum of the distance
}
while ( cut_d == 0.0 );

double d_up_now = 0;
for ( dit = min_dists.begin(); dit != min_dists.end(); ++dit )
{
    d_up_now += *dit;
    if ( d_up_now >= cut_d ) break;   //choose the value 
 }

if ( dit == min_dists.end() )  //choose the center index
    ifeature = pfeatures.size()-1;
else
    ifeature = dit - min_dists.begin();  

该段代码的核心思想就是在总的距离之间随机选取一个值，可以想象，如果距离的值越大，在总和之中占据的比例也越大，随机选取得到的点在该区间的概率也越大，总而言之，该随机选取得到的值在大值中的可能性也越大，这样就有可能选取到与当前聚类中心相聚比较远的点。如果并不是很理解的话，可以参考K-means与K-means++。在距离计算的时候，该代码使用的是bit运算，具体的可以参考Bit Twiddling Hacks，是一个介绍bit运算非常好的网站。

KMeans

KMeans算法的主要步骤为：

1、随机选取得到k个样本作为聚类中心：（该步骤已经通过KMeans++得到）；
2、对于每一个样本，计算他们与中心点之间的距离，取最小的距离的中心作为他们的归类；
3、重新计算每个类的中心点；
4、如果每个样本的中心都不再变化，则算法收敛，可以退出；否则返回1。

该算法的主要代码在Vocabulary::HKmeansStep中，具体操作详见代码，这里就不展开讨论了。

树的生成

比如在第1层得到k个聚类中心以及每个中心中对应的特征点集合之后，就需要将其生成树节点，每个树节点产生的形式如下：

// create nodes
    for ( unsigned int i = 0; i < clusters.size(); ++i )
    {
        NodeId id = m_nodes.size();
        m_nodes.push_back ( Node ( id ) );   //m_nodes represents the tree,
        m_nodes.back().descriptor = clusters[i];  //represent the cluster
        m_nodes.back().parent = parent_id; 
        m_nodes[parent_id].children.push_back ( id );   //save the children's information
    }

如果层数没有到达L，则再继续对每个节点进行聚类。

// go on with the next level
    if ( current_level < m_L )
    {
        // iterate again with the resulting clusters
        const std::vector<NodeId> &children_ids = m_nodes[parent_id].children;
        for ( unsigned int i = 0; i < clusters.size(); ++i )
        {
            NodeId id = children_ids[i];

            std::vector<cv::Mat> child_features;
            child_features.reserve ( groups[i].size() );
            //groups reserve the descriptors of every node
            std::vector<unsigned int>::const_iterator vit;
            for ( vit = groups[i].begin(); vit != groups[i].end(); ++vit )
            {
                child_features.push_back ( descriptors[*vit] );
            }

            if ( child_features.size() > 1 )
            {
                HKmeansStep ( id, child_features, current_level + 1 );
            }
        }
    }

单词的产生

单词产生的函数如以下代码所示，他主要的目的就是给叶子节点的word_id赋值，并且设置单词（描述子）的值。

void Vocabulary::createWords()
{
    m_words.resize ( 0 );

    if ( !m_nodes.empty() )
    {
        m_words.reserve ( ( int ) pow ( ( double ) m_k, ( double ) m_L ) );


        auto  nit = m_nodes.begin(); // ignore root
        for ( ++nit; nit != m_nodes.end(); ++nit )
        {
            if ( nit->isLeaf() )
            {
                nit->word_id = m_words.size();
                m_words.push_back ( & ( *nit ) );
            }
        }
    }
}

设置节点权重

在文本处理中，对于每一个单词的重要性是不一样的，比如说常见的字眼“的”、“是”等等，他们出现的频率是很高，可是他们的区分度并不高，所以他的并没有太大的重要性，而“蜜蜂”、“盐”等等一些名词，并不是所有的句子都会存在的，则他们的区分度可能就会高一点，重要性也会增加。因此，在文件检索中，一种常用的方法就是TF-IDF（Term Frequency-Inverse Document Frequency）。TF指的是某单词在一幅图像中经常出现，它的区分度就高。而IDF指某单词在字典中出现的频率越低，则分类图像时区分度越高。之前我一直不知道这个内容有啥用，在请教了室友之后知道，这个权重可以在原本的特征维数上再加一维用来表示重要程度，这一维数据会使得匹配结果更加的准确。所以一副图像就可以表示为：

其中表示TF-IDF的权重，表示图像中提取得到的描述子。在DBoW3中，描述子的权重如以下代码所示：

void Vocabulary::setNodeWeights
( const std::vector<std::vector<cv::Mat> > &training_features )
{
    const unsigned int NWords = m_words.size();
    const unsigned int NDocs = training_features.size();

    if ( m_weighting == TF || m_weighting == BINARY )
    {
        // idf part must be 1 always
        for ( unsigned int i = 0; i < NWords; i++ )
            m_words[i]->weight = 1;
    }
    else if ( m_weighting == IDF || m_weighting == TF_IDF )
    {
        // IDF and TF-IDF: we calculte the idf path now

        // Note: this actually calculates the idf part of the tf-idf score.
        // The complete tf-idf score is calculated in ::transform

        std::vector<unsigned int> Ni ( NWords, 0 );
        std::vector<bool> counted ( NWords, false );


        for ( auto mit = training_features.begin(); mit != training_features.end(); ++mit )
        {
            fill ( counted.begin(), counted.end(), false );

            for ( auto 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;
                }
            }
        }

        // set ln(N/Ni)
        for ( unsigned int i = 0; i < NWords; i++ )
        {
            if ( Ni[i] > 0 )
            {
                m_words[i]->weight = log ( ( double ) NDocs / ( double ) Ni[i] );
            }// else // This cannot occur if using kmeans++
        }

    }

}

至此，字典就正式生成了，描述子的内容和权重存储在m_words中，而m_nodes存储了每个节点的信息。

字典的保存

字典保存的函数在void Vocabulary::save ( cv::FileStorage &f,const std::string &name ) const中，具体内容就不详述了。

参考资料

DBow3代码
视觉SLAM十四讲