李 煬,翟社平

(西安郵電大學(xué) 計算機(jī)學(xué)院，陜西 西安 710061)

改進(jìn)的SIFT圖像匹配算法

李 煬,翟社平

(西安郵電大學(xué) 計算機(jī)學(xué)院，陜西 西安 710061)

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

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

0 引 言

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

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

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

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

1 SIFT算法

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

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

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

(2)關(guān)鍵點精確定位；

(3)關(guān)鍵點方向分配；

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

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

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

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

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

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

(2)關(guān)鍵點精確定位；

(3)對關(guān)鍵點進(jìn)行仿射模擬；

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

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

2.1 尺度空間極值點提取

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

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

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

(1)

(2)

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

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

(3)

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

2.2 關(guān)鍵點精確定位

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

(4)

得到的極值點為：

(5)

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

(6)

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

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

(7)

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

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

(8)

Det(H)=DxxDyy-(Dxy)2

(9)

因此D的主曲率與H的特征值的比例關(guān)系如下：

(10)

Lowe教授在他的論文中指出，當(dāng)這一比例關(guān)系不在某閾值范圍內(nèi)時則將該點刪除。

2.3 對關(guān)鍵點進(jìn)行仿射模擬

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

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

(11)

仿射空間的構(gòu)建方法如下：

(12)

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

2.4 關(guān)鍵點分配方向

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

像素的梯度表示如下：

(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)

確定關(guān)鍵點的方向采用梯度直方圖的統(tǒng)計法，如圖1所示，統(tǒng)計以關(guān)鍵點為中心一定區(qū)域內(nèi)的圖像像素點對關(guān)鍵點方向所做的貢獻(xiàn)。

圖1 梯度直方圖

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

2.5 特征點描述

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

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

圖2 描述子生成示意圖

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

2.6 算法描述

以下用偽代碼對文中算法進(jìn)行描述：

I=read(image)

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

f(x,y)=getInformat(I)

//得到髙斯金字塔的層數(shù)

m=min(x,y)

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

M=3

//構(gòu)建高斯金字塔

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()

{

//消除極值點中的邊緣相應(yīng)

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

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

I2(x,y)=Taylor(I1)

//對求得的極值點進(jìn)行仿射空間的模擬

AffineDeal(exactpoint)

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

distribute(I2)

}

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

Descriptor(AffineDeal)

end

3 實驗結(jié)果與分析

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

3.1 匹配率對比

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

圖3 實驗結(jié)果

3.2 匹配時間對比

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

表1 圖像實驗對比結(jié)果

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

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

4 結(jié)束語

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

[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] 盧 彬.改進(jìn)的ASIFT算法在圖像配準(zhǔn)中的應(yīng)用[J].電視技術(shù),2014,38(11):211-214.

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

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

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

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

[14] 宋耀鑫,張丹丹,唐伶俐,等.基于ASIFT算法的低重疊度無人機(jī)影像拼接方法[J].遙感技術(shù)與應(yīng)用,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)；西安郵電大學(xué)創(chuàng)新基金項目(114-602080059)

李 煬(1990-)，男，碩士，研究方向為嵌入式系統(tǒng)設(shè)計；翟社平，副教授，博士，研究方向為嵌入式系統(tǒng)、語義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