基于ORB+PROSAC誤匹配剔除算法的視覺SLAM研究

徐子鋒 石超 王永鋒 陳龍

摘? 要：在視覺SLAM前端特征點匹配過程中，采用RANSAC算法剔除誤匹配特征點存在迭代次數不穩定、效率低、魯棒相差等問題，從而對相機定位產生影響。與ORB算法結合，本文引入一種漸進采樣一致性算法，即PROSAC（Progressive Sampling Consensus），來消除迭代次數不穩定問題。利用Kinect v2相機對改進的RGB-D SLAM算法進行實驗，獲得三維點云地圖和相機軌跡，實現了ORB+PROSAC的誤匹配剔除算法。與ORB+RANSAC的結合方式相對比，本文算法驗證魯棒性更好，實時性更強。

關鍵詞：視覺SLAM;特征點匹配;RANSAC算法;PROSAC算法

中圖分類號：TP391.4? ? ?文獻標識碼：A

Abstract：In the process of feature point matching in the front of visual SLAM，a series of problems have been found when using the RANSAC algorithm to eliminate the mismatched feature points，such as unstable iterations，low efficiency and robust phase difference，resulting in an impact on camera positioning.Combined with the ORB algorithm，this paper introduces a progressive sampling consensus algorithm，PROSAC （Progressive Sampling Consensus），to eliminate the instability of iteration times.Using the Kinect v2 camera with the improved RGB-D SLAM algorithm，the 3D point cloud map and camera trajectory can be obtained in the experiment and the mismatch elimination algorithm of ORB+PROSAC can be realized.Compared with the combination with ORB+RANSAC，the proposed algorithm verifies the robustness better with a stronger real-time performance.

Keywords：visual SLAM;feature point matching;RANSAC algorithm;PROSAC algorithm

1? ?引言（Introduction）

移動機器人的同步定位與地圖構建（Simultaneous Localization and Mapping，SLAM）[1]是實現移動機器人自主定位導航的關鍵技術。視覺SLAM由于傳感器價格低廉，以及所能采集到的信息豐富等特點，越來越多地出現在工業應用中。

視覺SLAM前端系統中，圖像在匹配過程中受到噪聲干擾，會導致特征點的誤匹配，影響相機定位。為了提高視覺SLAM前端特征點匹配的精確性，通常在匹配過程中加入隨機采樣一致性算法，即RANSAC（Random Sampling Consensus）[2]，對誤匹配點進行剔除。RANSAC算法是隨機過程，會導致迭代次數不穩定，且時間開銷大，不能很好滿足實時性要求。另外，現在越來越多的研究人員嘗試著將機器學習的方法加入視覺SLAM前端中，使得圖像匹配更加魯棒，但是需要大量樣本的訓練，計算量也會增加。

視覺SLAM前端圖像匹配既要滿足精確度要求，同時還需要滿足實時性要求。對此，文中提出在圖像匹配過程中引入一種漸進采樣一致性算法，即PROSAC（Progressive Sampling Consensus）[3]，來消除迭代次數不穩定問題，將兩種誤匹配點剔除方式與ORB算法結合對比。利用Kinect v2相機對改進的RGB-D SLAM[4]算法進行實驗，為了使結果更加準確，利用圖優化的方式對相機位姿進行優化，獲得三維點云地圖和相機軌跡，進而證明了ORB+PROSAC算法的優勢。

2? ORB特征點匹配算法（ORB feature point matchingalgorithm）

2.1? ?特征點提取

2.3? ?特征點匹配

如圖2所示為兩張圖片間的特征點匹配，特征匹配解決了SLAM中的前端數據關聯問題。假設在圖像中提取特征點，m=1，2，…，M，在圖像中提取特征點，n=1，2，…，N進行特征點匹配。最簡單的特征匹配方法就是暴力匹配（Brute-Force Matcher），即對每一個特征點，與所有的測量描述子的距離進行排序，取最近的一個作為匹配點。描述子距離表示了兩個特征之間的相似程度，在實際運用中可以取不同的距離度量范數。對于BRIEF描述子，用漢明距離（Hamming distance）[8]為度量。兩個二進制串之間的漢明距離指的是它們不同位數的個數。當特征點數量很大時，暴力匹配法運算量將變大，尤其是當匹配一個幀和一張地圖的時，不能滿足SLAM中的實時性需求，因此可以用快速近似最近鄰（FLANN）[9]算法進行匹配。

3? 基于 PROSAC 的誤匹配剔除算法（Mismatch-based culling algorithm based on PROSAC）

3.1? ?RANSAC算法原理

RANSAC算法用于二維平面上對隨機點進行采樣并擬合出一條直線。具體算法：隨機從二維平面中選取兩個點，將兩點進行連線。設定距離閾值，分別計算平面中其他點和該直線的距離，當距離小于設定閾值時，則被認為是內點;當距離大于設定閾值時，則被認為是外點，不斷重復隨機采樣的過程，找出所有最佳距離點，擬合成直線，如圖3所示為RANSAC隨機采樣過程。

3.2? ?PROSAC算法原理

RANSAC算法中選取的樣本點是隨機的，需要不斷的迭代才能選取出盡量多的內點，因此整個計算過程時間增加，迭代次數不穩定。PROSAC算法和RANSAC算法有所不同，首先是將樣本點進行預排序，篩選出符合的樣本點，然后對匹配模型進行估計。這樣減少模型的迭代次數，且模型正確率高。在二維平面隨機點擬合直線過程中，首先將樣本集中點部分分為兩個部分，在進行距離閾值設定，選取最佳內點，從而最后擬合出最佳直線，如圖4所示為PROSAC隨機采樣過程。

3.3? ?ORB+PROSAC與ORB+RANSAC特征點檢測實驗

為了驗證ORB算法分別和RANSAC算法和PROSAC算法結合的有效性，運用OpenCV工具進行對比實驗。實驗結果如圖6—圖10所示。

4? 基于RGB-D傳感器的3D SLAM（3D SLAM based on RGB-D sensor）

4.1? ?幀間相機運動恢復

完成特征提取與匹配之后，可根據已經匹配的特征對相機進行運動估計[13]。根據特征的信息的不同，可以分為2D坐標信息和3D坐標信息。2D坐標信息可以從圖像中直接獲取，3D坐標深度信息可以通過其他方式獲取，單雙目相機可以通過三角化的方法獲取，RGB-D傳感器可以直接通過深度圖像與RGB圖像配準獲得。求解相機運動有三種方式：2D-2D、3D-2D和3D-3D。2D-2D相機位姿估計計算兩幀圖像之間的本質矩陣，通過構建最小二乘法和SVD分解方法將本質矩陣分解，求解R和t，再乘計算的t的相對尺度，最終獲得相機運動。本質矩陣有五個自由度，三個旋轉加上三個平移，減去一個尺度化因子。本質矩陣的計算至少需要五組圖像對應點，通常采用五點算法和八點算法計算。3D-2D的方法是最小化重投影誤差的方法計算，而3D-3D的方法則是最小化三維位姿誤差，因此3D-2D方法比3D-3D方法更精確，最小化重投影誤差的形式是為了找到式（9）中最小的Tk：

4.2? ?ICP算法

迭代最鄰近點（Iterative Closest Points，ICP）算法常用于對齊兩組點云。假設存在兩組名為Pr和Pl的點云，通過計算方程的最小值來獲得兩組點云的剛性變換，為了計算使方程最小的旋轉和平移矩陣R和t，在兩組點云Pr和Pl中根據一定的約束條件，尋找最鄰近點，然后計算最優匹配參數R和t，則誤差函數為：

4.3? ?位姿優化

傳統的SLAM基于濾波和非線性優化的方式進行優化，效率較低。引入圖優化[14]方式的優化方法可以完成相機局部和全局的位姿優化。圖由節點和邊組，pose節點代表相機位姿，point節點代表相機觀測到的路標點，邊代表兩個節點間的約束。完全構建圖后，應調整相機的姿勢以滿足邊界約束。用誤差函數表達兩個節點滿足約束的程度。基于圖優化的SLAM系統分為兩個模塊，即前端和后端。在前端中，需要從傳感器數據中提取幾何約束，并解決數據關聯的問題。最后，構造圖結構的節點和邊。在后端模塊中，尋找狀態向量，該狀態向量可以使幾何約束的似然函數最大化。將SLAM抽象成圖的形式之后節點表示待優化變量，邊表示誤差項約束條件，包括相機節點間約束，以及相機位姿和路標點的約束。前者依賴于系統閉環檢測產生的約束，如圖12和圖13所示。后者依賴于相機對路標點觀測產生的約束，如圖11所示。通過構建圖優化的方式可以縮小系統的誤差累積，從而構建信息一致的地圖。

4.4? ?地圖構建

地圖的構建[15]可以分為局部地圖和全局地圖兩種。局部地圖保留了當前位置附近特征點信息，這些特征點用來與當前幀進行匹配求解當前相機位姿，隨著相機的運動新的幀不斷被加進來，數據維護將會變大，因此需要丟棄之前的幀以保證系統實時性。全局地圖則是記錄所有特征點的信息，后期通過地圖的加載和匹配可用于機器人的定位導航和路徑規劃。系統在傳感器數據中提取關鍵幀，估計關鍵幀匹配關系。可以用（Bundle Adjustment，BA）方式優化關鍵幀匹配點的重投影誤差，由于地圖點和關鍵幀是冗余的，需要對關鍵幀進行剔除，才能獲得魯棒的地圖。到目前為止，已經可以獲得全局一致的相機軌跡，通過引入深度信息，跟蹤在全局3D坐標系中投影所有測量點坐標，可生成環境的點云地圖。

5? ?基于kinect v2的 SLAM實驗設計與分析（Design?and analysis of SLAM experiment based onkinect v2）

5.1? ?基于ORB+PROSAC特征提取的SLAM系統框架

如圖14所示為RGB-D SLAM系統框架，共五個主要模塊，包括特征檢測、運動估計、ICP算法、基于圖優化的位姿優化和地圖構建。利用Kinect傳感器獲取深度圖像和RGB圖像，使用ORB算法進行特征檢測，同時利用PROSAC算法在圖像特征點匹配中剔除外點，獲得更精確的匹配點，準確估計相機運動。為了獲得相機的全局最優姿態和環境地圖，通過將圖優化方法應用于系統，提取深度信息，可生成實驗室環境3D點云地圖。

5.2? ?實驗硬件平臺

為檢驗ORB+PROSAC特征點匹配算法實際運行效果，使用事先標定好的Kinect V2相機，以及內存4GB、CPU為Intel i5 4210M、2.6GHz、顯卡為Intel HD4600集成顯卡筆記本電腦作為硬件平臺，在實驗室環境下對算法進行實際測試。如圖15所示為Kinect V2相機。

5.3? ?實驗結果及分析

由于缺少外部設備對相機進行跟蹤，無法計算得到各時刻相機位置與真實相機位置之間的誤差。從運行結果來看，RGB-D SLAM算法能夠很好地進行初始化，且高效實時運行，如圖16所示相機在特征點跟蹤階段比較穩定，無丟幀或者失幀的情況。此外，在回環檢測階段能夠對相機軌跡進行全局調整，配準傳感器深度信息，建立如圖17和圖18所示實驗室環境特征點地圖和3D點云地圖，因此實驗證明ORB+PROSAC方式效率高，魯棒性好。

6? ?結論（Conclusion）

本文從RANSAC算法和PROSAC算法的對比分析入手，理論分析可知RANSAC算法迭代次數不穩定、匹配效率低，PROSAC算法引入了質量因子，通過質量因子分級質量好的內點用于估計模型的方式，可減少算法的迭代次數、降低計算和時間復雜度。通過ORB特征點匹配結合兩種算法實驗對比，得出PROSAC算法優于RANSAC算法。用Kinect v2相機對改進的RGB-D SLAM算法進行實際運行，獲得三維點云地圖和相機軌跡，進而驗證了ORB+PROSAC算法在視覺SLAM的應用魯棒性好，實時性強。

參考文獻（References）

[1] Mur-Artal R，Montiel J M M，Tardós J D.ORB-SLAM：A Versatile and Accurate Monocular SLAM System[J].IEEE Transactions on Robotics，2017，31（05）：1147-1163.

[2] Bahraini MS，Bozorg M，RadAB.SLAM in dynamic environments via ML-RANSAC[J].Mechatronics，2018，49（08）：105-118.

[3] Panpan Z，Derui D，Yongxiong W，et al.An improved GMS-PROSAC algorithm for image mismatch elimination[J].Systems Science & Control Engineering，2018，6（01）：220-229.

[4] Ma L，Kerl C，Stuckler J，et al.CPA-SLAM：Consistent plane-model alignment for direct RGB-D SLAM[C].2016 IEEE International Conference on Robotics and Automation（ICRA）.IEEE，2016，8（02）：120-124.

[5] 吳金津，王鵬程，龍永新.基于FAST角點檢測的圖像配準算法[J].湖南工業大學學報，2014，28（04）：71-75.

[6] 張陽，許鋼，張星宇.一種改進的ORB特征點匹配算法[J].重慶工商大學學報（自然科學版），2018，179（03）：73-78.

[7] 高翔，張濤.視覺SLAM十四講：從理論到實踐[M].北京：電子工業出版社，2017：133-182.

[8] 邸凱昌，萬文輝，趙紅穎.視覺SLAM技術的進展與應用[J].測繪學報，2018，47（06）：84-93.

[9] 許芬，王振.基于Kinect傳感器和ORB特征的視覺SLAM算法設計與實現[J].計算機工程與科學，2018，40（05）：76-81.

[10] 邢凱盛，凌有鑄，陳孟元.ORB特征匹配的誤匹配點剔除算法研究[J].電子測量與儀器學報，2016，30（08）：1255-1262.

[11] 鄭顧平，閆勃勃，李剛.基于機器學習的多車牌識別算法應用研究[J].計算機技術與發展，2018，254（06）：135-138.

[12] 李倫.基于PROSAC算法的室內定位算法研究[D].哈爾濱：哈爾濱工業大學，2018：36-50.

[13] 辛冠希.基于RGB-D攝像機的同步定位與建圖研究[D].哈爾濱：哈爾濱工業大學，2016：29-54.

[14] 張毅，沙建松.基于圖優化的移動機器人視覺SLAM[J].智能系統學報，2018，13（02）：290-295.

[15] 楊林志.基于視覺的移動機器人SLAM算法研究[D].成都：西南交通大學，2018：42-66.