在ORB-SLAM和Kintinuous中都使用到了一種閉環(huán)檢測算法DBoW2，下面結合論文對該算法做詳細介紹益兄。
DBow2算法主要用于重定位或者稱作閉環(huán)檢測弓柱，英文叫l(wèi)oop closure或者place recognition。DBoW2算法中使用的特征點是ORB特征痊乾，這是一種結合了FAST特征和BRIEF描述子的特征（值得注意的是ORB-SLAM中使用的是ORB結合DBoW2回環(huán)檢測喘批，Kintinuous使用的是SURF特征結合DBoW回環(huán)檢測）撩荣。作者將特征點的描述子（description）空間離散化，構建了詞樹（vocabulary tree）饶深。然后用這種樹為幾何驗證（geometric verification）階段快速尋找點的對應餐曹。
本文下面將分為三個部分對該算法進行介紹：
1.二值特征（binary feature）
ORB特征是一種結合了FAST特征和BRIEF描述的一種特征，F(xiàn)AST關鍵點是一種角點敌厘，它通過在一個半徑為3的Bresenham圓中比較一些像素的灰度來獲得台猴，然后在每一個FAST特征點的周圍都選取一個方形的patch計算BRIEF描述子。BRIEF描述子是用一個二值向量來表示的俱两，向量中的每一位都是patch中灰度值進行比較的結果饱狂，patch大小和向量的長度都是事先給定好的，可以根據實際需要選擇合適的值宪彩。
上圖中的Lb表示向量的長度休讳，ai和bi表示在patch中隨機選取的兩個坐標，這兩個坐標的選取是服從正態(tài)分布的尿孔。
使用BRIEF描述子最主要的優(yōu)勢是由于它的描述子是二值的俊柔，因此可以利用異或（xor）快速計算和比較。
2.圖像數(shù)據的建立（image database）
image database由一個多級的詞包（hierarchical bag of words）（實際上是一棵詞樹vocabulary tree）以及直接索引（direct index）和逆向索引（inverse index）構成活合。下面上圖：
bag-of-words使用視覺詞表（visual vocabulary）將圖像轉化為一個稀疏的數(shù)值向量倔丈，visual vocabulary可以離線生成，將訓練集圖像（training）的描述空間（descriptor space）離散成W個視覺詞匯（visual words）状蜗。
建立這個vocabulary tree可以分為三步：
- 從訓練圖像中離線提取desciptor
- 對提取到的descriptors進行聚類需五，聚類方法是k-means生成種子后的k-medians聚類，得到了vocabulary tree的第一層轧坎，共k個節(jié)點
- 接下來的每一層都進行與第一步相同的操作宏邮，最終得到W個葉節(jié)點。
每一個word都會根據其在訓練集中的關聯(lián)性得到一個權重值缸血。但是那些出現(xiàn)頻率非常高的words蜜氨，顯然它們的辨識度很低，因此會相應降低它們的權重捎泻。加權方法使用的是tf-idf（term frequency - inverse document frequency）飒炎。
順便說一下這tf-idf，這是一種標準的計算權重的方法笆豁，它的計算方法為
t = (word在當前文檔出現(xiàn)的次數(shù)/當前文檔的總詞數(shù))*log(整個數(shù)據集中的文檔數(shù)/數(shù)據集中出現(xiàn)該word的文檔數(shù))郎汪。應用在視覺領域中，將文檔換成圖像即可闯狱。
每一幅圖像都被轉換成一個詞包向量v（bag-of-words vector）煞赢，其特征點的描述子被從根節(jié)點到葉節(jié)點以最小化Hamming距離的方式傳遞下去。
兩個bag-of-words相似性可以用score來表示哄孤，score的計算方式如下圖：
伴隨著bag-of-words照筑，還會維持一個inverse index，它為每一個word存儲一個圖像列表录豺，表明它都在哪些圖像中出現(xiàn)過朦肘。這方便了我們對image database的訪問，只比較那些有相同word的圖像即可双饥。除此之外媒抠，這篇文章還使用了direct index，它為每一幅圖像的特征都存儲了與該特征相關聯(lián)的第l層的節(jié)點（l的值預先給出）咏花。這會為后面的geometric verification帶來好處趴生。
3.閉環(huán)檢測算法
A.Database的訪問
根據上文的相似度score，計算出一個歸一化相似度score昏翰。
從式中可以看出苍匆，使用當前幀與前一幀的相似度作為期望score，當兩幀之間的相似度非常小的時候棚菊，會錯誤地得到一個很高的值浸踩。為了排除這種影響，作者為其設置了閾值统求，也就是說當前后兩幀相差很大時不做回環(huán)檢測检碗。
B.群組匹配（match grouping）
為了避免短時間內的多幀圖像訪問database据块，要將一定時間間隔的圖像劃為一組（island），將當前幀圖像與這組圖像相似度的和作為群組相似度折剃，選擇相似度最高的組作為匹配另假，然后進行后續(xù)的暫時一致性驗證（temporal consistency）。
這樣的island也有助于正確的匹配怕犁，因為一旦當前幀與某一幀形成閉環(huán)边篮，那么必然與其前后幀都有很高的相似度，這樣就會形成一個很長的island奏甫，群組相似度也會有助于匹配長island戈轿。
C.暫時一致性（Temporal consistency）
如果某幀圖像匹配到了一個組，那么一定和這個組前k個組相似度也很高阵子，因為這k+1個組是相互覆蓋的凶杖。
D.幾何驗證（geometric verification）
驗證幾何一致性的關鍵在于利用RANSAC，通過在兩幀圖像上的12個點對應款筑，找到一個基本矩陣智蝠。
建立點對應就需要尋找特征點的最近鄰點，這時候就需要用到我們前面提到的direct index奈梳。要查找圖像上的一個特征點杈湾，只需要在l層上該特征點所對應節(jié)點上尋找即可。l的值需要預先設定攘须，l值設為零漆撞，那么就只能去葉節(jié)點找，找到的對應點很少于宙。如果l值設置為根節(jié)點浮驳，相當于在所有節(jié)點中尋找，沒有做任何優(yōu)化捞魁。
以上就是DBoW2算法的全部內容至会。
持續(xù)更新，歡迎提出質疑或與作者就相關問題進行討論谱俭。
參考文獻：
Bags of Binary Words for Fast Place Recognition in Image Sequences
