基于LDA的SIFT算法在圖像配準中的應用

丁湘楠，謝正忠，宋曉寧

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003）

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

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

1 SIFT算法特征原理

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

1）尺度空間極值檢測

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

其中：

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

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

2）確定關鍵點位置及其所在尺度

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

3）確定關鍵點方向參數

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

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

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

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

4）生成SIFT特征向量

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

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

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

5）關鍵點相似性判定

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

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

2 LDA-based SIFT方法

2.1 線性鑒別分析法

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

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

樣本類內離散度矩陣定義為：

其中，

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

其中，Wopt是下式的解：

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

2.2 LDA-based SIFT算法步驟

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

1）對待匹配圖像進行預處理；

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

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

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

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

3 實驗結果及分析

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

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

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

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

4 結 論

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

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

表1 SIFT算法與本文算法匹配特征向量維數及匹配時間比較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]宋蓓蓓.圖像的多尺度多方向變換及其應用研究 [D].西安:西安電子科技大學，2008.

[5]李杰.圖像的方向多尺度分析及其應用研究 [D].成都:電子科技大學，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]宋楓溪，高秀梅，劉樹海.統計模式識別中的維數削減與低損降維[J].計算機學報，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].計算機科學，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]陳莉.文檔挖掘與降維技術[J].西北大學學報，2003，33（3）:267-271.CHEN Li.Text mining and technology of dimensionality reduction[J].Journal of Northwest University，2003，33（3）:267-271.