張寧麗，馬 燕，李順寶，徐衍魯，程 瑋

(上海師范大學(xué) a.信息與機(jī)電工程學(xué)院；b.數(shù)理學(xué)院，上海 200234)

?

FKPCA-SIFT算法在圖像匹配中的應(yīng)用

張寧麗a，馬 燕a，李順寶b，徐衍魯a，程 瑋b

(上海師范大學(xué) a.信息與機(jī)電工程學(xué)院；b.數(shù)理學(xué)院，上海 200234)

SIFT是目前廣泛應(yīng)用于目標(biāo)識(shí)別和圖像匹配領(lǐng)域的算法，但其在使用過程中存在描述子維數(shù)過大、耗時(shí)時(shí)間長(zhǎng)的缺點(diǎn)。針對(duì)這個(gè)問題，常用的解決辦法是利用PCA算法對(duì)描述子進(jìn)行降維，由于PCA是一種線性降維算法，因此它的使用具有局限性。對(duì)此，利用模糊K均值算法對(duì)其進(jìn)行改進(jìn)(稱為FKPCA)，并用改進(jìn)的RANSAC算法消除誤匹配點(diǎn)。實(shí)驗(yàn)結(jié)果表明，PCA-SIFT算法和FKPCA-SIFT都很好地保持了SIFT算法原有的優(yōu)點(diǎn)，具有很高的匹配正確率。但相對(duì)于PCA-SIFT算法，F(xiàn)KPCA-SIFT不僅適用于線性降維也適用于非線性降維，具有更好的匹配精度，拓展了PCA-SIFT算法的適用范圍。

SIFT；PCA-SIFT；FKPCA-SIFT；RANSAC；線性降維；非線性降維

David G.Lowe在2004年總結(jié)提出一種基于尺度空間的特征匹配算法(SIFT)，它對(duì)于尺度變換、光照和旋轉(zhuǎn)都有很強(qiáng)的穩(wěn)定性，因此廣泛應(yīng)用于目標(biāo)識(shí)別和圖像匹配等眾多領(lǐng)域[1]。但是它也存在維數(shù)過大、耗時(shí)過長(zhǎng)的特點(diǎn)，傳統(tǒng)的處理方法是引入PCA(主成分分析)算法，構(gòu)成基于主成分的特征不變變換PCA-SIFT，對(duì)SIFT算法中得到的特征向量進(jìn)行降維，該算法在繼承SIFT很多優(yōu)點(diǎn)的基礎(chǔ)上[2]，提高匹配速度。但是PCA算法是一種線性降維方法，這就限制了它只能用于對(duì)具有線性特征的數(shù)據(jù)進(jìn)行降維，而對(duì)于非線性數(shù)據(jù)，其降維效果就不是很理想。而FKmeans(模糊K均值算法)是一種既能夠用于線性數(shù)據(jù)也能夠用于非線性數(shù)據(jù)的聚類算法，因此，文中利用FKmeans算法對(duì)PCA-SIFT算法進(jìn)行改進(jìn)(以下簡(jiǎn)稱FKPCA-SIFT算法)，既保留了傳統(tǒng)PCA-SIFT算法的所有優(yōu)點(diǎn)，且拓展了PCA-SIFT算法的適用范圍，相比較PCA-SIFT算法，F(xiàn)KPCA-SIFT算法更具有普遍適用性。

1 SIFT算法描述

1.1 檢測(cè)尺度空間的極值

一幅圖像的尺度空間L(x,y,σ)，定義為一個(gè)尺度可變化的高斯函數(shù)G(x,y,σ)與原圖矩陣I(x,y)的卷積，即

L(x,y,σ)=I(x,y)*G(x,y,σ)

(1)

式中：*代表兩個(gè)式子之間做卷積；(x,y)代表圖像中每個(gè)像素位置；σ表示尺度空間大小因子，其值越小表明圖像平滑越多；相反地，圖像平滑越少。

使用高斯金字塔來表示不同層次的尺度空間，首先對(duì)原圖進(jìn)行不同尺度的高斯模糊，然后對(duì)圖像進(jìn)行降采樣(隔點(diǎn)采樣)，構(gòu)建高斯金字塔。將經(jīng)過高斯模糊后的不同尺度的相鄰上下兩層圖像作差，如式(2)所示，由此可得3組高斯差分圖像(每組內(nèi)N張圖像)，然后在各組內(nèi)的高斯差分圖像(DoG)上進(jìn)行極值檢測(cè)[3]。

D(x，y，σ)=L(x，y，Kσ)-L(x，y，σ)

(2)

式中：L(x,y,σ) 表示尺度為σ的尺度空間；L(x，y，Kσ)表示尺度為Kσ的尺度空間；D(x，y，σ)表示圖形差分空間。為了尋找DoG圖像的極值點(diǎn)，要將同一組內(nèi)相鄰兩層DoG圖像中每一個(gè)像素點(diǎn)和它相鄰的所有點(diǎn)進(jìn)行比較，看其是否是它的尺度域和圖像域中的最大點(diǎn)或最小點(diǎn)。圖1中，中間尺度圖像中的中心檢測(cè)點(diǎn)要首先和與它同尺度的8個(gè)相鄰點(diǎn)相比較，然后再與上下相鄰尺度空間中的18個(gè)點(diǎn)進(jìn)行比較，所以共需要比較26個(gè)點(diǎn)，這樣可以確保在原圖像和處理后的尺度空間中都檢測(cè)到極值點(diǎn)。

圖1 檢測(cè)極值點(diǎn)

1.2 關(guān)鍵點(diǎn)定位

1.3 關(guān)鍵點(diǎn)方向的確定

m(x,y)=

(3)

θ(x,y)=arctan((L(x,y+1)-L(x,y-1))/(L(x+1, y)-L(x-1,y)))

(4)

1.4 生成關(guān)鍵點(diǎn)描述子

SIFT特征點(diǎn)描述子是通過關(guān)鍵點(diǎn)在其領(lǐng)域高斯圖像梯度統(tǒng)計(jì)結(jié)果表示的。首先將選取的關(guān)鍵點(diǎn)的鄰域分塊，計(jì)算每個(gè)小塊內(nèi)的方向直方圖，生成每塊內(nèi)獨(dú)特的向量，該向量抽象了該區(qū)域內(nèi)的圖像信息，因此對(duì)每個(gè)鄰域來說是唯一的。通過大量的實(shí)驗(yàn)，Lowe建議描述子使用關(guān)鍵點(diǎn)鄰域尺度空間內(nèi)的1個(gè)4×4的窗口，然后計(jì)算每個(gè)窗口內(nèi)的8個(gè)方向的梯度信息，生成1個(gè)4×4×8=128維向量來表示該關(guān)鍵點(diǎn)[4]。

2 PCA-SIFT算法

2.1 PCA-SIFT算法實(shí)現(xiàn)步驟

SIFT算法具有很好的魯棒性和抗干擾性，有著廣泛的應(yīng)用，但是由于SIFT算子具有很高的維度，增加了其計(jì)算復(fù)雜性和時(shí)間復(fù)雜度，并且在大規(guī)模特征數(shù)據(jù)庫(kù)的檢索中存在存儲(chǔ)壓力。針對(duì)SIFT算法本身存在的這種數(shù)據(jù)量大、耗時(shí)長(zhǎng)的問題，最常用的方法是采用PCA(主成分分析)算法對(duì)描述子進(jìn)行降維，它通過一個(gè)正交變換把原數(shù)據(jù)變換到一個(gè)新的坐標(biāo)系統(tǒng)中，用幾個(gè)較少的綜合指標(biāo)來代替原來較多的指標(biāo)，從而實(shí)現(xiàn)高維數(shù)據(jù)到低維數(shù)據(jù)的轉(zhuǎn)換。實(shí)驗(yàn)證明將SIFT算法與傳統(tǒng)的PCA算法結(jié)合[5]，不僅能保存SIFT算法原有的特性，而且降低了SIFT描述子的維數(shù)，從而減少了數(shù)據(jù)量，提高匹配速率。

利用PCA算法對(duì)128維的SIFT特征描述子進(jìn)行降維時(shí)，首先將兩幅圖像所得的N個(gè)SIFT描述子拼接成一個(gè)N×128維的矩陣M，計(jì)算M的平均特征向量[6]。然后計(jì)算樣本點(diǎn)與平均特征向量的差值向量，最后構(gòu)建協(xié)方差矩陣，計(jì)算它的特征值和特征向量，將特征值和特征向量按照降序進(jìn)行排序，選取排序后矩陣中的前t個(gè)特征向量構(gòu)成一個(gè)投影矩陣，從而將描述子投影到一個(gè)較低的t維子空間中，提高匹配效率[7]。

2.2 PCA算法的不足

主成分分析算法PCA(Principal Components Analysis)是利用少數(shù)的幾項(xiàng)綜合指標(biāo)來代表原來的多項(xiàng)指標(biāo)，然后用綜合指標(biāo)來解釋多項(xiàng)指標(biāo)的方差—協(xié)方差結(jié)構(gòu)。這幾項(xiàng)綜合指標(biāo)即為原來多項(xiàng)指標(biāo)的主成分，所得到的綜合指標(biāo)主成分，要盡可能多地保留原指標(biāo)中的信息且彼此不相關(guān)[8]。雖然利用PCA算法對(duì)SIFT特征描述子進(jìn)行降維時(shí)，可以保留描述子的大部分信息，但是利用主成分分析法進(jìn)行數(shù)據(jù)降維時(shí)，也存在一定的不足。首先，在提取主成分的過程中，要將指標(biāo)正態(tài)標(biāo)準(zhǔn)化，在將指標(biāo)進(jìn)行標(biāo)準(zhǔn)化的過程中，會(huì)消除各指標(biāo)在因變異造成的影響，按照以上算法提取的主成分存在信息丟失的現(xiàn)象，它只包含了各指標(biāo)之間相互影響這部分信息，從而使得特征提取性下降。其次，PCA算法是一個(gè)線性降維方法，當(dāng)指標(biāo)間的線性程度不高時(shí)，應(yīng)用線性主成分分析算法也會(huì)造成特征提取能力的下降，如圖2所示。最后，當(dāng)每個(gè)主成分前的負(fù)荷因子的符號(hào)有正有負(fù)時(shí)，綜合評(píng)價(jià)函數(shù)的意義就不明確，無法清晰的命名[9]，圖3是PCA-SIFT算法匹配后，經(jīng)過改進(jìn)的RANSAC算法對(duì)Box的處理結(jié)果。

圖2 利用PCA-SIFT對(duì)Box處理的結(jié)果

圖3 利用FKPCA-SIFT對(duì)Box處理的結(jié)果

3 利用模糊K均值算法對(duì)PCA-SIFT進(jìn)行改進(jìn)

模糊K均值算法是把n個(gè)向量，經(jīng)過訓(xùn)練之后，分為c個(gè)組，并為每一組求得一個(gè)聚類中心，使得每個(gè)向量和聚類中心之間的相似性指標(biāo)的價(jià)值函數(shù)達(dá)到最大。模糊K-means算法使用模糊劃分，對(duì)于每個(gè)給定的數(shù)據(jù)點(diǎn)，用值在[0，1]間的一個(gè)隸屬度來確定其屬于各個(gè)聚類中心的程度。然后根據(jù)其隸屬度，將各個(gè)數(shù)據(jù)點(diǎn)歸到相應(yīng)的類里。算法實(shí)現(xiàn)的具體步驟為[10-11]：

2)由k個(gè)聚類中心，求得平均特征向量

(5)

然后計(jì)算所有聚類中心點(diǎn)的特征向量與平均特征向量的差值向量

(6)

3)構(gòu)建協(xié)方差矩陣[12]

(7)

計(jì)算協(xié)方差矩陣的特征值λi和特征向量ei,i=1,2,…,k。

5)把原來的128維SIFT特征描述子通過式(8)投影到另一個(gè)N維子空間中，從而可以得到t維的PCA-SIFT描述子。

Yi=Xi×A

(8)

模糊K均值聚類算法是一種既可以用于線性，也可以用于非線性的聚類方法，而PCA是一種線性降維算法，所以，首先利用模糊K-means算法改進(jìn)PCA不能用于非線性降維的不足，然后再與SIFT結(jié)合，使其匹配更精確[13]，圖3是FKPCA-SIFT算法匹配后，經(jīng)過改進(jìn)的RANSAC算法對(duì)Box的處理結(jié)果。

4 改進(jìn)的RANSAC算法

通過SIFT算法初步匹配后，由于匹配過程中顏色等信息的丟失，會(huì)存在一些誤匹配的點(diǎn)，所以需要利用一種算法去除這些誤匹配的點(diǎn)，使得圖像能夠正確匹配。一般情況下，可以利用最小二乘法，對(duì)于得到的特征點(diǎn)進(jìn)行直線擬合，然后判斷各點(diǎn)到直線的距離，由此來去除誤匹配的點(diǎn)。但是SIFT算法中匹配點(diǎn)較多，直接利用最小二乘法進(jìn)行擬合時(shí)，會(huì)出現(xiàn)一些偏離很大的點(diǎn)，這里稱之為野點(diǎn)，使得擬合的直線與理想直線有很大的偏差，不能夠正確地去除誤匹配點(diǎn)。

為了更好地去除錯(cuò)誤數(shù)據(jù)(野點(diǎn))，常使用一些魯棒性比較好地去除誤匹配算法：RANSAC算法。它的基本思想是：假設(shè)給定了一組正確的樣本數(shù)據(jù)，則必定能夠找到一種方法來計(jì)算出符合這些數(shù)據(jù)模型的參數(shù)。而原樣本中包含的可以被所建模型準(zhǔn)確描述的數(shù)據(jù)，稱為內(nèi)點(diǎn)(inliers)。而原樣本中偏離所建模型很遠(yuǎn)的異常數(shù)據(jù)，稱為外點(diǎn)(outliers)。具體過程是：每次隨機(jī)抽取樣本中的兩個(gè)數(shù)據(jù)，由這兩個(gè)點(diǎn)得到一個(gè)直線方程。然后計(jì)算其他樣本點(diǎn)到達(dá)這條直線的距離，如果得到的距離小于給定的閾值，則將這個(gè)點(diǎn)看做是內(nèi)點(diǎn)，否則為外點(diǎn)。最后統(tǒng)計(jì)所有的內(nèi)點(diǎn)，計(jì)算符合所得到的直線方程的內(nèi)點(diǎn)數(shù)目，重復(fù)以上過程，以得到內(nèi)點(diǎn)數(shù)目最多的直線作為最終的擬合直線[14]。

對(duì)于得到的擬合直線，計(jì)算每點(diǎn)到直線的距離，根據(jù)以下準(zhǔn)則，去除SIFT算法初始匹配中的誤匹配點(diǎn)[15]

(9)

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

實(shí)驗(yàn)環(huán)境為CPU3.20GHz，內(nèi)存為4.0Gbyte，操作系統(tǒng)為Windows7，仿真平臺(tái)為MATLAB7.12.0。實(shí)驗(yàn)中采用了不同場(chǎng)景下的圖像進(jìn)行對(duì)比，分別用傳統(tǒng)的PCA-SIFT算法和FKPCA-SIFT算法對(duì)圖像進(jìn)行處理，然后從匹配的正確率和匹配點(diǎn)數(shù)上進(jìn)行比較(實(shí)驗(yàn)結(jié)果見圖4～圖9)。

圖4 利用PCA-SIFT對(duì)Building圖像處理的結(jié)果

圖5 利用FKPCA-SIFT算法對(duì)Building的匹配結(jié)果

圖6 利用PCA-SIFT對(duì)Beaver的匹配結(jié)果

圖7 利用FKPCA-SIFT對(duì)Beaver的匹配結(jié)果

圖8 利用PCA-SIFT對(duì)Cow的處理結(jié)果

圖9 利用FKP CA-SIFT對(duì)Cow處理的結(jié)果

從表1～3可以得出以下結(jié)論：

1) 正確率：無論是PCA-SIFT算法還是FKPCA-SIFT算法都繼承了SIFT算法對(duì)于尺度變換和旋轉(zhuǎn)的魯棒性，經(jīng)過改進(jìn)的RANSAC算法去除誤匹配后保證圖像中各個(gè)點(diǎn)都能夠正確匹配。

2) 匹配精確度：由于PCA是一種線性降維方法，所以對(duì)于具有線性特征分布的特征點(diǎn)，它能夠起到很好的降維作用，如對(duì)圖4中的Building降維，能夠保留足夠的特征點(diǎn)用于圖像的正確匹配，但是對(duì)于非線性分布的特征點(diǎn)，通過PCA處理后，很多特征點(diǎn)都會(huì)被去除掉，如圖6和圖8，經(jīng)過PCA-SIFT處理后，只有少數(shù)的點(diǎn)被保留，雖然匹配正確率很高，但是匹配精度很低，圖像的很多區(qū)域都沒有被匹配，只有少數(shù)區(qū)域得到匹配。而利用FKPCA-SIFT算法可以彌補(bǔ)PCA-SIFT的這個(gè)缺點(diǎn)，如圖7和圖9，利用FKPCA-SIFT對(duì)圖像處理的結(jié)果，圖像中大部分區(qū)域都能夠得到正確匹配，在保證匹配正確率的前提下提高了匹配精度。

表1 PCA-SIFT與FKPCA-SIFT對(duì)Building的匹配結(jié)果對(duì)比

表2 PCA-SIFT與FKPCA-SIFT對(duì)Beaver的匹配結(jié)果對(duì)比

表3 PCA-SIFT與FKPCA-SIFT對(duì)Cow的匹配結(jié)果對(duì)比

6 小結(jié)

PCA-SIFT算法和FKPCA-SIFT算法都是在保持SIFT算法對(duì)于尺度變換和旋轉(zhuǎn)魯棒性的基礎(chǔ)上，在匹配速率上對(duì)該算法做出改進(jìn)，相對(duì)于PCA-SIFT算法，F(xiàn)KPCA-SIFT算法不僅具有對(duì)數(shù)據(jù)進(jìn)行降維，節(jié)約匹配時(shí)間的優(yōu)點(diǎn)，而且進(jìn)一步拓展了它的適用范圍。它不僅對(duì)于線性分布的特征點(diǎn)有很好的匹配精度，對(duì)于非線性分布的特征點(diǎn)也有很高的匹配正確率和匹配精度，因此具有更好的適用性，為相關(guān)的研究提供一個(gè)參考平臺(tái)。

[1]LOWEDG.Distinctiveimagefeaturesfromscale-invariantkeypoint

[J].International Journal of Computer Vision，2004，60(2)：91-110.

[2]LOWE D G.Object recognition from local scale-invariant features[C]//Proc.International Conference on Computer Vision.Corfu，Greece：IEEE Press，1999：1150-1157.

[3]FERGUS R，PERONA P，ZISSERMAN A.Object class recognition by unsupervised scale-invariant learning[C]//Proc.IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]：IEEE Press，2003：264-271.

[4]QIU Wentao，ZHAO Jian，LIU Jie.Image matching combine SIFT with regional SSDA[C]//Proc.International Conference on Control Engineering and Communication Technology.[S.l.]：IEEE Press，2012：177-179.

[5]TURK M，PENTLAND A.Face recognition using eigenfaces[J].Computer Vision and Pattern Recognition，1991，32(5)：1289-1295.

[6]SHARMA G，CHAUDHURY S，SRIVASTAVA J.Bag-of-features kernel eigen spaces for classification[C]//Proc.International Conference on Pattern Recognition.[S.l.]：IEEE Press，2008：1-4.

[7]ZHANG Y，WEI K B.Research on wide baseline stereo matching based on PCA-SIFT[C]//Proc.International Conference on Advanced Computer Theory and Engineering.[S.l.]：IEEE Press，2010：137-140.

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

[9]徐永智，華惠川.對(duì)主成分分析三點(diǎn)不足的改進(jìn)[J].科技管理研究，2009(6)：128-130.

[10]KANUNGO T，MOUNT D M.An efficient K-means clustering algorithm： analysis and implementation[J].IEEE Trans.Pattern Analysis and Maching Intelliggence，2002，24(7)：881-892.

[11]江秋鑫.基于SIFT特征的圖像相似性度量及其應(yīng)用研究[D].大連：大連理工大學(xué)，2012.

[12]李麗麗.模糊C-均值聚類算法及其在圖像分割中的應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2009.

[13]KANUNGO T，MOUNT D.An efficient K-means clustering algorithm： analysis and implantation[J].IEEE Trans.PAMI，2004(24)：881-892.

[14]BHATTACHARYA P，GAVRILOVA M.Improving RANSAC feature matching with local topological information[J].Voronoi Diagrams in Science and Engineering(ISVD)，2012，29(7)：17-23.

[15]延偉東，田錚，溫金環(huán)，等.基于偏最小二乘的SIFT誤匹配校正方法[J].計(jì)算機(jī)應(yīng)用，2012，32(5)：1255-1257.

張寧麗(1990— )，女，碩士研究生，主研圖像處理與模式識(shí)別；

馬 燕(1970— )，女，教授，主研圖像處理與模式識(shí)別；

李順寶(1963— )，副教授，主研計(jì)算機(jī)應(yīng)用；

徐衍魯(1989— )，女，碩士研究生，主研圖像處理與模式識(shí)別；

程 瑋(1985— )，助教，主研網(wǎng)絡(luò)與多媒體技術(shù)。

責(zé)任編輯：時(shí) 雯

Application of FKPCA-SIFT Algorithm in Image Matching

ZHANG Ninglia，MA Yana，LI Shunbaob，XU Yanlua，CHENG Weib

(a.DepartmentofInformationMechanicalandElectricalEngineering；b.DepartmentofMathematic&Science，ShanghaiNormalUniversity，Shanghai200234，China)

SIFT algorithm is widely used in the field of object recognition and image matching.But it also has disadvantages that sub-dimension is too large and time-consuming.For this problem， the common solution is using PCA algorithm to reduce dimension of the descriptors.But PCA is a linear dimensionality reduction algorithm， so its use is limited.For this situation， using the fuzzy K-means algorithm to improve it (called FKPCA) and eliminate false matching points with an improved RANSAC algorithm.The experimental results are shown that both of the PCA-SIFT and FKPCA-SIFT algorithm can perfectly keep the original advantages of SIFT that have a high matching accuracy.But compared with the PCA-SIFT algorithm， FKPCA-SIFT can not only be used to the linear dimension reduction， it can also be applied to non-linear situation.The FKPCA-SIFT has better matching accuracy and expands the application scope of PCA-SIFT.

SIFT；PCA-SIFT； FKPCA-SIFT； improved RANSAC； linear dimensionality reduction； non-linear dimensionality reduction

國(guó)家自然科學(xué)基金項(xiàng)目(61373004)

TP391.4

A

10.16280/j.videoe.2015.07.005

2014-04-22

【本文獻(xiàn)信息】張寧麗，馬燕，李順寶，等.FKPCA-SIFT算法在圖像匹配中的應(yīng)用[J].電視技術(shù),2015，39(7).