基于组合图像特征与分层节点搜索的回环检测方法

李卓，魏国亮，管启，黄苏军，赵珊

图文信息技术

基于组合图像特征与分层节点搜索的回环检测方法

李卓a，魏国亮b，管启a，黄苏军a，赵珊a

（上海理工大学 a.光电信息与计算机工程学院 b.理学院，上海 200093）

文中通过提出一种新的回环解决方案，平衡回环检测系统的高准确率与高运行效率。提出一种利用组合图像特征与分层节点搜索的新方法。首先，计算一种原始图像的下采样二值化全局特征和经过改进的ORB（oriented FAST and rotated BRIEF）局部特征，将其存入图像特征数据库。其次，引入一种分层节点搜索算法，在数据库中搜索与当前图像特征最相似的全局特征作为回环候选。最后，利用改进的ORB特征进行局部特征匹配，验证候选图像，确定回环检测结果。使用该算法在3个不同的数据集上进行验证，测试中每次回环检测的平均处理时间仅需19 ms。实验结果表明，该算法在运行效率、准确率、召回率等方面均达到了领域内的先进水平。

回环检测；全局特征；局部特征；分层节点

通过机器实现自动包装与运输已成为现代工厂中降低制造成本的重要方法，vSLAM正是实现这一目标的关键技术之一[1]。vSLAM利用相机使机器进行定位与建图，从而实现工厂的自动化包装、运输等环节。系统长时间运行会产生累计误差，导致所建地图的精度降低。回环检测是vSLAM系统中的一个重要环节，它可以确定机器是否返回到先前经过的位置，这种信息对于减小累计误差，创建正确的地图和提高地图的精度具有重要意义。

通常，vSLAM中回环检测问题可转化为基于内容的图像检索问题，即在历史图像中找到与指定图像最相似的一帧。传统图像检索方法大致可分为4类；基于全局图像特征、基于局部图像特征、基于视觉词袋方法、基于组合图像特征[2]。全局特征如Bradley等[3]使用的加权梯度方向直方图，Singh等[4]设计的Gist特征等，其计算、匹配速度较快，但准确率较低。Lowe等[5]提出尺度不变特征变换（Scale-invariant feature transform, SIFT）局部特征，其稳定性和准确率有较大提高，但特征提取、匹配太过耗时，无法应用于实时回环检测系统。Galvez等[6]将局部二值特征BRIEF与词袋方法组合使用，词袋模型（Distributed bag of words, DBoW2）使得实时运行的回环检测系统成为可能。近年来流行的几种SLAM算法如ORBSLAM3等[7]都是采用此方法进行回环检测，但是，词袋模型带来的准确率降低等问题依旧困扰着研究者们。

随着深度学习的快速发展，出现了许多利用深度学习代替传统方法的回环方案[8]，如Shan An等[9]提出FILD(Fast and incremental loop closure detection)，Yue H等[10]提出的BoSP(Bag of SuperPoints)以及Arandjelovic等[11]提出的基于NetVLAD的方法。此类方法虽然达到了较高的准确率，但过于复杂的特征计算需要强大的计算力，短期内无法在小型平台如无人机上实时运行。与此同时，基于组合特征的方法也有了进展，Carrasco等[12]提出的Haloc算法利用全局标签和SIFT特征完成回环检测，较大地提升了系统准确率。

尽管有如此多种方法解决回环检测问题，但大多数都不能既满足vSLAM系统实时性的要求，又满足其高准确率和召回率的要求。针对此问题，文中提出一种回环检测方法，使用计算速率大大加快的二值图像特征以及高效的图像检索算法，使系统能够在保证高准确率和高召回率的前提下实时运行。

1 算法概述

算法主要框架见图1。与基于组合特征的回环检测系统结构类似，整个过程可以分为3个阶段：计算图像特征、全局搜索候选图像以及候选验证。

第1阶段，计算图像的全局二值特征与局部二值特征，选取二值特征的原因是提高系统运行效率，保证实时运行。第2阶段，使用分层节点搜索算法在历史帧中找到当前图像的回环候选帧，应用此搜索算法使得系统能在大规模地图中实时运行。第3阶段，利用局部特征匹配来验证回环候选帧，当匹配数超过预先设定的阈值时，通过RANSAC[13]进行几何验证，最终确定回环帧。

2 图像特征提取

2.1 全局图像特征

为加快图像检索速率，文中使用一种简单的全局图像描述方法[14]，具体过程见图2。首先利用高斯滤波器对图像进行平滑处理，接着对图像进行降采样缩小尺寸，然后使用大津法进行二值化处理，产生几百位的二进制码。这种全局二值特征计算速率极快，准确率也非常高，当采用汉明距离作为图像间相似度时，1 s内可与千万张图像进行计算。

2.2 改进ORB特征

ORB特征[15]具有计算速度快、旋转不变性等优点，但与浮点型特征如SIFT、SURF等相比其稳定性和可区分性都有所不及。文中希望引入一种既拥有二值特征计算速度快等优点，又拥有浮点型特征稳定性好、可区分性好等优点的局部特征。Schlegel等[16]的工作带来了一些启发，将图像信息的其他线索以二进制码的形式添加至描述符，使其可以记录更多图像信息，可区分性将变得更好。

图1 回环检测算法系统框架

图2 全局图像特征提取

基于上述分析，文中提出了一种ORB特征的改进型特征，描述尺度信息的ORB特征（Scale-ORB，SORB），在一定程度上改进了ORB特征稳定性与可区分性差的缺点。将特征点的尺度信息编码成八位二进制字符串，添加到ORB特征描述符之后，以便在计算距离时直接使用这些信息。首先将特征点的尺度信息转化为八位二进制码()，为特征点尺度信息（0—7），并附加到原始ORB描述符之后，从而得到一个新的描述符,。()根据式（1）得到。

(1)

(2)

不同尺度的特征点对应的二进制字符串见图3。新生成描述符与ORB特征的描述符都为位向量，可通过计算2个向量之间不同位的数量来测量其汉明距离。计算机通过异或运算实现此操作，这正是计算机最擅长且速度最快的计算方式之一。

图3 特征点尺度对应的二进制字符串

3 分层节点搜索算法

视觉回环检测系统的另一个核心问题是数据检索算法。暴力搜索和k-d树是解决数据检索问题的2个经典方法，但都有各自的缺点。暴力搜索只适用于小规模数据，一旦规模过大，检索过程将十分耗时，系统不能实时运行。k-d树搜索算法在使用SIFT等浮点特征构造搜索结构时表现良好，使用二进制码时性能会遭受较大的损失。近年来Schlegel等[17]提出的HBST搜索方法在数据规模过大时也容易失去作用，因此文中提出一种适用于大规模数据且高效的检索算法，即分层节点搜索算法。

算法的分层结构见图4。检索过程具体为：在系统运行过程中将历史图像在线聚类为若干图像袋，每个图像袋内包含若干相似的图像，称为二级节点，其中最早出现的图像称为一级节点；整个检索过程分为2层，第1层检索是在一级节点图像中找到与当前图像相似度最高的若干图像，第2层检索是从上述一级节点图像袋内找到与当前图像相似度最高的若干图像，并将其作为回环候选。在实验中这种检索方法不仅表现出与暴力搜索相当的准确率，且效率更高。

分层节点结构的更新过程见图5。记当前图像与其前一帧图像的汉明距离为，依次计算当前图像与一级节点图像的汉明距离，判断最小距离是否小于设定的参数。若小于，表明当前图像与此一级节点图像十分相似，可将当前图像添加至此一级节点的图像袋，进一步判别是否发生了回环。若大于，则利用当前图像创建新图像袋，并将其置于新图像袋内。这表明当前图像与历史图像有较大差别，大概率是机器访问了新的位置。

为提高回环检测系统的召回率，文中还设计了一种动态阈值算法。回环问题中机器得到的图像在时间与空间上都是连续的。一段极小的时间内，若机器形成回环，在后续几个时刻内必将连续形成回环，这是由时间、空间连续带来的必然现象。动态阈值算法具体表现为：当系统连续形成次回环时扩大上述阈值，使得=(≥1)。后续几个时刻大概率会继续形成回环，扩大阈值有助于减少全局特征描述图像带来的误差，从而在一定程度上提高系统的召回率。由于在全局搜索后还将进行回环验证，因此不必担心添加了错误的回环候选图像而导致系统准确率下降。

4 验证候选图像

利用分层节点搜索算法找出当前图像的回环候选图像后需要进行候选验证，从而确定唯一的回环帧或是确定不产生回环。这个过程需要利用图像的局部特征进行匹配。在匹配过程中，当前图像某一描述符的最近邻与次近邻满足式（3）时认为产生了一个正确的匹配。

图4 分层节点架构

图5 分层节点搜索算法的更新与检索

(3)

5 实验与评估

通过实验测定SORB特征与分层节点搜索算法的有效性，并将文中算法与3种传统方案和3种深度学习方案进行对比，以验证其先进性。实验在3个数据集上进行，其中2个是由牛津大学的Mark Cummins等[18]采集的City Center和New College数据集，分别包含1237对图像和1073对图像。第3个数据集为Malaga07[19]，一段在室外的微动态公路上采集的数据，包含2121对图像，此数据集的真实回环信息由手工标定得到。文中选取了这些数据集的单侧图像进行实验，3个数据集中具有代表性的图像见图6。实验均在同一台计算机上进行，其主要硬件配置包括：CPU为Intel Xeon(R)Gold 5120处理器，主频2.2 GHz，内存32 G。

5.1 算法有效性分析

5.1.1 全局特征维度

图像特征的维度是特征描述图像的关键。维度越大，承载的图像信息越多，越能更好区分不同图像。随着特征维度增大，计算量也会增加，系统运行效率将变低，不能达到实时运行的目的。需要在内存占用与系统性能二者之间做出取舍，达到最优效果。如图7所示，分别选取全局特征维度为300维、480维、960维进行比较。3个数据集上的结果显示，全局特征维度增加至480维时系统达到最佳性能，虽然960维时系统性能也接近最佳，但此时计算量与内存都将大大增加，因此在后续实验中选择480维作为全局特征维度。

图6 数据集中的部分图像

Fig.6 Some images in dataset

图7 不同维度的全局特征对应的召回率-准确率曲线

5.1.2 SORB特征的有效性

将形成回环的2幅图像进行局部特征匹配时，正确的匹配对中有接近90%的特征点是尺度相同的，所有正确匹配对的尺度差都在一个尺度单位以内。若将特征的尺度信息添加至描述符中，匹配错误的特征之间距离将变大，正确的匹配不会发生改变。由式（3）可知，最近邻与次近邻距离之比将变小，从而提高特征匹配的准确率。

为验证SORB特征有效性，分别应用该特征与传统ORB特征在3个数据集上进行测试，实验结果见图8。由图8可知，在City Center数据集上，当准确率为100%时，应用2种特征的系统最大召回率基本一致。在New College数据集上，当准确率为100%时，SORB特征比传统ORB特征最大召回率高出2%左右。在Malaga07数据集上，当准确率为100%时，SORB特征比传统ORB特征最大召回率高出6%左右。在计算耗时方面，提取一张图像的SORB特征只比传统的ORB特征多出0.2 ms左右，这对整个系统来讲几乎没有影响。综上得出，在图像匹配方面，SORB特征的各项性能是优于传统ORB特征的。后期还可将此方法应用在最新的局部图像特征如BEBLID[20]中去，验证文中提出方法的通用性。

5.1.3 分层节点搜索算法性能分析

为验证分层节点搜索算法的有效性，将其与暴力搜索算法进行了对比实验。首先确定影响算法性能的几个参数的取值，一是选择距离最近的前个一级节点进行下一步搜索，二是在上述几个一级节点的图像袋中选择距离最近的前个二级节点作为候选图像。在3个数据集上进行的实验得到，当为4，为16时，分层节点搜索算法达到最优性能。

搜索算法最重要的性能指标之一是其满足高准确率时的搜索效率，暴力搜索是目前搜索算法中准确率最高的算法之一，由于其搜索效率低下才不被广泛应用。分层节点搜索算法与暴力搜索算法应用于不同规模地图时的搜索效率见图9。图9中暴力搜索算法耗时随地图规模的增加明显快于分层节点搜索算法，当地图规模小于16 000帧时，暴力搜索方法的效率更高，这是由于构造分层节点结构需要消耗一定时间，当地图规模大于16 000帧图像后，分层节点搜索算法的效率将变得更高，并且此后耗时增长十分缓慢，因此，当在大规模地图中应用时，分层节点搜索算法更有优势。

图8 SORB特征与ORB特征对应的召回率-准确率曲线

图9 暴力搜索与分层节点搜索算法的效率对比

5.1.4 动态阈值算法的有效性

参数确定是动态阈值算法的关键。通过实验测定代表连续回环次数的和代表倍数的的具体取值。将选为1～3，不超过3是因为太长的回环确认时间将导致召回率下降，使动态阈值算法变得没有意义。的选值则在1～2，太大的将导致全局搜索的准确率降低。通过改变参数、算法在New College数据集下的准确率-召回率曲线，见图10。随着从1增加到2，当准确率为100%时，系统的最大召回率在逐渐增加，当超过2时系统的最大召回率开始降低。也是如此，随着的增长系统的最大召回率逐渐增加，当为1.5时达到最大值。当为2，为1.5时，系统在数据集中显示出了最优的准确率与召回率，相较于不使用动态阈值法（即为1，为1）的系统，最大召回率提高了近10%。

图10 不同阈值对应的召回率-准确率曲线

5.2 几种回环算法对比

选取全局特征维度为480维，连续回环次数为2，倍数为1.5进行试验，此数据下文中算法表现出最佳性能。文中算法与Haloc、DBoW2、FAB-MAP2[21]以及深度学习方法NetVLAD、BoSP、FILD进行了对比实验，结果见表1。基于深度学习的方案FILD在New College和Malaga07数据集下表现出最佳性能，方案BoSP在City Center数据集下表现出最佳性能，且大幅领先其他方案。4种传统方法中，New College数据集下，文中算法与DBoW2性能相近，二者均优于Haloc和FAB-MAP2。另外2个数据集下，文中算法明显优于其他传统方案，且性能比早期深度学习方案NetVLAD更好，仅在最大召回率方面不足近2年提出的基于深度学习的BoSP与FILD。

通过New College数据集测试了各算法进行回环检测的平均用时，见表2。几种基于深度学习的方案在利用GPU(GeForce GTX 1080)加速的情况下一次回环检测仍需要40～400 ms，而文中算法不使用GPU加速也仅需19 ms。综合表1、2可以看出，基于深度

学习的方案虽然在最大召回率方面有着明显优势，但巨大的时间消耗使得它不能部署在小型机器上实时运行，这也体现了一般算法的运行效率与准确率是不宜兼顾的。文中算法平衡了召回率、准确率、运行效率等多个方面，且性能均优于目前流行的传统方法如DBoW2、Haloc、FAB-MAP2，这是因为文中算法全部采取二值图像特征，相比浮点数特征大大缩短了特征提取与匹配的时间消耗。使用二值特征将导致图像信息缺失，从而降低了算法精度，但文中采用SORB特征增加了描述符所携带的图像信息，提升了特征匹配的准确率，在一定程度上弥补了损失的精度。另外，文中提出的分层节点搜索方法通过图像聚类减少了检索数量，进一步提高了运行效率。动态阈值算法则在不增加计算复杂度、不降低准确率的前提下提升了算法的召回率。从实验结果来看，正是上述几点工作发挥了作用，才能同时提升算法的运行效率与准确率，满足目前vSLAM系统对回环检测算法性能的要求，因此，可以认为文中提出的算法在综合性能上优于其他几种对比方法。

表1 准确率为100%时算法的最大召回率

Tab.1 Maximum recall of algorithm at precision of 100% %

注：黑体表明几种算法中的最优数据

表2 几种算法的时间消耗

Tab.2 Time consumption of several algorithms ms

注：黑体表明几种算法中的最优数据；NetVLAD(G)中G表示此方法使用GPU处理

6 结语

文中提出了一种实时视觉回环检测新方法，并在3个数据集上验证了方法的有效性。文章的主要贡献：提出了一种SORB特征，与传统ORB特征相比，局部特征匹配更加准确，在保持回环系统运行速率不变的同时其准确率、召回率也有所提升；构造了一种在线建立的分层节点搜索算法，减少了系统中图片检索产生的时间消耗，使得系统在大规模地图中的应用成为可能；提出了一种动态阈值算法，显著提高了系统的召回率。

后续将在更多数据集中进一步评估文中提出的方案，并尝试将局部特征改进方法应用到其他二值特征算法中，以验证此方法的通用性。最后准备将算法整合到一个完整的vSLAM系统中，应用在自动化工厂包装、运输环节的机器上。

[1] 李俊. 基于SLAM导航的多目视觉AGV系统设计[J]. 包装工程, 2018, 39(19): 181-189.

LI Jun. Design of Multi Vision AGV System Based on SLAM Navigation[J]. Packaging Engineering, 2018, 39(19): 181-189.

[2] 刘强, 段富海, 桑勇, 等. 复杂环境下视觉SLAM闭环检测方法综述[J]. 机器人, 2019, 41(1): 112-123.

LIU Qiang, DUAN Fu-hai, SANG Yong, et al. A Survey of Loop-Closure Detection Method of Visual SLAM in Complex Environments[J]. Robot, 2019, 41(1): 112-123.

[3] BRADLEY D M, PATEL R, VANDAPEL N, et al. Real-Time Image-Based Topological Localization in Large Outdoor Environments[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Edmonton, 2005: 3670-3677.

[4] SINGH G, KOSECKA J. Visual Loop Closing Using Gist Descriptors in Manhattan World[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA), 2010: 4042-4047.

[5] LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

[6] GALVEZ L 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.

[7] CAMPOS C, ELVIRA R, RODRIGUEZ J J R, et al. ORB-SLAM3: An Accurate Open-Source Library for Visual, Visual-Inertial, and Multimap SLAM[J]. IEEE Transactions on Robotics, 2021, 23: 1-17.

[8] 李少朋, 张涛. 深度学习在视觉SLAM中应用综述[J]. 空间控制技术与应用, 2019, 45(2): 1-10.

LI Shao-peng, ZHANG Tao. A Survey of Deep Learning Application in Visual SLAM[J]. Aerospace Control and Application, 2019, 45(2): 1-10.

[9] AN Shan, CHE Guang-fu, ZHOU Fang-ru, et al. Fast and Incremental Loop Closure Detection Using Proximity Graphs[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Macau, 2019: 378-385.

[10] YUE Hao-song, MIAO Jin-yu, YU Yue, et al. Robust Loop Closure Detection Based on Bag of SuperPoints and Graph Verification[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Macau, 2019: 3787-3793.

[11] ARANDJELOVIC R, GRONAT P, TORII A, et al. NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, 2016: 5297-5307.

[12] NEGRE CARRASCO P L, BONIN-FONT F, OLIVER-CODINA G. Global Image Signature for Visual Loop-Closure Detection[J]. Autonomous Robots, 2016, 40(8): 1403-1417.

[13] FISCHLER M A, BOLLES R C. A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[14] WU Jun-jun, ZHANG Hong, GUAN Yi-sheng. An Efficient Visual Loop Closure Detection Method in a Map of 20 Million Key Locations[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, 2014: 861-866.

[15] RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: An Efficient Alternative to SIFT or SURF[C]// Proceedings of IEEE International Conference on Computer Vision, Los Alamitos, 2011: 2564-2571.

[16] SCHLEGEL D, GRISETTI G. Adding Cues to Binary Feature Descriptors for Visual Place Recognition[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA). Montreal, 2019: 5488-5494.

[17] SCHLEGEL D, GRISETTI G. HBST: A Hamming Distance Embedding Binary Search Tree for Visual Place Recognition[J]. IEEE Robotics and Automation, 2018, 3(4): 3741-3748.

[18] 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.

[19] BLANCO C J L, MORENO D F A, GONZALEZ J J. The Málaga Urban Dataset: High-Rate Stereo and LiDAR in a Realistic Urban Scenario[J]. The International Journal of Robotics Research, 2014, 33(2): 207-214.

[20] SUAREZ I, SFEIR G, BUENAPOSADA J M, et al. BEBLID: Boosted Efficient Binary Local Image Descriptor[J]. Pattern Recogn, 2020, 133: 366-372.

[21] CUMMINS M, NEWMAN P. Appearance-Only SLAM at Large Scale with FAB-MAP 2.0[J]. The International Journal of Robotics Research, 2011, 30(9): 1100-1123.

Loop Detection Method Based on Combined Image Features and Hierarchical Node Search

LI Zhuoa, WEI Guo-liangb, GUAN Qia, HUANG Su-juna, ZHAO Shana

(a.School of Optical Electrical and Computer Engineering b.College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China)

The work aims to propose a loop solution to balance the high precision and high efficiency of loop detection system. A new method based on combined image features and hierarchical nodes search algorithm was proposed. Firstly, a down-sampled binary global feature of the original image and improved ORB local feature were calculated and stored in the image feature database. Secondly, a hierarchical node search algorithm was introduced to search the database for the global feature most similar to the current image feature as a loopback candidate. Finally, the improved ORB features were applied to local feature matching to verify the candidate images and confirm the results of loop detection. The algorithm was validated on three different data sets, and the average time of each loop detection in the test was only 19 ms. The experimental results indicate that the algorithm has reached the advanced level in terms of operation efficiency, precision and recall.

loop detection; global feature; local feature; hierarchical node

TP242

A

1001-3563(2022)05-0257-08

10.19554/j.cnki.1001-3563.2022.05.035

2021-06-16

国家自然科学基金（61873169）；上海市“科技创新行动计划”国内科技合作项目（20015801100）

李卓（1996—），男，上海理工大学硕士生，主攻视觉SLAM。

魏国亮（1973—），男，博士，上海理工大学教授，主要研究方向为非线性系统、多智能体协同控制。