一種基于全局-局部聯(lián)合二進制特征的快速閉環(huán)檢測算法

劉洋洋，魏國亮，管 啟，王 遠

1(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

2(上海理工大學(xué) 理學(xué)院，上海 200093)

1 引 言

實時定位與地圖構(gòu)建(Simultaneous Localization and Mapping，SLAM)是機器人在未知環(huán)境下自主導(dǎo)航的一個核心問題.近年來，隨著SLAM技術(shù)的發(fā)展，基于相機的視覺SLAM因為低廉的價格受到越來越多研究者的關(guān)注.基于視覺的閉環(huán)檢測是視覺SLAM的一個重要環(huán)節(jié)，主要通過圖像識別曾經(jīng)到過的場景.閉環(huán)檢測對減小系統(tǒng)產(chǎn)生的累計誤差，建立全局一致性地圖至關(guān)重要.

目前基于視覺的閉環(huán)檢測算法主要分為4類：1)基于視覺詞袋模型(Bag of Visual Word，BoVW)的閉環(huán)檢測方法.該方法比較經(jīng)典的工作為FAB-MAP[1].但是基于詞袋的方法只關(guān)注單詞本身忽略了單詞之間位置關(guān)系，因此容易出現(xiàn)一定程度的感知偏差[2]；2)基于局部特征的閉環(huán)檢測方法.近年來，出現(xiàn)了許多高效局部特征提取算法，推動了閉環(huán)檢測的發(fā)展，如SURF[3]，ORB[4]，BRISK[5]等；3)基于全局特征的閉環(huán)檢測方法.例如，Oliva等人提出的Gist全局特征[6]，Sunderhauf等人的BRIEF-Gist全局特征[7]；4)基于組合特征的閉環(huán)檢測算法.此方法將多種圖像特征進行組合，避免了單一圖像特征的局限性.這方面突出的工作是Wang等人提出的結(jié)合全局特征和局部特征的拓撲地圖定位算法[8]，其使用由粗到細的場景匹配策略.

不同于傳統(tǒng)的圖像特征提取方案，基于深度學(xué)習(xí)的圖像特征提取也是閉環(huán)檢測發(fā)展的重要方向，該特征對光照、遮擋和視角變化都有較強的魯棒性.使用該特征的閉環(huán)檢測對復(fù)雜環(huán)境擁有更好的適應(yīng)性，并且特征包含一定程度的語義信息[9].2015年Xia最先利用簡單的PCANet實現(xiàn)閉環(huán)檢測[10].隨后，Hou等人使用Place-CNN模型提取全局特征進行閉環(huán)檢測[11]，并對網(wǎng)絡(luò)不同層提取特征的表現(xiàn)了進行評估.2019年由Shan等人提出的FILD方案，該方案將利用MobileNetV2網(wǎng)絡(luò)模型得到的全局特征和SURF特征相結(jié)合，通過GPU加速實現(xiàn)高準確率實時閉環(huán)檢測[12]，是當前最好的閉環(huán)檢測算法.雖然基于深度學(xué)習(xí)閉環(huán)檢測算法有著不錯的性能，然而該方法非常依賴用于訓(xùn)練的場景數(shù)據(jù)，并且卷積神經(jīng)網(wǎng)絡(luò)的前向傳播過程往往需要GPU才能實時計算.在無人機等計算資源受限的微型機器人或小型化平臺上，采用深度學(xué)習(xí)的閉環(huán)檢測會占用大量系統(tǒng)資源，從而影響SLAM定位和建圖等主線程的實時性.

綜上所述，雖然基于外觀的閉環(huán)檢測取得了豐富的研究成果，但是目前并沒有一種性能優(yōu)異且能夠在計算資源受限的設(shè)備中部署SLAM閉環(huán)檢測方案.在Wang等人工作的基礎(chǔ)上，我們進一步優(yōu)化組合特征的提取和檢索方法，提出一種聯(lián)合二進制特征的快速閉環(huán)檢測算法.

本文的主要創(chuàng)新可歸納為：1)使用局部差異二值算子[13](Local Difference Binary，LDB)提取圖像的全局和局部二進制特征，縮短特征提取時間的同時，降低了圖像特征的存儲成本；2)保證搜索精度的前提下，通過基于漢明距離的增強局部敏感哈希算法[14](Locality Sensitive Hashing，LSH)加快了大尺度場景中全局特征檢索速度；3)使用二進制局部特征匹配檢查全局搜索的結(jié)果，這種層次式的匹配策略在提高系統(tǒng)效率的同時又可以保證檢測結(jié)果的高可靠性；4)優(yōu)化多種圖像特征存儲結(jié)構(gòu)的同時，通過索引機制加快數(shù)據(jù)庫中的特征信息訪問速度，降低了系統(tǒng)運行時的內(nèi)存占用.

2 算法概述

本文所提出的算法主要由3部分組成，其系統(tǒng)框架如圖1所示.第1部分為圖像特征提取模塊，該模塊將查詢圖像統(tǒng)一為固定大小的正方形.使用局部差異二值算子(LDB)分別提取正方形圖像的512維全局特征和以每個FAST關(guān)鍵點[15]為中心45×45大小區(qū)塊的256維局部特征描述子，根據(jù)圖像序號將全局特征和局部特征一起存儲到數(shù)據(jù)庫中.第2部分為全局特征搜索模塊，使用基于漢明距離的LSH進行全局搜索，然后通過搜索得到圖像索引查找數(shù)據(jù)庫中對應(yīng)全局特征V，計算V與當前圖像全局特征的距離，如果距離小于閾值則將其索引作為全局搜索的最終結(jié)果.第3部分為局部特征檢驗?zāi)K，根據(jù)全局搜索得到的索引找到數(shù)據(jù)庫中對應(yīng)的局部特征描述子，通過索引幀和候選幀之間的局部特征匹配驗證全局特征匹配的結(jié)果，如果正確匹配對數(shù)量超過閾值N則認為是正確的回環(huán)幀并將其作為最終輸出.

圖1 閉環(huán)檢測系統(tǒng)框架

3 圖像特征提取

為了完成閉環(huán)檢測任務(wù)，需要將圖像抽象為某種數(shù)字特征，用以描述該張圖片或圖片所表示的場景.按照描述對象的不同，提取的特征又可分為全局特征和局部特征.其中，全局特征是利用整幅圖像的紋理，顏色，形狀等信息生成高維的數(shù)字向量；局部特征是從圖像中具有代表性局部區(qū)域提取的信息，這種局部區(qū)域通常為角點，邊緣等.在本節(jié)中，將介紹如何利用LDB算子快速提取這兩種圖像特征.

3.1 全局特征提取

LDB算子最初由楊欣等人提出，作為一種局部特征描述子生成方法，其利用底層的灰度信息同時也提取了中層視覺中的梯度信息，這種多重信息的混合使用極大地提升了數(shù)字特征的區(qū)分能力，故本文將其作為全局特征描述子，以增強圖像的代表性.

在使用LDB算子計算全局描述子之前，為了方便圖像區(qū)塊劃分和后續(xù)計算，首先將輸入圖像統(tǒng)一為固定大小的正方形圖像塊P.然后將圖像P劃分成n×n個等尺寸的圖像塊，利用式(1)對網(wǎng)格中兩個不同的圖像塊提取信息.

(1)

其中，i和j表示網(wǎng)格中的第i和第j個圖像塊，F(xiàn)un(i)是從第i個區(qū)塊中提取信息的函數(shù).Fun(i)包含以下3種形式：

Fun(i)={FI(i)，F(xiàn)dx(i)，F(xiàn)dy(i)}

(2)

其中：

(3)

FI(i)表示提取第i個圖像塊的平均灰度，Gx(i)和Gy(i)分別表示圖像塊i中x和y方向上的梯度大小，m表示圖像塊i中像素的數(shù)量，平均灰度和圖像塊的梯度都可利用積分圖加速計算.由式(1)可知，執(zhí)行一次Bin函數(shù)會產(chǎn)生3個二進制位.當n×n網(wǎng)格中所有的圖像塊都經(jīng)過式(1)處理后，將產(chǎn)生的所有二進位拼接起來，組成一個維數(shù)為bn的二進制向量x，其中：

(4)

如果將x作為最終的圖像全局描述子，那圖像塊的尺寸會影響全局描述子的魯棒性和區(qū)分性.圖像被劃分成較大網(wǎng)格會產(chǎn)生更具魯棒性的全局描述子，從較小網(wǎng)格中提取的全局描述子會包含更多的細節(jié)信息，因此比從較大網(wǎng)格中提取的全局描述子更具區(qū)分性.

如圖2所示，為實現(xiàn)全局描述子的高魯棒性和高區(qū)分性，將圖像P劃分成4種不同大小的網(wǎng)格，網(wǎng)格大小分別是2×2、3×3、4×4和5×5.將大小為n×n網(wǎng)格上產(chǎn)生的二進制向量xn×n按照式(5)組合形成原始的LDB描述子v.

圖2 全局特征提取

v=x2×2++x3×3++x4×4++x5×5

(5)

其中++表示串聯(lián)操作，通過式(4)和式(5)可得到原始的LDB描述符v的維數(shù)為1386.劃分為不同大小網(wǎng)格會導(dǎo)致原始的LDB描述符某些位之間存在一定的相關(guān)性，造成一定程度的信息冗余.通過隨機選取描述符v中一定數(shù)量的二進制位可以減少信息的冗余.所有被選擇的二進制位構(gòu)成圖像的全局描述子，最終全局描述子的維數(shù)為D.全局特征由LDB全局描述子描述.

3.2 局部特征提取

不同于可以直接提取的圖像全局特征，局部特征的提取包括關(guān)鍵點檢測和描述子構(gòu)建兩個步驟.關(guān)鍵點檢測是找到所有像素點中對某種函數(shù)響應(yīng)值比較高的像素點，利用這些像素點標記圖像中的特殊區(qū)域.然后通過描述子構(gòu)建將關(guān)鍵點周圍的圖像塊信息轉(zhuǎn)換成數(shù)字特征.

在關(guān)鍵點檢測階段，本文使用增強FAST算法提取關(guān)鍵點.FAST是一種快速關(guān)鍵點檢測方法，該方法認為當一個像素與鄰域像素灰度值差別較大時，該像素就可能是關(guān)鍵點.增強FAST算法是FAST算法的改進，主要解決FAST檢測器不能檢測特征方向的問題.在特征描述階段，由3.1節(jié)可知LDB算子原本就是一種局部特征描述子生成方法，因此可直接生成關(guān)鍵點周圍區(qū)域的LDB描述子.使用LDB描述子描述局部特征一方面可提高局部特征的魯棒性和區(qū)分性，另一方面直接利用計算全局描述子時產(chǎn)生的積分圖像計算局部LDB描述子，積分圖的重復(fù)使用極大的加快了描述子的計算過程.

但實際中，機器人不能準確的回到原來經(jīng)過的位置，當前機器人位姿跟先前的位姿是不完全相同的，所拍攝的圖像會有一定程度的旋轉(zhuǎn)或扭曲，因此產(chǎn)生LDB描述子也與之前不同.為實現(xiàn)局部LDB描述子的旋轉(zhuǎn)不變性，需估計FAST關(guān)鍵點的主方向.我們通過灰度質(zhì)心法[16]估計特征點主方向，該方法先通過圖像塊的矩計算特征點鄰域的質(zhì)心，圖像塊的矩定義為：

(6)

在式(6)中，I(x，y)表示位于圖像(x，y)處的像素灰度值.然后通過一階矩得到該區(qū)域的質(zhì)心C的坐標為：

(7)

最后，將關(guān)鍵點坐標和質(zhì)心組成一個向量，將向量的角度θ作為該關(guān)鍵點的主方向：

(8)

得到關(guān)鍵點的主方向后，利用關(guān)鍵點主方向旋轉(zhuǎn)特征點為中心45×45大小積分圖像.在旋轉(zhuǎn)后的積分圖像上利用式(1)生成原始LDB描述子.類似于全局描述子的生成過程，為了避免某些位之間的相干性并限制描述子的維數(shù)，在原始LDB描述子上隨機選擇256個二進制位組成最終的LDB描述子.

4 基于增強LSH的全局搜索

當輸入圖像提取全局特征Q后，便需在數(shù)據(jù)庫中進行全局搜索查找與其相似的全局特征，數(shù)據(jù)庫中存放所有先前拍攝圖像的特征信息.全局搜索是在數(shù)據(jù)庫中逐一計算所有歷史圖像對應(yīng)的全局特征與Q的距離，如果存在全局特征Q1與Q的距離小于設(shè)定閾值，則認為Q1對應(yīng)的幀為全局搜索的結(jié)果.但在大尺度場景中，隨著機器人經(jīng)過的位置增多，需要查詢的圖像信息也會增多，導(dǎo)致每一次全局搜索消耗的時間都在增加.針對全局搜索的這一缺點，本文采用基于漢明距離的增強LSH算法加速搜索.

4.1 LSH搜索

LSH是一種被廣泛使用的最近鄰搜索(Approximate Nearest Neighbor，ANN)算法.該算法的核心是找到一種局部敏感的哈希函數(shù)，使外觀空間中相鄰的高維矢量通過哈希函數(shù)后更有可能產(chǎn)生相同的值.不同的局部敏感哈希函數(shù)用于不同的距離度量，例如范數(shù)距離、余弦距離、漢明距離等.由于全局特征是高維二值向量，因此本文采用基于漢明距離的局部敏感哈希函數(shù)，該函數(shù)定義如下：

給定函數(shù)簇：

H={h|hi(v)}

(9)

其中hi(v)表示取出二進制向量v第i位上的值.從H中隨機的取k個h函數(shù)，將k個h函數(shù)組合形成最終的局部敏感哈希函數(shù)g：

g={h1，h2，…，hk}

(10)

函數(shù)g產(chǎn)生的哈希值也稱為哈希桶，k的大小即為哈希值的維數(shù)，每個g函數(shù)都能生成2k個哈希桶，每個哈希桶中包含具有相同子位的全局特征，所有哈希桶組成一個哈希表.

與基于暴力查找的全局搜索不同，當查詢Q的最近鄰時，基于LSH全局搜索首先查找Q對應(yīng)的哈希桶，并逐一檢查該哈希桶中的其他已經(jīng)存在的全局特征與Q之間的漢明距離.如果距離低于設(shè)定的閾值t則將該全局特征對應(yīng)的幀作為結(jié)果輸出.其中，兩個全局特征D1和D2之間的漢明距離如下：

‖D1-D2‖H=bitsum(D1⊕D2)

(11)

式(11)中⊕為二進制的異或操作，bitsum為統(tǒng)計向量中的非0位的個數(shù).

4.2 多表多探針增強的LSH搜索

由于全局特征和哈希函數(shù)的生成具有一定的隨機性，降低了LSH算法找到當前全局特征最近鄰的概率.提高最近鄰檢索精度除了減小哈希值維數(shù)增加每個桶的容量外，還可以通過多表和多探針技術(shù)[17]增強LSH搜索.

多表技術(shù)是將一個全局特征經(jīng)過l個不同的g函數(shù)處理，將產(chǎn)生的l個哈希值分別存入l個哈希表中.查詢時，將查詢特征所屬不同表中的l個桶內(nèi)的全局特征組成一個集合.只需在集合中查找查詢?nèi)痔卣鞯淖罱?，無需搜索整個數(shù)據(jù)庫.多表技術(shù)以犧牲一定內(nèi)存和查詢時間為代價，提高全局特征搜索精度.

針對多表技術(shù)內(nèi)存占用大和查詢時間長等缺點，我們將存儲桶中存放的全局特征替換全局特征對應(yīng)輸入圖像的序號，該序號也是全局特征在數(shù)據(jù)庫的位置索引.查詢時，通過存儲桶中索引查找數(shù)據(jù)庫中對應(yīng)位置的全局特征，將符合閾值條件的全局特征所屬的索引值輸出.這種索引機制降低哈希表的內(nèi)存占用并提高了數(shù)據(jù)庫的查詢速度.因此，即使創(chuàng)建多個哈希表，系統(tǒng)的搜索時間和占用內(nèi)存空間都沒有大幅增加.

多探針技術(shù)則通過檢查全局特征所在的桶和相鄰的桶，以提高搜索最近鄰的概率.多探針層級(Multi Probe Level，MPL)為0時表示只檢查全局特征所在的桶，MPL為1表示也檢查哈希值存在1位差異的相鄰?fù)?，以此類?多探針技術(shù)能夠在不增加哈希表個數(shù)的前提下搜索更多的圖像信息.在本文實驗中MPL都設(shè)置為1.

本節(jié)引入LSH算法一方面能夠與3.1節(jié)產(chǎn)生二進制全局特征高度結(jié)合，避免外觀空間轉(zhuǎn)換造成的信息丟失，提高了檢索精度和速度.另一個方面與傳統(tǒng)暴力搜索相比，該方法能夠最大限度的保證搜索精度，減少內(nèi)存占用的同時提高檢索速度.

5 局部特征檢驗

雖然多表和多探針技術(shù)能夠在一定程度上提高LSH搜索最近鄰的精度，但并不能確保檢測結(jié)果是100%的正確的.如果將全局搜索結(jié)果直接作為閉環(huán)檢測的輸出，可能會導(dǎo)致錯誤的判斷，對整個機器人SLAM系統(tǒng)產(chǎn)生不可估量的影響.為保證閉環(huán)檢測結(jié)果的高可靠性，本文加入局部特征檢驗環(huán)節(jié)對全局搜索的結(jié)果進行檢查.

局部特征檢驗環(huán)節(jié)主要通過使用局部特征匹配的方式對全局搜索結(jié)果進行檢查.局部特征匹配與全局特征匹配不同，其包含了更多的細節(jié)信息，能夠在圖像視角、光照條件變化或存在局部遮擋時匹配到正確的對應(yīng)圖像，但大量圖像進行局部特征匹配會占用系統(tǒng)有限的計算資源.為了平衡閉環(huán)檢測的時間和準確性，將全局搜索輸出作為檢驗?zāi)K的輸入，這種聯(lián)合全局特征和局部特征的層次式的匹配策略不僅提高檢測效率還保證了結(jié)果的高可靠性.

5.1 局部特征匹配

在3.2節(jié)中用增強的FAST算法檢測關(guān)鍵點后，為控制局部特征的數(shù)量并降低不穩(wěn)定特征對系統(tǒng)的影響，利用關(guān)鍵點的Harris響應(yīng)值進行非極大值抑制，篩選100個關(guān)鍵點并計算其LDB描述子，隨后將全局描述子和100個局部描述子一起存放到數(shù)據(jù)庫中對應(yīng)的索引位置中.當全局搜索得到候選幀的索引后，通過索引查找數(shù)據(jù)庫中相應(yīng)的局部特征描述子并與當前幀的局部特征描述子進行暴力匹配.在匹配的過程中，當前幀中一個描述子的最近鄰和次近鄰滿足式(12)時則認為是一個正確的匹配[3].

(12)

其中，fc表示當前幀中一個描述子，fA和fA1是候選幀中的描述子，fA是fc的最近鄰，fA1是fc的次最近鄰.較低的比值意味著最佳匹配比其最佳競爭者表現(xiàn)得更好，可能是正確的匹配.當特征在外觀空間中聚集更緊密時，距離比值更大，特征相對于彼此不夠獨特，為了避免誤匹配刪除當前這對匹配.

兩幅圖像認為是正確回環(huán)則至少存在N個正確匹配對.局部特征匹配是對全局搜索結(jié)果的再檢查，局部特征匹配應(yīng)盡可能保證全局搜索結(jié)果的準確性.如果全局搜索的得到的候選幀與當前幀的匹配數(shù)都小于N，則清除所有候選幀.

5.2 局部特征存儲

使用局部特征匹配時，局部特征會占用機器人的大量存儲空間.與Wang方案中使用的SIFT[8]描述子相比，LDB描述子優(yōu)勢更為突出，因為二進制描述子不僅提取速度快、占用存儲空間少而且易存易取.例如，存儲一幀圖像100個SIFT描述子至少需要12kB的存儲空間，而一幀圖像100個LDB描述子僅需要3kB的空間.存儲10000張圖像每張圖像100個LDB描述子僅需30M的存儲空間.

全局描述子與局部特征描述子一起存放到存儲器中，通過數(shù)據(jù)庫中的索引(圖像序號)快速查找相應(yīng)的局部特征描述子.通過索引將全局特征和局部特征關(guān)聯(lián)，提升數(shù)據(jù)庫的讀取和存儲效率，降低數(shù)據(jù)庫的復(fù)雜性.這種整體式的存儲方式使得機器人可加載存儲器中先前運動軌跡中的圖像特征，或者可以加載其他搭載該算法機器人產(chǎn)生的圖像特征，實現(xiàn)大尺度場景和多軌跡的閉環(huán)檢測，提高了機器人的閉環(huán)檢測能力.

6 實驗與結(jié)果分析

在本節(jié)中，首先介紹實驗環(huán)境和算法中的關(guān)鍵參數(shù).然后，設(shè)計多個實驗，實驗由簡單到復(fù)雜，根據(jù)實驗結(jié)果確定算法中的關(guān)鍵參數(shù).最后將本文所提出的算法與Wang的算法、FAB-MAP、FILD等進行對比分析.

6.1 實驗環(huán)境和關(guān)鍵參數(shù)說明

本文實驗所用計算機硬件配置為：CPU為i5-1035G1處理器，主頻1GHz，內(nèi)存8G.FILD算法使用Nvidia GTX1070顯卡進行計算，除此之外其余實驗均使用CPU單核單線程計算.

實驗測試使用City_Center和New_College數(shù)據(jù)集[1]，由牛津大學(xué)Mark Cummins等人采集.該數(shù)據(jù)集主要用于閉環(huán)檢測模塊的測試和評估.兩個數(shù)據(jù)集分別包含2146張，2474張雙目圖像.圖像為640×480大小的三通道彩色圖，此外，數(shù)據(jù)集提供真實閉環(huán)信息.兩個數(shù)據(jù)集中部分圖像如圖3上半部分所示，運動軌跡如圖3下半部分所示，在實驗中只使用左側(cè)相機圖像.

圖3 City_Center和New_College數(shù)據(jù)集部分圖像及機器人運動軌跡

閉環(huán)檢測常用的性能評價指標是準確率和召回率，其計算公式如下：

(13)

其中TP表示檢測結(jié)果中正確的閉環(huán)個數(shù)，F(xiàn)P表示檢測結(jié)果中錯誤的閉環(huán)數(shù)目，F(xiàn)N表示未被檢測出的真實閉環(huán)數(shù)目.TP+FP表示檢測到的所有輸出結(jié)果，TP+FN表示數(shù)據(jù)集中真實閉環(huán)的個數(shù).一般用準確率--召回率曲線(簡稱P-R曲線)反映閉環(huán)檢測算法的綜合性能[18].通過改變算法中全局搜索的距離閾值t產(chǎn)生不同的準確率和召回率進而繪制P-R曲線.雖然大多數(shù)系統(tǒng)將準確率作為優(yōu)化指標，但是一個好的閉環(huán)算法能夠在保證準確率的同時擁有很高的召回率.

本文提出算法中的關(guān)鍵參數(shù)如表1所示.

表1 提出算法中的一些關(guān)鍵參數(shù)

6.2 全局特征維數(shù)設(shè)置

全局特征的表示和檢索是整個系統(tǒng)的核心，而全局特征維數(shù)又是全局特征表示的關(guān)鍵.全局特征維數(shù)越高包含的信息越多，區(qū)分性越強，需要的存儲空間越多.而全局特征維數(shù)越小信息越少，區(qū)分性變?nèi)酰枰拇鎯臻g變小.通過全局特征加暴力搜索即可組成最簡單的閉環(huán)檢測系統(tǒng).在New_College和City_Center數(shù)據(jù)集上對這種最簡單的閉環(huán)檢測系統(tǒng)進行測試.根據(jù)以上實驗確定本文提出算法中全局特征的維數(shù).全局特征分別選取256、512、1024維進行比較.如圖4所示，1024維特征和512維特征擁有相同的性能，但512維特征需要的存儲空間更少，所以后續(xù)實驗使用LDB產(chǎn)生512維的全局特征.

圖4 不同維數(shù)的全局特征對應(yīng)的P-R曲線

6.3 LSH參數(shù)選擇和搜索性能分析

影響LSH搜索精度的兩個主要因素是哈希值維數(shù)K和哈希表個數(shù)T.在最小閉環(huán)檢測系統(tǒng)基礎(chǔ)上，將暴力搜索替換為LSH搜索，選擇多種哈希表數(shù)和哈希值維數(shù)組合進行測試.最終當哈希表個數(shù)為10，哈希值維數(shù)為11時，LSH搜索可以達到與暴力搜索接近的性能，如圖5所示.

圖5 暴力搜索和LSH搜索P-R曲線

在保證搜索精度的基礎(chǔ)上，為驗證LSH算法能夠加快全局特征的搜索，在網(wǎng)絡(luò)上隨機選取10700圖像組成圖像檢索數(shù)據(jù)集，并使用該數(shù)據(jù)集進行測試.圖6為使用該數(shù)據(jù)集實驗過程中全局特征搜索用時變化情況，其中LSH搜索使用10個哈希表，哈希值維數(shù)為11.LSH搜索時間不再隨數(shù)據(jù)庫的增加而快速增加.當數(shù)據(jù)庫小于4000幀圖像時暴力搜索更有效率，但數(shù)據(jù)庫超過4000幀后LSH搜索效率將超過暴力搜索.圖6中LSH搜索P-R曲線未起始于0點，是由于從全局特征提取相應(yīng)的哈希值和建立哈希表并進行存儲需花費一定時間.

圖6 LSH搜索與暴力搜索時間對比

6.4 局部特征匹配對數(shù)選擇

全局搜索的輸出是局部特征檢驗?zāi)K的輸入.為了控制局部特征匹配時間，全局搜索輸出最相似的前4幀圖像索引，作為局部特征匹配的輸入.因為沒有全局特征距離閾值檢查，即使該幀不存在閉環(huán)也會出現(xiàn)相應(yīng)的候選幀，這是局部特征檢驗?zāi)K能夠遇到的最困難的情況.這種包含大量錯誤的全局搜索結(jié)果，要求局部特征檢驗?zāi)K能夠找出所有錯誤候選幀.為了尋找最優(yōu)的匹配對數(shù)N，將匹配對數(shù)N從1開始計算相應(yīng)的召回率和準確率.選擇準確率為100%時召回率最高的點作為其匹配對數(shù).在New_College和City_Center數(shù)據(jù)集分別進行測試，在兩個數(shù)據(jù)集上最優(yōu)選擇匹配對數(shù)分別是8 和11.匹配對數(shù)應(yīng)至少是8個，8個匹配對也是能通過RANSAC[19]迭代估計的基本矩陣恢復(fù)出相對位姿的最少的匹配對數(shù).

6.5 與其他算法的比較

根據(jù)上述實驗得到本文所提出算法關(guān)鍵參數(shù)，LDB生成512維的全局特征，LSH搜索使用10個哈希表、哈希值維數(shù)為11進行搜索，全局搜索輸出滿足閾值t的最相似的前4幀圖像索引輸入到局部特征檢驗環(huán)節(jié)，局部特征匹配對數(shù)N由6.4節(jié)選定.因為OACH未公開源碼，采用文獻[8]中的給出相關(guān)配置實現(xiàn)其算法.FILD和FAB-MAP算法采用其開源代碼中的默認參數(shù)進行試驗.

圖7給出了本文算法和Wang提出方案在New_College和City_Center數(shù)據(jù)集的P-R曲線.因為加入嚴格的局部特征檢驗?zāi)K，該模塊會刪除全局搜索結(jié)果中的絕大多數(shù)誤檢測，使輸出結(jié)果的準確率達到100%.當全局搜索輸出滿足閾值且最相似的前4幀數(shù)據(jù)時，由于全局特征區(qū)分性有限，使得真正的閉環(huán)圖像不在輸出前4個結(jié)果中，因而召回率達到一定程度后就不會再繼續(xù)增加，所以采用局部特征驗證后P-R曲線呈現(xiàn)一條近似的直線段.由圖7可知本文算法性能與Wang等人提出的方案接近.

圖7 兩種算法的P-R曲線比較

相比于P-R曲線，閉環(huán)檢測更關(guān)注于準確率100%時召回率的大小.如表2所示，我們將本文算法與Wang等人提出的算法，F(xiàn)AB-MAP、FILD算法進行比較.FAB-MAP算法在New_College數(shù)據(jù)集中得到47%的召回率是通過非常復(fù)雜的方法得到的，完成一次檢測至少需要3s.而最新的基于深度學(xué)習(xí)的FILD算法在City_Center數(shù)據(jù)集中達到了相對較高的召回率，這是由于大多數(shù)傳統(tǒng)的圖像特征無法更好的應(yīng)對CityCenter數(shù)據(jù)集中劇烈視角和光照變化.

表2 4種算法準確率為100%時對應(yīng)的召回率

時間方面，如表3所示，使用New_College數(shù)據(jù)集的1074張圖像統(tǒng)計了3種基于組合特征的閉環(huán)檢測算法各個環(huán)節(jié)的平均用時.Wang的算法中多尺度Harris[20]關(guān)鍵點與OACH全局特征是一起計算的，局部特征只需計算關(guān)鍵點對應(yīng)的SIFT描述子即可，因而局部特征提取時間較短.由于FILD算法的CNN全局特征和局部特征(SURF)無法在CPU上實現(xiàn)實時特征提取，因此必需使用GPU進行加速，即使如此整個算法完成一次閉環(huán)檢測仍然需要50ms.由表3可知，在保證一定召回率的基礎(chǔ)上，本文提出的算法是速度最快的.此外，本文使用了增強的LSH搜索，使全局搜索用時恒定，不會隨數(shù)據(jù)庫容量的增加而增加.當數(shù)據(jù)庫中存儲10000張圖像信息時，Wang的方案中完成一次全局特征搜索時間長達30ms，而本文所提出的算法最多只需1ms.

表3 3種算法各環(huán)節(jié)平均用時(ms)

基于上述實驗結(jié)果可，本文提出的算法與Wang等人提出的方案相近，速度上優(yōu)于大多數(shù)閉環(huán)檢測算法，另外，我們的算法實現(xiàn)簡單，更容易在計算資源有限的設(shè)備中部署.

7 結(jié) 語

本文提出一種基于全局-局部聯(lián)合二進制特征的快速閉環(huán)檢測算法，該算法旨在保證閉環(huán)檢測準確率的前提下進一步提高檢測的速度.該方案使用聯(lián)合的二進制特征加速場景匹配，實現(xiàn)簡單且占用計算資源少.該算法分為3大部分，首先，使用局部差異二值算子生成全局特征和局部特征.然后，通過局部敏感哈希加速全局特征搜索.最后，利用局部特征對全局搜索的結(jié)果進行匹配檢查確定真正的閉環(huán)幀.實驗表明，在單核單線程無GPU加速的情況下，本文提出的算法能夠保證閉環(huán)檢測的高準確性和高實時性.接下來的工作是進一步優(yōu)化圖像特征的存儲結(jié)構(gòu)，并增強算法對視角和光照變化的魯棒性.