一種基于ORB檢測(cè)的特征點(diǎn)匹配算法

劉 威,趙文杰,李德軍,王 驍，葉 怡

(1.空軍航空大學(xué)航空航天情報(bào)系,吉林 長(zhǎng)春 130022;2.解放軍94891部隊(duì)，江蘇 蘇州 215000)

?

·圖像與信號(hào)處理·

一種基于ORB檢測(cè)的特征點(diǎn)匹配算法

劉 威1,趙文杰1,李德軍1,王 驍2，葉 怡2

(1.空軍航空大學(xué)航空航天情報(bào)系,吉林 長(zhǎng)春 130022;2.解放軍94891部隊(duì)，江蘇 蘇州 215000)

針對(duì)傳統(tǒng)的SURF局部特征匹配算法實(shí)時(shí)性不高的問(wèn)題,充分利用ORB特征點(diǎn)檢測(cè)算法簡(jiǎn)單高效的優(yōu)勢(shì),提出了一種新的特征點(diǎn)匹配算法。首先,針對(duì)原始ORB特征匹配算法出現(xiàn)大量誤匹配對(duì)的問(wèn)題,采用基于K最近鄰的特征點(diǎn)描述后,對(duì)前后兩幀特征點(diǎn)進(jìn)行雙向匹配,再通過(guò)順序抽樣一致性算法進(jìn)一步提純。實(shí)驗(yàn)結(jié)果表明,經(jīng)過(guò)本文算法提純后匹配對(duì)準(zhǔn)確度提升到99.9%,平均耗時(shí)0.46 s,處理速度約是SURF特征匹配算法的5倍,SIFT特征匹配算法的25倍,能夠滿足實(shí)時(shí)運(yùn)用的需求。

特征點(diǎn)匹配；ORB角點(diǎn)檢測(cè)；局部特征

1 引 言

特征點(diǎn)匹配算法在運(yùn)動(dòng)目標(biāo)檢測(cè)與識(shí)別、視覺(jué)導(dǎo)航等領(lǐng)域有著廣泛應(yīng)用[1]。目前常用的特征點(diǎn)匹配算法主要有：SIFT[2]、SURF[3]和ORB[4]等。其中SIFT算法是David G.Lowe在2004年提出的一種具有里程碑意義的尺度不變特征變換算法,在多尺度空間提取特征點(diǎn)；SURF算法由SIFT算法改進(jìn)而來(lái),通過(guò)積分圖像和盒式濾波器來(lái)替代SIFT中的尺度空間分解,大大減少了計(jì)算量。但在對(duì)實(shí)時(shí)性要求較高的應(yīng)用中,這兩種算法依然無(wú)法滿足要求。而由Rublee等人在ICCV2011上提出的ORB算法在保證尺度、旋轉(zhuǎn)不變的基礎(chǔ)上,速度較前兩種算法有了很大的提高。作為一種局部不變特征匹配算法,ORB是建立在FAST特征點(diǎn)檢測(cè)[5]和BRIEF特征點(diǎn)描述[6]的基礎(chǔ)之上,其采用的二進(jìn)制局部特征描述符的實(shí)時(shí)性大大優(yōu)于SIFT、SURF等浮點(diǎn)型局部特征描述符[11]。

本文基于ORB角點(diǎn)檢測(cè)提出一種特征匹配算法。利用ORB算法快速提取特征點(diǎn),改進(jìn)其匹配策略消除誤匹配點(diǎn)。與傳統(tǒng)的SURF特征匹配算法相比,本文算法在實(shí)時(shí)性上有了很大提高；與傳統(tǒng)的ORB特征匹配算法相比,本文算法能夠極大消除噪聲點(diǎn)。

2 ORB特征匹配算法

原始的ORB匹配算法主要經(jīng)過(guò)以下幾個(gè)步驟：首先,利用Oriented FAST檢測(cè)子在連續(xù)兩幅圖像上檢測(cè)特征點(diǎn)；再通過(guò)Rotated BRIEF描述符生產(chǎn)特征點(diǎn)的二進(jìn)制描述向量；最后連續(xù)兩幅圖像的特征點(diǎn)的匹配采用漢明距離比值準(zhǔn)則得到最終的特征點(diǎn)匹配對(duì)。

2.1 Oriented FAST特征點(diǎn)檢測(cè)

FAST由于其高效性得到了廣泛應(yīng)用,Rosten等人[7]在算法中加入了機(jī)器學(xué)習(xí)和ID3決策樹(shù)機(jī)制提出了一種簡(jiǎn)單快速的FAST特征點(diǎn)檢測(cè)算法。在文獻(xiàn)[7]中,Rosten等人將FAST特征點(diǎn)定義為：圖像中某點(diǎn)的灰度值比周圍鄰域內(nèi)大多數(shù)像素點(diǎn)的灰度值都大或小時(shí),該點(diǎn)為特征點(diǎn)。檢測(cè)點(diǎn)p周圍的16個(gè)點(diǎn),如果有連續(xù)12個(gè)點(diǎn)的灰度值與點(diǎn)p的灰度值之差大于一定的閾值,則將點(diǎn)p判定為特征點(diǎn),為此可以通過(guò)一個(gè)角點(diǎn)響應(yīng)函數(shù)CRF來(lái)判斷一個(gè)FAST特征點(diǎn)：

(1)

(2)

其中,I(x)是待測(cè)點(diǎn)鄰域內(nèi)任一點(diǎn)的灰度值;I(p)是當(dāng)前待測(cè)點(diǎn)的灰度值。所有圓周點(diǎn)與待測(cè)點(diǎn)的響應(yīng)函數(shù)值的和為N,ORB算法中N為9,當(dāng)N大于一定閾值時(shí)待測(cè)點(diǎn)為特征點(diǎn)。為了使得特征點(diǎn)能適應(yīng)光照變化,ORB算法首先設(shè)置較低的閾值提取多數(shù)的特征點(diǎn),再利用Harris角點(diǎn)[8]的評(píng)價(jià)函數(shù)找到角點(diǎn)響應(yīng)值較高的前N個(gè)FAST特征點(diǎn)；為了使特征點(diǎn)具有尺度不變性,ORB算法使用金字塔算法得到多尺度圖像,得到FAST特征點(diǎn)的尺度特征；為了使特征點(diǎn)具有方向不變性,ORB算法使用灰度質(zhì)心法[9]為特征點(diǎn)提供一個(gè)主方向：找到特征點(diǎn)局部區(qū)域內(nèi)的灰度形心,用特征點(diǎn)到形心的矢量方向來(lái)確定特征點(diǎn)的主方向,局部區(qū)域矩的公式是：

(3)

則這些矩計(jì)算特征點(diǎn)區(qū)域上的灰度形心為：

(4)

則質(zhì)心與特征點(diǎn)的夾角即FAST特征點(diǎn)的主方向：

(5)

2.2 Rotated BRIEF特征點(diǎn)描述

ORB算法中采用BRIEF描述子對(duì)檢測(cè)到的特征點(diǎn)進(jìn)行描述,并解決了BRIEF描述子不具有旋轉(zhuǎn)不變性的問(wèn)題。

BRIEF描述子是最簡(jiǎn)單的一種二進(jìn)制描述子,其生成過(guò)程如下：在圖像塊內(nèi)隨機(jī)生成點(diǎn)對(duì)(對(duì)數(shù)可以是128、256和512),每一個(gè)點(diǎn)對(duì)對(duì)應(yīng)一個(gè)二進(jìn)制位,定義如下：

(6)

其中,p(x)和p(y)是點(diǎn)對(duì)的灰度,隨機(jī)選擇n對(duì)點(diǎn)(xi,yi)就可以生成一個(gè)二進(jìn)制字符串,則生成的特征描述子可以表示為：

(7)

由于BRIEF描述子比較的是點(diǎn)對(duì)的像素值,對(duì)噪聲非常敏感。為了消除噪聲的影響,ORB算法采取如下策略：在特征點(diǎn)鄰域的31×31像素區(qū)域內(nèi)隨機(jī)選取5×5的子窗口,比較窗口的灰度積分來(lái)替換點(diǎn)對(duì)的像素值的比較。為了解決BRIEF描述子不具有旋轉(zhuǎn)不變性的問(wèn)題,ORB算法的解決方案是：在特征點(diǎn)上選取n對(duì)特征,得到一個(gè)2n矩陣：

(8)

利用特征點(diǎn)檢測(cè)得到的主方向確定的仿射變換矩陣Rθ對(duì)進(jìn)行旋轉(zhuǎn)得到新的描述矩陣：

(9)

結(jié)合式(7)這樣就可以得到矯正后的BRIEF描述子：

(10)

其中,n可取128、256、512,在ORB算法中作者選取的是相關(guān)性較低的256對(duì)像素塊對(duì)進(jìn)行特征描述。

2.3 ORB特征點(diǎn)匹配

2.1.1 心理護(hù)理 術(shù)前關(guān)注患者的心理狀態(tài)至關(guān)重要［7］?；颊邽槟贻p女性，病史2年余，因咳嗽、咳痰、發(fā)熱就診于多家醫(yī)院，口服抗結(jié)核藥物效果不滿意，經(jīng)多次氣管鏡檢查發(fā)現(xiàn)氣管下段狹窄。隨著病情進(jìn)展呼吸困難加重，霧化、平喘、對(duì)癥治療無(wú)效，使患者對(duì)治療信心不足。雖然對(duì)手術(shù)抱有希望，但又擔(dān)心手術(shù)失敗。護(hù)士及時(shí)了解患者心理變化，隨時(shí)了解各種檢查結(jié)果，給予心理疏導(dǎo)。告訴其醫(yī)護(hù)人員及家人正在積極想辦法、做準(zhǔn)備，并列舉成功實(shí)施氣管手術(shù)的病例鼓勵(lì)患者，講解大致手術(shù)過(guò)程，增強(qiáng)患者戰(zhàn)勝疾病的信心。在不影響治療、護(hù)理的情況下，盡量讓家屬陪伴，增加患者安全感，使患者能積極配合檢查、治療。

上節(jié)中得到的256維ORB特征描述子,為了建立連續(xù)兩幅圖像上特征點(diǎn)的對(duì)應(yīng)關(guān)系,我們計(jì)算第二幀圖像上每個(gè)特征點(diǎn)與第一幀圖像上全部特征點(diǎn)描述向量的漢明距離,用D(Vp,Vq)表示,其中Vp是第二幀中某一特征點(diǎn)p的特征向量,Vq是第一幀中最鄰近特征點(diǎn)q的特征向量,D(Vp,Vq)越小說(shuō)明兩個(gè)特征點(diǎn)越相似,漢明距離最小的即為匹配對(duì)。

3 一種匹配對(duì)提純的改進(jìn)算法

從以上的分析發(fā)現(xiàn)ORB算法存在兩大缺陷：一是基于窮舉搜索得到的匹配對(duì)沒(méi)有考慮兩特征點(diǎn)是否屬于同一區(qū)域；二是當(dāng)多個(gè)特征點(diǎn)較為接近時(shí)算法將喪失判斷能力,影響了匹配精確度。常見(jiàn)的誤匹配去除算法——RANSAC,是一種隨機(jī)參數(shù)估計(jì)算法,該算法的缺點(diǎn)是隨機(jī)抽取匹配對(duì),不考慮匹配對(duì)的質(zhì)量好壞,當(dāng)誤匹配對(duì)較多時(shí)依然會(huì)造成很大偏差。為此本文提出一種新的特征點(diǎn)匹配算法——PROMATCH(progressive match),對(duì)去除誤匹配對(duì)提出如下改進(jìn)策略。

3.1 基于K最近鄰的特征點(diǎn)匹配對(duì)描述

3.2 基于漢明距離近鄰比值準(zhǔn)則的雙向匹配

(11)

(12)

Vj≠Vq}

(13)

(14)

3.3 基于PROSAC算法去除誤匹配

PROSAC算法[10]是RANSAC算法的改進(jìn),不是隨機(jī)抽取匹配對(duì),而是根據(jù)匹配對(duì)的質(zhì)量好壞對(duì)匹配對(duì)進(jìn)行排序,在模型參數(shù)擬合時(shí)優(yōu)先抽取質(zhì)量較高的匹配對(duì)進(jìn)行迭代估計(jì)。這里我們將上一步中計(jì)算得到的最近鄰和次近鄰的比值R作為匹配質(zhì)量的定量表示,對(duì)經(jīng)過(guò)雙向匹配后得到的特征點(diǎn)匹配對(duì)進(jìn)行進(jìn)一步提純,本文采用的PROSAC算法步驟如下：

(1)初始設(shè)置：迭代次數(shù)初值設(shè)為0,是否為內(nèi)點(diǎn)的誤差閾值、內(nèi)點(diǎn)數(shù)目的閾值、最大迭代次數(shù)。

(2)若迭代次數(shù)小于最大迭代次數(shù),選取樣本集中前n個(gè)具有較高質(zhì)量的數(shù)據(jù),從中隨機(jī)取出m個(gè),計(jì)算模型參數(shù),并計(jì)算用此模型參數(shù)得到的誤差小于內(nèi)點(diǎn)誤差閾值的數(shù)據(jù)數(shù)量,即內(nèi)點(diǎn)數(shù)量。若迭代次數(shù)大于最大迭代次數(shù),則返回對(duì)應(yīng)內(nèi)點(diǎn)數(shù)量最大的一組內(nèi)點(diǎn)。

(3)判定內(nèi)點(diǎn)數(shù)量是否大于設(shè)定的內(nèi)點(diǎn)數(shù)目閾值,大于則返回內(nèi)點(diǎn),否則迭代次數(shù)加1跳轉(zhuǎn)第二步。

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

實(shí)驗(yàn)平臺(tái)采用Intel Core(TM)2 Duo CPU主頻2.5GHz的PC機(jī),沒(méi)有任何硬件加速,用C++和OpenCV庫(kù)在VS2010上進(jìn)行調(diào)試,實(shí)驗(yàn)采用一段無(wú)人機(jī)航拍視頻圖像,圖像大小為1920pixel×1080pixel,首先給出本文算法與原始ORB特征匹配算法的效果對(duì)比圖,如圖1所示,進(jìn)而再進(jìn)行算法準(zhǔn)確性和實(shí)時(shí)性的分析。

圖1 特征匹配算法效果對(duì)比圖

4.1 算法匹配準(zhǔn)確度比較分析

為了驗(yàn)證本文PROMATCH提純算法的準(zhǔn)確性,本文選用航拍視頻幀中的5組數(shù)據(jù),對(duì)沒(méi)有提純匹配對(duì),和使用了RANSAC提純算法以及本文的PROMATCH提純算法進(jìn)行對(duì)比試驗(yàn)。如表1和表2所示。

表1 特征點(diǎn)匹配對(duì)提純算法對(duì)比

表2 不同算法匹配對(duì)數(shù)目和耗時(shí)對(duì)比

從表1中我們可以發(fā)現(xiàn),基于窮盡搜索得到的特征匹配對(duì)中存在著大量的誤匹配,使用了RANSAC提純算法后將匹配準(zhǔn)確度從68.4%提升到了91.8%,但依然存在著大量誤匹配,勢(shì)必對(duì)特征匹配的應(yīng)用帶來(lái)很大影響,而經(jīng)過(guò)本文的PROMATCH算法提純后,誤匹配對(duì)基本接近于零,為特征匹配的后續(xù)應(yīng)用提供了可靠數(shù)據(jù)。

為了驗(yàn)證算法的實(shí)時(shí)性,下面將本文的特征匹配算法和傳統(tǒng)的SIFT、SURF特征匹配算法進(jìn)行對(duì)比試驗(yàn),表1是在航拍視頻幀中的5組數(shù)據(jù)上得到的試驗(yàn)結(jié)果,我們可以發(fā)現(xiàn)：本文算法得到的匹配對(duì)數(shù)目最多且耗時(shí)最低,雖然在特征匹配階段算法復(fù)雜度有所增加,但在處理速度約是SURF的5倍,SIFT的25倍,能夠滿足實(shí)時(shí)處理的需求。

5 結(jié) 論

針對(duì)傳統(tǒng)SURF算法實(shí)時(shí)性不高、ORB算法準(zhǔn)確度不夠的兩難問(wèn)題,本文提出了一種新的特征匹配算法。首先利用ORB算法快速提取特征點(diǎn),提出一種新的特征點(diǎn)匹配算法(PROMATCH)消除誤匹配點(diǎn),該方法利用了ORB算法的實(shí)時(shí)性,并對(duì)影響配準(zhǔn)準(zhǔn)確性的關(guān)鍵步驟——特征點(diǎn)匹配進(jìn)行了改進(jìn),有效濾除了誤匹配對(duì),最后通過(guò)一段航拍視頻圖像驗(yàn)證了本文算法的匹配精確度和實(shí)時(shí)性,下一步擬打算將本文算法運(yùn)用到復(fù)雜場(chǎng)景下的目標(biāo)檢測(cè)和跟蹤中去。

[1] YAO Siyuan,WANG Xiaoming,WANG Shuai.Fast feature points matching based on SURF[J].Laser & Infrared,2014,44(3):347-350.(in chinese)

堯思遠(yuǎn),王曉明,王帥.基于SURF的特征點(diǎn)快速匹配算法[J].激光與紅外,2014,44(3):347-350.

[2] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[3] Bay H,Tuytelaars T,Gool L V.SURF:Speeded up robust features[C].Proceedings of European Conference on Computer Vision,2006,1:404-417.

[4] Rublee E,Rabaud V,Konolige K,et al.ORB:An efficient alternative to SIFT or SURF[C].Proceedings of IEEE International Conference on Computer Vision,Washington,USA,2011:2564-2571.

[5] Mair E,Hager G D,Burschka D,et al.Adaptive and generic corner detection based on the accelerated segment test[C].Proceedings of European Conference on Computer Vision,Greece,2010,63(12):183-196.

[6] Calonder M,Lepetit V,Fua P.BRIEF:Binary Robust Independent Elementary Features[C].Proceedings of European Conference on Computer Vision,Greece,2010,63(14):778-792.

[7] Rosten E,Drummond T.Machine learning for high-speed corner detection[M].New York:Springer,2006:25-36.

[8] Harris C,Stephens M.A combined corner and edge detector[C].Proceedings of Alvey Vision Conference,1988:147-151.

[9] P L Rosin.Measuring corner properties[C].Computer Vision and Image Understanding,1999,73(2)：291-307.

[10]Chum O,Matas J.Matching with PROSAC-Progressive Sample Consensus[C]Proceedings of IEEE Computer Society Conference on Computer Vision and Patten Recognition,2005,2:220-226.

[11]LI Junshan,ZHU Yinghong,ZHU Xiaojuan,et.al.Description and matching of self-similarities for IR and visual images[J].Laser & Infrared,2013,43(3):339-343.(in chinese)

李俊山,朱英宏,朱曉娟,等.紅外與可見(jiàn)光圖像自相似性特征的描述與匹配[J].激光與紅外,2013,43(3):339-343.

Feature points matching algorithm based on ORB detection

LIU Wei1,ZHAO Wen-jie1,LI De-jun1，WANG Xiao2,YE Yi2

(1.Department of Aerospace Intelligence,Aviation Univ.of Air Force.,Changchun 130022,China;2.PLA 94891 Troop,Suzhou 215000,China)

As traditional SURF local feature points matching algorithm has low real-time,a new feature points matching algorithm is proposed by using the advantage of ORB feature points detection.First of all,there are a large number of false matching pairs in the original ORB,and these false matching pairs are described by feature points based on K nearest neighbor,and then the feature points in two consecutive frames are bilaterally matched.At last,the consistency is further refined by sequential sampling algorithm.Experimental results show that the match accuracy is up to 99.9% after purification,and the average running time is 0.46 s.Processing speed is about 5 times faster than SURF feature matching algorithm and 25 times faster than SIFT feature matching algorithm,and it can meet the requirements of real-time processing.

feature matching；ORB Detection；local feature

1001-5078(2015)11-1380-05

國(guó)家自然科學(xué)基金項(xiàng)目(No.61301233);全軍軍事學(xué)研究生課題(No.213JY512)資助。

劉 威(1991-)，男，碩士研究生，主要研究方向?yàn)槟繕?biāo)檢測(cè)與跟蹤。E-mail：1224337250@qq.com

2015-03-18;

2015-05-28

TP39

A

10.3969/j.issn.1001-5078.2015.11.019