丁湘楠，謝正忠，宋曉寧

（江蘇科技大學(xué) 計算機科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003）

SIFT（Scale-invariant Feature Transform）是一種基于特征的配準方法[1]。SIFT特征匹配算法是由David G.Lowe于2004年在總結(jié)了現(xiàn)有的基于不變量技術(shù)的特征檢測方法的基礎(chǔ)上提出的。SIFT算法能提取穩(wěn)定的特征，也可以處理兩幅圖像之間發(fā)生旋轉(zhuǎn)、平移、視角變換、仿射變換、光照變換等情況下的匹配問題，甚至在某種程度上對任意角度拍攝的圖像也具備較為穩(wěn)定的特征匹配能力，從而能夠?qū)崿F(xiàn)兩幅差異較大的圖像之間的特征的匹配。因此這種算法很適合應(yīng)用于圖像配準。此方法具有精確度高、匹配能力強的特點。雖然此算法具有許多優(yōu)點，但是算法本身復(fù)雜度高，匹配時間久，尤其對于數(shù)據(jù)量較大的遙感影像的處理，應(yīng)用SIFT算法時處理速度會明顯降低，過于耗時。因此，將SIFT算法直接應(yīng)用于遙感影像的處理并不實用，在實際生活中也未能使用這種算法處理遙感影像[2]。但是SIFT算法具有其他圖像配準算法難以媲美的優(yōu)點，有著非常好的應(yīng)用前景。

為此，我們通過大量研究提出了一種基于SIFT算法的改進方案。即在SIFT算法的特征提取中加入線性鑒別分析方法（Linear Discriminant Analysis，LDA），以減少 SIFT 特征提取的維度。此方案既能保持SIFT算法本身的精確度高、匹配能力強的特點，又能提高匹配的效率，實時性強。非常適合將其應(yīng)用于維數(shù)高的圖像配準，例如自然圖像配準、單幅人臉圖像比對等領(lǐng)域。此改進算法具有廣泛的應(yīng)用前景。

1 SIFT算法特征原理

SIFT特征匹配算法主要包括2個部分[3]：首先是生成SIFT算法中所需的特征描述子，即從待匹配圖像中提取出特征向量；其次是匹配SIFT算法的特征向量。

1）尺度空間極值檢測

一幅圖像 I（x，y）的尺度空間定義為 L（x，y，σs），如圖 1所示，是由不同尺度的高斯函數(shù) G（x，y，σ）與原圖像卷積運算生成的[4]。相鄰尺度的圖像相減就得到一組DOG（Difference of Gaussian）圖像 G（x，y，σ），設(shè) σ 是尺度空間因子，（x，y）是圖像 I（x，y）的空間坐標，公式如下：

其中：

檢測尺度空間極值時，所檢測像素需要跟同尺度的8個像素和上下相鄰尺度的9×2個像素，共26個像素進行比較，確保二維圖像空間和尺度空間都檢測到局部極值。

圖1 DOG尺度空間極值檢測示意圖Fig.1 Extrema detection in scale space

2）確定關(guān)鍵點位置及其所在尺度

把尺度空間圖像當(dāng)做一個曲面，按照特征點周圍的像素點的梯度分布情況，通過擬合三維二次函數(shù)確定關(guān)鍵點的尺度和位置，同時去除低對比度的關(guān)鍵點和不穩(wěn)定的邊緣響應(yīng)點，以增強匹配的穩(wěn)定性[5]。

3）確定關(guān)鍵點方向參數(shù)

利用關(guān)鍵點鄰域像素的梯度方向的分布特性為每個關(guān)鍵點指定方向參數(shù)，使得算子具有旋轉(zhuǎn)不變性的特點。通過公式（3）和（4）可計算出像素梯度的模 m（x，y）和方向 θ（x，y）：

在實際運用和計算中，我們在以關(guān)鍵點為中心的鄰域窗口采取樣本，同時利用直方圖統(tǒng)計鄰域像素的梯度方向。其中，梯度直方圖的范圍是0～360度，以每10度為一個柱，共計36個柱。關(guān)鍵點的方向的選取是通過直方圖的峰值，即該關(guān)鍵點處鄰域梯度的主方向。圖2所示是采用7個柱時利用梯度直方圖為關(guān)鍵點確定主方向，箭頭所指直方圖的峰值即為關(guān)鍵點的方向。

圖2 由梯度方向直方圖確定主梯度方向示意圖Fig.2 Determine the direction of keypoint

在梯度方向直方圖中，當(dāng)有另外一個能量相當(dāng)于主峰值能量的80%的峰值存在時，則可以認為該關(guān)鍵點的輔方向即為該方向。一個關(guān)鍵點可能在同時會被指定具有多個方向（一個主方向，及多個輔方向），這樣可以增強圖像匹配的魯棒性。此時，圖像關(guān)鍵點特征檢測已全部完成，每個關(guān)鍵點有3個特征：方向、位置及其尺度。通過以上步驟就可確定一個SIFT向量的特征區(qū)域[6]。

4）生成SIFT特征向量

特征描述符是通過統(tǒng)計特征點鄰域的梯度信息得到的。如圖3（a）所示，圓的中心點是一個關(guān)鍵點，最小格代表關(guān)鍵點鄰域所在的尺度空間的一個像素，長度代表梯度的模值，箭頭的方向代表梯度的方向。每個種子點由在4×4的區(qū)域上計算8個方向的梯度直方圖，然后再繪制其累加值，即可得到。對于圖3（b），圖中標出的紅色的關(guān)鍵點由4個種子點組成，每個種子點都有8個方向的向量信息。由此，一個關(guān)鍵點可產(chǎn)生32個數(shù)據(jù)，形成一個32維的特征向量。

實際計算中，為了增強匹配的穩(wěn)健性，Lowe建議對每個關(guān)鍵點采用4×4共16個種子點進行描述，這樣每個關(guān)鍵點就可以產(chǎn)生128個數(shù)據(jù)，即形成128維的SIFT特征向量（見圖3）。此時SIFT特征向量已經(jīng)去除了旋轉(zhuǎn)、尺度變化等幾何形變因素的影響，再繼續(xù)將特征向量的長度進行歸一化，就可以去除光照變化的影響。

圖3 由關(guān)鍵點鄰域梯度信息生成特征向量Fig.3 Features vector based on key-points grads information

5）關(guān)鍵點相似性判定

當(dāng)通過以上步驟生成兩幅圖的SIFT特征描述子以后，可使用關(guān)鍵點特征描述符的歐式距離作為兩幅圖像中關(guān)鍵點的相似性判定度量。取一幅圖像中的某個關(guān)鍵點，找出另一幅圖像中歐式距離最近的兩個關(guān)鍵點，在這兩個關(guān)鍵點中，若最近距離除以次近距離少于某個比例閾值，則可以接受該匹配點。若要使匹配結(jié)果更加穩(wěn)定，可以降低閾值，但同時會減少SIFT的特征點數(shù)。

通過對SIFT算法的描述能夠看出，此算法雖然匹配能力較強，但是參數(shù)較多，耗時久，計算復(fù)雜度高。將其應(yīng)用于數(shù)據(jù)量大的影像時效率會偏低，需要對此算法進行改進。

2 LDA-based SIFT方法

2.1 線性鑒別分析法

線性鑒別方法（LDA）屬于監(jiān)督的模式分類方法，LDA從數(shù)據(jù)分類的角度考慮問題。在信息繁多的高維特征空間中，LDA能夠從中提取出最具有鑒別能力的低維特征，通過這些提取出來的低維特征[9]，可以幫助我們聚集同一類別的所有樣本，并且最大程度的將不同類別進行分開處理，同時它選擇使樣本類間離散度和樣本類內(nèi)離散度的比值最大的特征[8]。樣本類間離散度矩陣定義為：

其中，ui是Ci類的均值，u是所有樣本的均值，pi是先驗概率。

樣本類內(nèi)離散度矩陣定義為：

其中，

希望通過投影后，使得最大程度上的不同類別的樣本在低維空間能夠盡量分開，同時希望我們得到的每個類別內(nèi)部樣本信息盡量密集[10]，也就是說，樣本類內(nèi)離散度越小越好，樣本類間離散度越大越好。因此，如果Sw是非奇異矩陣，最優(yōu)的投影方向Wopt就是使得樣本類間離散度矩陣和樣本類內(nèi)離散度矩陣的行列式比值最大的那些正交特征向量。因此Fisher準則函數(shù)定義為：

其中，Wopt是下式的解：

也就是對應(yīng)于矩陣S-1wSb較大的特征λi值的特征向量。

2.2 LDA-based SIFT算法步驟

本節(jié)提出的LDA-based SIFT方法的主要思想是：在利用SIFT算法提取出圖像中的特征向量后，利用LDA算法從中提取出最具有鑒別能力的特征向量，即用較少維數(shù)的特征向量盡量完整的描述圖像，在匹配時既可以保證準確性，又大大縮短了匹配時間。利用SIFT-LDA算法進行圖像配準的主要步驟如下：

1）對待匹配圖像進行預(yù)處理；

2）通過SIFT算法提取出待匹配圖像的特征點的特征向量；

3）通過LDA方法從SIFT提取的特征向量中進一步提取出最具有鑒別能力的特征向量；

4）進行特征向量的匹配。

以上就是LDA-based SIFT算法進行圖像匹配的一般步驟。實現(xiàn)了在不顯著降低SIFT的魯棒性和獨特性的前提下，盡量降低其特征點的維數(shù)。既能保證匹配的準確度，又縮短了匹配的時間。

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

我們將本文提出的改進方案用于兩個實驗，一是配準自然圖像，如圖4所示。

圖4 自然圖像匹配Fig.4 Registration of natural image

其中（a）圖是參考圖像，（b）圖是待配準圖像，將兩幅圖像分別用SIFT算法處理后取得的有效關(guān)鍵點分別如圖（c）和圖（d）所示，再對圖像進行LDA降維處理后得到的自然圖像的配準效果如圖（e）所示。另一個實驗是用于人臉圖像的對比，如圖 5所示。其中（a）圖是參考圖像，（b）圖是待配準圖像，將兩幅圖像運用本文提出的方法，即對SIFT算法加入LDA降維后的匹配效果如圖5（c）所示。

傳統(tǒng)的SIFT算法與本論文提出的算法對于提取的特征向量維數(shù)比較如表1所示，其中N為特征點個數(shù)。通過這兩組圖像以及表1可以看出，本文提出的把傳統(tǒng)的SIFT算法與LDA降維方法相結(jié)合的方案在保證SIFT算法本身的高匹配性的前提下，又能有效的提高匹配速度，提高效率，實時性強。

4 結(jié) 論

SIFT算法本身精確度高、匹配能力強，但由于算法自身較復(fù)雜，在匹配過程中過于耗時、實時性差，很大程度的限制了它的實際應(yīng)用。我們通過大量研究提出了這種基于SIFT算法的改進方案，在保證了它的高匹配能力的前提下，同時大大縮短了算法的匹配時間，提高了匹配效率，增強了實時性。使得改進后的SIFT算法更有利于解決實際問題，有著更廣泛的應(yīng)用前景。

圖5 人臉圖像比對Fig.5 Registration of face image

表1 SIFT算法與本文算法匹配特征向量維數(shù)及匹配時間比較Tab.1 Comparison of the two methods

[1]YU L，ZHANG D R，Holden E J.A fast and fully automatic registration approach based on point features for multi-source remote sensing images[J].Journal of Digital Imaging，2010，23（3）:287-300.

[2]Xu Y P，Hu K N，Tian Y.Classification of hyperspectral imagery using SIFT for spectral matching[J].Congress on Image and Signal Processing，2008，2（10）:704-708.

[3]MA Chao-jie，GUAN Ping.Image automatic mosaic method based on phase and SIFT feather correlation[J].Laser&Infrared，2011，41（4）:470-473.

[4]宋蓓蓓.圖像的多尺度多方向變換及其應(yīng)用研究 [D].西安:西安電子科技大學(xué)，2008.

[5]李杰.圖像的方向多尺度分析及其應(yīng)用研究 [D].成都:電子科技大學(xué)，2007.

[6]DENG Rong-feng，LI Xi-ying.Robust image mosaic algorithm based on SIFT feature matching[J].Journal of Computer Applications，2009，29（3）:219-221.

[7]宋楓溪，高秀梅，劉樹海.統(tǒng)計模式識別中的維數(shù)削減與低損降維[J].計算機學(xué)報，2005（11）:1915-1922.SONG Feng-xi，GAO Xiu-mei，LIU Shu-hai.Dimensionality reduction in statistical pattern recognition and low loss dimensionality reduction[J].Chinese Journal of Computers，2005（11）:1915-1922.

[8]Zhao Z X，Yu S Q，Wu X Y.A multi-target tracking algorithm using texture forreal-time surveillance[C]//Proceedingsofthe IEEE InternationalConference on Robotics and Biomimetics， Bangkok， Thailand:IEEE，2009:2150-2155.

[9]吳柯，牛瑞卿，王毅.基于PCA與EM算法的多光譜遙感影像變化檢測研究[J].計算機科學(xué)，2010，37（3）:282-284.WU Ke，NIU Rui-qing，WANG Yi.Change detection of multi-spectral remote sensed images based on PCA and EM algorithm[J].Computer Science，2010，37（3）:282-284.

[10]陳莉.文檔挖掘與降維技術(shù)[J].西北大學(xué)學(xué)報，2003，33（3）:267-271.CHEN Li.Text mining and technology of dimensionality reduction[J].Journal of Northwest University，2003，33（3）:267-271.