PCA-SIFT特征匹配算法研究

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

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

?

PCA-SIFT特征匹配算法研究

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

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

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

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

數字圖像匹配技術廣泛應用于圖像拼接與融合、目標識別跟蹤、攝影測量遙感、圖像檢索等圖像處理和機器視覺領域[1]。SIFT算法因為對物體旋轉、背景遮擋、尺度縮放、明暗變化、外界噪聲等復雜情形，都有很好的處理效果，因此在圖像匹配領域得到廣泛應用。但是利用SIFT特征進行匹配過程特別復雜，存在著耗時長、匹配點對少以及匹配準確率低的問題。

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

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

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

1SIFT特征提取

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

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

2PCA-SIFT特征提取

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

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

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

2.1PCA-SIFT投影矩陣的預先構建

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

圖1　PCA-SIFT描述向量的構建流程

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

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

圖2　遍歷像素塊中每一個非邊緣像素

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

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

2.2PCA-SIFT描述向量生成

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

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

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

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

3實驗分析

3.1實驗條件

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

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

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

3.2實驗步驟

結合實驗目的，實驗條件，總結實驗步驟如下：

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

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

3)分別利用SIFT算法和本文的PCA-SIFT算法計算特征點的描述向量，并且統計各自消耗的計算時間；

4)利用兩種特征計算的描述向量各自進行匹配，統計各自所用的匹配時間，改變匹配閾值(threshold),統計不同閾值條件下匹配點對數量以及錯誤匹配點對數量；

5)拍攝該場景內的其它具有部分重疊圖像作為測試圖像(場景視頻捕捉的場景范圍應盡量覆蓋測試圖像包含的場景)，重復步驟3)、4)進行多次實驗，匯總實驗結果。

3.3算法匹配準確率比較

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

針對該測試圖像，統計在不同匹配閾值條件下，利用兩種特征進行特征點匹配時的匹配點對數量和匹配準確率，匯總實驗結果如表1所示。

表1　特定閾值下匹配點對數量與準確率匯總

圖4　匹配閾值與匹配點數、匹配準確率關系圖

為了直觀對比SIFT與PCA-SIFT特征的匹配性能，分別繪制利用兩種特征進行匹配時的匹配閾值與匹配點數、匹配準確率關系折線圖如圖4所示。

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

3.4算法執行速度比較

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

表2　兩種特征匹配耗時對比　ms

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

4結束語

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

參考文獻：

[1]牛俊偉，郝向陽，劉松林.一種改進的SIFT 特征提取算法[J].測繪科學技術學報，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]郭文靜，李軍.基于改進SIFT的圖像拼接算法[J].工業控制計算機，2014，27(11):17-19.

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

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

[8]王鶴.基于PCA-SIFT算法的車牌識別技術研究[D].太原：太原理工大學，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] 鄭守住，程朋根，陳曉勇，等.結合改進特征算法和狄洛尼三角網的圖像匹配方法[J].測繪科學，2015，40(2)：155-159.

[責任編輯：劉文霞]

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

文獻標識碼：A

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

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

基金項目：國家自然科學基金資助項目(41201390)

收稿日期：2015-07-26