馬 莉，韓 燮

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

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

1 生成SIFT特征描述符

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

1.1 尺度空間的建立

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

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

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

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

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

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

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

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

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

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

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

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

3)計(jì)算所有樣本點(diǎn)的特征向量與平均特征向量的差，得到差值向量

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

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

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

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

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

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

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

3.1 對(duì)應(yīng)特征點(diǎn)的匹配

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

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

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

3.2 消除錯(cuò)誤匹配

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

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

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

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

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

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

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

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

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

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

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

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

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

5 小結(jié)

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

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

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

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

[4]馮嘉.SIFT算法的研究和改進(jìn)[D].長(zhǎng)春:吉林大學(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.