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

龍法寧， 楊夏妮

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

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

龍法寧， 楊夏妮

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

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

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

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

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

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

1 SRC算法時(shí)間開(kāi)銷分析

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

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

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

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

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

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

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

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

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

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

3 快速稀疏分類算法

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

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

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

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

故式(7)可化為：

由式(9)得：

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

4.1 AR人臉庫(kù)識(shí)別率

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

圖1 AR無(wú)遮擋人臉庫(kù)

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

表1 各種人臉識(shí)別算法對(duì)比(%)

表2 快速稀疏識(shí)別算法高維識(shí)別率和計(jì)算時(shí)間

4.2 算法時(shí)間開(kāi)銷

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

表3 運(yùn)算時(shí)間對(duì)比(s)

5 結(jié) 束 語(yǔ)

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

[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í)與技術(shù), 2011, 7(19): 4641-4643.

[4] 張 娟, 詹永照, 毛啟容, 鄒 翔. 基于 Gabor小波和稀疏表示的人臉表情識(shí)別[J]. 計(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

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

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