改進的SIFT圖像匹配算法

李 煬,翟社平

(西安郵電大學 計算機學院，陜西 西安 710061)

改進的SIFT圖像匹配算法

李 煬,翟社平

(西安郵電大學 計算機學院，陜西 西安 710061)

在眾多圖像匹配算法中，SIFT算法是在總結了眾多傳統算法優勢的基礎上，將尺度空間理論融合到圖像特征點提取過程中，這樣SIFT算法就保持了圖像的尺度和旋轉不變性，另外在外部光照變化等因素的影響下也能對圖像的特征點進行準確的匹配，但該算法在仿射變換方面還存在很大的不足。針對不足之處，采用SIFT算法的方法提取圖像的特征點，然后通過使用ASIFT中的方法對提取到的特征點進行仿射變換以及為特征點分配方向，這樣在增強了圖像的抗仿射性的基礎上也保持了圖像的旋轉不變性。實驗結果表明，改進算法在保持了原SIFT算法各種優勢的基礎上，在增強圖像的抗仿射性方面，可以取得良好的效果。

SIFT；ASIFT；抗仿射性；圖像匹配；特征點

0 引 言

隨著計算機技術的發展，人工智能、機器視覺等人機交互技術也成為科研工作者重點研究的方向。研究人機交互技術時有一項關鍵技術就是圖像匹配。

1999年哥倫比亞大學的David G.Lowe教授[1]總結了現有的基于不變量技術的特征檢測方法，并正式提出了一種基于尺度空間,對圖像旋轉、縮放以及仿射變換保持不變性的局部圖像特征描述算法—SIFT(尺度不變特征變換)，并且該算法在2004年被Lowe教授完善。

SIFT算法雖然對圖像的旋轉、縮放以及仿射變換保持不變性，但是在圖像發生較大的仿射變換時該算法的匹配效果將會大大下降，并且由于它生成的描述子為128維，這給后續的圖像匹配增加了負擔和計算復雜度。于是Ye等提出的PCA-SIFT[2]算法就是在SIFT算法的基礎上對其進行降維，減少了匹配過程的計算量，但是這使得匹配率有所下降。無論是SIFT還是PCA-SIFT都得將圖像轉換成灰度圖像才能進行處理，CSIFT[3]算法是針對彩色圖像進行不變特征的提取。SURF[4]算法可以說是SIFT算法的加強版，其計算量小，運算速度快，而且提取的特征點數量幾乎與SIFT相同，但同樣它也繼承了SIFT的一個陋習，就是在圖像發生較大的仿射變換時，圖像的匹配效果將大打折扣。由于SIFT和SURF不具有完全仿射不變性，因此J.M.Morel等提出了ASIFT[5]算法，該算法可以抵抗強仿射變換，增加了提取的特征點數量，但是唯一的缺點是計算量過大，不能滿足實時性要求。

基于SIFT算法與ASIFT算法的優勢，文中提出將ASIFT算法中抗仿射性的方法與SIFT算法相結合，既解決了ASIFT算法計算量大的問題，又解決了SIFT算法抗仿射性差的問題。

1 SIFT算法

SIFT算法是Lowe教授在1999年對之前的圖像匹配算法總結的基礎上提出的，并在2004年進行了完善。SIFT(Scale Invariant Feature Transform，尺度不變特征變換)是基于局部特征描述的算子，就是對圖像中的局部區域進行不變量的提取。該算法是在尺度空間[6]對關鍵點進行提取，然后將提取到的關鍵點進行方向描述，這樣就可以保持尺度和旋轉不變性，最后生成一個特征點描述子。

SIFT算法對圖像中的關鍵點進行提取時，是對圖像中一些不變性比較好的點進行提取。不變性好的點就是一些十分突出的點，不會由于噪聲和光照等外界因素的變化而變化，比如在一片黑色區域中的亮點、角點、邊緣點等。SIFT算法的實現主要包括四個步驟：

(1)尺度空間極值點提取；

(2)關鍵點精確定位；

(3)關鍵點方向分配；

(4)生成關鍵點描述子。

通過這四個步驟提取整幅圖像中的特征點，之后做圖像匹配時，只需比較兩幅圖像中的特征點的相似度就可以判斷這兩幅圖像的相似程度了。

雖說SIFT算法在圖像匹配時具有很大的優勢，但當一幅圖像發生較大的仿射變換時，SIFT算法的匹配效果將會大大下降。

2 SIFT算法的改進

文中算法在SIFT算法的基礎上進行改進，主要是對SIFT算法的抗仿射能力進行了改善。主要包括以下幾個步驟：

(1)尺度空間極值點提取；

(2)關鍵點精確定位；

(3)對關鍵點進行仿射模擬；

(4)為關鍵點分配方向；

(5)生成特征點描述子。

2.1 尺度空間極值點提取

SIFT算法首先通過對圖像做高斯模糊和降采樣來構建高斯金字塔，這樣一幅圖像就可以產生幾組圖像，在每一組圖像中又可以分成幾層(一般為3～5層)。然后對每組圖像進行高斯差分處理，在處理后的圖像中提取極值點。

高斯核是實現尺度變換的唯一線性變換核[7]，因此尺度函數空間L(x,y,σ)是由圖像函數I(x,y)與高斯函數卷積得到。

L(x,y,σ)=I(x,y)*G(x,y,σ)

(1)

(2)

通過改變σ的值將得到一些列的高斯模糊后的圖像，這些圖像便構成了尺度空間。然后對尺度空間里面的每組圖片進行分層，并將每組圖片的最高一層進行高斯模糊。接下來對相鄰兩層做差及高斯差分處理，這一處理通過高斯差分函數D(x,y,σ)實現。

D(x,y,σ)=L(x,y,kσ)-L(x,y,σ)

(3)

得到高斯差分尺度空間后，在高斯差分尺度空間中將每個像素點與它同尺度的8個像素以及上下相鄰尺度的18個像素點作比較，最后找到局部區域的極值點。

2.2 關鍵點精確定位

由于高斯差分函數對噪聲比較敏感，會對提取到的極值點的準確性產生一定影響，因此還需要對提取到的極值點繼續進行檢測。為了提高關鍵點的穩定性，需要對提取到的極值點進行曲線擬合。利用高斯差分函數在尺度空間的泰勒展開式為：

(4)

得到的極值點為：

(5)

將極值點帶入式(4)中得到極值為：

(6)

Lowe教授指出，重復以上步驟5次得到的效果較好，然后去除那些效果不好的極值點。將式(6)中絕對值小于等于0.02的極值點去除。

以上僅僅去除了對比度較低的極值點，高斯差分函數還具有很強的邊緣響應。也就是高斯差分函數的峰值點在橫跨邊緣的方向有較大的主曲率[8]，垂直邊緣有較小的主曲率。而主曲率可以通過計算該點的二階Hessian得到：

(7)

其中，Dxx表示高斯差分金字塔中某尺度在x方向求二階導。這里D的主曲率與H的特征值成正比，為了避免計算特征值而只考慮它們之間的比例關系。令α為最大特征值，β為最小特征值，則它們之間的關系設為α=rβ。

Tr(H)=Dxx+Dyy=α+β

(8)

Det(H)=DxxDyy-(Dxy)2

(9)

因此D的主曲率與H的特征值的比例關系如下：

(10)

Lowe教授在他的論文中指出，當這一比例關系不在某閾值范圍內時則將該點刪除。

2.3 對關鍵點進行仿射模擬

ASIFT算法加入經度和緯度是為了構建仿射空間，然后在仿射空間中對待匹配的圖像進行仿射模擬，進而對模擬的圖像進行匹配，這樣就保證了圖像的仿射不變性。這樣做是將整幅圖片中的所有像素點都進行仿射空間的構建，將會增加計算量，進而導致算法運行速度下降。而文中算法是僅僅對圖片中的特征點進行仿射變換，相較于整幅圖片來說，特征點的數量僅僅占很小的一部分，因此計算量將會下降。

其行列式為正，且不存在相似矩陣，則其存在唯一的分解[9]：

(11)

仿射空間的構建方法如下：

(12)

其中，I'為特征點的集合。

2.4 關鍵點分配方向

為了保證提取到的特征點的旋轉不變性，還需要為關鍵點指定方向參數，這樣就可以保證在圖片發生旋轉后仍然能夠提取關鍵點并與原圖像中的點匹配。為關鍵點賦予方向采用求每個點梯度值的方法。

像素的梯度表示如下：

(13)

梯度幅值為：

m(x,y)=(L(x+1,y)-L(x-1,y))2+(L(x,y+1)-L(x,y-1))1/2

(14)

梯度方向為：

(15)

確定關鍵點的方向采用梯度直方圖的統計法，如圖1所示，統計以關鍵點為中心一定區域內的圖像像素點對關鍵點方向所做的貢獻。

圖1 梯度直方圖

直方圖以每10°方向為一個柱，共36個柱，柱所代表的方向為像素點的方向，柱的長度代表了梯度幅值[10]。Lowe教授建議直方圖半徑采用3*1.5*σ。直方圖進行統計時，每相鄰三個點要采用高斯加權，模板采用[0.25,0.5,0.25]，并連續加權兩次，這樣就可以為特征點指定方向。

2.5 特征點描述

以關鍵點為中心取16×16的窗口，在每4×4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，這樣一個關鍵點由4×4共16個種子點組成，每個種子點有8個方向向量信息，形成128維的SIFT特征向量[11]。

如圖2所示，左圖的種子點由8×8單元組成，每一個小格都代表了特征點鄰域所在的尺度空間的一個像素，箭頭方向代表了像素梯度方向，箭頭長度代表該像素的幅值。然后在4×4的窗口內計算8個方向的梯度方向直方圖。繪制每個梯度方向的累加可形成一個種子點，右圖為一個特征點由4個種子點的信息組成。

圖2 描述子生成示意圖

對生成的128維向量描述子與帶匹配的圖像的描述子進行歐氏距離[12]計算，就可以得到兩張圖像的相似度。

2.6 算法描述

以下用偽代碼對文中算法進行描述：

I=read(image)

//得到圖像的信息,x:長，y:寬

f(x,y)=getInformat(I)

//得到髙斯金字塔的層數

m=min(x,y)

//高斯金字塔中每一層的組數，一般為3～5

M=3

//構建高斯金字塔

GaussianIM(image)

{

for i=0 to m

{//對圖像做高斯模糊處理

A(i)=Gaussian(I)

for j=0 to M+3

{//對每一層的圖像做高斯處理，得到6組圖像

B(j)=Gaussian(A(i)) j=j+1

}

//對圖像做降采樣處理

DownSample(A(image))

i=i+1

}

}

//求高斯金字塔中的極值像素點

extreme(image)

{//對高斯金字塔做高斯差分處理

DOGIM(GaussianIM(image))

//每一組圖像在尺度空間中的極值點

getextreme(DOGIM)}

exactpoint()

{

//消除極值點中的邊緣相應

I1(x,y)=Dealedge(extreme(image))

//使用泰勒公式對離散的極值點做進一步處理

I2(x,y)=Taylor(I1)

//對求得的極值點進行仿射空間的模擬

AffineDeal(exactpoint)

//為每個極值點分配方向，使其具有方向性

distribute(I2)

}

//對仿射空間得到的極值點生成128位的描述子

Descriptor(AffineDeal)

end

3 實驗結果與分析

為了驗證改進后的算法的正確性，文中分別做了以下兩組實驗分析及對比。

3.1 匹配率對比

由圖3可見，文中算法提升了特征點的匹配率，而且有效降低了ASIFT算法中出現的重復匹配特征點的現象。

圖3 實驗結果

3.2 匹配時間對比

通過表1可以發現，文中算法相對于ASIFT算法降低了算法運行的時間，并且相對于SIFT算法提升了特征點的匹配率。

表1 圖像實驗對比結果

文中算法是在SIFT算法提取特征點的基礎上，通過使用ASIFT算法的構造仿射空間的方法，對特征點進行仿射變換，這樣將會增強特征點的抗仿射性，同時也降低了計算量。因為文中算法只是針對特征點進行仿射空間的構造，并不是針對圖像信息中所有的像素點，相對于整個圖像的像素點數量來說，特征點的數量還是比較少，那么計算量將會下降90%以上，同時算法的執行時間也提升了80%以上。實驗中，文中算法相對于SIFT算法匹配率提升了11.89%，較ASIFT算法提升了76.86%，并且算法執行速率提升了5.07 s。

文中算法保持了SIFT算法中特征點的尺度、旋轉不變性，以及在光照等外部因素影響的條件下，增強了特征點的抗仿射能力，進而增加了圖像的匹配率。缺點是在特征點的提取方面保持了與SIFT算法的一致，沒有像ASIFT算法那樣的特征點提取量。在一些對實時性要求較高的場景，改進算法的效果相對于ASIFT算法將會十分明顯。

4 結束語

文中在對SIFT算法和ASIFT算法進行深入研究的基礎上，對SIFT算法的抗仿射性能力進行了改進。由于ASIFT是在提取圖像特征點之前對圖像中的所有像素點構建仿射空間[13-14]，也就是進行仿射變換的模擬，這樣雖然使得圖像特征點的數量得到了提升，但是圖像特征點的匹配率卻沒有提升或提升的效果不明顯。通過對SIFT算法特征點提取完成后，對提取到的特征點進行仿射空間的構建，這樣就能提升特征點的抗仿射能力，進而提升了特征點的匹配率，同時也降低了在進行仿射空間構建時的計算量，節約了匹配時間，提升了匹配速率。該算法的缺點在于特征點的數量沒有ASIFT算法那么多，僅僅是繼承了SIFT算法的特征點數量，所以還值得深入研究。

[1] Lowe D G.Distinctive image features from scale-invariant key-point[J].International Journal of Computer Vision,2004,60(2):91-110.

[2] Ye K,Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors[C]//Proceedings of the conference on computer vision and pattern recognition.[s.l.]:IEEE,2004:90-98.

[3] Abdel-Hakim A E,Farag A A.CSIFT:ASIFT descriptor with color invariant characteristics[C]//IEEE computer society conference on computer vision and pattern recognition.[s.l.]:IEEE,2006:1978-1983.

[4] Bay H,Ess A,Tuytelars T,et al.Speeded-Up Robust Features(SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-359.

[5] Morel J M,Yu Guoshen.ASIFT:a new framework for fully affine invariant image comparison[J].SIAM Journal on Imaging Sciences,2009,2(2):438-469.

[6] Lindeberg T. Scale-space theory:a basic tool for analysing structures at different scales[J].Journal of Applied Statistics,1994,21(2):223-261.

[7] Lindeberg T.Scale-space theory in computer vision[M].[s.l.]:Springer Science & Business Media,1994.

[8] Babaud J,Witkin A P,Baudin M,et al.Uniqueness of the Gaussian kernel for scale-space filtering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1986,8(1):26-33.

[9] 盧 彬.改進的ASIFT算法在圖像配準中的應用[J].電視技術,2014,38(11):211-214.

[10] 周 穎.基于SIFT算法的圖像特征匹配[J].現代計算機,2015(2):63-68.

[11] 朱 進,丁亞洲,肖雄武，等.基于SIFT改進算法的大幅面無人機影像特征匹配方法[J].計算機應用研究,2015,32(10):3156-3159.

[12] 張忠林,曹志宇,李元韜.基于加權歐式距離的k_means算法研究[J].鄭州大學學報：工學版,2010,31(1):89-92.

[13] 何婷婷,芮建武,溫 臘.CPU-GPU協同算加速ASIFT算法[J].計算機科學,2014,41(5):14-19.

[14] 宋耀鑫,張丹丹,唐伶俐,等.基于ASIFT算法的低重疊度無人機影像拼接方法[J].遙感技術與應用,2015,30(4):725-730.

Improved SIFT Image Matching Algorithm

LI Yang,ZHAI She-ping

(School of Computer Science,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

In many image matching algorithm,SIFT algorithm puts the scale space theory fusion into image feature point extraction process based on the summary of the advantages of many traditional algorithms,so that it keeps the scale and rotation invariance for image and in the external light illumination changes and other factors influence,can also match the image feature points accurately.But it still exists great shortage in terms of affine transformation.Aiming at them,the SIFT method is used to extract image feature points and ASIFT method is applied to carry out affine transformation for extracted feature points and to distribute direction,enhancing image anti affine and maintaining the image rotation invariance.The experimental results show that the improved algorithm can achieve good results in enhancing the anti radiation of the image based on the advantages of the original SIFT algorithm.

SIFT;ASIFT;anti affine;image matching;feature points

2016-01-25

2016-05-11

時間：2016-10-24

陜西省自然基金面上項目(2012JM8044)；陜西省教育廳項目(12JK0733)；西安郵電大學創新基金項目(114-602080059)

李 煬(1990-)，男，碩士，研究方向為嵌入式系統設計；翟社平，副教授，博士，研究方向為嵌入式系統、語義Web。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1114.052.html

TP391.41

A

1673-629X(2016)11-0058-05

10.3969/j.issn.1673-629X.2016.11.013