PCA-SIFT特征匹配算法研究

李　欽，游　雄，李　科，張彥喜

(1.鄭州測繪學(xué)院，河南 鄭州 450052；2.65014部隊(duì)，遼寧 沈陽 110000)

?

PCA-SIFT特征匹配算法研究

李欽1，游雄1，李科1，張彥喜2

(1.鄭州測繪學(xué)院，河南 鄭州 450052；2.65014部隊(duì)，遼寧 沈陽 110000)

摘要：SIFT特征具有旋轉(zhuǎn)、尺度和明暗變化的不變性，在圖像匹配中得到廣泛應(yīng)用。針對SIFT特征匹配中耗時(shí)長、匹配點(diǎn)對少、準(zhǔn)確率低的問題，提出PCA-SIFT特征匹配的方法。使用更加精簡的方法構(gòu)建特征點(diǎn)描述向量，通過預(yù)先構(gòu)建的投影矩陣對描述向量進(jìn)行主成分分析，降低描述向量的維度從而提高了特征匹配的速度，同時(shí)降維也對描述向量進(jìn)行了去噪提純，使得匹配更加準(zhǔn)確。實(shí)驗(yàn)證明，利用PCA-SIFT特征進(jìn)行匹配在降低匹配耗時(shí)的同時(shí)，增加了匹配點(diǎn)對，匹配準(zhǔn)確率也得到提高。

關(guān)鍵詞：PCA-SIFT；特征匹配；描述向量；主成分分析

數(shù)字圖像匹配技術(shù)廣泛應(yīng)用于圖像拼接與融合、目標(biāo)識別跟蹤、攝影測量遙感、圖像檢索等圖像處理和機(jī)器視覺領(lǐng)域[1]。SIFT算法因?yàn)閷ξ矬w旋轉(zhuǎn)、背景遮擋、尺度縮放、明暗變化、外界噪聲等復(fù)雜情形，都有很好的處理效果，因此在圖像匹配領(lǐng)域得到廣泛應(yīng)用。但是利用SIFT特征進(jìn)行匹配過程特別復(fù)雜，存在著耗時(shí)長、匹配點(diǎn)對少以及匹配準(zhǔn)確率低的問題。

針對SIFT特征提取需要消耗大量時(shí)間的問題，Bay H，Tuytelaars T等提出了SURF特征提取的方法[2,3]。SURF特征提取可大大縮短特征點(diǎn)匹配時(shí)間，但是匹配性能也大幅度下降，匹配準(zhǔn)確率平均只能達(dá)到SIFT算法的30%～40%；Rublee等[4]在2011年的ICCV上提出了ORB(Oriented FAST and Rotated BRIEF)特征算子。這種基于ORB的特征提取的速度比基于SIFT、SURF的方法都有了極大的提高，但是特征匹配的準(zhǔn)確性易受到圖像紋理和不均勻光照的影響；郭文靜等針對SIFT算法中描述向量計(jì)算耗時(shí)長，維數(shù)多的問題，提出了用CS-LBP(center-symmetric local binary pattern)算子結(jié)合SIFT特征點(diǎn)生成描述向量的方法[5]，首先提取SIFT特征點(diǎn)，對每個(gè)特征點(diǎn)生成81維的CS-LBP特征描述向量然后進(jìn)行匹配，這種方法能夠有效減少運(yùn)算量，加快運(yùn)算速度，然而匹配準(zhǔn)確度卻明顯下降。

以上的解決方法中，加快特征提取匹配速度的同時(shí)，匹配準(zhǔn)確度都有所下降，針對這一問題，許多學(xué)者研究了將主成分分析的方法應(yīng)用于SIFT特征提取構(gòu)造PCA-SIFT特征。主成分分析是從多指標(biāo)分析出發(fā)，運(yùn)用統(tǒng)計(jì)分析原理與方法提取少數(shù)幾個(gè)彼此不相關(guān)的綜合性指標(biāo)而保持其原指標(biāo)所提供的大量信息的一種統(tǒng)計(jì)方法，也是考察多個(gè)變量間相關(guān)性的一種多元統(tǒng)計(jì)方法。具體地說，就是將高維空間的問題轉(zhuǎn)化到低維空間去處理，使問題變得比較簡單、直觀，而且這些較少的綜合指標(biāo)之間互不相關(guān)，又能提供原有指標(biāo)的絕大部分信息[6]。目前，主成分分析方法已經(jīng)廣泛地應(yīng)用于圖像識別、分析應(yīng)用中。

傳統(tǒng)的PCA-SIFT算法[7,8]的做法是提取兩幅待匹配圖像的特征點(diǎn)，利用這些特征點(diǎn)的128維描述向量構(gòu)造投影矩陣，最后利用該投影矩陣將這些特征點(diǎn)的描述向量變換至低維空間，實(shí)現(xiàn)描述向量的主成分分析。傳統(tǒng)的PCA-SIFT算法雖然實(shí)現(xiàn)了描述向量的降維，然而構(gòu)造投影矩陣的過程卻消耗了大量的時(shí)間，且描述向量的復(fù)雜構(gòu)建過程并未改變，因此在提高特征匹配耗時(shí)上，效果并不明顯。本文采用的PCA-SIFT算法，投影矩陣是預(yù)先構(gòu)建的，且適用于相關(guān)場景的任意一幅圖像，其構(gòu)建時(shí)間無需計(jì)入特征點(diǎn)的匹配用時(shí)，同時(shí)采用一種更加精簡的方法構(gòu)建特征點(diǎn)描述向量，這就大大提高了特征點(diǎn)的匹配速度。實(shí)驗(yàn)表明，PCA-SIFT特征不僅加快了匹配速度，而且可以得到更多的匹配點(diǎn)對，匹配準(zhǔn)確性也得到提高。

1SIFT特征提取

SIFT算法是David G.Lower在1999年提出[9]，并在2004年加以完善[10]，其具有旋轉(zhuǎn)、縮放、平移變化的不變性。SIFT特征提取過程一般包括尺度空間極值點(diǎn)檢測、特征點(diǎn)精確定位、確定特征點(diǎn)主方向、計(jì)算特征點(diǎn)描述向量以及特征點(diǎn)匹配。

SIFT算法首先通過對圖像進(jìn)行不同尺度的高斯模糊和降采樣建立高斯圖像金字塔，對高斯圖像金字塔同一組中上下相鄰圖像相減得到高斯差分金字塔，在高斯差分空間中遍歷每一像素檢測極值點(diǎn)；在極值點(diǎn)處Taylor展開進(jìn)行曲線擬合，得到修正后的位置、尺度信息，從而精確定位極值點(diǎn)，通過設(shè)定閾值的方法，以及運(yùn)用海森矩陣的性質(zhì)，保留最優(yōu)特征點(diǎn)；計(jì)算特征點(diǎn)5×5鄰域范圍內(nèi)的每一個(gè)像素的梯度幅值和方向,統(tǒng)計(jì)梯度方向直方圖確定特征點(diǎn)的主方向；將坐標(biāo)軸旋轉(zhuǎn)至特征點(diǎn)主方向以保證描述向量具有旋轉(zhuǎn)不變性，將以特征點(diǎn)為圓心的16×16圓形區(qū)域等分為4×4的子區(qū)域，在每個(gè)子區(qū)域上計(jì)算8個(gè)方向的梯度方向直方圖，最終為每個(gè)子區(qū)域形成一個(gè)8維矢量，這樣便可為每個(gè)特征點(diǎn)構(gòu)建4×4×8=128維的描述向量，歸一化處理生成最終的特征點(diǎn)描述向量。

2PCA-SIFT特征提取

SIFT特征提取過程中描述向量計(jì)算復(fù)雜，且維數(shù)較高，匹配過程涉及到計(jì)算特征點(diǎn)之間的歐氏距離，描述向量的高維性無疑是這一過程計(jì)算耗時(shí)的主要原因。因此無論是描述向量的計(jì)算過程，還是特征匹配過程，都需要消耗較多的時(shí)間，難以滿足實(shí)時(shí)性的要求。另外，提取SIFT特征進(jìn)行匹配識別的應(yīng)用中，也會(huì)出現(xiàn)錯(cuò)誤匹配的情況，因此為了提高匹配準(zhǔn)確度，有必要對SIFT特征進(jìn)行改進(jìn)。

針對這些問題，在精確確定特征點(diǎn)位置之后，以一種更加精簡的方法構(gòu)建描述向量，再進(jìn)行主成分分析降低描述向量維度，在加快匹配速度的同時(shí)匹配準(zhǔn)確度也有所提高。

PCA-SIFT特征和SIFT特征具有相同的描述過程，即它們具有相同的精確定位位置、尺度及主方向[11]，所不同的是PCA-SIFT采用特征點(diǎn)周圍的m×m的像素塊(本文實(shí)驗(yàn)中采用41×41的像素塊)計(jì)算它的描述向量，并利用主成分分析的方法將描述向量降低至合適的維度(本文實(shí)驗(yàn)中將描述向量降低至36維)，以達(dá)到更精簡的表示方法。PCA-SIFT描述向量的構(gòu)建流程如圖1所示。

2.1PCA-SIFT投影矩陣的預(yù)先構(gòu)建

構(gòu)建PCA-SIFT描述向量時(shí)，預(yù)先生成投影矩陣并存儲(chǔ)，之后直接利用這些預(yù)先存儲(chǔ)的投影矩陣與描述向量相乘實(shí)現(xiàn)描述向量的主成分分析，歸一化后生成最終的PCA-SIFT描述向量，這樣投影矩陣是預(yù)先生成并存儲(chǔ)的不計(jì)入計(jì)算耗時(shí)，大大精簡了計(jì)算過程。同時(shí)，投影矩陣的適用廣泛，對于相應(yīng)場景的任意一幅圖像提取的特征點(diǎn)描述向量，都可以直接利用該預(yù)先生成的投影矩陣進(jìn)行主成分分析，無須重新生成新的投影矩陣。本文預(yù)先構(gòu)建投影矩陣的一般步驟如下：

圖1　PCA-SIFT描述向量的構(gòu)建流程

1)選擇一系列有代表性的圖像(這里代表性圖像要求是待匹配圖像所在場景及周圍拍攝的系列圖片，本文實(shí)驗(yàn)中，通過拍攝待匹配圖像所在的場景視頻，按照固定間隔提取視頻關(guān)鍵幀作為代表性圖像，視頻捕捉范圍覆蓋了待匹配圖片捕捉的場景)，利用SIFT特征點(diǎn)檢測方法精確確定這些圖像的所有特征點(diǎn)，設(shè)特征點(diǎn)總數(shù)為k。

2)對于檢測到的每一個(gè)特征點(diǎn)，將坐標(biāo)軸旋轉(zhuǎn)至特征點(diǎn)主方向，選擇特征點(diǎn)m×m鄰域范圍的像素塊，計(jì)算像素塊中每一個(gè)非邊緣像素的垂直和水平梯度，如圖2所示。

圖2　遍歷像素塊中每一個(gè)非邊緣像素

水平和垂直梯度計(jì)算公式如式(1)、式(2)所示，這樣就形成了大小為dim=(m-2)×(m-2)×2維的矢量。

4)計(jì)算協(xié)方差矩陣covA的特征值，并按照大小順序排列，獲取對應(yīng)的特征向量，選擇前n個(gè)特征向量組成大小為n×dim的矩陣并存儲(chǔ)即為投影矩陣，其中n為最終PCA-SIFT描述向量的維數(shù)，它可以是根據(jù)經(jīng)驗(yàn)設(shè)置的固定值，也可以基于特征值動(dòng)態(tài)選擇(本文實(shí)驗(yàn)中將n設(shè)置成36)。

2.2PCA-SIFT描述向量生成

通過以上步驟預(yù)先生成投影矩陣，該投影矩陣是針對測試圖像所在場景，拍攝場景中一些列圖像作為代表性圖像構(gòu)建而成的，這里要求代表性圖像捕捉的場景范圍應(yīng)盡可能地覆蓋測試圖像包含的場景。該投影矩陣的適應(yīng)性很強(qiáng)，對于代表性圖像所捕捉場景范圍內(nèi)，任意拍攝的不同測試圖像，都可以結(jié)合該投影矩陣完成圖像特征點(diǎn)描述向量的主成分分析。

如果測試圖像來自另一場景，且與構(gòu)建投影矩陣所用的場景差別很大，則需要重新構(gòu)建投影矩陣。另外，由于室外場景復(fù)雜，范圍較大，獲取代表性圖片構(gòu)建投影矩陣的困難較大，這里的PCA-SIFT特征匹配算法一般用于室內(nèi)局部場景下的圖像。

任意拍攝場景中的具有一定重疊的兩幅圖像作為待匹配測試圖像，檢測測試圖像上的每一個(gè)特征點(diǎn)，按照以下步驟計(jì)算其PCA-SIFT描述向量：

確定了特征點(diǎn)的PCA-SIFT描述向量，測試圖像對的特征匹配過程與SIFT特征匹配有著類似的過程，即查找一幅圖像中的每個(gè)特征點(diǎn)在另一幅圖像中的最鄰近和次臨近距離，設(shè)定閾值確定匹配點(diǎn)對。

3實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)條件

為了綜合對比兩種特征的匹配速度、準(zhǔn)確率及匹配點(diǎn)對數(shù)量，拍攝場景視頻，按照一定間隔提取視頻幀作為代表性圖像用于預(yù)先構(gòu)建PCA-SIFT特征中的投影矩陣，任意拍攝具有部分重疊的兩幅圖像(見圖3)作為測試圖像用于特征點(diǎn)匹配實(shí)驗(yàn)。

圖3　部分閾值條件下兩種特征匹配對比

另外根據(jù)以往實(shí)驗(yàn)經(jīng)歷，選取特征點(diǎn)周圍41×41的鄰域像素塊計(jì)算特征點(diǎn)的PCA-SIFT描述向量以獲得較好的匹配效果。本文實(shí)驗(yàn)環(huán)境為64位Linux Debian7.5，Intel(R) Core(TM) i7-3632QM CPU @ 2.20 GHz處理器，4 G內(nèi)存。

3.2實(shí)驗(yàn)步驟

結(jié)合實(shí)驗(yàn)?zāi)康模瑢?shí)驗(yàn)條件，總結(jié)實(shí)驗(yàn)步驟如下：

1)選取具有部分重疊的測試圖像，并利用SIFT特征點(diǎn)檢測方法檢測出兩幅圖像中的所有特征點(diǎn)；

2)針對待匹配測試圖片所在的場景，拍攝該場景視頻，按照一定間隔抽取關(guān)鍵幀作為代表性圖像構(gòu)建投影矩陣并存儲(chǔ)；

3)分別利用SIFT算法和本文的PCA-SIFT算法計(jì)算特征點(diǎn)的描述向量，并且統(tǒng)計(jì)各自消耗的計(jì)算時(shí)間；

4)利用兩種特征計(jì)算的描述向量各自進(jìn)行匹配，統(tǒng)計(jì)各自所用的匹配時(shí)間，改變匹配閾值(threshold),統(tǒng)計(jì)不同閾值條件下匹配點(diǎn)對數(shù)量以及錯(cuò)誤匹配點(diǎn)對數(shù)量；

5)拍攝該場景內(nèi)的其它具有部分重疊圖像作為測試圖像(場景視頻捕捉的場景范圍應(yīng)盡量覆蓋測試圖像包含的場景)，重復(fù)步驟3)、4)進(jìn)行多次實(shí)驗(yàn)，匯總實(shí)驗(yàn)結(jié)果。

3.3算法匹配準(zhǔn)確率比較

任意選取一對測試圖像，分別利用SIFT和PCA-SIFT特征進(jìn)行匹配，不同閾值條件下的特征點(diǎn)匹配情況如圖3所示，圖中黃色圓圈即為檢測到的特征點(diǎn)(左圖檢測到的特征點(diǎn)數(shù)量為746，右圖為615)，藍(lán)線連接的點(diǎn)對即為正確的匹配點(diǎn)對，紅線連接的點(diǎn)對為錯(cuò)誤的匹配點(diǎn)對。

針對該測試圖像，統(tǒng)計(jì)在不同匹配閾值條件下，利用兩種特征進(jìn)行特征點(diǎn)匹配時(shí)的匹配點(diǎn)對數(shù)量和匹配準(zhǔn)確率，匯總實(shí)驗(yàn)結(jié)果如表1所示。

表1　特定閾值下匹配點(diǎn)對數(shù)量與準(zhǔn)確率匯總

圖4　匹配閾值與匹配點(diǎn)數(shù)、匹配準(zhǔn)確率關(guān)系圖

為了直觀對比SIFT與PCA-SIFT特征的匹配性能，分別繪制利用兩種特征進(jìn)行匹配時(shí)的匹配閾值與匹配點(diǎn)數(shù)、匹配準(zhǔn)確率關(guān)系折線圖如圖4所示。

分析實(shí)驗(yàn)結(jié)果可以得到，相比于SIFT特征，PCA-SIFT特征可以獲得較多的匹配點(diǎn)對，尤其是隨著匹配閾值的增大，兩者之間的差異更加明顯。另外，隨著匹配閾值的增大，PCA-SIFT特征匹配準(zhǔn)確率始終保持在90%以上，明顯優(yōu)于SIFT特征。因此可以得到以下結(jié)論：相對于SIFT特征，利用PCA-SIFT特征進(jìn)行匹配可以得到更多的匹配點(diǎn)對，且準(zhǔn)確率明顯較高，描述向量維度的降低，并未使得匹配準(zhǔn)確率有所下降，反而使其得到提高，這是因?yàn)閷μ卣鼽c(diǎn)描述向量進(jìn)行主成分分析，不僅是對其進(jìn)行簡化，也是對其進(jìn)行去噪聲、去冗余、提純的過程，消除了描述向量里的干擾成分，使得其更加精簡緊湊。PCA-SIFT特征僅保留描述向量的本質(zhì)信息，去除了多余的干擾信息，使得匹配準(zhǔn)確率得到提高。

3.4算法執(zhí)行速度比較

PCA-SIFT特征匹配算法中，投影矩陣是預(yù)先構(gòu)建的，選取測試場景中的任意一組圖像都可以利用該投影矩陣完成主成分分析的過程。其中構(gòu)建投影矩陣所用時(shí)間主要由代表性圖像數(shù)量和每幅圖像所需的處理時(shí)間決定(實(shí)驗(yàn)中選取了1 254幀作為代表性圖像，構(gòu)建投影矩陣用時(shí)約為298 s)。選取不同的測試圖像進(jìn)行多次實(shí)驗(yàn)，統(tǒng)計(jì)利用兩種特征進(jìn)行實(shí)驗(yàn)時(shí)，描述向量計(jì)算的平均耗時(shí)，以及測試圖像特征點(diǎn)匹配的平均耗時(shí)，匯總實(shí)驗(yàn)結(jié)果如表2所示。

表2　兩種特征匹配耗時(shí)對比　ms

通過表2可以明顯看出，相對于SIFT特征，PCA-SIFT特征在描述向量的計(jì)算上耗時(shí)稍少，但是差別并不明顯，然而在特征匹配過程中，PCA-SIFT特征匹配的耗時(shí)卻明顯減少，幾乎縮短了一個(gè)量級。這主要是因?yàn)镻CA-SIFT特征經(jīng)過主成分分析的作用維數(shù)較低，使得在特征匹配過程中，通過計(jì)算歐氏距離來選擇最鄰近和次鄰近距離的用時(shí)大大減少，從而提高了匹配速度。

4結(jié)束語

本文在分析SIFT特征匹配一般過程的基礎(chǔ)上，總結(jié)了利用SIFT特征進(jìn)行匹配存在的耗時(shí)長、匹配點(diǎn)對少、準(zhǔn)確率低的問題，針對這些問題提出了PCA-SIFT特征匹配的方法。采用一種更加精簡的方法構(gòu)建特征點(diǎn)的初始描述向量，利用預(yù)先構(gòu)建的投影矩陣實(shí)現(xiàn)對初始描述向量的主成分分析，從而降低了描述向量的維度保證了匹配速度的提高，同時(shí)降維不僅是對描述向量進(jìn)行簡化，也是對其進(jìn)行去噪、提純的過程，使得生成的低維描述向量更能反映特征點(diǎn)的本質(zhì)，從而保證匹配更加準(zhǔn)確，匹配點(diǎn)對數(shù)量也明顯增多。實(shí)驗(yàn)表明，利用PCA-SIFT特征進(jìn)行匹配，在降低匹配耗時(shí)的同時(shí)，增加了匹配點(diǎn)對，提高了匹配準(zhǔn)確率。

參考文獻(xiàn)：

[1]牛俊偉，郝向陽，劉松林.一種改進(jìn)的SIFT 特征提取算法[J].測繪科學(xué)技術(shù)學(xué)報(bào)，2014，31(2):173-176.

[2]BAY H，TUYTELAARST，GOOL L V.Speeded-Up Robust Features[C].European Conference on Computer Vision，2006，1:404-417.

[3]BAY H，TUYTELAARS T，GOOL L V.Speeded-Up Robust Features(SURF)[J].Computer Vision and Image Understanding，2008，110(3):346-359.

[4]RUBLEE E，RABAUD V，KONOLIGE K,et al.ORB：an efficient alternative to SIFT or SURF[C].ICCV 2011：Proceedings of the 2011 International Conference of Computer Vision.Piscataway：IEEE,2011:2564-2571.

[5]郭文靜，李軍.基于改進(jìn)SIFT的圖像拼接算法[J].工業(yè)控制計(jì)算機(jī)，2014，27(11):17-19.

[6]浮丹丹，周紹光，徐洋,等.基于主成分分析的點(diǎn)云平面擬合技術(shù)研究[J].測繪工程，2014,23(4)：20-23.

[7]肖明亮.基于PCA-SIFT的虹膜識別研究[D].天津：中國民航大學(xué),2008.

[8]王鶴.基于PCA-SIFT算法的車牌識別技術(shù)研究[D].太原：太原理工大學(xué)，2013.

[9]LOWE D G.Object recognition from local scale-invariant feature[C].Los AlaIIlitos:The 7thIEEE International Conference on Computer Vision，1999.

[10] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004,60(2):91-110.

[11] YAN K，SUKTHANKAR R.PCA-SIFT：A More Distinctive Representation for Local Descripters[C].Proc.CVPR 2004.[S.l.]:IEEE Press，2004:506-513.

[12] 鄭守住，程朋根，陳曉勇，等.結(jié)合改進(jìn)特征算法和狄洛尼三角網(wǎng)的圖像匹配方法[J].測繪科學(xué)，2015，40(2)：155-159.

[責(zé)任編輯：劉文霞]

Research on the matching algorithm of PCA-SIFT

LI Qin1，YOU Xiong1，LI Ke1，ZHANG Yanxi2

(1.Zhengzhou Institute of Surveying and Mapping，Zhengzhou 450052，China；2.Troops 65012，Shenyang 110000，China)

Abstract：SIFT is widely used in the feature matching because it is resistant to the rotation，scale and illumination changes.The matching method of PCA-SIFT is proposed aiming at the problems of time-consuming，fewer matching points and low accuracy rate in SIFT.A simplified method is adopted to build the descriptor.The process of PCA reduces the dimensionality of the key point descriptors and improves the matching efficiency.In addition，reducing the dimension is also helpful to denoise the description vector，which makes feature matching more accurate.The experiments prove that the PCA-SIFT proposed in the paper can reduce the matching time，increase the number of matching points and improve the accuracy rate.

Key words：PCA-SIFT；feature matching；description vectors；principal component analysis

中圖分類號：TP391.41

文獻(xiàn)標(biāo)識碼：A

文章編號：1006-7949(2016)04-0019-06

作者簡介：李欽(1990-)，男，碩士研究生.

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(41201390)

收稿日期：2015-07-26