董海霞，曾連蓀

　　（上海海事大學 信息工程學院，上海 201306）

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

　　關鍵詞：詞袋；視覺詞典；閉環檢測；圖像數據庫；匹配

0引言

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

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

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

1問題定義

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

　　1.1二進制特征

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

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

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

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

　　1.2圖像數據庫

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

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

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

2閉環檢測算法

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

　　2.1查詢數據庫

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

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

　　2.2匹配組

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

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

　　2.3時間上的一致性

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

　　2.4幾何驗證

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

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

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

3實驗

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

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

4結束語

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

參考文獻

　　［1］ 曲麗萍. 移動機器人同步定位與地圖構建關鍵技術的研究［D］. 哈爾濱： 哈爾濱工程大學, 2013.

　　［2］ 柴紅霞. 移動機器人在SLAM中數據關聯方法的研究［D］. 大連： 大連理工大學, 2010.

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

　　［4］ 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.

　　［5］ 崔大成,曾連蓀.基于視覺字典的移動機器人閉環檢測方法研究［J］.微型機與應用,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.

　　［7］ 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.

　　［8］ 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.

　　［10］ 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