董海霞，曾連蓀

　?。ㄉ虾：Ｊ麓髮W(xué) 信息工程學(xué)院，上海 201306）

　　摘要：在基于人工視覺的移動機器人導(dǎo)航中，閉環(huán)檢測是機器人準確構(gòu)建地圖及定位的一個重要問題。本文研究的閉環(huán)檢測算法結(jié)合了計算機視覺中的詞袋技術(shù)和視覺詞典技術(shù)，在對圖像進行處理時利用了BRIEF+FAST關(guān)鍵點的方法，利用離線階段生成的詞典樹將二進制描述子空間離散化。訓(xùn)練圖像生成的圖像數(shù)據(jù)庫結(jié)構(gòu)主要由等級詞袋、倒置索引和直接索引組成。倒置索引和直接索引提高了算法的效率。為了保證閉環(huán)檢測結(jié)果的可靠性，對于匹配的圖像還要進行驗證。重點詳述了一種高效的閉環(huán)檢測算法，相對一般的基于概率的閉環(huán)檢測，在硬件設(shè)備相同的情況下，本算法效率更高。

　　關(guān)鍵詞：詞袋；視覺詞典；閉環(huán)檢測；圖像數(shù)據(jù)庫；匹配

0引言

　　即時定位與構(gòu)圖（Simultaneous Localization and Mapping，SLAM）指的是機器人在未知的環(huán)境中，增量式地創(chuàng)建周圍環(huán)境的連續(xù)地圖，同時利用創(chuàng)建的地圖為自身導(dǎo)航［1］。SLAM問題可以實現(xiàn)機器人真正的自主導(dǎo)航。數(shù)據(jù)關(guān)聯(lián)是指移動機器人用確定傳感器觀測量與目標源之間的對應(yīng)關(guān)系［2］。機器人進行一段時間的運行后，當(dāng)長時間沒有被觀測到的區(qū)域被機器人自身攜帶的傳感器觀測到時，標準的匹配算法就會失敗。當(dāng)能穩(wěn)定地檢測到這些區(qū)域時，閉環(huán)檢測算法就能夠提供正確的數(shù)據(jù)關(guān)聯(lián)。

　　早期數(shù)據(jù)關(guān)聯(lián)算法的研究主要停留在幾何方面，Singer等人提出的最近鄰（Nearest Neighbor, NN）算法是最早也是最簡單的數(shù)據(jù)關(guān)聯(lián)方法［3］。在環(huán)境特征密度較大的情況下，使用NN算法容易發(fā)生關(guān)聯(lián)失敗現(xiàn)象，由于NN算法忽略了數(shù)據(jù)之間的相關(guān)性，可能導(dǎo)致一些錯誤的關(guān)聯(lián)。Jose Neira等人提出了聯(lián)合相容性檢驗（Joint Compatibility Test, JC Test）算法。聯(lián)合相容分支定界（Joint Compatibility Branch and Bound, JCBB）［3］算法能排除一些NN算法無法排除的錯誤的關(guān)聯(lián)假設(shè)［4］，基于幾何的數(shù)據(jù)關(guān)聯(lián)方法沒有充分利用到機器人周圍的環(huán)境信息。隨著相機價格的下降，相機取代傳統(tǒng)的傳感器，在數(shù)據(jù)關(guān)聯(lián)方面的應(yīng)用越來越廣泛。機器人通過所攜帶相機拍攝的周圍環(huán)境圖片含有豐富的信息，因此可以通過對圖片的處理，判斷圖片間的相似性，看是否形成了一個閉環(huán)，從而對機器人構(gòu)建的地圖進行修正或增廣。

　　本文中的閉環(huán)檢測算法主要基于視覺詞典［5］及對匹配的圖像進行的幾何檢測，其高效性使得這種算法更適合實時應(yīng)用。

1問題定義

　　閉環(huán)檢測是指當(dāng)移動機器人到達一個先前已經(jīng)構(gòu)建過地圖的位置時，能夠判斷出這個位置已經(jīng)構(gòu)建過地圖，然后對原來構(gòu)建的地圖進行更新、修正［6］。

　　1.1二進制特征

　　在進行兩幅圖像比較時，需要從圖像中提取關(guān)鍵點和局部特征，這一步是非常費時的，這也是閉環(huán)檢測算法實時應(yīng)用的瓶頸。為了克服提取特征和關(guān)鍵點費時的問題，本文采用了FAST關(guān)鍵點和最優(yōu)的BRIEF描述子。FAST關(guān)鍵點是一些像角一樣的點，這些點是通過在一個半徑為3的Bresenham圓中，對一些像素點的灰度強度進行比較得到的［7］。因為檢測到的像素點的個數(shù)有限，所以在實時的應(yīng)用中，F(xiàn)AST關(guān)鍵點也能很快被檢索到。

　　對于每一個FAST關(guān)鍵點，以這個點為中心點畫一個方形的圖像塊，然后計算一個BRIEF描述子。BRIEF描述子是二進制的比特向量，通過圖像塊（為了降低噪聲已經(jīng)事先經(jīng)過高斯平滑處理）中兩個像素點的強度比較得到比特分量的值［8］。給定圖像塊的尺度Sb，設(shè)置好用于比較的像素點的對數(shù)Lb（也就是描述子向量的長度），像素點是在離線階段隨機選擇的。對于圖像中的關(guān)鍵點P，它的BRIEF描述子向量B(P) 可以描述為：

　　Bi(P)是描述子向量中的第i個比特，I(·)表示平滑圖像中像素點的強度，ai、bi表示第i個檢測點相對于圖像塊中心點的2D偏置量，它們的取值范圍是:

　　這種描述子向量不需要訓(xùn)練，只是在離線時隨機選擇的點，占用的時間可以忽略。BRIEF描述子最大的優(yōu)點是計算速度快，由于這種描述子只是一個比特向量，可以通過異或比較兩個向量之間不同比特的個數(shù)（漢明距離），在實時的應(yīng)用中計算歐氏距離要比計算漢明距離慢得多。在使用SIFT和SURF描述子時，計算兩個向量之間的距離就是計算歐氏距離。

　　1.2圖像數(shù)據(jù)庫

　　為了讓機器人識別出目前所在的位置是否已經(jīng)構(gòu)建過地圖，本文使用了圖像數(shù)據(jù)庫。圖像數(shù)據(jù)庫主要由等級詞袋、倒置索引和直接索引三部分組成，如圖1所示。詞典中的字就是樹中的葉子節(jié)點。倒置索引中存放的是字的權(quán)重。直接索引中的內(nèi)容主要是圖像的特征以及與特征相關(guān)的詞典樹中的節(jié)點。

　　在機器人自主導(dǎo)航過程中，機器人攜帶的相機拍攝了大量的圖片。為了能夠有序地存儲這些圖片，用詞袋技術(shù)通過視覺詞典把圖片轉(zhuǎn)換成稀疏的數(shù)值向量［9］。視覺詞典是在離線階段生成的，它把描述子空間離散成W個視覺字。本文所用的特征BRIEF使得二進制描述子空間離散化，生成一個更簡潔的詞典，把詞袋按等級排列，整個詞典就是一個樹形的結(jié)構(gòu)。為了生成詞典樹，從訓(xùn)練圖像（這些圖像與在線處理的圖像是相互獨立的）中提取大量的特征，它們所對應(yīng)的描述子按照Kmeans算法離散成Kw個二進制的簇，這些簇就是詞典樹的一級節(jié)點，對于每一個節(jié)點再進行Kmeans算法，生成第二級節(jié)點，依次按照這種步驟進行Lw次，最終就會生成W個字的詞典樹［10］。根據(jù)字在訓(xùn)練集中的相關(guān)性，給每個字分配一個權(quán)重，那些出現(xiàn)次數(shù)比較頻繁、對于區(qū)分不同圖像沒有太大作用的字，分配較小的權(quán)重，對于區(qū)分圖像作用顯著的字，分配權(quán)重大一些。假設(shè)在t時刻，獲得一幅圖像It，根據(jù)圖像中特征的二進制描述子，從根到葉子遍歷整個詞典樹，按照漢明距離最小原則在每一級選擇一個節(jié)點，到達葉子節(jié)點時就可以得到該圖像對應(yīng)的二進制數(shù)值向量Vt∈Rw。兩幅圖像I1、I2之間的相似性可通過計算它們的數(shù)值向量之間的相似值來衡量：

　　在圖像數(shù)據(jù)庫中除了詞袋外還有倒置索引和直接索引。對于詞典中的一個字Wi，倒置索引中內(nèi)容是包含這個字的圖像的列表。有了這種結(jié)構(gòu)，在從數(shù)據(jù)庫中搜索與查詢圖像相似的數(shù)據(jù)庫圖像時，就可以只在與查詢圖像有共同字的數(shù)據(jù)庫圖像中進行搜索。如果在倒置索引中存放圖像的數(shù)值向量中對應(yīng)Wi這個字的分量，還可以得到字在圖像中的權(quán)重。直接索引存儲的是圖像It中字的父節(jié)點和與節(jié)點相關(guān)的局部特征ftj。直接索引的結(jié)構(gòu)可以使得在幾何驗證時，只尋找同一個字的特征間或者是有相同父節(jié)點的特征間的對應(yīng)性，這樣就節(jié)省了時間。但是，當(dāng)有新的圖像要加入數(shù)據(jù)庫時，倒置索引和直接索引都要進行更新。

2閉環(huán)檢測算法

　　本文研究的閉環(huán)檢測算法主要分為四步個步驟。

　　2.1查詢數(shù)據(jù)庫

　　從圖像數(shù)據(jù)庫中檢索與給定圖像相似的圖像。當(dāng)機器人獲得最新的圖像It時，首先根據(jù)在離線階段生成的詞典樹把它轉(zhuǎn)換成詞袋向量Vt，然后在數(shù)據(jù)庫中進行搜索得到一些候選的匹配〈Vt,Vt1〉，〈Vt,Vt2〉，…，根據(jù)公式（3）計算出這些匹配對應(yīng)的相似值s(Vt,Vtj)，相似值的變化范圍是由查詢圖像和圖像中字的分布決定的。對相似值進行歸一化，得到歸一化相似值η:

　　Vt-Δt是前一幅圖像的詞袋向量。當(dāng)機器人在某一瞬間狀態(tài)急劇變化時，s(Vt,Vt-Δt)的值就會很小，導(dǎo)致歸一化相似值很高。為了避免這種錯誤的出現(xiàn)，對s(Vt,Vt-Δt)設(shè)置一個小的門限值，忽略短時間內(nèi)與Vt相似度很低的圖像。同時，為了避免有效的圖像被錯誤的忽略掉，門限值應(yīng)該設(shè)置得小一點。對于歸一化相似值η，設(shè)置一個門限α，拋棄那些沒有達到最小相似值α的匹配。

　　2.2匹配組

　　當(dāng)相機的拍攝頻率較高時，時間間隔很短的圖像往往具有很高的相似性。為了避免在數(shù)據(jù)庫中搜索時時間間隔很短的圖像之間互相競爭，這里把拍攝時間間隔很短的圖像看做是一個島，在匹配的時候把這些匹配看做是一個匹配。將時間戳tni，…，tmi，用一個時間戳Ti表示，VTi 表示整個圖像島的詞袋數(shù)值向量。根據(jù)相似值H，對島的相似性進行排序：

　　具有最大相似值的島作為候選的匹配組，再進行一致性檢驗。用圖像島的方法消除連續(xù)圖像匹配時的競爭，如果It和It′是一個真正的閉環(huán)，It往往與It′±Δt，It’±2Δt，… ，也有很高的相似性。

　　2.3時間上的一致性

　　在得到最佳的匹配島VT′后，要檢測當(dāng)前匹配與前面匹配的一致性。即匹配〈Vt，VT′〉與前面k個匹配〈Vt-Δt,VT1〉，…，〈Vt-kΔt,VTk〉必須一致，類似于JCBB算法中匹配時聯(lián)合兼容性檢驗。如果一個島符合一致性檢驗，則認為最大η值對應(yīng)的匹配〈Vt，Vt′〉是最佳匹配（t′∈T′），把它作為一個候選的閉環(huán)，最后還要經(jīng)過幾何驗證來判斷其是否是一個真正的閉環(huán)。

　　2.4幾何驗證

　　對于候選為閉環(huán)的圖像還要進行幾何驗證。幾何驗證是指利用RANSAC(Random Sample Consensus)算法在匹配的圖像It和It′之間找到局部特征的對應(yīng)性。局部特征的比較有兩種方法，遞歸搜索是最簡單也是最慢的方法，它是通過計算 It中的每一個特征和It′中的每一個特征在描述子空間中的距離， 根據(jù)最近鄰比例策略，選擇特征之間的對應(yīng)特性。但是當(dāng)圖像中特征點數(shù)量很多時，遞歸搜索法的計算量是不可接受的。

　　另外一種方法是近似最近鄰法，當(dāng)有一幅新的圖像加入圖像數(shù)據(jù)庫中，要把成對的節(jié)點和特征存儲在直接索引中，在對It和It′進行幾何驗證時，查詢It′的直接索引，只比較同一個節(jié)點關(guān)聯(lián)的特征，節(jié)點在詞典樹中的級數(shù)l是事先給定的。由于進行特征比較的次數(shù)明顯少于遞歸搜索，節(jié)省了大量時間。l的設(shè)置會影響幾何驗證的結(jié)果，當(dāng)l=0時，只對屬于同一個字的特征進行比較，這時幾何驗證效率最高，但是圖像間對應(yīng)的特征對數(shù)也是最少的，這就可能導(dǎo)致正確的閉環(huán)由于缺乏點之間的對應(yīng)性而被拒絕。相反，當(dāng)l=LW時，全部候選的匹配都能通過幾何驗證，但是此時，幾何驗證的效率也沒有得到改善。

　　在幾何驗證階段，只是對于匹配的圖像之間進行驗證，以確定兩者的相似度足夠高，在驗證之后還要進行正確的數(shù)據(jù)關(guān)聯(lián)。

3實驗

　　整個實驗?zāi)M的是室外靜態(tài)環(huán)境下閉環(huán)檢測算法的過程，具體步驟：首先在離線階段生成視覺詞典樹，然后在機器人運行時利用生成的詞典樹進行閉環(huán)檢測。整個過程共檢測到7個閉環(huán)，提取特征用的是BRIEF算法，特征提取時間為8.946 99 ms/圖，實驗中的詞袋字典是在離線階段生成的，規(guī)模是106，詞典樹中共有754 997個字，詞典樹的級數(shù)是L=6，Kmeans算法中K的值設(shè)置為10。

　　實驗中的原始算法是由美國計算機視覺研究者Dorian Gálvez López 提出的DLoopDetector算法，本文實驗中不同于原始算法的地方是：在Dorian Gálvez López的實驗中，DBow2與DLoopDetector是分立的；在本文進行的實驗中，把DBow2與DLoopDetector結(jié)合在一起，即利用DBow2生成的詞典樹進行閉環(huán)檢測實驗。本文實驗效果圖如圖2所示。

4結(jié)束語

　　在視覺SLAM中，閉環(huán)檢測是數(shù)據(jù)關(guān)聯(lián)的擴展，是一個從點對點到面對面的過程。本文研究的閉環(huán)檢測算法使用的圖像數(shù)據(jù)庫結(jié)構(gòu)除了等級詞袋、倒置索引外，還有直接索引，這種結(jié)構(gòu)使得幾何驗證的效率更佳。二進制描述子BRIEF的使用使提取圖像特征、計算描述子之間距離的速度更快。但是在尺度、光照、相機發(fā)生旋轉(zhuǎn)時，BRIEF描述子是不穩(wěn)定的。因為本文中實驗是在室外靜態(tài)環(huán)境下進行的，而且相機也只是在平面內(nèi)進行微小運動，所以多數(shù)實驗具有很高的準確性。

參考文獻

　?。?］ 曲麗萍. 移動機器人同步定位與地圖構(gòu)建關(guān)鍵技術(shù)的研究［D］. 哈爾濱： 哈爾濱工程大學(xué), 2013.

　　［2］ 柴紅霞. 移動機器人在SLAM中數(shù)據(jù)關(guān)聯(lián)方法的研究［D］. 大連： 大連理工大學(xué), 2010.

　?。?］ 張雪晶,孫作雷,曾連蓀，等.基于聯(lián)合相容分支定界的關(guān)聯(lián)算法研究［J］.微型機與應(yīng)用,2015,34(15):8284,88.

　?。?］ NEIRA J， TARDS J D. Data association in stochastic mapping using the joint compatibility test［J］. Robotics and Automation, IEEE Transactions on, 2001，17（6）：890897.

　?。?］ 崔大成,曾連蓀.基于視覺字典的移動機器人閉環(huán)檢測方法研究［J］.微型機與應(yīng)用,2015,34(9):8588.

　　［6］ WILLIAMS B, CUMMINS M, NEIRA J, et al. A comparison of loop closing techniques in monocular SLAM［J］. Robotics and Autonomous Systems, 2009，57（12）：11881197.

　?。?］ GLVEZLPEZ D， TARDS J. D. Bags of binary words for fast place recognition in image sequences［J］. Robotics, IEEE Transactions on, 2012，28（5）：11881197.

　?。?］ CALONDER M, LEPETIT V, STRECHA C, et al. Brief: binary robust independent elementary features［C］. Computer VisionECCV 2010, 2010:778792.

　　［9］ SIVIC J, ZISSERMAN A. Video google: a text retrieval approach to object matching in videos［C］. In Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, 2003：14701477.

　?。?0］ NISTER D， STEWENIUS H. Scalable recognition with a vocabulary tree［C］. In Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, 2006：21612168