一種改進的ORB算法

潘 盼

(上海海事大學 信息工程學院，上海 201703)

一種改進的ORB算法

潘 盼

(上海海事大學 信息工程學院，上海 201703)

針對目前SLAM算法對特征提取的可靠性和魯棒性要求越來越高的問題，基于ORB(二進制定向簡單描述符)特征提取算法，提出了一種基于模塊化區域分割的方法，解決了特征提取過程中提取無效特征點過多和特征點分布不均勻的矛盾。該方法使得ORB算法的特征提取更加均勻和合理，也更有利于圖像的特征匹配。實驗研究表明，該方法提高了算法的有效性和可靠性。

ORB；模塊分割；特征匹配

0 引言

研究表明，基于特征的圖像匹配方法越來越受到人們的重視，特別是在視覺SLAM(Simultaneous Localization And Mapping)[1]領域更是成為不可或缺的關鍵技術。其在移動機器人導航[2]、運動識別、三維立體重建等方面都有極為廣泛的應用。

在眾多特征匹配的方法中，SIFT(Scale Invariant Feature Transform)[3]算法一直占據著主流的地位，雖然其在抗噪聲、光照以及尺度變化等方面表現出良好的魯棒性，但巨大的運算開銷也使它的實時性大打折扣。隨后基于SIFT的加速魯棒性特征(Speed-Up Robust Feature,SURF)[4]的出現，簡化了算法并且大大提升了特征點匹配的計算速度和魯棒性。隨著特征點提取在視覺各個領域的廣泛應用，RUBLEE E等人提出基于FAST[5](Features from Accelerated Segment Test)和BRIEF[6](Binary Robust Independent Elementary Features)方法的ORB[7](Orineted FAST and Rotated,BRIEF)算法。該算法在魯棒性和有效性方面表現優異。雖然有這么多不同特征點提取算法，但在視覺SLAM系統中如何選擇依然是個需要慎重考慮的問題。因此本文通過實驗對比不同的算法的有效性和魯棒性，并依據實際的SLAM應用提出一種改進的ORB算法，同時驗證其可靠性。

1 ORB算法原理

1.1 ORB算法流程

特征點提取步驟如下：

(1)利用FAST方法提取圖片中的特征信息。

(2)利用Harris方法對上一步提取的特征點排序。

(3)構造圖像金字塔，然后對金字塔的每一層搜索FAST特征點。

(4)應用灰度質心方法定位。

特征描述子：實際上ORB算法采用的是具有旋轉不變性的BRIEF也即rBRIEF。其主要思想是依據灰度值的大小選取某個特征點附近的幾個像素點對，構成二進制編碼的算子，即為該點的特征描述子。

特征點的匹配：ORB算法獲得所有特征點的信息和特征描述子，然后計算成對的兩幅圖的所有特征點之間的向量間的漢明距離[8]，若滿足一定的條件(例如求最短的漢明距與次短漢明距)，當這兩個數值的比不大于0.8且長度都不大于50時，則認為這對特征點滿足匹配條件。算法流程如圖1所示。

1.1.1FAST特征點提取

ORB使用FAST方法來搜索圖像中的特征點。而FAST提取方法的核心思想是：基于加速分割測試特性，如圖像中某像素點與其相鄰區域內擁有足夠多不同特征時，就認為該點為特征點，一般可以將大于總數3/4的點判為角點。

FAST算法提取的步驟：

(1)選取圖像中像素點K，將該點像素值設為Kp，然后判斷該點是否為特征點。

(2)給定一個經驗閾值T，本文設為9。

(3)考慮將該點設為圓心，以3像素為半徑構造一個包含16個像素N個連續像素點的離散化圓，如圖2所示。

圖2 FAST角點檢測

(4)采用決策樹ID3算法[9]構造三叉樹，快速剔除掉偽角點，對于像素點K，設其鄰域的16個點位置為t，t∈{1…16}的點標記為K→t，依據下列計算公式將該點分為三類：

(1)

簡單來說該步驟就是先計算1、5、9、13這4個具有代表性的像素點，首先檢查上下兩個點，若它們都比閾值大或比閾值小，再檢查左右兩個位置的點，至少3個滿足閾值條件，也就是絕對值大于T，才進行候補點的檢測，如不滿足上面的條件則把這個點剔除掉。

從上述方法可以看出，相對于其他特征點提取方法，FAST的提取方法計算速度快，可以應用到實時場景中。但FAST方法并沒有對特征點進行描述子計算，因此不具備尺度和旋轉不變的性質，在復雜的場景中并不會直接拿來應用。

雖然FAST角點提取算法相比于其他提取算法效率更高，但不能很好地適應旋轉變化，ORB算法通過強度中心方法為FAST特征點計算一個主方向。首先在像素點局部區域確定強度中心，然后從像素點K到強度中心構造方向向量，如圖3所示。

圖3 強度中心

假設圖像中區域塊的階數(Moments)為：

(2)

式中用I(x,y)表示圖片某點處的灰度值，p和q等于0或者等于1。半徑為r的圖像中求得其強度中心C為:

(3)

其中m00為零階矩，m01m10為一階矩。

求得點O與中心點C夾角為該點的主方向,用以下公式計算：

θ=arctan 2(m01,m10)

(4)

1.1.2BRIEF特征描述子

ORB算法采用rBRIEF來構造特征描述子，其實質內容為：以FAST方法得出的特征點為中心，隨機選取附近若干像素的點對。利用高斯二元分布對每個點對進行像素的灰度變化二值化比較，也即大于為1小于為0。將比較結果存為一個二進制串。生成指定次數位的二進制串，就得到BRIEF的描述。具體步驟如下：

(1)定義一個經過高斯分布處理的圖像鄰域B，其對應的描述子準測函數τ為：

(5)

其中B(x)為鄰域x位置的灰度函數。

(2)選取n對(xi,yi)測試點對，由此唯一確定了一個二進制串：

(6)

(3)為了使生成的不具有方向的描述子具備旋轉不變性，將前面求得的特征點質心方向添加到描述子中。隨機選取(xi,yi)則可以定義一個2×n的矩陣Q：

(7)

式中(xi,yi)為測試點對。

得到該點方向θ相應的矩陣Rθ，構造點對的矩陣：

Qθ=RθQ

(8)

最終特征點的描述算子為：

gn(B,θ)=fn(B)|(xi,yi)∈Qθ

(9)

(4)因為ORB對噪聲敏感，所以普遍采用在31×31的窗口搜索5×5子窗口像素灰度平均值代替該處灰度值。即找出像素點對相關性最小的塊構成所需的特征描述子。具體步驟如下：

(1)在某個像素鄰域內計算點對測試值τ，對所有的τ計算與其距離為0.5的點，并排序形成向量S。

(2)貪婪法逐步搜索。

①首先將第一個τ值帶入R中，并從S中剔除；

②然后將向量S下一個值與R中所有值比較。將相關度高的丟棄，否則就添加到生成描述子；

③重復以上幾個步驟直到最終向量S中有256個坐標時，特征描述子則構造完成。將相關度閾值增加，再次構造。保證最終描述子有較低的相關性。

1.1.3特征點匹配

特征匹配被廣泛應用在圖像識別等眾多領域，已成為計算機視覺研究中最常用的處理方法。在視覺SLAM中為了更好地進行位姿估計、閉環檢測[10]等，需要對生成的特征描述子進行匹配與跟蹤。相比于SIFT和SURF用歐式距離進行描述，這里計算歐式距離然后作為評價準則從而得到相距最近的作為相似的一對。

ORB利用二值字符特征點描述的漢明距離作為評價標準，選出漢明距離最小的作為相似的一對。由上節得到ORB的n=256維二進制描述算子，隨機選取K1、K2兩幅圖像的描述算子：

K1=x0x1…xn，K2=y0y1…yn

(10)

ORB的描述子相似度用漢明距離做異或運算然后求和來表示，記為D(K1，K2)：

(11)

其中D(K1,K2)越小則表明特征點對相似程度越高。因為只在同位置進行求異或運算，計算漢明距離遠沒有計算歐式距離復雜。ORB二值特征描述子在匹配上擁有更大的優勢，同時，將應用模型估計中常用的RANSAC(Random Sample Consensus)[11]方法進行外點誤匹配剔除。選取兩幅圖像進行比較，三種不同方法得到的結果對比如圖4所示，其中圖(d)通過RANSAC方法消除了外點，盡管匹配的數目有所減少，但是正確率顯著提高了。

圖4 特征匹配結果

1.2 ORB特征提取算法的優化

視覺SLAM運動估計的正確性往往取決于算法所獲取到的特征數目，同時也依賴于特征點在整張圖片中的位置。一般來說特征越多估計越精確，特征越少估計越不準確，嚴重的甚至會導致算法失效。而在實際中，過多的特征點意味著計算量的增大，這對實時性的影響不可忽視。因此應盡可能在提取到足夠多的特征點的情況下，保證特征點能均勻地分布在這個圖像中。為達到實際應用的要求，本文設計一種區域模塊分割的ORB特征提取算法，步驟如下：

(1)將得到的圖像分割成大小均勻的模塊化子區域，稱之為柵格(Grid)。在這里將圖像劃分成M×N個子區域，也就是柵格。這樣圖片區域中的特征點信息會隨機分布。將柵格先行后列排序表示為{h1,h2,h3,…,hm}。

(2)將檢測不到特征點的柵格hi設為不感興趣區域，且在后面檢測中不再考慮該區域。將檢測到nj個候選點的柵格hj設為感興趣。判斷nj與j的大小(j的設置依據經驗值，這里設為5)，如果前者不大于后者則將子區域的候選特征點設為檢測點；若前者大于后者，再進一步做Harris[12]角點檢測排序操作，選出表現最好的j個點。其余的作為候選檢測點ki。

基于上述方法的ORB特征提取算法的優點可總結為：

(1)每個選擇的特征點都是子區域中表現最優的特征點。

(2)選取特征點的數量可根據實際應用靈活變化。

(3)最終選取出的點盡量平均分布在整張圖片的區域中。

2 實驗結果與分析

本文實驗是在Windows 7 + OpenCV2.4.9平臺上實現的，采用的原始圖像如圖5所示，像素大小640×480，圖像格式為.bmp。

圖5 原始參考圖像

未優化的ORB特征提取結果見圖6。最終的優化過的ORB特征提取如圖7所示。由圖可得,相比于圖6，由于進行了Harris方法的二次排序，圖7避免了選取到性能較差的特征點；優化后的提取結果更加均勻，也更具代表性。

圖6 ORB特征提取示意圖

圖7 優化后的ORB特征提取示意圖

速度測試：算法的耗費時間是評價一個方法優劣的重要方面。在硬件平臺近似相同的情況下，若匹配的結果相似或者是為了滿足系統實時性的要求，運行的速度越快，表示該算法越好。本文算法運行時間比較結果如表1所示。

表1 算法運行時間比較

由上述實驗可以看出，優化后的ORB在提取相同級別數量的特征點的情況下并未損失過多的運行速度。相反，優化后的算法提升了特征提取的性能，提取的特征點也更加均勻。這能大大提高SLAM算法的穩定性。

3 結論

本文從理論上介紹了ORB特征提取的算法流程和原理，針對特征點數量與質量的矛盾這一問題采用了一種基于模塊化分割的ORB特征提取優化方法使提取的特征點更均勻地分布在整個圖像區域，分析比較了原算法和改進算法的速度性能和提取效果，實驗結果表明在不影響特征提取數量的條件下提取的質量得到了一定程度的提高，從而獲得了更好的性能。

[1] 權美香,樸松昊,李國. 視覺SLAM綜述[J]. 智能系統學報,2016,11(6):768-776.

[2] 王志文,郭戈. 移動機器人導航技術現狀與展望[J]. 機器人,2003,25(5):470-474.

[3] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

[4] BAY H, TUYTELAARS T, VAN GOOL L. Surf: speeded up robust features[C].European Conference on Computer Vision, Springer Berlin Heidelberg, 2006: 404-417.

[5] VISWANATHAN D G. Features from accelerated segment test (FAST)[EB/OL].(2016-04-15)[2017-03-30]https://wenku.baidu.com/view/af9743d725c52cc58ad6beac.html.

[6] CALONDER M, LEPETIT V, STRECHA C, et al. Brief: binary robust independent elementary features[C].European Conference on Computer Vision, Springer Berlin Heidelberg, 2010: 778-792.

[7] RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: an efficient alternative to SIFT or SURF[C].2011 IEEE International Conference on Computer Vision (ICCV), IEEE, 2011: 2564-2571.

[8] NOROUZI M, FLEET D J, SALAKHUTDINOV R R. Hamming distance metric learning[C].Advances in Neural Information Processing Systems, 2012: 1061-1069.

[9] 王永梅,胡學鋼. 決策樹中ID3算法的研究[J]. 安徽大學學報(自然科學版),2011,35(3):71-75.

[10] 楊恒. 基于局部特征提取匹配的視覺SLAM閉環檢測方法研究[D].衡陽：南華大學,2015.

[11] FISCHLER M A, BOLLES R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[12] HARRIS C, STEPHENS M. A combined corner and edge detector[C]. Proceedings of Fourth Alvey Vision Conference, 1988: 147-151.

An improved ORB algorithm

Pan Pan

(School of Information Engineering, Shanghai Maritime University, Shanghai 201703, China)

Aiming at the improvement of the reliability and robustness of the feature extraction in SLAM algorithm, an improved method of feature extraction is proposed. Based on the ORB (Oriented fast and Rotated Brief) feature extraction algorithm, an area segmentation method is proposed. It solves the problems of too more invalid feature points and the uneven distribution of feature points. This method makes the feature extraction of ORB algorithm more uniform and reasonable, and is more conducive to the image feature matching. The experimental results show that this method improves the effectiveness and reliability of the algorithm.

ORB; module segmentation; feature matching

TP911.73

A

10.19358/j.issn.1674- 7720.2017.20.007

潘盼.一種改進的ORB算法[J].微型機與應用，2017,36(20)：23-26.

2017-03-31)

潘盼(1989-)，男，碩士，主要研究方向：移動機器人導航、機器視覺。