基于分塊非負矩陣分解人臉識別增量學習
2009-01-01 00:00:00潘彬彬陳文勝徐晨
計算機應用研究 2009年1期
(深圳大學 數學與計算科學學院，智能計算科學研究所， 廣東 深圳 518060)
摘 要：非負矩陣分解(NMF)算法可以提取圖像的局部特征，然而NMF算法有兩個主要缺點：a）當矩陣維數較大時，NMF算法非常耗時；b）當增加新的訓練樣本或類別時，NMF算法必須進行重復學習。為克服NMF算法這些缺點，提出了一種新的分塊NMF算法(BNMF)。特別地，該方法還可用于增量學習。通過在FERET和CMU PIE人臉數據庫上進行實驗，結果表明該算法均優于NMF和PCA算法。
關鍵詞：非負矩陣分解； 局部特征提取； 人臉識別； 增量學習
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)01011704
Incremental learning of face recognitionbased on block nonnegative matrix factorization
PAN Binbin， CHEN Wensheng， XU Chen
(Institute of Intelligent Computing Science， CollegeofMathematics Computational Science， Shenzhen University， Shenzhen Guangdong 518060， China )
Abstract:Nonnegative matrix factorization (NMF) can extract local features of images. However， NMF method has two main drawbacks. One shortcoming is that it is very timeconsuming to deal with large matrices. The other is that it must implement repetitive learning， when the training samples or classes are incremental. In order to overcome these two limitations， this paper presented a novel block NMF (BNMF) method. In particular， it could be applied to incremental learning. Two face databases， namely FERET and CMU PIE face databases， were selected for evaluation. Comparing with NMF and PCA schemes， the proposed method gives superior results.
Key words：nonnegative matrix factorization; local feature extraction; face recognition; incremental learning
0 引言
人臉識別研究的關鍵是特征提取，有基于全局特征的提取，也有基于局部特征的提取。特征臉方法也稱為主元分析法[1]（PCA），是一種基于全局特征提取的人臉識別方法。PCA將主成分提取出來，減少了樣本間的冗余信息，達到了降維的目的。然而，特征臉方法有幾個缺點：a)如何選取主元仍然是個問題；b)當訓練樣本線性不可分時，特征臉方法的識別率很低；c)基于全局特征的PCA無法提取到局部特征。
非負矩陣分解(NMF)是在矩陣元素均為非負數的約束條件下的一種矩陣分解方法。NMF是一種局部特征提取方法，其將人臉表示成基圖像的線性組合，而基圖像代表了眼、鼻子、嘴等人臉的局部特征，符合人類思維局部構成整體的概念。這種方法最早由Lee等人[2，3]提出并成功應用于基于物體局部特征的識別，之后研究人員對NMF方法進行了更深入的研究。Li等人[4]提出了局部非負矩陣分解（LNMF），得到的局部特征更加明顯，并提高了識別率。 Guillamet等人[5]對NMF的基矩陣W作出了改進，引入了加權NMF算法。除了對基矩陣W進行限制，文獻[6~9]針對系數矩陣H進行了研究。文獻[10~11]對基矩陣W和系數矩陣H的稀疏性進行了研究；除此之外，還有對W和H的迭代式進行研究的，如文獻[12，13]在迭代式中引入投影梯度方法。
目前基于NMF的所有算法大多存在兩方面的缺點，即分解速度慢以及對訓練樣本或類別的增加都必須重復學習，這大大限制了NMF在實際中的應用。本文提出的分塊非負矩陣分解(BNMF)方法很好地克服了以上兩個缺點。BNMF算法具有許多好的性質，如系數矩陣H具有很好的稀疏性、不同類的系數列向量具有正交性、具有較低的計算復雜度。特別地，該方法可以用于增量學習。
1 非負矩陣分解算法
設訓練樣本集合{v1，v2，…，vn}。其中vi為列向量，n為訓練樣本個數。將所有訓練樣本組成矩陣V=[v1，v2，…，vn]，NMF的思想是將V近似分解為兩個矩陣的乘積：
Vm×n≈V⌒m×n=Wm×rHr×n(1)
其中：Wm×r和Hr×n都是非負矩陣；r為基向量的個數，一般選擇r滿足(m+n)r＜mn，即減少了數據存儲空間。W的r列稱為基圖像，H的每一列稱為系數。
V與V⌒之間的誤差定義為[2]
D(V‖V⌒=WH)=∑i，j(Vi，j log Vi，j/V⌒i，j-Vi，j+V⌒i，j)(2)
NMF要解決如下最優化問題：
min D(V‖V⌒=WH)，
s.t. W≥0，H≥0，∑iWi，k=1，k(3)
由式(3)可得到以下求解W和H的迭代式[2]:
Wi，j←Wi，j∑k(Vik/(WH)ik)Hjk(4)
Wij←Wij/∑kWkj(5)
Hij←Hij∑kWki(Vkj/(WH)kj)(6)
文獻[3]證明了上述迭代算法是收斂的。
2 分塊非負矩陣分解
2.1 算法提出
人臉數據庫的數據很多，每張人臉的維數又很大，因此得到的待分解矩陣V的維數很大，這樣使得NMF的分解速度很慢。另外，當人臉數據庫的某一類加入新的訓練樣本或加入新的一類時，NMF需要進行重新分解，不利于實際應用。為了克服NMF的以上缺點，運用分塊的思想對NMF算法進行修改。將大矩陣按每類進行分塊，即同一類的訓練樣本形成一塊小矩陣；然后對每塊小矩陣進行分解；最后再將分解后的小矩陣合成大矩陣。
設Vm×n=[V1，V2，…，Vc]。其中：Vi=[v(i)1，v(i)2，…，V(i)ni]；v(i)j為屬于第i類的訓練樣本；ni為第i類的訓練樣本數；c為類別數，i=1，2，…，c； j=1，2，…，ni。
設每類所取的訓練樣本數相同，記為n0，則總的訓練樣本數n=cn0。對每個Vi進行NMF：
(Vi)m×n0≈NMF(Wi)m×r0(Hi)r0×n0；i=1，2，…，c(7)
則有
[V1 V2 … Vc]≈[W1 W2 Wc]H1H2Hc(8)
若記Wm×r=[W1 W2 … Wc]，Hr×n=diag(H1，H2，…，Hc)。其中r=cr0，則由式(8)得到分塊非負矩陣分解Vm×n≈BNMFWm×rHr×n。由式(8)易見H中不同類的系數列向量是正交的，即消除了不同類之間的相關性。這表明BNMF算法可以很好地提取模式的分類特征。
2.2 系數矩陣H的稀疏性
本節討論BNMF算法中H的稀疏性。設向量h∈Rn，稀疏度函數sparseness:Rn→R。其中值域為[0，1]。稀疏度函數反映了向量的能量分布情況，能量分布越集中，稀疏度越高；反之，稀疏度越低。因此，當向量只有一個非零分量時，能量最集中，稀疏度為1；當向量的所有分量相等時，能量分布最均勻，稀疏度為0。
稀疏度函數可用向量的L1和L2范數來定義[10]：
sparseness(h)=(n-‖h‖1/‖h‖2)/（n-1）(9)
其中：n為向量h的維數。
定理 BNMF算法中系數矩陣H每一列hi的稀疏度有如下估計：
(cr0-r0)/(cr0-1)≤sparseness(hi)≤1(10)
證明 設hi=(0，…，0，h(j)i1，…，h(j)ir0，0，…，0）(11)
其中：hi屬于第j類，hi∈Rr。設另一向量
hi=(h(j)i1，…，h(j)ir0)∈Rr0(12)
易知‖hi‖1=‖hi‖1，‖hi‖2=‖hi‖2。而
1≤‖h‖1/‖h‖2≤r0(13)
所以
(r-r0)/(r-1)≤(r-‖hi‖1/‖hi‖2)/(r-1)≤1(14)
又r=cr0，故
(cr0-r0)/(cr0-1)≤sparseness(hi)≤1(15)
證畢。
在實驗中取r0=4。對于FERET數據庫，c=120，可得0.952 2≤sparseness(hi)≤1；對于CMU PIE數據庫，c=68，可得0.935 5≤sparseness(hi)≤1。所以，BNMF算法的系數矩陣H每一列的稀疏度是很高的。
2.3 計算復雜度
本節討論BNMF和NMF的計算復雜度。
先討論NMF的計算量。設Vm×n≈Wm×rHr×n，H的迭代式為
Haμ←（Haμ/∑mi=1Wia)∑mi=1(WiaViμ/∑rk=1WikHkμ）
(16)
由于乘法運算比加法運算慢很多，只需討論乘法運算的次數即可。上述迭代法進行的乘法次數為mr+2m+2次，則H迭代一次所需的乘法次數約為nr(mr+2m+2)。
W的迭代式為
Wia←(Wia/∑nμ=1Wia)∑nμ=1(HaμViμ/∑rk=1WikHkμ）(17)
上述迭代法進行的乘法次數約為nr+2n+2次，則W迭代一次所需的乘法次數約為mr(nr+2n+2)。
所以NMF迭代一次所需的乘法運算為
TNMF=2mnr2+4mnr+2mr+2nr(18)
下面再來討論分塊的NMF的計算量。設
(Vi)m×n0≈(Wi)m×r0(Hi)r0×n0；i=1，2，…，c(19)
由上面的討論可知，對于每一個Vi，迭代一次所需的乘法運算為
2mn0r20+4mn0r0+2mr0+2n0r0(20)
一共進行c次，總共需要
TBNMF=(2mn0r20+4mn0r0+2mr0+2n0r0)c=
（2mnr2/c2）+（4mnr/c）+（2nr/c）+（2mr）(21)
比較式(18)和(21)可以看出，BNMF的計算量比NMF的計算量要小很多。
2.4 增量學習
當增加新的訓練樣本或類別時，現有的所有基于NMF的算法必須進行重復學習。而BNMF算法可以進行增量學習，這樣可大大縮短訓練時間。
a)當第i類Vi中增加一個新訓練樣本x0時，令V⌒i=[Vi，x0]，訓練樣本矩陣變為
V⌒=[V1 … V⌒i … Vc](22)
此時Vk≈NMFWkHk(k≠i)無須重復計算，只需計算V⌒i≈NMFW⌒iH⌒i即可。從而得到新的分塊非負矩陣分解
V⌒≈BNMFW⌒H⌒=[W1 … W⌒i … Wc]H1 H⌒i Hc(23)
b)當增加一新的類別Vc+1時，新的訓練樣本矩陣為
V⌒=[V1 … Vc … Vc+1](24)
同樣，Vk≈NMFWkHk(k=1，2，…，c)無須再計算，只需計算Vc+1=Wc+1Hc+1即可。從而可得新的分塊矩陣分解
V⌒≈BNMFW⌒H⌒=[W1 … Wc … Wc+1]H1 Hc Hc+1(25)
2.5 算法設計
本節具體給出了BNMF算法。BNMF算法應用于人臉識別分兩個階段。
1)訓練階段
a)設每個訓練樣本的維數為m，總共有c類，每類n0個訓練樣本。將同一類的訓練樣本形成小矩陣(Vi)m×n0，i=1，2，…，c。
b)對每個(Vi)m×n0進行NMF：
(Vi)m×n0≈NMF(Wi)m×r0(Hi)r0×n0；i=1，2，…，c(26)
同時得到基矩陣Wi和系數矩陣Hi。
c）將得到的所有基矩陣Wi組成Wm×r=[W1 W2 … Wc]。所有Hi組成Hr×n=diag(H1，H2，…，Hc)。其中r=cr0，n=cn0。則得到BNMF算法
Vm×n≈BNMFWm×rHr×n(27)
如果某類有新的訓練樣本或新的類別加入時，不需要全部重復訓練，只需由2.4節的增量學習方法可得新的分解：V⌒≈BNMFW⌒H⌒。
2）識別階段
a）特征提取。對于人臉向量，投影到特征空間span{W1，W2，…，Wr}的坐標為
=W+(28)
其中W+為W的MoorePenrose逆。
b)最近鄰分類。計算測試樣本坐標與每類均值坐標的距離d(，hi)。其中hi=W+vi。vi為第i類樣本均值，i=1，2，…，c。記j=arg mini d(，hi)，則歸為第j類。
3 實驗結果
本章給出BNMF、NMF和PCA方法在FERET人臉庫和CMU PIE人臉庫上的實驗結果。在實驗中，所有分辨率為112×92的原人臉圖像經兩次D4小波變換得到分辨率為30×25的人臉圖像，降維后的人臉圖像用來作訓練和測試。如果小波變換后的圖像像素值出現負值，則進行簡單的平移，保證所有圖像像素值非負。另外，BNMF和NMF算法的所有分解迭代次數均為1 000次。
3.1 人臉數據庫
對于FERET人臉數據庫，選取120人，每人6張像。其中包含了表情、光照、姿態和年齡的變化。圖1給出了FERET數據庫上同一人的6幅人臉圖像。
CMU PIE數據庫含有68人，每人56張照片，其中每人包括了13種姿態、43種光照條件和4種表情下的人臉圖像。圖2給出了CMU PIE數據庫中來自同一人的部分人臉圖像。
3.2 使用FERET人臉數據庫
給出BNMF方法與NMF、PCA方法在FERET人臉庫上的測試結果。
3.2.1 原圖重構
圖3列出了各種算法對原圖的重構。與原圖對比可以發現，PCA和NMF重構后的圖像與原圖差異較大，且基于局部特征提取的NMF在重構后邊緣較模糊，但眼、鼻和嘴等細節部分均較好地重構了出來；BNMF重構后的圖像與原圖差異最小。
3.2.2 FERET數據庫上非增量學習
對于FERET人臉庫，每人隨機選取n(n=2，3，4，5)幅像作訓練，其余(6-n)幅圖像作測試。在NMF和BNMF算法中，分別選取r=120和r0=4。實驗連續進行10次，記錄10次平均識別率和平均時間。各方法在不同訓練樣本數下的識別率由表1和圖4給出。可以看出，以2幅圖像作訓練時，BNMF、NMF和PCA方法的識別率分別為66.07%、64.44% 和34.33% 。隨著訓練樣本數的增加，三種算法的識別率均有提高。當以9幅圖像作訓練時，BNMF、NMF和PCA方法的識別率分別提高到81.67%、80.25%和37.58%。另外，表2給出了BNMF和NMF實驗所耗平均時間比較。實驗結果表明本文的方法具有最好的識別率和計算效率；PCA的性能最差。
3.2.3 FERET人臉數據庫上類增量學習
給出BNMF和NMF算法在FERET數據上的類增量學習實驗結果。FERET人臉庫中選取119人，每人隨機取3幅圖像作訓練，其余3幅作測試。當增加新的一類組成120個類時，NMF算法需要進行重復學習，即120人中，每人隨機取3幅圖像作訓練，其余3幅作測試。而BNMF算法僅需對新增加的類進行增量學習即可。實驗重復10次，記錄10次平均識別率和平均時間。其結果分別由表3、圖5和表4給出。
由實驗結果可知，對119類進行實驗時，BNMF要比NMF少耗16 s左右，而當增加新的一類時，BNMF增量學習僅需0.86 s，遠遠低于NMF的74.58 s。在識別率方面，BNMF的增量學習方法同樣能夠保持比NMF高的識別率。
3.3 使用CMU PIE人臉數據庫
給出BNMF方法與NMF、PCA方法在CMU PIE人臉庫上的實驗結果。
3.3.1 CMU PIE數據庫上非增量學習
CMU PIE數據庫中，每人隨機選取n(n=7，14，21，28)幅圖像作訓練，其余(56-n)幅圖像作測試。在NMF和BNMF中分別選取r=68和r0=4。實驗重復10次，BNMF、NMF和PCA的平均識別率和平均時間分別由表5和6給出，圖6給出了實驗結果的直觀比較。實驗結果表明BNMF算法在非增量學習中具有最好的識別率和計算效率。
3.3.2 CMU PIE數據庫上類增量學習
CMU PIE數據庫中選取67人，每人隨機取7幅圖像作訓練，其余49幅作測試。當增加新的一類組成68個類時，NMF算法需要進行重復學習，即68人中，每人隨機取7幅圖像作訓練，其余49幅作測試。BNMF算法僅需對新增加的類進行增量學習即可。實驗重復10次，記錄10次平均識別率和平均時間，其結果分別由表7和8給出，圖7給出了實驗結果的直觀比較。
實驗結果表明，對67人，BNMF要比NMF少耗時17 s左右；增加新的一類時，BNMF的增量學習僅需1.36 s，遠遠低于NMF的79.58 s。另外，BNMF的類增量學習方法同樣具有最高識別率。
3.3.3 CMU PIE數據庫上樣本增量學習
在CMU PIE數據庫68個人中，每人隨機選取7幅圖像進行訓練，其余的作測試。現只對第一個人分別增加7、14和21幅圖像進行訓練，其余人的訓練樣本數不變，仍為7幅。實驗重復10次，BNMF和NMF的平均識別率和平均時間分別由表9、圖8和表10給出。實驗結果表明本文方法具有最好的性能。
4 結束語
本文提出了分塊非負矩陣分解（BNMF）的增量學習算法，該算法克服了目前基于NMF算法的缺點。本文的方法不但各類之間的系數向量是正交的，即消除了不同類之間的相關性，而且系數矩陣是稀疏的，且具有較低的計算復雜度。通過在FERET和CMU PIE人臉數據庫上進行實驗，實驗結果表明BNMF算法的性能均優于NMF和PCA算法。
致謝：感謝US Army Research Laboratory提供的FERET人臉數據庫和Carnegie Mellon University提供的CMU PIE人臉數據庫。
參考文獻：
［1］TURK M， PENTLAND A. Eigenfaces for recognition[J]. Journal of Cognitive Neuroscience，1991，3(1): 7186.
[2]LEE D D， SEUNG H S. Learning the parts of objects by nonnegative matrix factorization[J]. Nature， 1999，401(6755):788791.
[3]LEE D D， SEUNG H S. Algorithms for nonnegative matrix factorization[C]//Proc of Neural Information Processing Systems. 2000:556562.
[4]LI S Z， HOU Xinwen， ZHANG Hongjiang， et al. Learning spatially localized， partsbased representation[C]//Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2001: 207212.
[5]GUILLAMET D， BRESSAN M， VITRID J. A weighted nonnegative matrix factorization for local representations[C]//Proc ofIEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2001:942947.
[6]WANG Y， JIAR Y， HU C， et al. Fisher nonnegative matrix factorization for learning local features[C]//Proc of the 6th Asian Conference on Computer Vision. 2004:2730.
[7]XUE Yun， TONG C S， CHEN Wensheng， et al. A modified nonnegative matrix factorization algorithm for face recognition[C]//Proc of the 18th International Conference on Pattern Recognition.Washington DC:IEEE Computer Society， 2006:495498.
[8]BUCIU I， PITAS I. A new sparse image representation algorithm applied to facial expression recognition[C]//Proc of the 14th IEEE Workshop on Machine Learning for Signal Processing. 2004:539548.
[9]KOTSIA I， ZAFEIRIOU S， PATAS I. A novel discriminant nonnegative matrix factorization algorithm with applications to facial image characterization problems[J]. IEEE Trans on Information Forensics and Security，2007，2(3):588595.
[10]HOYER P O. Nonnegative matrix factorization with sparseness constraints[J]. Journal of Machine Learning Research， 2004，5(11):14571469.
[11]HOYER P O. Nonnegative sparse coding[C]//Proc ofthe 12th IEEE Workshop on Neural Networks for Signal Processing. 2002:557565.
[12]LIN C J. Projected gradient methods for nonnegative matrix factorization[J]. Neural Computation， 2007，19(10):27562779.
[13]LIN C J. On the convergence of multiplicative update algorithms for nonnegative matrix factorization[J]. IEEE Trans on Neural Networks， 2007，18(6):15891596.
