張夢真 王慶芝 劉其朋

摘要：SeqSLAM是移動機器人領(lǐng)域廣泛使用的一種視覺定位算法，它對光照等因素較魯棒，但受視角變化影響較大。另外，SeqSLAM采用了蠻力搜索匹配的方式，在較大規(guī)模數(shù)據(jù)集中無法滿足實時性要求。針對以上問題，對SeqSLAM算法做了兩方面的改進(jìn)：首先將圖像表示為局部聚合描述子向量，提取圖像特征；然后采用層次化可導(dǎo)航小世界網(wǎng)絡(luò)算法搜索相似圖像序列，具有更高的搜索效率。測試表明，改進(jìn)的SeqSLAM算法可以獲得更高的精確率和召回率，搜索時間顯著降低。

關(guān)鍵詞：SeqSLAM；回環(huán)檢測；局部聚合描述子向量；層次化可導(dǎo)航小世界網(wǎng)絡(luò)

中圖分類號： TP183文獻(xiàn)標(biāo)識碼： A

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

基金項目：國家自然科學(xué)基金青年科學(xué)基金（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）是自主移動機器人領(lǐng)域的研究熱點^[1-2]。在機器人建圖過程中，如果可以準(zhǔn)確判斷行駛路徑中的回環(huán)（即回到了曾經(jīng)到過的地點），則可以通過全局優(yōu)化減少偏移量，顯著提高建圖的精度^[3-4]?；谝曈X信息的回環(huán)檢測容易受到視角、光照、季節(jié)、天氣等因素的影響，可能出現(xiàn)誤判。為了提高檢測準(zhǔn)確性，SeqSLAM算法在檢測時考慮了時序信息，通過對比兩個圖像序列（而不是孤立的兩幅圖像）來判斷機器人是否到達(dá)了之前的地點^[5]。研究表明，SeqSLAM算法可以很好地的應(yīng)對光照、季節(jié)等變換的影響，提高了回環(huán)檢測算法的實用性。

在標(biāo)準(zhǔn)的SeqSLAM算法中，一幅圖像的特征直接由其本身的像素值表示。如果兩幅圖像對應(yīng)位置像素之差的絕對值之和較小，則認(rèn)為這兩幅圖像是相似的。這種判斷圖像相似性的方式比較簡單直觀，但是在公開數(shù)據(jù)集上的測試表明，SeqSLAM對視角變化的魯棒性較差。為了解決這一問題，SeqSLAM的原作者采用深度學(xué)習(xí)技術(shù)，基于一幅圖像構(gòu)造出虛擬的左右平移的多幅圖像，從而擴大了圖像搜索對比的空間，在一定程度上提高了水平視角變換的魯棒性，但對于其他類型的視角變換效果依然較差^[6]。為了進(jìn)一步改進(jìn)SeqSLAM中的圖像表征問題，Tsintotas等^[7]將詞袋模型（Bag of Words， BoW）引入SeqSLAM中，圖像用詞袋向量表征，可以較好地應(yīng)對視角變換的問題。詞袋模型是一種比較經(jīng)典的圖像特征表示模型，它從圖像中提取出若干具有代表性的視覺單詞，用一個低維特征向量來表示一幅圖像^[7]。已有研究表明，詞袋模型對圖像的表征比較粗?；?，其本質(zhì)是統(tǒng)計一幅圖像中視覺單詞出現(xiàn)的次數(shù)，無法進(jìn)一步細(xì)分原始圖像局部特征點相對于視覺單詞的偏移程度。因此，本文采用更加精細(xì)化、圖像表征效果更好的局部聚合描述子向量（Vector of Locally Aggregated Descriptors， VLAD）來描述圖像，以期獲得更優(yōu)的檢測效果^[8]。

除了改進(jìn)SeqSLAM算法中的圖像表征方式，研究者們還嘗試提高SeqSLAM的搜索效率。標(biāo)準(zhǔn)的SeqSLAM采用蠻力搜索的方式對比圖像序列，為了檢測n時刻圖像是否與某一歷史圖像構(gòu)成回環(huán)，需要搜索從初始時刻到n-1時刻所有的圖像序列。對于整個行駛路線來說，計算復(fù)雜度為O（n²），在大規(guī)模數(shù)據(jù)集上無法滿足實時性要求。文獻(xiàn)[9]用網(wǎng)絡(luò)流方法替換了SeqSLAM中的蠻力搜索算法，但整體計算復(fù)雜度仍為O（n²）。文獻(xiàn)[10]采用隱馬爾可夫鏈查找最佳匹配圖像序列，其中需要計算相似性矩陣，計算復(fù)雜度并沒有降低。Siam等^[11]提出了Fast-SeqSLAM算法，針對機器人在同一路線上行駛兩次的情形，第1次行駛時，將圖像描述保存為樹結(jié)構(gòu)；第2次行駛時，采用最近鄰搜索的方式尋找與當(dāng)前圖像序列相似度最高的圖像序列。Fast-SeqSLAM算法的計算復(fù)雜度可以達(dá)到O（nlogn）級別，但它的問題在于需要預(yù)先存儲圖像數(shù)據(jù)，因此無法用于在線回環(huán)檢測。為了應(yīng)對這一問題，本文在VLAD圖像表征的基礎(chǔ)上，將層次化可導(dǎo)航小世界網(wǎng)絡(luò)（Hierarchical Navigable Small World， HNSW）應(yīng)用于相似圖像序列的搜索過程中^[12]。與Fast-SeqSLAM不同，本文的改進(jìn)算法可以在機器人行駛過程中實時構(gòu)造層次化可導(dǎo)航小世界網(wǎng)絡(luò)，并實現(xiàn)了在線回環(huán)檢測的功能。

本文主要貢獻(xiàn)和創(chuàng)新點包括兩部分：1）在改進(jìn)SeqSLAM圖像表征方面，采用了局部聚合描述子向量方式，可以更好地應(yīng)對圖像視角變換等問題；2）在提高SeqSLAM搜索效率方面，采用了近似最近鄰搜索算法——層次化可導(dǎo)航小世界網(wǎng)絡(luò)，可以在幾乎不損失搜索精度的情況下顯著降低搜索時間。

1 基于VLAD和HNSW改進(jìn)的SeqSLAM算法

為方便理解，首先給出算法的整體框圖，如圖1所示，然后逐一介紹各部分的具體實現(xiàn)。

1.1 圖像的VLAD描述

與經(jīng)典的詞袋模型類似，VLAD也需要離線構(gòu)造視覺詞典。一般在大規(guī)模圖像數(shù)據(jù)集上采用SIFT，SURF，ORB等算法提取大量局部特征，然后經(jīng)過K-Means聚類得到若干視覺單詞。假設(shè)一個視覺詞典C包含k個單詞，記作C={c₁，c₂，…，c_k}，其中c_i為經(jīng)過K-Means聚類算法得到的第i個簇CL_i的中心點。直觀理解為視覺特征空間被劃分為k個子空間，每個子空間由它的中心點（即視覺單詞）表示，如圖2所示，其中黑點代表從數(shù)據(jù)集中提取的局部視覺特征，五角星代表聚類中心點，所有屬于同一個簇的局部視覺特征可以由相應(yīng)的一個視覺單詞表示。

在視覺詞典的基礎(chǔ)上，圖像I可以用相應(yīng)的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搜索相似圖像序列

當(dāng)圖像被表示成VLAD向量之后，可以通過比較這些向量之間的差距來判斷圖像之間的相似性，進(jìn)而判斷是否出現(xiàn)了回環(huán)。為了提高判斷的準(zhǔn)確性，SeqSLAM并不是對比單幅圖像的相似性，而是對比由多個連續(xù)圖像組成的序列，當(dāng)兩個圖像序列中相鄰的多幅圖像都相似時，才認(rèn)為檢測到了回環(huán)。標(biāo)準(zhǔn)SeqSLAM中采用了蠻力搜索的方式，檢測時間較長。為了提高檢測速度，本文采用了HNSW近似最近鄰搜索的方式。

1.2.1 在線構(gòu)造HNSW數(shù)據(jù)結(jié)構(gòu)

HNSW可以隨著機器人的移動而在線構(gòu)造。為了將HNSW算法應(yīng)用到圖像序列中，首先需要將圖像序列轉(zhuǎn)換為HNSW網(wǎng)絡(luò)中的節(jié)點，過程如圖3所示，其中長度為p的圖像序列（以VLAD形式呈現(xiàn)）轉(zhuǎn)化為一個節(jié)點，因此節(jié)點包含數(shù)據(jù)的維度為p×k×d。

在定義了節(jié)點的基礎(chǔ)上，接下來可以構(gòu)造HNSW網(wǎng)絡(luò)，其本身是一個多層網(wǎng)絡(luò)，如圖4所示。

下面介紹HNSW具體的構(gòu)造步驟。當(dāng)機器人移動時，假設(shè)在n時刻接收到一幅圖像，則從n-p到n時刻圖像序列對應(yīng)的VLAD序列形成一個節(jié)點，其中p為序列長度。該節(jié)點所處的最高層數(shù)服從幾何概率分布，即概率隨層數(shù)的升高而指數(shù)減小。如果節(jié)點位于l層，則該節(jié)點同時位于0到l-1層。在每一層上，節(jié)點采用貪婪算法搜索最近的若干鄰居節(jié)點，并與之相連。采用這種方式就可以構(gòu)造出層次化的可導(dǎo)航小世界網(wǎng)絡(luò)。已有研究表明，“小世界”現(xiàn)象背后的原因是網(wǎng)絡(luò)中同時存在長程連接和短程連接，其中通過長程連接可以快速到達(dá)目標(biāo)節(jié)點附近區(qū)域，通過短程連接可以局部精確搜索^[13-14]。不難發(fā)現(xiàn)，前述方法構(gòu)造出的HNSW網(wǎng)絡(luò)中，上層網(wǎng)絡(luò)中的連接相當(dāng)于長程連接，下層網(wǎng)絡(luò)中的連接相當(dāng)于短程連接。

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

在機器人移動過程中，與HNSW構(gòu)造過程同時進(jìn)行的是最近鄰節(jié)點（即相似圖像序列）的搜索。搜索過程由頂層網(wǎng)絡(luò)中一個隨機選擇的節(jié)點開始，然后依照網(wǎng)絡(luò)鄰居關(guān)系貪婪搜索到本層中的最近鄰節(jié)點，然后轉(zhuǎn)到下一層，從該節(jié)點繼續(xù)貪婪搜索。該過程一直持續(xù)到最底層網(wǎng)絡(luò)，最終找到全局近似最近鄰節(jié)點。搜索過程如圖5所示。

從圖5中可以看到，該HNSW網(wǎng)絡(luò)共有3層，空心圓節(jié)點表示問詢節(jié)點，即當(dāng)前圖像序列對應(yīng)的節(jié)點，搜索從頂層隨機節(jié)點開始，標(biāo)注為start，搜索它的鄰居，找到與問詢節(jié)點距離最近的節(jié)點，轉(zhuǎn)入下一層繼續(xù)搜索，最終在底層找到問詢節(jié)點的近似最近鄰節(jié)點，標(biāo)注為end。問詢節(jié)點與end節(jié)點對應(yīng)的圖像場景就是機器人行駛路徑中可能存在的回環(huán)。

2 公開數(shù)據(jù)集驗證

本節(jié)將通過實驗分析改進(jìn)算法的精確率-召回率（Precision-Recall， PR）指標(biāo)以及搜索時間復(fù)雜度。以兩個公開數(shù)據(jù)集作為測試平臺——NewCollege和CityCentre。測試代碼已分享到連接：https：//github.com/qipengliuNTU/Efficient-SeqSLAM-with-HNSW，實驗中的關(guān)鍵參數(shù)如表1所示。

2.1 PR曲線指標(biāo)

為了更好地理解PR曲線指標(biāo)，簡要介紹一些相關(guān)的概念。在回環(huán)檢測中，如果兩幅不同場景拍攝的圖像被誤認(rèn)為是同一場景的圖像，這種錯誤被稱為假陽性（False Positive， FP）;同一場景的兩幅圖像被誤認(rèn)為是不同場景的圖像，這種錯誤被稱為假陰性（False Negative， FN）。相應(yīng)地，正常檢測到了回環(huán)就稱為真陽性（True Positive， TP），正確檢測到了非回環(huán)就是真陰性（True Negative， TN）。在此基礎(chǔ)上，可以計算精確率P和召回率R為

其中，#Z表示Z樣本的數(shù)量。

本文對比4種算法：1）標(biāo)準(zhǔn)的SeqSLAM；2）基于BoW改進(jìn)的SeqSLAM；3）基于VLAD改進(jìn)的SeqSLAM；4）基于VLAD和HNSW改進(jìn)的SeqSLAM。

PR曲線如圖6所示，其中圖例表明了每條曲線對應(yīng)的算法。從圖6可以看出，與傳統(tǒng)的SeqSLAM算法相比，基于VLAD改進(jìn)的算法在召回率提高時，可以保持較高的精確率，而前者的精確率下降較快?；贐oW改進(jìn)的算法一直保持較高的精確率，這意味著它檢測到回環(huán)基本上是正確的，但是召回率無法進(jìn)一步提升，表明它錯過了一些真實的回環(huán)?；贖NSW改進(jìn)的算法效果僅次于蠻力搜索算法。

2.2 搜索時間對比

移動機器人的某些應(yīng)用場景，例如自動駕駛汽車，對回環(huán)檢測的實時性要求較高。傳統(tǒng)的SeqSLAM中采用蠻力搜索的方式，無法應(yīng)對大規(guī)模數(shù)據(jù)集（即較長行駛路線）的檢測。從圖6的PR曲線可以看出，基于HNSW改進(jìn)的算法具有與蠻力搜索算法類似的效果，但搜索時間顯著降低，如圖7所示。

在機器人的移動過程中，需要檢測的圖像數(shù)量不斷增加。圖7中seq+vlad在搜索相似圖像時采用了蠻力搜索的方式，即當(dāng)前圖像序列要與所有歷史圖像序列逐一對比，時間復(fù)雜度為O（n），其中n為歷史圖像數(shù)量。隨著歷史圖像的增加，每次接收到新圖像之后需要對比的圖像也相應(yīng)增加，搜索時間會逐漸變長。實驗中記錄了從搜索開始到結(jié)束的用時，結(jié)果如圖7所示，搜索時間隨著歷史圖像規(guī)模的擴大而線性增長，符合理論預(yù)期。圖7中seq+vlad+hnsw算法采用HNSW最近鄰搜索方法。文獻(xiàn)[12]指出，HNSW算法的復(fù)雜度為O（logn）。實驗中記錄了搜索開始到結(jié)束的用時，結(jié)果如圖7所示，搜索時間隨歷史圖像的增加呈對數(shù)增長，符合理論預(yù)期。

3 結(jié)論

本文從圖像表征魯棒性和圖像匹配效率兩方面對標(biāo)準(zhǔn)的SeqSLAM做了改進(jìn)。在圖像表征方面，采用了局部聚合描述子向量VLAD方式，可以在更精細(xì)的層面上刻畫圖像局部特征點以及整幅圖像的特征，更好地應(yīng)對圖像視角變換的影響；在提高SeqSLAM搜索效率方面，采用了近似最近鄰搜索算法——層次化可導(dǎo)航小世界網(wǎng)絡(luò)HNSW，可以在幾乎不損失搜索精度的情況下提高搜索效率。基于公開數(shù)據(jù)集NewCollege和CityCentre的測試表明，改進(jìn)算法具有較高的檢測準(zhǔn)確率和召回率，并且搜索時間顯著下降。

在未來工作中，可以嘗試功能更強的圖像表征方式，例如基于深度神經(jīng)網(wǎng)絡(luò)的NetVLAD^[15]。另外，可以嘗試將改進(jìn)的回環(huán)檢測算法嵌入到完整的SLAM框架中，在實際項目中測試其性能。

參考文獻(xiàn)：

[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ìn)展[J]. 智能系統(tǒng)學(xué)報， 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]劉強， 段富海， 桑勇， 等. 復(fù)雜環(huán)境下視覺SLAM閉環(huán)檢測方法綜述[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]楊淑靜， 叢海林， 楊超. 動態(tài)運行復(fù)雜體系檔案信息化管理問題與對策——青島大學(xué)材料學(xué)科實訓(xùn)平臺[J]. 化學(xué)教育（中英文）， 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]周鍵，董永紅.測控實驗室內(nèi)關(guān)鍵節(jié)點電壓的校正方法仿真[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.

（責(zé)任編輯 李 進(jìn)）