心血來潮的想看看回環(huán)檢測，然后發(fā)現(xiàn)詞袋模型是怎么產(chǎn)生的都不會（這真是一個悲傷的故事）温鸽，所以就仔細(xì)看了一下它的代碼，除此之外還問了問做自然語言處理的室友，室友說這個方法已經(jīng)很老了（不禁淚目屹逛，只能解釋傳統(tǒng)的才是優(yōu)秀的），但最起碼還是問明白了一些汛骂。以下內(nèi)容都是我自己的理解罕模，如果有人看到覺得不對的請批評指正。

詞袋模型的生成

總的來說帘瞭，如果要用DBoW3產(chǎn)生一本字典淑掌，首先需要對一幅圖像提取特征并且生成描述子，在ORBSLAM中蝶念，使用的是BREIF描述子抛腕，這樣一幅圖像就可以使用描述子來表示了。之后訓(xùn)練一個字典則需要調(diào)用以下函數(shù)：

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

以上代碼的descriptors是從多幅圖像中提取的描述子媒殉，他的類型可以是vector<cv::Mat>或者是vector<vector<cv::Mat>>担敌。create函數(shù)就是具體生成詞袋模型的函數(shù)，下面可以具體看一下create函數(shù)廷蓉。源碼中重載了多種create函數(shù)全封，但是最核心的部分還是void Vocabulary::create (const std::vector<std::vector<cv::Mat> > &training_features )。在該函數(shù)中主要的算法有以下幾個部分桃犬，下面會根據(jù)不同的部分來進(jìn)行分析刹悴。

// 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叉樹節(jié)點(diǎn)的形式

為了提升查找效率，DBoW使用了K叉樹的方式來對描述子進(jìn)行存儲并且查找攒暇。對于樹結(jié)構(gòu)來說土匀，最重要的是需要保存他的父節(jié)點(diǎn)和子節(jié)點(diǎn)，除此之外扯饶，它的id值也可以進(jìn)行存儲恒削。所以DBoW3中池颈，每個節(jié)點(diǎn)的形式代碼所示，整個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

在樹中钓丰，根據(jù)根節(jié)點(diǎn)個數(shù)以及層數(shù)的不同躯砰，樹的節(jié)點(diǎn)共有個，而id值就是從0開始一共有這個多個携丁，而最底層葉子節(jié)點(diǎn)是存儲了每個描述子的信息琢歇，而上面的每一層中的節(jié)點(diǎn)值都代表他們的聚類中心，根據(jù)每一類中心的不同梦鉴，找單詞的時候就比原來效率提高了許多李茫。word_id指的是單詞的id值，他從0開始共有個肥橙，只有葉子節(jié)點(diǎn)才會有這個word id值魄宏。
聚類主要是使用了KMeans++算法，它相較于KMeans多了一個自主選擇初始聚類中心的過程存筏，他們的算法如下所示宠互。

Kmeans++

該算法主要是為了選出合適的聚類中心，因?yàn)閷τ贙means來說椭坚，聚類中心的選取是隨機(jī)的并不能很好的表現(xiàn)出數(shù)據(jù)的特點(diǎn)予跌，所以使用KMeans++可以得到合適的聚類中心，它主要的算法流程為：

1善茎、從數(shù)據(jù)點(diǎn)中均勻隨機(jī)選取一個數(shù)據(jù)作為中心點(diǎn)券册。
2、對于每一個中心點(diǎn)x垂涯，計算其他點(diǎn)與x之間的最短距離D(x)烁焙。
3、如果D(x)越大集币，則證明他被選取為中心點(diǎn)的可能性越大考阱，使用輪盤法選出下一個聚類中心。
4鞠苟、重復(fù)步驟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();  

該段代碼的核心思想就是在總的距離之間隨機(jī)選取一個值，可以想象河质，如果距離的值越大冀惭，在總和之中占據(jù)的比例也越大震叙，隨機(jī)選取得到的點(diǎn)在該區(qū)間的概率也越大，總而言之散休，該隨機(jī)選取得到的值在大值中的可能性也越大媒楼，這樣就有可能選取到與當(dāng)前聚類中心相聚比較遠(yuǎn)的點(diǎn)。如果并不是很理解的話戚丸，可以參考K-means與K-means++划址。在距離計算的時候，該代碼使用的是bit運(yùn)算限府，具體的可以參考Bit Twiddling Hacks夺颤，是一個介紹bit運(yùn)算非常好的網(wǎng)站。

KMeans

KMeans算法的主要步驟為：

1胁勺、隨機(jī)選取得到k個樣本作為聚類中心：（該步驟已經(jīng)通過KMeans++得到）世澜；
2、對于每一個樣本署穗，計算他們與中心點(diǎn)之間的距離寥裂，取最小的距離的中心作為他們的歸類；
3蛇捌、重新計算每個類的中心點(diǎn)抚恒；
4、如果每個樣本的中心都不再變化络拌，則算法收斂俭驮，可以退出；否則返回1春贸。

該算法的主要代碼在Vocabulary::HKmeansStep中混萝，具體操作詳見代碼，這里就不展開討論了萍恕。

樹的生成

比如在第1層得到k個聚類中心以及每個中心中對應(yīng)的特征點(diǎn)集合之后逸嘀，就需要將其生成樹節(jié)點(diǎn)，每個樹節(jié)點(diǎn)產(chǎn)生的形式如下：

// 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
    }

如果層數(shù)沒有到達(dá)L允粤，則再繼續(xù)對每個節(jié)點(diǎn)進(jìn)行聚類崭倘。

// 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 );
            }
        }
    }

單詞的產(chǎn)生

單詞產(chǎn)生的函數(shù)如以下代碼所示，他主要的目的就是給葉子節(jié)點(diǎn)的word_id賦值类垫，并且設(shè)置單詞（描述子）的值司光。

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 ) );
            }
        }
    }
}

設(shè)置節(jié)點(diǎn)權(quán)重

在文本處理中，對于每一個單詞的重要性是不一樣的悉患，比如說常見的字眼“的”残家、“是”等等，他們出現(xiàn)的頻率是很高售躁，可是他們的區(qū)分度并不高坞淮，所以他的并沒有太大的重要性茴晋，而“蜜蜂”、“鹽”等等一些名詞回窘，并不是所有的句子都會存在的诺擅，則他們的區(qū)分度可能就會高一點(diǎn)，重要性也會增加毫玖。因此掀虎，在文件檢索中，一種常用的方法就是TF-IDF（Term Frequency-Inverse Document Frequency）付枫。TF指的是某單詞在一幅圖像中經(jīng)常出現(xiàn)烹玉，它的區(qū)分度就高。而IDF指某單詞在字典中出現(xiàn)的頻率越低阐滩，則分類圖像時區(qū)分度越高二打。之前我一直不知道這個內(nèi)容有啥用，在請教了室友之后知道掂榔，這個權(quán)重可以在原本的特征維數(shù)上再加一維用來表示重要程度继效，這一維數(shù)據(jù)會使得匹配結(jié)果更加的準(zhǔn)確。所以一副圖像就可以表示為：

其中表示TF-IDF的權(quán)重装获，表示圖像中提取得到的描述子瑞信。在DBoW3中，描述子的權(quán)重如以下代碼所示：

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++
        }

    }

}

至此穴豫，字典就正式生成了凡简，描述子的內(nèi)容和權(quán)重存儲在m_words中，而m_nodes存儲了每個節(jié)點(diǎn)的信息精肃。

字典的保存

字典保存的函數(shù)在void Vocabulary::save ( cv::FileStorage &f,const std::string &name ) const中秤涩，具體內(nèi)容就不詳述了。

參考資料

DBow3代碼
視覺SLAM十四講