[学习SLAM] ORB-SLAM中BOW特征匹配
通常估计两帧之间的运动, 我们需要分别计算两帧中的所有特征点, 然后计算特征点之间的匹配关系. 再通过对应特征点的移动情况来估计两帧之间的摄像机运动.
这中间会涉及好很多问题, 至今未能得到有效解决:
提取特征点的类型: 众所周知, 对于自然场景图像, SIFT和SURF特征点具有非常好的特性, 充分考虑了尺度, 光照, 旋转等因素的影响. 然而SIFT, SURF特征的计算非常耗时, 很难满足实时应用的需要. 于是我们只能转而使用质量较差但计算较为简单的图像特征点, 如FAST, ORB等.
特征点匹配的问题: 在确定特征点位置后, 我们可以计算这个特征点的descriptor. 然后在两帧之间两两对比descriptor, 当descriptor之间的distance低于某个阈值时, 便认为这两个特征是同一个点. 然而这里存在两个问题:
(1) 到底distance阈值应该设为多少, 大多凭实验经验获得, 并没有什么理论依据.
(2) 特征点之间两两比对, 计算量非常大. 而且其实有很多比对是不需要的. 目前的解决方案主要是假设两帧之间的相对运动不大, 于是可以在第一帧的特征点位置附近来搜索对应特征即可. 但是即使如此, 计算量还是难以满足实时需要. 所以在ORB-SLAM中, 还有很多其它的工程上的优化被考虑进去.
刚开始接触ORB的时候, 误解了作者对bow模块的使用, 还以为bow只是简单地用于loop closure detection, 后面仔细查看代码后发现并没有那么简单.
在作者使用的Bag of Word词典中, 词典是一个事先训练好的分类树, 而BOW特征有两种:
1. BowVector: 即是分类树中leaf的数值与权重(叶)
2. FeatureVector: 是分类树中leaf的id值与对应输入ORB特征列表的特征序号.
ORB SLAM中, 在利用帧间所有特征点比对初始化地图点以后, 后面的帧间比对都采用Feature vector.进行, 而不再利用所有特征点的descriptor两两比对. 这样做的好处当然是加快了处理速度, 但是信息再次被压缩抽象化, 不可避免会造成性能降低. 然而根据作者在之前的文章[1]及github上的描述, 对一幅图片的BOW特征抽取可以在5ms以内完成, 而在19000张图片构成的database中, 图片搜索可以在10ms内完成, 且保证False Positive为0. 具体的实验我没有进行验证, Whatever, ORB-SLAM证明了这样处理是有效的, 至少在数据集上, 及速度较慢的应用上, 可以实现令人满意的精度.
其实处理非常简单, 在已经获得图像特征点集合的基础上, 再根据词典, 对每个特征做一次分类. 再对第二幅图像提取特征, 然后也根据词典, 也对这幅图像的所有特征进行分类. 用分类后的特征类别代替原本的特征descriptor, 即用一个数字代替一个向量进行比对, 显然速度可以大大提升.
这一方案在ORB SLAM整个project中被大量应用, 除了初始化时, 因为需要较准确的地图点及初始位姿估计, 而采用descriptor进行暴力比对. 后面的在SearchForTriangulation, SearchByBoW的过程中, 都是直接使用Feature vector作为特征的值的. 在实际应用中发现效果十分不错.
然而这一种方法有一个最恼人的问题就是, 每次在初始化系统的时候必须载入一个100多m的词典库, 在我的android orb下测试, 这个载入的过程长达2分钟以上.
当前使用的词典是使用K-mean（KNN的说法可能有误，正解为K-mean）算法生成的分类树, 学过机器学习的童鞋都知道, 这是一种instance based的聚类算法, 分类速度快, 但是所需存储空间大. 所以如果使用其它的聚类算法生成分类器, 不知是否还能达到real time的需求.
另外, 是否可以通过一些online learning的方法进行词典学习, 或者把特征descriptor转为二进制表达, 加速运算. 这些都是待考究的问题.
[1]Gálvez-López, Dorian, and Juan D. Tardos. “Bags of binary words for fast place recognition in image sequences.” Robotics, IEEE Transactions on 28.5 (2012): 1188-1197.
1、视觉词袋模型
特征点是由兴趣点和描述子表达的，把具有某一类特征的特征点放到一起就构成了一个单词（word），由所有这些单词就可以构成字典（vocabulary）了，有了字典之后，给定任意特征fi，只要在字典中逐层查找（使用的是汉明距离），最后就能找到与之对应的单词wj了.
2、单词的权重
每一类用该类中所有特征的平均特征（meanValue）作为代表，称为单词（word）。每个叶节点被赋予一个权重. 比较常用的一种权重是TF-IDF.(补充：TF-IDF（term frequency–inverse document frequency）是一种用于信息检索与数据挖掘的常用加权技术。TF意思是词频(Term Frequency)，IDF意思是逆文本频率指数(Inverse Document Frequency)。)
- 如果某个词或短语在一篇文章中出现的频率
TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类. -
TF-IDF实际上是TF * IDF，TF代表词频(Term Frequency)，表示词条在文档d中出现的频率。IDF代表逆向文件频率(Inverse Document Frequency)。如果包含词条t的文档越少，IDF越大，表明词条t具有很好的类别区分能力.
DBoW2作者提供了TF、IDF、BINARY、TF-IDF等权重作为备选，默认为TF-IDF.
2、构造离线词典
orb-slam中的离线词典就是那个比较大的文件ORBvoc.txt，它是DBoW2作者使用orb特征，使用大量图片训练的结果.
2.1 存储结构
对每一幅训练图像，提取特征点，将所有这些特征点，通过对描述子（descriptors）聚类的方法，如，k-means++，将其分成若干类（每一类即表示一个单词），即实现聚类的过程，但是由于我们使用的描述子是256维的，那么这个类别（单词）数量不能太小（不然造成误匹配），至少是成千上万，那么这就带来一个查找效率问题，O(N)肯定是不行了，所以视觉BoW一般使用树的结构进行存储（以空间换时间呗），时间效率将达到log(N)级别.
2.2 聚类实现
由于单词过多，需要提高查找效率，简单的方法是进行二分法、N叉树等，使用k叉树，深度为d，一共可以构成kd个单词，聚类过程如下：
- 从训练图像中抽取特征
- 将抽取的特征用 k-means++ 算法聚类（使用汉明距离），将描述子空间划分成 k 类
- 将划分的每个子空间，继续利用 k-means++ 算法做聚类
- 重复Lw
- Lw次上述过程，将描述子建立成树形结构，如下图所示
3、图像识别
3.1 查找
离线生成视觉词典以后，在slam过程中（相对于离线，这里也叫，在线查找），对一新进来的图像帧，将其中每个特征点都从单词树根节点往下遍历，取汉明距离最小的节点接着往下遍历直到叶节点，就可以找到位于叶子节点的单词了.
为了查找方便，DBoW2使用了两种数据结构，逆向索引inverse index和正向索引direct index.
使用下面的代码，计算词包mBowVec和mFeatVec，其中mFeatVec记录了在第4层所有node节点正向索引.
void Frame::ComputeBoW()
{
if(mBowVec.empty())
{
vector<cv::Mat> vCurrentDesc = Converter::toDescriptorVector(mDescriptors);
mpORBvocabulary->transform(vCurrentDesc,mBowVec,mFeatVec,4); //第四层
}
}
3.1 正向索引，用于加速匹配
正向索引的数据结构如下，继承自std::map，NodeId为第4层上node节点的编号，其范围在[0,kl)内，l表示当前层数（这里以最上层为0层），std::vector<unsigned int>是所有经过该node节点特征编号集合。
/// Vector of nodes with indexes of local features
class FeatureVector: public std::map<NodeId, std::vector<unsigned int> >
TrackReferenceKeyFrame() 函数中的 SearchByBoW() 对pKF和F中属于同一node的特征点，进行快速匹配. 过程如下:
DBoW2::FeatureVector::const_iterator KFit = vFeatVecKF.begin();
DBoW2::FeatureVector::const_iterator Fit = F.mFeatVec.begin();
DBoW2::FeatureVector::const_iterator KFend = vFeatVecKF.end();
DBoW2::FeatureVector::const_iterator Fend = F.mFeatVec.end();
while(KFit != KFend && Fit != Fend)
{
/*【步骤1】： 分别取出属于同一node的ORB特征点(只有属于同一node，才有可能是匹配点)*/
if(KFit->first == Fit->first)
{
const vector<unsigned int> vIndicesKF = KFit->second;
const vector<unsigned int> vIndicesF = Fit->second;
/*【步骤2】： 遍历KF中属于该node的特征点*/
for(size_t iKF=0; iKF<vIndicesKF.size(); iKF++)
{
const unsigned int realIdxKF = vIndicesKF[iKF];
MapPoint* pMP = vpMapPointsKF[realIdxKF]; // 取出KF中该特征对应的MapPoint
......
这种加速特征匹配的方法在ORB-SLAM2中被大量使用。注意到，
- 正向索引的层数如果选择第
0层（根节点），那么时间复杂度和暴力搜索一样 - 如果是叶节点层，则搜索范围有可能太小，错失正确的特征点匹配
- 作者一般选择第二层或者第三层作为父节点（
L=6），正向索引的复杂度约为O(N^2/K^m)
作者用反向索引记录每个叶节点对应的图像编号。当识别图像时，根据反向索引选出有着公共叶节点的备选图像并计算得分，而不需要计算与所有图像的得分。
- 为图像生成一个表征向量v，图像中的每个特征都在词典中搜索其最近邻的叶节点。所有叶节点上的
TF-IDF权重集合构成了BoW向量v - 根据BoW向量，计算当前图像和其它图像之间的L1
- L1范数，有了距离定义，即可根据距离大小选取合适的备选图像
s(v1, v2)=1−12∣v1∣v1∣−v2∣v2∣∣- s(v1, v2)=1−21∣∣v1∣v1−∣v2∣v2∣
使用词袋模型，在重定位过程中找出和当前帧具有公共单词的所有关键帧，代码如下：
// words是检测图像是否匹配的枢纽，遍历该pKF的每一个word for(DBoW2::BowVector::const_iterator vit=F->mBowVec.begin(), vend=F->mBowVec.end(); vit != vend; vit++) { // 提取所有包含该word的KeyFrame list<KeyFrame*> &lKFs = mvInvertedFile[vit->first]; for(list<KeyFrame*>::iterator lit=lKFs.begin(), lend= lKFs.end(); lit!=lend; lit++) { KeyFrame* pKFi=*lit; if(pKFi->mnRelocQuery!=F->mnId)// pKFi还没有标记为pKF的候选帧 { pKFi->mnRelocWords=0; pKFi->mnRelocQuery=F->mnId; lKFsSharingWords.push_back(pKFi); } pKFi->mnRelocWords++; } }