視覺SLAM中ORB配準算法的研究

李艷山，劉智，李攀，周玉軒，王世凱

（長春理工大學 電子信息工程學院，長春 130022）

SLAM技術是實現(xiàn)移動機器人在未知環(huán)境中自主定位和導航的關鍵技術，V-SLAM技術則使用移動機器人搭載的相機采集的圖像作為唯一的觀測信息于運動過程中估計自身的軌跡，同時構建出環(huán)境的模型［1］。一個完整的V-SLAM算法框架包括圖像的采集、局部相機軌跡和地圖的估計、全局相機軌跡和地圖的優(yōu)化三部分。其中局部相機軌跡和地圖的估計主要采用圖像特征點法和直接法來實現(xiàn)。由于圖像特征點法具有運行穩(wěn)定、對外界干擾（光照、噪聲、旋轉、尺度等）具有良好的穩(wěn)定性［2］。因此，越來越多的V-SLAM研究者采用基于圖像的特征點的方法來完成圖像的預處理。最早，Lowe提出了尺度不變特征變換（Scale-Invariant Feature Transform，SIFT）算法［3］，該算法充分考慮了特征點在圖像尺度變化過程中的魯棒性，保證了特征點在圖像尺度變化過程中配準的準確率。完文韜等人在2018年提出了一種改進的SIFT算法［4］，該算法有效的剔除圖像配準過程中的誤匹配點對。但是，以上算法均很難滿足V-SLAM的實時性要求。Bay等人在2016年提出了加速魯棒特征（Speed-Up Robust Feature，SU-RF）算法［5］，該算法主要解決SIFT算法中存在的計算量過大問題。張鳳晶等人在2016年提出了改進的SURF算法［6］，該算法在不增加配準的時間前提下，提高了配準的精確度。夏巖等人在2017年提出了改進的SURF算法［7］，該算法提升了圖像配準的成功率，同時縮短了配準的時間。但是，SIFT和SURF算法在V-SLAM中仍然需要一定的計算量，目前普通PC機的CPU難以進行實時的定位與建圖，可以通過GPU進行加速計算，但是引入GPU將帶來整個SLAM成本的提高。Rublee等人在2011年ICCV的論文中提出了基于FAST（Feature from Accelerated Segment Test）［8-9］特征點提取和BRIEF（Binary Robust Independent Elementary Feature）［10］特征描述，稱之為ORB（Oriented FAST and Rotated BRIEF）算法［11］，該算法和SURF、SIFT算法相比，其計算速度具有大幅度的提升。

ORB算法改進了FAST特征點提取算法，在原版FAST的基礎上計算了特征點的主方向，使提取出來的特征點增加了旋轉不變性。ORB算法主要通過檢測局部像素灰度差異值來提取特征點，同時對特征點增加了的二進制描述子BRIEF，目前廣泛的應用于實時性較高的V-SLAM系統(tǒng)中。然而，針對ORB算法在特征點提取時存在效率低下、隨機采樣一致性（Random Sample Consensus，RANSAC）［12］在特征點配準中存在耗時過長的問題，將導致V-SLAM系統(tǒng)的實時性及準確性大幅度下降。因此，本文在對ORB配準算法進行理論分析的基礎上提出了一種改進版的ORB配準算法。首先，將介紹V-SLAM算法的整體流程及原ORB算法，包括特征點的提取及描述子計算方法。然后，分別提出了ORB和RANSAC的改進算法。最后，通過實驗驗證，改進的ORB配準算法比原算法更加高效、魯棒。

1 V-SLAM整體流程及ORB配準算法

1.1 V-SLAM整體流程

在基于特征點法的整個V-SLAM過程中，首先對采集到的圖像進行預處理，主要為圖像的特征點提取與配準。然后，根據(jù)相鄰圖像之間的配準點來估計局部相機的運動軌跡及構建局部地圖，然而僅僅通過累加原理來構建出全局的相機運動軌跡及全局地圖，將不可避免出現(xiàn)累計誤差。非線性優(yōu)化部分采用Bundle adjustment（BA）算法［13］對相機位姿估計值、局部地圖和閉環(huán)檢測結果進行優(yōu)化，從而得到全局一致的相機位姿軌跡和地圖?；谔卣鼽c法的V-SLAM總體算法框架如圖1所示。

圖1 基于特征點法的V-SLAM總體算法框架

基于ORB算法的圖像預處理的過程主要包括以下三個階段：FAST特征點的提取過程，提取圖像中的特征點位于什么位置；BRIEF描述子計算過程，對特征點周圍的像素信息進行描述；特征點的配準過程，根據(jù)相近的特征點具有相近的描述子的原則，采用漢明距離結合RANSAC算法對所提取到的特征點進行精確的配準。基于ORB算法的圖像預處理過程如圖2所示。

圖2 基于ORB算法的圖像預處理過程

1.2 ORB特征點提取

在ORB算法中，使用FAST對特征點進行提取。由于FAST不具有旋轉不變性，因此在ORB算法中對FAST檢測子進行改進增加了旋轉不變性，稱為（Oriented FAST，oFAST）。FAST特征點提取思想：若圖像中局部區(qū)域像素灰度出現(xiàn)明顯變化（過亮或者過暗），則將該像素點定義為候選特征點，F(xiàn)AST特征點提取示意圖如圖3所示。

圖3 FAST特征點提取示意圖

FAST算法檢測特征點過程如下：

（1）圖像特征點提取。在圖像中選取任意一個像素P，它的灰度值為Ip。設定一個合適的閾值。以像素P為中心，設置半徑為3的一個離散化Bresenham圓，選取圓周上的16個像素點。如果圓上序號為1，5，9，13的像素亮度有3個同時都大于Ip+t或者小于Ip-t，則判定P可能為一個特征點，進行第2步，否則丟棄該點P。

（2）進一步判定圓上的12個連續(xù)的像素亮度值是否都大于Ip+t或者小于Ip-t，如成立則判定P為一個特征點，進行第3步，否則丟棄該點P。

（3）計算提取到特征點的Harris響應值并排序，選擇前N個最大響應值作為最終特征點的集合。

（4）采用灰度質(zhì)心法對提取到的特征點進行描述，增加特征點的旋轉不變性。首先，圖像塊的矩定義如式（1）所示：

其中，I(x,y)為點(x,y)處的灰度值，p+q為灰度矩的階數(shù)。要求x和y都在半徑為r的圓形區(qū)域內(nèi)，即x,y∈[-r,r].

通過圖像塊的矩，求出圖像塊的質(zhì)心如式（2）所示：

連接圖像塊的幾何中心O與質(zhì)心C，得到一個方向向量，特征點的方向定義如式（3）所示：

（5）循環(huán)以上5步，對每一個像素執(zhí)行相同的操作。

1.3 特征點描述子

ORB算法采用BRIEF描述子對提取到的特征點像素信息進行描述。BRIEF描述子描述方法為在特征點周圍挑選指定數(shù)量的像素點對，通過比較相應的灰度值，利用一系列的0和1組合編碼成以二進制形式描述特征。

對于一個光滑圖像領域p的準則τ定義如式（4）所示：

其中，p(x)為平滑后的圖像領域p在x處的灰度值，則特征可以被定義為n維二進制向量如式（5）所示：

其中，n可以為128、256、521等。n值大小的選取可以根據(jù)存儲效率、識別率和速度的要求進行相應的選擇。

由于BRIEF描述子不具有旋轉不變性，因此對其進行改進并添加一個方向信息，稱為rBRIEF。在位置(xi,yi)處，對任意的n個二進制特征，定義矩陣S如式（6）所示：

利用此區(qū)域的旋轉方向θ和對應的旋轉矩陣Rθ，對S進行變換如式（7）所示：

于是矯正后的BRIEF描述子為如式（8）所示：

得到校正的BRIEF之后，再進行貪婪搜索，在像素塊中找出相關性最低的256個像素塊對，作為最終的BRIEF。

2 ORB配準算法改進

2.1 ORB配準算法改進的總體思想

本文對ORB特征點的提取及配準算法分別進行改進，首先對待檢測的圖像采用區(qū)域二分法加速判斷特征點在圖像中的位置，然后對檢測出來的特征點依次構建圖像金字塔及引入灰度質(zhì)心法以增加特征點的尺度不變性以及旋轉不變性，最后采用改進的RANSAC配準算法剔除誤匹配點對。改進的ORB配準算法整體流程如圖4所示。

圖4 改進的ORB配準算法整體流程圖

2.2 FAST特征點提取算法改進方法

在特征點配準過程中，將相鄰兩張圖像的非重疊區(qū)域視為無效區(qū)域，在無效區(qū)域中進行特征點的提取及配準是不正確的。如果在提取特征點時去除在無效區(qū)域的特征點提取、計算描述子及特征點匹配的時間，可以大大加速ORB算法的配準時間，從而提升V-SLAM算法框架的實時性。基于以上思想，提出FAST特征點提取的改進方法。首先，在特征點提取時對待提取的圖像區(qū)域進行劃分，將待提取特征點的圖像均勻分成2個區(qū)域，并且進行分組編號。例如使用ORB算法提取一幀圖像特征點的時間為T，則使用區(qū)域二分處理之后每塊區(qū)域的特征點提取時間為t=T2，完成整幀圖像的特征點配準所需要的時間t1為：

因為t1＜2T，即提取每幀圖像特征點的時間減少了25%。假設兩幀圖像的重疊率為x，可提高的效率為y，則：

所以不管x取值是多少，y的值總是不小于50%。即在ORB特征點提取過程中，采用區(qū)域二分法，特征點提取至少提高效率50%以上。

2.3 RANSAC算法改進方法

傳統(tǒng)的RANSAC算法在剔除ORB特征點誤匹配時沒有考慮配準點的質(zhì)量好壞便隨機抽取，將提取出來的所有特征點都進行了迭代計算，導致特征點在配準過程中消耗了大量的時間?；诖藛栴}，提出改進算法，將隨機抽樣的樣本進行一次篩選，把明顯錯誤的匹配對剔除，減少RANSAC的迭代次數(shù)。改進的RANSAC算法流程圖如圖5所示。

改進的RANSAC算法步驟如下：

（1）左圖中提取到的特征點記作集合X={xi|xi∈X,i=1,2,...,n}，與之對應的右圖提取到的特征點記作集合Y={yi|yi∈Y,i=1,2,...,n}

（2）對集合X，Y中提取的特征點采用雙向匹配交叉過濾方法對配準對進行篩選，過程如下：對集合X中的每個特征點xi找到集合Y中與之對應的特征點yi，同理，對集合Y中的每個特征點yi找到集合中X與之對應的特征點xi；同時引入逆向匹配機制，如果X中的特征點xi在Y中的匹配點為yi，且Y中的特征點yi在X中的匹配點為xi，則認為這對匹配對是正確的，如果匹配不成功，則直接剔除掉。

（3）設置一個描述子漢明距離的閾值，對篩選之后的配準點對進行漢明距離計算并排序，對漢明距離值大于設置的閾值的配準點對剔除。

（4）經(jīng)過以上兩步剔除誤匹配之后，再使用RANSAC算法進行迭代配準特征點，從而得到更加準確的配準點對。

圖5 改進的RANSAC算法流程圖

3 實驗結果及分析

3.1 實驗安排

本節(jié)將改進的算法和原算法進行實驗對比。實驗環(huán)境：Ubuntu16.04操作系統(tǒng)，安裝了OpenCV 3.1.0［14］。主要實驗為：改進的FAST特征點提取算法對比實驗和改進的RANSAC算法對比實驗，并對實驗結果進行比較和分析。為了驗證本文提出的改進算法對環(huán)境具有普遍性、通用性，分別選取了室外場景和室內(nèi)場景圖片進行實驗驗證。

3.2 FAST特征點提取改進算法對比實驗

為了驗證本文提出的改進的FAST特征點提取算法的高效性，將分別選取像素大小為800×500的兩幅室外和室內(nèi)圖片進行實驗。首先，使用改進的FAST算法對采集到的圖像進行特征點提取。然后，將改進算法與原算法提取到同一幀圖像的特征點所用時間進行對比。圖6所示為改進的FAST算法特征點提取室外場景圖，圖7所示為改進的FAST算法特征點提取室內(nèi)場景圖。

圖6 改進FAST算法特征點提取室外場景圖

圖7 改進FAST算法特征點提取室內(nèi)場景圖

表1 FAST特征點提取算法耗時對比

表1為原FAST特征點提取算法和本文改進的FAST特征點提取算法處理同一幀圖像特征點所用的時間對比。可以發(fā)現(xiàn)，使用改進的算法進行特征點提取時，處理的時間明顯縮短，特征點提取效率提升40%左右。按照理論部分的結論，使用改進的算法提取特征點時，提取效率至少能提高50%，其主要原因在改進的FAST特征點提取算法中構建了圖像金字塔以增加特征點的尺度不變性，浪費了一定的時間。實驗表明，使用改進的FAST特征點提取算法可以大大提升特征點提取的速度。

3.3 RANSAC改進算法對比實驗

為了驗證本文提出的RANSAC改進算法對圖像配準的高效性及準確性。選取像素大小為410×320的四幅室外和室內(nèi)圖片分別進行配準實驗。首先，對待配準圖像進行采集。圖8（a）為待配準室外場景的左幀圖像，圖8（b）為待配準室外場景的右?guī)瑘D像。圖9（a）為待配準室內(nèi)場景的左幀圖像，圖9（b）為待配準室內(nèi)場景的右?guī)瑘D像。其次，使用原FAST特征提取算法結合暴力匹配算法對采集到的室外和室內(nèi)相鄰場景圖像分別進行特征點提取與配準。圖10所示為原FAST算法結合暴力匹配算法的室外場景配準圖，圖11所示為原FAST算法結合暴力匹配算法的室內(nèi)場景配準圖?？梢园l(fā)現(xiàn)，暴力匹配算法將導致圖像配準過程中出現(xiàn)大量的誤匹配。然后，引入RANSAC算法剔除圖像配準過程中出現(xiàn)的大量誤匹配。圖12所示為引入RANSAC算法的室外場景配準圖，圖13所示為引入RANSAC算法的室內(nèi)場景配準圖?？梢园l(fā)現(xiàn)，RANSAC算法可以有效的剔除暴力匹配中出現(xiàn)的大量的誤匹配，但是還會存在少量的誤匹配。最后，使用改進的FAST特征提取算法結合改進的RANSAC算法對采集到的室外和室內(nèi)相鄰場景圖像分別進行特征點提取與配準。圖14所示為改進的FAST算法結合改進的RANSAC算法的室外場景配準圖，圖15所示為改進的FAST算法結合改進的RANSAC算法的室內(nèi)場景配準圖。可以發(fā)現(xiàn)，使用改進的RANSAC算法可以進一步剔除原RANSAC算法遺留的誤匹配對，進一步提升圖像配準的準確性。同時，將改進的算法與原算法處理同一對圖像的配準點集對數(shù)、剔誤率、配準時間進行對比。

圖8 室外場景待配準原始圖像

圖9 室內(nèi)場景待配準原始圖像

圖10 FAST+暴力匹配算法室外場景準圖

圖11 FAST+暴力匹配算法室內(nèi)場景準圖

圖12 FAST+RANSAC算法室外場景配準圖

圖13 FAST+RANSAC算法室內(nèi)場景配準圖

圖14 改進FAST+改進RANSAC算法室外場景配準圖

圖15 改進FAST+改進RANSAC算法室內(nèi)場景配準圖

表2 室外場景配準算法結果對比

表3 室內(nèi)場景配準算法結果對比

表2為FAST特征點提取算法結合暴力匹配算法、FAST特征點提取算法結合RANSAC算法、本文改進的FAST特征點提取算法結合改進RANSAC算法對采集到的室外場景圖像進行配準結果的對比。表3為暴力匹配算法、FAST特征點提取算法結合原始RANSAC算法、本文改進FAST特征點提取算法結合改進RANSAC算法對采集到的室內(nèi)場景圖像進行配準的結果對比?？梢园l(fā)現(xiàn)，使用改進的FAST特征點提取算法結合改進的RANSAC算法進行圖像配準時，雖然最終得到的配準點集個數(shù)略有減少，但是更有效地剔除了配準過程中出現(xiàn)的誤匹配。在提升配準速度的同時，大大提升了配準的精確度。實驗表明，使用改進的FAST特征點提取算法結合改進RANSAC的算法進行圖像配準時，可以提升配準速度，同時能夠有效地剔除誤匹配，保證了配準點對的準確性。

4 結論

本文提出了一種改進的ORB圖像配準算法。在原有算法的基礎上，首先采用二分區(qū)域法對提取圖像特征點時進行預處理，之后使用改進的RANSAC迭代算法完成特征點匹配。通過實驗結果表明，改進的ORB配準算法在保證配準特征點數(shù)量相當?shù)耐瑫r可以有效地剔除誤匹配，保證了配準點集之間的準確性，同時提升了配準的速度。其改進的ORB算法給V-SLAM中的位姿估計算法提供了良好的初始值，其結果有助于提升V-SLAM系統(tǒng)的實時性和位姿估計及建圖的準確性。ORB配準算法仍有許多難點，如特征點較少圖像之間的配準、尺度變化圖像之間的配準、旋轉變化圖像之間的配準等，這些難點還有待深入研究。