原文链接:VSLAM系列原创09讲 | 如何在线生成BoW词袋向量?原理+代码详解
本文系ORB-SLAM2原理+代码实战系列原创文章,对应的视频课程见: ORB-SLAM2总共60讲已经全部上线可观看!
代码注释地址:
https://github.com/electech6/ORB_SLAM2_detailed_comments
VSLAM系列原创01讲 | 深入理解ORB关键点提取:原理+代码
VSLAM系列原创02讲 | ORB描述子如何实现旋转不变性?原理+代码
VSLAM系列原创03讲 | 为什么需要ORB特征点均匀化?
VSLAM系列原创04讲 | 四叉树实现ORB特征点均匀化分布:原理+代码
VSLAM系列原创05讲 | 单目初始化中如何进行特征匹配?原理+代码
VSLAM系列原创07讲 | 词袋有什么用?ORB特征点构建BoW是否靠谱?
VSLAM系列原创08讲 | 如何离线训练BoW字典?终于搞懂了!
接上回继续。。。
在线生成词袋向量
师兄:以上是离线生成训练字典的过程。在ORB-SLAM2中,对于新来的一帧图像,我们会利用上面的离线字典给当前图像在线生成词袋向量。具体流程是这样的:
小白:图中的level up是什么意思?
师兄:可以简单的将level up理解为搜索范围。每个描述子转化为单词后会包含一个属性叫做单词的节点ID(图中的word’s node id),这个节点ID距离叶子的层级就是level up。以后特征匹配的时候,只在该单词的节点ID内部搜索即可。如果这个level up设置比较大,单词的节点ID会比较靠近根节点,那么搜索范围就会扩大,极端的就是在整个字典树里搜索,那肯定相当慢;但是如果这个level up设置的比较小,单词的节点ID会比较靠近叶子,那么很可能搜不到匹配的特征点。还是拿前面国家机构的例子来类比,比如我想在整个国家寻找一个人(单词),这个单词的节点ID就相当于我的搜索范围,是在某个省级范围还是村级范围搜索。如果是省级范围,那搜索效率就很低,如果是在村级范围,搜索是很快,但是如果要找的人是在隔壁村,那就无法搜索到。因此level up要设置为一个合适的值,在ORB-SLAM2里level up=3。
确定一个特征描述子的单词ID、权重、单词所属的节点(距离叶子深度为level up深度的节点)ID ,对应的实现代码见:
/**
* @brief 确定一个特征描述子的单词ID和权重,单词所属的节点(距离叶子为level up深度的节点)ID
* @param[in] feature 特征描述子
* @param[in & out] word_id 单词ID
* @param[in & out] weight 单词权重
* @param[in & out] nid 单词所属的节点(距离叶子为level up深度的节点)ID
* @param[in] levelsup 单词距离叶子的深度
*/
template<class TDescriptor, class F>
void TemplatedVocabulary<TDescriptor,F>::transform(const TDescriptor &feature,
WordId &word_id, WordValue &weight, NodeId *nid, int levelsup) const
{
vector<NodeId> nodes;
typename vector<NodeId>::const_iterator nit;
// m_L表示树的深度
// nid_level表示当前特征点转化为单词所属的节点ID
const int nid_level = m_L - levelsup;
if(nid_level <= 0 && nid != NULL) *nid = 0; // 根节点
NodeId final_id = 0;
int current_level = 0;
// 开始沿着字典树进行搜索
do
{
++current_level;
nodes = m_nodes[final_id].children;
final_id = nodes[0];
// 取当前节点内第一个子节点的描述子距离作为初始化最佳距离
double best_d = F::distance(feature, m_nodes[final_id].descriptor);
// 遍历nodes中所有的描述子,找到最小距离对应的描述子
for(nit = nodes.begin() + 1; nit != nodes.end(); ++nit)
{
NodeId id = *nit;
double d = F::distance(feature, m_nodes[id].descriptor);
if(d < best_d)
{
best_d = d;
final_id = id;
}
}
// 记录当前描述子所属的节点ID,它距离叶子深度为levelsup
if(nid != NULL && current_level == nid_level)
*nid = final_id;
} while( !m_nodes[final_id].isLeaf() );
// 取出字典树中距离当前特征描述子距离最小的那个节点的单词ID和权重赋予该特征点
word_id = m_nodes[final_id].word_id;
weight = m_nodes[final_id].weight;
}
一幅图像里所有特征点按照上述方法,通过字典树最终转化为两个向量BowVector和FeatureVector,详细的代码见:
/**
* @brief 将一幅图像所有的特征点转化为BowVector和FeatureVector
* @param[in] features 图像中所有的特征点
* @param[in & out] v BowVector
* @param[in & out] fv FeatureVector
* @param[in] levelsup 单词距离叶子的深度
*/
template<class TDescriptor, class F>
void TemplatedVocabulary<TDescriptor,F>::transform(
const std::vector<TDescriptor>& features,
BowVector &v, FeatureVector &fv, int levelsup) const
{
v.clear();
fv.clear();
if(empty())
{
return;
}
// 根据选择的评分类型来确定是否需要将BowVector归一化
LNorm norm;
bool must = m_scoring_object->mustNormalize(norm);
typename vector<TDescriptor>::const_iterator fit;
// 代码里使用的权重类型是TF_IDF
if(m_weighting == TF || m_weighting == TF_IDF)
{
unsigned int i_feature = 0;
// 遍历图像中所有的特征点
for(fit = features.begin(); fit < features.end(); ++fit, ++i_feature)
{
WordId id; // 单词节点
NodeId nid; // 单词所属的节点(距离叶子为level up深度的节点)ID,用于限制搜索范围
WordValue w; // 单词对应的权重
// 确定一个特征描述子的单词ID和权重,单词所属的节点(距离叶子为level up深度的节点)ID
// id:单词ID,w:单词权重,nid:单词所属节点ID
transform(*fit, id, w, &nid, levelsup);
if(w > 0)
{
// 如果单词权重大于0,将其添加到BowVector和FeatureVector
v.addWeight(id, w);
fv.addFeature(nid, i_feature);
}
}
// ...
}
// ...
}
小白:我们费那么大劲,把图像里所有特征点转化为两个向量BowVector和FeatureVector,有什么具体作用呢?
师兄:先给出结论,这些操作相当于把当前图像信息进行了压缩,这两个向量对特征点快速匹配、闭环检测、重定位意义重大。下面具体来分析一下:
先说说BowVector,它的数据结构是:
std::map<WordId, WordValue>
其中 WordId 和 WordValue 表示单词Word在所有叶子中距离最近叶子的ID和权重,这和我们前面介绍的一致。对于同一个单词ID,它的权重是累加并不断更新的,见代码
/**
* @brief 更新BowVector中的单词权重
*
* @param[in] id 单词的ID
* @param[in] v 单词的权重
*/
void BowVector::addWeight(WordId id, WordValue v)
{
// 返回指向大于等于id的第一个值的位置
BowVector::iterator vit = this->lower_bound(id);
// 根据新增加的单词是否在BowVector里来更新权重
if(vit != this->end() && !(this->key_comp()(id, vit->first)))
{
// 如果id=vit->first,说明是同一个单词,累加更新权重
vit->second += v;
}
else
{
// 如果该单词ID不在BowVector中,作为新成员添加进来
this->insert(vit, BowVector::value_type(id, v));
}
}
再来说说FeatureVector,它的数据结构是:
std::map<NodeId, std::vector<unsigned int> >
其中NodeId并不是该叶子直接的父节点id,而是距离叶子深度为level up对应的节点的id,这在前面也反复提到了,对应字典树图示里的 Word’s node id。在特征匹配时,搜索该单词的匹配点的时候是在和它具有同样node id下面所有子节点中的单词进行匹配,搜索区域见图示中的Word’s search region。所以搜索范围大小是根据level up来确定的,level up 值越大,搜索范围越广,速度越慢;level up 值越小,搜索范围越小,速度越快,但能够匹配的特征就越少。
其中第2个参数std::vector中实际存的是NodeId下所有特征点在图像中的索引。见代码
/**
* @brief 把node id下所有的特征点的索引值归属到它的向量里
*
* @param[in] id 节点ID,内部包含很多单词
* @param[in] i_feature 特征点在图像中的索引
*/
void FeatureVector::addFeature(NodeId id, unsigned int i_feature)
{
// 返回指向大于等于id的第一个值的位置
FeatureVector::iterator vit = this->lower_bound(id);
// 将同样node id下的特征点索引值放在一个向量里
if(vit != this->end() && vit->first == id)
{
// 如果这个node id已经创建,可以直接插入特征点索引
vit->second.push_back(i_feature);
}
else
{
// 如果这个node id还未创建,创建后再插入特征点索引
vit = this->insert(vit, FeatureVector::value_type(id, std::vector<unsigned int>() ));
vit->second.push_back(i_feature);
}
}
(左右滑动看完整代码)
* * *