基于鑒別混合結(jié)構(gòu)保持投影的人臉識別算法

王成國，胡西川

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

0 引言

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

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

1 相關(guān)工作

（1）NPE算法

NPE可以認(rèn)為是LEE算法的線性化改進，它是一種線性化降維方法。NPE的目標(biāo)是保持投影空間中數(shù)據(jù)的局部鄰域結(jié)構(gòu)，NPE使用局部最小二乘法來計算親和度矩陣。算法步驟如下：

首先構(gòu)造一個鄰近圖，對應(yīng)鄰近圖設(shè)置重構(gòu)權(quán)重系數(shù)矩N，Nij滿足：

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

對于非零的Nij的大小可以通過最小化如下?lián)p失函數(shù)來計算：

上式進一步可寫為：

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

最優(yōu)投影w是通過最小化如下?lián)p失函數(shù)獲得的：

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

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

（2）SPP算法

SPP同NPE一樣也是一種線性降維方法，SPP在稀疏表示[9]原理的基礎(chǔ)上，通過把原始空間中的數(shù)據(jù)投影到投影空間，同時保持?jǐn)?shù)據(jù)的稀疏結(jié)構(gòu)關(guān)系不變，從而達到降維的作用。

SPP的計算步驟如下：

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

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

然后，稀疏表示系數(shù)矩陣i表示為：

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

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

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

（3）SNPP算法

該算法根據(jù)NPE算法和SPP算法的相似性，通過深度整合NPE和SPP的結(jié)構(gòu)到一個混合結(jié)構(gòu)中，提出了一種新線性降維方法，此方法既保持?jǐn)?shù)據(jù)的稀疏性，又保持了數(shù)據(jù)的近鄰關(guān)系。在高維空間或者低維空間都有較好的性能表現(xiàn)。

本算法的目標(biāo)函數(shù)是：

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

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

求解方法上式可得最優(yōu)解W。

（4）MMMC算法

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

進一步可獲得如下形式：

將上式可轉(zhuǎn)化為求解最大特征值問題，從而求得最優(yōu)投影W。

2 基于鑒別混合結(jié)構(gòu)保持投影的線性降維算法（DSNPP）

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

算法步驟如下：

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

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

或者是：

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

第三步，獲得復(fù)合結(jié)構(gòu)的投影矩陣Z，其中：

第四步，構(gòu)造改進的SNPP目標(biāo)函數(shù)：

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

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

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

最后：構(gòu)造最終的目標(biāo)函數(shù)：

以上優(yōu)化問題可以轉(zhuǎn)化為如下：

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

從而可得到：

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

3 實驗

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

（1）AR人臉數(shù)據(jù)庫的實驗

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

圖1 AR人臉數(shù)據(jù)庫的部分人臉圖像

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

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

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

圖2 不同維度下照片識別準(zhǔn)確率(AR數(shù)據(jù)庫)

（2）PIE人臉數(shù)據(jù)庫上的實驗

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

圖3 PIE人臉數(shù)據(jù)庫的部分人臉圖像

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

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

4 結(jié)語

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