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

劉洋洋，魏國亮，管 啟，王 遠(yuǎn)

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

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

1 引 言

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

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

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

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

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

2 算法概述

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

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

3 圖像特征提取

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

3.1 全局特征提取

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

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

(1)

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

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

(2)

其中：

(3)

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

(4)

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

如圖2所示，為實(shí)現(xiàn)全局描述子的高魯棒性和高區(qū)分性，將圖像P劃分成4種不同大小的網(wǎng)格，網(wǎng)格大小分別是2×2、3×3、4×4和5×5.將大小為n×n網(wǎng)格上產(chǎn)生的二進(jì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)格會(huì)導(dǎo)致原始的LDB描述符某些位之間存在一定的相關(guān)性，造成一定程度的信息冗余.通過隨機(jī)選取描述符v中一定數(shù)量的二進(jìn)制位可以減少信息的冗余.所有被選擇的二進(jìn)制位構(gòu)成圖像的全局描述子，最終全局描述子的維數(shù)為D.全局特征由LDB全局描述子描述.

3.2 局部特征提取

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

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

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

(6)

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

(7)

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

(8)

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

4 基于增強(qiáng)LSH的全局搜索

當(dāng)輸入圖像提取全局特征Q后，便需在數(shù)據(jù)庫中進(jìn)行全局搜索查找與其相似的全局特征，數(shù)據(jù)庫中存放所有先前拍攝圖像的特征信息.全局搜索是在數(shù)據(jù)庫中逐一計(jì)算所有歷史圖像對(duì)應(yīng)的全局特征與Q的距離，如果存在全局特征Q1與Q的距離小于設(shè)定閾值，則認(rèn)為Q1對(duì)應(yīng)的幀為全局搜索的結(jié)果.但在大尺度場(chǎng)景中，隨著機(jī)器人經(jīng)過的位置增多，需要查詢的圖像信息也會(huì)增多，導(dǎo)致每一次全局搜索消耗的時(shí)間都在增加.針對(duì)全局搜索的這一缺點(diǎn)，本文采用基于漢明距離的增強(qiáng)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)表示取出二進(jìn)制向量v第i位上的值.從H中隨機(jī)的取k個(gè)h函數(shù)，將k個(gè)h函數(shù)組合形成最終的局部敏感哈希函數(shù)g：

g={h1，h2，…，hk}

(10)

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

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

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

(11)

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

4.2 多表多探針增強(qiáng)的LSH搜索

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

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

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

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

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

5 局部特征檢驗(yàn)

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

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

5.1 局部特征匹配

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

(12)

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

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

5.2 局部特征存儲(chǔ)

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

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

6 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

閉環(huán)檢測(cè)常用的性能評(píng)價(jià)指標(biāo)是準(zhǔn)確率和召回率，其計(jì)算公式如下：

(13)

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

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

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

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

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

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

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

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

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

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

圖6 LSH搜索與暴力搜索時(shí)間對(duì)比

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

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

6.5 與其他算法的比較

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

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

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

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

表2 4種算法準(zhǔn)確率為100%時(shí)對(duì)應(yīng)的召回率

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

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

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

7 結(jié) 語

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