HOG-FLANN在圖像匹配ORB算法中的應用

楊 雷，唐瑞尹，張 怡

（1.華北理工大學電氣工程學院，河北 唐山 063210；2.北華航天工業學院電子與控制工程學院，河北 廊坊 065000）

1 引言

圖像匹配是機器視覺中重要的研究領域之一，被應用于雙目相機三維重構、目標跟蹤和機器人識別中。隨著機器視覺的發展，對圖像的匹配的準確率要求也越來越高。目前成熟的圖像特征點檢測算法有SIFT算法[1]、SURF算法[2]、和基于一種快速的特征點提取和描述ORB（Oriented FAST and Rotated BRIEF）[3]算法。ORB 算法最大的優點是可以極大的縮短圖像匹配的時間，但ORB算法對噪聲敏感[4]，容易產生含有不穩定邊緣的特征點。

隨著研究的不斷進步，在圖像匹配中經常使用ORB算法和FLANN（Fast Library for Approximate Nearest Neighbors）[5]相結合的匹配方法對圖像進行預匹配，并通過使用隨機抽樣性（RANdom Sample Consensus，RANSAC）[6-7]算法完成圖像特征點的匹配。RANSAC算法可以有效提高圖像特征點匹配的準確率，但當樣本中數據較多且局部內所占比例較低時。RANSAC計算最優模型參數時間呈指數增長，且移除錯誤匹配后仍然有較多的錯誤匹配。文獻[8]采用在極線約束下通過ORB特征算法進行圖像匹配，但該算法只能用于雙目相機的圖像匹配中；文獻[9]采用了圖像的彩色信息與SURF-ORB 算法相結合的方式，該算法具有很好的光照不變性，在不同的光照條件下，圖像匹配的準確率有所提高。

針對上述情況這里采用了HOG（Histogram of Oriented Gradient，HOG）[10]窗口約束下的FLANN圖像匹配方式。在這里算法中通過在HOG 窗口約束下使用FLANN 對ORB 特征點進行預匹配，然后采用RANSAC完成圖像特征點的匹配。實驗結果表明使用HOG 和FLANN 相互結合可以有效的提高圖像預匹配的準確率。

2 特征點檢測與匹配

特征點的檢測準確率是影響圖像匹配準確率的重要因素之一。ORB算法是圖像匹配常用的算法其主要作用是對圖像特征點進行檢測與描述。

2.1 ORB算法

ORB 算法的特征點的選取是通過oFAST 算法進行選取的，而oFAST算法是在FAST算法的基礎上改進而來，FAST算法的特征點檢測方式如下：

在圖像中選取某個像素點p其灰度值為IP，并且以p為圓心，確定一個閾值t讓圓上16個連續像素點的灰度值分別與IP做差值運算。若其中有12個以上差值的絕對值大于IP-t或小于IP+t則視p點為特征點，原理圖，如圖1所示。

圖1 FAST角點選取原理圖Fig.1 FAST Corner Selection Principle

由于上述方式需要對圖像的所有像素點遍歷并做差值運算，導致計算速度慢。ORB算法對FAST進行了改進稱其為oFAST，該算法選取了其中四個像素點作為判斷依據。oFAST在加快運算速度的同時，降低了抗噪聲的能力，容易把含有噪聲的邊緣點選作為特征點。如圖1所示在oFAST中分別選取1、5、9和13像素點作為判斷依據。如果其中有3個以上差值的絕對值都大于IP+t或都小于IP-t則被視p點為角點，其判別式，如式（1）所示。

ORB算法為了實現旋轉不變性，是通過求取一個特征點的方向來實現的。該方法是通過矩來得到特征點在r為半徑范圍內的質心，并將特征點原點到質心形成的向量作為該特征點的方向。該特征點的領域矩，如式（2）所示。

式中：x，y—坐標值；I（x，y）—灰度值；r—半徑。

該特征點窗口的質心坐標，如式（3）所示。

該特征點的主方向角度θ，如式（4）所示。

oFAST算法選取的特征點窗口是通過rBRIEF描述子進行描述的。該描述子是通過對BRIEF描述子的改進，進而使其具有了旋轉不轉性以及減少了描述子之間相關性。BRIEF算法的思想是在oFAST檢測的特征點窗口處通過高斯分布隨機的選取點對。然后將這些隨機點對的灰度值進行大小比較，進而得到一組二進制數。該組二進制數τ的計算方式，如式（5）所示。

式中：P（x）—點x處的灰度值。表達式，如式（6）所示。

由于點對的選取是通過高斯分布隨機選取的，導致生成的描述子對噪聲十分的敏感。因此在oFAST特征點選取之前需要對圖像進行高斯平滑濾波，這在一定的程度上降低了噪聲的干擾，但顯然不能解決ORB算法對噪聲敏感的問題。

為了解決BRIEF 不具備旋轉不變性的問題，提出了一個含有方向角的Steered BRIEF算法。在任意特征點位置定義了一個2×n維的點對矩陣，如式（7）所示。

根據特征點的主方向角度θ定義一個旋轉矩陣Rθ，則點對矩陣與Rθ的關系，如式（8）所示。

其中，Rθ的表達式，如式（9）所示。

則Steered BRIEF描述符，如式（10）所示。

ORB 為了增加描述子的區分度對Steered BRIEF 進行了改進。描述子表達了不同特征點之間的區別，因此每個描述子應該具有其獨特性。如果描述子之間的可區分度比較差，就容易引起誤匹配。為了降低描述子之間的相關性，在ORB算法中采用了統計學習的方式，其具備步驟如下：

（1）首先建立一個300k個測試集，對于測試集考慮其31×31的領域；

（2）在此領域中使用（5×5）的平均灰度值取代某個點對的灰度值，共得到M中點對；

（3）通過選取較小的點對，進而得到300k×M個矩陣Q；

（4）按照矩陣Q中的列向量之間的相關性使用貪婪搜索對列向量重新排序，最終得到相關性最低的描述符，該描述符為rBRIEF；

2.2 HOG算法

方向梯度直方圖（Histogram of Oriented Gradient，HOG）是一種圖像特征的描述符。HOG算法經常用于行人檢測中，在本文中通過HOG窗口平移的方式將目標圖中的局部窗口與背景圖的局部窗口進行描述子匹配，最終得到HOG 窗口的局部匹配圖。本文算法中HOG窗口特征描述方式如下：

（1）將被檢測圖轉換為灰度圖；

（2）將輸入圖像進行Gamma校正，其的目的是提高改算法的可靠性；

（3）通過卷積的方式遍歷整個輸入圖像，主要是獲取每個像素的梯度；

（4）將輸入圖像方式劃分成小局部窗口，這里為（128*128像素/窗口）；

（5）將局部窗口劃分成cell，本文中為（8*8像素/cell）；

（6）將多個cell 組成一個block 描述子，這里為（16*16 像素/block）；

（7）通過將block在局部窗口中的滑動，這里block滑動的增量為（8*8像素），得到局部窗口的HOG描述子；

（8）按照一定的步調滑動圖像中的HOG窗口，得到整個輸入圖像不同區域的描述子；

（9）將目標圖中每個HOG 窗口與背景的HOG 窗口進行對比，通過相關性大小判斷兩個局部窗口是否匹配，如式（11）其中R值越小表示目標局部窗口與背景局部窗口的相關性越高；

相關性大小比較，如式（11）所示。

式中：R—相關性系數；n—描述子個數；Ti和Ii—目標圖和背景圖中HOG描述子值；

局部HOG窗口匹配，如圖2所示。

圖2 HOG局部窗口匹配圖Fig.2 HOG Local Window Matching Graph

2.3 FLANN匹配器

圖像特征點匹配是通過計算特征點之間相關性完成的，常用的圖像匹配方式有BFMatcher（Brute Force Matcher）和FLANN兩種匹配方式。BFMatcher是通過對圖像所有特征點進行匹配，尋找最佳的圖像匹配點。

FLANN是一種近似匹配方式，其具有計算速度快的特點，并且通過改變FLANN的參數可以調整圖像匹配的準確度和改變該算法的計算速度。FLANN匹配是對大數據集和高維向量進行最近鄰搜索算法的集合，且該算法不受局部敏感哈希的影響。

2.4 HOG-FLANN匹配算法

這里提出了HOG與FLANN相結合的檢測算法。該算法是通過在HOG的局部窗口的約束下通過FLANN對ORB的特征點進行匹配，該方法可以有效提高ORB算法特征點匹配的準確率。采用ORB算法中rBRIEF作為特征點的描述子，通過使用HOG的局部窗口的約束下的FLANN 進行圖像預匹配，最后利用RANSAC完成圖像特征點的匹配。

該算法的流程，如圖3所示。

圖3 文中算法流程圖Fig.3 Algorithm Flow Chart in this Paper

這里算法中的計算步驟主要如下：

（1）通過使用HOG局部窗口按照平移的方式對目標圖和背景圖進行遍歷，然后采用式（11）獲取R值。R值越小表示兩個窗口的相關性越高，通過選取R的最小值，獲得兩個圖像中局部窗口的匹配結果。

（2）通過ORB算法提取圖像特征點，得到一個含有256位的二進制描述符。

（3）在HOG局部窗口的約束下對ORB算法提取圖像特征點進行查詢，選取HOG局部窗口內的特征點。

（4）采用FLANN對目標圖和背景圖的相互匹配的局部窗口中的特征點進行匹配，最后利用RANSAC完成圖像特征點匹配。

經過上述特征點匹配后可以有效的提高ORB算法特征點的匹配精度，使其具有很好的魯棒性。

在HOG局部窗口約束下的FLANN匹配結果，如圖4所示。

圖4 局部窗口的特征點預匹配Fig.4 Feature Point Pre-Matching for Local Windows

2.5 RANSAC算法

由于FLANN 預匹配的精度不夠高仍然存在大量的匹配錯誤，所以需要移除錯誤的匹配點。

這里采用了RANSAC 對錯誤的匹配點進行處理，該算法可以有效去除錯誤率超50%的匹配點，所以具有較好的穩定性。并且這里是通過RANSAC 去除錯誤點的大小去衡量預匹配的準確率。

3 實驗結果分析

為了驗證這里算法的合理性進行了對照實驗，主要是通過這里算法和FLANN算法的對照實驗。通過該實驗驗證這里算法在不同像素、噪聲和對比度下的匹配準確率。

該對比實驗的仿真環境為CPU Intel（R）Core（TM）i5-4200M 2.50GHZ、RAM 4GB、開發環境為VS2015與OpenCv 3.1。

3.1 實驗結果

這里采用了桌面照片作為測試圖，通過使用該測試圖對這里算法與原有算法進行了對比，并且驗證了在含有噪聲和改變亮度時本算法的穩定性，這里的算法的準確率明顯高于原有算法，如圖5～圖7所示。這里算法與原有算法的匹配結果的數據對比，由表（1）可以看出在不同條件下這里算法剔除誤匹配的數目要小于原有算法，說明這里算法具有更好的預匹配效果。

圖5 原有算法與文中算法預匹配的對比Fig.5 Comparison Between the Original Algorithm and the Present Algorithm

圖6 不同亮度下原有算法與文中算法預匹配對比Fig.6 Comparison Between the Original Algorithm and the Present Algorithm under Different Luminance

圖7 含有噪聲下原有算法與文中算法預匹配對比Fig.7 Comparison Between the Original Algorithm and the Present Algorithm Under Noise

表1 文中算法與原有算法的數據對比Tab.1 Data Comparison between the Present Algorithm and the Original Algorithm

4 結束語

針對傳統ORB 特征點一般采用FLANN 進行圖像特征點預匹配，這里采用HOG窗口與FLANN的相結合的算法。首先通過移動的HOG 窗口對圖像進行局部窗口進行匹配，再通過使用FLANN對局部窗口中的特征點進行預匹配，通過該算法可以有效的提高圖像匹配的準確率。經實驗測得這里算法的預匹配準確率由原來的89%提高到了94%，但是由于為了提高HOG局部窗口匹配的準確性，需要對圖像進行HOG窗口遍歷，所以將降低時效性，這將是今后的研究方向之一。