基于改進SIFT算法的圖像匹配方法研究

夏 杰，李奇安，李 悅，單海歐

（遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001）

圖像匹配就是運用算法將不同條件下攝取的兩幅或多幅圖像在空間上進行相互匹配。目前圖像匹配已經(jīng)廣泛地運用于社會多種領(lǐng)域，比如空間物體三維重建、模式識別以及目標(biāo)物運動分析等。

傳統(tǒng)的圖像匹配算法計算量較大，在圖像目標(biāo)發(fā)生旋轉(zhuǎn)、縮放、光照等參數(shù)發(fā)生變化時適應(yīng)力不強。近年來，在計算機視覺領(lǐng)域中，基于局部不變量描述符的算法在圖像匹配方面取得了令人矚目的進展。

David G.Lowe教授提出一種基于尺度空間的、對圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征描述算子——SIFT算法[1]。

SIFT算法可以很好地解決旋轉(zhuǎn)和縮放在圖像匹配過程中的影響，但在實時性上存在不足。許多研究人員對該算法進行了改進，例如，Yan Ke的 PCA-SIFT方法[2]；Mikolajczy的GLOH算法[3]；劉立等人用圓形窗口的12維向量作為特征描述子的方法[4]；劉健等人采用對數(shù)極坐標(biāo)變換、信息熵原理提取SIFT特征和不變矩特征，構(gòu)造新型特征描述符進行匹配的方法[5]；王曉華等人以街區(qū)距離和棋盤距離的線性組合代替歐式距離作為特征描述符之間的相似性度量的方法[6]。改進的算法很多，大多是改進特征向量的計算方法，提高算法速度的方法，但效果不太理想。筆者針對SIFT算法的不足，提出了以街區(qū)距離代替歐式距離的新方法來提高SIFT特征匹配效率。

1 SIFT算法簡介

SIFT算法分為4步，即檢測尺度空間中的極值點，精確定位檢測到的極值點位置，為極值點分配方向，生成描述極值點的SIFT特征向量。

1.1 檢測尺度空間極值點

一幅二維輸入圖像 I（x，y）和尺度可變高斯函數(shù) G（x，y，σ）卷積可得到該輸入圖像的尺度空間 L（x，y，σ）如式（1）。

其中，（x，y）是每個像素在輸入圖像中的空間坐標(biāo)，符號*表示卷積，σ是高斯正態(tài)分布的方差，也是尺度空間因子，σ越小，圖像被平滑的越少，尺度也就越小。

不同尺度空間的差分生成高斯差分尺度空間（DOG scale-space），即 D（x，y，σ），DOG 空間可以有效的在尺度空間內(nèi)檢測到穩(wěn)定的關(guān)鍵點。尺度空間域上的圖像特征點由常數(shù)乘性尺度因子k的相鄰尺度高斯差分與圖像卷積生成：

DOG空間檢測極值時，將關(guān)鍵點在同尺度周圍的鄰域8個像素和上下相鄰對應(yīng)尺度位置的周圍鄰域9×2個像素總共26個像素相互比較。

1.2 精確定位極值點

DOG算子會產(chǎn)生較強的邊緣響應(yīng)，對DOG算子進行檢驗后，精確定位為特征點。剔除對噪聲很敏感的點和不穩(wěn)定的邊緣響應(yīng)點后，剩余的特征點匹配能力和抗噪聲能力都比較強。低對比度的點用擬合三維二次函數(shù)濾除，得到亞像素精度關(guān)鍵點的位置和尺度。

1.3 極值點方向分配

關(guān)鍵點鄰域像素的梯度方向分布特性為圖像中的任一關(guān)鍵點確定方向，使算子具備旋轉(zhuǎn)不變性。

像素點的梯度表示為：

式（4）、（5）分別是像素（x，y）處梯度的模值和方向，L 為每個極值點各自所在的尺度。

1.4 生成SIFT特征向量

任一尺度內(nèi)，以關(guān)鍵點為中心的鄰域內(nèi)進行像素采樣，計算出像素梯度方向的直方圖，轉(zhuǎn)換為128維的特征向量。實際操作是，以關(guān)鍵點為中心取一個正方形塊，平均分為8×8的小格，計算每4×4的小塊上8個方向的直方圖，產(chǎn)生128個數(shù)據(jù)，即128維的SIFT特征向量。SIFT特征向量長度歸一化，可以去除尺度變化、旋轉(zhuǎn)等幾何變形和光照因素的影響。

2 對特征匹配算法的改進

原SIFT算法在特征向量的計算過程中，采用主方向旋轉(zhuǎn)并統(tǒng)計梯度直方圖的方式，生成128維特征向量。圖像特征匹配時計算量相當(dāng)龐大，占算法全部時間的50%左右，直接影響SIFT算法的實時性。文中改進算法的主要思想是減少特征向量的計算量，提高特征匹配速度。

原SIFT算法匹配圖像時，需要一幅圖像中的特征點和另外一幅圖像中的所有特征點進行匹配，每一個特征點有128維數(shù)據(jù)，計算量之大可想而知。改進的SIFT算法是在特征向量匹配中，通過街區(qū)距離代替歐式距離，通過極限幾何約束消除多的錯誤匹配點對，減少匹配時間，提高算法的匹配效率，盡可能地提高SIFT的實時性。

原SIFT算法特征向量提取時，采用歐氏距離函數(shù)作為特征的相似性度量，歐氏距離是兩個像素之間的直線距離，在二維情況下定義為：

而街區(qū)距離是二維圖像中相應(yīng)情形的推廣距離，即

其中（x1，y1），（x2，y2）分別是兩個像素的二維坐標(biāo)，比較公式（6）和（7）可看出，L1比 L0計算量少。用線性組合后的 L1代替L0，可以降低圖像匹配過程的計算量，同時減少計算的偏差。 定義一個參數(shù) α，以 αL1代替 L0，即 L0=αL1。 很明顯，L0要進行128次乘法和一次開平方的運算；而L1只需要一次乘法運算。如果圖像中生成128維的SIFT特征點有k個，則每個特征點都減少了127 k次計算。算法改進后，圖像匹配的匹配點對就是兩點間距離最短的特征向量。此方法明顯縮短了運算時間，提高了算法的效率。

3 仿真實驗及結(jié)果分析

本次仿真利用MATLAB7.0編程，運行在配置為Pentium（R） Dual－Core CPU E5700 3.0 GHz、2.00 GB RAM、操作系統(tǒng)為Microsoft Windows7的微機平臺上。文中選取內(nèi)容和背景比較復(fù)雜的圖像 a（圖 1）和b（圖2），經(jīng)過多次反復(fù)實驗，測算出錯誤匹配對、算法時間和匹配率。匹配的過程中，對算法中的值不斷的調(diào)試，經(jīng)過大量的測試，最合適的值在0.600～1.500之間。實驗結(jié)果如下，圖1和圖2為原始圖像a和b，在拍攝時進行了相機平移、轉(zhuǎn)動和變焦操作；分別對原始圖像a和原始圖像b檢測SIFT特征，圖像a有1 147個特征點，圖像b有1 032個特征點；圖3是原SIFT算法匹配的結(jié)果，圖4是改進SIFT算法的結(jié)果。圖像匹配的匹配率是SIFT特征對減去錯誤匹配對后的值除以SIFT特征對的百分比，比較數(shù)據(jù)如表1所示。

表1 圖像匹配比較數(shù)據(jù)Tab.1 Comparative data of image matching

圖1 原始圖像aFig.1 Original image a

圖2 原始圖像bFig.2 Original image b

圖3 原SIFT算法匹配的結(jié)果Fig.3 Results of the original SIFT algorithm matching

圖4 改進SIFT算法匹配的結(jié)果Fig.4 Results of the improved SIFT algorithm matching

對比后可明顯看出改進算法在匹配率上比原SIFT算法高，匹配時間減少，雖然總的匹配特征對要少，但對匹配的結(jié)果影響不大。匹配率增大的同時，匹配的精度略有提高，圖像的尺度、光照、視角以及噪聲所導(dǎo)致的干擾也隨之降低。本文提出的改進圖像匹配特征向量的計算方法，減少了運算時間，提高了圖像匹配算法的實時性。

4 結(jié)束語

本文研究原SIFT算法后，在特征向量匹配過程中，用街區(qū)距離代替歐式距離實現(xiàn)圖像的匹配。實驗結(jié)果達到了預(yù)定目標(biāo)，在滿足匹配率的同時，減少了匹配時間，提高了圖像特征匹配的實時性。SIFT算法的可擴展性很強，可以輕松地與其他特征檢測方法相結(jié)合，在今后的研究中，希望可以使用PCA-SIFT、CSIFT、SURF、ASIFT 等算法來實現(xiàn)圖像匹配。

[1]Lowe D.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision，2004，60（2）:91-110.

[2]Ke Y，Sukthankar R.Pca-Sift:a more distinctive representation for local image descriptors [C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Washington，2004.

[3]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors，pattern analysis and Machine Intelligence[J].IEEE Transactions，2005，27（10）:1615-1630.

[4]劉立，彭復(fù)員，趙坤.采用簡化SIFT算法實現(xiàn)快速圖像匹配[J].紅外與激光工程，2008，37（1）:181-184.LIU Li，PENG Fu-yuan，ZHAO Kun.Simplified SIFT algorithm for fast image matching[J].Infrared and Laser Engineering.2008，37（1）:181-184.

[5]劉健，張國華，黃琳琳.基于改進SIFT的圖像配準(zhǔn)算法[J].北京航空航天大學(xué)學(xué)報，2010，36（9）:1121-1124.LIU Jian，ZHANG Guo-hua，HUANG Lin-lin.Image registration approach based on improved SIFT[J].Journal of Beijing University of Aeronautics and Astronautics，2010，36 （9）:1121-1124.

[6]王曉華，傅衛(wèi)平，梁元月.提高SIFT特征匹配效率的方法研究[J].機械科學(xué)與技術(shù)，2009，28（9）:1252-1254.WANG Xiao-hua，F(xiàn)U Wei-ping，LIANG Yuan-yue.A Method for Improving SIFT Feature Matching Efficiency[J].Mechanical Science and Technology for Aerospace Engineering，2009，28（9）:1252-1254.