王成國(guó)，胡西川

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

0 引言

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

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

1 相關(guān)工作

（1）NPE算法

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

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

如果xj不是xi的近鄰點(diǎn)，則Nij=0，否則Nij≠0。

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

上式進(jìn)一步可寫(xiě)為：

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

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

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

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

（2）SPP算法

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

SPP的計(jì)算步驟如下：

首先，對(duì)于每一個(gè)xi的稀疏表示向量si可以通過(guò)求解如下l1正則項(xiàng)最小問(wèn)題來(lái)求解：

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

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

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

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

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

（3）SNPP算法

該算法根據(jù)NPE算法和SPP算法的相似性，通過(guò)深度整合NPE和SPP的結(jié)構(gòu)到一個(gè)混合結(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重要性的兩個(gè)參數(shù)。α β取值范圍是[-1,1]。

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

（4）MMMC算法

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

進(jìn)一步可獲得如下形式：

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

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

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

算法步驟如下：

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

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

或者是：

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

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

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

對(duì)上式求解廣義特征值問(wèn)題可得到：

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

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

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

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

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

從而可得到：

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

3 實(shí)驗(yàn)

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

（1）AR人臉數(shù)據(jù)庫(kù)的實(shí)驗(yàn)

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

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

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

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

表1 算法在AR人臉庫(kù)上的最高識(shí)別率

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

（2）PIE人臉數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)

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

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

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

表2 算法在PIE人臉庫(kù)上的最高識(shí)別率

4 結(jié)語(yǔ)

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