基于組合圖像特征與分層節點搜索的回環檢測方法

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

圖文信息技術

基于組合圖像特征與分層節點搜索的回環檢測方法

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

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

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

回環檢測；全局特征；局部特征；分層節點

通過機器實現自動包裝與運輸已成為現代工廠中降低制造成本的重要方法，vSLAM正是實現這一目標的關鍵技術之一[1]。vSLAM利用相機使機器進行定位與建圖，從而實現工廠的自動化包裝、運輸等環節。系統長時間運行會產生累計誤差，導致所建地圖的精度降低。回環檢測是vSLAM系統中的一個重要環節，它可以確定機器是否返回到先前經過的位置，這種信息對于減小累計誤差，創建正確的地圖和提高地圖的精度具有重要意義。

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

隨著深度學習的快速發展，出現了許多利用深度學習代替傳統方法的回環方案[8]，如Shan An等[9]提出FILD(Fast and incremental loop closure detection)，Yue H等[10]提出的BoSP(Bag of SuperPoints)以及Arandjelovic等[11]提出的基于NetVLAD的方法。此類方法雖然達到了較高的準確率，但過于復雜的特征計算需要強大的計算力，短期內無法在小型平臺如無人機上實時運行。與此同時，基于組合特征的方法也有了進展，Carrasco等[12]提出的Haloc算法利用全局標簽和SIFT特征完成回環檢測，較大地提升了系統準確率。

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

1 算法概述

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

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

2 圖像特征提取

2.1 全局圖像特征

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

2.2 改進ORB特征

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

圖1 回環檢測算法系統框架

圖2 全局圖像特征提取

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

(1)

(2)

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

圖3 特征點尺度對應的二進制字符串

3 分層節點搜索算法

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

算法的分層結構見圖4。檢索過程具體為：在系統運行過程中將歷史圖像在線聚類為若干圖像袋，每個圖像袋內包含若干相似的圖像，稱為二級節點，其中最早出現的圖像稱為一級節點；整個檢索過程分為2層，第1層檢索是在一級節點圖像中找到與當前圖像相似度最高的若干圖像，第2層檢索是從上述一級節點圖像袋內找到與當前圖像相似度最高的若干圖像，并將其作為回環候選。在實驗中這種檢索方法不僅表現出與暴力搜索相當的準確率，且效率更高。

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

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

4 驗證候選圖像

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

圖4 分層節點架構

圖5 分層節點搜索算法的更新與檢索

(3)

5 實驗與評估

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

5.1 算法有效性分析

5.1.1 全局特征維度

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

圖6 數據集中的部分圖像

Fig.6 Some images in dataset

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

5.1.2 SORB特征的有效性

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

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

5.1.3 分層節點搜索算法性能分析

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

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

圖8 SORB特征與ORB特征對應的召回率-準確率曲線

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

5.1.4 動態閾值算法的有效性

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

圖10 不同閾值對應的召回率-準確率曲線

5.2 幾種回環算法對比

選取全局特征維度為480維，連續回環次數為2，倍數為1.5進行試驗，此數據下文中算法表現出最佳性能。文中算法與Haloc、DBoW2、FAB-MAP2[21]以及深度學習方法NetVLAD、BoSP、FILD進行了對比實驗，結果見表1。基于深度學習的方案FILD在New College和Malaga07數據集下表現出最佳性能，方案BoSP在City Center數據集下表現出最佳性能，且大幅領先其他方案。4種傳統方法中，New College數據集下，文中算法與DBoW2性能相近，二者均優于Haloc和FAB-MAP2。另外2個數據集下，文中算法明顯優于其他傳統方案，且性能比早期深度學習方案NetVLAD更好，僅在最大召回率方面不足近2年提出的基于深度學習的BoSP與FILD。

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

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

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

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

注：黑體表明幾種算法中的最優數據

表2 幾種算法的時間消耗

Tab.2 Time consumption of several algorithms ms

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

6 結語

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

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

[1] 李俊. 基于SLAM導航的多目視覺AGV系統設計[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] 劉強, 段富海, 桑勇, 等. 復雜環境下視覺SLAM閉環檢測方法綜述[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] 李少朋, 張濤. 深度學習在視覺SLAM中應用綜述[J]. 空間控制技術與應用, 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

國家自然科學基金（61873169）；上海市“科技創新行動計劃”國內科技合作項目（20015801100）

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

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