基于thLSH的快速閉環檢測方法

姜海洋　樸松昊　張祖亮

摘 要：同步定位與地圖構建（SLAM）問題是實現移動機器人在未知環境中自我定位和導航的關鍵技術，具有重大的理論意義和研究價值。閉環檢測是SLAM中的一個關鍵模塊，對機器人實時更新地圖和避免引入錯誤的地圖節點起著關鍵作用。本文將視覺閉環檢測問題看作是圖像檢索問題，基于深度學習的思想，將RandNet神經網絡應用到閉環檢測，并利用基于閾值的局部敏感哈希算法對其提取的圖像特征匹配過程進行加速。實驗結果表明：本文所提出的基于thLSH的快速閉環檢測方法，在保證高準確率的前提下，特征匹配速度提升了10倍，能夠更好滿足閉環檢測的實時性需求。

關鍵詞：同步定位和地圖構建； 閉環檢測； 神經網絡； 局部敏感哈希

Abstract： The issue of Simultaneous Localization and Mapping （SLAM） is a crucial technology for autonomous positioning and navigation of mobile robots in an unknown environment， and has theoretical significance and research value. Loop closure detection is a vital module in SLAM and plays an important role in updating the map in real time and avoiding the introduction of wrong map nodes. The loop detection vision problem in this thesis is regarded as an image retrieval issue， and based on the idea of deep learning， the RandNet neural network is applied to the loop detection problem， and a threshold-based locality-sensitive hashing algorithm is also used to accelerate the image feature matching process. The experimental results show that the fast loop detection method based on thLSH proposed in this paper can improve the feature extraction speed by more than 3 times on the premise of high accuracy， the speed of feature matching is 10 times higher， and it can meet the real-time requirement of loop detection.

Key words： visual Simultaneous Localization and Mapping； loop closure detection； neural network； locality-sensitive hashing

引言

同步定位和建圖問題（simultaneous localization and mapping，簡稱SLAM）中的即時定位和建圖，是利用算法對傳感器在未知環境中采集的信息進行處理，由于環境的未知性、建模算法本身的缺陷、傳感器的累計誤差等問題，致使SLAM的定位與建圖的精度不夠準確，甚至可能導致環路不能閉合，而無法判斷機器人是否回到已訪問過的區域。SLAM中的閉環檢測（Loop Closure Detetion，LCD）模塊是通過判斷當前位置是否處于已訪問過的區域，抑制傳感器的累積誤差[1]，進而提高后端圖優化的準確性，保證地圖構建的效果的精準表達。

閉環檢測，本質上是數據的關聯問題。在基于視覺同步定位與地圖構建（visual Simultaneous Localization and Mapping， vSLAM）系統中，通常采用的方法是將當前位置采集的場景圖像與此前所采集的場景圖像進行匹配，當2個場景圖像的相似度達到一定閾值時，即可判定發生了閉環。當前，大部分vSLAM系統的閉環檢測還是采用基于SIFT[2]、SURF[3]等特征的視覺詞袋模型[4]（Bag of View Words，BoVW），但是當場景或是感知條件不斷動態變化時，圖像的特征描述魯棒性很低。在閉環檢測過程中，環境中可能出現比較相似的場景或者物體，易導致在視覺圖像特征匹配時產生感知混淆[5]（perceptual aliasing）問題。另外，隨著測量時間的增長，傳感器所測得的數據規模也越來越大，圖像視覺特征相似度的計算量也隨之增加，此時若僅僅依賴機器人的本體傳感器，閉環檢測的精度將大幅下降，這些問題都將造成vSLAM閉環檢測失敗，因此需要構建獨立的閉環檢測系統。

近幾年，深度學習理論和技術得到快速發展，在圖像識別和分類問題中優勢明顯，已有部分學者開始將深度學習技術應用到vSLAM的閉環檢測中，但是大部分方法的參數訓練過程耗時較長，并且獲取的圖像特征維度較大。而在較大規模的閉環檢測中，場景過大、圖像特征維度高等問題，將導致圖像特征匹配過程計算量過大，而無法滿足vSLAM工作實時性的需求。

本文圍繞vSLAM系統中的閉環檢測問題展開了深入的研究，選取基于無預訓練且高效的RandNet神經網絡的閉環檢測方法，提高場景圖像特征的提取速度，并針對傳統所使用的基于余弦相似度矩陣的匹配方法，提出了一種基于閾值局部敏感哈希的圖像特征匹配方法，將場景圖像特征匹配速度提高10倍。

1 相關工作

目前，大部分視覺閉環檢測算法是基于Image-to-Image匹配，即將移動機器人當前所處位置的場景圖像與先前訪問過的場景圖像進行相似度比較匹配。在此匹配策略下，閉環檢測被看作是圖像匹配問題，所以考慮的是圖像描述性和相似性度量這2個問題。

傳統的Image-to-Image解決方案中，最常用的圖像描述方法是視覺詞袋模型。Cummins 等人[6]提出基于視覺外觀（visual appearance）對場景進行描述，使用 FAST 算子提取每一幅訓練圖像的局部特征，然后將特征描述空間通過K中心點聚類（k-medians clustering）方法聚類為簇，成為詞典樹的第一層，重復執行獲取其它層，最終得到W個葉子節點，即視覺詞匯，移動機器人在運動時將生成的視覺詞匯與視覺單詞空間（visual word space）進行快速匹配，實現閉環檢測。Zhang等人[7]將圖像的透視不變二值特征描述子應用到增量式的視覺詞袋模型中，把漢明距離看成相似度測量，提高了閉環檢測的效率。梁志偉等人[8] 應用混合高斯模型為視覺詞袋中的每一個視覺詞匯建立概率模型，得到每一個視覺詞匯的向量表示，并用貝葉斯濾波器提高閉環檢測的準確率。Liu等人[9]把圖像的GIST描述子當作圖像的全局特征，提高BoVW方法閉環檢測的效率。文獻[10]用基于ORB的視覺詞典進行閉環檢測，利用ORB特征的旋轉不變性和處理尺度變化的特性，能夠從不同視角識別場景。文獻[11]將空間共生信息添加到視覺詞典當中，解決了閉環檢測感知混淆的缺陷。Li等人[12]提出利用金字塔TF-IDF得分的視覺詞典樹對SLAM進行閉環檢測，解決了基于視覺詞典樹的閉環檢測視覺詞匯數目的限制和算法效率低的問題。文獻[13]提出了一種基于融合時間信息、拓撲構建場景地圖的閉環檢測方法，提升了準確率和召回率。

盡管在當前的研究中，結合BoVW和 GIST在閉環檢測中效果不錯，但由于BoVW和GIST特征都是手工設計，導致模型對光照變化非常敏感，場景或感知條件一旦發生變化，則不能夠提供較高魯棒性的圖像特征描述，致使vSLAM閉環檢測的成功率大幅度降低。

近幾年來，深度學習模型的興起為圖像描述指出了新的方向，能夠由淺入深地提取圖像特征，給出魯棒的圖像描述，在圖像識別和分類等領域取得巨大成功。考慮到移動機器人在Image-to-Image匹配中同樣需要準確的特征信息，自2015 年以來，學者們開始嘗試將深度學習方法應用到vSLAM的閉環檢測中。Xia等人[14]利用級聯深度學習模型 PCANet 提取圖像特征，網絡簡單并且便于調試，但是為了防止輸出圖像的特征維度過大，導致輸入圖像像素過小。Hou等人[15]利用基于caffe框架的AlexNet模型進行特征提取，通過實驗發現，與傳統的圖像特征提取方法相比，在光照變化明顯的環境中，深度學習提取圖像特征的魯棒性更高，而且特征提取速率更快，但是所提取特征的維度過高，SLAM系統不能夠實時運行。文獻[16]中利用AlexNet對Places數據庫經由再訓練而得的模型進行特征提取，發現通過Places數據集再訓練的網絡明顯提高閉環檢測的準確率。同時為了解決實時性問題，Bai等人[17]研發的 Places-CNN深度學習模型，利用局部敏感哈希（local-sensitive hash）進行圖像特征壓縮，提高特征匹配效率。文獻[18]中，利用Nordland數據集對Places-AlexNet深度學習預訓練模型再訓練，通過實驗比較二元歐氏距離、二元余弦距離、三元歐氏距離和三元余弦距離幾種特征向量的相似性度量，發現余弦距離比歐氏距離效果更佳。

上述基于深度學習模型的閉環檢測中，通常采用有監督的學習方法，需要大量標簽數據，在移動機器人工作之前花費較多時間對神經網絡中的參數進行訓練，在環境未知的前提下實際操作具有很大的困難。因此，采用不依賴于數據集的模型有更高的可行性。

Gao等人[19]使用堆棧式去噪稀疏自編碼模型提取圖像特征，通過計算特征的相似性矩陣，判斷是否發生閉環，同時優化自動編碼機中的損失函數。該方法在公開的數據集上測試，取得了較好的效果，但是沒有考慮圖像的空間局部特性。

與傳統Image-to-Image匹配的閉環檢測方法相比，基于深度學習模型的閉環檢測把圖像信息表達得更加充分，對于光照等感知條件有更高的魯棒性。但是實時性問題依然沒有解決。

2 基于thLSH的快速閉環檢測

2.1 RandNet級聯神經網絡

RandNet神經網絡[20]是由Chan等人提出的，其原形是PCANet神經網絡， Xia等人已在文獻[14]中將PCANet應用在vSLAM的閉環檢測當中，但是PCANet的一個缺點是需要已知的場景圖像進行預訓練，而其變種RandNet神經網絡，成功克服了這個問題，但是以犧牲一點準確率作為代價。移動機器人未來將應用于各種未知復雜的環境中，若是能消除預訓練的困擾，還能保持較高的準確率，當然是最理想的情況。為此，本文提出了基于RandNet的神經網絡的vSLAM閉環檢測方法。

RandNet神經網絡模型包含以下3個步驟，分別是：多級濾波器組濾波、二值化哈希編碼和分塊直方圖。如圖1所示，就是RandNet模型框架結構示意圖。

所提取的圖像特征是一個稀疏的向量，不同場景圖像之間很容易區分，代價就是向量維度比較大，增加了特征相似性的計算量。而RandNet神經網絡的性能與PCANet神經網絡的性質差別已經在文獻[14]給出，本文則將側重于研究thLSH方法，僅采用RandNet神經網絡進行場景圖像的特征提取。

2.2 基于thLSH的快速閉環檢測

對于閉環檢測中的特征匹配問題，傳統方法利用的是余弦距離相似性矩陣。雖然通過余弦距離相似性矩陣可以保證閉環檢測的準確性，但卻存在設計不足，也就是：余弦距離是通過浮點數向量之間的乘除運算得來，當特征向量的維度k較大時，計算量較大，不能滿足SLAM系統的實時運行需要。

閉環檢測中的特征匹配問題，即在已經訪問過的位置區域中尋找與當前位置圖像特征相似度最高的特征，用以判斷是否發生閉環，可以看作是圖像檢索問題。基于此，就可以考慮利用局部敏感哈希算法加速檢索過程。

Lv等人[21]提出了一種基于閾值的局部敏感哈希算法（Locality-Sensitive Hashing Scheme Based on Thresholding，簡稱thLSH），用位向量的漢明距離來近似特征向量的加權L1距離。而在閉環檢測中通常使用的是余弦距離，所以本文提出使用thLSH作為濾波器，先將距離位向量最近的k個向量之外的向量都剔除出余弦距離最近鄰的候選集，之后在k個候選特征中，比較余弦距離找出最近鄰。至此，可得研究流程設計分述如下。

（1）位向量的設計生成。首先，研究討論如何將一個特征向量通過哈希函數轉化為位向量，使得生成的2個位向量之間的漢明距離近似于2個特征向量之間的加權L1距離。算法1的設計代碼可參見如下。

（3）利用加權L1距離進行濾波。在前k加權L1距離近鄰中利用余弦距離找出最近鄰，再與設定加權L1距離閾值進行比較，用以判斷是否發生閉環。

綜上研究可得，基于thLSH的閉環檢測流程可如圖2所示。

3 實驗結果和分析

3.1 實驗環境及參數配置

實驗平臺是Windows 10（64位）下的Matlab2014a 。數據集是City Center和 New College，這2個數據集是由牛津大學Cummins等人采選收集，主要用于vSLAM的研究和閉環檢測算法的評估驗證。2個數據集分別包含1 237 對和 1 073對圖像，圖像均是尺寸為640×480的三通道彩色圖。數據集中還給出了形成閉環區域的真實標注，用來檢驗閉環檢測算法的準確率，標注以矩陣的形式給出，若圖像i與圖像j形成閉環區域，即可認定是在相同位置采集的，則（i， j）對應的數值為 1，否則為 0。

RandNet神經網絡的參數包括級聯層數、塊的大小k1、k2，每層級聯使用濾波器的數量L1、L2和輸出層中的局部直方圖塊的尺寸，實驗的參數與文獻[16]中所使用的并無差別，只是根據實際需要稍加調整，具體可見表1。原圖集為640×480的三通道彩色圖，但是作為輸入時，預處理成32×24大小的三通道圖。

本文使用準確率、召回率、平均精確率和時間性能進行驗證。其中，準確率和召回率是評價SLAM閉環檢測的2個常用指標，研究將用到的計算公式可描述如下：

式（6）、式（7）中，準確率表示檢測到的正確閉環數（TP）和檢測到的閉環總數（TP+FP）之比，召回率表示檢測到的正確閉環數（TP）和數據集中存在的總閉環總數（TP+FN）之比。

過程中，先利用算法提取特征，計算數據集中各圖像的余弦距離，得到相似度矩陣。再調整余弦距離的閾值，依據數據集提供的真實閉環檢測標注計算相應的準確率和召回率，由此繪制得到準確率-召回率曲線（即precision-recall曲線，或簡稱P-R曲線）。

3.2 實驗結果與分析

在基于閾值局部敏感哈希算法的性能比較實驗中，將對基于閾值的局部敏感哈希算法、基于隨機超平面的局部敏感哈希算法和基于余弦距離相似性矩陣算法的閉環檢測匹配進行測試。測試結果及分析內容闡述如下。

（1）準確率-召回率曲線的實驗結果比較。數據集New College和City Centre的實驗結果分別如圖3～5和圖6～8所示。顯然，基于隨機超平面局部敏感哈希算法的準確率-召回率曲線比基于閾值的局部敏感哈希算法和基于余弦相似性矩陣的閉環檢測匹配算法性能都要好，而基于閾值的局部敏感哈希算法，準確率稍微比基于余弦相似性矩陣的算法低一些。

（2）閉環檢測匹配時間的結果比較。基于數據集City Centre和New College的閉環檢測匹配時間記錄可分別參見表2與表3。分析可知，基于隨機超平面的局部敏感哈希算法（即表中的shLSH）對場景圖像特征的匹配速度提升了3倍多，而基于閾值的局部敏感哈希算法卻是基于隨機超平面的局部敏感哈希算法3倍多，是基于余弦相似性矩陣的算法的10倍。究其原因就在于基于余弦相似性矩陣的算法要進行大量的浮點數乘除運算，雖然基于隨機超平面的局部敏感哈希算法最終也是利用位向量的漢明距離來進行研究運算，但是在降維過程中，仍然調取了浮點數矩陣乘法機制進行運算，而基于閾值的局部敏感哈希算法，則是在利用閾值將浮點向量轉換為位向量后計算漢明距離，并沒有更多的浮點運算，因此計算速度大大加快，進而顯著提升了圖像特征匹配速度。

4 結束語

針對目前基于深度學習的vSLAM中閉環檢測過程無法滿足實時性的需求的現狀，本文提出了基于閾值的局部敏感哈希算法對特征匹配過程進行加速。在RandNet神經網絡提取場景圖像特征的基礎上設計部署了仿真實驗，與傳統基于余弦相似性矩陣的方法和基于隨機超平面的局部敏感哈希方法進行比較。實驗結果表明，該方法能夠將傳統的基于余弦相似性矩陣方法提速10倍，而且比基于隨機超平面的局部敏感哈希方法也要快上3倍有余，因而能夠更好滿足閉環檢測的實時性需求。

參考文獻

[1] BEEVERS K， HUANG W. Loop closing in topological maps[C]// Proceedings of the 2005 IEEE Internationla Conference on Robotics and Automation（ICRA 2005）. Barcelona， Spain：IEEE， 2005：4367-4372.

[2] NG P C， HENIKOFF S. SIFT： Predicting amino acid changes that affect protein function[J]. Nucleic Acids Research， 2003， 31（13）： 3812-3814.

[3] BAY H， ESS A， TUYTELAARS T， et al. Speeded-up robust features （SURF）[J]. Computer Vision and Image Understanding， 2008， 110（3）： 346-359.

[4] SHEKHAR R， JAWAHAR C V. Word image retrieval using bag of visual words[C]//International Workshop on Document Analysis Systems. Gold Coast，Queensland， Australia：IEEE，2012： 297-301.

[5] WILLIAMS B，CUMMINS M， NEIRA J，et al. An image-to-map loop closing method for monocular SLAM[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Nica，France：IEEE， 2008： 2053-2059.

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

[7] ZHANG Guangcong， LILLY M J， VELA P A. Learning binary features online from motion dynamics for incremental loop closure detection and place recognition[J].arXiv preprint arXiv：1601.03821， 2016.

[8] 梁志偉， 陳燕燕， 朱松豪，等. 基于視覺詞典的單目視覺閉環檢測算法[J]. 模式識別與人工智能， 2013， 26（6）：561-570.

[9] LIU Yang， ZHANG Hong. Visual loop closure detection with a compact image descriptor[C]// IEEE/RSJ International Conference on Intelligent Robots and Systems. Vilamoura-Algarve， Portugal：IEEE， 2012：1051-1056.

[10]MUR-ARTAL R， TARDS J D. Fast relocalisation and loop closing in keyframe-based SLAM[C]//IEEE International Conference on Robotics and Automation. Hongkong， China：IEEE，2014：846-853.

[11]KEJRIWAL N， KUMAR S， SHIBATA T. High performance loop closure detection using bag of word pairs[J]. Robotics and Autonomous Systems， 2016， 77： 55-65.

[12]LI Bo， YANG Dan， DENG Lin. Visual vocabulary tree with pyramid TF-IDF scoring match scheme for loop closure detection[J]. Acta Automatica Sinica， 2011，37（6）： 665-673.

[13]MURPHY L， SIBLEY G. Incremental unsupervised topological place discovery[C]//IEEE International Conference on Robotics and Automation. Hongkong， China：IEEE， 2014： 1312-1318.

[14]Xia Yifan， LI Jie， QI Lin， et al. Loop closure detection for visual SLAM using PCANet features[C]//International Joint Conference on Neural Networks. Vancouver， BC，Canada：IEEE， 2016：2274-2281.

[15]HOU Yi， ZHANG Hong， ZHOU Shilin. Convolutional neural network-based image representation for visual loop closure detection[J]. arXiv preprint arXiv：1501.05241，2015.

[16]GOMEZ-OJEDA R， LOPEZ-ANTEQUERA M， PETKOV N， et al. Training a convolutional neural network for appearance-invariant place recognition[J]. arXiv preprint arXiv： 1505.07428， 2015.

[17]BAI Dongdong， WANG Chaoqun， ZHANG Bo， et al. Matching-range-constrained real-time loop closure detection with CNNs features[J]. Robotics and Biomimetics， 2016， 3（1）： 15.

[18]SHAHID M， NASEER T， BURGARD W. DTLC： Deeply trained loop closure detections for lifelong visual SLAM[C]//Proceedings of the RSS Workshop on Visual Place Recognition： What is it Good For.Ann Arbor， Michigan， USA：University of Michigan， 2016.

[19]GAO Xiang， ZHANG Tao. Unsupervised learning to detect loops using deep neural networks for visual SLAM system[J].Autonomous Robots， 2017， 41（1）：1-18.

[20]CHAN T H， JIA Kui， GAO Shenghua， et al. PCANet： A simple deep learning baseline for image classification[J].arXiv preprint arXiv： 1404.3606， 2014.

[21]LV Qin， CHARIKAR M， LI Kai. Image similarity search with compact data structures[J]. Thirteenth ACM International Conference on Information & Knowledge Management. Washington， DC， USA：ACM， 2004： 208-217.