一种基于全局-局部联合二进制特征的快速闭环检测算法

1 引 言

实时定位与地图构建(Simultaneous Localization and Mapping，SLAM)是机器人在未知环境下自主导航的一个核心问题.近年来，随着SLAM技术的发展，基于相机的视觉SLAM因为低廉的价格受到越来越多研究者的关注.基于视觉的闭环检测是视觉SLAM的一个重要环节，主要通过图像识别曾经到过的场景.闭环检测对减小系统产生的累计误差，建立全局一致性地图至关重要.

目前基于视觉的闭环检测算法主要分为4类：1)基于视觉词袋模型(Bag of Visual Word，BoVW)的闭环检测方法.该方法比较经典的工作为FAB-MAP[1].但是基于词袋的方法只关注单词本身忽略了单词之间位置关系，因此容易出现一定程度的感知偏差[2]；2)基于局部特征的闭环检测方法.近年来，出现了许多高效局部特征提取算法，推动了闭环检测的发展，如SURF[3]，ORB[4]，BRISK[5]等；3)基于全局特征的闭环检测方法.例如，Oliva等人提出的Gist全局特征[6]，Sunderhauf等人的BRIEF-Gist全局特征[7]；4)基于组合特征的闭环检测算法.此方法将多种图像特征进行组合，避免了单一图像特征的局限性.这方面突出的工作是Wang等人提出的结合全局特征和局部特征的拓扑地图定位算法[8]，其使用由粗到细的场景匹配策略.

不同于传统的图像特征提取方案，基于深度学习的图像特征提取也是闭环检测发展的重要方向，该特征对光照、遮挡和视角变化都有较强的鲁棒性.使用该特征的闭环检测对复杂环境拥有更好的适应性，并且特征包含一定程度的语义信息[9].2015年Xia最先利用简单的PCANet实现闭环检测[10].随后，Hou等人使用Place-CNN模型提取全局特征进行闭环检测[11]，并对网络不同层提取特征的表现了进行评估.2019年由Shan等人提出的FILD方案，该方案将利用MobileNetV2网络模型得到的全局特征和SURF特征相结合，通过GPU加速实现高准确率实时闭环检测[12]，是当前最好的闭环检测算法.虽然基于深度学习闭环检测算法有着不错的性能，然而该方法非常依赖用于训练的场景数据，并且卷积神经网络的前向传播过程往往需要GPU才能实时计算.在无人机等计算资源受限的微型机器人或小型化平台上，采用深度学习的闭环检测会占用大量系统资源，从而影响SLAM定位和建图等主线程的实时性.

综上所述，虽然基于外观的闭环检测取得了丰富的研究成果，但是目前并没有一种性能优异且能够在计算资源受限的设备中部署SLAM闭环检测方案.在Wang等人工作的基础上，我们进一步优化组合特征的提取和检索方法，提出一种联合二进制特征的快速闭环检测算法.

本文的主要创新可归纳为：1)使用局部差异二值算子[13](Local Difference Binary，LDB)提取图像的全局和局部二进制特征，缩短特征提取时间的同时，降低了图像特征的存储成本；2)保证搜索精度的前提下，通过基于汉明距离的增强局部敏感哈希算法[14](Locality Sensitive Hashing，LSH)加快了大尺度场景中全局特征检索速度；3)使用二进制局部特征匹配检查全局搜索的结果，这种层次式的匹配策略在提高系统效率的同时又可以保证检测结果的高可靠性；4)优化多种图像特征存储结构的同时，通过索引机制加快数据库中的特征信息访问速度，降低了系统运行时的内存占用.

2 算法概述

本文所提出的算法主要由3部分组成，其系统框架如图1所示.第1部分为图像特征提取模块，该模块将查询图像统一为固定大小的正方形.使用局部差异二值算子(LDB)分别提取正方形图像的512维全局特征和以每个FAST关键点[15]为中心45×45大小区块的256维局部特征描述子，根据图像序号将全局特征和局部特征一起存储到数据库中.第2部分为全局特征搜索模块，使用基于汉明距离的LSH进行全局搜索，然后通过搜索得到图像索引查找数据库中对应全局特征V，计算V与当前图像全局特征的距离，如果距离小于阈值则将其索引作为全局搜索的最终结果.第3部分为局部特征检验模块，根据全局搜索得到的索引找到数据库中对应的局部特征描述子，通过索引帧和候选帧之间的局部特征匹配验证全局特征匹配的结果，如果正确匹配对数量超过阈值N则认为是正确的回环帧并将其作为最终输出.

图1 闭环检测系统框架

Fig.1 framework of closed-loop detection system

3 图像特征提取

为了完成闭环检测任务，需要将图像抽象为某种数字特征，用以描述该张图片或图片所表示的场景.按照描述对象的不同，提取的特征又可分为全局特征和局部特征.其中，全局特征是利用整幅图像的纹理，颜色，形状等信息生成高维的数字向量；局部特征是从图像中具有代表性局部区域提取的信息，这种局部区域通常为角点，边缘等.在本节中，将介绍如何利用LDB算子快速提取这两种图像特征.

3.1 全局特征提取

LDB算子最初由杨欣等人提出，作为一种局部特征描述子生成方法，其利用底层的灰度信息同时也提取了中层视觉中的梯度信息，这种多重信息的混合使用极大地提升了数字特征的区分能力，故本文将其作为全局特征描述子，以增强图像的代表性.

在使用LDB算子计算全局描述子之前，为了方便图像区块划分和后续计算，首先将输入图像统一为固定大小的正方形图像块P.然后将图像P划分成n×n个等尺寸的图像块，利用式(1)对网格中两个不同的图像块提取信息.

(1)

其中，i和j表示网格中的第i和第j个图像块，Fun(i)是从第i个区块中提取信息的函数.Fun(i)包含以下3种形式：

Fun(i)={FI(i)，Fdx(i)，Fdy(i)}

(2)

其中：

(3)

FI(i)表示提取第i个图像块的平均灰度，Gx(i)和Gy(i)分别表示图像块i中x和y方向上的梯度大小，m表示图像块i中像素的数量，平均灰度和图像块的梯度都可利用积分图加速计算.由式(1)可知，执行一次Bin函数会产生3个二进制位.当n×n网格中所有的图像块都经过式(1)处理后，将产生的所有二进位拼接起来，组成一个维数为bn的二进制向量x，其中：

(4)

如果将x作为最终的图像全局描述子，那图像块的尺寸会影响全局描述子的鲁棒性和区分性.图像被划分成较大网格会产生更具鲁棒性的全局描述子，从较小网格中提取的全局描述子会包含更多的细节信息，因此比从较大网格中提取的全局描述子更具区分性.

如图2所示，为实现全局描述子的高鲁棒性和高区分性，将图像P划分成4种不同大小的网格，网格大小分别是2×2、3×3、4×4和5×5.将大小为n×n网格上产生的二进制向量xn×n按照式(5)组合形成原始的LDB描述子v.

图2 全局特征提取

Fig.2 Global feature extraction

v=x2×2++x3×3++x4×4++x5×5

(5)

其中++表示串联操作，通过式(4)和式(5)可得到原始的LDB描述符v的维数为1386.划分为不同大小网格会导致原始的LDB描述符某些位之间存在一定的相关性，造成一定程度的信息冗余.通过随机选取描述符v中一定数量的二进制位可以减少信息的冗余.所有被选择的二进制位构成图像的全局描述子，最终全局描述子的维数为D.全局特征由LDB全局描述子描述.

3.2 局部特征提取

不同于可以直接提取的图像全局特征，局部特征的提取包括关键点检测和描述子构建两个步骤.关键点检测是找到所有像素点中对某种函数响应值比较高的像素点，利用这些像素点标记图像中的特殊区域.然后通过描述子构建将关键点周围的图像块信息转换成数字特征.

在关键点检测阶段，本文使用增强FAST算法提取关键点.FAST是一种快速关键点检测方法，该方法认为当一个像素与邻域像素灰度值差别较大时，该像素就可能是关键点.增强FAST算法是FAST算法的改进，主要解决FAST检测器不能检测特征方向的问题.在特征描述阶段，由3.1节可知LDB算子原本就是一种局部特征描述子生成方法，因此可直接生成关键点周围区域的LDB描述子.使用LDB描述子描述局部特征一方面可提高局部特征的鲁棒性和区分性，另一方面直接利用计算全局描述子时产生的积分图像计算局部LDB描述子，积分图的重复使用极大的加快了描述子的计算过程.

但实际中，机器人不能准确的回到原来经过的位置，当前机器人位姿跟先前的位姿是不完全相同的，所拍摄的图像会有一定程度的旋转或扭曲，因此产生LDB描述子也与之前不同.为实现局部LDB描述子的旋转不变性，需估计FAST关键点的主方向.我们通过灰度质心法[16]估计特征点主方向，该方法先通过图像块的矩计算特征点邻域的质心，图像块的矩定义为：

(6)

在式(6)中，I(x，y)表示位于图像(x，y)处的像素灰度值.然后通过一阶矩得到该区域的质心C的坐标为：

(7)

最后，将关键点坐标和质心组成一个向量，将向量的角度θ作为该关键点的主方向：

(8)

得到关键点的主方向后，利用关键点主方向旋转特征点为中心45×45大小积分图像.在旋转后的积分图像上利用式(1)生成原始LDB描述子.类似于全局描述子的生成过程，为了避免某些位之间的相干性并限制描述子的维数，在原始LDB描述子上随机选择256个二进制位组成最终的LDB描述子.

4 基于增强LSH的全局搜索

当输入图像提取全局特征Q后，便需在数据库中进行全局搜索查找与其相似的全局特征，数据库中存放所有先前拍摄图像的特征信息.全局搜索是在数据库中逐一计算所有历史图像对应的全局特征与Q的距离，如果存在全局特征Q1与Q的距离小于设定阈值，则认为Q1对应的帧为全局搜索的结果.但在大尺度场景中，随着机器人经过的位置增多，需要查询的图像信息也会增多，导致每一次全局搜索消耗的时间都在增加.针对全局搜索的这一缺点，本文采用基于汉明距离的增强LSH算法加速搜索.

4.1 LSH搜索

LSH是一种被广泛使用的最近邻搜索(Approximate Nearest Neighbor，ANN)算法.该算法的核心是找到一种局部敏感的哈希函数，使外观空间中相邻的高维矢量通过哈希函数后更有可能产生相同的值.不同的局部敏感哈希函数用于不同的距离度量，例如范数距离、余弦距离、汉明距离等.由于全局特征是高维二值向量，因此本文采用基于汉明距离的局部敏感哈希函数，该函数定义如下：

给定函数簇：

H={h|hi(v)}

(9)

其中hi(v)表示取出二进制向量v第i位上的值.从H中随机的取k个h函数，将k个h函数组合形成最终的局部敏感哈希函数g：

g={h1，h2，…，hk}

(10)

函数g产生的哈希值也称为哈希桶，k的大小即为哈希值的维数，每个g函数都能生成2k个哈希桶，每个哈希桶中包含具有相同子位的全局特征，所有哈希桶组成一个哈希表.

与基于暴力查找的全局搜索不同，当查询Q的最近邻时，基于LSH全局搜索首先查找Q对应的哈希桶，并逐一检查该哈希桶中的其他已经存在的全局特征与Q之间的汉明距离.如果距离低于设定的阈值t则将该全局特征对应的帧作为结果输出.其中，两个全局特征D1和D2之间的汉明距离如下：

‖D1-D2‖H=bitsum(D1⊕D2)

(11)

式(11)中⊕为二进制的异或操作，bitsum为统计向量中的非0位的个数.

4.2 多表多探针增强的LSH搜索

由于全局特征和哈希函数的生成具有一定的随机性，降低了LSH算法找到当前全局特征最近邻的概率.提高最近邻检索精度除了减小哈希值维数增加每个桶的容量外，还可以通过多表和多探针技术[17]增强LSH搜索.

多表技术是将一个全局特征经过l个不同的g函数处理，将产生的l个哈希值分别存入l个哈希表中.查询时，将查询特征所属不同表中的l个桶内的全局特征组成一个集合.只需在集合中查找查询全局特征的最近邻，无需搜索整个数据库.多表技术以牺牲一定内存和查询时间为代价，提高全局特征搜索精度.

针对多表技术内存占用大和查询时间长等缺点，我们将存储桶中存放的全局特征替换全局特征对应输入图像的序号，该序号也是全局特征在数据库的位置索引.查询时，通过存储桶中索引查找数据库中对应位置的全局特征，将符合阈值条件的全局特征所属的索引值输出.这种索引机制降低哈希表的内存占用并提高了数据库的查询速度.因此，即使创建多个哈希表，系统的搜索时间和占用内存空间都没有大幅增加.

多探针技术则通过检查全局特征所在的桶和相邻的桶，以提高搜索最近邻的概率.多探针层级(Multi Probe Level，MPL)为0时表示只检查全局特征所在的桶，MPL为1表示也检查哈希值存在1位差异的相邻桶，以此类推.多探针技术能够在不增加哈希表个数的前提下搜索更多的图像信息.在本文实验中MPL都设置为1.

本节引入LSH算法一方面能够与3.1节产生二进制全局特征高度结合，避免外观空间转换造成的信息丢失，提高了检索精度和速度.另一个方面与传统暴力搜索相比，该方法能够最大限度的保证搜索精度，减少内存占用的同时提高检索速度.

5 局部特征检验

虽然多表和多探针技术能够在一定程度上提高LSH搜索最近邻的精度，但并不能确保检测结果是100%的正确的.如果将全局搜索结果直接作为闭环检测的输出，可能会导致错误的判断，对整个机器人SLAM系统产生不可估量的影响.为保证闭环检测结果的高可靠性，本文加入局部特征检验环节对全局搜索的结果进行检查.

局部特征检验环节主要通过使用局部特征匹配的方式对全局搜索结果进行检查.局部特征匹配与全局特征匹配不同，其包含了更多的细节信息，能够在图像视角、光照条件变化或存在局部遮挡时匹配到正确的对应图像，但大量图像进行局部特征匹配会占用系统有限的计算资源.为了平衡闭环检测的时间和准确性，将全局搜索输出作为检验模块的输入，这种联合全局特征和局部特征的层次式的匹配策略不仅提高检测效率还保证了结果的高可靠性.

5.1 局部特征匹配

在3.2节中用增强的FAST算法检测关键点后，为控制局部特征的数量并降低不稳定特征对系统的影响，利用关键点的Harris响应值进行非极大值抑制，筛选100个关键点并计算其LDB描述子，随后将全局描述子和100个局部描述子一起存放到数据库中对应的索引位置中.当全局搜索得到候选帧的索引后，通过索引查找数据库中相应的局部特征描述子并与当前帧的局部特征描述子进行暴力匹配.在匹配的过程中，当前帧中一个描述子的最近邻和次近邻满足式(12)时则认为是一个正确的匹配[3].

≤0.7

(12)

其中，fc表示当前帧中一个描述子，fA和fA1是候选帧中的描述子，fA是fc的最近邻，fA1是fc的次最近邻.较低的比值意味着最佳匹配比其最佳竞争者表现得更好，可能是正确的匹配.当特征在外观空间中聚集更紧密时，距离比值更大，特征相对于彼此不够独特，为了避免误匹配删除当前这对匹配.

两幅图像认为是正确回环则至少存在N个正确匹配对.局部特征匹配是对全局搜索结果的再检查，局部特征匹配应尽可能保证全局搜索结果的准确性.如果全局搜索的得到的候选帧与当前帧的匹配数都小于N，则清除所有候选帧.

5.2 局部特征存储

使用局部特征匹配时，局部特征会占用机器人的大量存储空间.与Wang方案中使用的SIFT[8]描述子相比，LDB描述子优势更为突出，因为二进制描述子不仅提取速度快、占用存储空间少而且易存易取.例如，存储一帧图像100个SIFT描述子至少需要12kB的存储空间，而一帧图像100个LDB描述子仅需要3kB的空间.存储10000张图像每张图像100个LDB描述子仅需30M的存储空间.

全局描述子与局部特征描述子一起存放到存储器中，通过数据库中的索引(图像序号)快速查找相应的局部特征描述子.通过索引将全局特征和局部特征关联，提升数据库的读取和存储效率，降低数据库的复杂性.这种整体式的存储方式使得机器人可加载存储器中先前运动轨迹中的图像特征，或者可以加载其他搭载该算法机器人产生的图像特征，实现大尺度场景和多轨迹的闭环检测，提高了机器人的闭环检测能力.

6 实验与结果分析

在本节中，首先介绍实验环境和算法中的关键参数.然后，设计多个实验，实验由简单到复杂，根据实验结果确定算法中的关键参数.最后将本文所提出的算法与Wang的算法、FAB-MAP、FILD等进行对比分析.

6.1 实验环境和关键参数说明

本文实验所用计算机硬件配置为：CPU为i5-1035G1处理器，主频1GHz，内存8G.FILD算法使用Nvidia GTX1070显卡进行计算，除此之外其余实验均使用CPU单核单线程计算.

实验测试使用City_Center和New_College数据集[1]，由牛津大学Mark Cummins等人采集.该数据集主要用于闭环检测模块的测试和评估.两个数据集分别包含2146张，2474张双目图像.图像为640×480大小的三通道彩色图，此外，数据集提供真实闭环信息.两个数据集中部分图像如图3上半部分所示，运动轨迹如图3下半部分所示，在实验中只使用左侧相机图像.

图3 City_Center和New_College数据集部分图像及机器人运动轨迹

Fig.3 Partial images of City_Center and New_College datasets and the trajectory of the robot

闭环检测常用的性能评价指标是准确率和召回率，其计算公式如下：

准确率召回率

(13)

其中TP表示检测结果中正确的闭环个数，FP表示检测结果中错误的闭环数目，FN表示未被检测出的真实闭环数目.TP+FP表示检测到的所有输出结果，TP+FN表示数据集中真实闭环的个数.一般用准确率--召回率曲线(简称P-R曲线)反映闭环检测算法的综合性能[18].通过改变算法中全局搜索的距离阈值t产生不同的准确率和召回率进而绘制P-R曲线.虽然大多数系统将准确率作为优化指标，但是一个好的闭环算法能够在保证准确率的同时拥有很高的召回率.

本文提出算法中的关键参数如表1所示.

表1 提出算法中的一些关键参数

Table 1 Key parameters in the proposed algorithm

6.2 全局特征维数设置

全局特征的表示和检索是整个系统的核心，而全局特征维数又是全局特征表示的关键.全局特征维数越高包含的信息越多，区分性越强，需要的存储空间越多.而全局特征维数越小信息越少，区分性变弱，需要的存储空间变小.通过全局特征加暴力搜索即可组成最简单的闭环检测系统.在New_College和City_Center数据集上对这种最简单的闭环检测系统进行测试.根据以上实验确定本文提出算法中全局特征的维数.全局特征分别选取256、512、1024维进行比较.如图4所示，1024维特征和512维特征拥有相同的性能，但512维特征需要的存储空间更少，所以后续实验使用LDB产生512维的全局特征.

图4 不同维数的全局特征对应的P-R曲线

Fig.4 P-R curves corresponding to global features of different dimensions

6.3 LSH参数选择和搜索性能分析

影响LSH搜索精度的两个主要因素是哈希值维数K和哈希表个数T.在最小闭环检测系统基础上，将暴力搜索替换为LSH搜索，选择多种哈希表数和哈希值维数组合进行测试.最终当哈希表个数为10，哈希值维数为11时，LSH搜索可以达到与暴力搜索接近的性能，如图5所示.

图5 暴力搜索和LSH搜索P-R曲线

Fig.5 Brute force search and LSH search P-R curve

在保证搜索精度的基础上，为验证LSH算法能够加快全局特征的搜索，在网络上随机选取10700图像组成图像检索数据集，并使用该数据集进行测试.图6为使用该数据集实验过程中全局特征搜索用时变化情况，其中LSH搜索使用10个哈希表，哈希值维数为11.LSH搜索时间不再随数据库的增加而快速增加.当数据库小于4000帧图像时暴力搜索更有效率，但数据库超过4000帧后LSH搜索效率将超过暴力搜索.图6中LSH搜索P-R曲线未起始于0点，是由于从全局特征提取相应的哈希值和建立哈希表并进行存储需花费一定时间.

图6 LSH搜索与暴力搜索时间对比

Fig.6 LSH search and brute force search time comparison

6.4 局部特征匹配对数选择

全局搜索的输出是局部特征检验模块的输入.为了控制局部特征匹配时间，全局搜索输出最相似的前4帧图像索引，作为局部特征匹配的输入.因为没有全局特征距离阈值检查，即使该帧不存在闭环也会出现相应的候选帧，这是局部特征检验模块能够遇到的最困难的情况.这种包含大量错误的全局搜索结果，要求局部特征检验模块能够找出所有错误候选帧.为了寻找最优的匹配对数N，将匹配对数N从1开始计算相应的召回率和准确率.选择准确率为100%时召回率最高的点作为其匹配对数.在New_College和City_Center数据集分别进行测试，在两个数据集上最优选择匹配对数分别是8 和11.匹配对数应至少是8个，8个匹配对也是能通过RANSAC[19]迭代估计的基本矩阵恢复出相对位姿的最少的匹配对数.

6.5 与其他算法的比较

根据上述实验得到本文所提出算法关键参数，LDB生成512维的全局特征，LSH搜索使用10个哈希表、哈希值维数为11进行搜索，全局搜索输出满足阈值t的最相似的前4帧图像索引输入到局部特征检验环节，局部特征匹配对数N由6.4节选定.因为OACH未公开源码，采用文献[8]中的给出相关配置实现其算法.FILD和FAB-MAP算法采用其开源代码中的默认参数进行试验.

图7给出了本文算法和Wang提出方案在New_College和City_Center数据集的P-R曲线.因为加入严格的局部特征检验模块，该模块会删除全局搜索结果中的绝大多数误检测，使输出结果的准确率达到100%.当全局搜索输出满足阈值且最相似的前4帧数据时，由于全局特征区分性有限，使得真正的闭环图像不在输出前4个结果中，因而召回率达到一定程度后就不会再继续增加，所以采用局部特征验证后P-R曲线呈现一条近似的直线段.由图7可知本文算法性能与Wang等人提出的方案接近.

图7 两种算法的P-R曲线比较

Fig.7 Comparison of P-R curves of two algorithms

相比于P-R曲线，闭环检测更关注于准确率100%时召回率的大小.如表2所示，我们将本文算法与Wang等人提出的算法，FAB-MAP、FILD算法进行比较.FAB-MAP算法在New_College数据集中得到47%的召回率是通过非常复杂的方法得到的，完成一次检测至少需要3s.而最新的基于深度学习的FILD算法在City_Center数据集中达到了相对较高的召回率，这是由于大多数传统的图像特征无法更好的应对CityCenter数据集中剧烈视角和光照变化.

表2 4种算法准确率为100%时对应的召回率

Table 2 When the accuracy rate of the four algorithms is 100%，the recall rates are given

时间方面，如表3所示，使用New_College数据集的1074张图像统计了3种基于组合特征的闭环检测算法各个环节的平均用时.Wang的算法中多尺度Harris[20]关键点与OACH全局特征是一起计算的，局部特征只需计算关键点对应的SIFT描述子即可，因而局部特征提取时间较短.由于FILD算法的CNN全局特征和局部特征(SURF)无法在CPU上实现实时特征提取，因此必需使用GPU进行加速，即使如此整个算法完成一次闭环检测仍然需要50ms.由表3可知，在保证一定召回率的基础上，本文提出的算法是速度最快的.此外，本文使用了增强的LSH搜索，使全局搜索用时恒定，不会随数据库容量的增加而增加.当数据库中存储10000张图像信息时，Wang的方案中完成一次全局特征搜索时间长达30ms，而本文所提出的算法最多只需1ms.

表3 3种算法各环节平均用时(ms)

Table 3 Average time of each part for three algorithms(ms)

基于上述实验结果可，本文提出的算法与Wang等人提出的方案相近，速度上优于大多数闭环检测算法，另外，我们的算法实现简单，更容易在计算资源有限的设备中部署.

7 结 语

本文提出一种基于全局-局部联合二进制特征的快速闭环检测算法，该算法旨在保证闭环检测准确率的前提下进一步提高检测的速度.该方案使用联合的二进制特征加速场景匹配，实现简单且占用计算资源少.该算法分为3大部分，首先，使用局部差异二值算子生成全局特征和局部特征.然后，通过局部敏感哈希加速全局特征搜索.最后，利用局部特征对全局搜索的结果进行匹配检查确定真正的闭环帧.实验表明，在单核单线程无GPU加速的情况下，本文提出的算法能够保证闭环检测的高准确性和高实时性.接下来的工作是进一步优化图像特征的存储结构，并增强算法对视角和光照变化的鲁棒性.