基于不同的实现方法，目前主流的闭环检测算法大致可以分为3类：①地图到地图(Map-to-Map)类方法。Clemente和Davison[4]于2007年提出一种“分段式”地图概念，极大地提高了其在动态和复杂环境中的稳健性，但是因为空间特征需要构建稀疏地图，最终的闭环检测结果往往因为信息量不够而欠准确。②图像到地图(Image-to-Map)类方法。Williams等[5]在设计重定位模块时提出了一种通过查找当前图像帧与地图特征对应关系来确定寻找两者的匹配关系，但是这种方法需要把每一次的闭环信息都用来训练分类器，浪费大量的计算资源。③目前主流的图像到图像(Image-to-Image)类方法。这种匹配算法主要通过特征算子评估图像间的相似性确定闭环。其中，特征算子大致可以分为局部算子和全局算子2类[6]。全局算子主要通过单个全局描述子去描述整张图像[7]。早期的研究成果主要是全局描述子的设计，Krose等[8]通过主成分分析(Principal Component Analysis，PCA)降维生成图像的全局描述子。后来研究人员开始考虑图像本身的性质。Lowry等[9]通过在线学习改进了PCA描述子，指出PCA的前半部分的维度代表了图像序列相似的信息，对环境变换比较敏感，而后半部分维度的PCA特征则相反，更能应对环境的变换。相比全局描述子，局部描述子的方法目前更为通用。局部描述子方法的流行主要因为视觉词袋(Bag-of-Words，BoW)技术。Cummins和Newman[10]较早地把词袋技术引入到闭环检测中，通过Chow-Liu树计算视觉单词的联合概率分布，从而获得闭环的后验概率，以此判断闭环是否可能发生。Galvez-Lopez和Tardos[11]创造性地提出DBoW算法。DBoW利用词汇树向量化图像，并通过正向(Direct Index)和反向(Inverse Index)2种索引结构提高计算效率。ORB-SLAM2系统[12]作为近几年视觉SLAM系统的代表性工作，通过DBoW算法获得了较强的闭环检测和重定位能力。
综上所述，闭环检测已经取得了一些进展。但即使是应用程度最广的闭环检测DBoW算法，仍然存在诸多问题：①词袋模型通过聚类生成视觉单词，通过向量比较图像序列之间的相似性，随着场景范围的扩大，尤其是大范围的场景重建，计算量也会随之增加，实时性将会面对挑战[13]。②在闭环检测中，一个真阳性闭环(预测为闭环的真闭环)能够显著优化视觉里程计的误差，但一个假阳性闭环(预测为闭环的假闭环)可能导致整个后端优化模块收敛到错误的方向。正确地检测出闭环对整个SLAM系统至关重要。目前，一些闭环检测算法的准确率在复杂场景下还远远不够，尽管已经有一些研究希望能够降低闭环检测的错误率[14-15]，但往往会加重整个SLAM后端的负担，并且提高也不明显。
针对上述问题，本文提出了一种高效准确的闭环检测算法TPSV-DBoW(Tracking Prediction and Structural Verification-Distributed Bag of Words)。为了提高闭环检测算法的准确率与鲁棒性，将局部算子与全局描述符结合。利用局部算子(视觉单词)比较图像的相似性，得到闭环候选帧；通过全局描述符进行结构校验，验证闭环候选帧是否是真闭环，以此设计了词袋模型和图像结构校验模块。针对传统闭环检测算法耗时随图像数量增加而显著增加的问题，进而设计了跟踪预测模型，基于相邻前几帧图像的闭环检测结果预测当前帧的状态。
1 闭环检测算法 如图 1所示，TPSV-DBoW算法由词袋模型、图像结构校验、跟踪预测模型3个模块组成。算法通过词袋模型模块和图像结构校验模块将局部特征与全局特征相结合, 以提高闭环检测算法在复杂场景下的准确率与鲁棒性。词袋模型通过二元鲁棒独立基本特征(Binary robust independent elementary feature，Brief)离线词袋树得到图像的视觉单词向量，实现图像的数字化。之所以选用Brief而不是其他更加鲁棒的特征算子是为了提高算法运行速度，且本模块的设计是提供闭环候选帧而不是直接得到真闭环，Brief算子的性能足够满足本模块的需要。图像结构校验模块通过全局算子进行结构校验。出于节省计算资源的考虑，没有设计专门用于校验的全局算子，而是通过对图像灰度化、归一化处理，将归一化之后的图像平均分成4份，每份图像的中心像素点直接作为定向快速旋转Brief ORB的特征点，避免了提取特征点的复杂操作。之后，计算特征点的局部描述符。每个ORB局部描述符恰好覆盖每份图像(即归一化图像的四分之一)，可作为归一化图像的全局描述符。词袋模型提供候选闭环，图像结构校验模块验证是否为真闭环。这种局部描述符与全局描述符相结合的方法可以进一步提高闭环检测的准确率。在跟踪预测模块中，前几帧的闭环检测结果可以作为后一帧闭环判断的先验条件。在传统的闭环检测算法中，当前图像都需要与之前所有已经出现过的图像比较相似性得分才能判断闭环是否存在，这会导致计算时间随着图像数量的增加而急剧增加。本模块的设计主要是根据前几帧的闭环状态判断当前图像的闭环状态。主要有2点，其一先判断当前图像是否存在闭环，其二如果存在则预测出闭环候选集，借此提高闭环检测的实时性。
 |
| 图 1 闭环检测流程 Fig. 1 Flowchart of loop closure detection |
| 图选项 |
2 核心算法模块 2.1 词袋模型计算相似性 对每一帧图像计算Brief算子。Brief是典型的二进制描述符，可降低计算复杂度，提高计算速度。Brief只是计算描述符的方法，不包含提取特征点的过程，所以需要先利用FAST(Features from Accelerated Segment Test)算法检测特征点，再计算Brief描述符。之后通过Brief词袋树完成图像的向量化。视觉词袋有多种组织方式，对应于不同的搜索复杂度。词袋模型采用的结构如图 2所示，其是一个度为K=10、层数L=6的搜索树，时间复杂度为lg 6。
 |
| 图 2 Brief词袋树 Fig. 2 Vocabulary tree of Brief |
| 图选项 |
词袋树每个叶节点的单词都被赋予一个TF-IDF权重，如下：
 | (1) |
式中：nid为图像d中视觉单词i出现的频数；nd为图像d中视觉单词的总数；N为图像序列总数；Ni为所有图像中视觉单词i出现的总数。TF越高，说明单词在这幅图像中出现的越多，单词的IDF越高，说明其他图像中很少出现，二者结合起来，则认为此单词具有很好的区分能力，权重也就越高。
对图像中的每个特征算子通过层序遍历池袋树，即从根节点开始搜索，首先确定根节点的10个子节点中与其最匹配的节点，再从这个子节点开始搜索。这样一层层往下遍历，从而得到其对应的视觉单词。最终得到整张图的视觉单词描述模型：
 | (2) |
式中：Iu为图像；dn为视觉单词。这些值构成图像的描述向量vt。对2幅图像比较计算两者的相似度，计算公式如下：
 | (3) |
2.2 图像结构校验模块 本模块是基于全局描述符的设计，通过全局描述符校验闭环候选帧。词袋模型通过局部描述符寻找候选闭环，在此基础上，通过本模块进行图像结构校验。这种设计可大大提高闭环检测的鲁棒性与准确率。
将候选闭环图像与当前图像灰度化、归一化，如图 3所示，左边为未处理之前的1 241×376的彩色图像，右边为归一化之后的127×127的灰度图像。与仅用中心特征作为全局特征[7]的方法不同，将归一化之后的图像平均分成4块(见图 4)，每块为64×64像素。之后把每份图像的中心像素点直接作为ORB特征点，这样可以避免特征点定位的复杂操作，从而提高计算效率。在每个特征点的邻域直接计算ORB局部描述符，图 4左边的数字即为第一份图像的ORB描述符。每个局部描述符恰好覆盖每份图像，即归一化图像的四分之一。4个局部描述符恰好覆盖整张图像，可作为图像的全局特征。这种方式不需要设计特别复杂的全局描述符即可完成结构校验。
 |
| 图 3 图像归一化 Fig. 3 Image normalization |
| 图选项 |
 |
| 图 4 ORB全局特征 Fig. 4 ORB holistic features |
| 图选项 |
ORB拥有旋转不变性，对噪声不敏感，相对鲁棒，并且计算速度也较快，完全可以满足结构校验的需要。ORB使用矩来计算特征点以r为半径范围内的质心。矩的定义如下：
 | (4) |
式中：I(x, y)为(x, y)处的灰度值。通过该矩计算邻域质心为
 | (5) |
特征点坐标到质心的向量作为该特征点的方向。假设角点坐标为O，此向量的角度即为特征点方向[7]。
 | (6) |
在进行图像结构校验时，将归一化图像各区域的全局算子两两比较，记录汉明距离大于100的数目，如下[7]：
 | (7) |
式中：Nx为候选闭环的第x份区域；Ix为当前图像的第x份区域，x∈{1, 2, 3, 4}。
闭环候选图像与当前图像归一化之后，每张图像各划分为4份区域，匹配之后，若其中有2份及以上区域间的汉明距离大于100，则认为当前的候选闭环不是正确闭环，应当舍弃。
2.3 跟踪预测模型 随着场景的扩大，尤其是大范围场景的闭环检测，当前图像需要与之前所有已经出现过的图像逐帧比较，以此寻找闭环。因此，计算量会随着图像序列的增加而增加。由于词袋模型和图像结构校验模块将局部特征与全局特征相结合，在一定程度上也提高了计算的时间复杂度，因而设计了跟踪预测模型来处理以上问题。
跟踪预测模型能够有效地节约整个算法的耗时。跟踪预测模型的设计原则为：根据前几帧的检测结果判断当前图像是否可能有闭环。如果预测不存在闭环，则可以跳过与已经出现过的图像逐帧比较的阶段[7]。此外，认为如果预测当前图像存在闭环并且连续前几帧图像有闭环，则可以预测当前图像的闭环候选集，即把闭环图像限定在少量连续的图像集合内，减少与当前图像逐帧比较的数量，提高闭环检测的速度。
本模块的核心思想是：依据前几帧图像的闭环检测结果预测当前图像的闭环检测结果。因为相邻图像具有相似性，即使相机以一个相对较快的速度在移动，由于曝光速度的原因，相邻图像描述的场景仍然没有太大差别。所以，如果某张图像不存在闭环且其与之前所有图像的相似度得分都很低，那么其下一帧图像也应该不存在闭环。如图 5所示，如果当前图像与之前所有的图像相似度得分都小于阈值Slow，把其定义为low Score的图像。low Score图像的相邻图像得分应该相对较低，而存在闭环的图像的相邻图像的相似度得分应该较高。
 |
| 图 5 相似得分的连续性 Fig. 5 Continuity of similarity score |
| 图选项 |
如图 6(a)所示，若i+n-1为当前图像，i+n、i+n+1、i+n+2、i+n+3为其后4帧图像。如果当前图像为low Score的图像，认为其后4帧图像之内不存在high Score的图像。这4帧图像都可跳过比较相似性的阶段。4帧之后则需要重新通过词袋模型与之前所有的图像逐帧比较相似性。另一种可预测的情况如图 6(b)所示，i为当前图像的序号，i-3、i-2、i-1为当前图像之前的图像序号，其对应的闭环图像为xi-3、xi-2、xi-1。因为相机的速度在很短的时间内近似于匀速，在考虑干扰的情况下，闭环图像的差值近似于高斯分布，如下[7]：
 | (8) |
 |
| 图 6 跟踪预测模型 Fig. 6 Tracking prediction model |
| 图选项 |
式中：μ为高斯均值；σ2为高斯方差。
 | (9) |
 | (10) |
计算可得闭环候选集的范围为[xi-1+μ-10σ, xi-1+μ+10σ]。
3 实验结果分析 实验所用主机的配置为：CPU为I7-6700，主频3.4 GHz，内存32 GB。对比算法为DBoW。实验所用数据集为KITTI Visual Odometry数据集。
KITTI Visual Odometry数据集部分图像如图 7所示，其属于城市公路数据集，包含较多相似场景，并且其中含有不少假闭环，是一个比较具有挑战性的实验数据集。
 |
| 图 7 实验场景 Fig. 7 Experimental scene |
| 图选项 |
3.1 准确率数据集实验 KITTI Visual Odometry数据集中含有ground truth真实地图标号为00~10的数据集，图 7中的实验图像便是标号为00数据集中的场景。标号00~10数据集中含有连续闭环的为00、02、05、06数据集，可以作为用来检测闭环检测算法性能的数据集。本文在这几组数据集上与DBoW算法比较，验证了提出的闭环检测算法的准确率。
图 8(a)、(c)、(e)、(g)为DBoW算法在00、02、05、06数据集上的实验结果，图 8(b)、(d)、(f)、(h)为TPSV-DBoW算法在00、02、05、06数据集上的实验结果。图 8中连续的线条为相机的运动轨迹。正确的闭环(即相机确实曾经到过此处)旁边有黑色实线标记，没有黑色实线标记的路径表示相机轨迹未发生闭环。如果算法在没有黑色实线标记的路径中检测出闭环，则认为出现误检情况。误检越多，闭环检测算法的准确率越低。图 8(b)、(d)、(f)、(h)的错误闭环分别少于图 8(a)、(c)、(e)、(g)，TPSV-DBoW的准确率表现更优。
 |
| 图 8 实验结果 Fig. 8 Experimental results |
| 图选项 |
具体闭环的准确率如表 1所示，可以看出TPSV-DBoW算法的优越性。在表 1中，除02数据集外，闭环检测算法的准确率都达到了80%以上。由于02数据集相似场景很多(道路两旁几乎都是相同的树木)，本文所提算法和DBoW算法的准确率都相对较低，但相比DBoW依旧有25.35%的提升。总体上，除了06数据集，TPSV-DBoW算法基本都有25%左右的显著提升。由于06数据集本身比较简单，故性能普遍较好。DBoW算法已经达到了78.86%的准确率，所提出的算法在此基础上仅提升了14.04%。
表 1 闭环检测准确率 Table 1 Loop closure detection accuracy
| 数据集标号 | 准确率/% | 准确率提升/% | |
| DBoW算法 | TPSV-DBoW算法 | ||
| 00 | 67.00 | 83.07 | 23.99 |
| 02 | 26.67 | 33.43 | 25.35 |
| 05 | 62.78 | 84.89 | 35.22 |
| 06 | 78.86 | 89.93 | 14.04 |
表选项
3.2 实时性检测数据集实验 为了验证TPSV-DBoW算法的实时性，实时性检测实验使用01~10号KITTI Visual Odometry数据集(其中01、06、07数据集都为1 100张图像)。图 9展示了闭环检测耗时与图像数量的关系，表 2记录了闭环检测耗时的具体数据。可以看到，随着图像数量的增加，闭环检测算法耗时急剧增加，因为要检测出当前图像是否存在闭环，需要与之前所有的图像序列比较。由图 9可见，随着图像数目的增加，算法在实时性上具有更好的表现，实时性的提升也更加显著。主要是因为跟踪预测模型能够预测当前图像是否可能存在闭环，以及存在闭环的情况下，预测当前的闭环候选集来减少与当前图像比较相似性的图像数量，从而提高算法的计算效率。
 |
| 图 9 实时性实验 Fig. 9 Real-time performance experiment |
| 图选项 |
表 2 实时性对比 Table 2 Real-time performance comparison
| 数据集标号 | 图像数量 | 耗时/s | 实时性提升/% | |
| DboW算法 | TPSV-DboW算法 | |||
| 04 | 271 | 18.55 | 18.53 | 0.10 |
| 03 | 801 | 67.44 | 66.11 | 1.96 |
| 01、06、07 | 1 100 | 67.30 | 66.70 | 0.89 |
| 10 | 1 200 | 93.56 | 92.17 | 1.48 |
| 09 | 1 590 | 118.76 | 116.99 | 1.48 |
| 05 | 2 761 | 190.71 | 186.87 | 2.01 |
| 08 | 4 070 | 432.17 | 416.78 | 3.56 |
| 02 | 4 661 | 619.58 | 595.71 | 3.85 |
表选项
4 结束语 SLAM是移动机器人视觉导航领域的关键技术，闭环检测在其中至关重要。为了提高闭环检测的准确率和实时性，提出了一种高效准确的闭环检测算法。①词袋模型与图像结构校验模块通过将全部算子与局部算子结合的方法大大提高了闭环检测的准确率。②考虑到算法复杂度及大场景下闭环检测等因素，跟踪预测模型用于提高计算效率。③相比于DBoW算法，TPSV-DBoW算法的准确率基本提升了20%以上，实时性也更加优越。
虽然TPSV-DBoW算法的闭环检测准确率有着较大的提升，但精度还存在提升空间，对于复杂场景准确率也有所降低。算法检测时间较DBoW算法有所减少，但当图像序列数量增加时，耗时也呈指数级增长。除此以外，动态场景等复杂环境下算法的鲁棒性也遭受挑战。下一步工作将着重研究提高复杂场景下闭环检测的性能及闭环检测算法对各种场景的适应能力。
参考文献
| [1] | GUI J J, GU D B, WANG S, et al. A review of visual inertial odometry from filtering and optimisation perspectives[J]. Advanced Robotics, 2015, 29(20): 1289-1301. DOI:10.1080/01691864.2015.1057616 |
| [2] | 何俊学, 李战明. 基于视觉的同时定位与地图构建方法综述[J]. 计算机应用研究, 2010, 27(8): 2839-2844. HE J X, LI Z M. Survey of vision-based approach to simultaneous localization and mapping[J]. Application Research of Computers, 2010, 27(8): 2839-2844. DOI:10.3969/j.issn.1001-3695.2010.08.007 (in Chinese) |
| [3] | HESS W, KOHLER D, RAPP H H.Systems and methods of detecting loop closure in simultaneous localization and mapping (SLAM) applications: U.S.14/972, 938[P].2019-06-11. |
| [4] | CLEMENTE L, DAVISON A.Mapping large loops with a single hand-held camera[C]//Robotics Science and Systems, 2007, 2(2): 297-304. |
| [5] | WILLIAMS B, CUMMINS M, NEIRA J, et al.An image-to-map loop closing method for monocular SLAM[C]//IEEE International Conference on Intelligent Robots and Systems.Piscataway: IEEE Press, 2008: 2053-2059. |
| [6] | 刘强, 段富海. 复杂环境下视觉SLAM闭环检测方法综述[J]. 机器人, 2018, 40(6): 123-136. LIU Q, DUAN F H. A survey of loop-closure detection method of visual SLAM in complex environments[J]. Robot, 2018, 40(6): 123-136. (in Chinese) |
| [7] | 刘国忠, 胡钊政. 基于SURF和ORB全局特征的快速闭环检测[J]. 机器人, 2017, 39(1): 36-45. LIU G Z, HU Z Z. Fast loop closure detection based on holistic features from SURF and ORB[J]. Robot, 2017, 39(1): 36-45. DOI:10.3969/j.issn.1004-6437.2017.01.005 (in Chinese) |
| [8] | KROSE B J A, VLASSIS N, BUNSCHOTEN R, et al. A probabilistic model for appearance-based robot localization[J]. Image & Vision Computing, 2001, 19(6): 381-391. |
| [9] | LOWRY S M, WYETH G F, MILFORD M J. Unsupervised online learning of condition-invariant images for place recognition[J]. Procedia-Social and Behavioral Sciences, 2014, 106: 1418-1427. |
| [10] | CUMMINS M, NEWMAN P.Probabilistic appearance based navigation and loop closing[C]//Proceedings 2007 IEEE International Conference on Robotics and Automation.Piscataway: IEEE Press, 2007: 2042-2048. |
| [11] | GALVEZ-LOPEZ D, TARDOS J D. Bags of binary words for fast place recognition in image sequences[J]. IEEE Transactions on Robotics, 2012, 28(5): 1188-1197. DOI:10.1109/TRO.2012.2197158 |
| [12] | MUR-ARTAL R, TARDOS J D. ORB-SLAM2:An open-source SLAM system for monocular, stereo, and RGB-D cameras[J]. IEEE Transactions on Robotics, 2017, 33(5): 1255-1262. DOI:10.1109/TRO.2017.2705103 |
| [13] | 梁志伟, 陈燕燕, 朱松豪, 等. 基于视觉词典的单目视觉闭环检测算法[J]. 模式识别与人工智能, 2013, 26(6): 561-570. LIANG Z W, CHEN Y Y, ZHU S H, et al. Loop closure detection algorithm based on monocular vision using visual dictionary[J]. Pattern Recognition and Artificial Intelligence, 2013, 26(6): 561-570. DOI:10.3969/j.issn.1003-6059.2013.06.007 (in Chinese) |
| [14] | GUCLU O, CAN A B. Fast and effective loop closure detection to improve SLAM performance[J]. Journal of Intelligent and Robotic Systems, 2019, 93(3-4): 495-517. DOI:10.1007/s10846-017-0718-z |
| [15] | ZHANG G, YAN X, YE Y. Loop closure detection via maximization of mutual information[J]. IEEE Access, 2019, 7: 124217-124232. DOI:10.1109/ACCESS.2019.2937967 |
