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

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

圖文信息技術(shù)

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

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

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

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

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

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

通常，vSLAM中回環(huán)檢測問題可轉(zhuǎn)化為基于內(nèi)容的圖像檢索問題，即在歷史圖像中找到與指定圖像最相似的一幀。傳統(tǒng)圖像檢索方法大致可分為4類；基于全局圖像特征、基于局部圖像特征、基于視覺詞袋方法、基于組合圖像特征[2]。全局特征如Bradley等[3]使用的加權(quán)梯度方向直方圖，Singh等[4]設(shè)計的Gist特征等，其計算、匹配速度較快，但準確率較低。Lowe等[5]提出尺度不變特征變換（Scale-invariant feature transform, SIFT）局部特征，其穩(wěn)定性和準確率有較大提高，但特征提取、匹配太過耗時，無法應(yīng)用于實時回環(huán)檢測系統(tǒng)。Galvez等[6]將局部二值特征BRIEF與詞袋方法組合使用，詞袋模型（Distributed bag of words, DBoW2）使得實時運行的回環(huán)檢測系統(tǒng)成為可能。近年來流行的幾種SLAM算法如ORBSLAM3等[7]都是采用此方法進行回環(huá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的方法。此類方法雖然達到了較高的準確率，但過于復(fù)雜的特征計算需要強大的計算力，短期內(nèi)無法在小型平臺如無人機上實時運行。與此同時，基于組合特征的方法也有了進展，Carrasco等[12]提出的Haloc算法利用全局標簽和SIFT特征完成回環(huán)檢測，較大地提升了系統(tǒng)準確率。

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

1 算法概述

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

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

2 圖像特征提取

2.1 全局圖像特征

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

2.2 改進ORB特征

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

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

圖2 全局圖像特征提取

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

(1)

(2)

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

圖3 特征點尺度對應(yīng)的二進制字符串

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

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

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

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

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

4 驗證候選圖像

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

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

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

(3)

5 實驗與評估

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

5.1 算法有效性分析

5.1.1 全局特征維度

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

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

Fig.6 Some images in dataset

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

5.1.2 SORB特征的有效性

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

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

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

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

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

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

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

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

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

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

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

選取全局特征維度為480維，連續(xù)回環(huán)次數(shù)為2，倍數(shù)為1.5進行試驗，此數(shù)據(jù)下文中算法表現(xiàn)出最佳性能。文中算法與Haloc、DBoW2、FAB-MAP2[21]以及深度學(xué)習(xí)方法NetVLAD、BoSP、FILD進行了對比實驗，結(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個數(shù)據(jù)集下，文中算法明顯優(yōu)于其他傳統(tǒng)方案，且性能比早期深度學(xué)習(xí)方案NetVLAD更好，僅在最大召回率方面不足近2年提出的基于深度學(xué)習(xí)的BoSP與FILD。

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

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

表1 準確率為100%時算法的最大召回率

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

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

表2 幾種算法的時間消耗

Tab.2 Time consumption of several algorithms ms

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

6 結(jié)語

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

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

[1] 李俊. 基于SLAM導(dǎo)航的多目視覺AGV系統(tǒng)設(shè)計[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] 劉強, 段富海, 桑勇, 等. 復(fù)雜環(huán)境下視覺SLAM閉環(huán)檢測方法綜述[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)新行動計劃”國內(nèi)科技合作項目（20015801100）

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

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