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

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

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

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

傳統的圖像匹配算法計算量較大，在圖像目標發生旋轉、縮放、光照等參數發生變化時適應力不強。近年來，在計算機視覺領域中，基于局部不變量描述符的算法在圖像匹配方面取得了令人矚目的進展。

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

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

1 SIFT算法簡介

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

1.1 檢測尺度空間極值點

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

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

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

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

1.2 精確定位極值點

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

1.3 極值點方向分配

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

像素點的梯度表示為：

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

1.4 生成SIFT特征向量

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

2 對特征匹配算法的改進

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

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

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

而街區距離是二維圖像中相應情形的推廣距離，即

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

3 仿真實驗及結果分析

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

表1 圖像匹配比較數據Tab.1 Comparative data of image matching

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

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

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

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

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

4 結束語

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

[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]劉立，彭復員，趙坤.采用簡化SIFT算法實現快速圖像匹配[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的圖像配準算法[J].北京航空航天大學學報，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]王曉華，傅衛平，梁元月.提高SIFT特征匹配效率的方法研究[J].機械科學與技術，2009，28（9）:1252-1254.WANG Xiao-hua，FU 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.