主成分分析法(PCA)在SIFT匹配算法中的應(yīng)用

馬 莉，韓 燮

(中北大學(xué)電子與計算機(jī)科學(xué)技術(shù)學(xué)院，山西 太原 030051)

David G.Lowe于2004年提出了基于尺度不變特征變換(SIFT)的特征提取算法。此算法的基本特性是穩(wěn)定，它對于不同場景、不同光照、不同幾何形狀變換都具有較強(qiáng)的穩(wěn)定性，提高了匹配的精確度[1]。但算法仍然存在一些不足，比如特征描述符的維數(shù)過大以及耗時過長。在原始的SIFT特征提取算法中融入一種主要用于對數(shù)據(jù)進(jìn)行降維的主成分分析法(PCA)，就得到一種基于主成分不變特征變換(PCA－SIFT)的特征提取算法[2]，PCA－SIFT算法既繼承了傳統(tǒng)SIFT算法穩(wěn)定性和多量性的優(yōu)點，又利用主成分分析法降低了傳統(tǒng)SIFT特征描述符向量的維數(shù)，提高了匹配效率。

1 生成SIFT特征描述符

SIFT算法要在尺度空間和二維平面空間中同時進(jìn)行極值檢測以找出局部極值點，并且對所提取出的關(guān)鍵點進(jìn)行精確的定位，然后根據(jù)此關(guān)鍵點所處位置周圍鄰域點的梯度方向計算出該關(guān)鍵點的主方向[3]，以實現(xiàn)算子對幾何變換和旋轉(zhuǎn)的不變性。一般生成SIFT特征描述符需要幾個步驟:1)尺度空間的建立;2)計算關(guān)鍵點特征方向，進(jìn)行特征點定位;3)SIFT特征描述符的向量表示。

1.1 尺度空間的建立

Koenderink證明了高斯卷積核是實現(xiàn)尺度變換的唯一線性變換核[4]。二維的高斯函數(shù)定義為

式中:(x，y)是空間坐標(biāo)。那么，一副圖像的二維尺度空間就可以由圖像和高斯核卷積得到

特征點的檢測要在尺度空間和平面空間中同時進(jìn)行，這樣才可以確保得到穩(wěn)健性強(qiáng)的特征點。因此就引入了DoG算子，它是兩個不同尺度高斯核的差分值[5]，DoG算子的構(gòu)成為

接下來就要構(gòu)建一個大小為O組，并且每組中由S層圖像構(gòu)成的圖像金字塔，組與組之間的關(guān)系為:上一組的圖像降采樣得到下一組圖像。在構(gòu)建好圖像金字塔的基礎(chǔ)上，進(jìn)行局部極值檢測，其中每一個像素都需要跟同一平面中的其他8個像素和相鄰尺度空間中該像素所對應(yīng)位置的9×2個像素進(jìn)行計算比較[6]，只有被檢測像素點的高斯核差分值(即DoG值)都大于或都小于與它進(jìn)行比較的26個像素的DoG值時，才能把此點作為一個局部極值點。

1.2 計算關(guān)鍵點的特征方向

為了使所提取的特征點具有縮放和旋轉(zhuǎn)不變性，就要利用每個關(guān)鍵點周圍鄰域的其他點來計算此關(guān)鍵點的特征方向。其中關(guān)鍵點處梯度模值的計算如式(4)所示，關(guān)鍵點主方向的計算如式(5)所示

1.3 SIFT特征描述符的向量表示

如圖1所示，對每一個篩選出的特征點，要以此特征點作為中心點，在這個點的周圍選取一個大小為16×16的區(qū)域，再將這個所選取區(qū)域平均分成4個大小均為4×4的小區(qū)域，并且計算每個小區(qū)域的梯度直方圖，直方圖包含有8個bin方向，這樣就獲得了一個4×4×8=128維的向量，也就是生成了SIFT特征描述符向量，直方圖的峰值就是所選特征點的主方向。

圖1 SIFT特征描述符的向量表示示意圖

2 PCA－SIFT特征描述符的建立

PCA－SIFT描述符與標(biāo)準(zhǔn)SIFT描述符具有相同的亞像素位置(Sub－pixel)、尺度(Scale)和主方向(Dominant Orientations)，但在特征描述符生成時有所不同，PCASIFT用主成分分析法(PCA)將傳統(tǒng)SIFT的128維特征向量進(jìn)行降維，以達(dá)到更精確的表示方式。利用主成分分析法對傳統(tǒng)的128維SIFT特征描述符進(jìn)行降維的具體方法如下:

1)輸入兩幅待匹配圖像中所有關(guān)鍵點(設(shè)為n個)的128維SIFT特征描述符，將輸入的這n個特征描述符作為樣本，寫出樣本矩陣為[x1，x2，...，xn]T，其中 xi表示第 i個特征點的128維特征向量。

3)計算所有樣本點的特征向量與平均特征向量的差，得到差值向量

5)求協(xié)方差矩陣的128個特征值λi和128個特征向量ei。

6)將求出的128個特征值按從小到大的順序進(jìn)行排列λ1≥λ2≥…≥λ128和對應(yīng)的特征向量[e1，e2，…，e128]。

7)選取對應(yīng)t個最大特征值的特征向量作為主成分的方向，在實驗中選取t=20。

8)構(gòu)造一個128×t的矩陣A，它的列由t個特征向量組成。

9)把原始的128維SIFT描述符依據(jù)式(6)投影到所計算出的n維子空間M中，就可以得到PCA－SIFT的描述符 y1，y2，…，yn了，即

因為實驗中選取t=20，所以矩陣A的大小為128×20，xi的大小為1×128，所以xi*A就得到了一個大小為1×20的矩陣，即每一個yi就是一個20維的特征描述符，也就是把原來的128維傳統(tǒng)SIFT特征描述符降成了20維的 PCA－SIFT 特征描述符[6]。

3 基于PCA－SIFT特征提取算法的圖像匹配

3.1 對應(yīng)特征點的匹配

當(dāng)對兩幅待匹配圖像分別使用PCA－SIFT特征提取算法找出各自的特征點并進(jìn)行精確定位，生成對應(yīng)的特征描述向量后，就可以計算特征向量間的歐式距離，兩個特征向量之間的歐式距離值越小，就說明這兩個點越相似，它們的匹配程度就越高。歐式距離的計算如式(7)所示

式中:(x1，x2，……，x128)，(x'1，x'2，……，x'128)分別為待匹配兩幅圖像上的關(guān)鍵點所生成的特征向量。首先找出其中一幅圖像中的某個關(guān)鍵點，采用遍歷的方法在另外一副圖像中找出與這個關(guān)鍵點歐式距離最近和次近的兩個關(guān)鍵點，如果最近的距離與次近的距離的比值小于某個閾值，那么認(rèn)為這一對點就是一對匹配點。在實驗中選取閾值為0.6，如式(8)所示

式中:Dnearest為最近歐式距離，Dhpyo－nearest為次近歐式距離。

3.2 消除錯誤匹配

在實驗中由于環(huán)境因素和遮擋因素，有可能出現(xiàn)錯誤的匹配，為了提高匹配的正確性和穩(wěn)健性，需要采取一些措施來保證匹配的正確率。RANSAC算法是一種依靠對數(shù)據(jù)進(jìn)行擬合的算法，它具有很強(qiáng)的穩(wěn)健性，首先要在分析具體問題的前提下，設(shè)計出某種適合這個問題的目標(biāo)函數(shù)，然后反復(fù)進(jìn)行迭代來估計該數(shù)學(xué)函數(shù)模型中參數(shù)的初始值，繼續(xù)利用求出的初始參數(shù)值把所有的數(shù)據(jù)分為滿足該模型參數(shù)的“內(nèi)點”和不滿足該模型參數(shù)的“外點”，最后反過來用所有滿足該模型參數(shù)的“內(nèi)點”重新對模型參數(shù)進(jìn)行估計，最終得到精確的匹配結(jié)果，消除錯誤匹配[7]。

3.3 變換模型參數(shù)的估計

假定以圖像1(I1)作為參考系，將圖像2(I2)變換到圖像1所在的坐標(biāo)系，變換后的圖像為I'2，則其對應(yīng)關(guān)系為

式中:(x，y)和(x'，y')是一對匹配點，只需4對匹配點即可算出T，得到T后，就可確定這8個參數(shù)。這8個參數(shù)決定了兩幅圖像坐標(biāo)之間的轉(zhuǎn)換關(guān)系，確定其值后就可以得到精確的圖像匹配結(jié)果。

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

實驗環(huán)境為 CPU Pentium 2.94 GHz，內(nèi)存 1.5 Gbyte，顯存為128 Mbyte，操作系統(tǒng)為Windows XP，仿真平臺為Matlab 7.1，所用的圖像采集設(shè)備為Bumblebee雙目視覺相機(jī)。使用了不同場景下的圖像進(jìn)行實驗，包括光照、旋轉(zhuǎn)、縮放等情況。在這些不同的情況下進(jìn)行實驗并對傳統(tǒng)的SIFT算法和改進(jìn)后的PCA－SIFT算法在匹配的正確率和匹配所用的時間上進(jìn)行比較(實驗結(jié)果見圖2～圖5，表1～表4)。

圖2 不同算法下的匹配結(jié)果圖(截圖)

表1 原圖使用SIFT和PCA－SIFT匹配結(jié)果的比較

表2 光照改變時使用SIFT和PCA－SIFT匹配結(jié)果的比較

表3 旋轉(zhuǎn)時使用SIFT和PCA－SIFT匹配結(jié)果的比較

表4 縮放時使用SIFT和PCA－SIFT匹配結(jié)果的比較

根據(jù)表1～表4，可以得出以下結(jié)論有:1)在匹配的正確率方面。無論圖像是在光照改變，旋轉(zhuǎn)，還是在縮放的情況下PCA－SIFT都具有很穩(wěn)定的匹配性能;2)在匹配的時間方面?；赑CA－SIFT的匹配算法使得匹配的時間有所降低，提高了匹配的效率。

從實驗結(jié)果中可以看出基于PCA－SIFT描述符的匹配算法和基于傳統(tǒng)SIFT特征描述符的匹配算法在各種情況下的正確率都基本上相當(dāng)，但是在時間上PCA－SIFT算法卻大大地節(jié)約了匹配時間，這就說明PCA－SIFT算法既保持了SIFT算法穩(wěn)定性和精確性，又減少了匹配時間。

5 小結(jié)

把主成分分析法引入到傳統(tǒng)的SIFT匹配算法中，把特征描述符的維數(shù)從128維減少到20維，減少數(shù)據(jù)量，節(jié)約了整個匹配算法的運行時間。實驗證明PCA－SIFT算法既保持了傳統(tǒng)SIFT算法的穩(wěn)定性和精確性的優(yōu)點，又比傳統(tǒng)的SIFT算法有一定程度的改進(jìn)。

[1]周峰.基于尺度不變特征變換(SIFT)的圖像配準(zhǔn)技術(shù)研究[D].昆明:昆明理工大學(xué)，2010.

[2]吳若鴻.基于特征匹配的雙目立體視覺技術(shù)研究[D].武漢:武漢科技大學(xué)，2010.

[3]徐秀云.基于特征點的景象匹配技術(shù)研究[D].南京:南京理工大學(xué)，2009.

[4]馮嘉.SIFT算法的研究和改進(jìn)[D].長春:吉林大學(xué)，2010.

[5]PLUIM J P W，MAINTZ J B A，VIERGEVER M A.Mutual information matching in multiresolution contexts[EB/OL].[2011－06－12].http://www.docin.com/p－43905533.html.

[6]COPPINI G，DICIOTTI S.Matching of medical images by self－organizing neural networks[J].Pattern Recognition Letters，2004，25(3):341－352.

[7]FLUSSER J，SUK T.A moment－based approach to registration of images with affinegeometric distortion[J].IEEE Trans.Geo－Science and Remote Sensing，1994，32(2):382－387.