基于LDA的SIFT算法在圖像配準(zhǔn)中的應(yīng)用

丁湘楠，謝正忠，宋曉寧

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

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

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

1 SIFT算法特征原理

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

1）尺度空間極值檢測(cè)

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

其中：

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

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

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

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

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

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

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

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

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

4）生成SIFT特征向量

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

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

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

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

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

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

2 LDA-based SIFT方法

2.1 線性鑒別分析法

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

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

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

其中，

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

其中，Wopt是下式的解：

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

2.2 LDA-based SIFT算法步驟

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

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

2）通過(guò)SIFT算法提取出待匹配圖像的特征點(diǎn)的特征向量；

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

4）進(jìn)行特征向量的匹配。

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

3 實(shí)驗(yàn)結(jié)果及分析

我們將本文提出的改進(jìn)方案用于兩個(gè)實(shí)驗(yàn)，一是配準(zhǔn)自然圖像，如圖4所示。

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

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

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

4 結(jié) 論

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

圖5 人臉圖像比對(duì)Fig.5 Registration of face image

表1 SIFT算法與本文算法匹配特征向量維數(shù)及匹配時(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)計(jì)模式識(shí)別中的維數(shù)削減與低損降維[J].計(jì)算機(jī)學(xué)報(bào)，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算法的多光譜遙感影像變化檢測(cè)研究[J].計(jì)算機(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é)報(bào)，2003，33（3）:267-271.CHEN Li.Text mining and technology of dimensionality reduction[J].Journal of Northwest University，2003，33（3）:267-271.