闭环检测中词袋与词对袋的对比研究

曾桂萍，孙作雷，潘 盼

(上海海事大学 信息工程学院，上海 201306)

闭环检测中词袋与词对袋的对比研究

曾桂萍，孙作雷，潘 盼

(上海海事大学 信息工程学院，上海 201306)

从词袋技术(BoW)入手探究拓扑地图中的闭环检测算法，在性能和时间效率两个因素系统地对比了词袋技术与词对袋技术(BoWP)，词袋技术是以Dorian Gálvez López 提出的DLoopDetector算法为参考，词对袋(BoWP)技术是以Nishant Kejriwal提出的高性能闭环检测为原始算法，主要凸显了词对袋技术在性能上的优越性。词袋技术的优点是技术成熟易实现，但存在感知混叠问题。通过额外创建一个由词对组成的词典来克服传统词袋法中因矢量的量化导致的感知混淆的限制。实验表明，词对袋方法比Dloop能提供更好的召回性能，并且减少了算法的计算时间及复杂度。

词袋；词对袋；闭环检；同步定位和构图

0 引言

闭环检测[1]是移动机器人同步定位和构图(Simultaneous Localization and Mapping，SLAM)[2]的关键技术。本文以外观(图像)为基础的拓扑地图研究SLAM系统的闭环检测问题，机器人需要准确无误地辨认出已访问过的位置，闭环检测成功能够显著降低构图中的累积误差。SLAM系统多数采用成熟的词袋技术，本文以基于场景对象识别的实时视觉构图(DloopDetector，Dloop)[3]为代表性的词袋(Bag-of-Word，BoW)[4]技术，与新提出的词对袋(Bag of Word Pair，BoWP)[5]技术在原理和性能上进行比较。Dloop具有传统词袋技术难以解决的问题，比如矢量量化导致的感知混淆，即将机器人在不同的地理位置观测到的相似场景误认为同一个位置，而词对袋技术刚好通过直接特征匹配方法解决了Dloop感知混淆的问题，用其原始特征直接计算图像的相似度；词袋技术中机器人对先前观测图像进行的离线训练方式生成视觉词汇库，离线词典无法很好地描述机器人将来观测的场景图像，导致召回性能不太乐观，词对袋技术通过在线的拓扑图方法改善了系统性能。因此，研究具有低复杂度和高召回性能的视觉闭环探测具有重要意义。

1 词袋技术

词袋技术被广泛用于场景识别和闭环检测中，而闭环检测实质上是一种检测观测数据相似性的算法，即实时地计算当前观测图像是否与环境地图中的关键帧发生闭环。词袋模型从大量的图像中提取相似的视觉特征(像SURF[6])并聚类，然后建立离线词典，进而寻找每个图中含有哪些“单词”(word)，用字典中词频的直方图查找检索图像与地图中现有图像之间的相似性。Dloop采用K-L 散度及卡方距离检索候选闭环，同时运用树形结构管理词典，TF-IDF(Term Frequency-Inverse Document Frequency)[7]技术作为权重机制来选取视觉单词，以及正向索引计算特征的相关性，反向索引加速比较场景图像等技术，以确保对当前查询图像的搜索效率。

归一化相似度计算图像候选闭环，公式如下：

(1)

其中，vt-Δt表示上一帧图像，用与上一帧图像计算的相似度来归一化与字典树中图像计算的相似度，选取阈值α，当前帧与上一帧图像相似度大于α归为候选闭环，否则不做闭环检测。真实闭环的确认是通过验证是否满足时间以及几何一致性以避免假阳性闭环，一致性足够高的图像即视为闭环并用于修正或增广地图，使地图更加精确。

正确的图像匹配能获得成功的闭环从而保证轨迹与地图的全局一致性，反过来错误的匹配会损害地图的精确性，这些错误分为两类：(1)假阳性(False Positive，FP)，又称感知偏差，指事实上不同的场景被当成了同一个；(2)假阴性(False Negative,FN)，又称感知变异，指事实上同一个场景被当成了两个，这就是上文提出的矢量量化所致的感知混淆。精确度(Precision，P)反映判定的正例中真正的正例样本的比重，即判别为闭环中真实闭环的概率；召回率(Recall，R)反映被正确判定的正例占总的正例的比重，即真实的闭环在所有正例中的比率。计算公式如下：

(2)

一个好的闭环检测算法应该能检测出尽量多的真实回环，本文用准确率-召回率曲线来评价Dloop与BoWP算法的好坏。虽然此方法能提供更好的召回性能，但随着地图尺寸的不断增长会带来过高的计算要求。

2 词对袋(BoWP)分析

本文的词对袋(BoWP)技术是以Nishant Kejriwal提出的高性能闭环检测为原始算法[5]，词对袋主要目标是解决词袋法中感知混淆问题，以及提高词袋方法的召回性能，即结合共现信息相关联的方向属性更好地检测闭合环路。

2.1基本思想

BoWP技术除创建单词组成的字典外还增加词对的词典，即需要创建两个词典：单词词典用原始特征在线的方式创建，将输入图像的新词增量加入到使用FLANN库[8]的K-D树[9]中；词对的字典使用多重映射数据结构[6]实现。有效的词对需要考虑共现信息且满足空间约束条件，共现信息指一个单词位置空间邻域是否包含其他邻近字，若包含则与其他邻近字一起形成共现信息提供更好的闭环辨识。词典中的字是基于特征点的尺度参数形成的定向邻域范围，而特征点规模取决于它在特征提取算法时检测到的尺寸。BoWP的关键技术包括在线地创建增量词典，用K-D树基于近邻搜索来识别潜在的候选闭环，用FLANN库(1.8.4版本)于拓扑构图中。

2.2 BoWP原理分析

BoWP中图像特征选用SURF描述符，因其对光度和几何扭曲的鲁棒性良好且用时少。两个词典：单词词典是由K-D树创建，词对的字典使用多重映射数据结构实现。现用这些单词和对应词对计算相似度，即检索图像和地图中现有节点之间基于TF-IDF的评分。

(3)

由于图像是被有顺序地获取的，BoWP闭环的决策过程纳入贝叶斯框架的时间相干性，提供有效对抗可能出现的瞬态错误的鲁棒性。引用Angeli[11]等人的贝叶斯框架：融合多个观测量信息为单一的观测似然值，用于计算图像中节点的后验闭环概率[12]。BoWP获得的观察似然值有可能合并了单词与词对的信息，其似然函数公式如下：

(4)

(5)

其中μw、σw和μwp、σwp分别对应观察矢量(zw,zwp)中单词和词对的均值和标准偏差，随机变量X可采用任何节点索引作为其值，若与当前图像没有相似节点则乘1，若为一个新位置则X=-1代入似然公式，在该节点X=i的综合似然性为：

L(X=iM)=Lw(X=iM)LWP(X=iM)

(6)

所以节点索引i取集合{-1, 1,…,M}中任意值，此似然值计算节点的后验概率P(X=iM)便于检索图片的闭环候选。若节点具有最高闭环概率比阈值θlc=0.5更高，便可声明为图像的一个可能候选闭环。如果该节点满足第二阶段的RANSAC验证：

(7)

其中Ninliers是匹配RANSAC的点数量，Nimage和Nnode为图片内点数量和节点数量，θransac是唯一用户定义的参数，当Pmatch≥θransac时进一步证实了该闭环，若不满足，则为新的节点加入地图特征中[13]。

3 实验结果与分析

Dloop与BoWP实验图像特征均采用64维的SURF矢量处理图像并进行场景识别，如图1所示对比了Dloop与BoWP在慕尼黑工业大学数据集室外捕获的同一个闭环结果，Dloop中轨迹中黑色加粗线段表示的是产生闭环的部分，当前帧只有在发生闭环时才提取出闭环帧；BoWP根据检索图像的似然值，选出后验概率最高的且满足RANSAC验证的闭环。

图1 慕尼黑工业大学数据集下分别用Dloop与BoWP捕捉闭环

3.1 Dloop与BoWP召回性能的比较分析

表1中，BoWP与Dloop在保证θransac值、α阈值等保持一致的条件下，在同一数据集比较两种技术的召回性能，实验采用新学院数据集以及慕尼黑工业大学的室内室外数据集，可看出BoWP的召回率均高于Dloop算法。因为BoWP掺入空间同现信息克服感知混叠问题，并相应提高了其召回性能。如表可见所有数据集中BoWP比Dloop获得更高的召回率。

表1 Dloop与BoWP在同一数据集上召回率比较

3.2 Dloop与BoWP计算时间的比较分析

Dloop与BoWP算法的计算时间分配比重多的部分，其一是每个图像SURF特征的提取，另一个是创建K-D树并扩建地图尺寸。计算复杂性主要取决于词典大小和地图中的节点数量，当BoWP技术的词典尺寸是上一次重建K-D树词典尺寸的两倍时，需要进行重建K-D树；而Dloop中是在每一次迭代过程都得需要重建一次树[14]，所以理论上Dloop耗费的时间长一些，通过实验也可以得到证实。表2中记录了BoWP与Dloop在3个数据集下的计算时间，对比结果还是比较明显的，BoWP处理图片所需计算时间比Dloop时间少。

表2 不同数据集各图像的平均计算时间 (s)

4 结束语

可靠的定位与构图需鲁棒性强的闭环检测算法，其挑战在于合理的计算复杂度下获得更高的召回率。本文词袋与词对袋对比算法的实验代码分别引用DloopDetector算法与基于词对袋的高性能闭环检测到研究中。词袋方法(Dloop)的优势是速度快，技术成熟易于实现，但其召回率低。词对袋技术提高了召回率，因其将空间邻域信息结合到词典中，并且解决了词袋技术的感知混淆问题，缺点是需要另外建一词典存储空间信息，因而占用较多的内存。最高效的闭环检测算法是结合简单和执行速度快的词袋技术，同时采用高召回性能词对袋技术，以便应对不断增大的地图尺寸实现实时高效的检测闭环，为SLAM系统的整体构图提供关键的支撑，获得更加精确的图并实现高效定位。

[1] LATIF Y, LERMA C C, NEIRA J. Robust loop closing over time, in: proceedings of robotics: science and systems[C]. Sydney, Australia, July, 2012: 233-240.

[2] MADDERN W, MILFORD M, WYETH G. CAT-SLAM: probabilistic localisation and mapping using a continuous appearance-based trajectory[J]. Int. J. Robot. Res, 2012, 31(4): 429-451.

[3] GALVEZ-LOPEZ D, TARDOS J D. Bags of binary words for fast place recognition in image sequences[J]. IEEE Transactions on Robot, 2012,28(5): 1188-1197.

[4] ANGELI A, FILLIAT D, DONCIEUX S, et al. Fast and incremental method for loop-closure detection using bags of visual words[J]. IEEE Transactions on Robot,2008,24(5):1027-1037.

[5] NISHANT K, SWAGAT K, TOMOHIRO S. High performance loop closure detection using bag of word pairs[J]. Robotics and Autonomous Systems, 2016,77: 55-65.

[6] BAY H, ESS A, TUYTELAARS T, et al. Speeded-up robust features (SURF)[J]. Computer Vision and Image Understanding, 2008,110(3): 346-359.

[7] BERGIN J. Sets, maps, multisets, and multimaps[C]. In: Data Structure Programming, Springer, 1998: 239-266.

[8] JOHNS E, YANG G Z. Feature co-occurrence maps: appearance-based localisation throughout the day[C]. In: 2013 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2013: 3212-3218.

[9] MORIOKA N, SATOH S. Building compact local pairwise codebook with joint feature space clustering[C]. In: Computer Vision-ECCV 2010, Springer, 2010: 692-705.

[10] LABBÉ M, MICHAUD F. Appearance-based loop closure detection for online large-scale and long-term operation[J]. IEEE Transactions on Robotics, 2013, 29(3): 734-745.

[11] CUMMINS M J, NEWMAN P M. FAB-MAP: Probabilistic localization and mapping in the space of appearance[J]. International Journal of Robotics Research, 2008, 27(6): 647-665.

[12] LIU Y, ZHANG H. Indexing visual features: real-time loop closure detection using a tree structure[C]. In: 2012 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2012: 3613-3618.

[13] NISTER D, STEWENIUS H. Scalable recognition with a vocabulary tree[C]. In: Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on. IEEE, 2006: 2161-2168.

[14] 崔大成,曾连荪.基于视觉字典的移动机器人闭环检测方法研究[J].微型机与应用,2015,34(9):85-88.

A comparative research on BoW and BoWP in loop closure detection

Zeng Guiping, Sun Zuolei, Pan Pan

(School of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

The paper explores loop closure detection algorithm in the topological map from Bag of Words (BoW) technology, and systematically compares the performance in time and efficiency between Bag-of-Word and Bag of Word Pairs (BoWP). The BoW technology reference the DLoopDetector algorithm proposed by Dorian Gálvez López, because it’s mature technology is easy to realize. The BoWP technology is based on a high performance loop closure detection algorithm, which proposed by Nishant Kejriwal. It highlights the superiority in the BoWP technology on the performance, by creating an extra dictionary of word pairs to overcome the limitation of perceptual aliasing due to vector quantization in the traditional bag of word method. The experimental results show that the BoWP can provide better recall performance than the typical Dloop, besides, it can reduce the computational time and complexity of the algorithm.

BoW; BoWP; loop closure detection; simultaneous localization and mapping

TP273

：A

10.19358/j.issn.1674- 7720.2017.17.006

曾桂萍，孙作雷，潘盼.闭环检测中词袋与词对袋的对比研究[J].微型机与应用，2017,36(17)：21-23,30.

2017-03-13)

曾桂萍(1993-)，女，硕士，主要研究方向：移动机器人导航。孙作雷(1982-)，男，博士，副教授，主要研究方向：移动机器人导航、机器学习。潘盼(1989-)，男，硕士，主要研究方向：移动机器人导航。