曾桂萍，孫作雷，潘 盼

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

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

曾桂萍，孫作雷，潘 盼

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

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

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

0 引言

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

1 詞袋技術(shù)

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

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

(1)

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

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

(2)

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

2 詞對(duì)袋(BoWP)分析

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

2.1基本思想

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

2.2 BoWP原理分析

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

(3)

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

(4)

(5)

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

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

(6)

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

(7)

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

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

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

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

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

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

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

3.2 Dloop與BoWP計(jì)算時(shí)間的比較分析

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

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

4 結(jié)束語(yǔ)

可靠的定位與構(gòu)圖需魯棒性強(qiáng)的閉環(huán)檢測(cè)算法，其挑戰(zhàn)在于合理的計(jì)算復(fù)雜度下獲得更高的召回率。本文詞袋與詞對(duì)袋對(duì)比算法的實(shí)驗(yàn)代碼分別引用DloopDetector算法與基于詞對(duì)袋的高性能閉環(huán)檢測(cè)到研究中。詞袋方法(Dloop)的優(yōu)勢(shì)是速度快，技術(shù)成熟易于實(shí)現(xiàn)，但其召回率低。詞對(duì)袋技術(shù)提高了召回率，因其將空間鄰域信息結(jié)合到詞典中，并且解決了詞袋技術(shù)的感知混淆問(wèn)題，缺點(diǎn)是需要另外建一詞典存儲(chǔ)空間信息，因而占用較多的內(nèi)存。最高效的閉環(huán)檢測(cè)算法是結(jié)合簡(jiǎn)單和執(zhí)行速度快的詞袋技術(shù)，同時(shí)采用高召回性能詞對(duì)袋技術(shù)，以便應(yīng)對(duì)不斷增大的地圖尺寸實(shí)現(xiàn)實(shí)時(shí)高效的檢測(cè)閉環(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] 崔大成,曾連蓀.基于視覺(jué)字典的移動(dòng)機(jī)器人閉環(huán)檢測(cè)方法研究[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)檢測(cè)中詞袋與詞對(duì)袋的對(duì)比研究[J].微型機(jī)與應(yīng)用，2017,36(17)：21-23,30.

2017-03-13)

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