基于视觉字典的移动机器人闭环检测方法研究

崔大成，曾连荪

（上海海事大学信息工程学院，上海201306）

基于视觉字典的移动机器人闭环检测方法研究

崔大成，曾连荪

（上海海事大学信息工程学院，上海201306）

针对移动机器人同步定位和地图构建（SLAM）的闭环检测问题，提出了一种基于视觉字典的闭环检测方法。该方法首先使用SURF算法对每一帧图像进行特征提取，生成视觉单词，构建视觉字典树，再基于“词袋”（Bag of Words，BoW）对场景建模，通过计算图像视觉单词的匹配度估计图像间的相似度。为提高闭环检测的成功率，运用贝叶斯滤波与相似度来计算闭环假设的后验概率分布。同时，为提高系统的实时性，引入了内存管理机制。实验结果显示该方法是有效的。

SLAM；视觉单词；闭环检测；内存管理

0 引言

机器人学是一门综合学科，代表着目前高技术的发展前沿，移动机器人作为机器人研究领域的一个重要分支，在军事、生产自动化等许多领域都有广泛的应用，具有重要的实用价值，已经成为机器人领域的研究热点之一[1-2]。自主导航作为移动机器人的关键技术，是机器人在没有外部环境先验知识的帮助下，依赖自身的传感器实现地图创建和精确定位。闭环检测是机器人研究的又一重要内容，用以判断机器人当前的位置是否为之前已经经历过的历史环境区域。有效的场景模型是机器人视觉SLAM闭环检测[3-6]的关键。BoW[7-8]是一种非常有效的场景建模方法，它通过提取图像局部特征，并对其分类构建视觉字典树[9]。任何一幅图像都可以通过视觉字典中的单词集合进行表示。在视觉闭环检测方面，Cummins等人提出了基于拓扑外观的概率闭环检测FABMAP[10]方法。本文首先使用SURF算法提取图像的局部特征，再基于BoW方法构建场景模型，创建视觉字典树，并根据图像间的相似度进行图像预处理，最后基于贝叶斯滤波更新闭环检测的后验概率，提高闭环检测的准确性；同时引入内存管理机制，提高闭环检测的实时性，增强系统的执行效率。

1 基于视觉字典的场景模型表示

借鉴文本处理领域中的“词袋法”，使用BoW方法将图像的连续特征离散化，用一组无序的局部特征集合表示图像。BoW只强调用维数相同而权重不同的向量描述来表示视觉特征，忽略它们之间的空间位置关系，是视觉SLAM场景表示的一种有效的建模方法。

本文提出了基于BoW的场景表示方法，其具体过程可分为3步：（1）使用SURF算法提取图像局部特征；（2）使用KD-Tree索引方法创建视觉字典树；（3）投影图像特征到字典树，计算图像间的相似度。基于BoW，一幅图像就可以通过对应的视觉单词进行表示，这不仅保存了图像的局部特征，也节约了图像的存储空间。

1.1 字典的创建

创建BoW的目的是为了将相似的特征描述向量划分为相同的视觉单词，通常采用的表示方法有：KMeans算法[11]、近似K-Means算法和Mean-Shift算法等，其主要就是对局部特征点聚类，每个聚类中心代表一个视觉单词。该算法对于高维局部特征，效率下降，稳定性也降低。Moosmann等人则借鉴随机决策树和随机森林算法思想，提出了随机聚类森林方法，减弱了视觉字典生成过程中的随机性，但其时间复杂度高且占用内存大。为了获得更加准确的视觉字典分类和提高视觉字典的生成效率，本文基于随机聚类森林算法，使用随机KD-Tree索引方法，具体实现过程如下所述：

首先，假设在t时刻获取图像It，通过SURF算法提取到图像的M个视觉特征集合{Fm}（0＜m≤M），集合中的每个视觉特征Fm都是64维。由于系统受外部噪声等因素影响，需要对视觉特征进行预筛选；再根据筛选结果，使用KD-Tree方法创建视觉字典树；最后使用最近邻距离比算法，更新视觉字典。设此时视觉字典中有N个视觉单词，集合为{Vn}（0＜n≤N）。

式（1）是对视觉特征的预筛选，只提取响应强度不小于Tresponse的视觉特征。同时，如果提取当前场景图像的视觉特征与平均每幅场景图像的视觉特征之比小于Tbad，则认为该场景表示不合格。TmaxFeatures是提取一幅场景图像最大的视觉特征数。

式（2）表示，基于视觉字典对当前视觉特征使用最近距离比算法，如果RNNDR＜TNNDR（最近距离比阈值），则将当前两个视觉特征看成是一个视觉单词，更新视觉字典。

1.2 基于视觉字典的图像相似度计算方法

基于BoW图像表示，如果两幅图像相似，则说明有相同的视觉单词，图像相似度可以通过图像间视觉单词的匹配度来估计。设Nt和Nc分别为SURF算法提取两幅图像相应的视觉单词数，Npair为图像间匹配的视觉单词数，则图像间的相似度Sim（It，Ic）为：

通过式（3），将图像间的相似度转化为视觉单词的匹配度，大大减少了计算的复杂度。

2 基于贝叶斯滤波闭环检测方法

闭环检测过程可以分为图像预处理、贝叶斯滤波更新和闭环获取三个过程。对于图像预处理过程，如果在图像获取过程中，获取图像的频率较高，则相邻图像的相似度较高，即表示同一场景的可能性较大。因此，需要在图像预处理时，剔除与前一时刻相似度高的场景图像，通过不断更新当前图像与历史图像的后验概率获取闭环。

2.1 图像预处理

在机器人获取场景图像过程中，相邻图像间的相似度一般都较大。如果对所有图像都处理，势必会增加系统负担。通过添加图像间的相似度阈值Tsim，可以有效减少数据量处理。在本文中，为了后续程序更好地检测闭环，引入图像权重概念，权重越高表示在该图像发生闭环的可能性越大。设t时刻获取的图像为It，具体图像预处理过程如下所示：

1.It←对新图像特征提取和筛选，设权重Wt=0；

2.if It不合格

3.删除It；

4.else

5.Ic←获取前一个时刻保存的图像

6.Sim（It，Ic）←计算图像It与Ic的相似度；

7.If Sim（It，Ic）大于Tsim

8.It←合并图像It与图像Ic；

9.Weight（It）=Weight（Ic）+1；

10.保存It，删除Ic

11.end if；

2.2 贝叶斯滤波更新

基于贝叶斯滤波理论，在没有完全情报的情况下，先对未知状态进行主观概率估计，再利用贝叶斯修正事件发生的概率，最后依据后验概率做最优决策，即将闭环检测假设看成是一个迭代的贝叶斯估计问题，通过估计当前图像与已经访问过的历史图像相匹配的后验概率来检测闭环。

设Xt为t时刻发生闭环假设的一个随机变量，X=i表示当前图像It与历史图像Ii相匹配，而Xt=-1表示当前图像It为新的场景图像，此刻没有发生闭环。贝叶斯滤波主要包含两部分，状态预测和测量更新，通过计算所有时刻i=-1，…，t发生闭环的概率来估计后验概率分布p（Xt|It）。

状态预测：

测量更新：

依据贝叶斯得到t时刻的后验概率分布为：其中，η是归一化因子；It=I-1，…；It为在t时刻获取的整个图像序列。

在使用后验概率进行闭环检测时，最重要的两个环节就是对观测模型和运动模型的估计。在本文中，使用似然函数对观测模型进行评估。如果当前时刻发生闭环，似然函数L（Xt|It）计算公式为：

如果当前时刻没有发生闭环，则似然函数L（Xt|Lt）为：

其中Sim表示当前图像It与发生闭环的历史图像Ii的相似度，μ和σ分别表示当前图像与历史图像相似度的平均值和标准差。如果计算获得的似然值L（Xt|It）较大，意味着当前图像与历史图像的相似度较小，即当前图像为新场景图像的可能性较大。

运动模型预测闭环的状态，具体可以分为以下四种情况：

（1）p（Xt=-1│Xt-1=-1）=0.9，如果在t-1时刻没有发生闭环，那么在t时刻也没有发生闭环的概率为0.9；

（2）p（Xt=i│Xt-1=-1）=0.1/n，i∈[0，t-1]，如果在t-1时刻没有发生闭环，那么t时刻发生闭环的概率为0.1/n，其中n为获取图像的总数；

（3）p（Xt=-1│Xt-1=i）=0.1，i∈[0，t-1]，如果在t-1时刻发生闭环，那么在t时刻图像i处发生闭环的概率为0.1；

（4）p（Xt=i│Xt-1=j），i，j∈[0，t]，表示在t时刻和t-1时刻都发生闭环的概率。定义该概率是以j为中心的非空离散高斯函数，并且j与其相邻8个（i=j-4，…，j+ 4）领域值之和为0.9。

2.3 闭环获取

闭环检测过程是一个不断预测和更新的过程，通过上一时刻的预测和更新来估计当前的后验概率p（Xt│It）。如果当前估计的后验概率p（Xt│It）大于闭环阈值Tloop，则认为发生闭环，否则继续获取场景图像It进行新的闭环检测。

3 实时性的实现

为提高系统闭环检测的实时性，本文引入短期内存、工作内存和长期内存三种内存管理机制。短期内存主要用来合并相似度较高图像并更新其权重，其遵循先进先出原则。当短期内存中储存的图像数目大于设定储存空间大小时，将最先添加到短期内存中的图像转移到工作内存中，进行后续处理。工作内存主要是实现贝叶斯滤波更新和实时闭环检测。在工作内存中保存着权重较大的图像，权重小的图像或处理时间超过设定时间阈值的图像被实时地转存到长期内存中。长期内存的作用相当于数据库，保存大量的图像。这种通过短期内存激活工作内存，再激活长期内存的机制，大大减少了数据量的处理，提高了系统的实时性能。

4 实验结果

本文提出的闭环检测算法基于处理器Intel Core T6600，2.2 GHz主频，2 GB内存，通过手持微软Kinect XBOX在一个相对较小的环境区域，以1 Hz/s的采样速率，共采集到120张320×240场景图像。图1展示的是微软Kinect XBOX和在实验室取景轨迹。

图1 微软Kinect与实验室环境

4.1 图像特征提取算法选取

SIFT算法是图像特征提取与匹配中常用且有效的方法，其在仿射变换、噪声等情况下有良好的匹配性能，但由于其生成的特征描述维数较高，计算量大和时间复杂度高，系统的实时性能低。SURF算法是在积分图像的基础上，利用方框滤波近似代替二阶高斯滤波，大大提高了运算效率。如图2与图3所示，是使用SIFT和SURF算法对图像的处理。结果显示，使用SURF算法更有效。

图2 图像处理时间

图3 图像特征提取

4.2 实验阈值的设置

实验中各个阈值的选取不仅关系到系统的检测，也影响系统的性能。首先，对于场景图像的采样速率R，如果设置较小，会影响系统的实时性；若设置过大，会影响闭环检测的准确性。根据经验，采样频率R设为1 Hz。其次，对于图像的处理时间阈值Ttime，主要由配置、运行环境等因素决定，但都要满足系统处理每张图像所需的时间。一般情况下，采样频率设为1 Hz，Ttime为600 ms～800 ms。相关阈值设置如表1所示。

表1 实验阈值设置

4.3 实验结果与分析

利用本文提供的方法对数据进行处理，图4是实验室环境下对图像的处理过程。前者是通过SURF算法提取场景图像的视觉特征过程，后者表示在第84帧场景图像处与第2帧场景图像处发生了闭环。

图4 场景图像处理过程

根据表1参数，实验室环境下闭环检测的结果如图5所示。菱形表示系统没有检测到闭环的图像序列，圆圈表示正确检测到闭环的图像序列，而三角形则表示检测到闭环但拒绝闭环的图像序列。

图5 闭环检测结果

5 结论

本文提出的基于视觉字典的图像表示与图像间的相似度计算方法，极大地提高了系统闭环检测效率，体现了系统的实时处理能力。通过对实验室环境的检测，本方法得到了很好的验证，为后续机器人的研究奠定了基础。目前，实验环境还比较局限，还要对其作进一步探索。

[1]刘宝平，张红梅.移动机器人研究现状和未来发展的分析[J].科技信息，2009（29）：65．

[2]王丽杨，陈明.移动机器人的导航地位和地图构建技术综述[J].中国新技术新产品，2011（17）：13．

[3]ANGELI A，FILLIAT D．A fast and incremental method for loop-closure detection using bags of visual words[J]．IEEE Transactions on Robotics，2008，24（5）：204-226．

[4]ANGELI A，FILLIAT D.Real time visual loop closure detection[C].IEEE International Conference on Robotics and Automation（ICRA），Pasadena，2008：1842-1847．

[5]Liu Yang，Zhang Hong.Indexing visual features：real-time loop closure detection using a tree structure[C].International Conference on Robotics and Automation，2012：3613-3618．

[6]MATHIEU L，FRANCOIS M.Appearance-based loop closure detection for online large-scale and long-term operation[J]. IEEE Transaction on Robotics，2013，9（3）：734．

[7]刘红光，魏小敏.Bag of Words算法框架的研究[J].舰船电子工程，2011，31（9）：125-128．

[8]BOTTERILL T，GREEN R，MILLS S.A Bag-of-Words speedometer for single camera SLAM[C].24thInternational Conference Image and Vision Computing New Zealand（IVCNZ 2009），2009：91-96．

[9]CUMMINS M，NEWMAN P．Accelerating FAB-MAP with concentration inequalities[J]．IEEE Trans on Robotics，2010，26（6）：1042-1050．

[10]梁志伟，陈燕燕，朱松豪，等．基于视觉字典的单目视觉闭环检测算法[J]．模式识别与人工智能，2013，26（6）：561-570．

[11]李博，杨丹，邓林．移动机器人闭环检测的视觉字典树金字塔TF-IDF得分匹配方法[J]．自动化学报，2011，37（6）：665-673．

Loop closure detection based on visual dictionary for mobile robots

Cui Dacheng，Zeng Liansun
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China）

Aiming at the problem of loop closure detection in simultaneous localization and mapping（SLAM）for mobile robots，this paper presents a novel detection algorithm based on visual dictionary.Firstly，it uses SURF algorithm to extract features to generate visual words for each required image，and builds a visual vocabulary tree.Then，it builds a scene model based on bag of words（BoW）algorithm.The similarity between the images will be estimated by the degree of matching in visual words.In order to improve the continuity of the loop closure detection，the Bayesian filter method and similarity is applied to estimate the posteriori probability distribution of loop closure detection.Meanwhile，in order to improve the system′s real-time and process speed，the paper introduces memory management mechanisms.The experimental results demonstrate that this method is effective.

SLAM；visual word；loop closure detection；memory management

TP302.1

A

1674-7720（2015）09-0085-04

2014-12-03）

崔大成（1987-），男，硕士生，主要研究方向：移动机器人导航。

曾连荪（1962-），男，教授，硕士生导师，主要研究方向：无线接入技术。