基于直接鄰域保護嵌入的人臉識別

孫慶娟

（聊城大學 數學科學學院， 山東 聊城 252059）

1 引言

人臉識別是利用計算機分析人臉圖像，從中提取有用的識別信息來辨別身份的一門技術。近年來，相繼提出了許多種人臉識別方法，這些方法面臨的一個主要問題就是圖像維數太大，解決這一問題的方法就是進行維數約簡，即降維。現已有許多可行的線性降維方法，包括主成分分析（PCA）[1]71-86，線性判別分析（LDA）[2]711-720等。這兩種方法都只考慮了人臉圖像的全局結構，而忽略了局部結構，但在許多實際的分類問題中，特別是采用最近鄰方法進行分類時，局部結構比全局結構能提供更加重要的信息。NPE算法[3]208-213是一種用于人臉表示和識別的線性降維方法，它主要是對局部線性嵌入（LLE）算法[4]2323-2326的線性逼近，不但繼承了LLE的優點，而且充分考慮了人臉圖像的流形結構。

NPE在處理高維數據時同樣面臨著矩陣奇異性問題，因此本文提出一種直接算法，并在ORL人臉庫上通過實驗證明了該方法的有效性。

2 鄰域保護嵌入(NPE)算法

NPE算法是一種用于人臉表示和識別的線性降維方法。給定一組人臉數據集{x1,… ,xn} ?Rm，假設X= [x1,… ,xn]，文獻[3]給出的NPE 算法的具體步驟如下：

（1） 構造鄰域圖：設G為有n個節點的圖，第i個節點與人臉圖xi相對應。如果xi是xj的k近鄰，或xj是 xi的k近鄰，則在它們之間連上一條邊。

（2） 選擇權值：設N表示權值矩陣，其每條邊上的權值為Nij，規定沒有邊連接的Nij為零。利用下面的準則函數求這些權值：

約束條件

（3） 考慮一種極限情況，將n維空間的數據投影到一條直線上，其映射為 y=(y,…,y)T。由于在這條1n直線上的每一個數據都可表示為其鄰域點的線性組合，因此我們可以最小化下面的重構誤差函數：

另外，假設投影是線性的，即 yT= wTX ，經過簡單的代數變換，代價函數變為 Φ(y ) =wTXMXTw，其中M=(I ?N)T(I ?N)，I= diag(1,…,1)。為了排除尺度因子的影響，增加約束 yTy=1?wTXXTw =1，最終優化問題變為

實際上這是一個關于求解下列廣義特征向量的問題：

3 直接鄰域保護嵌入算法（DNPE）

一般地，廣義特征向量的求解還存在著一個問題，就是X的行向量可能是線性相關的，從而導致 XXT奇異。在線性代數中，求解廣義特征值問題的一種常用方法是采用同時對角化的思想。由于矩陣M是對稱半正定的，所以矩陣 XMXT和 XXT都是對稱半正定的。該方法的主要原理是通過對角化 XXT來去掉它的零空間，再通過投影和對角化 XMXT來尋找投影向量。

引理：鄰域保護嵌入方法中， XXT的零空間不包含任何判別信息。

算法試圖尋找一個投影矩陣W能同時對角化 XMXT和 XXT，使得 WXXTW =I ， WXMXTWT=Λ，其中Λ是升序排列的對角矩陣。為了降低維數到d(d＜＜n)，簡單挑選W的前d行，其對應Λ中最小的d個對角元素[5]。

具體步驟如下：

（1）對角化 XXT：尋找正交矩陣 V (VVT=I )，使得 VXXTVT=Λ1，其中Λ1是降序排列的對角矩陣，可以通過傳統的特征值分解方法來得到，即V的每一行是 XXT的一個特征向量，Λ1包含了其所有的特征值。因為XXT可能是奇異的，所以其一些特征值可能為零（或接近于零），因此需要去掉這些特征值和特征向量（因為這些方向的投影對鄰域保護嵌入來說不包含任何有用的判別信息）。

設Y∈ Rm×n（n是特征空間的維數）是V的前m行，則 YXXTYT= Di＞0，其中Di為對應于非零特征值的m×n對角矩陣。

（3） 計算投影矩陣W：令 W= U1Z，則W滿足（1）式。對于一個給定的n維的輸入x，它在其特征空間的投影向量為y=Wx，此時y的維數降為d（d＜＜n）。

4 實驗和結果分析

為驗證上述分析結果，我們對PCA，PCA+LDA，NPE和本文算法（DNPE）分別在標準ORL人臉圖像庫上進行了比較試驗。為了結果的客觀性和可比性，采用了統一的圖像預處理和最近鄰分類器，距離測量使用歐氏距離。ORL人臉圖像庫包括40個人，每個人10幅圖像。在ORL庫中隨機抽取每人5幅圖像作為訓練集，其余作為測試集，并運行20次獲得平均正確識別率。PCA，PCA+LDA，NPE和DNPE的平均識別率分別為85.9%，92.2%，92.7%和94.1%。

從上述結果可以看出，本文算法對高維的圖像數據來說是一個較優的求解算法，取得了比其他算法更高的識別率。一方面說明考慮局部流形結構的降維方法能更有效地得到數據鄰域的分布特性，同時也說明了通過同時對角化的投影變換的確能提高識別率。

5 結束語

本文提出一種新的直接鄰域保護嵌入算法并將其應用于人臉識別，該算法在傳統NPE算法的基礎上進行了改進，與其他算法相比，取得了較高的識別率。

[1]M.Turk, A.Pentland, Eigenfaces for recognition[J]. Journal of Cognitive Neuroscience, 1992, (3).

[2]P.Belhumeur, J.Hespanha, D.kriegman, Eigenfaces vs. Fisherfaces: recognition using class specific linear projection[J]. IEEE Trans. Pattern Anal. Mach. Intell, 1997, (19).

[3]X.He, D.Cai, S.Yan et a1.Neighborhood Preserving Embedding[J]. IEEE International Conference on Computer Vision. 2005,(1).

[4]Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding[J]. Science, 2000, 290(5 500).

[5]K.Fukunaga. Introduction to Statistical Pattern Recogniton: 2nd Edition[M]. New York: Academic Press, 1990.