潘 盼

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

一種改進(jìn)的ORB算法

潘 盼

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

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

ORB；模塊分割；特征匹配

0 引言

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

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

1 ORB算法原理

1.1 ORB算法流程

特征點(diǎn)提取步驟如下：

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

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

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

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

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

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

1.1.1FAST特征點(diǎn)提取

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

FAST算法提取的步驟：

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

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

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

圖2 FAST角點(diǎn)檢測

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

(1)

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

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

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

圖3 強(qiáng)度中心

假設(shè)圖像中區(qū)域塊的階數(shù)(Moments)為：

(2)

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

(3)

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

求得點(diǎn)O與中心點(diǎn)C夾角為該點(diǎn)的主方向,用以下公式計(jì)算：

θ=arctan 2(m01,m10)

(4)

1.1.2BRIEF特征描述子

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

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

(5)

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

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

(6)

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

(7)

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

得到該點(diǎn)方向θ相應(yīng)的矩陣Rθ，構(gòu)造點(diǎn)對的矩陣：

Qθ=RθQ

(8)

最終特征點(diǎn)的描述算子為：

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

(9)

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

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

(2)貪婪法逐步搜索。

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

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

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

1.1.3特征點(diǎn)匹配

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

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

K1=x0x1…xn，K2=y0y1…yn

(10)

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

(11)

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

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

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

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

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

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

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

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

(2)選取特征點(diǎn)的數(shù)量可根據(jù)實(shí)際應(yīng)用靈活變化。

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

2 實(shí)驗(yàn)結(jié)果與分析

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

圖5 原始參考圖像

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

圖6 ORB特征提取示意圖

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

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

表1 算法運(yùn)行時(shí)間比較

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

3 結(jié)論

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

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

[2] 王志文,郭戈. 移動機(jī)器人導(dǎo)航技術(shù)現(xiàn)狀與展望[J]. 機(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] 王永梅,胡學(xué)鋼. 決策樹中ID3算法的研究[J]. 安徽大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,35(3):71-75.

[10] 楊恒. 基于局部特征提取匹配的視覺SLAM閉環(huán)檢測方法研究[D].衡陽：南華大學(xué),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

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

2017-03-31)

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