HOG-FLANN在圖像匹配ORB算法中的應(yīng)用

楊 雷，唐瑞尹，張 怡

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

1 引言

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

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

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

2 特征點(diǎn)檢測與匹配

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

2.1 ORB算法

ORB 算法的特征點(diǎn)的選取是通過oFAST 算法進(jìn)行選取的，而oFAST算法是在FAST算法的基礎(chǔ)上改進(jìn)而來，F(xiàn)AST算法的特征點(diǎn)檢測方式如下：

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

圖1 FAST角點(diǎn)選取原理圖Fig.1 FAST Corner Selection Principle

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

ORB算法為了實(shí)現(xiàn)旋轉(zhuǎn)不變性，是通過求取一個(gè)特征點(diǎn)的方向來實(shí)現(xiàn)的。該方法是通過矩來得到特征點(diǎn)在r為半徑范圍內(nèi)的質(zhì)心，并將特征點(diǎn)原點(diǎn)到質(zhì)心形成的向量作為該特征點(diǎn)的方向。該特征點(diǎn)的領(lǐng)域矩，如式（2）所示。

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

該特征點(diǎn)窗口的質(zhì)心坐標(biāo)，如式（3）所示。

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

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

式中：P（x）—點(diǎn)x處的灰度值。表達(dá)式，如式（6）所示。

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

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

根據(jù)特征點(diǎn)的主方向角度θ定義一個(gè)旋轉(zhuǎn)矩陣Rθ，則點(diǎn)對矩陣與Rθ的關(guān)系，如式（8）所示。

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

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

ORB 為了增加描述子的區(qū)分度對Steered BRIEF 進(jìn)行了改進(jìn)。描述子表達(dá)了不同特征點(diǎn)之間的區(qū)別，因此每個(gè)描述子應(yīng)該具有其獨(dú)特性。如果描述子之間的可區(qū)分度比較差，就容易引起誤匹配。為了降低描述子之間的相關(guān)性，在ORB算法中采用了統(tǒng)計(jì)學(xué)習(xí)的方式，其具備步驟如下：

（1）首先建立一個(gè)300k個(gè)測試集，對于測試集考慮其31×31的領(lǐng)域；

（2）在此領(lǐng)域中使用（5×5）的平均灰度值取代某個(gè)點(diǎn)對的灰度值，共得到M中點(diǎn)對；

（3）通過選取較小的點(diǎn)對，進(jìn)而得到300k×M個(gè)矩陣Q；

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

2.2 HOG算法

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

（1）將被檢測圖轉(zhuǎn)換為灰度圖；

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

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

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

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

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

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

（8）按照一定的步調(diào)滑動圖像中的HOG窗口，得到整個(gè)輸入圖像不同區(qū)域的描述子；

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

相關(guān)性大小比較，如式（11）所示。

式中：R—相關(guān)性系數(shù)；n—描述子個(gè)數(shù)；Ti和Ii—目標(biāo)圖和背景圖中HOG描述子值；

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

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

2.3 FLANN匹配器

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

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

2.4 HOG-FLANN匹配算法

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

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

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

這里算法中的計(jì)算步驟主要如下：

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

（2）通過ORB算法提取圖像特征點(diǎn)，得到一個(gè)含有256位的二進(jìn)制描述符。

（3）在HOG局部窗口的約束下對ORB算法提取圖像特征點(diǎn)進(jìn)行查詢，選取HOG局部窗口內(nèi)的特征點(diǎn)。

（4）采用FLANN對目標(biāo)圖和背景圖的相互匹配的局部窗口中的特征點(diǎn)進(jìn)行匹配，最后利用RANSAC完成圖像特征點(diǎn)匹配。

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

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

圖4 局部窗口的特征點(diǎn)預(yù)匹配Fig.4 Feature Point Pre-Matching for Local Windows

2.5 RANSAC算法

由于FLANN 預(yù)匹配的精度不夠高仍然存在大量的匹配錯(cuò)誤，所以需要移除錯(cuò)誤的匹配點(diǎn)。

這里采用了RANSAC 對錯(cuò)誤的匹配點(diǎn)進(jìn)行處理，該算法可以有效去除錯(cuò)誤率超50%的匹配點(diǎn)，所以具有較好的穩(wěn)定性。并且這里是通過RANSAC 去除錯(cuò)誤點(diǎn)的大小去衡量預(yù)匹配的準(zhǔn)確率。

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

為了驗(yàn)證這里算法的合理性進(jìn)行了對照實(shí)驗(yàn)，主要是通過這里算法和FLANN算法的對照實(shí)驗(yàn)。通過該實(shí)驗(yàn)驗(yàn)證這里算法在不同像素、噪聲和對比度下的匹配準(zhǔn)確率。

該對比實(shí)驗(yàn)的仿真環(huán)境為CPU Intel（R）Core（TM）i5-4200M 2.50GHZ、RAM 4GB、開發(fā)環(huán)境為VS2015與OpenCv 3.1。

3.1 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

4 結(jié)束語

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