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

龍法寧， 楊夏妮

（玉林師范學院計算機科學與工程學院，廣西 玉林 537000）

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

龍法寧， 楊夏妮

（玉林師范學院計算機科學與工程學院，廣西 玉林 537000）

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

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

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

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

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

1 SRC算法時間開銷分析

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

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

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

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

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

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

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

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

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

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

3 快速稀疏分類算法

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

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

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

由于 xTATb是一個數，而這個數的轉置是它的本身，因此有：

故式(7)可化為：

由式(9)得：

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

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

上的元素都加上同一個數 μ ＞0，則上述方程變為：

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

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

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

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

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

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

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

4 實驗結果及分析

4.1 AR人臉庫識別率

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

圖1 AR無遮擋人臉庫

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

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

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

4.2 算法時間開銷

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

表3 運算時間對比(s)

5 結 束 語

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

[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范數最小化算法的性能分析和比較[J]. 電腦知識與技術, 2011, 7(19): 4641-4643.

[4] 張 娟, 詹永照, 毛啟容, 鄒 翔. 基于 Gabor小波和稀疏表示的人臉表情識別[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)；玉林師范學院青年科研資助項目(2010YJQN19)

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