羅升斯 黎展榮

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

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

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

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

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

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

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

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

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

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

2.1 ORB特征提取方法

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

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

2.2 創(chuàng)建BoW模型

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

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

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

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

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

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

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

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

3.2 計算閉環(huán)

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

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

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

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

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

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

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

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

5 結(jié)論

視覺SLAM閉環(huán)檢測中，使用ORB特征提取方法，能快速且較魯棒地為構(gòu)建BoW提供特征點，通過視覺字典樹結(jié)構(gòu)快速查詢圖像特征。本文通過全排列特征空間向量比較圖像間相似性，與BoW方法相比，提高了圖像匹配的準(zhǔn)確率和魯棒性，處理速度符合實時性要求，可較好地保證閉環(huán)檢測的性能。未來將進(jìn)一步挖掘圖像特征間更有效的空間聯(lián)系信息，或結(jié)合其他減少圖像感知歧義的方法，進(jìn)一步提高閉環(huán)檢測的準(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]李博，楊丹，鄧林.移動機(jī)器人閉環(huán)檢測的視覺字典樹金字塔TF-IDF得分匹配方法[J].自動化學(xué)報，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].自動化學(xué)報，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.