余 宇，胡 峰

(重庆邮电大学 计算机科学与技术学院，重庆 400065)

0 引 言

同步定位与建图(simultaneous localization and mapping，SLAM)[1]自提出以来，一直是机器人领域的重要研究内容，其主要目的是实现运动物体在陌生环境中自身定位及增量式的地图构建。进入2000年以后，随着计算性能的提高，主流的SLAM系统多采取摄像头作为传感器，这种基于视觉图像信息来感受周围环境的SLAM系统称为视觉SLAM[2]。其系统核心功能被分为3个独立的模块，分别是前端视觉里程计、回环检测和后端优化。前端视觉里程计部分主要利用帧间的多视几何关系计算出自身姿态变化，而后端优化主要解决的问题是消除整个系统中由于各种原因产生的噪声对位姿估计和建图的影响。在视觉SLAM系统长时间的自主导航运行中，不可避免的会因为邻近帧间的误差积累导致后端的优化收敛出现严重的偏差，这样的偏差在建图过程中会反映为漂移。因此，在视觉SLAM系统中引入了回环检测模块，用于消除累计误差，控制建图的全局一致性。

1 相关工作

传统的回环检测方法分为两种。一种是基于视觉里程计的方法，这种方法是利用视觉里程计中的几何关系，假设相机回到了之前的位置，再进行是否构成回环的判断，但由于视觉里程计自身存在偏移误差，这种判断逻辑准确性较低，误差较大[3]。另外一种方法是基于视觉图像的方法[4,5]，根据帧间相似性来判断回环，把回环检测问题归纳成为一个场景识别问题。其主要思路是通过前端摄像头获取到场景影像数据，运用计算机视觉的方法来计算图像间的相似性，从而判断回环。因为能够有效的在不同环境中工作，这一方法自21世纪初被提出以来，已经成为视觉SLAM研究中的重点。

基于视觉图像方法的核心问题是如何计算图像间的相似性，现阶段较常使用方法是在图像中标定人工设计的关键点，然后进行特征描述子之间的相似度计算。在FAB-MAP[6]中使用了SIFT(scale-invariant feature transform)算法提取图像特征，然后通过构建视觉词袋模型(bag of visual word，BoVW)进行回环检测，因为在静态环境中的较高准确率得到了广泛应用。而在ORB-SLAM[7]的回环检测模块中使用了FAST算法提取图像关键点，BRIEF算法作为特征描述子，同样通过构建BoVW进行回环检测，因为其快速的图像特征提取速度，在实时性要求比较高的视觉SLAM系统中得到广泛使用。Sünderhauf等[8]提出了使用GIST算法提取图像特征，改进的BRIEF算法作为特征描述子的回环检测方法，该方法对图像进行全局特征提取，提高了有效回环的检测率。但在回环检测中无论是对图像进行全局特征提取还是局部特征提取，都是基于设计算法人员的人为经验，当在现实环境中面对光照变化，天气变化，季节变换等情况时会出现准确率下降，不能够稳定的工作。而在实际场景中当图像剧烈变化时，会出现视觉单词无法匹配和旋转不变性较差等问题。

近年来，深度学习方法在计算机视觉方面的研究得到飞速发展，在图像分类、图像检测、图像分割等领域都取得了极大的成功，视觉SLAM系统的研究也开始尝试和深度学习进行结合。Konda和Memisevic[9]提出了一个端到端的卷积神经网络用于视觉里程计中，在实际环境中可以有效预测摄像机方向和速度的变化。Costante等[10]发现在图像发生了光照变化和运动模糊的情况下，利用卷积神经网络能够有效地进行帧间估计确定位姿。Sünderhauf等[11]提出的利用物体对象进行语义地图的构建方法中，使用了SSD卷积神经网络进行关键帧的物体检测，构造出了信息更丰富的语义地图。McCormac等[12]在提出的基于卷积神经网络的稠密三维地图的构建中，使用了卷积神经网络对生成的2D场景进行物体分类，构建出具有物体对象标签的地图。在将深度学习的方法应用到回环检测方面，Chen等提出基于CNN(convolutional neural network)的回环检测算法[13]，在数据集上显著提升了召回率。在实际运行中，面对摄像头所捕捉到的图像场景光照变化和角度变形，导致回环检测准确率急速下降的问题时，Xia等[14]提出基于AlexNet模型进行特征提取然后使用SVM算法进行二次训练的回环检测模型，相比人工设计特征的算法具有更好的鲁棒性。Gao等[15]通过非监督学习中的自编码(Autoencoder)算法提取图像特征后，使用相似度矩阵作为度量方式进行回环检测，在数据集上取得较好成绩。虽然以上方法在和传统人工设计特征相比都具有更高的准确率和更强的鲁棒性，但是都会出现过高维度的特征向量增加了计算复杂度，庞大的神经网络训练不适合应用在常搭载SLAM系统的移动平台，不适合的神经网络模型应用在回环检测中容易形成过拟合等问题。

2 基于深度学习的回环检测算法

面对以上出现的问题，我们提出了基于深度学习的回环检测算法。算法整体分为两个部分(如图1所示)，基于卷积神经网络VGG-19[16]的图像特征向量集构造和基于局部敏感哈希(locality sensitive hashing，LSH)[17]算法的快速回环检测。在第一个部分，我们通过VGG-19对图像集进行整体特征提取并构造对应特征向量矩阵，解决了人工设计的特征提取算法在回环检测中面对光照和角度变化时准确率下降问题。在第二个部分，我们提出基于余弦距离的LSH算法对构造的特征向量矩阵进行降维聚类，加速回环检测识别，解决了高纬度的特征向量引起的计算性能开销过大无法快速检测回环的问题。

图1 特征向量矩阵的构造和LSH算法聚类过程

2.1 基于VGG-19的图像特征向量集构造

在图像特征提取时选择不同的算法会直接影响最终回环检测的效果，而预训练的卷积神经网络VGG-19在图像特征提取上具有良好的特征表述能力与可操作性。在2014年的ILSVRC大赛中VGG-19使用了预训练的VGG-11参数做初始化，在图像分类和定位项目上取得了优异的成绩，说明在图像任务中直接使用预训练的VGG-19具有较高增益。此外，VGG-19中使用了3*3的小卷积核来代替常见的大卷积核，更多的小卷积核的使用可以使决策函数在进行特征辨别的时候更准确，有效避免大卷积核对于图像部分特征会出现多次卷积导致提取困难的情况，对于图像的细节特征描述也会更加精确。因此，我们选择了在ImageNet数据集上进行预训练的卷积神经网络VGG-19作为图像特征提取的网络结构。

VGG-19一共拥有5个卷积层模块和3个全连接层，因为FC8层是为了比赛中图像分类目的作输出层所以不考虑作为特征提取层。对于其余卷积层和全连接层，我们在不同数据集下作了效果比较(包括一个池化层)。如图2所示，Conv1层提取特征过于粗糙不具有蕴含图像全局信息能力；Conv3层提取特征向量维度过高不适宜后续运算；而FC7层提取特征稀疏性较好，特征向量维度适中且能够对图像做较好的区分，最终选择了FC7层的输出向量作为图像特征表示。

图2 VGG-19不同中间层的图像特征效果

我们改变了VGG-19的输出结构，使其能够在前向传播过程中直接输出指定层的图像特征向量。以输入单张三通道图像fi为例，首先我们会对图像进行去均值标准化处理

(1)

al=σ(zl)=σ(al-1*Wl+bl)

(2)

ReLU(x)=max(0,x)

(3)

其中，上标l代表当前层数，al代表第l层的输出，*代表卷积，W代表卷积核，b代表偏置量，σ(·) 代表了使用的激活函数ReLU。同时，在每个卷积层的后面会接一个最大池化层，可以有效提高感受野大小，池化层的前向传播方式是

S=βdown(C)+b

(4)

其中，β和b为标量， down(C)表示对输入的矩阵C进行下采样。在网络末端有FC6和FC7作为全连接层，对隐藏层学到的分布式特征进行映射，使用卷积核进行全层卷积实现

(5)

同时，为了加快图像特征的提取，我们对VGG-19的BATCH做了调整，对于一次性输入的k张图像，能够在前向传播到FC7层时直接输出一个 (k,4096) 的特征矩阵M

(6)

2.2 基于余弦距离的局部敏感哈希算法

局部敏感哈希是一种用于高维空间数据向低维空间映射的最近邻查询算法。不同于一般的哈希算法，该算法的主要目的是让在高维空间内相似度高的数据通过特定的Hash函数，能够映射为同一个Hash值，在网页去重、图像和视频检索、聚类搜索等领域均取得了比较好的应用效果。

首先在度量空间Μ=(M,d) 内定义一个LSH函数簇F={h∶M→S}， 同时定义距离阈值R>1和σ>1， 对于任意两点p,q∈Μ有

ifd(p,q)≤RthenPRh(h(p)=h(q))≥P1

(7)

ifd(p,q)≥σRthenPRh(h(p)=h(q))≤P2

(8)

其中，函数d(p,q) 表示向量之间的度量，PRh表示概率，当P1>P2时，我们就把这样的一个LSH函数簇F称为是 (R,σR,P1,P2) 敏感的。对于不同的度量方式我们可以确定不同的LSH函数簇，在本文中我们采用随机超平面的思想[18]，把基于余弦距离的LSH函数簇应用在了回环检测上。

我们先定义了特征向量之间的余弦距离度量，其中Α,Β分别为两张图像的特征向量，Αi,Βi分别代表向量Α,Β的各分量

(9)

在高维空间中对于任意两个特征向量A,B∈Μ均存在被一随机超平面分割为可能的3种情形(如图3所示)。

基于此，我们可以构造在欧几里得空间内基于余弦距离度量的LSH函数hμ

(10)

其中，v表示我们的图像特征向量，μ表示生成的随机超平面。对于v中的任意两向量v1，v2都存在θ1，θ2。 在θ1<θ2的情况下，当v1，v2两向量的夹角小于θ1时有

(11)

当v1，v2两向量的夹角大于θ2时有

(12)

那么我们便可以把式(10)中的hμ称为在余弦距离度量下 (θ1,θ2,(π-θ1)/π,(π-θ2)/π) 敏感的，将其应用在回环检测策略中便可以大幅度降低匹配所需查询时间。

2.3 基于LSH算法的回环检测策略

如果直接采用式(10)对HashTable进行构造，往往会出现待匹配向量查询范围窄和聚类区分度不够等问题，进而导致FalsePositive和FalseNegative增加。我们为了进一步提高LSH算法聚类的准确性和回环检测的性能，可以使用“AND”和“OR”两种策略来对式(7)和式(8)中的P1,P2进行调整。“AND”策略指的是通过增加超平面的方法，对于空间中的任意两个向量v1，v2， LSH函数簇F={h1,h2,h3…hl}， 当且仅当每一个hn(v1)=hn(v2){n=1,2…l} 时，才有h(v1)=h(v2)。 通过这种策略使P1,P2变为P1l,P2l， 减小了FalsePositive的情况。“OR”策略指的是在函数簇F={h1,h2,h3……hl} 中只要存在任意一个hn(v1)=hn(v2){n=1,2…l} 时，便有h(v1)=h(v2)， 通常是以增加映射以后的HashTable实现，假设增加以后HashTable数量为t， 则通过这种策略使P1,P2变为1-(1-P1)t, 1-(1-P2)t， 减小了FalseNegative的情况。

在本文中我们改进了“OR”策略，并将改进以后的“OR”策略与“AND”策略结合，以此增加待匹配图像的搜索范围，提高回环检测的准确率。我们首先定义了l为超平面的个数，通过生成l个Hash函数构成哈希函数簇F={hi|i=1,2,…l}， 然后对每一个特征向量ν进行映射以后得到的一个l位的Signature(后文中以S表示)。最后把被映射为相同S的特征向量聚为一类并投射到同一个Bucket中，这样的Bucket集合便构成了我们的HashTable，具体步骤如下：

算法1：构造HashTable算法

输入：通过VGG-19提取的图像特征向量矩阵：Μ={vi|i=1,2,…n}， 哈希函数簇：F={hi|i=1,2,…l}， 随机超平面个数：l。

输出：HashTable集合T={bi|i=1,2,…m}。

步骤1 对每一个特征向量vi(i=1,2,…n)， 通过哈希函数簇F进行映射(由式(10)决定)，得到每一个特征向量的l位S， 构成集合Si(i=1,2,…n)。

步骤2 对集合Si(i=1,2,…n) 进行聚类，相同的S生成一个Bucket，由此构建了新的集合T={bi|i=1,2,…m}。

步骤3 返回T。

基于构造的HashTable，我们在回环检测的时候，对“OR”策略进行了改进。首先定义了一个偏移量γ， 然后对于任一待匹配的图像，允许与有γ个位偏差的S所对应的特征向量进行余弦距离比较(由式(9)决定)，具体步骤如下：

算法2：回环检测算法

输入：待匹配的图像：f， 哈希函数簇：F={hi|i=1,2,…l} (注意，输入的哈希函数簇应保持和构建Hash Table时一致)，阈值：τ， 偏移量：γ。

步骤1 将f输入到VGG-19中，经过前向传播算法得到对应特征向量vf。

步骤2 将vf经过哈希函数簇F映射得到对应的Sf。

步骤3 在构建的HashTable中，计算与Sf有γ个位偏差的所有可能映射，构成待匹配集合V。

步骤4 对属于集合V中的所有特征向量与vf进行余弦相似度计算。

2.4 算法时间复杂度分析

如果单纯使用暴力匹配方式计算所有特征向量之间的余弦距离，算法时间复杂度将达到O(n2)。 而我们在构建HashTable的算法1中，时间复杂度为O(l*n)， 其中，l是超平面个数，n是特征向量矩阵中的向量个数。在回环检测的算法2中，时间复杂度取决于集合V， 远小于数据集大小，可以近似为O(1)， 有效降低了算法时间复杂度。如图4所示，图4(a)表明了HashTable的规模随超平面增加基本呈线性增长，图4(b)表明匹配耗时随偏移量增加呈正态分布。

图4 Hash Table的规模和匹配耗时随偏移量增加的变化趋势

3 实验结果与分析

3.1 实验数据集

在本文中我们使用了由牛津大学机器人团队收集的NewCollege和CityCentre两个视觉SLAM回环检测数据集，在数据集中分别包含2146张和2474张由移动机器人在室外环境中采集的左右对图像(如图5所示)，在数据集中下标是奇数的为左摄像头采集，偶数的为右摄像头采集，图像格式为Jpg，尺寸为640*480像素，数据集中包含有回环真值方便研究人员对比实验结果。实验硬件平台为2.7 GHz Intel Core i5处理器，8 GB DDR3内存。

图5 New College和City Centre数据集中左右摄像头采集图像

为了更好体现算法性能，我们根据左右摄像头采集的图像重新分割了数据集，其中NewCollegeLeft表示左摄像头采集到的所有图像，NewCollegRight表示右摄像头所采集的所有图像。以此类推，我们也对CityCentre数据集进行了分割，构造了CityCentreLeft和CityCentreRight两个子数据集(见表1)。

表1 数据集划分

3.2 回环检测准确性比较

在性能评价上我们采用了准确率-召回率(precision-recall，P-R)曲线和平均准确率来展示算法对于回环检测的性能。首先我们比较了在不同超平面和偏移量的情况下的P-R曲线。

从图6和图7中可以看出，无论是在NewCollege或CityCentre数据集上，我们在设定16个超平面和8位偏移量的情况下均取得了最好的效果，随着超平面数量和偏移量的下降，算法性能开始出现下滑。不难发现，算法在CityCentre数据集上的效果普遍优于在NewCollege数据集上的效果，这是因为CityCentre数据集中的图像场景中有更多的人和车辆，预训练的VGG-19模型对于这样的场景识别能力更强。接下来，我们分别提取了FAB-MAP[6]、ORB-SLAM[7]、文献[14]中基于Alexnet的回环检测方法以及文献[15]中基于Autoencoder的回环检测方法，并在数据集上与本文提出的算法做了平均准确率对比。

图6 在数据集City Centre上的P-R曲线

图7 在数据集New College上的P-R曲线

从表2中可以看出，基于深度学习使用了Autoencoder和AlexNet的算法在平均准确率上均高于传统的人工设计特征进行提取的算法。再一次验证了，基于深度学习的图像特征提取具有更好的光照不变性和对图像场景的识别能力。其中，本文提出的算法在两个数据集上相比FAB-MAP的平均准确率提高了12%，相比ORB-SLAM提高了15%，相比Autoencoder提高了8%。另外，在NewCollege数据集上，本文提出的算法略低于AlexNet的算法，在CityCentre数据集上，本文提出的算法与基于AlexNet的算法大致相当。这是因为在基于AlexNet的算法中直接使用了高维的特征向量进行二次训练，提高了模型的拟合能力。

表2 算法在数据集上的平均准确率

3.3 时间性能比较

在视觉SLAM系统中为了实现机器人的同步定位与建图，对于回环检测模块的实时性有着较高的要求。基于此，从以下3个方面对算法的时间性能进行了比较。首先，我们随机抽取了两个数据集中的2000张图像，对于不同算法构造单张图像特征描述的平均耗时进行了比较。

从表3中可以看出相比于另外3种算法，基于AlexNet的算法和本文提出的算法大幅度降低了构建图像特征描述所需耗时，原因在于传统方法中的关键点提取与特征描述子的构建需要耗费一定的时间，而基于深度学习的方法能够直接输出图像的特征表述。另外，仅仅从构造单张图像的特征描述所花费时间上进行比较，本文提出的算法与基于AlexNet的算法差异不大，主要原因是因为两者在构建单张图像的特征描述上具有相似结构。

表3 算法在数据集上构造特征描述时间比较

接下来，基于VGG-19构造的图像特征矩阵，我们比较了在检测回环时直接使用暴力匹配与LSH算法进行降维以后再进行匹配的耗时(设定超平面个数为16，偏移量为8，时间单位：s)。

从表4中可以看出，相比于暴力匹配的遍历方法，LSH算法大幅度提升了检测回环的时间性能，满足了回环检测模块对于实时性的要求。

表4 暴力匹配与LSH降维后进行匹配耗时

最后，我们对以上算法在NewCollege和CityCentre上做了匹配时间比较，匹配时间指的是对于新加入的图像进行特征提取和在数据集中检测回环的时间之和，结果见表5(时间单位：s)。

表5 算法在数据集上的匹配时间比较

从表5中可以看出，本文提出的算法在时间性能上具有较大优势，相比FAB-MAP提高了59%，相比ORB-SLAM提高了29%。另外，相比于AlexNet，我们在可以接收的范围内牺牲了一部分准确率，但提高了28%的时间性能，更能够满足视觉SLAM系统的实际应用。

4 结束语

目前，视觉SLAM与深度学习的结合还处于初步阶段，深度学习中的卷积神经网络是通过模拟人类大脑神经的工作方式而构造的，虽然大多数科研人员认为卷积神经网络技术是一个“黑盒”模型，但不妨碍其在计算机视觉领域的巨大成功。而视觉SLAM进行环境感知的形式都是通过图像或者视频等形式进行，因此将深度学习的方法应用到视觉SLAM中是一项非常有意义的研究。基于此，本文提出的结合卷积神经网络和LSH算法的视觉SLAM回环检测算法较已有的回环检测算法显著提高了检测效率和准确率，能够有效降低光照、天气、角度等变化对回环检测的影响，并满足视觉SLAM系统对于实时性的要求。在未来，我们希望对如何建立一个端到端的基于深度学习的完整视觉SLAM系统展开研究。