作者：Liam
來源：微信公眾號|3D視覺工坊(系投稿)

Bags of Binary Words for Fast Place Recognition in Image Sequences

原來論文中很詳細(xì)的講述了閉環(huán)和重定位過程中的操作，當(dāng)看對應(yīng)代碼的時候，最好先看看這些過程的說明。

摘要

本文提出了一種利用FAST+BRIFE得到的單詞包進(jìn)行視覺位置重識別的新方法。首先離散化二進(jìn)制描述符空間生成一個詞匯樹，然后利用這個樹來加速匹配點(diǎn)的幾何驗(yàn)證。本文的方法利用相同的參數(shù)在不同的數(shù)據(jù)集上做了測試都沒有假陽性的結(jié)果。包括特征提取的整個過程在有26300張圖片的序列中僅需要22ms/幀。

介紹

對于需要長時間運(yùn)行的SLAM系統(tǒng)，魯棒的重定位模塊十分重要。在跑實(shí)驗(yàn)的時候如果沒有閉環(huán)檢測，如果系統(tǒng)長時間的運(yùn)行后又到了先前到過的場景，這個時候傳統(tǒng)的識別方法就會失效，閉環(huán)檢測可以提供正確的數(shù)據(jù)關(guān)聯(lián)來獲得全局一致性的地圖。同樣的方法可以用在機(jī)器人由于突然的運(yùn)動，遮擋或者運(yùn)動模糊造成的軌跡丟失的重定位。在[1]中，作者證明了在小環(huán)境下map-to-image(尋找相機(jī)的最新幀與地圖上的特征之間的對應(yīng)。)的方法有著不錯的效果。但是在大場景下，image-to-image（或appearance-based尋找來自相機(jī)的最新圖像與之前看到的圖像之間的對應(yīng)關(guān)系）的方法表現(xiàn)的更好，比如快速的appearance-base（FAB-MAP）的大規(guī)模建圖更好.基本的技術(shù)是利用機(jī)器人實(shí)時收集的圖像來建立一個數(shù)據(jù)庫，當(dāng)進(jìn)來新的圖像的時候可以檢索得到與之最相近的圖像，如果他們足夠的相似，就認(rèn)為他們是一個閉環(huán)。最近幾年，很多算法都利用這個方法實(shí)現(xiàn)[2][3][4][5][6],即基于圖像匹配，將它們作為詞袋空間中的數(shù)值向量進(jìn)行比較.詞袋模型可以進(jìn)行非常有效和快速的圖像匹配，但是它們并不是閉環(huán)檢測的完美解決方案，這主要是由于perceptual aliasing(感知混淆)(我的理解是可能是相似的場景，比如同樣的走廊)造成的。為此，我們在后面進(jìn)行了檢查匹配圖像的幾何一致性的驗(yàn)證步驟。閉環(huán)檢測算法的瓶頸通常是特征提取，這在計算周期上比其他步驟要耗時十倍左右。這可能會導(dǎo)致SLAM算法在兩個解耦的線程中運(yùn)行:一個執(zhí)行主要的SLAM功能，另一個只是進(jìn)行閉環(huán)檢測，就像[5]中的那樣。

本文利用普通的CPU和單目相機(jī)可以實(shí)時的檢測閉環(huán)，建立圖像間的對應(yīng)點(diǎn)的匹配。本文的方法基于詞袋模型和幾何檢測（有幾個重要的新特性使它比目前的方法快得多）。最重要的速度改善的原因是因?yàn)槔昧税姹拘薷暮蟮腂RIEF描述子和FAST。BRIEF描述子是一個二進(jìn)制的向量，其中每個位是圍繞關(guān)鍵點(diǎn)的給定像素對之間的強(qiáng)度比較的結(jié)果。雖然簡短的描述符很難對比例和旋轉(zhuǎn)保持不變，但我們的實(shí)驗(yàn)表明，它們對于平面攝像機(jī)運(yùn)動的閉環(huán)是非常健壯的，這是移動機(jī)器人的常見情況，在特殊性和計算時間之間提供了一個很好的折中。本文引入了一組離散化二進(jìn)制空間的單詞，并使用一個直接索引(除了通常的反向索引之外)對其進(jìn)行擴(kuò)充。這是第一次利用二進(jìn)制單詞進(jìn)行閉環(huán)檢測。反向索引用于快速檢索可能與給定圖像相似的圖像。提出了一種利用直接索引有效獲取圖像間點(diǎn)對應(yīng)的新方法，加快了閉環(huán)驗(yàn)證的幾何檢驗(yàn)速度。為了驗(yàn)證是一個閉環(huán)，我們驗(yàn)證了圖像匹配的時間一致性。本文的創(chuàng)新之處在于，它提供了一種技術(shù)，可以在查詢數(shù)據(jù)庫時防止在同一位置收集的圖像相互競爭。我們通過將匹配過程中描述相同位置的圖像分組來實(shí)現(xiàn)這一點(diǎn)。通過實(shí)驗(yàn)證明本方法可以在52毫秒內(nèi)運(yùn)行整個閉環(huán)檢測過程，包括特征提取，其中包含26300張圖像(平均22毫秒)，這比以前的技術(shù)要好一個數(shù)量級。

相關(guān)工作

基于外觀的位置識別由于取得了優(yōu)異的結(jié)果，在機(jī)器人領(lǐng)域引起了極大的關(guān)注,這方面的一個例子是fabmap系統(tǒng)，它使用一個全景相機(jī)來檢測閉環(huán)，在軌跡為70公里和1000公里的序列中召回率分別為48.4%和3.1%，沒有假陽性。FAB-MAP用詞袋表示圖像，并使用一個“Chow-Liu”tree來離線學(xué)習(xí)單詞的共視概率。FAB-MAP已經(jīng)成為閉環(huán)檢測的黃金標(biāo)準(zhǔn)，但是當(dāng)圖像長時間在相似的場景中運(yùn)行的時候，其魯棒性會下降，這可能是使用前置相機(jī)時的情況。在Fast and incremental method for loop-closure detection using bags of visual words的工作中，兩個視覺單詞(外觀和顏色)以增量的方式在線創(chuàng)建。這兩個單詞一起作為貝葉斯過濾器的輸入，貝葉斯過濾器估計兩個圖像之間的匹配概率，考慮到以前的情況下的匹配概率。與這些概率方法相比，我們依靠時間一致性檢查來考慮以前的匹配，提高了檢測的可靠性。為了進(jìn)行候選幀檢驗(yàn)，我們通常利用幾何驗(yàn)證。利用極線約束來檢驗(yàn)最好的匹配候選幀。而且利用直接索引的方式更快的計算對應(yīng)點(diǎn)。Robust place recognition with stereo sequences利用雙目視覺里程計來得到實(shí)時的環(huán)境地圖，利用詞袋模型的方法檢測閉環(huán)。它們的幾何檢查包括計算匹配圖像之間的空間變換。但是，他們不考慮與以前匹配的一致性，這導(dǎo)致他們需要把幾何檢查應(yīng)用在多個幾個閉環(huán)檢測的候選對象。在大多數(shù)閉環(huán)檢測的系統(tǒng)中利用的是尺度不變的SIFT或者SUFT。因?yàn)樗麄儗Τ叨裙庹蘸托D(zhuǎn)具有不變性，而且在輕微的視角變化中表現(xiàn)出良好的行為，然而，這些特征通常需要100到700毫秒之間進(jìn)行計算。還有其他類似的特征可以減少運(yùn)算時間，例如SIFT描述子或者降低維度的SIFT。Konolige利用緊湊的隨機(jī)樹特征使工作有了質(zhì)的變化。這個方法計算當(dāng)前圖像塊和其他先前離線訓(xùn)練過的圖像塊的相似度。通過計算描述子來連接這些圖像塊中相似的值，最后利用random orthoprojections的方法降低維度。這就可以產(chǎn)生一個很快的描述子來滿足實(shí)時性的要求。本文和[3]的相似之處就是也利用了高效的特征。BRIEF描述子或者是尺度不變的BRISK和旋轉(zhuǎn)不變的FAST及BRIEF(orb)特征都是二進(jìn)制、僅需要很少時間去計算的。作為一種優(yōu)勢，它們的信息非常緊湊，因此占用的內(nèi)存更少，比較起來也更快。這允許更快地轉(zhuǎn)換到單詞空間。

二進(jìn)制特征

在圖像中提取特征和描述子是很耗時的，本文中利用FAST特征點(diǎn)和BRIEF描述子，F(xiàn)AST關(guān)鍵點(diǎn)的提取類似檢測角點(diǎn)，在半徑為3的圓中比較像素點(diǎn)的灰度值。因?yàn)橹挥泻苌僖徊糠窒袼攸c(diǎn)需要比較（一般135）所以這些點(diǎn)可以很快得到。對于每一個FAST特征點(diǎn)，我們檢測它周圍一個連續(xù)的塊狀的BRIEF描述子。描述子是二進(jìn)制的向量，其代表圖像塊中兩個像素點(diǎn)灰度值的比較結(jié)果。圖像塊需要預(yù)先利用高斯核函數(shù)濾波。根據(jù)先前給定的圖像塊大小Sb，在圖像塊中利用離線的方法隨機(jī)的選擇像素點(diǎn)對。除了Sb，我們也要設(shè)置Lb：描述子的長度。對于一個點(diǎn)p，它的描述子向量B(p)根據(jù)下式?jīng)Q定：

BRIEF描述子速度很快，一個256位的描述子僅需要17.3μm因?yàn)槊總€描述子就是一個二進(jìn)制的vector，所以可以直接比較兩個向量不同的位來得到兩個向量的距離(漢明距離)，即兩個向量可以直接進(jìn)行異或運(yùn)算。SIFT和SUFT的描述子是由浮點(diǎn)數(shù)組成的，經(jīng)常需要計算歐式距離。

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

為了檢測閉環(huán)，我們利用分層的單詞和直接及反向索引組成圖像數(shù)據(jù)庫。詞袋是一種使用視覺詞匯表將圖像轉(zhuǎn)換成稀疏的數(shù)字向量的技術(shù)，允許我們管理大量的圖像。視覺詞袋是通過離線的將描述符空間離散成W個視覺單詞生成的。通過離散化二進(jìn)制描述子空間，可以創(chuàng)建了更緊湊的詞袋。對于有層次的詞袋，詞匯表的結(jié)構(gòu)是樹狀的。為了得到詞袋，我們從一些訓(xùn)練圖像中提取豐富的特征，首先利用k-means++ seeding來執(zhí)行k-medians clustering以離散化檢測到的描述子。中值導(dǎo)致非二進(jìn)制的描述子截斷成0。這些簇構(gòu)成詞匯表樹的第一級節(jié)點(diǎn)。通過使用與每個節(jié)點(diǎn)關(guān)聯(lián)的描述符重復(fù)此操作創(chuàng)建后續(xù)級別，直到Lw次。最后，我們得到了一棵有W葉子節(jié)點(diǎn)的樹，W個葉子節(jié)點(diǎn)就是詞匯表中的單詞。每個單詞都根據(jù)其在訓(xùn)練集中的相關(guān)性賦予權(quán)重，減少那些頻繁出現(xiàn)的單詞的權(quán)重，因?yàn)樗麄儽鎰e性很弱。我們在這里定義頻率這個術(shù)語-inverse document frequency(tf-idf)。然后為了轉(zhuǎn)換一個在t時刻得到的

兩個結(jié)構(gòu)(詞袋和反向索引)通常是單詞包方法中用于搜索圖像的惟一結(jié)構(gòu)。但是作為一種新穎的通用方法，我們還利用直接索引存儲每個圖像的特征。我們根據(jù)單詞在樹中的層數(shù)l對節(jié)點(diǎn)進(jìn)行分離，從葉節(jié)點(diǎn)開始，層數(shù)為l = 0，直到根節(jié)點(diǎn)l = Lw。對于每個圖像It，我們存儲他的直接索引。l層的節(jié)點(diǎn)是其中出現(xiàn)的單詞的祖先，以及與每個節(jié)點(diǎn)關(guān)聯(lián)的本地特征ftj列表。我們利用直接索引和單詞樹的均值來在BRIEF空間中大概的找到圖像的最近鄰。直接索引只計算屬于一個word或者在第l層有共同根節(jié)點(diǎn)的對應(yīng)點(diǎn)的特征來加速之間的幾何驗(yàn)證。當(dāng)一個新的圖像添加到數(shù)據(jù)庫直接索引更新,當(dāng)獲得了候選的匹配而且進(jìn)行了幾何驗(yàn)證，則可以存取直接索引。

閉環(huán)檢測算法

為了檢測到閉環(huán)，本文用了作者以前的工作[5][6],主要包含以下這四個過程：

A.數(shù)據(jù)庫查詢

我們利用圖像數(shù)據(jù)庫來存儲和檢索和給定的圖像相似的圖像，當(dāng)最新的圖像進(jìn)來了

B.Match Grouping（匹配分組）

C.時間一致性

當(dāng)獲得了最佳的匹配分組V_T'以后，我們檢測他和之前序列的時間一致性。在本篇論文中，作者利用[5]和[6]擴(kuò)展了時間一致性。(v_t,V_T')一定要和以前連續(xù)的k個分組得分連續(xù)，然后在V_T'分組中找到相似度得分最高的，然后把他看成一個候選幀，這個候選幀最后經(jīng)過幾何驗(yàn)證才可以被確定。

D.幾何一致性檢測

我們在兩個匹配的閉環(huán)候選幀用幾何檢測。這個檢驗(yàn)是通過它至少12個對應(yīng)點(diǎn)利用隨機(jī)樣本一致性(RANSAC)找到I_t和I_t'之間的一個基礎(chǔ)矩陣。為了計算這些對應(yīng)點(diǎn)，我們必須將序列圖像的局部特征與匹配圖像的局部特征進(jìn)行比較。有幾種方法來得到這種比較：

暴力搜索：通過比較I_t和I_t'之間特征的描述子之間的距離，根據(jù)最近鄰距離比例策略搜索對應(yīng)點(diǎn)。每個圖像的復(fù)雜度都是n^2

第二種技術(shù)是通過在k維(k-d)樹中排列描述符向量來計算近似最近鄰[7]

我們可以利用詞袋加速特征匹配。因此，在向數(shù)據(jù)庫添加圖像時，我們在直接索引中存儲節(jié)點(diǎn)和特征的列表。為了在I_t和I_t'獲得對應(yīng)點(diǎn)，直接查找I_t'幀的直接索引，僅對在詞袋中l(wèi)級的相同節(jié)點(diǎn)中的特征進(jìn)行比較。這個條件加快了特征匹配的計算速度。參數(shù)l是預(yù)先確定的，需要在It和It'之間獲得的特征點(diǎn)的數(shù)量和花費(fèi)的時間之間進(jìn)行權(quán)衡。當(dāng)l=0時，只比較屬于同一單詞的特征(正如我們在[12]中所表示的那樣)，這樣可以達(dá)到最高的加速，但是只能獲得很少的匹配點(diǎn)。這使得閉環(huán)檢測過程的召回減少，因?yàn)橐恍┱_的閉環(huán)由于缺乏對應(yīng)點(diǎn)而被舍棄。另一方面，當(dāng)l=Lw時，召回不受影響，但執(zhí)行時間也沒有提高（最后一層就和暴力匹配是一樣的）。我們只需要基本矩陣進(jìn)行驗(yàn)證，但注意，在計算之后，我們可以提供與下面運(yùn)行的任何SLAM算法匹配的圖像之間的數(shù)據(jù)關(guān)聯(lián)，而不需要額外的成本(有了F矩陣就可以解算RT了)。

參考文獻(xiàn)：

1.A comparison of loop closing techniques in monocular SLAM

2.FAB-MAP: Probabilistic localization and mapping in the space of appearance

3.Robust place recognition with stereo sequences

4.Fast and incremental method for loop-closure detection using bags of visual words

5.CI-graph SLAM for 3D reconstruction of large and complex environments using a multicamera system

6.Robust place recognition with stereo sequences

7.Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph

本文僅做學(xué)術(shù)分享，如有侵權(quán)，請聯(lián)系刪文。

3D視覺工坊-ORB-SLAM3源碼交流群

已建立3D視覺工坊-ORB-SLAM3源碼微信交流群！想要進(jìn)ORB-SLAM3源碼交流群的同學(xué)，可以直接加微信號：CV_LAB 。加的時候備注一下：研究方向+學(xué)校+昵稱，即可。然后就可以拉你進(jìn)群了。

強(qiáng)烈推薦大家關(guān)注「小凡」知乎和「3D視覺工坊」微信公眾號，可以快速了解到最新優(yōu)質(zhì)的3D視覺論文。