基于thLSH的快速闭环检测方法

姜海洋　朴松昊　张祖亮

摘 要：同步定位與地图构建（SLAM）问题是实现移动机器人在未知环境中自我定位和导航的关键技术，具有重大的理论意义和研究价值。闭环检测是SLAM中的一个关键模块，对机器人实时更新地图和避免引入错误的地图节点起着关键作用。本文将视觉闭环检测问题看作是图像检索问题，基于深度学习的思想，将RandNet神经网络应用到闭环检测，并利用基于阈值的局部敏感哈希算法对其提取的图像特征匹配过程进行加速。实验结果表明：本文所提出的基于thLSH的快速闭环检测方法，在保证高准确率的前提下，特征匹配速度提升了10倍，能够更好满足闭环检测的实时性需求。

关键词：同步定位和地图构建； 闭环检测； 神经网络； 局部敏感哈希

Abstract： The issue of Simultaneous Localization and Mapping （SLAM） is a crucial technology for autonomous positioning and navigation of mobile robots in an unknown environment， and has theoretical significance and research value. Loop closure detection is a vital module in SLAM and plays an important role in updating the map in real time and avoiding the introduction of wrong map nodes. The loop detection vision problem in this thesis is regarded as an image retrieval issue， and based on the idea of deep learning， the RandNet neural network is applied to the loop detection problem， and a threshold-based locality-sensitive hashing algorithm is also used to accelerate the image feature matching process. The experimental results show that the fast loop detection method based on thLSH proposed in this paper can improve the feature extraction speed by more than 3 times on the premise of high accuracy， the speed of feature matching is 10 times higher， and it can meet the real-time requirement of loop detection.

Key words： visual Simultaneous Localization and Mapping； loop closure detection； neural network； locality-sensitive hashing

引言

同步定位和建图问题（simultaneous localization and mapping，简称SLAM）中的即时定位和建图，是利用算法对传感器在未知环境中采集的信息进行处理，由于环境的未知性、建模算法本身的缺陷、传感器的累计误差等问题，致使SLAM的定位与建图的精度不够准确，甚至可能导致环路不能闭合，而无法判断机器人是否回到已访问过的区域。SLAM中的闭环检测（Loop Closure Detetion，LCD）模块是通过判断当前位置是否处于已访问过的区域，抑制传感器的累积误差[1]，进而提高后端图优化的准确性，保证地图构建的效果的精准表达。

闭环检测，本质上是数据的关联问题。在基于视觉同步定位与地图构建（visual Simultaneous Localization and Mapping， vSLAM）系统中，通常采用的方法是将当前位置采集的场景图像与此前所采集的场景图像进行匹配，当2个场景图像的相似度达到一定阈值时，即可判定发生了闭环。当前，大部分vSLAM系统的闭环检测还是采用基于SIFT[2]、SURF[3]等特征的视觉词袋模型[4]（Bag of View Words，BoVW），但是当场景或是感知条件不断动态变化时，图像的特征描述鲁棒性很低。在闭环检测过程中，环境中可能出现比较相似的场景或者物体，易导致在视觉图像特征匹配时产生感知混淆[5]（perceptual aliasing）问题。另外，随着测量时间的增长，传感器所测得的数据规模也越来越大，图像视觉特征相似度的计算量也随之增加，此时若仅仅依赖机器人的本体传感器，闭环检测的精度将大幅下降，这些问题都将造成vSLAM闭环检测失败，因此需要构建独立的闭环检测系统。

近几年，深度学习理论和技术得到快速发展，在图像识别和分类问题中优势明显，已有部分学者开始将深度学习技术应用到vSLAM的闭环检测中，但是大部分方法的参数训练过程耗时较长，并且获取的图像特征维度较大。而在较大规模的闭环检测中，场景过大、图像特征维度高等问题，将导致图像特征匹配过程计算量过大，而无法满足vSLAM工作实时性的需求。

本文围绕vSLAM系统中的闭环检测问题展开了深入的研究，选取基于无预训练且高效的RandNet神经网络的闭环检测方法，提高场景图像特征的提取速度，并针对传统所使用的基于余弦相似度矩阵的匹配方法，提出了一种基于阈值局部敏感哈希的图像特征匹配方法，将场景图像特征匹配速度提高10倍。

1 相关工作

目前，大部分视觉闭环检测算法是基于Image-to-Image匹配，即将移动机器人当前所处位置的场景图像与先前访问过的场景图像进行相似度比较匹配。在此匹配策略下，闭环检测被看作是图像匹配问题，所以考虑的是图像描述性和相似性度量这2个问题。

传统的Image-to-Image解决方案中，最常用的图像描述方法是视觉词袋模型。Cummins 等人[6]提出基于视觉外观（visual appearance）对场景进行描述，使用 FAST 算子提取每一幅训练图像的局部特征，然后将特征描述空间通过K中心点聚类（k-medians clustering）方法聚类为簇，成为词典树的第一层，重复执行获取其它层，最终得到W个叶子节点，即视觉词汇，移动机器人在运动时将生成的视觉词汇与视觉单词空间（visual word space）进行快速匹配，实现闭环检测。Zhang等人[7]将图像的透视不变二值特征描述子应用到增量式的视觉词袋模型中，把汉明距离看成相似度测量，提高了闭环检测的效率。梁志伟等人[8] 应用混合高斯模型为视觉词袋中的每一个视觉词汇建立概率模型，得到每一个视觉词汇的向量表示，并用贝叶斯滤波器提高闭环检测的准确率。Liu等人[9]把图像的GIST描述子当作图像的全局特征，提高BoVW方法闭环检测的效率。文献[10]用基于ORB的视觉词典进行闭环检测，利用ORB特征的旋转不变性和处理尺度变化的特性，能够从不同视角识别场景。文献[11]将空间共生信息添加到视觉词典当中，解决了闭环检测感知混淆的缺陷。Li等人[12]提出利用金字塔TF-IDF得分的视觉词典树对SLAM进行闭环检测，解决了基于视觉词典树的闭环检测视觉词汇数目的限制和算法效率低的问题。文献[13]提出了一种基于融合时间信息、拓扑构建场景地图的闭环检测方法，提升了准确率和召回率。

尽管在当前的研究中，结合BoVW和 GIST在闭环检测中效果不错，但由于BoVW和GIST特征都是手工设计，导致模型对光照变化非常敏感，场景或感知条件一旦发生变化，则不能够提供较高鲁棒性的图像特征描述，致使vSLAM闭环检测的成功率大幅度降低。

近几年来，深度学习模型的兴起为图像描述指出了新的方向，能够由浅入深地提取图像特征，给出鲁棒的图像描述，在图像识别和分类等领域取得巨大成功。考虑到移动机器人在Image-to-Image匹配中同样需要准确的特征信息，自2015 年以来，学者们开始尝试将深度学习方法应用到vSLAM的闭环检测中。Xia等人[14]利用级联深度学习模型 PCANet 提取图像特征，网络简单并且便于调试，但是为了防止输出图像的特征维度过大，导致输入图像像素过小。Hou等人[15]利用基于caffe框架的AlexNet模型进行特征提取，通过实验发现，与传统的图像特征提取方法相比，在光照变化明显的环境中，深度学习提取图像特征的鲁棒性更高，而且特征提取速率更快，但是所提取特征的维度过高，SLAM系统不能够实时运行。文献[16]中利用AlexNet对Places数据库经由再训练而得的模型进行特征提取，发现通过Places数据集再训练的网络明显提高闭环检测的准确率。同时为了解决实时性问题，Bai等人[17]研发的 Places-CNN深度学习模型，利用局部敏感哈希（local-sensitive hash）进行图像特征压缩，提高特征匹配效率。文献[18]中，利用Nordland数据集对Places-AlexNet深度学习预训练模型再训练，通过实验比较二元欧氏距离、二元余弦距离、三元欧氏距离和三元余弦距离几种特征向量的相似性度量，发现余弦距离比欧氏距离效果更佳。

上述基于深度学习模型的闭环检测中，通常采用有监督的学习方法，需要大量标签数据，在移动机器人工作之前花费较多时间对神经网络中的参数进行训练，在环境未知的前提下实际操作具有很大的困难。因此，采用不依赖于数据集的模型有更高的可行性。

Gao等人[19]使用堆栈式去噪稀疏自编码模型提取图像特征，通过计算特征的相似性矩阵，判断是否发生闭环，同时优化自动编码机中的损失函数。该方法在公开的数据集上测试，取得了较好的效果，但是没有考虑图像的空间局部特性。

与传统Image-to-Image匹配的闭环检测方法相比，基于深度学习模型的闭环检测把图像信息表达得更加充分，对于光照等感知条件有更高的鲁棒性。但是实时性问题依然没有解决。

2 基于thLSH的快速闭环检测

2.1 RandNet级联神经网络

RandNet神经网络[20]是由Chan等人提出的，其原形是PCANet神经网络， Xia等人已在文献[14]中将PCANet应用在vSLAM的闭环检测当中，但是PCANet的一个缺点是需要已知的场景图像进行预训练，而其变种RandNet神经网络，成功克服了这个问题，但是以牺牲一点准确率作为代价。移动机器人未来将应用于各种未知复杂的环境中，若是能消除预训练的困扰，还能保持较高的准确率，当然是最理想的情况。为此，本文提出了基于RandNet的神经网络的vSLAM闭环检测方法。

RandNet神经网络模型包含以下3个步骤，分别是：多级滤波器组滤波、二值化哈希编码和分块直方图。如图1所示，就是RandNet模型框架结构示意图。

所提取的图像特征是一个稀疏的向量，不同场景图像之间很容易区分，代价就是向量维度比较大，增加了特征相似性的计算量。而RandNet神经网络的性能与PCANet神经网络的性质差别已经在文献[14]给出，本文则将侧重于研究thLSH方法，仅采用RandNet神经网络进行场景图像的特征提取。

2.2 基于thLSH的快速闭环检测

对于闭环检测中的特征匹配问题，传统方法利用的是余弦距离相似性矩阵。虽然通过余弦距离相似性矩阵可以保证闭环检测的准确性，但却存在设计不足，也就是：余弦距离是通过浮点数向量之间的乘除运算得来，当特征向量的维度k较大时，计算量较大，不能满足SLAM系統的实时运行需要。

闭环检测中的特征匹配问题，即在已经访问过的位置区域中寻找与当前位置图像特征相似度最高的特征，用以判断是否发生闭环，可以看作是图像检索问题。基于此，就可以考虑利用局部敏感哈希算法加速检索过程。

Lv等人[21]提出了一种基于阈值的局部敏感哈希算法（Locality-Sensitive Hashing Scheme Based on Thresholding，简称thLSH），用位向量的汉明距离来近似特征向量的加权L1距离。而在闭环检测中通常使用的是余弦距离，所以本文提出使用thLSH作为滤波器，先将距离位向量最近的k个向量之外的向量都剔除出余弦距离最近邻的候选集，之后在k个候选特征中，比较余弦距离找出最近邻。至此，可得研究流程设计分述如下。

（1）位向量的设计生成。首先，研究讨论如何将一个特征向量通过哈希函数转化为位向量，使得生成的2个位向量之间的汉明距离近似于2个特征向量之间的加权L1距离。算法1的设计代码可参见如下。

（3）利用加权L1距离进行滤波。在前k加权L1距离近邻中利用余弦距离找出最近邻，再与设定加权L1距离阈值进行比较，用以判断是否发生闭环。

综上研究可得，基于thLSH的闭环检测流程可如图2所示。

3 实验结果和分析

3.1 实验环境及参数配置

实验平台是Windows 10（64位）下的Matlab2014a 。数据集是City Center和 New College，这2个数据集是由牛津大学Cummins等人采选收集，主要用于vSLAM的研究和闭环检测算法的评估验证。2个数据集分别包含1 237 对和 1 073对图像，图像均是尺寸为640×480的三通道彩色图。数据集中还给出了形成闭环区域的真实标注，用来检验闭环检测算法的准确率，标注以矩阵的形式给出，若图像i与图像j形成闭环区域，即可认定是在相同位置采集的，则（i， j）对应的数值为 1，否则为 0。

RandNet神经网络的参数包括级联层数、块的大小k1、k2，每层级联使用滤波器的数量L1、L2和输出层中的局部直方图块的尺寸，实验的参数与文献[16]中所使用的并无差别，只是根据实际需要稍加调整，具体可见表1。原图集为640×480的三通道彩色图，但是作为输入时，预处理成32×24大小的三通道图。

本文使用准确率、召回率、平均精确率和时间性能进行验证。其中，准确率和召回率是评价SLAM闭环检测的2个常用指标，研究将用到的计算公式可描述如下：

式（6）、式（7）中，准确率表示检测到的正确闭环数（TP）和检测到的闭环总数（TP+FP）之比，召回率表示检测到的正确闭环数（TP）和数据集中存在的总闭环总数（TP+FN）之比。

过程中，先利用算法提取特征，计算数据集中各图像的余弦距离，得到相似度矩阵。再调整余弦距离的阈值，依据数据集提供的真实闭环检测标注计算相应的准确率和召回率，由此绘制得到准确率-召回率曲线（即precision-recall曲线，或简称P-R曲线）。

3.2 实验结果与分析

在基于阈值局部敏感哈希算法的性能比较实验中，将对基于阈值的局部敏感哈希算法、基于随机超平面的局部敏感哈希算法和基于余弦距离相似性矩阵算法的闭环检测匹配进行测试。测试结果及分析内容阐述如下。

（1）准确率-召回率曲线的实验结果比较。数据集New College和City Centre的实验结果分别如图3～5和图6～8所示。显然，基于随机超平面局部敏感哈希算法的准确率-召回率曲线比基于阈值的局部敏感哈希算法和基于余弦相似性矩阵的闭环检测匹配算法性能都要好，而基于阈值的局部敏感哈希算法，准确率稍微比基于余弦相似性矩阵的算法低一些。

（2）闭环检测匹配时间的结果比較。基于数据集City Centre和New College的闭环检测匹配时间记录可分别参见表2与表3。分析可知，基于随机超平面的局部敏感哈希算法（即表中的shLSH）对场景图像特征的匹配速度提升了3倍多，而基于阈值的局部敏感哈希算法却是基于随机超平面的局部敏感哈希算法3倍多，是基于余弦相似性矩阵的算法的10倍。究其原因就在于基于余弦相似性矩阵的算法要进行大量的浮点数乘除运算，虽然基于随机超平面的局部敏感哈希算法最终也是利用位向量的汉明距离来进行研究运算，但是在降维过程中，仍然调取了浮点数矩阵乘法机制进行运算，而基于阈值的局部敏感哈希算法，则是在利用阈值将浮点向量转换为位向量后计算汉明距离，并没有更多的浮点运算，因此计算速度大大加快，进而显著提升了图像特征匹配速度。

4 结束语

针对目前基于深度学习的vSLAM中闭环检测过程无法满足实时性的需求的现状，本文提出了基于阈值的局部敏感哈希算法对特征匹配过程进行加速。在RandNet神经网络提取场景图像特征的基础上设计部署了仿真实验，与传统基于余弦相似性矩阵的方法和基于随机超平面的局部敏感哈希方法进行比较。实验结果表明，该方法能够将传统的基于余弦相似性矩阵方法提速10倍，而且比基于随机超平面的局部敏感哈希方法也要快上3倍有余，因而能够更好满足闭环检测的实时性需求。

参考文献

[1] BEEVERS K， HUANG W. Loop closing in topological maps[C]// Proceedings of the 2005 IEEE Internationla Conference on Robotics and Automation（ICRA 2005）. Barcelona， Spain：IEEE， 2005：4367-4372.

[2] NG P C， HENIKOFF S. SIFT： Predicting amino acid changes that affect protein function[J]. Nucleic Acids Research， 2003， 31（13）： 3812-3814.

[3] BAY H， ESS A， TUYTELAARS T， et al. Speeded-up robust features （SURF）[J]. Computer Vision and Image Understanding， 2008， 110（3）： 346-359.

[4] SHEKHAR R， JAWAHAR C V. Word image retrieval using bag of visual words[C]//International Workshop on Document Analysis Systems. Gold Coast，Queensland， Australia：IEEE，2012： 297-301.

[5] WILLIAMS B，CUMMINS M， NEIRA J，et al. An image-to-map loop closing method for monocular SLAM[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Nica，France：IEEE， 2008： 2053-2059.

[6] CUMMINS M， NEWMAN P. FAB-MAP： Probabilistic localization and mapping in the space of appearance[J]. International Journal of Robotics Research， 2008， 27（6）：647-665.

[7] ZHANG Guangcong， LILLY M J， VELA P A. Learning binary features online from motion dynamics for incremental loop closure detection and place recognition[J].arXiv preprint arXiv：1601.03821， 2016.

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

[9] LIU Yang， ZHANG Hong. Visual loop closure detection with a compact image descriptor[C]// IEEE/RSJ International Conference on Intelligent Robots and Systems. Vilamoura-Algarve， Portugal：IEEE， 2012：1051-1056.

[10]MUR-ARTAL R， TARDS J D. Fast relocalisation and loop closing in keyframe-based SLAM[C]//IEEE International Conference on Robotics and Automation. Hongkong， China：IEEE，2014：846-853.

[11]KEJRIWAL N， KUMAR S， SHIBATA T. High performance loop closure detection using bag of word pairs[J]. Robotics and Autonomous Systems， 2016， 77： 55-65.

[12]LI Bo， YANG Dan， DENG Lin. Visual vocabulary tree with pyramid TF-IDF scoring match scheme for loop closure detection[J]. Acta Automatica Sinica， 2011，37（6）： 665-673.

[13]MURPHY L， SIBLEY G. Incremental unsupervised topological place discovery[C]//IEEE International Conference on Robotics and Automation. Hongkong， China：IEEE， 2014： 1312-1318.

[14]Xia Yifan， LI Jie， QI Lin， et al. Loop closure detection for visual SLAM using PCANet features[C]//International Joint Conference on Neural Networks. Vancouver， BC，Canada：IEEE， 2016：2274-2281.

[15]HOU Yi， ZHANG Hong， ZHOU Shilin. Convolutional neural network-based image representation for visual loop closure detection[J]. arXiv preprint arXiv：1501.05241，2015.

[16]GOMEZ-OJEDA R， LOPEZ-ANTEQUERA M， PETKOV N， et al. Training a convolutional neural network for appearance-invariant place recognition[J]. arXiv preprint arXiv： 1505.07428， 2015.

[17]BAI Dongdong， WANG Chaoqun， ZHANG Bo， et al. Matching-range-constrained real-time loop closure detection with CNNs features[J]. Robotics and Biomimetics， 2016， 3（1）： 15.

[18]SHAHID M， NASEER T， BURGARD W. DTLC： Deeply trained loop closure detections for lifelong visual SLAM[C]//Proceedings of the RSS Workshop on Visual Place Recognition： What is it Good For.Ann Arbor， Michigan， USA：University of Michigan， 2016.

[19]GAO Xiang， ZHANG Tao. Unsupervised learning to detect loops using deep neural networks for visual SLAM system[J].Autonomous Robots， 2017， 41（1）：1-18.

[20]CHAN T H， JIA Kui， GAO Shenghua， et al. PCANet： A simple deep learning baseline for image classification[J].arXiv preprint arXiv： 1404.3606， 2014.

[21]LV Qin， CHARIKAR M， LI Kai. Image similarity search with compact data structures[J]. Thirteenth ACM International Conference on Information & Knowledge Management. Washington， DC， USA：ACM， 2004： 208-217.