一種改進(jìn)的ORB特征點(diǎn)匹配算法?

唐管政 唐大全 谷旭平

（海軍航空大學(xué) 煙臺(tái) 264001）

1 引言

圖像特征匹配［1］是通過(guò)提取圖像中的特征點(diǎn)，將兩幅前后時(shí)間序列上的圖像進(jìn)行相關(guān)性計(jì)算，得到兩幅圖像的特征匹配。目前已廣泛應(yīng)用于無(wú)人機(jī)視覺(jué)導(dǎo)航、無(wú)人機(jī)目標(biāo)跟蹤與識(shí)別和同時(shí)定位與建圖等領(lǐng)域。圖像特征匹配主要有兩種，分別為塊匹配計(jì)算方法和點(diǎn)匹配計(jì)算方法，其中塊匹配計(jì)算方法雖然簡(jiǎn)單高效，但是當(dāng)圖像某部分被遮蓋時(shí)，會(huì)出現(xiàn)匹配點(diǎn)漂移的情況，致使匹配有所偏差。而點(diǎn)匹配計(jì)算方法，在無(wú)人機(jī)運(yùn)動(dòng)過(guò)程中，對(duì)圖像的位移較為敏感，并對(duì)光照變化、圖像噪聲、圖像畸變和遮擋具有一定的魯棒性。目前主流的點(diǎn)匹配計(jì)算方法有以下幾種：SIFT［2］、SURF［3］和 ORB［4］等。DavidG.Lowe等在于2004年提出了一種新的特征匹配算法?SIFT算法，但是SIFT算法中的計(jì)算量大，在實(shí)際應(yīng)用中不具有實(shí)時(shí)性。因此Bay H等于2006在SIFT算法的基礎(chǔ)上改進(jìn)了運(yùn)算速度，提出了SURF算法，但是仍然無(wú)法滿(mǎn)足實(shí)時(shí)性較高的應(yīng)用要求。而Rublee等于2011年將FAST算法［5］和BRIEF算法［6］相結(jié)合，提出了ORB算法，運(yùn)算速度較SIFT、SURF算法有了明顯的提升，但是運(yùn)用ORB算法在實(shí)際中仍然出現(xiàn)誤匹配率高和魯棒性差等問(wèn)題。針對(duì)以上問(wèn)題，本文對(duì)ORB算法的特征匹配環(huán)節(jié)進(jìn)行改進(jìn)，得到一種新的算法。

2 ORB特征匹配算法原理

ORB算法是將FSAT算法和BRIEF算法相結(jié)合并進(jìn)行改進(jìn)的算法［7］。

2.1 特征點(diǎn)提取

FAST特征提取算法中，當(dāng)灰度圖中存在一像素點(diǎn)鄰域內(nèi)的大部分像素點(diǎn)的灰度值大于或小于該點(diǎn)時(shí)，判定該像素點(diǎn)為特征點(diǎn)［8］。

如圖1所示，以p點(diǎn)為圓心的半徑為3個(gè)像素的區(qū)域內(nèi)，比較p點(diǎn)和該點(diǎn)為圓心的圓環(huán)上所有點(diǎn)的灰度值的大?。?/p>

圖1 FAST特征點(diǎn)檢測(cè)

其中N為特征點(diǎn)個(gè)數(shù)，I（i）為第i個(gè)點(diǎn)的灰度值，εd為設(shè)置的灰度閾值，N一般取9，即若存在連續(xù)9個(gè)點(diǎn)的灰度值變化量超過(guò)設(shè)定值，判定p點(diǎn)為特征點(diǎn)。為了方便運(yùn)算，可先計(jì)算p點(diǎn)與圓周上序號(hào)為1、5、9、13的特征點(diǎn)之間的差值，當(dāng)有任意三個(gè)特征點(diǎn)大于或小于閾值，才計(jì)算與其他像素點(diǎn)的差值，再采用Harris的方法對(duì)其進(jìn)行排序［9］。ORB算法中采用建立圖像金字塔的方法使原FAST特征具有尺度不變性，每層分別提取FAST特征點(diǎn)。又針對(duì)FAST特征點(diǎn)不具有方向性的情況，采用灰度質(zhì)心法，計(jì)算特征點(diǎn)鄰域內(nèi)的質(zhì)心，將特征點(diǎn)與質(zhì)心之間的矢量的方向定義為特征點(diǎn)的方向，局部圖像的幾何區(qū)域矩的公式是：

2.2 特征點(diǎn)描述

ORB算法中通過(guò)BRIEF描述子對(duì)提取的特征點(diǎn)進(jìn)行闡述，BRIEF中采用9×9的高斯算子進(jìn)行濾波［10］。在31×31的窗口中，生成一對(duì)隨機(jī)點(diǎn)，并以這一對(duì)點(diǎn)為中心，取其中5×5的子窗口，比對(duì)兩個(gè)點(diǎn)所在窗口的灰度值，再進(jìn)行數(shù)學(xué)運(yùn)算。運(yùn)算過(guò)程如下：在以提取的特征點(diǎn)為中心的周?chē)S機(jī)選擇點(diǎn)對(duì)（一般取128、256或者512），所有點(diǎn)對(duì)都生成一個(gè)二進(jìn)制編碼：

其中，p（x）和p（y）表示點(diǎn)對(duì)灰度值，選取n個(gè)對(duì)點(diǎn)（xi，yi）生成一個(gè)二進(jìn)制編碼，并將n個(gè)點(diǎn)對(duì)的進(jìn)行比較，作為描述子：

選擇n對(duì)點(diǎn)，生成2n矩陣：

利用特征點(diǎn)方向作為變換矩陣Rθ，將矩陣進(jìn)行變換生成新的矩陣：

其中θ為特征點(diǎn)所在坐標(biāo)系中相對(duì)于橫軸的夾角，通過(guò)上式，可得改進(jìn)的BRIEF描述子：

其中，n一般128、256、512，在ORB算法中取256。

2.3 特征點(diǎn)匹配

ORB算法中，D（Up，Uq）代表兩個(gè)可能匹配的特征點(diǎn)之間的漢明距離，Up是第一幅中某一點(diǎn)p的矢量，Uq是第二幅中最鄰近點(diǎn)q的矢量，距離越小證明兩個(gè)點(diǎn)越符合匹配條件，采用最近鄰法進(jìn)行判斷。如果最近鄰點(diǎn)和次近鄰點(diǎn)距離比值小于某一設(shè)定值時(shí)，判定這兩個(gè)點(diǎn)匹配成功。

3 對(duì)特征點(diǎn)匹配的改進(jìn)算法

3.1 基于最近鄰比率的匹配算法

原ORB算法中匹配方法運(yùn)算量大，本文運(yùn)用K最近鄰算法，對(duì)樣本集進(jìn)行整理，其中K取2，對(duì)第一幅圖像進(jìn)行特征點(diǎn)提取，在第二幅圖像中搜尋最近鄰距離和次近鄰距離的點(diǎn)，假設(shè)Uq*是第一幅圖像中次近鄰點(diǎn)q的矢量，匹配特征點(diǎn)對(duì)可表示為pi（Up，Uq*），其中i=1，2，…，n。n為第二幅圖像中的特征點(diǎn)數(shù)。

用最鄰近距離和次近鄰距離的比值作為評(píng)價(jià)匹配點(diǎn)對(duì)質(zhì)量的標(biāo)準(zhǔn)，假設(shè)Up和Uq*的距離是D（Up，Uq*），定義 D（Up，Uq）與 D（Up，Uq*）的比值是最近鄰比率 NNDR（Nearest Neighbor Distance Ratio），當(dāng)NNDR小于設(shè)定值時(shí)，則p點(diǎn)與q點(diǎn)匹配，定義最近鄰比率是：

如果NNDR小于設(shè)定值時(shí)，認(rèn)為p點(diǎn)匹配q點(diǎn)，否則不匹配。

具體步驟如下。

1）通過(guò)計(jì)算當(dāng)設(shè)定值設(shè)為0.7時(shí)匹配效果最佳，設(shè)定集合A為所有的匹配點(diǎn)對(duì)：A=｛pi（Uq，Uq*），i=1，2，…，m1｝，m1表示第一幅到第二幅的匹配點(diǎn)對(duì)的數(shù)量。

2）從第二幅中找到每一個(gè)第一幅的特征點(diǎn)的最鄰近和次鄰近的點(diǎn)，當(dāng)NNDR小于設(shè)定值時(shí)，設(shè)定集合B為所有的的匹配點(diǎn)對(duì)：B=｛qi（Up，Up*），i=1，2，…，m2｝，m2表示從第二幅到第一幅的匹配點(diǎn)對(duì)的數(shù)量。

3）如果A中某一匹配點(diǎn)對(duì)（pi，qj），可以在B中找到一個(gè)與之對(duì)應(yīng)的匹配點(diǎn)對(duì)（qj，pi），則該匹配點(diǎn)對(duì)正確。通過(guò)這樣的前向后向匹配后，篩選得到的所有匹配可以用集合C表示：C=｛pi（Uq，Uq*）），i=1，2，…，m3｝，m3表示通過(guò)前向后向匹配后確定的匹配點(diǎn)對(duì)的數(shù)量。

3.2 基于PROSAC算法的誤匹配剔除

目前常用的匹配誤差剔除算法有RANSAC算法［11］、PROSAC 算法［12］，其 中 PROSAC 算 法 是 在RANSAC算法的基礎(chǔ)上改進(jìn)而來(lái)的，而PROSAC算法先整理樣本按質(zhì)量?jī)?yōu)劣排序，再?gòu)馁|(zhì)量高的樣本中抽取子集，然后經(jīng)過(guò)多次驗(yàn)證得到最優(yōu)估計(jì)解。將NDDR作為評(píng)價(jià)匹配質(zhì)量?jī)?yōu)劣的標(biāo)準(zhǔn)，從前向后向匹配后的匹配點(diǎn)對(duì)剔除誤匹配點(diǎn)對(duì)，具體流程如下。

1）設(shè)置迭代次數(shù)初值和次數(shù)上限、內(nèi)點(diǎn)數(shù)量臨界值、誤差范圍，初值設(shè)為0。

2）將樣本數(shù)據(jù)按質(zhì)量?jī)?yōu)劣降序排序，然后選取n個(gè)質(zhì)量較高的數(shù)據(jù)。

3）在抽取的n個(gè)樣本數(shù)據(jù)中去掉任意m個(gè)樣本數(shù)據(jù)，計(jì)算出數(shù)據(jù)中模型參數(shù)誤差小于設(shè)定誤差臨界值的個(gè)數(shù)，作為內(nèi)點(diǎn)的個(gè)數(shù)。

4）若計(jì)算出的內(nèi)點(diǎn)數(shù)量大于設(shè)定臨界值，則內(nèi)點(diǎn)數(shù)量更新，否則將迭代次數(shù)加1，返回2）。

4 仿真與結(jié)果分析

以拍攝視頻中兩幅時(shí)間序列相鄰的一組圖片作為實(shí)驗(yàn)對(duì)象，通過(guò)實(shí)驗(yàn)得到改進(jìn)算法與原ORB算法的匹配結(jié)果圖，如圖2所示，考慮實(shí)際情況，在圖像中加入旋轉(zhuǎn)變化、光照變化、尺寸變化因素，得到改進(jìn)算法與原ORB算法的匹配結(jié)果對(duì)比圖，如圖3、4、5所示。

如圖2中所示，原ORB算法匹配情況較差，改進(jìn)算法匹配效果比原ORB算法好，無(wú)明顯誤匹配點(diǎn)對(duì)。圖3、4、5表明，在加入旋轉(zhuǎn)變化、光照變化因素后，原ORB依然存在大量誤匹配的情況，改進(jìn)ORB算法匹配效果良好，說(shuō)明改進(jìn)算法對(duì)旋轉(zhuǎn)、光照因素具有一定的魯棒性。

圖2 匹配結(jié)果對(duì)比圖（位移變化）

圖3 匹配結(jié)果對(duì)比圖（旋轉(zhuǎn)變化）

圖4 匹配結(jié)果對(duì)比圖（亮度變化）

為了證明本文算法的準(zhǔn)確性和實(shí)時(shí)性，選用視頻中的四組時(shí)間序列相鄰的圖片，對(duì)沒(méi)有誤匹配剔除，和使用了RANSAC算法以及本文的ORB-P算法進(jìn)行對(duì)比實(shí)驗(yàn)，并與SIFT、SURF算法做仿真時(shí)間對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1和表2所示。

如表1所示，未經(jīng)過(guò)誤匹配剔除的特征匹配點(diǎn)對(duì)中正確率只有67.9%，使用RANSAC算法后正確率達(dá)到92.5%，但是存在的誤匹配對(duì)實(shí)際應(yīng)用會(huì)造成影響。使用本文的ORB-P算法進(jìn)行誤匹配剔除后，匹配正確率達(dá)到99.6%，為實(shí)際應(yīng)用中對(duì)正確率的要求提供依據(jù)。表2是改進(jìn)算法和SIFT、SURF算法的仿真時(shí)間對(duì)比結(jié)果，從中可以看出，改進(jìn)算法平均用時(shí)0.24s，改進(jìn)算法運(yùn)算時(shí)間約是SURF算法運(yùn)算時(shí)間的1/4，是SIFT算法運(yùn)算時(shí)間的1/24，可以達(dá)到實(shí)際應(yīng)用中對(duì)運(yùn)算時(shí)間的要求。

表1 各算法匹配準(zhǔn)確性對(duì)比

表2 各算法運(yùn)算時(shí)間對(duì)比

5 結(jié)語(yǔ)

本文為解決原ORB算法錯(cuò)誤匹配情況較多的問(wèn)題，將原ORB算法進(jìn)行改良。通過(guò)基于最鄰近比率的匹配算法對(duì)原ORB算法的特征點(diǎn)匹配環(huán)節(jié)進(jìn)行改進(jìn)，減少了繁冗的計(jì)算量，提升了運(yùn)算速度，再結(jié)合PROSAC算法剔除了錯(cuò)誤的匹配點(diǎn)對(duì)，得到較為精準(zhǔn)的匹配結(jié)果。改進(jìn)后的方法與原方法相比，具有較強(qiáng)的準(zhǔn)確性和實(shí)時(shí)性，提高了算法的性能，為在復(fù)雜場(chǎng)景下的實(shí)際應(yīng)用打下基礎(chǔ)。