視覺SLAM中閉環(huán)檢測算法的研究

董海霞，曾連蓀

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

視覺SLAM中閉環(huán)檢測算法的研究

董海霞，曾連蓀

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

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

詞袋；視覺詞典；閉環(huán)檢測；圖像數據庫；匹配

0 引言

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

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

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

1 問題定義

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

1.1 二進制特征

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

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

(1)

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

(2)

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

1.2 圖像數據庫

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

圖1 詞典樹、倒置索引和直接索引組成的圖像數據庫

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

(3)

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

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

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

2.1 查詢數據庫

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

(4)

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

2.2 匹配組

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

(5)

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

2.3 時間上的一致性

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

2.4 幾何驗證

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

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

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

3 實驗

整個實驗模擬的是室外靜態(tài)環(huán)境下閉環(huán)檢測算法的過程，具體步驟：首先在離線階段生成視覺詞典樹，然后在機器人運行時利用生成的詞典樹進行閉環(huán)檢測。整個過程共檢測到7個閉環(huán)，提取特征用的是BRIEF算法，特征提取時間為8.946 99 ms/圖，實驗中的詞袋字典是在離線階段生成的，規(guī)模是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生成的詞典樹進行閉環(huán)檢測實驗。本文實驗效果圖如圖2所示。

圖2 實驗效果圖：機器人的運動軌跡，其中包括檢測到的閉環(huán)

4 結束語

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

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

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

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

[4] NEIRA J， TARDS 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] 崔大成,曾連蓀.基于視覺字典的移動機器人閉環(huán)檢測方法研究[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.

[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.

Loop detection algorithm in VSLAM

Dong Haixia，Zeng Liansun

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

In the mobile robot navigation based on artificial vision, loop closure detection is of vital importance for mapping and localization. Technologies in computer vision, bag-of-words and visual vocabulary, are applied in the loop closure detection algorithm in this essay. BRIEF+FAST key point is used to process images. Vocabulary tree that is created offline discretizes binary descriptor space. Training images are used to build image database, which is composed of a hierarchical bag of words, inverse indexes and direct indexes. Inverse indexes and direct indexes improve efficiency greatly. Verification has to be performed to improve reliability of loop closing candidates. Compared with probability loop detection, the algorithm in this essay is more efficient with the same hardware facilities.

bag-of-words; vision vocabulary; loop detection; image database; match

TP242

A

1674-7720(2016)05-0001-03

董海霞，曾連蓀．視覺SLAM中閉環(huán)檢測算法的研究[J] .微型機與應用，2016，35(5)：1-3,7.

2015-12-01)

董海霞(1990-)，女，碩士，主要研究方向：移動機器人導航。

曾連蓀(1962-)，男，在讀博士，教授，主要研究方向：定位導航系統(tǒng)。