曾桂萍，孫作雷，潘 盼

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

閉環(huán)檢測中詞袋與詞對袋的對比研究

曾桂萍，孫作雷，潘 盼

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

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

詞袋；詞對袋；閉環(huán)檢；同步定位和構(gòu)圖

0 引言

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

1 詞袋技術(shù)

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

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

(1)

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

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

(2)

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

2 詞對袋(BoWP)分析

本文的詞對袋(BoWP)技術(shù)是以Nishant Kejriwal提出的高性能閉環(huán)檢測為原始算法[5]，詞對袋主要目標(biāo)是解決詞袋法中感知混淆問題，以及提高詞袋方法的召回性能，即結(jié)合共現(xiàn)信息相關(guān)聯(lián)的方向?qū)傩愿玫貦z測閉合環(huán)路。

2.1基本思想

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

2.2 BoWP原理分析

BoWP中圖像特征選用SURF描述符，因其對光度和幾何扭曲的魯棒性良好且用時少。兩個詞典：單詞詞典是由K-D樹創(chuàng)建，詞對的字典使用多重映射數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)?，F(xiàn)用這些單詞和對應(yīng)詞對計算相似度，即檢索圖像和地圖中現(xiàn)有節(jié)點(diǎn)之間基于TF-IDF的評分。

(3)

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

(4)

(5)

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

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

(6)

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

(7)

其中Ninliers是匹配RANSAC的點(diǎn)數(shù)量，Nimage和Nnode為圖片內(nèi)點(diǎn)數(shù)量和節(jié)點(diǎn)數(shù)量，θransac是唯一用戶定義的參數(shù)，當(dāng)Pmatch≥θransac時進(jìn)一步證實(shí)了該閉環(huán)，若不滿足，則為新的節(jié)點(diǎn)加入地圖特征中[13]。

3 實(shí)驗結(jié)果與分析

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

圖1 慕尼黑工業(yè)大學(xué)數(shù)據(jù)集下分別用Dloop與BoWP捕捉閉環(huán)

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

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

表1 Dloop與BoWP在同一數(shù)據(jù)集上召回率比較

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

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

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

4 結(jié)束語

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

[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ī)器人閉環(huán)檢測方法研究[J].微型機(jī)與應(yīng)用,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

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

2017-03-13)

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