一種改進的ORB特征點匹配算法?

唐管政 唐大全 谷旭平

（海軍航空大學 煙臺 264001）

1 引言

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

2 ORB特征匹配算法原理

ORB算法是將FSAT算法和BRIEF算法相結合并進行改進的算法［7］。

2.1 特征點提取

FAST特征提取算法中，當灰度圖中存在一像素點鄰域內的大部分像素點的灰度值大于或小于該點時，判定該像素點為特征點［8］。

如圖1所示，以p點為圓心的半徑為3個像素的區域內，比較p點和該點為圓心的圓環上所有點的灰度值的大小：

圖1 FAST特征點檢測

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

2.2 特征點描述

ORB算法中通過BRIEF描述子對提取的特征點進行闡述，BRIEF中采用9×9的高斯算子進行濾波［10］。在31×31的窗口中，生成一對隨機點，并以這一對點為中心，取其中5×5的子窗口，比對兩個點所在窗口的灰度值，再進行數學運算。運算過程如下：在以提取的特征點為中心的周圍隨機選擇點對（一般取128、256或者512），所有點對都生成一個二進制編碼：

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

選擇n對點，生成2n矩陣：

利用特征點方向作為變換矩陣Rθ，將矩陣進行變換生成新的矩陣：

其中θ為特征點所在坐標系中相對于橫軸的夾角，通過上式，可得改進的BRIEF描述子：

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

2.3 特征點匹配

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

3 對特征點匹配的改進算法

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

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

用最鄰近距離和次近鄰距離的比值作為評價匹配點對質量的標準，假設Up和Uq*的距離是D（Up，Uq*），定義 D（Up，Uq）與 D（Up，Uq*）的比值是最近鄰比率 NNDR（Nearest Neighbor Distance Ratio），當NNDR小于設定值時，則p點與q點匹配，定義最近鄰比率是：

如果NNDR小于設定值時，認為p點匹配q點，否則不匹配。

具體步驟如下。

1）通過計算當設定值設為0.7時匹配效果最佳，設定集合A為所有的匹配點對：A=｛pi（Uq，Uq*），i=1，2，…，m1｝，m1表示第一幅到第二幅的匹配點對的數量。

2）從第二幅中找到每一個第一幅的特征點的最鄰近和次鄰近的點，當NNDR小于設定值時，設定集合B為所有的的匹配點對：B=｛qi（Up，Up*），i=1，2，…，m2｝，m2表示從第二幅到第一幅的匹配點對的數量。

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

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

目前常用的匹配誤差剔除算法有RANSAC算法［11］、PROSAC 算法［12］，其 中 PROSAC 算 法 是 在RANSAC算法的基礎上改進而來的，而PROSAC算法先整理樣本按質量優劣排序，再從質量高的樣本中抽取子集，然后經過多次驗證得到最優估計解。將NDDR作為評價匹配質量優劣的標準，從前向后向匹配后的匹配點對剔除誤匹配點對，具體流程如下。

1）設置迭代次數初值和次數上限、內點數量臨界值、誤差范圍，初值設為0。

2）將樣本數據按質量優劣降序排序，然后選取n個質量較高的數據。

3）在抽取的n個樣本數據中去掉任意m個樣本數據，計算出數據中模型參數誤差小于設定誤差臨界值的個數，作為內點的個數。

4）若計算出的內點數量大于設定臨界值，則內點數量更新，否則將迭代次數加1，返回2）。

4 仿真與結果分析

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

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

圖2 匹配結果對比圖（位移變化）

圖3 匹配結果對比圖（旋轉變化）

圖4 匹配結果對比圖（亮度變化）

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

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

表1 各算法匹配準確性對比

表2 各算法運算時間對比

5 結語

本文為解決原ORB算法錯誤匹配情況較多的問題，將原ORB算法進行改良。通過基于最鄰近比率的匹配算法對原ORB算法的特征點匹配環節進行改進，減少了繁冗的計算量，提升了運算速度，再結合PROSAC算法剔除了錯誤的匹配點對，得到較為精準的匹配結果。改進后的方法與原方法相比，具有較強的準確性和實時性，提高了算法的性能，為在復雜場景下的實際應用打下基礎。