基于层次化可导航小世界网络改进的SeqSLAM算法

张梦真 王庆芝 刘其朋

摘要：SeqSLAM是移动机器人领域广泛使用的一种视觉定位算法，它对光照等因素较鲁棒，但受视角变化影响较大。另外，SeqSLAM采用了蛮力搜索匹配的方式，在较大规模数据集中无法满足实时性要求。针对以上问题，对SeqSLAM算法做了两方面的改进：首先将图像表示为局部聚合描述子向量，提取图像特征；然后采用层次化可导航小世界网络算法搜索相似图像序列，具有更高的搜索效率。测试表明，改进的SeqSLAM算法可以获得更高的精确率和召回率，搜索时间显著降低。

关键词：SeqSLAM；回环检测；局部聚合描述子向量；层次化可导航小世界网络

中图分类号： TP183文献标识码： A

收稿日期：2021-10-13；修回日期：2021-12-22

基金项目：国家自然科学基金青年科学基金（61903212）

第一作者：张梦真（1995-），女，山东青岛人，硕士研究生，主要研究方向为视觉SLAM。

通信作者：刘其朋（1985-），男，山东菏泽人，博士，副教授，主要研究方向为自动驾驶与智能交通。

Improved SeqSLAM Using Hierarchical Navigable Small World Graphs

ZHANG Mengzhen， WANG Qingzhi， LIU Qipeng

（Institute of Complexity Science， Qingdao University， Qingdao 266071， China）

Abstract：SeqSLAM is a widely used loop closure detection algorithm in mobile robot and autonomous vehicle field. It could recognize revisited places by comparing sequences of images even under dramatic changes of season， illumination， and weather. However， SeqSLAM is vulnerable to viewpoint changes. In addition， SeqSLAM compares sequences of images by brute force method， which prevents its real-time application to large-scale image datasets. To address these problems， we first represent each image by a kind of low dimensional description — vector of locally aggregated descriptors （VLAD） which is robust to viewpoint changes， and then replace the brute force method by an approximate nearest neighbor search algorithm — hierarchical navigable small world graphs （HNSW）. Tests on publicly available datasets show that， the improved SeqSLAM with VLAD and HNSW could obtain much better detection results in the respect of precision-recall evaluation and the search time is reduced by orders of magnitude. We make code publicly available at https：//github.com/qipengliuNTU/Efficient-SeqSLAM-with-HNSW. Key words： SeqSLAM; loop closure detection; VLAD; hierarchical navigable small world

0 引言

同步定位與建图（Simultaneous Location And Mapping， SLAM）是自主移动机器人领域的研究热点^[1-2]。在机器人建图过程中，如果可以准确判断行驶路径中的回环（即回到了曾经到过的地点），则可以通过全局优化减少偏移量，显著提高建图的精度^[3-4]。基于视觉信息的回环检测容易受到视角、光照、季节、天气等因素的影响，可能出现误判。为了提高检测准确性，SeqSLAM算法在检测时考虑了时序信息，通过对比两个图像序列（而不是孤立的两幅图像）来判断机器人是否到达了之前的地点^[5]。研究表明，SeqSLAM算法可以很好地的应对光照、季节等变换的影响，提高了回环检测算法的实用性。

在标准的SeqSLAM算法中，一幅图像的特征直接由其本身的像素值表示。如果两幅图像对应位置像素之差的绝对值之和较小，则认为这两幅图像是相似的。这种判断图像相似性的方式比较简单直观，但是在公开数据集上的测试表明，SeqSLAM对视角变化的鲁棒性较差。为了解决这一问题，SeqSLAM的原作者采用深度学习技术，基于一幅图像构造出虚拟的左右平移的多幅图像，从而扩大了图像搜索对比的空间，在一定程度上提高了水平视角变换的鲁棒性，但对于其他类型的视角变换效果依然较差^[6]。为了进一步改进SeqSLAM中的图像表征问题，Tsintotas等^[7]将词袋模型（Bag of Words， BoW）引入SeqSLAM中，图像用词袋向量表征，可以较好地应对视角变换的问题。词袋模型是一种比较经典的图像特征表示模型，它从图像中提取出若干具有代表性的视觉单词，用一个低维特征向量来表示一幅图像^[7]。已有研究表明，词袋模型对图像的表征比较粗粒化，其本质是统计一幅图像中视觉单词出现的次数，无法进一步细分原始图像局部特征点相对于视觉单词的偏移程度。因此，本文采用更加精细化、图像表征效果更好的局部聚合描述子向量（Vector of Locally Aggregated Descriptors， VLAD）来描述图像，以期获得更优的检测效果^[8]。

除了改进SeqSLAM算法中的图像表征方式，研究者们还尝试提高SeqSLAM的搜索效率。标准的SeqSLAM采用蛮力搜索的方式对比图像序列，为了检测n时刻图像是否与某一历史图像构成回环，需要搜索从初始时刻到n-1时刻所有的图像序列。对于整个行驶路线来说，计算复杂度为O（n²），在大规模数据集上无法满足实时性要求。文献[9]用网络流方法替换了SeqSLAM中的蛮力搜索算法，但整体计算复杂度仍为O（n²）。文献[10]采用隐马尔可夫链查找最佳匹配图像序列，其中需要計算相似性矩阵，计算复杂度并没有降低。Siam等^[11]提出了Fast-SeqSLAM算法，针对机器人在同一路线上行驶两次的情形，第1次行驶时，将图像描述保存为树结构；第2次行驶时，采用最近邻搜索的方式寻找与当前图像序列相似度最高的图像序列。Fast-SeqSLAM算法的计算复杂度可以达到O（nlogn）级别，但它的问题在于需要预先存储图像数据，因此无法用于在线回环检测。为了应对这一问题，本文在VLAD图像表征的基础上，将层次化可导航小世界网络（Hierarchical Navigable Small World， HNSW）应用于相似图像序列的搜索过程中^[12]。与Fast-SeqSLAM不同，本文的改进算法可以在机器人行驶过程中实时构造层次化可导航小世界网络，并实现了在线回环检测的功能。

本文主要贡献和创新点包括两部分：1）在改进SeqSLAM图像表征方面，采用了局部聚合描述子向量方式，可以更好地应对图像视角变换等问题；2）在提高SeqSLAM搜索效率方面，采用了近似最近邻搜索算法——层次化可导航小世界网络，可以在几乎不损失搜索精度的情况下显著降低搜索时间。

1 基于VLAD和HNSW改进的SeqSLAM算法

为方便理解，首先给出算法的整体框图，如图1所示，然后逐一介绍各部分的具体实现。

1.1 图像的VLAD描述

与经典的词袋模型类似，VLAD也需要离线构造视觉词典。一般在大规模图像数据集上采用SIFT，SURF，ORB等算法提取大量局部特征，然后经过K-Means聚类得到若干视觉单词。假设一个视觉词典C包含k个单词，记作C={c₁，c₂，…，c_k}，其中c_i为经过K-Means聚类算法得到的第i个簇CL_i的中心点。直观理解为视觉特征空间被划分为k个子空间，每个子空间由它的中心点（即视觉单词）表示，如图2所示，其中黑点代表从数据集中提取的局部视觉特征，五角星代表聚类中心点，所有属于同一个簇的局部视觉特征可以由相应的一个视觉单词表示。

在视觉词典的基础上，图像I可以用相应的VLAD表示，步骤为

1）从图像I中提取m个局部特征描述符{d^I₁，d^I₂，…，d^I_m}；

2）对于视觉词典中的每一个单词c_j，计算落入簇CL_i的所有特征描述符与c_j的偏差之和，即

3）将所有的v_j归一化，并编排成一个长度为k×d的向量，其中d为局部描述符的维度。

1.2 基于HNSW搜索相似图像序列

当图像被表示成VLAD向量之后，可以通过比较这些向量之间的差距来判断图像之间的相似性，进而判断是否出现了回环。为了提高判断的准确性，SeqSLAM并不是对比单幅图像的相似性，而是对比由多个连续图像组成的序列，当两个图像序列中相邻的多幅图像都相似时，才认为检测到了回环。标准SeqSLAM中采用了蛮力搜索的方式，检测时间较长。为了提高检测速度，本文采用了HNSW近似最近邻搜索的方式。

1.2.1 在线构造HNSW数据结构

HNSW可以随着机器人的移动而在线构造。为了将HNSW算法应用到图像序列中，首先需要将图像序列转换为HNSW网络中的节点，过程如图3所示，其中长度为p的图像序列（以VLAD形式呈现）转化为一个节点，因此节点包含数据的维度为p×k×d。

在定义了节点的基础上，接下来可以构造HNSW网络，其本身是一个多层网络，如图4所示。

下面介绍HNSW具体的构造步骤。当机器人移动时，假设在n时刻接收到一幅图像，则从n-p到n时刻图像序列对应的VLAD序列形成一个节点，其中p为序列长度。该节点所处的最高层数服从几何概率分布，即概率随层数的升高而指数减小。如果节点位于l层，则该节点同时位于0到l-1层。在每一层上，节点采用贪婪算法搜索最近的若干邻居节点，并与之相连。采用这种方式就可以构造出层次化的可导航小世界网络。已有研究表明，“小世界”现象背后的原因是网络中同时存在长程连接和短程连接，其中通过长程连接可以快速到达目标节点附近区域，通过短程连接可以局部精确搜索^[13-14]。不难发现，前述方法构造出的HNSW网络中，上层网络中的连接相当于长程连接，下层网络中的连接相当于短程连接。

1.2.2 基于HNSW的近似最近邻搜索

在机器人移动过程中，与HNSW构造过程同时进行的是最近邻节点（即相似图像序列）的搜索。搜索过程由顶层网络中一个随机选择的节点开始，然后依照网络邻居关系贪婪搜索到本层中的最近邻节点，然后转到下一层，从该节点继续贪婪搜索。该过程一直持续到最底层网络，最终找到全局近似最近邻节点。搜索过程如图5所示。

从图5中可以看到，该HNSW网络共有3层，空心圆节点表示问询节点，即当前图像序列对应的节点，搜索从顶层随机节点开始，标注为start，搜索它的邻居，找到与问询节点距离最近的节点，转入下一层继续搜索，最终在底层找到问询节点的近似最近邻节点，标注为end。问询节点与end节点对应的图像场景就是机器人行驶路径中可能存在的回环。

2 公开数据集验证

本节将通过实验分析改进算法的精确率-召回率（Precision-Recall， PR）指标以及搜索时间复杂度。以两个公开数据集作为测试平台——NewCollege和CityCentre。测试代码已分享到连接：https：//github.com/qipengliuNTU/Efficient-SeqSLAM-with-HNSW，实验中的关键参数如表1所示。

2.1 PR曲线指标

为了更好地理解PR曲线指标，简要介绍一些相关的概念。在回环检测中，如果两幅不同场景拍摄的图像被误认为是同一场景的图像，这种错误被称为假阳性（False Positive， FP）;同一场景的两幅图像被误认为是不同场景的图像，这种错误被称为假阴性（False Negative， FN）。相应地，正常检测到了回环就称为真阳性（True Positive， TP），正确检测到了非回环就是真阴性（True Negative， TN）。在此基础上，可以计算精确率P和召回率R为

其中，#Z表示Z样本的数量。

本文对比4种算法：1）标准的SeqSLAM；2）基于BoW改进的SeqSLAM；3）基于VLAD改进的SeqSLAM；4）基于VLAD和HNSW改进的SeqSLAM。

PR曲线如图6所示，其中图例表明了每条曲线对应的算法。从图6可以看出，与传统的SeqSLAM算法相比，基于VLAD改进的算法在召回率提高时，可以保持较高的精确率，而前者的精确率下降较快。基于BoW改进的算法一直保持较高的精确率，这意味着它检测到回环基本上是正确的，但是召回率无法进一步提升，表明它错过了一些真实的回环。基于HNSW改进的算法效果仅次于蛮力搜索算法。

2.2 搜索时间对比

移动机器人的某些应用场景，例如自动驾驶汽车，对回环检测的实时性要求较高。传统的SeqSLAM中采用蛮力搜索的方式，无法应对大规模数据集（即较长行驶路线）的检测。从图6的PR曲线可以看出，基于HNSW改进的算法具有与蛮力搜索算法类似的效果，但搜索时间显著降低，如图7所示。

在机器人的移动过程中，需要检测的图像数量不断增加。图7中seq+vlad在搜索相似图像时采用了蛮力搜索的方式，即当前图像序列要与所有历史图像序列逐一对比，时间复杂度为O（n），其中n为历史图像数量。随着历史图像的增加，每次接收到新图像之后需要对比的图像也相应增加，搜索时间会逐渐变长。实验中记录了从搜索开始到结束的用时，结果如图7所示，搜索时间随着历史图像规模的扩大而线性增长，符合理论预期。图7中seq+vlad+hnsw算法采用HNSW最近邻搜索方法。文献[12]指出，HNSW算法的复杂度为O（logn）。實验中记录了搜索开始到结束的用时，结果如图7所示，搜索时间随历史图像的增加呈对数增长，符合理论预期。

3 结论

本文从图像表征鲁棒性和图像匹配效率两方面对标准的SeqSLAM做了改进。在图像表征方面，采用了局部聚合描述子向量VLAD方式，可以在更精细的层面上刻画图像局部特征点以及整幅图像的特征，更好地应对图像视角变换的影响；在提高SeqSLAM搜索效率方面，采用了近似最近邻搜索算法——层次化可导航小世界网络HNSW，可以在几乎不损失搜索精度的情况下提高搜索效率。基于公开数据集NewCollege和CityCentre的测试表明，改进算法具有较高的检测准确率和召回率，并且搜索时间显著下降。

在未来工作中，可以尝试功能更强的图像表征方式，例如基于深度神经网络的NetVLAD^[15]。另外，可以尝试将改进的回环检测算法嵌入到完整的SLAM框架中，在实际项目中测试其性能。

参考文献：

[1]CADENA C， CARLONE L， CARRILLO H， et al. Past， present， and future of simultaneous localization and mapping： toward the robust-perception age[J]. IEEE Transactions on Robotics， 2016， 32（6）： 1309-1332.

[2]王霞，左一凡. 视觉SLAM研究进展[J]. 智能系统学报， 2020， 15（5）： 825-834.

WANG X， ZUO Y F. Advances in visual SLAM research[J]. CAAI Transactions on Intelligent Systems， 2020， 15（5）： 825-834.

[3]刘强， 段富海， 桑勇， 等. 复杂环境下视觉SLAM闭环检测方法综述[J]. 机器人， 2019， 41（1）： 112-123.

LIU Q， DUAN F， SANG Y， et al. A survey of loop-closure detection method of visual SLAM in complex environments[J]. Robot， 2019， 41（1）： 112-123.

[4]杨淑静， 丛海林， 杨超. 动态运行复杂体系档案信息化管理问题与对策——青岛大学材料学科实训平台[J]. 化学教育（中英文）， 2023， 44（4）： 115-121. YANG S J， CONG H L， YANG C. Problems and countermeasures of archives information management in dynamic operation complex system： material discipline training platform of Qingdao university[J]. Chinese Journal of Chemical of Education， 2023， 44（4）：115-121.

[5]MILFORD M， WYETH G. SeqSLAM： visual route-based navigation for sunny summer days and stormy winter nights[C]// Proceedings of the IEEE International Conference on Robotics and Automation （ICRA）. Saint Paul：IEEE， 2012： 1643-1649.

[6]MILFORD M， SHEN C， LOWRY S， et al. Sequence searching with deep-learnt depth for condition and viewpoint invariant route-based place recognition[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops （CVPRW）. Boston：IEEE， 2015： 18-25.

[7]TSINTOTAS K， BAMPIS L， RALLIS S， et al. SeqSLAM with bag of visual words for appearance based loop closure detection[C]// Proceedings of the International Conference on Robotics in Alpe-Adria Danube Region. Patras： Springer， 2018： 580-587. [8]JEGOU H， DOUZE M， SCHMID C， et al. Aggregating local descriptors into a compact image representation[C]// Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR）. San Francisco： IEEE， 2010： 3304-3311. [9]NASEER T， SPINELLO L， BURGARD W， et al. Robust visual robot localization across seasons using network flows[C]// Proceedings of the AAAI Conference on Artificial Intelligence. Quebec： AAAI， 2014： 2564-2570.

[10]HANSEN P， BROWNING B. Visual place recognition using HMM sequence matching[C]// Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago： IEEE， 2014： 4549-4555.

[11]SIAM S， ZHANG H. Fast-SeqSLAM： a fast appearance based place recognition algorithm[C]// Proceedings of the IEEE International Conference on Robotics and Automation （ICRA）. Singapore： IEEE， 2017： 5702-5708.

[12]MALKOV Y， YASHUNIN D. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2020， 42（4）， 824-836.

[13]KLEINBERG J. Navigation in a small world[J]. Nature， 2000， 406（6798）： 845.

[14]周鍵，董永红.测控实验室内关键节点电压的校正方法仿真[J].计算机仿真，2022，39（7）：124-127，223.

Zhou J， DONG Y H.Simulation of voltage correction method for pilot nodes in measurement and control laboratory[J].Computer Simulation ，2022， 39（7）：124-127，223.

[15]ARANDJELOVIC R， GRONAT P， TORII A， et al. NetVLAD： CNN architecture for weakly supervised place recognition[C]// Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR）. Las Vegas： IEEE， 2016： 5297-5307.

（责任编辑 李 进）