DBoW:字典的生成

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

词袋模型的生成

总的来说,如果要用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

在树中,根据根节点个数以及层数的不同,树的节点共有\frac{k^{(L+1)}}{k-1}个,而id值就是从0开始一共有这个多个,而最底层叶子节点是存储了每个描述子的信息,而上面的每一层中的节点值都代表他们的聚类中心,根据每一类中心的不同,找单词的时候就比原来效率提高了许多。word_id指的是单词的id值,他从0开始共有k^L个,只有叶子节点才会有这个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个样本作为聚类中心:c_1, c_2,...,c_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指某单词在字典中出现的频率越低,则分类图像时区分度越高。之前我一直不知道这个内容有啥用,在请教了室友之后知道,这个权重可以在原本的特征维数上再加一维用来表示重要程度,这一维数据会使得匹配结果更加的准确。所以一副图像就可以表示为:
I = \{(w_1,\eta _1) , ...,(w_N,\eta _N)\} = \mathbf{v}_I
其中w_i表示TF-IDF的权重,\eta_i表示图像中提取得到的描述子。在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十四讲

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,386评论 6 479
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,939评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,851评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,953评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,971评论 5 369
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,784评论 1 283
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,126评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,765评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,148评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,744评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,858评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,479评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,080评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,053评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,278评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,245评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,590评论 2 343

推荐阅读更多精彩内容