一種改進(jìn)的SIFT圖像特征匹配算法

張永，武玉建

ZHANG Yong,WU Yu-jian

蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，蘭州 730050

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

1 引言

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

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

2 SIFT算法的基礎(chǔ)理論

2.1 特征點(diǎn)提取

SIFT特征點(diǎn)提取算法的步驟如下：

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

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

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

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

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

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

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

3 SIFT算法的改進(jìn)

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

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

本文利用內(nèi)核投影技術(shù)對(duì)傳統(tǒng) SIFT算法進(jìn)行改進(jìn)，其中的關(guān)鍵就是選擇合適的內(nèi)核函數(shù)。Walsh-Hadamard內(nèi)核函數(shù)因?yàn)榫哂辛己玫谋鎰e能力和計(jì)算效率[9]，而被選擇用來(lái)改進(jìn) SIFT算法。Walsh-Hadamard內(nèi)核函數(shù)可以表示為：

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

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

3.2 改進(jìn)的SIFT特征描述算子

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

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

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

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

3.3 特征匹配

在生成36維的SIFT特征描述算子后，以歐式距離作為相似度準(zhǔn)則對(duì)2個(gè)特征點(diǎn)進(jìn)行匹配。假設(shè)特征點(diǎn)對(duì) p和q的特征描述算子分別為Desp和 Desq，其歐氏距離定義為：

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

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

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

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

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

表1 改進(jìn)算法與SIFT算法的匹配時(shí)間比較

光照升高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 改進(jìn)算法與SIFT算法的匹配性能比較

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

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

5 結(jié)束語(yǔ)

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

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

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

[3]李中科,吳樂(lè)南.基于霍夫變換和相位相關(guān)的圖像配準(zhǔn)方法[J].信號(hào)處理,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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2010,22(2):286-292.

[8]孫農(nóng)亮,李煥煥,楊寧,等.基于SIFT二次匹配方法的同名像點(diǎn)識(shí)別[J].計(jì)算機(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.