李卓，魏國亮，管啟，黃蘇軍，趙珊

圖文信息技術(shù)

基于組合圖像特征與分層節(jié)點(diǎn)搜索的回環(huán)檢測(cè)方法

李卓a，魏國亮b，管啟a，黃蘇軍a，趙珊a

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

文中通過提出一種新的回環(huán)解決方案，平衡回環(huán)檢測(cè)系統(tǒng)的高準(zhǔn)確率與高運(yùn)行效率。提出一種利用組合圖像特征與分層節(jié)點(diǎn)搜索的新方法。首先，計(jì)算一種原始圖像的下采樣二值化全局特征和經(jīng)過改進(jìn)的ORB（oriented FAST and rotated BRIEF）局部特征，將其存入圖像特征數(shù)據(jù)庫。其次，引入一種分層節(jié)點(diǎn)搜索算法，在數(shù)據(jù)庫中搜索與當(dāng)前圖像特征最相似的全局特征作為回環(huán)候選。最后，利用改進(jìn)的ORB特征進(jìn)行局部特征匹配，驗(yàn)證候選圖像，確定回環(huán)檢測(cè)結(jié)果。使用該算法在3個(gè)不同的數(shù)據(jù)集上進(jìn)行驗(yàn)證，測(cè)試中每次回環(huán)檢測(cè)的平均處理時(shí)間僅需19 ms。實(shí)驗(yàn)結(jié)果表明，該算法在運(yùn)行效率、準(zhǔn)確率、召回率等方面均達(dá)到了領(lǐng)域內(nèi)的先進(jìn)水平。

回環(huán)檢測(cè)；全局特征；局部特征；分層節(jié)點(diǎn)

通過機(jī)器實(shí)現(xiàn)自動(dòng)包裝與運(yùn)輸已成為現(xiàn)代工廠中降低制造成本的重要方法，vSLAM正是實(shí)現(xiàn)這一目標(biāo)的關(guān)鍵技術(shù)之一[1]。vSLAM利用相機(jī)使機(jī)器進(jìn)行定位與建圖，從而實(shí)現(xiàn)工廠的自動(dòng)化包裝、運(yùn)輸?shù)拳h(huán)節(jié)。系統(tǒng)長時(shí)間運(yùn)行會(huì)產(chǎn)生累計(jì)誤差，導(dǎo)致所建地圖的精度降低。回環(huán)檢測(cè)是vSLAM系統(tǒng)中的一個(gè)重要環(huán)節(jié)，它可以確定機(jī)器是否返回到先前經(jīng)過的位置，這種信息對(duì)于減小累計(jì)誤差，創(chuàng)建正確的地圖和提高地圖的精度具有重要意義。

通常，vSLAM中回環(huán)檢測(cè)問題可轉(zhuǎn)化為基于內(nèi)容的圖像檢索問題，即在歷史圖像中找到與指定圖像最相似的一幀。傳統(tǒng)圖像檢索方法大致可分為4類；基于全局圖像特征、基于局部圖像特征、基于視覺詞袋方法、基于組合圖像特征[2]。全局特征如Bradley等[3]使用的加權(quán)梯度方向直方圖，Singh等[4]設(shè)計(jì)的Gist特征等，其計(jì)算、匹配速度較快，但準(zhǔn)確率較低。Lowe等[5]提出尺度不變特征變換（Scale-invariant feature transform, SIFT）局部特征，其穩(wěn)定性和準(zhǔn)確率有較大提高，但特征提取、匹配太過耗時(shí)，無法應(yīng)用于實(shí)時(shí)回環(huán)檢測(cè)系統(tǒng)。Galvez等[6]將局部二值特征BRIEF與詞袋方法組合使用，詞袋模型（Distributed bag of words, DBoW2）使得實(shí)時(shí)運(yùn)行的回環(huán)檢測(cè)系統(tǒng)成為可能。近年來流行的幾種SLAM算法如ORBSLAM3等[7]都是采用此方法進(jìn)行回環(huán)檢測(cè)，但是，詞袋模型帶來的準(zhǔn)確率降低等問題依舊困擾著研究者們。

隨著深度學(xué)習(xí)的快速發(fā)展，出現(xiàn)了許多利用深度學(xué)習(xí)代替?zhèn)鹘y(tǒng)方法的回環(huán)方案[8]，如Shan An等[9]提出FILD(Fast and incremental loop closure detection)，Yue H等[10]提出的BoSP(Bag of SuperPoints)以及Arandjelovic等[11]提出的基于NetVLAD的方法。此類方法雖然達(dá)到了較高的準(zhǔn)確率，但過于復(fù)雜的特征計(jì)算需要強(qiáng)大的計(jì)算力，短期內(nèi)無法在小型平臺(tái)如無人機(jī)上實(shí)時(shí)運(yùn)行。與此同時(shí)，基于組合特征的方法也有了進(jìn)展，Carrasco等[12]提出的Haloc算法利用全局標(biāo)簽和SIFT特征完成回環(huán)檢測(cè)，較大地提升了系統(tǒng)準(zhǔn)確率。

盡管有如此多種方法解決回環(huán)檢測(cè)問題，但大多數(shù)都不能既滿足vSLAM系統(tǒng)實(shí)時(shí)性的要求，又滿足其高準(zhǔn)確率和召回率的要求。針對(duì)此問題，文中提出一種回環(huán)檢測(cè)方法，使用計(jì)算速率大大加快的二值圖像特征以及高效的圖像檢索算法，使系統(tǒng)能夠在保證高準(zhǔn)確率和高召回率的前提下實(shí)時(shí)運(yùn)行。

1 算法概述

算法主要框架見圖1。與基于組合特征的回環(huán)檢測(cè)系統(tǒng)結(jié)構(gòu)類似，整個(gè)過程可以分為3個(gè)階段：計(jì)算圖像特征、全局搜索候選圖像以及候選驗(yàn)證。

第1階段，計(jì)算圖像的全局二值特征與局部二值特征，選取二值特征的原因是提高系統(tǒng)運(yùn)行效率，保證實(shí)時(shí)運(yùn)行。第2階段，使用分層節(jié)點(diǎn)搜索算法在歷史幀中找到當(dāng)前圖像的回環(huán)候選幀，應(yīng)用此搜索算法使得系統(tǒng)能在大規(guī)模地圖中實(shí)時(shí)運(yùn)行。第3階段，利用局部特征匹配來驗(yàn)證回環(huán)候選幀，當(dāng)匹配數(shù)超過預(yù)先設(shè)定的閾值時(shí)，通過RANSAC[13]進(jìn)行幾何驗(yàn)證，最終確定回環(huán)幀。

2 圖像特征提取

2.1 全局圖像特征

為加快圖像檢索速率，文中使用一種簡單的全局圖像描述方法[14]，具體過程見圖2。首先利用高斯濾波器對(duì)圖像進(jìn)行平滑處理，接著對(duì)圖像進(jìn)行降采樣縮小尺寸，然后使用大津法進(jìn)行二值化處理，產(chǎn)生幾百位的二進(jìn)制碼。這種全局二值特征計(jì)算速率極快，準(zhǔn)確率也非常高，當(dāng)采用漢明距離作為圖像間相似度時(shí)，1 s內(nèi)可與千萬張圖像進(jìn)行計(jì)算。

2.2 改進(jìn)ORB特征

ORB特征[15]具有計(jì)算速度快、旋轉(zhuǎn)不變性等優(yōu)點(diǎn)，但與浮點(diǎn)型特征如SIFT、SURF等相比其穩(wěn)定性和可區(qū)分性都有所不及。文中希望引入一種既擁有二值特征計(jì)算速度快等優(yōu)點(diǎn)，又擁有浮點(diǎn)型特征穩(wěn)定性好、可區(qū)分性好等優(yōu)點(diǎn)的局部特征。Schlegel等[16]的工作帶來了一些啟發(fā)，將圖像信息的其他線索以二進(jìn)制碼的形式添加至描述符，使其可以記錄更多圖像信息，可區(qū)分性將變得更好。

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

圖2 全局圖像特征提取

基于上述分析，文中提出了一種ORB特征的改進(jìn)型特征，描述尺度信息的ORB特征（Scale-ORB，SORB），在一定程度上改進(jìn)了ORB特征穩(wěn)定性與可區(qū)分性差的缺點(diǎn)。將特征點(diǎn)的尺度信息編碼成八位二進(jìn)制字符串，添加到ORB特征描述符之后，以便在計(jì)算距離時(shí)直接使用這些信息。首先將特征點(diǎn)的尺度信息轉(zhuǎn)化為八位二進(jìn)制碼()，為特征點(diǎn)尺度信息（0—7），并附加到原始ORB描述符之后，從而得到一個(gè)新的描述符,。()根據(jù)式（1）得到。

(1)

(2)

不同尺度的特征點(diǎn)對(duì)應(yīng)的二進(jìn)制字符串見圖3。新生成描述符與ORB特征的描述符都為位向量，可通過計(jì)算2個(gè)向量之間不同位的數(shù)量來測(cè)量其漢明距離。計(jì)算機(jī)通過異或運(yùn)算實(shí)現(xiàn)此操作，這正是計(jì)算機(jī)最擅長且速度最快的計(jì)算方式之一。

圖3 特征點(diǎn)尺度對(duì)應(yīng)的二進(jìn)制字符串

3 分層節(jié)點(diǎn)搜索算法

視覺回環(huán)檢測(cè)系統(tǒng)的另一個(gè)核心問題是數(shù)據(jù)檢索算法。暴力搜索和k-d樹是解決數(shù)據(jù)檢索問題的2個(gè)經(jīng)典方法，但都有各自的缺點(diǎn)。暴力搜索只適用于小規(guī)模數(shù)據(jù)，一旦規(guī)模過大，檢索過程將十分耗時(shí)，系統(tǒng)不能實(shí)時(shí)運(yùn)行。k-d樹搜索算法在使用SIFT等浮點(diǎn)特征構(gòu)造搜索結(jié)構(gòu)時(shí)表現(xiàn)良好，使用二進(jìn)制碼時(shí)性能會(huì)遭受較大的損失。近年來Schlegel等[17]提出的HBST搜索方法在數(shù)據(jù)規(guī)模過大時(shí)也容易失去作用，因此文中提出一種適用于大規(guī)模數(shù)據(jù)且高效的檢索算法，即分層節(jié)點(diǎn)搜索算法。

算法的分層結(jié)構(gòu)見圖4。檢索過程具體為：在系統(tǒng)運(yùn)行過程中將歷史圖像在線聚類為若干圖像袋，每個(gè)圖像袋內(nèi)包含若干相似的圖像，稱為二級(jí)節(jié)點(diǎn)，其中最早出現(xiàn)的圖像稱為一級(jí)節(jié)點(diǎn)；整個(gè)檢索過程分為2層，第1層檢索是在一級(jí)節(jié)點(diǎn)圖像中找到與當(dāng)前圖像相似度最高的若干圖像，第2層檢索是從上述一級(jí)節(jié)點(diǎn)圖像袋內(nèi)找到與當(dāng)前圖像相似度最高的若干圖像，并將其作為回環(huán)候選。在實(shí)驗(yàn)中這種檢索方法不僅表現(xiàn)出與暴力搜索相當(dāng)?shù)臏?zhǔn)確率，且效率更高。

分層節(jié)點(diǎn)結(jié)構(gòu)的更新過程見圖5。記當(dāng)前圖像與其前一幀圖像的漢明距離為，依次計(jì)算當(dāng)前圖像與一級(jí)節(jié)點(diǎn)圖像的漢明距離，判斷最小距離是否小于設(shè)定的參數(shù)。若小于，表明當(dāng)前圖像與此一級(jí)節(jié)點(diǎn)圖像十分相似，可將當(dāng)前圖像添加至此一級(jí)節(jié)點(diǎn)的圖像袋，進(jìn)一步判別是否發(fā)生了回環(huán)。若大于，則利用當(dāng)前圖像創(chuàng)建新圖像袋，并將其置于新圖像袋內(nèi)。這表明當(dāng)前圖像與歷史圖像有較大差別，大概率是機(jī)器訪問了新的位置。

為提高回環(huán)檢測(cè)系統(tǒng)的召回率，文中還設(shè)計(jì)了一種動(dòng)態(tài)閾值算法?；丨h(huán)問題中機(jī)器得到的圖像在時(shí)間與空間上都是連續(xù)的。一段極小的時(shí)間內(nèi)，若機(jī)器形成回環(huán)，在后續(xù)幾個(gè)時(shí)刻內(nèi)必將連續(xù)形成回環(huán)，這是由時(shí)間、空間連續(xù)帶來的必然現(xiàn)象。動(dòng)態(tài)閾值算法具體表現(xiàn)為：當(dāng)系統(tǒng)連續(xù)形成次回環(huán)時(shí)擴(kuò)大上述閾值，使得=(≥1)。后續(xù)幾個(gè)時(shí)刻大概率會(huì)繼續(xù)形成回環(huán)，擴(kuò)大閾值有助于減少全局特征描述圖像帶來的誤差，從而在一定程度上提高系統(tǒng)的召回率。由于在全局搜索后還將進(jìn)行回環(huán)驗(yàn)證，因此不必?fù)?dān)心添加了錯(cuò)誤的回環(huán)候選圖像而導(dǎo)致系統(tǒng)準(zhǔn)確率下降。

4 驗(yàn)證候選圖像

利用分層節(jié)點(diǎn)搜索算法找出當(dāng)前圖像的回環(huán)候選圖像后需要進(jìn)行候選驗(yàn)證，從而確定唯一的回環(huán)幀或是確定不產(chǎn)生回環(huán)。這個(gè)過程需要利用圖像的局部特征進(jìn)行匹配。在匹配過程中，當(dāng)前圖像某一描述符的最近鄰與次近鄰滿足式（3）時(shí)認(rèn)為產(chǎn)生了一個(gè)正確的匹配。

圖4 分層節(jié)點(diǎn)架構(gòu)

圖5 分層節(jié)點(diǎn)搜索算法的更新與檢索

(3)

5 實(shí)驗(yàn)與評(píng)估

通過實(shí)驗(yàn)測(cè)定SORB特征與分層節(jié)點(diǎn)搜索算法的有效性，并將文中算法與3種傳統(tǒng)方案和3種深度學(xué)習(xí)方案進(jìn)行對(duì)比，以驗(yàn)證其先進(jìn)性。實(shí)驗(yàn)在3個(gè)數(shù)據(jù)集上進(jìn)行，其中2個(gè)是由牛津大學(xué)的Mark Cummins等[18]采集的City Center和New College數(shù)據(jù)集，分別包含1237對(duì)圖像和1073對(duì)圖像。第3個(gè)數(shù)據(jù)集為Malaga07[19]，一段在室外的微動(dòng)態(tài)公路上采集的數(shù)據(jù)，包含2121對(duì)圖像，此數(shù)據(jù)集的真實(shí)回環(huán)信息由手工標(biāo)定得到。文中選取了這些數(shù)據(jù)集的單側(cè)圖像進(jìn)行實(shí)驗(yàn)，3個(gè)數(shù)據(jù)集中具有代表性的圖像見圖6。實(shí)驗(yàn)均在同一臺(tái)計(jì)算機(jī)上進(jìn)行，其主要硬件配置包括：CPU為Intel Xeon(R)Gold 5120處理器，主頻2.2 GHz，內(nèi)存32 G。

5.1 算法有效性分析

5.1.1 全局特征維度

圖像特征的維度是特征描述圖像的關(guān)鍵。維度越大，承載的圖像信息越多，越能更好區(qū)分不同圖像。隨著特征維度增大，計(jì)算量也會(huì)增加，系統(tǒng)運(yùn)行效率將變低，不能達(dá)到實(shí)時(shí)運(yùn)行的目的。需要在內(nèi)存占用與系統(tǒng)性能二者之間做出取舍，達(dá)到最優(yōu)效果。如圖7所示，分別選取全局特征維度為300維、480維、960維進(jìn)行比較。3個(gè)數(shù)據(jù)集上的結(jié)果顯示，全局特征維度增加至480維時(shí)系統(tǒng)達(dá)到最佳性能，雖然960維時(shí)系統(tǒng)性能也接近最佳，但此時(shí)計(jì)算量與內(nèi)存都將大大增加，因此在后續(xù)實(shí)驗(yàn)中選擇480維作為全局特征維度。

圖6 數(shù)據(jù)集中的部分圖像

Fig.6 Some images in dataset

圖7 不同維度的全局特征對(duì)應(yīng)的召回率-準(zhǔn)確率曲線

5.1.2 SORB特征的有效性

將形成回環(huán)的2幅圖像進(jìn)行局部特征匹配時(shí)，正確的匹配對(duì)中有接近90%的特征點(diǎn)是尺度相同的，所有正確匹配對(duì)的尺度差都在一個(gè)尺度單位以內(nèi)。若將特征的尺度信息添加至描述符中，匹配錯(cuò)誤的特征之間距離將變大，正確的匹配不會(huì)發(fā)生改變。由式（3）可知，最近鄰與次近鄰距離之比將變小，從而提高特征匹配的準(zhǔn)確率。

為驗(yàn)證SORB特征有效性，分別應(yīng)用該特征與傳統(tǒng)ORB特征在3個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果見圖8。由圖8可知，在City Center數(shù)據(jù)集上，當(dāng)準(zhǔn)確率為100%時(shí)，應(yīng)用2種特征的系統(tǒng)最大召回率基本一致。在New College數(shù)據(jù)集上，當(dāng)準(zhǔn)確率為100%時(shí)，SORB特征比傳統(tǒng)ORB特征最大召回率高出2%左右。在Malaga07數(shù)據(jù)集上，當(dāng)準(zhǔn)確率為100%時(shí)，SORB特征比傳統(tǒng)ORB特征最大召回率高出6%左右。在計(jì)算耗時(shí)方面，提取一張圖像的SORB特征只比傳統(tǒng)的ORB特征多出0.2 ms左右，這對(duì)整個(gè)系統(tǒng)來講幾乎沒有影響。綜上得出，在圖像匹配方面，SORB特征的各項(xiàng)性能是優(yōu)于傳統(tǒng)ORB特征的。后期還可將此方法應(yīng)用在最新的局部圖像特征如BEBLID[20]中去，驗(yàn)證文中提出方法的通用性。

5.1.3 分層節(jié)點(diǎn)搜索算法性能分析

為驗(yàn)證分層節(jié)點(diǎn)搜索算法的有效性，將其與暴力搜索算法進(jìn)行了對(duì)比實(shí)驗(yàn)。首先確定影響算法性能的幾個(gè)參數(shù)的取值，一是選擇距離最近的前個(gè)一級(jí)節(jié)點(diǎn)進(jìn)行下一步搜索，二是在上述幾個(gè)一級(jí)節(jié)點(diǎn)的圖像袋中選擇距離最近的前個(gè)二級(jí)節(jié)點(diǎn)作為候選圖像。在3個(gè)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)得到，當(dāng)為4，為16時(shí)，分層節(jié)點(diǎn)搜索算法達(dá)到最優(yōu)性能。

搜索算法最重要的性能指標(biāo)之一是其滿足高準(zhǔn)確率時(shí)的搜索效率，暴力搜索是目前搜索算法中準(zhǔn)確率最高的算法之一，由于其搜索效率低下才不被廣泛應(yīng)用。分層節(jié)點(diǎn)搜索算法與暴力搜索算法應(yīng)用于不同規(guī)模地圖時(shí)的搜索效率見圖9。圖9中暴力搜索算法耗時(shí)隨地圖規(guī)模的增加明顯快于分層節(jié)點(diǎn)搜索算法，當(dāng)?shù)貓D規(guī)模小于16 000幀時(shí)，暴力搜索方法的效率更高，這是由于構(gòu)造分層節(jié)點(diǎn)結(jié)構(gòu)需要消耗一定時(shí)間，當(dāng)?shù)貓D規(guī)模大于16 000幀圖像后，分層節(jié)點(diǎn)搜索算法的效率將變得更高，并且此后耗時(shí)增長十分緩慢，因此，當(dāng)在大規(guī)模地圖中應(yīng)用時(shí)，分層節(jié)點(diǎn)搜索算法更有優(yōu)勢(shì)。

圖8 SORB特征與ORB特征對(duì)應(yīng)的召回率-準(zhǔn)確率曲線

圖9 暴力搜索與分層節(jié)點(diǎn)搜索算法的效率對(duì)比

5.1.4 動(dòng)態(tài)閾值算法的有效性

參數(shù)確定是動(dòng)態(tài)閾值算法的關(guān)鍵。通過實(shí)驗(yàn)測(cè)定代表連續(xù)回環(huán)次數(shù)的和代表倍數(shù)的的具體取值。將選為1～3，不超過3是因?yàn)樘L的回環(huán)確認(rèn)時(shí)間將導(dǎo)致召回率下降，使動(dòng)態(tài)閾值算法變得沒有意義。的選值則在1～2，太大的將導(dǎo)致全局搜索的準(zhǔn)確率降低。通過改變參數(shù)、算法在New College數(shù)據(jù)集下的準(zhǔn)確率-召回率曲線，見圖10。隨著從1增加到2，當(dāng)準(zhǔn)確率為100%時(shí)，系統(tǒng)的最大召回率在逐漸增加，當(dāng)超過2時(shí)系統(tǒng)的最大召回率開始降低。也是如此，隨著的增長系統(tǒng)的最大召回率逐漸增加，當(dāng)為1.5時(shí)達(dá)到最大值。當(dāng)為2，為1.5時(shí)，系統(tǒng)在數(shù)據(jù)集中顯示出了最優(yōu)的準(zhǔn)確率與召回率，相較于不使用動(dòng)態(tài)閾值法（即為1，為1）的系統(tǒng)，最大召回率提高了近10%。

圖10 不同閾值對(duì)應(yīng)的召回率-準(zhǔn)確率曲線

5.2 幾種回環(huán)算法對(duì)比

選取全局特征維度為480維，連續(xù)回環(huán)次數(shù)為2，倍數(shù)為1.5進(jìn)行試驗(yàn)，此數(shù)據(jù)下文中算法表現(xiàn)出最佳性能。文中算法與Haloc、DBoW2、FAB-MAP2[21]以及深度學(xué)習(xí)方法NetVLAD、BoSP、FILD進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果見表1?；谏疃葘W(xué)習(xí)的方案FILD在New College和Malaga07數(shù)據(jù)集下表現(xiàn)出最佳性能，方案BoSP在City Center數(shù)據(jù)集下表現(xiàn)出最佳性能，且大幅領(lǐng)先其他方案。4種傳統(tǒng)方法中，New College數(shù)據(jù)集下，文中算法與DBoW2性能相近，二者均優(yōu)于Haloc和FAB-MAP2。另外2個(gè)數(shù)據(jù)集下，文中算法明顯優(yōu)于其他傳統(tǒng)方案，且性能比早期深度學(xué)習(xí)方案NetVLAD更好，僅在最大召回率方面不足近2年提出的基于深度學(xué)習(xí)的BoSP與FILD。

通過New College數(shù)據(jù)集測(cè)試了各算法進(jìn)行回環(huán)檢測(cè)的平均用時(shí)，見表2。幾種基于深度學(xué)習(xí)的方案在利用GPU(GeForce GTX 1080)加速的情況下一次回環(huán)檢測(cè)仍需要40～400 ms，而文中算法不使用GPU加速也僅需19 ms。綜合表1、2可以看出，基于深度

學(xué)習(xí)的方案雖然在最大召回率方面有著明顯優(yōu)勢(shì)，但巨大的時(shí)間消耗使得它不能部署在小型機(jī)器上實(shí)時(shí)運(yùn)行，這也體現(xiàn)了一般算法的運(yùn)行效率與準(zhǔn)確率是不宜兼顧的。文中算法平衡了召回率、準(zhǔn)確率、運(yùn)行效率等多個(gè)方面，且性能均優(yōu)于目前流行的傳統(tǒng)方法如DBoW2、Haloc、FAB-MAP2，這是因?yàn)槲闹兴惴ㄈ坎扇《祱D像特征，相比浮點(diǎn)數(shù)特征大大縮短了特征提取與匹配的時(shí)間消耗。使用二值特征將導(dǎo)致圖像信息缺失，從而降低了算法精度，但文中采用SORB特征增加了描述符所攜帶的圖像信息，提升了特征匹配的準(zhǔn)確率，在一定程度上彌補(bǔ)了損失的精度。另外，文中提出的分層節(jié)點(diǎn)搜索方法通過圖像聚類減少了檢索數(shù)量，進(jìn)一步提高了運(yùn)行效率。動(dòng)態(tài)閾值算法則在不增加計(jì)算復(fù)雜度、不降低準(zhǔn)確率的前提下提升了算法的召回率。從實(shí)驗(yàn)結(jié)果來看，正是上述幾點(diǎn)工作發(fā)揮了作用，才能同時(shí)提升算法的運(yùn)行效率與準(zhǔn)確率，滿足目前vSLAM系統(tǒng)對(duì)回環(huán)檢測(cè)算法性能的要求，因此，可以認(rèn)為文中提出的算法在綜合性能上優(yōu)于其他幾種對(duì)比方法。

表1 準(zhǔn)確率為100%時(shí)算法的最大召回率

Tab.1 Maximum recall of algorithm at precision of 100% %

注：黑體表明幾種算法中的最優(yōu)數(shù)據(jù)

表2 幾種算法的時(shí)間消耗

Tab.2 Time consumption of several algorithms ms

注：黑體表明幾種算法中的最優(yōu)數(shù)據(jù)；NetVLAD(G)中G表示此方法使用GPU處理

6 結(jié)語

文中提出了一種實(shí)時(shí)視覺回環(huán)檢測(cè)新方法，并在3個(gè)數(shù)據(jù)集上驗(yàn)證了方法的有效性。文章的主要貢獻(xiàn)：提出了一種SORB特征，與傳統(tǒng)ORB特征相比，局部特征匹配更加準(zhǔn)確，在保持回環(huán)系統(tǒng)運(yùn)行速率不變的同時(shí)其準(zhǔn)確率、召回率也有所提升；構(gòu)造了一種在線建立的分層節(jié)點(diǎn)搜索算法，減少了系統(tǒng)中圖片檢索產(chǎn)生的時(shí)間消耗，使得系統(tǒng)在大規(guī)模地圖中的應(yīng)用成為可能；提出了一種動(dòng)態(tài)閾值算法，顯著提高了系統(tǒng)的召回率。

后續(xù)將在更多數(shù)據(jù)集中進(jìn)一步評(píng)估文中提出的方案，并嘗試將局部特征改進(jìn)方法應(yīng)用到其他二值特征算法中，以驗(yàn)證此方法的通用性。最后準(zhǔn)備將算法整合到一個(gè)完整的vSLAM系統(tǒng)中，應(yīng)用在自動(dòng)化工廠包裝、運(yùn)輸環(huán)節(jié)的機(jī)器上。

[1] 李俊. 基于SLAM導(dǎo)航的多目視覺AGV系統(tǒng)設(shè)計(jì)[J]. 包裝工程, 2018, 39(19): 181-189.

LI Jun. Design of Multi Vision AGV System Based on SLAM Navigation[J]. Packaging Engineering, 2018, 39(19): 181-189.

[2] 劉強(qiáng), 段富海, 桑勇, 等. 復(fù)雜環(huán)境下視覺SLAM閉環(huán)檢測(cè)方法綜述[J]. 機(jī)器人, 2019, 41(1): 112-123.

LIU Qiang, DUAN Fu-hai, SANG Yong, et al. A Survey of Loop-Closure Detection Method of Visual SLAM in Complex Environments[J]. Robot, 2019, 41(1): 112-123.

[3] BRADLEY D M, PATEL R, VANDAPEL N, et al. Real-Time Image-Based Topological Localization in Large Outdoor Environments[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Edmonton, 2005: 3670-3677.

[4] SINGH G, KOSECKA J. Visual Loop Closing Using Gist Descriptors in Manhattan World[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA), 2010: 4042-4047.

[5] LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

[6] GALVEZ L D, TARDOS J D. Bags of Binary Words for Fast Place Recognition in Image Sequences[J]. IEEE Transactions on Robotics, 2012, 28(5): 1188-1197.

[7] CAMPOS C, ELVIRA R, RODRIGUEZ J J R, et al. ORB-SLAM3: An Accurate Open-Source Library for Visual, Visual-Inertial, and Multimap SLAM[J]. IEEE Transactions on Robotics, 2021, 23: 1-17.

[8] 李少朋, 張濤. 深度學(xué)習(xí)在視覺SLAM中應(yīng)用綜述[J]. 空間控制技術(shù)與應(yīng)用, 2019, 45(2): 1-10.

LI Shao-peng, ZHANG Tao. A Survey of Deep Learning Application in Visual SLAM[J]. Aerospace Control and Application, 2019, 45(2): 1-10.

[9] AN Shan, CHE Guang-fu, ZHOU Fang-ru, et al. Fast and Incremental Loop Closure Detection Using Proximity Graphs[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Macau, 2019: 378-385.

[10] YUE Hao-song, MIAO Jin-yu, YU Yue, et al. Robust Loop Closure Detection Based on Bag of SuperPoints and Graph Verification[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Macau, 2019: 3787-3793.

[11] ARANDJELOVIC R, GRONAT P, TORII A, et al. NetVLAD: CNN Architecture for Weakly Supervised Place Recognition[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, 2016: 5297-5307.

[12] NEGRE CARRASCO P L, BONIN-FONT F, OLIVER-CODINA G. Global Image Signature for Visual Loop-Closure Detection[J]. Autonomous Robots, 2016, 40(8): 1403-1417.

[13] FISCHLER M A, BOLLES R C. A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[14] WU Jun-jun, ZHANG Hong, GUAN Yi-sheng. An Efficient Visual Loop Closure Detection Method in a Map of 20 Million Key Locations[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA), Hong Kong, 2014: 861-866.

[15] RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: An Efficient Alternative to SIFT or SURF[C]// Proceedings of IEEE International Conference on Computer Vision, Los Alamitos, 2011: 2564-2571.

[16] SCHLEGEL D, GRISETTI G. Adding Cues to Binary Feature Descriptors for Visual Place Recognition[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA). Montreal, 2019: 5488-5494.

[17] SCHLEGEL D, GRISETTI G. HBST: A Hamming Distance Embedding Binary Search Tree for Visual Place Recognition[J]. IEEE Robotics and Automation, 2018, 3(4): 3741-3748.

[18] CUMMINS M, NEWMAN P. FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance[J]. International Journal of Robotics Research, 2008, 27(6): 647-665.

[19] BLANCO C J L, MORENO D F A, GONZALEZ J J. The Málaga Urban Dataset: High-Rate Stereo and LiDAR in a Realistic Urban Scenario[J]. The International Journal of Robotics Research, 2014, 33(2): 207-214.

[20] SUAREZ I, SFEIR G, BUENAPOSADA J M, et al. BEBLID: Boosted Efficient Binary Local Image Descriptor[J]. Pattern Recogn, 2020, 133: 366-372.

[21] CUMMINS M, NEWMAN P. Appearance-Only SLAM at Large Scale with FAB-MAP 2.0[J]. The International Journal of Robotics Research, 2011, 30(9): 1100-1123.

Loop Detection Method Based on Combined Image Features and Hierarchical Node Search

LI Zhuoa, WEI Guo-liangb, GUAN Qia, HUANG Su-juna, ZHAO Shana

(a.School of Optical Electrical and Computer Engineering b.College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China)

The work aims to propose a loop solution to balance the high precision and high efficiency of loop detection system. A new method based on combined image features and hierarchical nodes search algorithm was proposed. Firstly, a down-sampled binary global feature of the original image and improved ORB local feature were calculated and stored in the image feature database. Secondly, a hierarchical node search algorithm was introduced to search the database for the global feature most similar to the current image feature as a loopback candidate. Finally, the improved ORB features were applied to local feature matching to verify the candidate images and confirm the results of loop detection. The algorithm was validated on three different data sets, and the average time of each loop detection in the test was only 19 ms. The experimental results indicate that the algorithm has reached the advanced level in terms of operation efficiency, precision and recall.

loop detection; global feature; local feature; hierarchical node

TP242

A

1001-3563(2022)05-0257-08

10.19554/j.cnki.1001-3563.2022.05.035

2021-06-16

國家自然科學(xué)基金（61873169）；上海市“科技創(chuàng)新行動(dòng)計(jì)劃”國內(nèi)科技合作項(xiàng)目（20015801100）

李卓（1996—），男，上海理工大學(xué)碩士生，主攻視覺SLAM。

魏國亮（1973—），男，博士，上海理工大學(xué)教授，主要研究方向?yàn)榉蔷€性系統(tǒng)、多智能體協(xié)同控制。