一種快速的基于稀疏表示的人臉識別算法

龍法寧， 楊夏妮

（玉林師范學(xué)院計算機(jī)科學(xué)與工程學(xué)院，廣西 玉林 537000）

一種快速的基于稀疏表示的人臉識別算法

龍法寧， 楊夏妮

（玉林師范學(xué)院計算機(jī)科學(xué)與工程學(xué)院，廣西 玉林 537000）

基于稀疏表示的人臉識別算法(SRC)識別率相當(dāng)高，但是當(dāng)使用l1范數(shù)求最優(yōu)的稀疏表示時，大大增加了算法的計算復(fù)雜度，矩陣隨著維度的增加，計算時間呈幾何級別上升，該文提出利用拉格朗日算法求解矩陣的逆的推導(dǎo)思路，用一種簡化的偽逆求解方法來代替l1范數(shù)的計算，可將運(yùn)算量較高的矩陣求逆運(yùn)算轉(zhuǎn)變?yōu)檩p量級向量矩陣運(yùn)算，基于AR人臉庫的實驗證明，維度高的時候識別率高達(dá)97%，同時，計算復(fù)雜度和開銷比SRC算法大幅度降低95%。

稀疏編碼；分類方法；人臉識別；小波變換；快速算法

模式識別領(lǐng)域，人臉識別的研究相當(dāng)廣泛，各種算法層出不窮。特別在近兩三年對壓縮感知技術(shù)研究浪潮下，Wright等[1]把稀疏表示和人臉識別算法結(jié)合起來，獲得了相當(dāng)高的識別率，基本方法是把所有人臉樣本的集合看作訓(xùn)練集并構(gòu)造為一個超完備字典，而測試的人臉樣本則可通過該超完備字典進(jìn)行稀疏表示。這個表示不但是稀疏的，而且僅包括所有訓(xùn)練樣本的小部分，對應(yīng)其他樣本的稀疏解理想狀態(tài)下應(yīng)該都為零，對于這個超完備字典而言，它是測試樣本最佳的稀疏表示。并且它可以通過l1范數(shù)最小化求得。因此尋找最佳的稀疏表示就能相對完美地區(qū)分出不同類別的訓(xùn)練樣本，但是隨之而來的就是計算機(jī)的運(yùn)算時間大幅度增加。

基于稀疏表示的 SRC人臉識別算法[2]通過構(gòu)造一個用作訓(xùn)練的超完備字典其中 Ai是第i類人臉數(shù)據(jù)的集合，由同類的n幅人臉圖像形成訓(xùn)練字典，每幅圖像有m個像素點(diǎn)作為矩陣 Ai的一列，n是訓(xùn)練數(shù)據(jù)的類別個數(shù)。假設(shè)b為第i類的一個測試樣本，則b可由A線性表示為：

其中λ是一個很小的常數(shù)，那么對測試樣本b的分類方法如下所示：

1 SRC算法時間開銷分析

通過SRC算法的介紹和分析，發(fā)現(xiàn)除了對字典A的降維以外，時間開銷主要集中在求解欠定方程組 y=Ax的最優(yōu)稀疏解。通常情況下，欠定線性方程是沒有唯一解的，由于最優(yōu)重構(gòu)信號的求解計算復(fù)雜度很高，所以大多數(shù)研究聚焦在尋找可接受復(fù)雜度下的近似解（次優(yōu)解）。求次優(yōu)解是把l0范數(shù)放寬到l1范數(shù)通過線性規(guī)劃求解的，但是l1范數(shù)求解的計算復(fù)雜度仍然很高。經(jīng)證明可知道l2范數(shù)是用來度量重構(gòu)誤差的，需通過l2范數(shù)最小化問題找近似解，用l2范數(shù)代替l0范數(shù)，雖然有一定的誤差，但是可以解決l0范數(shù)可能無解的問題，同時在識別率有小幅下降的情況下，計算時間有很大的下降?，F(xiàn)在的算法是求得的解更加精確，但是計算復(fù)雜度更高，為了克服這一缺點(diǎn)越來越多的快速l1-min算法被提出。例如同倫算法、迭代收縮閾值、近端梯度、增廣拉格朗日乘子和梯度投影算法等[3]。

快速l1-min算法各有優(yōu)點(diǎn)，在運(yùn)算速度和正確率兩方面，無論是那一種算法在任何條件下都不可能達(dá)到最好。實際的應(yīng)用當(dāng)中，必須充分考慮人臉數(shù)據(jù)的特點(diǎn)以及應(yīng)用環(huán)境，在運(yùn)算速度和正確率之間找到平衡點(diǎn)，以達(dá)到最好地使用效果。因此在對識別響應(yīng)速度比較高的情況下，即使損失很小的識別率，也需要解決求解l1-min時間代價過大的問題。

2 基于Gabor小波的表情特征提取

文獻(xiàn)[4]通過分析Gabor小波和稀疏表示的生物學(xué)背景和數(shù)學(xué)特性，提出一種基于Gabor小波和稀疏表示的人臉表情識別方法。采用Gabor小波變換對表情圖像進(jìn)行特征提取，建立訓(xùn)練樣本Gabor特征的超完備字典，通過稀疏表示模型優(yōu)化人臉表情圖像的特征向量，利用融合識別方法進(jìn)行多分類器融合識別分類。但是該方法的綜合識別率只有82.3%，并不是很理想。文獻(xiàn)[5]提出了一種結(jié)合Gabor小波特征和SRC算法的人臉識別方法，AR人臉庫的識別率在圖像降維到300維的時候是95%比SRC的87%提高了8%，而維度超過500維時，最高識別率達(dá)到了97.14%，依然比SRC的91.19%提高了6%，但是對Gabor特征降維后圖像數(shù)字字典的時間開銷O(n2)是通過列向量從8781降到917維，維數(shù)依然很高，同時求解欠定線性方程采用的方法和SRC算法一致，運(yùn)算量一致。

因此，本文依舊采用Gabor小波變換來提取表情圖像的初始特征，然后采用別的方法來降低求解線性方程組的計算時間，文獻(xiàn)[6]給出了第j個二維Gabor小波濾波器的公式定義：

式(4)中，σ是與小波頻率帶寬有關(guān)的常數(shù)，z= (x ,y)為空間位置坐標(biāo)，κ確定了Gabor內(nèi)核的方向和尺度。例如，在采用8個方向和5個尺度的采樣時，某人方向和尺度上的κ可以寫為其中為采樣尺度，為尺度標(biāo)號；為采樣方向，為方向標(biāo)號。Kmax為最大頻率，f是頻域中的內(nèi)核間隔因子。令參數(shù)可以獲得較好的小波表征和辨別效果。

對人臉圖像進(jìn)行Gabor小波變換，就是將人臉圖像和Gabor小波的核函數(shù)進(jìn)行卷積。人臉表情圖像像素點(diǎn)z=(x, y)處的Gabor小波特征值是通過式(4)的濾波器與圖像的灰度值ψ ( κ ,z)卷積計算得到：

設(shè) Jk(z)的幅值和相位分別為 Ak和 φkφk，則組合不同尺度和方向的 J(z)，構(gòu)成

k圖像在z位置處的Gabor特征矢量，因此每幅人臉圖像可以通過式(4)獲得小波處理后的新圖像，構(gòu)為新的訓(xùn)練字典。

由于Gabor特征具有良好的空間局部性和方向選擇性，而且對光照、姿態(tài)具有一定的魯棒性，因此在人臉識別中獲得了成功地應(yīng)用。設(shè)圖像的大小為m×n，通過40個濾波器得到Gabor特征的維數(shù)高達(dá)40×m×n，計算量很大，且由于Gabor特征在相鄰像素間是高度相關(guān)和冗余的，所以通常只需要稀疏的提取部分節(jié)點(diǎn)上的Gabor特征，因此可以把Gabor的特征提取和SRC算法結(jié)合起來。

3 快速稀疏分類算法

一般來說人臉數(shù)據(jù)都是可以使用稀疏的信號來表示。那么如果給定測試人臉b是稀疏的或者是可壓縮的，可以通過解如下形式的優(yōu)化問題而獲得稀疏解：

由于SRC算法要獲得良好的人臉識別率，希望求得的解是盡可能的稀疏，而求解l1范數(shù)的常用方法有貪婪算法、凸優(yōu)化算法等，無一例外，都是通過不斷的迭代計算來獲得最優(yōu)的稀疏解，花費(fèi)的時間代價相當(dāng)大。

既然測試人臉b可由A線性表示為 b= Ax，則如果求得 A-1則公式可以轉(zhuǎn)換為： x = A-1b ，令于是有：

由于 xTATb是一個數(shù)，而這個數(shù)的轉(zhuǎn)置是它的本身，因此有：

故式(7)可化為：

由式(9)得：

若x*是 s( x)的極小點(diǎn)，則必有 ▽ s( x )=0，則：ATAx = ATb 即 x =(ATA)-1ATb。

上述方程組的解法需要 ATA正定才能求得ATA的逆，實際問題并不能保證 ATA正定，因此遇到這種情況，修正方法是現(xiàn)在矩陣A對角線k

上的元素都加上同一個數(shù) μ ＞0，則上述方程變?yōu)椋?/p>

這樣做的目的是：即使 ATA是奇異的，μ是一個很小的數(shù)，但是只要將μ取得充分大，總能使(ATA+ μI)正定，從而 (ATA+μI )x=ATb 肯定是有解的。因此，式(11)的目的是通過最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配。從而可以簡便地求得未知的數(shù)據(jù)，并使得所求數(shù)據(jù)與實際數(shù)據(jù)之間誤差的平方和最小，從而可以粗略模擬l2范數(shù)的計算。

綜合上述討論，快速稀疏分類的算法描述的具體步驟如下：

假設(shè)在給定的訓(xùn)練集 B =[B1,B2,…,Bn]中有k類已經(jīng)標(biāo)記好的樣本，其中第i類中含有ni個樣本。每個人臉樣本對應(yīng)于矩陣中的一個列向量 Bi, m為人臉圖像的維數(shù)。

Step 1. 對人臉庫構(gòu)造訓(xùn)練樣本集B，然后對B進(jìn)行小波變換得到新的字典 A= Gabor(B)，同理對測試集也進(jìn)行小波變換。

Step 2.對訓(xùn)練樣本集A中的每一個列向量進(jìn)行PCA降維，同理也對測試集進(jìn)行PCA降維，以確保矩陣是正定的，并且每張人臉的維數(shù)需要比人臉的個數(shù)要小，即構(gòu)成欠定矩陣。

Step 3.對訓(xùn)練集和測試集的每一個列向量 b利用式(11)進(jìn)行不太精確的稀疏編碼，得到稀疏表示其中求逆 A-1并不采用求解l1范數(shù)的最小化算法，而采用向量矩陣的輕量級運(yùn)算其中I是單位矩陣，μ是一個很小的值， (ATA+ μI )-1可以通過求解矩陣偽逆獲得。

Step 4.對稀疏表示后的訓(xùn)練集和測試集采用SVM或SRC分類器進(jìn)行分類決策。

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

4.1 AR人臉庫識別率

在實驗中，采用AR人臉數(shù)據(jù)庫[7]，從數(shù)據(jù)庫中選出50個男性對象和50個女性對象組成數(shù)據(jù)庫子集。其中，每個對象選擇 14幅僅有光照、表情變化的圖像，其中來自第一時間拍攝的7幅人臉圖像作為訓(xùn)練集，另外的7幅人臉圖像作為測試集，那么，訓(xùn)練集和測試集各有700幅人臉圖像，一共是1400幅人臉圖像，如圖1所示。

圖1 AR無遮擋人臉庫

對 Gabor核函數(shù)中相關(guān)參數(shù)的取值為v=5,u =8，對一幅人臉圖像進(jìn)行5個尺度8個方向上的Gabor小波變換。SVM分類器采用LIBSVM工具包的多類別SVM分類器，分類函數(shù)的參數(shù)是(′-s 1 -t 3 -c 1.2 -g 1.2′)，分別對測試集和訓(xùn)練集的 1400幅圖片進(jìn)行小波變換以后通過PCA分別降維為54、120、300維后進(jìn)行訓(xùn)練學(xué)習(xí)和測試，實驗結(jié)果如表1所示，本文的方法(簡稱Gabor+FastSparse+SVM)。本文方法的識別率在維度超過300以后，就接近甚至超過了結(jié)合小波變換的SRC算法。從表2可以看到，當(dāng)維度到達(dá)500的時候，識別率最高可以達(dá)到97.14%以上，和文獻(xiàn)[5]所采用Gabor+SRC的最佳識別率基本一致，因此可以看到本文方法擁有相當(dāng)高的識別率。

表1 各種人臉識別算法對比(%)

表2 快速稀疏識別算法高維識別率和計算時間

4.2 算法時間開銷

在CPU為Intel Core2 Duo E 7300 ，頻率為2.66 GHz，內(nèi)存為4 G的臺式機(jī)電腦上，對以上算法進(jìn)行了時間統(tǒng)計，為了獲得高識別率，不管是SRC算法還是本文的方法，都需要對人臉庫進(jìn)行小波變換，其所花費(fèi)的時間需96.818965 s，因此下面只對排除小波變換所需的運(yùn)算時間以外的識別時間進(jìn)行統(tǒng)計對比，其中SRC算法采用L1_magic工具包求解稀疏信號重構(gòu)的凸優(yōu)化方法[8]。實驗結(jié)果如表3所示，本文的方法所耗費(fèi)的時間比SRC的算法減少了95%以上。

表3 運(yùn)算時間對比(s)

5 結(jié) 束 語

本文方法在保留小波變換特征提取的 SRC算法的高識別率的基礎(chǔ)上，大幅度地降低了識別時間。其原因是基于稀疏表示的SRC算法，為了保留高識別率，必須求解l1范數(shù)的最小最優(yōu)解，使稀疏解盡可能的最小化，因此迭代時間過長，而本文采用了輕量級固定公式運(yùn)算來代替求解l1范數(shù)，從而減少了大量的時間，在稀疏解不夠稀疏的情況下，選擇了采用 SVM分類方法而不是 SRC的分類方法，從而保留了較高的識別率，實驗證明，在沒有優(yōu)化SVM的核函數(shù)的基礎(chǔ)上，當(dāng)圖像降維后大于500維的時候，最大達(dá)到了97%的識別率，如果排除小波轉(zhuǎn)換訓(xùn)練字典和測試字典的時間，識別分類所減少的運(yùn)算時間達(dá)到95%以上，因此有較強(qiáng)的實用價值，下一步工作，如果采用類似圖片分塊的識別方法，相信還可以獲得更佳的識別率。

[1] Wright J, Ma Yi, Mairal J, Sapiro G, Huang T, Yan Shuicheng. Sparse representation for computer vision and pattern recognition [J]. Proceedings of the IEEE, 2010, 98(6): 1031-1044.

[2] Wright J, Yang A Y, Ganesh A, Sastry S S, Ma Y. Robust face recognition via sparse representation [J]. IEEE PAMI, 2009, 31(2): 210-227.

[3] 劉 杰, 李昆侖. 快速 L1范數(shù)最小化算法的性能分析和比較[J]. 電腦知識與技術(shù), 2011, 7(19): 4641-4643.

[4] 張 娟, 詹永照, 毛啟容, 鄒 翔. 基于 Gabor小波和稀疏表示的人臉表情識別[J]. 計算機(jī)工程, 2012, 38(6): 207-208.

[5] Yang Meng, Zhang Lei. Gabor feature based sparse representation for face recognition with Gabor occlusion dictionary [J]. Proc. European Conf. Computer Vision, 2010, 6(5-11): 448-461.

[6] Liu Chengjun, Wechsler H. Gabor feature based classification using the enhanced fisher linear discriminant model for face recognition [J]. IEEE IP, 2002, 11(4): 467-476.

[7] Martinez A, Benavente R. The AR face database [R]. CVC Tech. Report, 24. 1998.

[8] Kim S J, Koh K, Lustig M, Boyd S, Gorinevsky D. A interior-point method for large-scale l1-regularized least squares [J]. IEEE Journal on Selected Topics in Signal Processing, 2007, 1(4): 606-617.

A Fast Face Recognition Algorithm Based on Sparse Representation

Long Faning, Yang Xiani
(Computer Science Department, Yulin Normal University, Yulin Guangxi 537000, China)

As a recently proposed technique, sparse representation based classification (SRC) has been widely used for face recognition (FR). Sparse representation based SRC algorithm has a high recognition rate. While l1-minimization (l1-min) has recently been studied extensively in optimization, the high computational cost associated with the traditional algorithms has largely hindered their application to high-dimensional, large-scale problems. This paper devotes to analyze the working mechanism of SRC and discusses accelerated l1-min techniques using augmented Lagrangian methods, consequently, we propose a very simple yet much more efficient face classification scheme. The performance of the new algorithms is demonstrated in a robust face recognition of AR database. The experimental results verify that these methods can greatly improve the face recognition speed rate (97% decrease), and maintain a high recognition rate (95%). These methods are of practical values.

sparse representation; classification method; face recognition algorithm; gabor wavelet; fast algorithm

TP 311

A

2095-302X(2014)06-0889-04

2014-05-29；定稿日期：2014-07-16

廣西教育廳科研立項項目桂教科研〔2011〕14號文件資助項目(201106LX512)；玉林師范學(xué)院青年科研資助項目(2010YJQN19)

龍法寧(1978-)，男，廣西玉林人，講師，碩士研究生。主要研究方向為圖像處理、模式識別。E-mail：longfaning@163.com