加入特征空間信息的視覺(jué)SLAM閉環(huán)檢測(cè)改進(jìn)方法

羅升斯 黎展榮

【摘 要】針對(duì)移動(dòng)機(jī)器人同步定位與地圖構(gòu)建（SLAM）的閉環(huán)檢測(cè)問(wèn)題，提出改進(jìn)閉環(huán)檢測(cè)準(zhǔn)確率的特征空間全排列向量匹配方法。使用ORB（Oriented FAST and Rotated BRIEF）方法提取圖像特征點(diǎn)，創(chuàng)建基于視覺(jué)字典樹的詞袋，初步篩選出候選閉環(huán)圖像。將圖像分成4塊大小均勻的區(qū)域，計(jì)算各區(qū)域視覺(jué)單詞向量并全排列，作為特征空間信息。比較特征空間信息方法和詞袋方法計(jì)算出的圖像間距離值，選取最小值對(duì)應(yīng)的圖像對(duì)作為最佳閉環(huán)。相比詞袋方法，特征空間信息方法可有效地改善圖像特征匹配的感知混淆問(wèn)題，在保證較高效率的同時(shí)，提高了閉環(huán)檢測(cè)的準(zhǔn)確率。

【關(guān)鍵詞】閉環(huán)檢測(cè)；視覺(jué)字典樹；詞袋；特征空間全排列信息

【中圖分類號(hào)】TP242 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-0688（2018）02-0118-04

SLAM（同步定位與地圖構(gòu)建）指自主移動(dòng)機(jī)器人根據(jù)環(huán)境構(gòu)建地圖并確定自身姿態(tài)和位置。相機(jī)能獲得廣泛優(yōu)質(zhì)的信息（分辨率足夠高、圖像顏色豐富等），而 且輕便、價(jià)格低，基于相機(jī)的視覺(jué)SLAM方法成為近十年來(lái)的研究熱點(diǎn)[1]。閉環(huán)檢測(cè)是視覺(jué)SLAM的一項(xiàng)重要過(guò)程，指判斷自主移動(dòng)機(jī)器人是否回到曾經(jīng)到達(dá)過(guò)的地點(diǎn)，它是減少機(jī)器人位姿累積誤差和地圖不確定性的關(guān)鍵步驟。閉環(huán)檢測(cè)有3種方式[2]：map to map、image to image、map to image，實(shí)際常采用image to image方式，即序列圖像匹配方法。

詞袋（Bag of Words，簡(jiǎn)稱BoW）[3]作為主流的圖像相似性匹配方法，被廣泛利用和改進(jìn)優(yōu)化。Josef Sivi[4]等人使用BoW，結(jié)合文本檢索中的TF-IDF（term frequency–inverse document frequency）模式分配視覺(jué)單詞權(quán)重，并加入停止詞，識(shí)別視頻圖片中的相似物體，提高了特征查詢的速度。David Nister[5]等人提出將BoW的視覺(jué)單詞作為構(gòu)建樹結(jié)構(gòu)的節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)個(gè)數(shù)為n，它的查找時(shí)間復(fù)雜度為O（log n），與時(shí)間復(fù)雜度為O（n2）的蠻力搜索方法相比，大大地提高了特征搜索的效率。Dorian Galvez-López[6]等人使用二進(jìn)制描述子BRIEF（Binary Robust Independent Elementary Features，二進(jìn)制魯棒的獨(dú)立基本特征）替換常用的SIFT（Distinctive Image Features from Scale-Invariant Keypoints，尺度不變關(guān)鍵點(diǎn)的獨(dú)特圖像特征）或SURF（Speeded-Up Robust Features，加速穩(wěn)健特征），提高了特征匹配速度，并節(jié)省了特征占用空間。但上述方法均忽略了特征的空間聯(lián)系，存在較大的投影量化誤差，造成感知歧義，即相同單詞投影到不同區(qū)域，不同單詞卻投影到相同區(qū)域。邊緣單詞發(fā)生此種情況的概率更大。

為提升圖像匹配的準(zhǔn)確率，開展了對(duì)BoW方法視覺(jué)單詞添加空間信息的研究。Nishant Kejriwal[7]等人用128維的SURF描述子表示圖像特征，在使用視覺(jué)字典樹結(jié)構(gòu)的BoW模型基礎(chǔ)上加入不同特征點(diǎn)，同時(shí)出現(xiàn)和空間鄰近關(guān)系的信息，然后用貝葉斯概率方法計(jì)算閉環(huán)。該方法應(yīng)用在閉環(huán)檢測(cè)中，取得了比傳統(tǒng)BoW方法更高的準(zhǔn)確率，但同時(shí)增加了較大時(shí)間復(fù)雜度。Svetlana Lazebnik[8]等人提出將圖像分為金字塔的多個(gè)層級(jí)，每層劃分不同大小的區(qū)域，分別統(tǒng)計(jì)并量化各層區(qū)域特征，然后通過(guò)特征向量相似度來(lái)確定匹配圖像，提升了圖像匹配準(zhǔn)確率。李博[9]等人提出帶TF-IDF權(quán)重的視覺(jué)字典樹和改進(jìn)的金字塔的分匹配模型，從視覺(jué)字典樹的下層往上層計(jì)算節(jié)點(diǎn)相似性增量匹配核函數(shù)，通過(guò)結(jié)合不同層次單詞的關(guān)聯(lián)性，降低投影量化歧義性。該方法改善BoW的視覺(jué)單詞本受單詞數(shù)目限制導(dǎo)致性能不佳的不足，提升了檢索效率并減小了匹配誤差。因圖像拍攝視角差異等原因，所以上述針對(duì)視覺(jué)單詞空間關(guān)系的改進(jìn)方法魯棒性不高，同時(shí)會(huì)明顯地增加比較特征空間關(guān)系的時(shí)間開銷。

本文將用于圖像相似性匹配的BoW方法作為改進(jìn)對(duì)象，加入均勻劃分4個(gè)區(qū)域的特征空間信息，通過(guò)比較全排列特征空間向量，提高閉環(huán)檢測(cè)的準(zhǔn)確率，且保證較高的效率。

1 系統(tǒng)總體結(jié)構(gòu)

本文對(duì)視覺(jué)SLAM的閉環(huán)檢測(cè)處理主要分為3個(gè)過(guò)程：提取圖像特征點(diǎn)、創(chuàng)建BoW模型、使用全排列特征空間信息檢測(cè)確認(rèn)閉環(huán)。具體流程為首先利用ORB方法提取圖像特征點(diǎn)，以此創(chuàng)建BoW，通過(guò)視覺(jué)字典樹結(jié)構(gòu)表示BoW，然后計(jì)算比較圖像庫(kù)圖像（機(jī)器人曾走過(guò)區(qū)域獲取到的圖像集合）和查詢圖像間向量的相似度。其次將相似度較大（即相似距離較?。┑膱D像庫(kù)圖像作為候選圖像，計(jì)算和比較它們及查詢圖像特征空間全排列向量的距離，選取距離最小值對(duì)應(yīng)的圖像對(duì)作為閉環(huán)。本文所設(shè)計(jì)的閉環(huán)檢測(cè)過(guò)程如圖1所示。

2 基于BoW模型的閉環(huán)檢測(cè)方法

2.1 ORB特征提取方法

特征提取是物體識(shí)別、圖像檢索等常見(jiàn)應(yīng)用的前提步驟，并為BoW的創(chuàng)建提供特征點(diǎn)。SIFT[10]特征具有平移、旋轉(zhuǎn)、縮放等不變性，是較魯棒的方法。然而該特征提取方法效率較低，不能較好地滿足SLAM的實(shí)時(shí)性要求。折中于速率和穩(wěn)定性的ORB[11]方法，是SLAM特征提取的較好選擇。ORB分為特征點(diǎn)檢測(cè)FAST（Features from Accelerated Segment Test，加速分段測(cè)試的特征）方法和改進(jìn)的特征點(diǎn)描述BRIEF方法的兩步處理過(guò)程。如圖2所示，用FAST方法比較被檢測(cè)像素點(diǎn)和以其為圓心的圓上16個(gè)像素點(diǎn)的灰度差值，如果有至少連續(xù)12個(gè)像素點(diǎn)與中心點(diǎn)的灰度差值同時(shí)小于閾值或者同時(shí)大于閾值，則被檢測(cè)的像素點(diǎn)為特征點(diǎn)，否則不是特征點(diǎn)。該方法簡(jiǎn)單可行，效率較高。

BRIEF的基本思想是將特征點(diǎn)周圍滿足某一特定分布規(guī)律像素點(diǎn)對(duì)的灰度值一一比較：大于關(guān)系用1表示，小于關(guān)系用0表示。將比較結(jié)果有序組成一串由0、1表示的向量，即得到特征描述子，它由二進(jìn)制數(shù)字組成，節(jié)省了特征存儲(chǔ)空間，使用位異或運(yùn)算符可提升特征間的比較速度。在ORB方法中，以圖像塊（假設(shè)用A表示）幾何中心和形心的連線作為特征點(diǎn)方向，以此保證BRIEF描述子具有旋轉(zhuǎn)不變性。計(jì)算形心和坐標(biāo)方向的公式如下：

2.2 創(chuàng)建BoW模型

借鑒文本檢索中單詞反映文本重要信息的作用，將表示圖像局部信息的特征點(diǎn)聚類成無(wú)序視覺(jué)單詞，將它們組成詞袋用來(lái)表征圖像。對(duì)特征點(diǎn)進(jìn)行k-means聚類得到聚類中心點(diǎn)（視覺(jué)單詞）后，對(duì)視覺(jué)單詞分配TF-IDF權(quán)重，權(quán)重值表示如下：

其中，nid表示第i個(gè)視覺(jué)單詞在圖像d中出現(xiàn)的頻數(shù)，nd表示圖像d的視覺(jué)單詞總數(shù)，N表示所有圖像總數(shù)，Ni表示第i個(gè)視覺(jué)單詞在所有圖像中出現(xiàn)的頻數(shù)。權(quán)重值被加入到特征索引結(jié)構(gòu)中，將圖像的各個(gè)特征點(diǎn)量化到與其距離最近的視覺(jué)單詞中，統(tǒng)計(jì)各視覺(jué)單詞的得分，即特征量化到各視覺(jué)單詞的權(quán)重值之和，將各視覺(jué)單詞得分組成向量用來(lái)表示該圖像。

2.3 基于BoW創(chuàng)建視覺(jué)字典樹

對(duì)于BoW方法，需要使用數(shù)量巨大的視覺(jué)單詞，以保證較高的圖像匹配準(zhǔn)確度，此時(shí)查找效率比較低。為了提高查找效率，采用樹結(jié)構(gòu)的節(jié)點(diǎn)來(lái)組織不同聚類層次的視覺(jué)單詞，葉子節(jié)點(diǎn)存儲(chǔ)圖像特征點(diǎn)，查找匹配特征點(diǎn)的過(guò)程為從根節(jié)點(diǎn)往下搜索到葉子節(jié)點(diǎn)。然而，使用視覺(jué)字典樹方法同樣會(huì)帶來(lái)較大的感知歧義問(wèn)題。為了改進(jìn)BoW模型局部特征匹配造成較大量化誤差的不足，提出對(duì)圖像比較全排列特征空間向量信息的方法。

3 分塊特征空間向量全排列比較方法

3.1 均勻劃分4塊區(qū)域的特征空間信息

受視角差異等因素的影響，包含相似內(nèi)容的不同圖像，它們的分塊區(qū)域不一定按序一一對(duì)應(yīng)，這種情況導(dǎo)致基于金字塔空間的圖像匹配方法的準(zhǔn)確性不高[12]。將圖像分成均勻的4塊區(qū)域，從左到右、從上到下分別編號(hào)為1，2，3，4。如圖3所示，不同符號(hào)表示不同的視覺(jué)單詞：（a）為某時(shí)刻相機(jī)獲取圖像，（b）為移動(dòng)機(jī)器人再次到達(dá)（a）所到過(guò)地點(diǎn)時(shí)相機(jī)獲取的圖像。因這2個(gè)不同時(shí)刻相機(jī)拍攝角度不一致，所以（a）中2和4區(qū)域分別和（b）中的1和3區(qū)域有較高對(duì)應(yīng)度。對(duì)于這種情況，將圖像的各區(qū)域兩兩比較，能得到更真實(shí)的匹配結(jié)果。采用均勻劃分4塊區(qū)域的特征空間全排列向量比較方法，既能利用特征空間關(guān)聯(lián)信息彌補(bǔ)BoW匹配方法易造成感知歧義的不足，又能改進(jìn)金字塔匹配方法導(dǎo)致效率較低和魯棒性不高的問(wèn)題。

在對(duì)圖像特征點(diǎn)聚類構(gòu)成視覺(jué)單詞后，記錄視覺(jué)單詞的位置。統(tǒng)計(jì)各區(qū)域中特征量化到各個(gè)視覺(jué)單詞的得分Sijk，它表示圖像i的特征量化到第j個(gè)區(qū)域的第k個(gè)視覺(jué)單詞的得分。假設(shè)視覺(jué)單詞數(shù)目為n，圖像i的每個(gè)區(qū)域特征空間向量為，4個(gè)區(qū)域的向量組合成4×3×2×1=24種特征空間全排列向量：Vi_space=（Via，Vib，Vic，Vid），其中a、b、c、d∈{1，2，3}且a≠b≠c≠d。該向量就是查詢圖像的特征空間信息，用于與圖像庫(kù)圖像中劃分4個(gè)區(qū)域按序排列的特征空間信息比較相似性，確定最優(yōu)閉環(huán)。

3.2 計(jì)算閉環(huán)

閉環(huán)檢測(cè)過(guò)程中，先判斷前一時(shí)刻圖像和當(dāng)前圖像的相似值是否小于設(shè)定閾值，決定是否進(jìn)一步處理當(dāng)前圖像。如果需要，使用BoW方法初步篩選出與查詢圖像的向量距離小于閾值的候選閉環(huán)圖像。向量間距離值計(jì)算如下。假設(shè)圖像庫(kù)圖像x的向量表示為Vx，查詢圖像y的向量為Vy，歸一化兩幅圖像向量并計(jì)算L1-范數(shù)距離的公式如下：

根據(jù)距離確定圖像相似度高低，距離越小，代表兩張圖像越相似，反之圖像越不相似。然后將查詢圖像的全排列向量分別與候選閉環(huán)圖像特征空間向量進(jìn)行相似性比較，使用公式（5）的L1-范數(shù)距離公式計(jì)算它們向量間的距離。最相似兩張圖像的距離值為BoW方法和特征空間信息方法計(jì)算距離的最小值，即，該值對(duì)應(yīng)的候選閉環(huán)圖像為選出的最優(yōu)閉環(huán)。

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

本實(shí)驗(yàn)所用軟硬件配置如下：電腦CPU為i7處理器，主頻是2.6GHz，內(nèi)存為16G，系統(tǒng)為Ubuntu 16.04 LTS，采用C++作為實(shí)驗(yàn)編程語(yǔ)言。本文的實(shí)驗(yàn)對(duì)象為New College數(shù)據(jù)集和City Centre數(shù)據(jù)集，它們是SLAM閉環(huán)檢測(cè)的標(biāo)準(zhǔn)數(shù)據(jù)集，由牛津大學(xué)移動(dòng)機(jī)器人實(shí)驗(yàn)室對(duì)室外大型場(chǎng)景采集而來(lái)。這兩個(gè)數(shù)據(jù)集帶有真實(shí)閉環(huán)信息，可用來(lái)檢驗(yàn)實(shí)驗(yàn)測(cè)試效果。

分別使用ORB方法和SURF方法（對(duì)SIFT的改進(jìn)，能加速特征提取）[13]，對(duì)New College數(shù)據(jù)集不同時(shí)刻、同一地點(diǎn)構(gòu)成閉環(huán)的兩張圖像0745.jpg和1563.jpg進(jìn)行特征提取和匹配實(shí)驗(yàn)，用圓圈標(biāo)記檢測(cè)到的特征點(diǎn)。調(diào)整兩種方法的特征檢測(cè)閾值，設(shè)定ORB方法的閾值為使它們檢測(cè)到數(shù)目接近的特征點(diǎn)，然后比較特征檢測(cè)效果（如圖4所示）。

圖5是2種特征提取方法對(duì)上述閉環(huán)圖像對(duì)的特征匹配效果，匹配點(diǎn)間用線段相連。選擇New College和City Centre數(shù)據(jù)集的各10對(duì)閉環(huán)圖像，采用這兩種特征提取方法進(jìn)行對(duì)比實(shí)驗(yàn)，將誤匹配點(diǎn)初步過(guò)濾后，結(jié)果列于表1。通過(guò)該實(shí)驗(yàn)可知，雖然ORB方法特征檢測(cè)的魯棒性不及SURF方法，但它也能較準(zhǔn)確地提取圖像特征，且用時(shí)明顯遠(yuǎn)遠(yuǎn)少于SURF方法，因此更好地滿足了SLAM對(duì)圖像特征提取準(zhǔn)確性和效率的要求。

利用基于視覺(jué)字典樹結(jié)構(gòu)的BoW方法量化表示圖像后，選出距離小于設(shè)定閾值的候選閉環(huán)，受相機(jī)平移偏轉(zhuǎn)和噪聲等影響，這些圖像難免會(huì)存在視覺(jué)混淆現(xiàn)象。單從BoW方法得出的圖像匹配得分大小選出候選閉環(huán)存在較大的局限性，本文采用特征空間信息方法加以改進(jìn)。分別對(duì)New College和City Centre數(shù)據(jù)集的查詢圖像和對(duì)應(yīng)候選閉環(huán)圖像，使用BoW方法和劃分4塊區(qū)域特征空間方法計(jì)算相似度，統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果見(jiàn)表2。

針對(duì)New College數(shù)據(jù)集的實(shí)驗(yàn)顯示，劃分4塊特征空間的方法明顯比BoW方法計(jì)算的真實(shí)閉環(huán)圖像間平均距離小，小約31.13%。雖然前者計(jì)算的錯(cuò)誤閉環(huán)圖像間平均距離較小，但只小了約2.89%。這說(shuō)明前者對(duì)相似圖像識(shí)別度明顯比后者高，兩者對(duì)非相似圖像識(shí)別度基本一致。最終前者的閉環(huán)檢測(cè)正確率比后者高約5.0%，時(shí)間僅增加約0.65%。City Centre數(shù)據(jù)集圖像整體偏暗，檢測(cè)到的特征點(diǎn)較少，導(dǎo)致圖像混淆度較高。在此數(shù)據(jù)集實(shí)驗(yàn)中，劃分4塊特征空間方法和BoW相比，前者計(jì)算的真實(shí)閉環(huán)圖像間平均距離比后者小約29.11%，錯(cuò)誤閉環(huán)圖像間平均距離只比后者小了約4.30%。同樣說(shuō)明前者對(duì)相似圖像識(shí)別度更高，而兩者對(duì)非相似圖像識(shí)別度基本相似。前者的閉環(huán)檢測(cè)正確率比后者高約3.5%，時(shí)間僅增加約0.58%。因此，特征空間信息方法優(yōu)于BoW方法。這是因?yàn)樘卣骺臻g信息方法統(tǒng)計(jì)了不同區(qū)域的特征信息，相似圖像間的這些特征信息理應(yīng)比較一致，對(duì)視角偏轉(zhuǎn)圖像間的匹配，全排列向量比較具有更高的魯棒性，而非相似圖像間不具有這樣的特性。特征空間信息方法降低了因視角偏轉(zhuǎn)、噪聲等帶來(lái)的感知偏差，提高了閉環(huán)檢測(cè)正確率，同時(shí)這種方法僅需查詢圖像全排列特征空間向量與候選圖像特征空間向量比較帶來(lái)的較小時(shí)間代價(jià)。

5 結(jié)論

視覺(jué)SLAM閉環(huán)檢測(cè)中，使用ORB特征提取方法，能快速且較魯棒地為構(gòu)建BoW提供特征點(diǎn)，通過(guò)視覺(jué)字典樹結(jié)構(gòu)快速查詢圖像特征。本文通過(guò)全排列特征空間向量比較圖像間相似性，與BoW方法相比，提高了圖像匹配的準(zhǔn)確率和魯棒性，處理速度符合實(shí)時(shí)性要求，可較好地保證閉環(huán)檢測(cè)的性能。未來(lái)將進(jìn)一步挖掘圖像特征間更有效的空間聯(lián)系信息，或結(jié)合其他減少圖像感知歧義的方法，進(jìn)一步提高閉環(huán)檢測(cè)的準(zhǔn)確率。

參 考 文 獻(xiàn)

[1]J Fuentes-Pacheco，J Ruiz-Ascencio，JM Rendó

n-Mancha.Visual simultaneous localization and mapping：a survey[J].Artificial Intelligence Review，

2015，43（1）：55-81.

[2]Brian Williams，Mark Cummins，Jose Neira，et al.

A comparison of loop closing techniques in monocular SLAM[J].Robotics & Autonomous Systems，2009，57（12）：1188-1197.

[3]Gabriella Csurka，Christopher R.Dance，Lixin Fan，Jutta Willamowski，Cédric Bray.Visual Categorization with Bags of Keypoints[C].Workshop on Statistical Learning in Computer Vision Eccv，2004，44 （247）：1-22.

[4]Josef Sivic，Andrew Zisserman.Video Google：A

Text Retrieval Approach to Object Matching in Vid-

eos[J].IEEE International Conference on Computer Vision，2003，2：147.

[5]David Nister，Henrik Stewenius.Scalable recognition

with a vocabulary tree[C].IEEE Computer Society

Conference on Computer Vision&Pattern Recognition.2006，2（10）：2161-2168.

[6]Dorian Galvez-Lopez，Juan D.Tardos.Bags of

Binary Words for Fast Place Recognition in Image Sequences[J].IEEE Transactions on Robotics，2012，

28（5）：1188-1197.

[7]Nishant Kejriwal，Swagat Kumara，Tomohiro Shibata.High performance loop closure detection using bag of word pairs[J].Robotics & Autonomous Systems，2015，77（C）：55-65.

[8]Svetlana Lazebnik，Cordelia Schmid，Jean Ponce.Beyond Bags of Features：Spatial Pyramid Matching for Recognizing Natural Scene Categories[C].Computer Vision and Pattern'Recognition，Page（s）：2169-2178.

[9]李博，楊丹，鄧林.移動(dòng)機(jī)器人閉環(huán)檢測(cè)的視覺(jué)字典樹金字塔TF-IDF得分匹配方法[J].自動(dòng)化學(xué)報(bào)，2011

37（6）：665-673.

[10]David G.Lowe Distinctive Image Features from

Scale-Invariant Keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[11]Ethan Rublee，Vincent Rabaud，Kurt Konolige，et al.

ORB：an efficient alternative to SIFT or SURF[C].IEEE International Conference on Computer Vision，2012，58（11）：2564-2571.

[12]張琳波，王春恒，肖柏華，等.基于Bag-of-phrases的圖像表示方法[J].自動(dòng)化學(xué)報(bào)，2012，38（1）：46-

54.

[13]Herbert Bay，Andreas Ess，Tinne Tuytelaars，et al.Speeded-Up Robust Features（SURF）[C].European Conference on Computer Vision，2006，110

（3）：404-417.