顧亞軍，胡伏原

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

一種基于分數(shù)階微分的FREAK改進算法

顧亞軍，胡伏原*

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

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

分數(shù)階微分；特征表示；圖模型；特征匹配

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

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

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

1 FREAK算法

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

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

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

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

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

2 基于分數(shù)階微分改進的FREAK算法

2.1 分數(shù)階微分梯度算子

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

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

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

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

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

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

2.2 基于結構保持的層次化特征匹配

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

2.2.1層次化的特征匹配

在圖像特征匹配中，通常使用Hamming距離進行點特征的相似性檢測，公式如下

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

（1）強匹配點對集構建：利用公式（7），通過設定較小的ξ值來獲得匹配度大的關鍵點對Vm，公式如下

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

（2）弱匹配點對匹配：對圖像中未構成匹配的特征點對進行匹配，考慮特征點之間結構相似性和距離約束，構建結構保持的圖模型

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

2.2.2結構保持的圖匹配

通常情況下，可以通過推理與學習的方法求解公式（9）。但考慮到移動設備對圖模型的推理和計算能力不足，因此，文中采取隨機在Vm中取兩對強匹配點，并引入角度變化簡化圖模型

式中，w1，w2為權重系數(shù)，代表了距離和角度對結果s的貢獻度，一般情況下設為相同的值。適于移動應用的匹配示意圖如圖2所示。

圖2 適于移動應用的特征匹配示意圖

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

3 實驗結果分析

為驗證文中算法的有效性，將改進算法與原始算法分別基于iPhone6進行特征表示和特征匹配對比實

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

3.1 特征點提取實驗對比

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

圖3 圖像特征點提取比較

表2 特征提取實驗詳細數(shù)據(jù)對比

3.2 特征點匹配

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

圖4 特征匹配對比

表3 特征匹配實驗詳細數(shù)據(jù)對比

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

4 結語

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

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

[2]賈棋，高新凱，羅鐘鉉.基于幾何約束的特征點匹配方法[J].計算機輔助設計與圖形學學報，2015，27（8）：1388-1397.

[3]李映，崔楊楊，韓曉宇.基于線特征和控制點的可見光SAR圖像配準[J].自動化學報，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]姒紹輝，胡伏原，付保川，等.自適應非整數(shù)步長的分數(shù)階微分掩模的圖像紋理增強算法[J].計算機輔助設計與圖形學學報，2014，26（9）：1438-1449.

[14]周激流，蒲亦非，廖科.分數(shù)階微積分原理及其在現(xiàn)代信號分析與處理中的應用[M].北京：科學出版社，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]胡伏原，姒紹輝，張艷寧，等.自適應分數(shù)階微分的復合雙邊濾波算法[J].中國圖象圖形學報，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

責任編輯：艾淑艷

2016－04－05

國家自然科學基金資助項目（61472267）

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

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