Chapter12 回环检测
- 词袋模型(BoW)
- 字典
- 相似度的计算
- 理论部分
- 实践:相似度计算
- 相似性评分的处理
- 关键帧的处理
- 检测之后的验证
词袋模型(BoW)
- 确定BoW的单词,从而组成字典。
- 确定一副图像中出现了哪些在字典中定义的概念,从而把一副图像转换成了一个向量的描述。
- 比较上一步中描述的相似程度。
字典
字典的结构
- 字典生成问题类似于一个聚类问题,聚类问题常用K-means方法:根据K-means,我们可以把已经提取的大量特征点聚类成一个含有k个单词的字典。
- 字典的存储结构:
使用一种k叉树来表达字典,假设我们有N个特征点,希望构建一个深度为d,每次分叉为k的树,那么做法如下:
- 在根节点,用K-means把所有样本聚成k类,这样得到了第一层。
- 对第一层的每个节点,把属于该节点的样本再聚成N类,得到下一层。
- 以此类推,最后得到叶子层。叶子层即所谓的Words
- 经过上述步骤,构建了一个k分支,深度为d的树,可以容纳kd个单词,在查找某个特定的单词时,只需将它与每个中间节点的聚类中心比较(一共d次),即可找到最后的单词,保证了对数级别的查找效率。
实践:创建字典
- 安装BoW库,下载地址:https://github.com/rmsalinas/DBow3
它是一个cmake工程,编译并且安装它。 - 完整代码:
feature_training.cpp
//2019.08.18
#include "DBoW3/DBoW3.h"
#include
#include
#include
#include
#include
#include using namespace cv;
using namespace std;int main(int argc,char **argv)
{//read the imagecout <<"reading images..." < images;for(int i&#61;0;i<10;i&#43;&#43;){string path &#61; "../data/" &#43; to_string(i&#43;1) &#43; ".png";images.push_back(imread(path));}//detect ORB featurescout <<"detecting ORB features..."< detector &#61; ORB::create();vector descriptors;for(Mat& image:images){vector keypoints;Mat descriptor;detector->detectAndCompute(image,Mat(),keypoints,descriptor);descriptors.push_back(descriptor);}//create vocabularycout<<"creating vocabulary..."<}
CMakeLists.txt
cmake_minimum_required( VERSION 2.8 )
project( loop_closure )set( CMAKE_BUILD_TYPE "Release" )
set( CMAKE_CXX_FLAGS "-std&#61;c&#43;&#43;11 -O3" )# opencv
find_package( OpenCV REQUIRED )
include_directories( ${OpenCV_INCLUDE_DIRS} )# dbow3
# dbow3 is a simple lib so I assume you installed it in default directory
set( DBoW3_INCLUDE_DIRS "/usr/local/include" )
set( DBoW3_LIBS "/usr/local/lib/libDBoW3.a" )add_executable( feature_training feature_training.cpp )
target_link_libraries( feature_training ${OpenCV_LIBS} ${DBoW3_LIBS} )
运行结果&#xff1a;
相似度的计算
理论部分
我们希望对单词的区分性或重要性加以评估&#xff0c;给它们不同的权值以起到更好的效果。在文本检索中&#xff0c;常用的一种做法称为TF-IDF(Term Frequency-Inverse Document Frequency)。
TF部分的思想是&#xff0c;某单词在一副图像中经常出现&#xff0c;它的区分度就高。
IDF的思想是&#xff0c;某单词在字典中出现的频率越低&#xff0c;则分类图像时区分度就越高。
在词袋模型中&#xff0c;在建立字典时可以考虑IDF部分。我们统计某个叶子节点wi中的特征数量相对于所有特征数量的比例作为IDF部分。假设所有的特征数量为n&#xff0c;wi中的特征数量为ni,那么该单词的IDF为&#xff1a;IDFi&#61;log(n/ni)
用来描述一个单词的特征点数量越少&#xff0c;说明这个单词越纯净&#xff0c;区分度也越好。
另一方面&#xff0c;TF部分则是指某个特征在单幅图像中出现的频率。假设图像A中单词wi出现了ni次&#xff0c;而一共出现的单词次数为n&#xff0c;那么TF为&#xff1a;TFi&#61;ni/n
在一幅图像中&#xff0c;某个单词出现的次数相比于它在所有图像中出现的次数占比越大&#xff0c;那么这个单词区分度越高。
某一个单词的权重定义为TF与IDF之积&#xff1a;
etai &#61; TFi×IDFi
考虑权重之后&#xff0c;对于某幅图像A&#xff0c;它的特征点可对应到许多个单词&#xff0c;组成它的Bag-of-Words:
A &#61; {(w1,etai),(w2,etai),…,(wN,etaN)} &#61; vA
由于相似的特征可能落到同一个类中&#xff0c;因此实际的**vA中会存在大量的零。这个向量vA**是一个稀疏的向量&#xff0c;它的非零部分指示了图像A中含有哪些单词&#xff0c;而这些部分的值为TF-IDF的值。
给定vA&#xff0c;vB&#xff0c;用L1范数计算它们的差异&#xff1a;
实践&#xff1a;相似度计算
loop_closure.cpp
//2019.08.18
#include "DBoW3/DBoW3.h"
#include
#include
#include
#include
#include
#include using namespace cv;
using namespace std;int main(int argc,char **argv)
{//read the images and databasecout <<"reading database"< images;for(int i&#61;0;i<10;i&#43;&#43;){string path &#61; "../data/" &#43; to_string(i&#43;1) &#43; ".png";images.push_back(imread(path));}//NOTE: in this case we are comparing images with a vocabulary generated by themselves, this may leed to overfitting.//detect ORB featurescout <<"detecting ORB features..."< detector &#61; ORB::create();vector descriptors;for(Mat& image:images){vector keypoints;Mat descriptor;detector->detectAndCompute(image,Mat(),keypoints,descriptor);descriptors.push_back(descriptor);}//we can compare the images directly or we can compare one image to a database//imagescout<<"comparing images with images"<}
CMakeLists.txt
cmake_minimum_required( VERSION 2.8 )
project( loop_closure )set( CMAKE_BUILD_TYPE "Release" )
set( CMAKE_CXX_FLAGS "-std&#61;c&#43;&#43;11 -O3" )# opencv
find_package( OpenCV REQUIRED )
include_directories( ${OpenCV_INCLUDE_DIRS} )# dbow3
# dbow3 is a simple lib so I assume you installed it in default directory
set( DBoW3_INCLUDE_DIRS "/usr/local/include" )
set( DBoW3_LIBS "/usr/local/lib/libDBoW3.a" )add_executable( loop_closure loop_closure.cpp )
target_link_libraries( loop_closure ${OpenCV_LIBS} ${DBoW3_LIBS} )
运行结果&#xff1a;
相似性评分的处理
绝对相似性评分鲁棒性不是很好&#xff0c;我们取一个先验相似度s(vt,vt-deltat),它表示某时刻关键帧图像与上一时刻的关键帧的相似性。然后&#xff0c;其他的分值都根据这个值进行归一化&#xff1a;
如果当前帧与之前的某关键帧的相似度超过当前帧与上一个关键帧相似度的3倍&#xff0c;就认为可能存在回环。
关键帧的处理
如果关键帧选得太近&#xff0c;那么将导致两个关键帧之间的相似性过高&#xff0c;相比之下不容易检测出历史数据中的回环。比如&#xff0c;检测结果经常是第n帧和第n-2帧&#xff0c;第n-3帧最为相似&#xff0c;这种结果似乎太平凡了&#xff0c;意义不大。从实践来说&#xff0c;用于回环检测的帧最好是稀疏一些&#xff0c;彼此之间不太相同&#xff0c;又能涵盖整个环境。
另一方面&#xff0c;如果成功检测到了回环&#xff0c;比如说出现在第1帧和第n帧。那么很可能第n&#43;1帧、第n&#43;2帧都会和第1帧之间构成回环。但是&#xff0c;确认第1帧和第n帧之间存在回环对轨迹优化是有帮助的&#xff0c;而再接下去的第n&#43;1帧、第n&#43;2帧都会和第1帧构成回环产生的帮助就没那么大了。所以&#xff0c;我们会把"相近"的回环聚成一类&#xff0c;使算法不要反复地检测同一类的回环。
检测之后的验证
词袋的回环检测算法完全依赖于外观而没有利用任何的几何信息&#xff0c;这导致外观相似的图像容易被当成回环。并且由于词袋不在乎单词顺序&#xff0c;只在意单词有无的表达方式&#xff0c;更容易引发感知偏差。所以&#xff0c;在回环检测之后&#xff0c;我们通常还会有一个验证步骤。
验证的方法有很多。其一是设立回环的缓存机制&#xff0c;认为单次检测到的回环并不足以构成良好的约束&#xff0c;而在一段时间中一直检测到的回环&#xff0c;才认为是正确的回环。这可以看成时间一致性检测。
另一方法是在空间上的一致性检测&#xff0c;即对回环检测到的两个帧进行特征匹配&#xff0c;估计相机的运动。然后&#xff0c;再把运动放到之前的位姿图中&#xff0c;检查与之前的估计是否有很大的出入。总之&#xff0c;验证部分通常是必须的&#xff0c;但如何实现却是见仁见智的问题。