基于鑒別混合結構保持投影的人臉識別算法

王成國，胡西川

（上海海事大學信息工程學院，上海 201306）

0 引言

人臉識別近些年來一直是研究的熱門領域，由于人臉圖像處在一個高維度的空間，避免“維數災難”，發現數據真實存在的子空間，維度的簡約顯得非常重要。目前有大量的降維算法已經被提出，例如主成分分析（PCA）[3]、線性判別分析（LDA）[4]等。這些方法屬于線性降維方法。由于這些線性方法無法發現復雜非線性數據的固有結構，近些年來，流行學習方法作為可以處理非線性數據的方法被大量的研究。其中具有代表性的方法有局部線性嵌入（LLE）[5]、拉普拉斯特征映射（LE）[6]算法，這些算法可以將數據的結構從原始高維空間投影到低維空間后得到最大的保持，然而這些方法無法給定一個顯示的映射，對于增量數據無法處理。同時實際生產數據中數據沒有嚴格的流形結構，使算法收到局限性。作為LLE的線性化方法鄰域保持嵌入（NPE）[7]算法和LE算法的線性化方法局部保持投影（LPP）算法克服了這些缺點并得到廣發的應用。但這兩種方法也有缺點，他們對鄰域的大小和邊權值參仍然無法確定。最近Qiao等人提出了根據稀疏表示理論提出了稀疏保持嵌（SPP）[8]算法，該算法將數據投影到低維空間的同時保持數據之間的稀疏表示性，此算法可以自動的選擇用哪些其他數據來線性表示待表示數據，一定程度上克服了NPE和LPP的需要確定鄰域參數和邊權值的缺點。

鄰域表示和稀疏表示各有其優缺點，對于低維數據來說，鄰域表示比稀疏表示更加重要，而對于高維數據來說稀疏表示更加有用[1]。可以結合兩者的優點來表示數據，使其更加準確地反映數據的特征。Zhang等人通過融合NPE算法和SPP算法中近鄰表示和稀疏表示提出了一種混合表示結構，充分地利用了數據的近鄰結構和稀疏結構，在降維投影方面表現出優勢。本文將數據的鑒別信息加入到混合結構保持投影算法中，再結合改進的最大余量準則，將充分利用數據的類別信息，從而在獲得的投影空間中更容易將數據進行分類。

1 相關工作

（1）NPE算法

NPE可以認為是LEE算法的線性化改進，它是一種線性化降維方法。NPE的目標是保持投影空間中數據的局部鄰域結構，NPE使用局部最小二乘法來計算親和度矩陣。算法步驟如下：

首先構造一個鄰近圖，對應鄰近圖設置重構權重系數矩N，Nij滿足：

如果xj不是xi的近鄰點，則Nij=0，否則Nij≠0。

對于非零的Nij的大小可以通過最小化如下損失函數來計算：

上式進一步可寫為：

其中：N=[n1,n2,...,nn]。

最優投影w是通過最小化如下損失函數獲得的：

其中 N?ij是（1）式的最優解。進一步化簡可得：

求解上式廣義特征向量可得投影矩陣W。

（2）SPP算法

SPP同NPE一樣也是一種線性降維方法，SPP在稀疏表示[9]原理的基礎上，通過把原始空間中的數據投影到投影空間，同時保持數據的稀疏結構關系不變，從而達到降維的作用。

SPP的計算步驟如下：

首先，對于每一個xi的稀疏表示向量si可以通過求解如下l1正則項最小問題來求解：

或者考慮噪音的情況下變化為如下：

然后，稀疏表示系數矩陣i表示為：

最后，我們可以通過優化如下問題來獲得最優的投影向量w：

其中：Sβ=S+ST-STS。

求解上式獲得投影矩陣W。

（3）SNPP算法

該算法根據NPE算法和SPP算法的相似性，通過深度整合NPE和SPP的結構到一個混合結構中，提出了一種新線性降維方法，此方法既保持數據的稀疏性，又保持了數據的近鄰關系。在高維空間或者低維空間都有較好的性能表現。

本算法的目標函數是：

其中 zi=αni+βsi，ni是（2）式鄰域表示系數向量，si是（7）式稀疏表示系數向量。

α和 β是反映s和w重要性的兩個參數。α β取值范圍是[-1,1]。

求解方法上式可得最優解W。

（4）MMMC算法

MMMC由Song等人提出，他們將最大間隔準則（MMC）算法中類內散度和類間散度的差改為商的形式，這樣就避免了在傳統方法中發生的小樣本問題，從而更有利于分類。MMMC函數定義如下:

進一步可獲得如下形式：

將上式可轉化為求解最大特征值問題，從而求得最優投影W。

2 基于鑒別混合結構保持投影的線性降維算法（DSNPP）

本文針對SNPP算法作為一種無監督降維方法，沒有充分利用類別鑒別信息的缺點，通過將數據的近鄰性和稀疏性加上鑒別信息，以及結合最大余量原則（MMMC）充分數據的鑒別信息，提出了鑒別混合結構保持投影的線性降維算法（DSNPP）的有監督的降維方法，增強的降維后數據的分類效果。

算法步驟如下：

第一步，用鑒別鄰域保持嵌入來替代鄰域保持嵌入算法來獲得鄰域保持系數矩陣N。首先構造鄰域圖時，加入類別鑒別信息。先選擇與xi屬于同一類別的k個近鄰點，再選擇不同類的k個近鄰點。設置權值矩陣時，與xi不相近鄰的點的邊權重設置為0；在與xi相近鄰的點的邊權重分兩種情況，若與xi屬于同一類別則權重提高為(1+β)nij(β>0)，否則，如不是同一類則保持nij不變，獲得鄰域表示系數矩陣N=[n1,n2,…,nn]，來替代（2）式的鄰域表示矩陣。

第二步，獲得將鑒別信息加入到稀疏表示后的稀疏表示系數矩陣S。將（5）、（6）式加入判別信息修改為如下：

或者是：

由此得到的稀疏表示矩陣S=[s1,s2,...,sn]，來替代（7）式獲得的稀疏表示矩陣。

第三步，獲得復合結構的投影矩陣Z，其中：

第四步，構造改進的SNPP目標函數：

對上式求解廣義特征值問題可得到：

增加約束：wTXXTw=1，避免解的退化。

第五步，我們希望投影矩陣滿足最大余量準則，如下有：

最后：構造最終的目標函數：

以上優化問題可以轉化為如下：

利用拉格朗日乘子法對上式求解得：

從而可得到：

求解上式廣義特征值特征向量從而可以求得最優解W。

3 實驗

為了驗證DSNPP算法的有效性，分別在AR、PIE人臉數據庫上將 PCA、NPE、SPP、SNPP、DSNPP 算法進行實驗對比。本文隨機選擇圖像，并重復實驗10次，平均值作為最后的輸出結果。經實驗可知，參數μ和c取值對實驗結果無影響，其中固定參數 μ=1，c=1。在降維投影空間我們使用KNN最近鄰算法最為最終分類算法，并取k=1。α和β的取值按照網格搜索，從-1到1，每步0.05增加。SNPP中鄰域大k的取值與NPE中k的取值相同，DSNPP中α和 β取值與SNPP中相同。ε=0.05。實驗前我們首先用PCA將原始數據降維為200維。

（1）AR人臉數據庫的實驗

該數據庫由126個人的超過4000張人臉圖像組成。對于每個人，有26張照片，其中13張照片沒有遮擋，另外13張照片有遮擋。實驗中使用AR人臉數據庫的一個子集，包含與100人（50名男性和50名女性）相對應的1400張面部圖像，其中每個人具有14個不同的具有照明改變和表情的圖像。這些圖像面的原始分辨率為165×120。這里，為了便于計算，我們將它們調整為32×32，并將灰度值重新調整為[0 1]。部分人臉圖像如圖1所示。

圖1 AR人臉數據庫的部分人臉圖像

參數選擇：NPE中k=23，α=0.95，β=0.1。實驗中每個人選取p張照片作為訓練集，剩余照片作為測試集。圖2顯示了p=3,5,8,10時，識別準確率隨時間的變化。

PCA、NPE、SPP、SNPP、DSNPP 算法在 AR 人臉數據庫上的最高設別率如表1所示

表1 算法在AR人臉庫上的最高識別率

圖2 不同維度下照片識別準確率(AR數據庫)

（2）PIE人臉數據庫上的實驗

PIE人臉數據庫含有68個人，每個人13種姿勢，43種光照條件，4種表情，共41368張圖片。本文選擇在所有光照條件和表情條件下的5個近似正向的姿態，每個人170張，總共11560張圖片。圖3顯示了PIE人臉庫中部分人臉圖像。表2顯示了算法在PIE數據庫上的最高識別率。

圖3 PIE人臉數據庫的部分人臉圖像

參數選擇：NPE中k=17，α=-0.15，β=0.6。實驗中每個人選取p張照片作為訓練集，剩余照片作為測試集。表2列出了p=30,35,40,45時，識別準確率隨時間的變化。

表2 算法在PIE人臉庫上的最高識別率

4 結語

本文在分析SNPP算法和MMMC算法的基礎上，利用判別信息，對SNPP算法進行了改進，提出了判別SNPP算法，給出了詳細的推導過程和具體步驟，并利用最近鄰分類器實現了分類。最后在兩個人臉數據庫上進行大量的仿真實驗，證明了該算法不論在低維還是高維數據中都有較高的識別準確率，是一種魯棒性比較好的算法。