一種改進的ORB算法

潘 盼

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

一種改進的ORB算法

潘 盼

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

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

ORB；模塊分割；特征匹配

0 引言

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

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

1 ORB算法原理

1.1 ORB算法流程

特征點提取步驟如下：

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

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

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

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

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

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

1.1.1FAST特征點提取

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

FAST算法提取的步驟：

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

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

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

圖2 FAST角點檢測

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

(1)

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

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

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

圖3 強度中心

假設圖像中區(qū)域塊的階數(shù)(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來構(gòu)造特征描述子，其實質(zhì)內(nèi)容為：以FAST方法得出的特征點為中心，隨機選取附近若干像素的點對。利用高斯二元分布對每個點對進行像素的灰度變化二值化比較，也即大于為1小于為0。將比較結(jié)果存為一個二進制串。生成指定次數(shù)位的二進制串，就得到BRIEF的描述。具體步驟如下：

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

(5)

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

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

(6)

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

(7)

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

得到該點方向θ相應的矩陣Rθ，構(gòu)造點對的矩陣：

Qθ=RθQ

(8)

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

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

(9)

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

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

(2)貪婪法逐步搜索。

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

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

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

1.1.3特征點匹配

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

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

K1=x0x1…xn，K2=y0y1…yn

(10)

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

(11)

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

圖4 特征匹配結(jié)果

1.2 ORB特征提取算法的優(yōu)化

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

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

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

基于上述方法的ORB特征提取算法的優(yōu)點可總結(jié)為：

(1)每個選擇的特征點都是子區(qū)域中表現(xiàn)最優(yōu)的特征點。

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

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

2 實驗結(jié)果與分析

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

圖5 原始參考圖像

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

圖6 ORB特征提取示意圖

圖7 優(yōu)化后的ORB特征提取示意圖

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

表1 算法運行時間比較

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

3 結(jié)論

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

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

[2] 王志文,郭戈. 移動機器人導航技術(shù)現(xiàn)狀與展望[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閉環(huán)檢測方法研究[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-)，男，碩士，主要研究方向：移動機器人導航、機器視覺。