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

馬 莉，韓 燮

(中北大學電子與計算機科學技術學院，山西 太原 030051)

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

1 生成SIFT特征描述符

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

1.1 尺度空間的建立

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

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

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

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

1.2 計算關鍵點的特征方向

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 對應特征點的匹配

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

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

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

3.2 消除錯誤匹配

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

3.3 變換模型參數的估計

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

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

4 實驗結果及分析

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

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

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

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

表3 旋轉時使用SIFT和PCA－SIFT匹配結果的比較

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

根據表1～表4，可以得出以下結論有:1)在匹配的正確率方面。無論圖像是在光照改變，旋轉，還是在縮放的情況下PCA－SIFT都具有很穩定的匹配性能;2)在匹配的時間方面。基于PCA－SIFT的匹配算法使得匹配的時間有所降低，提高了匹配的效率。

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

5 小結

把主成分分析法引入到傳統的SIFT匹配算法中，把特征描述符的維數從128維減少到20維，減少數據量，節約了整個匹配算法的運行時間。實驗證明PCA－SIFT算法既保持了傳統SIFT算法的穩定性和精確性的優點，又比傳統的SIFT算法有一定程度的改進。

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

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

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

[4]馮嘉.SIFT算法的研究和改進[D].長春:吉林大學，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.