COVFast-LCD:一种组合ORB和VLAD特征的快速回环检测算法

赵 珊,管 启,丁德锐,魏国亮,尚朝辉

1(上海理工大学 光电信息与计算机工程学院,上海 200093)

2(上海理工大学 理学院,上海 200093)

1 引 言

移动机器人在实现自主定位的同时,应具有探索未知环境并构建地图的能力,该任务被定义为同步定位和建图(SLAM)[1].在SLAM中,一个重要环节便是回环检测(LCD,Loop Closure Detection)[2],即机器人必须确定它是否已经回到先前建图的区域,以便在后续的探索阶段对之前产生的累积误差进行校正.

利用场景外观信息来检测先前访问过地方的过程被称为视觉回环检测[3],可以分为以下4类:1)基于全局特征的方法,例如Siam等人提出的使用HOG[4](Histogram of Oriented Gradient)描述符表示图像的Fast-SeqSLAM[5];2)基于局部特征的方法,例如一种将附加线索添加到原局部二值描述符中的方法[6],用于直接在描述符中捕获这些额外信息;3)基于词袋的方法,例如FAB-MAP[7]和DBoW2[8].FAB-MAP使用周柳树来学习场景外观的生成模型;DBoW2尝试从二进制特征创建可视词典,并以有效方式获得图像之间对应关系的直接索引,最后以组为单位匹配图像来提高回环检测的准确性.但由于其使用不具备旋转和尺度不变性的BRIEF[9]描述符来代表图像,导致该系统只能从平面轨迹和相似的视角进行回环检测;4)基于组合特征的方法,例如Korrapati等[10]提出的基于SURF[11]局部特征与局部特征聚合描述符[12,13](VLAD,Vector of Locally Aggregated Descriptors)的分层建图模型,以及一些流行的局部特征与CNN全局特征结合的方法[14].这类方法综合局部特征与全局特征优势,在图像搜索过程中首先使用全局描述符执行相似图像的粗搜索,然后使用局部特征来确认其关联.

VLAD描述符[12,13]是由H.Jégou等人提出并加以发展的.Korrapati H等[10]创造性地将VLAD引入机器人界,使用SURF描述符生成全局VLAD描述符,来实现分层视觉建图.虽然该方法召回率达到了FAB-MAP的两倍,但由于SURF描述符提取和VLAD计算时间过长,导致一帧图片平均处理时间长达150ms,远远无法满足视觉SLAM实时性的要求.R.Arandjelovic＇ 等人将传统VLAD与CNN网络相结合,提出了一种用于弱监督位置识别的CNN架构NetVLAD[15].此方法虽可达到较高的召回率,但在使用GPU的情况下仍需花费大量时间.最近,有学者将NetVLAD与VGG网络结合,开发了一种新的回环检测算法[16],在保证高召回率的情况下,提高了准确率,但同样面临花费时间过长的问题.

为解决此类问题,本文提出一种基于组合特征的快速回环检测算法COVFast-LCD(Combined ORB and VLAD for Fast Loop Closure Detection).具体地,当给定查询图像,第1阶段是使用图像局部特征ORB[17]量化生成全局的Binary-VLAD描述符,在此基础上快速地检索出N个回环候选项.第2阶段是再次利用ORB局部特征对这些回环候选项进行验证,获得最相似的图像,从而得到准确回环.本文的主要贡献总结如下:

·提出了Binary-VLAD量化算法,在不损失描述符代表性的前提下,加快了VLAD全局描述符的生成速度及其回环候选项的搜索速度;

·提出了一种改进的快速倒排索引策略,在满足全局粗检索阶段准确性要求的同时降低了存储成本;

·提出了一种用于几何验证的偏移稳定模型,因避免类似于RANSAC[18]算法基本矩阵计算的要求,提高了几何验证的效率.

2 COVFast-LCD算法框架

本文提出了一种新颖的基于ORB特征与VLAD描述符组合的回环检测算法COVFast-LCD.该算法主要由3个模块组成:图像描述模块、候选项搜索模块和候选项验证模块,其框架如图1所示.当输入图像进入流程时,提取图像的ORB特征并量化生成Binary-VLAD描述符.然后满足时间约束阈值限制的Binary-VLAD描述符在数据库中使用快速倒排索引策略进行粗搜索得到回环候选集.最后,对回环候选集进行ORB验证和几何验证获得正确回环.接下来的章节将详述3个模块中的创新性工作.

图1 COVFast-LCD算法框架

3 图像描述

图像描述方法可分为两类:全局描述符和局部图像特征.全局描述符因其表示简单,可以进行暴力搜索,但因其描述性不足,容易产生错误的回环候选图像.局部图像特征更强大,但通常每张图像需要数百个描述符,从而增加了匹配时间.因此,在实际应用场景中,一种常见方式是局部特征与全局特征组合使用,本文采用ORB局部特征与VLAD全局描述符来表示图像.

3.1 局部特征提取

如图1所示,首先对每张输入图片提取局部特征(关键点及其描述符向量).考虑到应用场景的实时性要求,本文选择处理一张图片平均只需11ms的二值局部特征ORB.它依赖OpenCV库中的ORB实现,默认在8个不同的比例下提取500个关键点,比例因子为1.2.该特征具备旋转和尺度不变性,不仅能减小计算代价,节约时间成本,而且保证系统可以从非常不同的角度识别位置.

3.2 Binary-VLAD描述符生成算法

正如引言所述,现有回环检测算法的实时性依然存在很大的改进空间.为避免对一张图片重复提取特征,造成时间和计算资源上的浪费,本文使用已获取的局部特征来生成可以代表整张图像的全局VLAD描述符.VLAD由SIFT[19]或SURF这样的局部图像描述符构建而成,是由局部描述符向量与视觉单词的残差累积生成的,表征了特征相对于中心(即视觉单词)的分布.因此,VLAD 描述符能准确地描述图像中的特征信息.进而,通过对生成向量的归一化处理避免了图像检索过程当中的突发(Burstiness)问题[20],即一个视觉元素在同一张图片中多次出现可能会减少其他重要特征的贡献,降低匹配的质量.不同于SIFT或SURF方法,本文采用的ORB描述符本质是一组二值向量,而上述的VLAD量化方法并不适用于这类二值局部特征,究其原因是对二值描述符简单向量作差无法代表该特征相对于中心的分布.为了克服这一不足,本节将建立一种适用于二值特征的VLAD生成算法,称之为Binary-VLAD算法.

类似于文献[13],针对训练集中全部图片的ORB描述符,使用k-means方法将其划分成k类,并获得k个聚类中心(单词),然后由ORB局部特征生成Binary-VLAD描述符的流程如下所述.

1.分配当前帧中每一个ORB描述符到对应的类中.具体地,记ORB描述符为x,寻找距离最近的聚类中心ci:

(1)

这意味着该描述符属于第i类.为了后续阐述的方便,记第i类有mi个描述符,每个描述符的维数皆为p.

2.计算第i类的每一描述符与其对应聚类中心ci的相同位元素的汉明距离.具体地,记第i类的第j个描述符为si,j,则si,j的第m位的汉明距离为:

ri,j,m=|[si,j]m-[ci]m|

(2)

其中[ci]m表示向量ci的第m个分量.进而,记由ri,j,m构成的向量为ri,j.值得一提的是,该向量可以由向量的异或运算直接获得:

ri,j=si,j⨁ci

3.计算同一聚类中的所有汉明距离生成的向量的累加和,即:

(3)

4.增广k个vi向量生成VLAD描述符,记为v.

5.计算图片中所有描述符的汉明距离的和:

(4)

6.设置阈值θ=D/(8pk),二值化向量v得到Binary-VLAD描述符:

(5)

注:Binary-VLAD算法是为二值特征量身定做的.一方面,因为需对每张图片都计算适应性阈值,所以相对于传统的VLAD描述符更具代表性.另一方面,因为二值表示的简单性,所以不需要经过降维处理后再进行后续的候选项搜索,避免信息损失.换句话说,Binary-VLAD算法不仅显著地减小计算时间,还使得后续全局搜索过程更为简单快速.

4 候选项搜索

在实际的任务中,数据库中的图像是动态更新的且相应的Binary-VLAD描述符是对应存储的.对于新采集的图像Iq来说,在获取全局Binary-VLAD描述符Vq后,候选项搜索的任务是在数据库中检索与Vq描述符匹配的图像.特别地,由于描述符是二值的,可通过汉明距离来计算相似性评分,并按汉明距离由小到大输出回环候选图片,从而寻找到最为相似的图像.

4.1 时间阈值限制

由于图像是按顺序拍摄的,相邻图像可能有很高相似性,这将导致假阳性回环.为了尽量避免这一现象的发生,本节对搜索的图像序列施加一个时间限制,即引入时间约束阈值β(其中β>0)用于防止对接近当前时间索引的图像生成回环候选.具体地,记当前时刻为t,不难有tL=t-β,则候选项只能在tL时刻之前的所有图片中搜索,即回环一定出现在tL时刻之前.

4.2 基于快速倒排索引的全局搜索策略

在SLAM中,经典的回环检测算法词袋模型(DBoW2)使用了倒排文件[21]的数据结构来加快搜索速度.在该算法中,通过词典将局部特征量化为一个词袋向量,然后使用倒排索引将该词袋向量与数据库中图像的进行比较,从而获得回环候选图片.不幸的是,该策略需要把该图像的信息同时添加到所有出现单词的倒排文件中,并计算相应的权重.在搜索阶段,同样对数据库中任意与当前图片有共同单词的图片计算评分,并累加全部单词下的图片评分,造成了高昂的计算代价.

因此,本文提出一种快速倒排索引策略,通过采用新的更新方式和搜索范围,使其满足全局粗搜索阶段快速性的要求.具体地,当前采集的图像Iq通常包含多个单词,在数据库更新阶段,将该图像的Binary-VLAD描述符和局部特征ORB描述符添加到出现频次最多的单词的倒排文件中,其数据结构如图2所示.在该图中,出现次数最多的单词是c7,则将该图片信息加入单词c7的倒排文件中.如果出现频次最多的单词不是唯一的,则把该图像的信息同时添加在相应单词的倒排文件中.

图2 图像数据库结构和更新方式

在候选项搜索阶段,提取新采集的图片中出现次数前d位的单词的倒排文件,然后计算倒排文件里存储的图片与该新采集的图片的Binary-VLAD描述符的相似性评分.显然,本文提出的策略相较于词袋模型的倒排索引,在满足粗搜索阶段准确性的要求的同时,计算量显著减小,内存消耗明显降低.虽然不可避免的损失了一些准确性,但接下来将通过搜索足够多的候选项以及在其中进行局部特征验证来弥补这一损失.

5 候选项验证

本节的目的是对搜索得到的候选回环项进行筛选验证,获得正确回环.值得一提的是,虽然采用Binary-VLAD描述符的搜索性能得到了较大程度的提高,但是相对于局部描述符,其量化过程中特征信息损失较大,牺牲了一些全局搜索的准确性.另外,传统的几何验证方法首先对查询图像和候选项图像采用随机一致性采样,获得n个特征点对,然后计算两张图片的基本矩阵,进而,基于该矩阵进一步计算得到两张图像对应特征点的重投影误差.为了得到正确的回环,一方面验证的候选项要足够多,另一方面基本矩阵计算等会造成资源和时间上的消耗,从而降低了回环检测的整体性能.

为克服上述缺陷,本节首先采用ORB特征对候选项进行筛选,删除错误的候选项,同时得到查询图像和候选图像匹配的特征点对,从而避免了随机一致性采样.然后借助于得到的特征点对,提出基于偏移稳定模型的几何验证算法,避免了基本矩阵的计算.

5.1 局部特征验证

相较于全局特征,局部特征提取的是图像中具有代表性的局部区域信息(如角点,边缘等),因此本节在全局粗搜索之后,对搜索结果进行局部特征验证,以删除错误的候选项,加快后续图像验证的效率.

(6)

其中ε为给定的阈值.显然,比值低于ε的特征匹配可视为好的匹配.如果一张候选图像匹配关键点对数大于给定的阈值m,那么其是正确回环的可能性相对较大,可被视为后续几何验证的候选项,反之则删除该图像.与此同时,这些特征匹配对可直接用于后续的几何验证,从而避免随机一致性采样.值得指出的是,如果没有一张候选图像通过验证,则清除所有候选项,认为该查询图像不存在回环.最后,根据经验,ε一般取值为0.7,m取值为“能恢复出相对位姿的最少匹配对数”8.在本文提出的COVFast-LCD算法中,由于局部特征采用二进制ORB特征,最近邻比测试的度量方式采用汉明距离,计算非常高效.

5.2 偏移稳定模型几何验证

几何验证即用几何约束来判断候选帧是否满足条件,是回环检测中常用的一种验证方法.考虑到已经获得了查询图像和候选项图像匹配的特征点对,受文献[10]启发,本节提出一种基于空间相似性的偏移稳定模型来完成几何验证.

假设机器人在局部平面环境中移动,考虑在方向不同,位置大致相同处获得的两张图像,图像中不同物体之间的距离会很好地保持.如果两幅图像来自相同的地方,那么相对于第1幅图像,第2幅图像中的所有物体都应该移动相同的量.换句话说,真实回环的特征点对偏移保持一致,而假回环的特征点对偏移毫无规律,如图3所示.更进一步来说,真正回环的偏移量数值保持稳定,波动小,而假回环的偏移量不稳定,波动大.基于这一原理,本文采用偏移量方差来表示偏移量的稳定程度,称之为偏移稳定模型:

图3 真假回环特征点对偏移比较图

(7)

与常用的RANSAC[18]方法相比,此模型简单高效,无需计算基本矩阵,只要简单的像素坐标作差,便可完成几何验证的任务.在局部特征验证环节已得到匹配关键点对的情况下,再使用该模型进行几何验证,非常快捷高效,且不以牺牲召回率为代价.

6 实验与结果分析

为评估本文提出的COVFast-LCD算法性能,本节在3个公开数据集上进行了测试,并与3种具有代表性的回环检测算法进行了比较,以验证所提出算法的优越性.与之对比的算法是:a)经典的词袋模型(DBoW2)[8]方法;b)基于传统VLAD与流行CNN网络结合的NetVLAD算法[15];c)最新的NetVLAD与VGG网络融合的VGG-NetVLAD算法[16].实验所用计算机配置为:Intel Xeon Silver 4116处理器,一块 GTX1080 显卡;实验环境为:Ubuntu 16.04.其中NetVLAD,VGG-NetVLAD两种方法实验时使用quadro m1000m GPU.

6.1 数据集

实验测试的数据集为3个公开可用的图像集:a)Malaga 2009 Parking6L[23],b)NewCollege[7]和c)City Center[7],其中Malaga 2009 Parking6L[23]是由Jose-Luis Blanco[24]等人发布的一组具有厘米精度的人工标注的机器人数据集,NewCollege[7]和City Center[7]都是由牛津大学发布的常用的回环检测评估测试数据集,数据集的更详细描述见表1.3个数据集都由双目图像组成,本实验只使用左侧相机图像,且从每个数据集中随机选择20%的图像形成训练数据集.

表1 数据集描述

6.2 实验参数设置

毫无疑问,COVFast-LCD算法的性能依赖于如下参数:时间约束阈值β,倒排索引搜索范围(即提取倒排文件的单词数d),局部特征验证范围(即全局搜索结果中需要进行ORB验证图像数N).

由于数据集内容、长度和重访长度不同,每个数据集的最佳参数也可能不同.时间约束阈值和倒排索引搜索范围皆影响查询时间和召回率.局部特征验证虽能极大程度避免假回环出现,但其毕竟相对而言较为耗时.因此需要在实验中根据随着该参数变换的时间和召回率表现,寻找一个性价比最高的局部特征验证范围.接下来,本节使用控制变量法为每个数据集寻找最佳参数.具体实验结果为:a)查询时间、召回率与时间约束阈值的关系如图4(a)所示;b)查询时间、召回率与倒排索引搜索范围的关系如图4(b)所示;c)验证时间、召回率与局部特征验证范围的关系如图4(c)所示其中,左纵坐标为时间(单位毫秒),右纵坐标为召回率,横坐标分别为时间约束阈值、搜索范围与验证范围.通常地,查询时间(或验证时间)短、召回率高所对应的参数值是最佳的选择.

图4 3个数据集控制变量的变化曲线

由图4中3组图可知,Malaga 2009 Parking 6L数据集的最佳参数为:β=80,k=3,N=12,即时间约束阈值β=80,提取前3个单词的倒排文件,对全局搜索结果的前12个进行局部特征验证;NewCollege数据集的最佳参数为:β=70,k=3,N=14;City Center数据集的最佳参数为:β=100,k=2,N=14.后续实验在每个数据集的最佳参数基础上进行.

6.3 与其他算法的比较

为验证本文提出的COVFast-LCD算法的优越性,本节通过对比实验,从时间性能,准确率-召回率两个方面来说明,具体如下所述.

6.3.1 时间性能比较

由于视觉SLAM系统常常运行于机器人,无人机,自动驾驶汽车等环境中,实时性是一项非常重要的性能要求.此外,消耗时间短的回环检测算法进一步满足了在大尺度场景下应用的需求.

对于本文所提出的COVFast-LCD算法,在第1个模块中,局部特征提取和VLAD生成不受地图更新的影响,实验得到其花费时间分别为13.76毫秒和0.74毫秒.而第2个模块的全局搜索和和第3个模块的局部特征验证的时间消耗通常会随着地图的实时更新而增加.在本文的实验中,全局搜索平均只需花费0.11毫秒,局部特征验证平均只需花费4.78毫秒,实验结果如表3所示.进而,由该表可知本文所提出的COVFast-LCD算法的时间消耗最小,比第2位的DBoW2算法快3毫秒,比基于深度学习的方法更是快了近10倍.

表3 时间性能比较

6.3.2 准确率-召回率比较

回环效果主要通过准确率和召回率来衡量.准确率是检测到真实回环的数量(真阳性)与检测到回环的总数(真阳性和假阳性)的比率,而召回率是检测到真实回环与现有真实回环总数的比率(真阳性和假阴性的总和).通常用准确率-召回率曲线(简称P-R曲线)反映闭环检测算法的综合性能.

4种算法在3个数据集上的P-R曲线如图5所示.由该图可知,本文方法在3个数据集上100%准确率时的召回率都表现最佳:在Malaga 6L 数据集上,4种算法100%准确率下的召回率分别为0.83、0.75、0.72、0.79,可见COVFast-LCD算法效果最好;在NewCollege数据集上,4种算法100%准确率下的召回率分别为0.59、0.56、0.31、0.31,同样是COVFast-LCD算法效果最好;最后在City Center数据集上,4种算法100%准确率下的召回率分别为0.39、0.31、0.35、0.39,同样是COVFast-LCD算法效果最好.

图5 3个数据集下4种方法的PR曲线

综合时间性能,本文所提出的COVFast-LCD算法不仅召回率略高于其他方法,速度更为优越,因此非常适合视觉SLAM实时运行的要求.

7 结 论

本文提出一种局部ORB特征与全局VLAD描述符组合的快速回环检测算法(COVFast-LCD),此方法融合局部特征和全局特征优点,显著提高算法速度,且不以牺牲召回率为代价.首先使用Binary-VLAD特征进行全局粗搜索,然后使用ORB特征对其结果进行精细验证,最后利用偏移稳定模型进行简单的几何验证.与经典的回环检测算法DBoW2和近年来最流行的基于深度学习的NetVLAD,VGG-NetVLAD方法相比,实现了成功率略高于它们,且时间远快于它们的效果.接下来会重点研究如何在满足实时性的前提下大幅度提高召回率,并测试本算法在SLAM框架下的表现.