DBOW概要理解与记录

前言

DBOW作为一种视觉回环技术被广泛应用在各类VSLAM框架中，之前的经验主要集中在使用和抽象理解层面，近期花了一些时间仔细阅读了相关论文和源码，这里做一些记录。

两个关键概念

Vocabulary

通过预先训练得到的词汇库，以树状数据结构保存，便于后续查询，如下图黄色部分：
在这里插入图片描述

训练过程：通过数据集提取每张图片feature构成一个feature集，将feature集进行按层级的kmeans++聚类（每一层都进行一次聚类，得到centroid node作为节点），最终获取到d层共w个words，每一个word根据在数据集中的频次计算其weight并保存，待后续使用。
查询过程：从根节点开始，将待查询feature（f）与每层的node计算hamming distance，选择最小值的node继续往下，依次从上到下贯穿整棵树，直到叶子节点，就得到其对应的word。

Dataset

上图中的蓝色部分，在实际使用中，需要实时构建数据库，用于后续查找回环。

构建数据库：采集到的每张图片提取全部feature，所有feature通过vocabulary查询获取对应word，所有word构成这张图片对应的Bowvector，同时，根据word的weight与单张图片中该word出现比例可以计算得到value，这些信息将会构成一张反向索引表（所有包含某个word的图片索引）和一张正向索引表（每张图片保护的word索引及alue），这两张表实际上就是数据库，用于后面提取历史keyframe对应的图片的Bowvector。

回环检测过程

1、构建自己的vocabulary并保存，这一步一般可以省略，可以直接使用作者提供的一份vocabulary file，如果效果不佳，可以考虑自己构建。
2、运行自己的VIO算法，每一个keyframe对应的图片加入到dataset，实时构建dataset，代码如下：

inline DBow::EntryId DBow::Database::AddEntry(const vector<float>& features)
{
	DBow::BowVector v;
	m_voc->Transform(features, v, false);
	return _AddEntry(v);
}

EntryId Database::_AddEntry(BowVector &v)
{
	VocParams::ScoringType norm;
	if(VocParams::MustNormalize(m_voc->Scoring(), norm)){
		// vectors are stored normalized if needed
		v.Normalize(norm);
	}

	EntryId eid = m_nentries;

	// update inverted file
	BowVector::const_iterator it;
	for(it = v.begin(); it != v.end(); it++){
		// eids are in ascending order in the index
		m_index[it->id].push_back(IFEntry(eid, it->value));
	}

	m_nentries++;

	return eid;
}

3、每一个新的keyframe对应的图片，加入dataset查询回环，具体过程是，将图片提取全部feature并通过vocabulary转换得到Bowvector，通过dataset查询相关的历史keyframe，计算当前keyframe与历史keyframe对应Bowvector的loss，计算算法有很多种类，如下：

	switch(info.Parameters->Scoring){
		
		case VocParams::L1_NORM:
			doQueryL1(v, ret, max_results, info.Parameters->ScaleScore);
			break;

		case VocParams::L2_NORM:
			doQueryL2(v, ret, max_results, info.Parameters->ScaleScore);
			break;

		case VocParams::CHI_SQUARE:
			doQueryChiSquare(v, ret, max_results, info.Parameters->ScaleScore);
			break;

		case VocParams::KL:
			doQueryKL(v, ret, max_results, info.Parameters->ScaleScore);
			break;

		case VocParams::BHATTACHARYYA:
			doQueryBhattacharyya(v, ret, max_results, info.Parameters->ScaleScore);
			break;

		case VocParams::DOT_PRODUCT:
			doQueryDotProduct(v, ret, max_results, info.Parameters->ScaleScore);
			break;
	}

得到score，对score进行排序获取candidates，如下：

void Database::doQueryL1(const BowVector &v, QueryResults &ret, 
						 const int max_results, const bool scale_score) const
{
	BowVector::const_iterator it;
	IFRow::const_iterator rit;
	QueryResults::iterator qit;
	
	for(it = v.begin(); it != v.end(); it++){
		WordId wid = it->id;
		WordValue qvalue = it->value;
		
		const IFRow& row = m_index[wid];

		for(rit = row.begin(); rit != row.end(); rit++){
			EntryId eid = rit->id;
			WordValue dvalue = rit->value;

			// scoring-dependent value
			double value = fabs(qvalue - dvalue) - fabs(qvalue) - fabs(dvalue);

			// check if this entry is already in the returning vector
			qit = find(ret.begin(), ret.end(), eid);

			if(qit == ret.end()){
				// insert
				ret.push_back(Result(eid, value));
			}else{
				// update
				qit->Score += value; 
			}
		} // for each inverted row 
	} // for each word in features	

	// resulting "scores" are now in [-2 best .. 0 worst]
	
	// sort vector in ascending order
	// (scores are inverted now --the lower the better--)
	sort(ret.begin(), ret.end());

	// cut vector
	if((int)ret.size() > max_results) ret.resize(max_results);

	// complete score
	// ||v - w||_{L1} = 2 + Sum(|v_i - w_i| - |v_i| - |w_i|) 
	//		for all i | v_i != 0 and w_i != 0 
	// (Nister, 2006)
	if(scale_score){
		for(qit = ret.begin(); qit != ret.end(); qit++) 
			qit->Score = -qit->Score/2.0;
	}else{
		for(qit = ret.begin(); qit != ret.end(); qit++) 
			qit->Score = 2.0 + qit->Score;
	}
}