張永，武玉建

ZHANG Yong,WU Yu-jian

蘭州理工大學 計算機與通信學院，蘭州 730050

School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050,China longteng001007@163.com

1 引言

作為數(shù)字圖像處理技術(shù)的重要組成部分，圖像匹配已經(jīng)被廣泛應用于傳感器信息融合、圖像差異性檢測、目標跟蹤與識別等領(lǐng)域。基于特征點的圖像匹配算法作為當前圖像匹配技術(shù)的主流方向和發(fā)展趨勢，得到了國內(nèi)外研究學者的關(guān)注，很多匹配算法也隨之被提出，比如基于模板的方法[1]、基于比值的方法[2]、相位相關(guān)法[3]等。但是以上算法均要求待匹配的圖像間要有一致的焦距，同時不能存在尺度縮放、旋轉(zhuǎn)、光照變化等情況，這就大大制約了算法的應用。具有尺度不變性的圖像匹配算法隨之被提出，其中基于局部不變性描述算子（Local Invariant Descriptor，LID）的方法在圖像匹配方面取得了顯著的進展。2004年，David G. Lowe教授提出了 SIFT（Scale Invariant Feature Transform）算法[4]。該算法能夠較好解決因場景部分遮擋、旋轉(zhuǎn)、縮放、視點變化而引起的圖形變化等問題，并已經(jīng)成功地應用于目標識別、圖像復原、圖像拼接等領(lǐng)域。然而，SIFT算法構(gòu)造的特征描述算子具有128維，高維度造成了計算復雜度過高。因此，許多學者對其進行了相關(guān)改進。文獻[5]提出了 SURF(Speeded Up Robust Features)算子，將Hessian矩陣和Haar小波相結(jié)合，使得特征描述算子的維度降為 64維。在文獻[6]中，主成分分析法 PCA(Principal Components Analysis)將傳 統(tǒng)SIFT算法的128維的特征描述算子降低至36維，但是PCA方法在構(gòu)造特征描述算子的計算量甚至超過了傳統(tǒng)SIFT，這就大大抵消了降維帶來的速度提高。文獻[7]將旋轉(zhuǎn)不變 LBP(Local Binary Patterns)與SIFT結(jié)合，降低了計算復雜度，但對圖像視角變化有嚴格要求。文獻[8]在標準 SIFT算法中引入全局幾何約束與唯一性約束，在不提高匹配時間的同時提高了匹配精度，其不足在于閾值的設定較為困難。

本文提出一種改進的SIFT算法，采用內(nèi)核投影算法對其進行改進，降低SIFT特征描述算子的維度，以達到提高匹配效率的目的。

2 SIFT算法的基礎理論

2.1 特征點提取

SIFT特征點提取算法的步驟如下：

（1） 檢測圖像尺度空間的極值。先對原始圖像進行一系列的高斯濾波，以此得到圖像的高斯空間。

此過程可以看作為當可變核參數(shù)σ取不同值時，可變高斯核函數(shù)G(x,y,σ)與輸入圖像I(x,y)進行卷積，由此得到圖像的尺度空間。其中，。由存在常數(shù)乘性尺度因子k的相鄰高斯差分函數(shù)與原始圖像進行卷積可形成高斯差分尺度空間（Difference of Gaussian）。

取此高斯差分尺度空間中的局部極值，便得到尺度空間的圖像特征點。對圖像進行高斯濾波保證特征點不受噪聲影響；對尺度空間的差分處理使特征點對光照變化具有魯棒性；在高斯差分空間中提取極值點保證了尺度不變性。

2.2 SIFT特征描述算子的構(gòu)造

構(gòu)造特征描述算子是為了確定特征點的主方向，而后在進行匹配時就可以把圖像旋轉(zhuǎn)到主方向，以保證圖像的旋轉(zhuǎn)不變性。),(yx 處的梯度值和方向分別為：

在以特征點為中心的鄰域窗口內(nèi)取樣，同時運用梯度直方圖來統(tǒng)計鄰域像素的梯度方向，直方圖的最高峰值點對應的方向即為主方向。

以特征點為中心取8×8的窗口，然后在4×4的圖像分塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，形成一個種子點。每個特征點用4×4共16個種子點描述，而每個種子點有8個方向向量信息，因此每個特征點可以產(chǎn)生128844=××個數(shù)據(jù)。由此，可以形成128維的SIFT特征向量或特征描述算子。

3 SIFT算法的改進

采用傳統(tǒng)SIFT算法可以生成穩(wěn)定的SIFT特征點，但其中的缺陷在于特征描述算子的生成過程中采用了主方向旋轉(zhuǎn)和統(tǒng)計梯度直方圖的方法，生成的特征描述算子具有128維，高維度造成了很大的計算量，從而影響了SIFT算法的實時性。改進算法的思想是降低特征描述算子的維度，來降低算法的計算量，提高匹配速度。

3.1 Walsh-Hadamard內(nèi)核投影

本文利用內(nèi)核投影技術(shù)對傳統(tǒng) SIFT算法進行改進，其中的關(guān)鍵就是選擇合適的內(nèi)核函數(shù)。Walsh-Hadamard內(nèi)核函數(shù)因為具有良好的辨別能力和計算效率[9]，而被選擇用來改進 SIFT算法。Walsh-Hadamard內(nèi)核函數(shù)可以表示為：

內(nèi)核矩陣只有+1和-1兩種元素，因而在計算過程中只有加減運算而沒有乘法運算，從而大大提高了運算速度。這一點對圖像處理來說是至關(guān)重要的，特別是在實時處理大量數(shù)據(jù)時，Walsh-Hadamard更能顯示出其優(yōu)越性。8階的二維Walsh-Hadamard內(nèi)核函數(shù)如圖 1所示，其中白色區(qū)域代表+1，黑色區(qū)域代表-1。

圖1 二維Walsh-Hadamard內(nèi)核函數(shù)

3.2 改進的SIFT特征描述算子

改進的SIFT算法主要是對于SIFT特征描述算子的改進。特征點的提取方法與傳統(tǒng)的 SIFT相同，得到特征點位置以及主方向。首先，根據(jù)得到的特征點的位置信息以及特征點所在的尺度將以特征點為中心的一個區(qū)域作為圖像子塊，并將圖像子塊內(nèi)所有像素點的梯度方向調(diào)整至主方向，得到了規(guī)范化的圖像子塊。根據(jù)實驗經(jīng)驗，實際應用中取以特征點為中心的 32×32大小的區(qū)域取得的效果最佳。

然后，在得到規(guī)范化的圖像子塊之后，計算出該子塊的方向梯度矩陣Gθ(x，y),其中θ包含4種方向：0（水平方向），4/π，2/π（豎直方向）和 4/3π 。圖像子塊中的不同方向的梯度矩陣可以通過下式得：

在上式中，σ為圖像子塊寬度的四分之一。經(jīng)過高斯平滑濾波之后，遠離子塊中心的梯度值對最終結(jié)果的不利影響也被消除。

最后，對獲得的方向梯度矩陣進行Walsh-Hadamard內(nèi)核投影，對于前12個投影值，取其水平梯度、豎直梯度；對于前6個投影值還需取其和Gπ/4(x,y)。由此就得到12×2+6×2=36維的特征描述算子。

3.3 特征匹配

在生成36維的SIFT特征描述算子后，以歐式距離作為相似度準則對2個特征點進行匹配。假設特征點對 p和q的特征描述算子分別為Desp和 Desq，其歐氏距離定義為：

采用優(yōu)先k-d樹進行優(yōu)先搜索，查找每個特征點的兩個近似最近鄰特征點。找到特征點p歐氏距離最近和次近的兩個相鄰特征點q′和q′′，然后計算（p，q′）和（p，q′′）兩組特征描述算子之間的歐氏距離比λ。如果比值λ小于給定的閾值T，則認為匹配成功，接受匹配點對（p，q′）。其中跟據(jù)后續(xù)實驗驗證，在閾值 T為 0.8時效果最好。

最后采用隨機抽樣一致性算法（Random Sample Consensus，RANSAC）[10]不斷在所有特征點對計算透視變換模型，統(tǒng)計符合模型的內(nèi)點，剔除錯誤匹配的特征點對，得到精確的圖像變換模型。

4 實驗結(jié)果

本文實驗結(jié)果如下：CPU為酷睿i5-2410M，內(nèi)存2GB，顯存1GB，操作系統(tǒng)為win7，仿真平臺為Matlab 9.0。

本文選取國際標準測試圖像Lena圖片(256×256)，在光照變化、尺度變化、旋轉(zhuǎn)變化等條件下對改進的SIFT算法進行測試。標準圖像共檢測出特征點382個，比較改進算法與SIFT算法在匹配時間上的差異，結(jié)果如表1所示。比較改進算法與傳統(tǒng) SIFT算法在匹配率和誤匹配率上的差異，結(jié)果如表2所示。

表1 改進算法與SIFT算法的匹配時間比較

光照升高50%420 124 317.23 420 124 329.47圖像翻轉(zhuǎn) 377 341 310.82 371 341 321.46圖像旋轉(zhuǎn)45°501 246 370.13 382 246 386.52尺度增大2倍506 158 330.61 506 158 342.12

表2 改進算法與SIFT算法的匹配性能比較

由表1與表2數(shù)據(jù)可知，在圖像存在尺度變化、旋轉(zhuǎn)以及光照變化時，改進的SITF算法保持了傳統(tǒng)SIFT算法的高匹配精度，并且匹配時間有所減少，對 SIFT算法的實時性有所提高。圖 2為利用改進SIFT算法的特征匹配結(jié)果。

圖2 改進SIFT算法的匹配結(jié)果

5 結(jié)束語

本文提出一種改進的SIFT算法，通過內(nèi)核投影技術(shù)改進 SIFT特征描述算子進而降低特征描述算子維度，從而降低了算法的計算復雜度，減少了匹配時間。實驗結(jié)果表明，改進算法在保證了SIFT較高匹配精度以及尺度不變性，同時提高了算法效率。

[1]劉臻,宮鵬,史培軍.基于分層多模板匹配的影像自動配準方法研究[J].計算機應用,2005,25(2):322-325.

[2]張少輝,沈曉蓉,范耀祖.一種基于圖像特征點提取及匹配的方法[J].北京航空航天大學學報,2008,34(5):516-519.

[3]李中科,吳樂南.基于霍夫變換和相位相關(guān)的圖像配準方法[J].信號處理,2004,20(2):167-169.

[4]Lowe D G. Distinctive Image Features from Scale-invariant Keypoints [J]. International Journal of Computer Vision,2004,60(2):91-110

[5]Herbert Bay , Andreas Ess , Tinne Tuytelaars ,Luc Van Gool.Speeded-Up Robust Features(SURF) [C].CVIU,2008,110(3):346-359.

[6]Yan Ke, Rahul Sukthankar. PCA-SIFT:A More Distinctive Representation for Local Image Descriptors[C]//Proceedings of the Conferen--ce on Computer Vision and Pattern Recogniti--on, Washington , USA , 2004:511-517.

[7]鄭永斌,黃新生,豐松江.SIFT和旋轉(zhuǎn)不變 LBP相結(jié)合的圖像匹配算法[J].計算機輔助設計與圖形學學報,2010,22(2):286-292.

[8]孫農(nóng)亮,李煥煥,楊寧,等.基于SIFT二次匹配方法的同名像點識別[J].計算機工程,2012,38(4):155-157.

[9]Yacov Hel-Or , Hagit Hel-Or.Real-Time Pattern Matching Using Projection Kernels [J].IEEE Computer Society,2005,27(9):1430-1445.

[10]Fischler M A, Bolles R C. Random Sample Consensus: A Paradigm for Model Fitting With Applications to Image Analysis and Automated Cartography [J]. Communications of ACM,1981, 24(6):381-395.