閉環檢測中詞袋與詞對袋的對比研究

曾桂萍，孫作雷，潘 盼

(上海海事大學 信息工程學院，上海 201306)

閉環檢測中詞袋與詞對袋的對比研究

曾桂萍，孫作雷，潘 盼

(上海海事大學 信息工程學院，上海 201306)

從詞袋技術(BoW)入手探究拓撲地圖中的閉環檢測算法，在性能和時間效率兩個因素系統地對比了詞袋技術與詞對袋技術(BoWP)，詞袋技術是以Dorian Gálvez López 提出的DLoopDetector算法為參考，詞對袋(BoWP)技術是以Nishant Kejriwal提出的高性能閉環檢測為原始算法，主要凸顯了詞對袋技術在性能上的優越性。詞袋技術的優點是技術成熟易實現，但存在感知混疊問題。通過額外創建一個由詞對組成的詞典來克服傳統詞袋法中因矢量的量化導致的感知混淆的限制。實驗表明，詞對袋方法比Dloop能提供更好的召回性能，并且減少了算法的計算時間及復雜度。

詞袋；詞對袋；閉環檢；同步定位和構圖

0 引言

閉環檢測[1]是移動機器人同步定位和構圖(Simultaneous Localization and Mapping，SLAM)[2]的關鍵技術。本文以外觀(圖像)為基礎的拓撲地圖研究SLAM系統的閉環檢測問題，機器人需要準確無誤地辨認出已訪問過的位置，閉環檢測成功能夠顯著降低構圖中的累積誤差。SLAM系統多數采用成熟的詞袋技術，本文以基于場景對象識別的實時視覺構圖(DloopDetector，Dloop)[3]為代表性的詞袋(Bag-of-Word，BoW)[4]技術，與新提出的詞對袋(Bag of Word Pair，BoWP)[5]技術在原理和性能上進行比較。Dloop具有傳統詞袋技術難以解決的問題，比如矢量量化導致的感知混淆，即將機器人在不同的地理位置觀測到的相似場景誤認為同一個位置，而詞對袋技術剛好通過直接特征匹配方法解決了Dloop感知混淆的問題，用其原始特征直接計算圖像的相似度；詞袋技術中機器人對先前觀測圖像進行的離線訓練方式生成視覺詞匯庫，離線詞典無法很好地描述機器人將來觀測的場景圖像，導致召回性能不太樂觀，詞對袋技術通過在線的拓撲圖方法改善了系統性能。因此，研究具有低復雜度和高召回性能的視覺閉環探測具有重要意義。

1 詞袋技術

詞袋技術被廣泛用于場景識別和閉環檢測中，而閉環檢測實質上是一種檢測觀測數據相似性的算法，即實時地計算當前觀測圖像是否與環境地圖中的關鍵幀發生閉環。詞袋模型從大量的圖像中提取相似的視覺特征(像SURF[6])并聚類，然后建立離線詞典，進而尋找每個圖中含有哪些“單詞”(word)，用字典中詞頻的直方圖查找檢索圖像與地圖中現有圖像之間的相似性。Dloop采用K-L 散度及卡方距離檢索候選閉環，同時運用樹形結構管理詞典，TF-IDF(Term Frequency-Inverse Document Frequency)[7]技術作為權重機制來選取視覺單詞，以及正向索引計算特征的相關性，反向索引加速比較場景圖像等技術，以確保對當前查詢圖像的搜索效率。

歸一化相似度計算圖像候選閉環，公式如下：

(1)

其中，vt-Δt表示上一幀圖像，用與上一幀圖像計算的相似度來歸一化與字典樹中圖像計算的相似度，選取閾值α，當前幀與上一幀圖像相似度大于α歸為候選閉環，否則不做閉環檢測。真實閉環的確認是通過驗證是否滿足時間以及幾何一致性以避免假陽性閉環，一致性足夠高的圖像即視為閉環并用于修正或增廣地圖，使地圖更加精確。

正確的圖像匹配能獲得成功的閉環從而保證軌跡與地圖的全局一致性，反過來錯誤的匹配會損害地圖的精確性，這些錯誤分為兩類：(1)假陽性(False Positive，FP)，又稱感知偏差，指事實上不同的場景被當成了同一個；(2)假陰性(False Negative,FN)，又稱感知變異，指事實上同一個場景被當成了兩個，這就是上文提出的矢量量化所致的感知混淆。精確度(Precision，P)反映判定的正例中真正的正例樣本的比重，即判別為閉環中真實閉環的概率；召回率(Recall，R)反映被正確判定的正例占總的正例的比重，即真實的閉環在所有正例中的比率。計算公式如下：

(2)

一個好的閉環檢測算法應該能檢測出盡量多的真實回環，本文用準確率-召回率曲線來評價Dloop與BoWP算法的好壞。雖然此方法能提供更好的召回性能，但隨著地圖尺寸的不斷增長會帶來過高的計算要求。

2 詞對袋(BoWP)分析

本文的詞對袋(BoWP)技術是以Nishant Kejriwal提出的高性能閉環檢測為原始算法[5]，詞對袋主要目標是解決詞袋法中感知混淆問題，以及提高詞袋方法的召回性能，即結合共現信息相關聯的方向屬性更好地檢測閉合環路。

2.1基本思想

BoWP技術除創建單詞組成的字典外還增加詞對的詞典，即需要創建兩個詞典：單詞詞典用原始特征在線的方式創建，將輸入圖像的新詞增量加入到使用FLANN庫[8]的K-D樹[9]中；詞對的字典使用多重映射數據結構[6]實現。有效的詞對需要考慮共現信息且滿足空間約束條件，共現信息指一個單詞位置空間鄰域是否包含其他鄰近字，若包含則與其他鄰近字一起形成共現信息提供更好的閉環辨識。詞典中的字是基于特征點的尺度參數形成的定向鄰域范圍，而特征點規模取決于它在特征提取算法時檢測到的尺寸。BoWP的關鍵技術包括在線地創建增量詞典，用K-D樹基于近鄰搜索來識別潛在的候選閉環，用FLANN庫(1.8.4版本)于拓撲構圖中。

2.2 BoWP原理分析

BoWP中圖像特征選用SURF描述符，因其對光度和幾何扭曲的魯棒性良好且用時少。兩個詞典：單詞詞典是由K-D樹創建，詞對的字典使用多重映射數據結構實現。現用這些單詞和對應詞對計算相似度，即檢索圖像和地圖中現有節點之間基于TF-IDF的評分。

(3)

由于圖像是被有順序地獲取的，BoWP閉環的決策過程納入貝葉斯框架的時間相干性，提供有效對抗可能出現的瞬態錯誤的魯棒性。引用Angeli[11]等人的貝葉斯框架：融合多個觀測量信息為單一的觀測似然值，用于計算圖像中節點的后驗閉環概率[12]。BoWP獲得的觀察似然值有可能合并了單詞與詞對的信息，其似然函數公式如下：

(4)

(5)

其中μw、σw和μwp、σwp分別對應觀察矢量(zw,zwp)中單詞和詞對的均值和標準偏差，隨機變量X可采用任何節點索引作為其值，若與當前圖像沒有相似節點則乘1，若為一個新位置則X=-1代入似然公式，在該節點X=i的綜合似然性為：

L(X=iM)=Lw(X=iM)LWP(X=iM)

(6)

所以節點索引i取集合{-1, 1,…,M}中任意值，此似然值計算節點的后驗概率P(X=iM)便于檢索圖片的閉環候選。若節點具有最高閉環概率比閾值θlc=0.5更高，便可聲明為圖像的一個可能候選閉環。如果該節點滿足第二階段的RANSAC驗證：

(7)

其中Ninliers是匹配RANSAC的點數量，Nimage和Nnode為圖片內點數量和節點數量，θransac是唯一用戶定義的參數，當Pmatch≥θransac時進一步證實了該閉環，若不滿足，則為新的節點加入地圖特征中[13]。

3 實驗結果與分析

Dloop與BoWP實驗圖像特征均采用64維的SURF矢量處理圖像并進行場景識別，如圖1所示對比了Dloop與BoWP在慕尼黑工業大學數據集室外捕獲的同一個閉環結果，Dloop中軌跡中黑色加粗線段表示的是產生閉環的部分，當前幀只有在發生閉環時才提取出閉環幀；BoWP根據檢索圖像的似然值，選出后驗概率最高的且滿足RANSAC驗證的閉環。

圖1 慕尼黑工業大學數據集下分別用Dloop與BoWP捕捉閉環

3.1 Dloop與BoWP召回性能的比較分析

表1中，BoWP與Dloop在保證θransac值、α閾值等保持一致的條件下，在同一數據集比較兩種技術的召回性能，實驗采用新學院數據集以及慕尼黑工業大學的室內室外數據集，可看出BoWP的召回率均高于Dloop算法。因為BoWP摻入空間同現信息克服感知混疊問題，并相應提高了其召回性能。如表可見所有數據集中BoWP比Dloop獲得更高的召回率。

表1 Dloop與BoWP在同一數據集上召回率比較

3.2 Dloop與BoWP計算時間的比較分析

Dloop與BoWP算法的計算時間分配比重多的部分，其一是每個圖像SURF特征的提取，另一個是創建K-D樹并擴建地圖尺寸。計算復雜性主要取決于詞典大小和地圖中的節點數量，當BoWP技術的詞典尺寸是上一次重建K-D樹詞典尺寸的兩倍時，需要進行重建K-D樹；而Dloop中是在每一次迭代過程都得需要重建一次樹[14]，所以理論上Dloop耗費的時間長一些，通過實驗也可以得到證實。表2中記錄了BoWP與Dloop在3個數據集下的計算時間，對比結果還是比較明顯的，BoWP處理圖片所需計算時間比Dloop時間少。

表2 不同數據集各圖像的平均計算時間 (s)

4 結束語

可靠的定位與構圖需魯棒性強的閉環檢測算法，其挑戰在于合理的計算復雜度下獲得更高的召回率。本文詞袋與詞對袋對比算法的實驗代碼分別引用DloopDetector算法與基于詞對袋的高性能閉環檢測到研究中。詞袋方法(Dloop)的優勢是速度快，技術成熟易于實現，但其召回率低。詞對袋技術提高了召回率，因其將空間鄰域信息結合到詞典中，并且解決了詞袋技術的感知混淆問題，缺點是需要另外建一詞典存儲空間信息，因而占用較多的內存。最高效的閉環檢測算法是結合簡單和執行速度快的詞袋技術，同時采用高召回性能詞對袋技術，以便應對不斷增大的地圖尺寸實現實時高效的檢測閉環，為SLAM系統的整體構圖提供關鍵的支撐，獲得更加精確的圖并實現高效定位。

[1] LATIF Y, LERMA C C, NEIRA J. Robust loop closing over time, in: proceedings of robotics: science and systems[C]. Sydney, Australia, July, 2012: 233-240.

[2] MADDERN W, MILFORD M, WYETH G. CAT-SLAM: probabilistic localisation and mapping using a continuous appearance-based trajectory[J]. Int. J. Robot. Res, 2012, 31(4): 429-451.

[3] GALVEZ-LOPEZ D, TARDOS J D. Bags of binary words for fast place recognition in image sequences[J]. IEEE Transactions on Robot, 2012,28(5): 1188-1197.

[4] ANGELI A, FILLIAT D, DONCIEUX S, et al. Fast and incremental method for loop-closure detection using bags of visual words[J]. IEEE Transactions on Robot,2008,24(5):1027-1037.

[5] NISHANT K, SWAGAT K, TOMOHIRO S. High performance loop closure detection using bag of word pairs[J]. Robotics and Autonomous Systems, 2016,77: 55-65.

[6] BAY H, ESS A, TUYTELAARS T, et al. Speeded-up robust features (SURF)[J]. Computer Vision and Image Understanding, 2008,110(3): 346-359.

[7] BERGIN J. Sets, maps, multisets, and multimaps[C]. In: Data Structure Programming, Springer, 1998: 239-266.

[8] JOHNS E, YANG G Z. Feature co-occurrence maps: appearance-based localisation throughout the day[C]. In: 2013 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2013: 3212-3218.

[9] MORIOKA N, SATOH S. Building compact local pairwise codebook with joint feature space clustering[C]. In: Computer Vision-ECCV 2010, Springer, 2010: 692-705.

[10] LABBé M, MICHAUD F. Appearance-based loop closure detection for online large-scale and long-term operation[J]. IEEE Transactions on Robotics, 2013, 29(3): 734-745.

[11] CUMMINS M J, NEWMAN P M. FAB-MAP: Probabilistic localization and mapping in the space of appearance[J]. International Journal of Robotics Research, 2008, 27(6): 647-665.

[12] LIU Y, ZHANG H. Indexing visual features: real-time loop closure detection using a tree structure[C]. In: 2012 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2012: 3613-3618.

[13] NISTER D, STEWENIUS H. Scalable recognition with a vocabulary tree[C]. In: Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on. IEEE, 2006: 2161-2168.

[14] 崔大成,曾連蓀.基于視覺字典的移動機器人閉環檢測方法研究[J].微型機與應用,2015,34(9):85-88.

A comparative research on BoW and BoWP in loop closure detection

Zeng Guiping, Sun Zuolei, Pan Pan

(School of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

The paper explores loop closure detection algorithm in the topological map from Bag of Words (BoW) technology, and systematically compares the performance in time and efficiency between Bag-of-Word and Bag of Word Pairs (BoWP). The BoW technology reference the DLoopDetector algorithm proposed by Dorian Gálvez López, because it’s mature technology is easy to realize. The BoWP technology is based on a high performance loop closure detection algorithm, which proposed by Nishant Kejriwal. It highlights the superiority in the BoWP technology on the performance, by creating an extra dictionary of word pairs to overcome the limitation of perceptual aliasing due to vector quantization in the traditional bag of word method. The experimental results show that the BoWP can provide better recall performance than the typical Dloop, besides, it can reduce the computational time and complexity of the algorithm.

BoW; BoWP; loop closure detection; simultaneous localization and mapping

TP273

：A

10.19358/j.issn.1674- 7720.2017.17.006

曾桂萍，孫作雷，潘盼.閉環檢測中詞袋與詞對袋的對比研究[J].微型機與應用，2017,36(17)：21-23,30.

2017-03-13)

曾桂萍(1993-)，女，碩士，主要研究方向：移動機器人導航。孫作雷(1982-)，男，博士，副教授，主要研究方向：移動機器人導航、機器學習。潘盼(1989-)，男，碩士，主要研究方向：移動機器人導航。