一種基于PCA降維的SIFT算法

肖璞，殷一鳴

（三江學院計算機科學與工程學院，南京210012）

0 引言

人臉識別是生物特征識別技術中重要的研究領域。由于臉部圖像采集過程中情緒和環境的變化，如多姿態的表情、光照強度的變化、噪聲強度的變化、旋轉、縮放尺度、人臉上的遮擋物（眼鏡、太陽鏡、帽子、傷口敷料等）、年齡變化等，準確而強大的人臉識別系統面臨著巨大的挑戰。SIFT算法基于尺度空間上圖像潛在的對尺度和選擇不變的興趣點，與圖像的大小、尺度縮放、旋轉都無關。該算法對于光照強度的變化、噪聲強度的變化以及微視角變化的容忍度相當高，保持了一定程度的穩定性。然而，SIFT算法的缺點也不容忽視。該算法具有高維度，每個特征點包含128維特征描述符，計算量很大。計算復雜度高，計算過程繁瑣，嚴重影響了人臉識別的實時性。經典的SIFT算法的計算量很大，每一個特征點都包含有4×4×8=128個特征描述向量，在細節復雜的區域提取過多的特征點容易產生誤匹配，針對目標跟蹤的實時性，SIFT算法的效率極低。

本文提出了一種改進的基于PCA降維的SIFT算法，在SIFT算法的原有基礎上利用降維方法來降低維度，簡化計算復雜性和計算繁瑣的過程，提高人臉識別的效率。改進的SIFT算法相比原有的SIFT算法有著明顯的優越性，在保持原算法的光照不變性，旋轉不變性，尺度縮放不變性和遮擋不變性的同時，可以加快海量數據的處理速度。

1 改進的PCA-SIFT算法

1.1 SIFT算法

人臉識別系統大致分為以下四個階段：人臉圖像采集及檢測、人臉圖像預處理、人臉圖像特征提取、人臉圖像匹配與識別[1]。其中，人臉圖像特征提取是人臉識別過程中至關重要的一步。特征提取不僅提取輸入圖像中最有用的特征，而且還大大降低了圖案樣本的維度。輸入的人臉圖像的特征點數量很多，所構建的尺度空間維數也很高，通過對人臉圖像的提取以獲得最有用的人臉特征，也達到了將尺度空間從高維降到了低維[2]。而人臉圖像特征提取的方法有尺度不變特征變換算法（SIFT）[3]等。人臉圖像匹配與識別是人臉識別流程的最后一步，最常用的相似度匹配算法是歐氏距離（Euclidean Distance），因為它具有明確的物理意義，良好的聚類效果，容易實現的特點[4]。

尺度空間理論[5]的提出最早可追溯到1962年。SIFT算法是一些基于尺度空間上圖像潛在的對尺度和選擇不變的興趣點，與圖像的大小、尺度縮放、旋轉都無關。同時，SIFT算法對于光照強度的變化、噪聲強度的變化以及微視角變化的容忍度相當高，保持了一定程度的穩定性。使用SIFT特征算法對于遮擋的人臉的偵測率也相當得高，僅僅是需要3個以上的SIFT人臉特征就能夠識別檢測出人臉。此外，SIFT算法獨特且信息豐富，可以在海量特征庫中快速準確地匹配。

國內外的研究學者針對SIFT算法提出了許多改進算法。林曉帆等人提出了基于SURF描述子的遙感圖像配準[6]，經過改進的SURF發算法極大地提高了效率，但該算法只是側重于遙感圖像的配準。芮挺等人提出了基于SIFT描述的Harris角點多源圖像配準[7]，也提高了匹配效率，提升了精度；張少敏等人提出了融合SIFT特征的熵圖估計醫學圖像非剛性匹配[8]，將醫學圖像配準改進的具有良好的魯棒性，該算法也只是側重于醫學圖像配準[9]。有許多學者提出了不同的改進方法，都有取得一定的成果，但也有一定的局限性。

1.2 PCA降維技術

在處理圖像時，為了提高準確率，一般會提取較多的特征點或是一些較為復雜的特征點，每個特征點又會生成128維的特征描述子。為了改進SIFT算法這種特性，需要對其引入降維技術處理，將120維的特征向量降維64維，甚至是32維的特征向量。

PCA作為一種線性降維技術，它將許多相關輸入特征的樣本作為輸入，并輸出作為輸入特征的線性組合的正交特征。也就是說將高維的原始圖像通過投影的方法映射到低維的空間中，并希望盡可能多地保留原始圖像的像素點，去除帶有比較少量信息的像素點。映射后數據的方差越大，保留的原始圖像的特征點越多。

PCA算法的核心是找到最大方差。設W是投影矩陣，則圖像x在新坐標里的投影是WTx，方差為WTxxTW，目標函數為：

再使用拉格朗日公式對公式（13）求解，得：

其中-λ是XXT的特征值，要想把圖像從n維降到k維，需要k個特征值對應的特征向量，由k個特征向量組成的矩陣W[10]。

研究證明，PCA是丟失原始圖像的像素點最少的一種線性降維技術。LDA算法也是一種比較經典的線性降維方法，但它有一個基本前提自變量是正態分布的。本文利用PCA降維技術對SIFT算法進行降維處理。

1.3 改進的PCA-SIFT算法

雖然，SIFT算法應用于人臉識別中解決了圖像的旋轉、尺度縮放、光照變化、噪聲干擾等問題，但由于存在高維（128維）的特征向量，使得計算復雜度較高，識別過程所需要的時間較長，實時性不高。為解決這一問題，本文提出了一種基于PCA降維的SIFT算法，利用對特征點具有篩選功能的PCA算法，將SIFT算法事先提取出來的特征點進行篩選過濾，把高維數據投影到低維空間中，去除冗余的特征點，從而改變了生成特征描述子的方式，達到降維的效果。生成PCA-SIFT描述子的流程圖如圖1所示。

圖1 生成PCA-SIFT描述子的流程圖

計算PCA-SIFT投影矩陣的算法描述如下：

（1）利用SIFT算法將訓練集中的特征點提取出，個數記為n。

（2）對每一個特征點在開始生成特征描述子的時候，劃分一個41×41的鄰域窗口，并將坐標軸旋轉至特征點主方向。去除四個角的邊緣像素，計算剩余每個像素在水平和豎直方向上的梯度，得到39×39×2=3042的描述向量。

（3）計算n個特征點的3042維描述向量的平均向量，并且用n個特征點的3042維向量減去平均向量，將得到的差值放入n×3042的矩陣W中。

（4）計算矩陣W的協方差矩陣CovW，并計算協方差矩陣CovW的特征值和特征向量。

（5）將獲得的特征值從大到小進行排序，選擇前k個特征值對應的特征向量作為主成分方向，從而組成k×3042的投影矩陣。其中k為PCA-SIFT特征描述子的維數。

生成PCA-SIFT特征描述子的算法步驟如下：

（1）將坐標軸旋轉至特征點的主方向，劃分一個41×41的鄰域窗口，并計算去除邊緣角點像素后的每個像素在水平和豎直方向上的梯度，即得到一個39×39×2=3042維的描述向量。

（2）利用上一節求得的投影矩陣乘以該向量，得到一個k維的特征向量。

2 PCA-SIFT算法實現

2.1 ORL人臉數據庫

ORL人臉數據庫是由英國劍橋大學AT&T實驗室創建的，里面包含有40個人，每人10張不同表情、姿態或含有不同程度遮擋物的灰度圖像。圖片的尺寸均為92×112。這是目前研究人臉識別使用最多的人臉數據庫之一。

2.2 算法實現

（1）SIFT算法的實現步驟如下：

Step1：構建DOG差分尺度空間。

Step2：構造高斯金字塔。

Step3：使用DOG來代替LOG，用差分代替微分。

Step4：構建DOG金字塔。

Step5：尋找關鍵點。

Step6：關鍵點精確定位。

Step7：刪除邊緣效應。

Step8：方向賦值：根據檢測到的關鍵點的局部圖像結構為特征點方向賦值。

（2）PCA算法不同維度的比較。

①首先定義PCA算法。

Step1：對列求平均值。

Step2：將所有樣例減去對應均值得到A。

Step3：獲取協方差矩陣。

Step4：求協方差矩陣的特征值和特征向量。

Step5：按列取前r個特征向量。

Step6：小矩陣特征向量向大矩陣特征向量過渡。

Step7：循環對特征向量歸一化。

②訓練PCA算法。

分別降維到40、30、20和10時的準確率如圖2所示。

圖2 不同維數的識別準確率的綜合圖

本文中我們選擇k=20，也就是說會把SIFT的128維特征描述子降到20維的PCA-SIFT特征描述子[11]。

3 實驗對比與分析

針對不同表情、姿態的變化、遮擋物，比例縮放等因素的影響，以下四組實驗展現了效果，如表1所示。

表1 實驗效果比較表

根據實驗結果對SIFT算法和PCA-SIFT兩種算法進行比較，如表2所示。

表2 SIFT算法和改進的PCA-SIFT算法的優缺點比較表

SIFT算法和PCA-SIFT兩種算法運算時間的比較如表3所示。

表3 SIFT算法和改進的PCA-SIFT算法運算時間比較表

綜上所述，改進的PCA-SIFT算法在效率上明顯優于SIFT算法，提高了算法的計算速度。

4 結語

本文基于PCA降維技術對SIFT算法進行了改進，完成了以下工作：

（1）闡述了改進的PCA-SIFT算法的原理，改變了生成描述子的方式。

（2）通過實驗實現了PCA-SIFT算法，并通過ORL人臉數據庫的人臉數據驗證了PCA-SIFT算法的優越性。在研究過程中，本文選擇了將維度降為20進行對比研究。比較了SIFT算法和PCA-SIFT算法下不同維度的運行情況。從而可以發現不同的維度對應的準確率不同。維度越低，準確率就越低。

本文在多姿態人臉識別中對SIFT算法進行了研究，通過對其優化和改進取得了一定的進展，但在研究過程中也遇到了一些瓶頸和問題。如實驗數據樣本的選取，維度的選取如何界定等。特別是如何提高降維之后的準確率，這在后期的工作中仍需進一步的探討和研究。