孫慶娟

（聊城大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 山東 聊城 252059）

1 引言

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

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

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

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

（1） 構(gòu)造鄰域圖：設(shè)G為有n個節(jié)點(diǎn)的圖，第i個節(jié)點(diǎn)與人臉圖xi相對應(yīng)。如果xi是xj的k近鄰，或xj是 xi的k近鄰，則在它們之間連上一條邊。

（2） 選擇權(quán)值：設(shè)N表示權(quán)值矩陣，其每條邊上的權(quán)值為Nij，規(guī)定沒有邊連接的Nij為零。利用下面的準(zhǔn)則函數(shù)求這些權(quán)值：

約束條件

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

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

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

3 直接鄰域保護(hù)嵌入算法（DNPE）

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

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

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

具體步驟如下：

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

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

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

4 實驗和結(jié)果分析

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

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

5 結(jié)束語

本文提出一種新的直接鄰域保護(hù)嵌入算法并將其應(yīng)用于人臉識別，該算法在傳統(tǒng)NPE算法的基礎(chǔ)上進(jìn)行了改進(jìn)，與其他算法相比，取得了較高的識別率。

[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.