基于層次化可導航小世界網絡改進的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.

（責任編輯 李 進）