一種基于分?jǐn)?shù)階微分的FREAK改進(jìn)算法

顧亞軍，胡伏原

（蘇州科技大學(xué)電子與信息工程學(xué)院，江蘇蘇州215009）

一種基于分?jǐn)?shù)階微分的FREAK改進(jìn)算法

顧亞軍，胡伏原*

（蘇州科技大學(xué)電子與信息工程學(xué)院，江蘇蘇州215009）

隨著移動(dòng)設(shè)備（智能手機(jī)、移動(dòng)平板）技術(shù)的快速發(fā)展，移動(dòng)端的特征匹配研究受到了愈來愈多的關(guān)注。該文在FREAK（Fast Retina Keypoint）算法的框架下，引入分?jǐn)?shù)階微分，改進(jìn)特征表示環(huán)節(jié)，提高特征表示的準(zhǔn)確性；在特征匹配中考慮移動(dòng)設(shè)備計(jì)算能力不足的問題，引入層次化匹配策略提高特征匹配正確率。實(shí)驗(yàn)結(jié)果表明：改進(jìn)算法提取的特征點(diǎn)數(shù)目比原始算法提高了近30%，匹配正確率平均提高近40%。

分?jǐn)?shù)階微分；特征表示；圖模型；特征匹配

隨著移動(dòng)設(shè)備（智能手機(jī)、移動(dòng)平板）技術(shù)的快速發(fā)展，其應(yīng)用范圍日趨廣泛，手機(jī)地圖、全景拍攝、圖片美化等已成為各移動(dòng)終端的常用軟件。在這些應(yīng)用的處理過程中，圖像特征匹配都是一個(gè)關(guān)鍵步驟[1]。

在移動(dòng)端圖像特征匹配算法中，點(diǎn)特征因提取容易，匹配靈活[2]，受到普遍關(guān)注。其基本思想是通過獲取點(diǎn)特征周圍的紋理描述，并引入距離約束計(jì)算各點(diǎn)相似度以實(shí)現(xiàn)同名點(diǎn)對(duì)的匹配[3-7]。長(zhǎng)期以來，研究者希望設(shè)計(jì)具有高檢測(cè)率和重復(fù)率的特征，并能夠克服尺度、旋轉(zhuǎn)、光照及噪聲等外部情況影響。M.Calonder在2010年提出了BRIEF（Binary RobustIndependent Elementary Features）特征算法[8]，該方法通過隨機(jī)提取圖像塊（image patch）中的像素對(duì)，進(jìn)行τ測(cè)試組成二進(jìn)制比特串。為達(dá)到理想的描述精度，該策略產(chǎn)生的點(diǎn)對(duì)數(shù)目往往很大且忽略考慮特征方向，因此，特征在描述圖像時(shí)準(zhǔn)確性不理想。Rublee等人[9]結(jié)合了FAST（Features From Accelerated Segment Tes）和BRIEF，提出了ORB（An Efficient Alternative to SIFT or SURF）算法，在BRIEF基礎(chǔ)上使二值描述符具備了旋轉(zhuǎn)不變性，但在特征表示中，ORB忽略了圖像尺度的變化。為此Stefen Leutenegger提出了二值魯棒尺度不變點(diǎn)特征（Binary RobustInvariant Scalable Keypoints，BRISK）[10]，該方法首先建立圖像金字塔，采用FAST點(diǎn)檢測(cè)模板提取潛在特征點(diǎn)。在特征點(diǎn)附近采用有限抽樣點(diǎn)數(shù)目的抽樣模式（pattern）組成多個(gè)點(diǎn)對(duì)（pair）進(jìn)行τ測(cè)試，構(gòu)成點(diǎn)特征描述子。類似地，具有代表性研究的還有Alahi等人[11]提出的FREAK算法，該算法是一種基于人眼視網(wǎng)膜細(xì)胞分布的抽樣模式[12]，越靠近關(guān)鍵點(diǎn)中心的區(qū)域采樣點(diǎn)越密集，從而有效地提高了點(diǎn)描述的準(zhǔn)確性。

上述點(diǎn)特征檢測(cè)與表示的方法都是基于整數(shù)階微分計(jì)算得到的特征向量，這容易受到其他信息的干擾，且會(huì)大幅度地衰減低頻信息，尤其是處于平坦區(qū)域的目標(biāo)特征。而分?jǐn)?shù)階微分在圖像甚低頻是一種非線性保留，圖像在經(jīng)過其處理后，平滑區(qū)域的紋理特征不但沒有受到衰減，反而在一定程度上得到非線性保留。因此，文中結(jié)合分?jǐn)?shù)階微分改進(jìn)了FREAK特征表示方法；同時(shí)，為了提高點(diǎn)匹配精度，在距離相似度的基礎(chǔ)上引入形狀約束構(gòu)建結(jié)構(gòu)不變圖模型，通過層次化的匹配策略實(shí)現(xiàn)了適合于移動(dòng)設(shè)備的快速匹配。

1 FREAK算法

FREAK算法在特征提取時(shí)為滿足尺度不變性，首先構(gòu)建圖像尺度空間金字塔，并且在每一層使用FAST-9特征檢測(cè)模板提取潛在特征點(diǎn)，公式如下

其中I（x）為半徑為9的圓周上的像素點(diǎn)灰度，I（p）為中心點(diǎn)的灰度，εd為灰度差閾值，N代表滿足條件的周邊像素的數(shù)量。如果N大于給定的閾值（一般為圓周上像素點(diǎn)數(shù)量的三分之二），則可認(rèn)定p為一個(gè)潛在的特征點(diǎn)。由于FAST算法無法區(qū)分角點(diǎn)和邊緣點(diǎn)，因此，采用非極大值抑制方法對(duì)潛在特征點(diǎn)進(jìn)行優(yōu)化，提高特征點(diǎn)質(zhì)量。

在人眼視網(wǎng)膜成像和識(shí)別機(jī)制的啟發(fā)下，Alexandre提出在特征點(diǎn)周圍進(jìn)行區(qū)域采樣，示意圖如圖1所示。

圖1 視網(wǎng)膜采集模型

圖1中，中心點(diǎn)為特征點(diǎn)，周圍的采樣圓半徑隨著距離中心點(diǎn)距離的增大而變大并伴有部分重疊。選取中心對(duì)稱的取樣區(qū)域，計(jì)算圖像局部梯度值g（pi，pj）用于構(gòu)建特征點(diǎn)方向，并結(jié)合τ測(cè)試獲取點(diǎn)的二值描述子。局部梯度計(jì)算公式如下

2 基于分?jǐn)?shù)階微分改進(jìn)的FREAK算法

2.1 分?jǐn)?shù)階微分梯度算子

FREAK算法在特征提取時(shí)采用基于整數(shù)階微分梯度算子的FAST檢測(cè)算法，由幅頻特性曲線可知，經(jīng)過整數(shù)階微分處理過后的圖像在甚低頻有所抑制，圖像平滑區(qū)域特征點(diǎn)數(shù)量較少，難以準(zhǔn)確描述圖像局部信息，從而降低了圖像匹配正確率。而經(jīng)過分?jǐn)?shù)階微分處理過的圖像平滑區(qū)域的紋理細(xì)節(jié)不但沒有受到大幅度的線性衰減，反而在一定程度上實(shí)現(xiàn)了對(duì)紋理的非線性保留[13-16]。基于分?jǐn)?shù)階微分公式（1）變?yōu)?/p>

其中，v為分?jǐn)?shù)階微分的階次，一般選擇為0.3～0.7之間。為進(jìn)一步細(xì)化公式，假設(shè)圖像在X和Y軸的分?jǐn)?shù)階微分在一定條件下可分，則分?jǐn)?shù)階微分可表示為

為簡(jiǎn)化計(jì)算，較少時(shí)間開銷，取公式（4）前三項(xiàng)系數(shù)將代入式（3），則可得到基于分?jǐn)?shù)階微分的改進(jìn)FAST特征檢測(cè)梯度算子，公式如下

其中，p1為特征點(diǎn)p水平方向上左右兩個(gè)點(diǎn)的點(diǎn)集，p2為特征點(diǎn)p垂直方向上左右兩個(gè)點(diǎn)的點(diǎn)集，p3為圓周上剩余點(diǎn)的點(diǎn)集。

FREAK在特征描述時(shí)，采用對(duì)稱于中心點(diǎn)的采樣點(diǎn)對(duì)，根據(jù)公式（2）所示的梯度計(jì)算特征點(diǎn)主方向，計(jì)算簡(jiǎn)單但其也存在明顯的缺點(diǎn)。對(duì)于圖像平滑區(qū)域或者紋理復(fù)雜區(qū)域，其使用的整數(shù)階微分難以刻畫圖像局部特征點(diǎn)，使得在上述區(qū)域內(nèi)所得到的特征主方向不穩(wěn)定，從而導(dǎo)致處于同一場(chǎng)景中的同一特征點(diǎn)的描述子之間出現(xiàn)誤匹配。因此，考慮將分?jǐn)?shù)階微分引入梯度算子中，重新構(gòu)建基于分?jǐn)?shù)階微分的圖像局部梯度，公式如下

其中，Iv（p，σ）＝G（x，y，σ）*w（x，y）*I（x，y）進(jìn)行卷積運(yùn)算，w（x，y）為點(diǎn)I（x，y）的微分，其模板半徑大小與高斯模板相同。

2.2 基于結(jié)構(gòu)保持的層次化特征匹配

FREAK算法在特征匹配時(shí)采用單一Hamming距離策略，當(dāng)特征點(diǎn)數(shù)量較多時(shí)誤匹配率較高。基于此，文中在稠密點(diǎn)匹配[17]的啟發(fā)下，通過在引入形狀約束，從距離和角度兩個(gè)方面對(duì)特征點(diǎn)位置進(jìn)行約束，以期提高特征匹配的正確率。此外，針對(duì)移動(dòng)設(shè)備計(jì)算能力不足的缺點(diǎn)，采用層次化的匹配方法，以有效避免算法中的推理和學(xué)習(xí)過程，提高特征匹配效率。

2.2.1層次化的特征匹配

在圖像特征匹配中，通常使用Hamming距離進(jìn)行點(diǎn)特征的相似性檢測(cè)，公式如下

其中，ξ為設(shè)定的閾值，其大小關(guān)系著圖像特征匹配的正確率。如其值設(shè)定過小，則匹配要求過于嚴(yán)格，正確率也隨之下降。但其也存在下限值，當(dāng)?shù)陀诖讼孪拗禃r(shí)，特征匹配正確率保持不變。受此啟發(fā)，文中通過設(shè)定ξ值來構(gòu)建強(qiáng)匹配點(diǎn)對(duì)集合，即ξ值較小時(shí)的正確匹配點(diǎn)對(duì)。對(duì)于弱匹配點(diǎn)對(duì)，即未能成功匹配的點(diǎn)對(duì)，通過周圍強(qiáng)匹配對(duì)進(jìn)行結(jié)構(gòu)輔助匹配。為降低算法時(shí)間復(fù)雜度，在強(qiáng)匹配點(diǎn)對(duì)隨機(jī)選取兩對(duì)，構(gòu)建結(jié)構(gòu)保持的層次化匹配模型進(jìn)行搜索匹配。

（1）強(qiáng)匹配點(diǎn)對(duì)集構(gòu)建：利用公式（7），通過設(shè)定較小的ξ值來獲得匹配度大的關(guān)鍵點(diǎn)對(duì)Vm，公式如下

表1 圖約束層次化匹配方法實(shí)現(xiàn)步驟

（2）弱匹配點(diǎn)對(duì)匹配：對(duì)圖像中未構(gòu)成匹配的特征點(diǎn)對(duì)進(jìn)行匹配，考慮特征點(diǎn)之間結(jié)構(gòu)相似性和距離約束，構(gòu)建結(jié)構(gòu)保持的圖模型

式中，φ為特征點(diǎn)對(duì)之間的相似度；（α，β）為兩幅圖像中的特征點(diǎn)點(diǎn)集；χm＝（xm，ym）為點(diǎn)m的位置。在特征點(diǎn)匹配時(shí)，s值越大，說明匹配度越高。

2.2.2結(jié)構(gòu)保持的圖匹配

通常情況下，可以通過推理與學(xué)習(xí)的方法求解公式（9）。但考慮到移動(dòng)設(shè)備對(duì)圖模型的推理和計(jì)算能力不足，因此，文中采取隨機(jī)在Vm中取兩對(duì)強(qiáng)匹配點(diǎn)，并引入角度變化簡(jiǎn)化圖模型

式中，w1，w2為權(quán)重系數(shù)，代表了距離和角度對(duì)結(jié)果s的貢獻(xiàn)度，一般情況下設(shè)為相同的值。適于移動(dòng)應(yīng)用的匹配示意圖如圖2所示。

圖2 適于移動(dòng)應(yīng)用的特征匹配示意圖

圖中{A1，A2}，{B1，B2}為Vm中隨機(jī)選取的兩對(duì)強(qiáng)匹配點(diǎn)。為快速預(yù)測(cè)待匹配點(diǎn)的位置，利用三角形的△A1B1C1～△A2B2C2和下式，在圖像patch2中尋找patch1中點(diǎn)C1的匹配點(diǎn)可能存在的區(qū)域R。然后通過公式（10），在R區(qū)域中尋找到s值最大的點(diǎn)即為匹配點(diǎn)。算法實(shí)現(xiàn)步驟見如表1。

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

為驗(yàn)證文中算法的有效性，將改進(jìn)算法與原始算法分別基于iPhone6進(jìn)行特征表示和特征匹配對(duì)比實(shí)

驗(yàn)。實(shí)驗(yàn)中選取Mikolajczyk和Schmid所使用的Graffiti庫(kù)[18]作為標(biāo)準(zhǔn)測(cè)試庫(kù)，通過模擬現(xiàn)實(shí)環(huán)境中存在的各種干擾因素（模糊、光照、旋轉(zhuǎn)及尺度變換）充分驗(yàn)證文中算法的魯棒性。

3.1 特征點(diǎn)提取實(shí)驗(yàn)對(duì)比

將特征點(diǎn)提取實(shí)驗(yàn)分為四組，分別對(duì)應(yīng)上述四種不同的圖像變換，并且在每組中選擇兩幅圖片對(duì)改進(jìn)算法與原始算法在特征點(diǎn)數(shù)量上進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖3所示，詳細(xì)實(shí)驗(yàn)數(shù)據(jù)見表2。從實(shí)驗(yàn)結(jié)果圖可以看出，改進(jìn)算法相比原始算法在圖像平滑區(qū)域提取的特征點(diǎn)數(shù)量明顯增多。且從表2中實(shí)驗(yàn)數(shù)據(jù)可以看出，圖像整體特征檢測(cè)數(shù)量也有明顯上升，平均新增率達(dá)到30%左右。

圖3 圖像特征點(diǎn)提取比較

表2 特征提取實(shí)驗(yàn)詳細(xì)數(shù)據(jù)對(duì)比

3.2 特征點(diǎn)匹配

為驗(yàn)證文中算法的有效性，將分別從特征匹配成功率、正確匹配新增率兩個(gè)方面對(duì)改進(jìn)算法、原始算法、ORB算法及BRISK算法進(jìn)行全面分析對(duì)比，實(shí)驗(yàn)結(jié)果如圖4所示，詳細(xì)實(shí)驗(yàn)數(shù)據(jù)見表3。

圖4 特征匹配對(duì)比

表3 特征匹配實(shí)驗(yàn)詳細(xì)數(shù)據(jù)對(duì)比

從實(shí)驗(yàn)結(jié)果圖和數(shù)據(jù)對(duì)比中可以看出，經(jīng)過改進(jìn)匹配方法的匹配正確率都較高，且相比原始算法匹配正確率有大幅提高（方向一致的正確匹配線密集，錯(cuò)誤匹配線稀疏）。其中，在旋轉(zhuǎn)變化中，由于兩幅圖像旋轉(zhuǎn)角度偏大（60°），因此，匹配結(jié)果略低，但與其他結(jié)果相比，仍然具有很好的魯棒性。

4 結(jié)語

近年來，移動(dòng)端圖像特征匹配受到越來越多的關(guān)注，但由于移動(dòng)端的特殊性，特征匹配的結(jié)果不甚滿意。為此，文中提出了一種適于移動(dòng)應(yīng)用的改進(jìn)FREAK算法，著重對(duì)特征表示和匹配中的兩個(gè)關(guān)鍵步驟進(jìn)行改進(jìn)。通過實(shí)驗(yàn)表明，經(jīng)過改進(jìn)的FREAK算法在特征提取數(shù)量以及匹配正確率方面都有較大提高。

[1]張麗敏.基于分?jǐn)?shù)階微積分的圖像特征匹配的方法研究[D].重慶：重慶大學(xué)，2011.

[2]賈棋，高新凱，羅鐘鉉.基于幾何約束的特征點(diǎn)匹配方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015，27（8）：1388-1397.

[3]李映，崔楊楊，韓曉宇.基于線特征和控制點(diǎn)的可見光SAR圖像配準(zhǔn)[J].自動(dòng)化學(xué)報(bào)，2012，38（12）：1968-1964.

[4]LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[5]KE Y，SUKTHANKAR R.PCA-SIFT：a more distinctive representation for local image descriptors[C]//Proceedings ofIEEE Computer Society Conference on Computer Vision and Pattern Recognition.IEEE，2004：506-513.

[6]BAY H，TUYTELAARS T，GOOL L V.SURF：speed up robust features[C]//Proceedings of the European Conference on Computer Vision.IEEE，2006：404-417.

[7]ENGIN T，VINCENT L，PASCAL F.DAISY：an efficient dense descriptor applied to width-baseline stereo[J].IEEE Transactions on Pattern Analysis MachineIntelligence，2010，32（5）：815-830.

[8]CALONDER M，LEPETIT V，STRECHA C，et al.BRIEF：binary robust independent elementary features[C]//Proceedings of the 11th European conference on Computer vision：PartIV.Springer-Verlag，2010：778-792.

[9]RUBLEE E，RABAUD V，KONOLIGE K，et al.ORB:An efficient alternative to SIFT or SURF[J].Proceedings，2011，58（11）：2564-2571.

[10]LEUTENEGGER S，CHLIM，SIEGWART R Y.BRISK：Binary Robust invariant scalable keypoints[C]//Computer Vision（ICCV），2011IEEEInternational Conference on.IEEE，2011：2548-2555.

[11]ORTIZ R.FREAK：Fast Retina Keypoint[C]//IEEE Conference on Computer Vision and Pattern Recognition.IEEE，2012：510-517.

[12]OLSHAUSEN B A，F(xiàn)IELD D J.What is the other 85%of V1 doing?[C]//23 Problems in Systems Neuroscience，2004.

[13]姒紹輝，胡伏原，付保川，等.自適應(yīng)非整數(shù)步長(zhǎng)的分?jǐn)?shù)階微分掩模的圖像紋理增強(qiáng)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（9）：1438-1449.

[14]周激流，蒲亦非，廖科.分?jǐn)?shù)階微積分原理及其在現(xiàn)代信號(hào)分析與處理中的應(yīng)用[M].北京：科學(xué)出版社，2010.

[15]HU F，SIS，WONG H S，et al.An adaptive approach for texture enhancement based on a fractional differential operator with non-integer step and order[J].Neurocomputing，2014，158：295-306.

[16]胡伏原，姒紹輝，張艷寧，等.自適應(yīng)分?jǐn)?shù)階微分的復(fù)合雙邊濾波算法[J].中國(guó)圖象圖形學(xué)報(bào)，2013，18（10）：1237-1246.

[17]ZHANG L，MAATEN L J P V D.Preserving structure in model-free tracking[J].IEEE Transactions on Pattern Analysis&MachineIntelligence，2014，36（4）：756-769.

[18]MIKOLAJCZYK K，TUYTELAARS T，SCHMID C，et al.A comparison of affine region detectors[J].International Journal of Computer Vision，2005，65（1/2）：43-72.

An improved FREAK algorithm based on fractional differential

GU Yajun，HU Fuyuan
（School of Electronic&Information Engineering，SUST，Suzhou 215009，China）

With the rapid technology development of mobile devices（smart phones,mobile tablet），the research on the characteristics of mobile terminals has received increasing attention.Based on the FREAK（Fast Retina Keypoint）algorithm,we introduced fractional differential to improve the feature representation accuracy.Taking the deficiency of computing capability of mobile devices into consideration,we introduced the concept of hierarchical matching strategy to improve the feature matching accuracy.The experimental results show that the improved algorithm can improve the number of feature points by nearly 30%and the matching accuracy by 40%against the original algorithm.

fractional differential；feature representation；graph model；feature matching

O175；TP391

A

1672－0687（2016）04－0062－06

責(zé)任編輯：艾淑艷

2016－04－05

國(guó)家自然科學(xué)基金資助項(xiàng)目（61472267）

顧亞軍（1990-），男，江蘇泰州人，碩士研究生，研究方向：移動(dòng)端特征匹配。

*通信聯(lián)系人：胡伏原（1978-），男，教授，博士，碩士生導(dǎo)師，E-mail：fuyuanhu@mail.usts.edu.cn。