稀疏表示的人臉識別及其優化算法

鄭 軼，蔡體健

（1.華東交通大學軌道交通學院，江西南昌300013；2.華東交通大學信息工程學院，江西南昌330013；3.中南大學信息科學與工程學院，湖南長沙410075）

人臉識別問題是一個經典的模式識別問題。近年來，受到壓縮感知理論的啟發，基于稀疏表示的人臉識別技術得到了廣泛研究?；谙∈璞硎镜娜四樧R別是利用訓練圖片構造字典，再通過求解一個欠定方程來求得測試圖片的最稀疏線性組合系數，然后根據這些系數來對圖像進行識別分類。

稀疏表示的人臉識別問題表示成數學形式為：Y=AX，其中Y∈Rm是m維自然信號，A∈Rm·n是預定義的基（又稱為字典），X∈Rn是自然信號在預定義基下的n維稀疏表示。在已知原始信號的基礎上，求解其在預定義基下的稀疏表示，是一個稀疏編碼問題，可有以下兩種求解方式［1-3］：

稀疏正規化約束下的稀疏編碼：

誤差約束下的稀疏編碼：

稀疏編碼與信號的壓縮感知重構具有相同的數學形式，其主要的求解算法包括最小l0范數法、貪婪迭代匹配追蹤系列算法等。其中，匹配追蹤類方法為其近似求解提供了有力工具，在穩定性和運行速度方面具有一定的優勢。目前常用的匹配追蹤類算法包括：正交匹配追蹤（orthogonal matching pursuit，OMP）算法［4-5］，基于樹型搜索的正交匹配追蹤算法［6］，正則化正交匹配追蹤算法［7-8］，壓縮采樣匹配追蹤算法［9］等。

1 正交匹配追蹤算法

正交匹配追蹤思想［4-5］本質上是來自于K“稀疏”，就是從過完備字典的N個原子中尋找K個關鍵分量，這K個關鍵分量系數的絕對值應該比其它N-K個分量大得多。算法在每一次的迭代過程中，從過完備原子庫里選擇與信號最匹配的原子來進行稀疏逼近并求出余量，然后不斷迭代選出與信號余量最為匹配的原子。為了減少迭代次數，算法通過遞歸對己選擇原子集合進行正交化以保證迭代的最優性。具體見算法1，其中第5步是貪心選擇原子的步驟，q是所選擇原子的索引；第6步是將所選擇的原子Aq添加到子空間Aφ，Aφ是A的子矩陣；第7步是對已選擇的原子進行正交化，并計算信號的表示系數，在此需要計算逆矩陣，矩陣的求逆運算是重量級的運算，往往需要對矩陣進行三角分解或QR分解；第8步是計算最小殘差R。

算法1正交匹配追蹤算法

第1步 輸入：字典A，列信號Y，誤差容限ε或稀疏閾值K

第2步 輸出：稀疏的系數X

第3步 初始化：設置殘差R∶=Y，系數X∶=0，Aφ∶=[ ]

第4步 do while（迭代條件成立）

第5步q∶=max

第6步Aφ∶=[Aφ Aq]

第7步X=

第8步R∶=Y-AφX

第9步 end do

2 改進的正交匹配追蹤快速算法

由于F是對稱正定矩陣，因此可令，又由于FF-1=I（I為單位矩陣），經過運算可得到：

由于每次迭代都只是增加一列，因此在上式中c和w都是標量，V和Y是向量，而是上一次迭代的逆矩陣，是個已知矩陣，因此F-1的求解變成了向量或向量矩陣的輕量級運算。

為了進一步減少正交匹配追蹤算法的計算量，可以跳過殘差R的計算，直接計算ATR，并充分利用上一次迭代的結果進行遞推。其演算過程如下：

算法2改進的快速正交匹配追蹤快速算法

第1步 輸入：字典A，列信號Y，誤差容限ε或稀疏閾值K

第2步 輸出：稀疏的系數X

第3步 初始化：設置殘差R∶=Y，系數X∶=0，Aφ∶=[ ]，G∶=[ ]，Q∶=[ ]，n∶=1，product 0=ATY

第4步 do while（迭代條件成立）

第5步q∶=maxk

第6步 Ifn＞1 then

第7步 計算c，V，w，Y，X，然后計算

第8步 Else

第9步F-1=

第10步 End if

第11步Aφ∶=[Aφ Aq]

第12步G=

第13步X=F-1Q

第14步ATR=product0-GX

第15步 更新product0和G

第16步 end do

3 在稀疏表示的人臉識別中的應用

基于稀疏表示的人臉識別利用測試人身份的稀疏性來進行人臉識別［10］。數學表示形式為：Y=AX，其中Y∈Rm是測試人臉圖像，A∈Rm×n是用已標識的若干個人的n幅人臉圖像形成訓練字典，每幅圖像有m個像素點。X=[0，…，0，XiT，0，…，0]T∈Rn是稀疏系數，除了與測試圖像對應的系數為非0，X的其他值大多為0。由于一般情況下n?m（雖然潛在的情況是n?m），A是非完備字典，高維的圖像數據破壞了方程的欠定性，無法利用現有的稀疏編碼算法求解，并且在現實中，噪聲或遮擋不可避免，為此改為用Y=AX+e來描述，其中e∈Rn是n維未知噪聲，再將此式變換一下：

式中：I是單位矩陣，B=[A I]∈Rm×(n+m)；W=∈Rn+m，此時n+m＞m，因此基于稀疏表示的人臉識別問題變成求解以下最優化問題，可以用以上的FOMP算法來計算測試樣本的表示系數X。

人臉識別問題實際上是一個測試樣本的歸類問題。獲得了測試樣本的稀疏表示X后，由于X中的非0系數是與字典中屬于某一樣本類的原子相關，根據這些非0系數就可以簡單快速判斷測試樣本所屬類別。但是由于不同樣本類的同一光照角度的圖像很相似，容易產生誤判，另外噪聲的存在使得許多小的非0項和多個類別相關，因此我們需要設計一個更精確的分類器。具體做法是：將X中某樣本類的系數保留，其他樣本類的系數清0，然后計算測試信號的非線性逼近誤差值，最后比較所有樣本類的誤差值，最小的非線性逼近誤差所對應的類即是測試樣本歸屬的類。

4 實驗與參數設置

以Yale B人臉庫［11］（the yale face database B）做人臉識別實驗，選用10個人某種姿勢下的64種不同光照條件下的640幅圖片，每幅人臉圖片大小為84×96 像素，對圖片進行了直方圖均衡化及歸一化處理，實驗中選取每個人的一部分圖片形成訓練字典，隨機選取其他的圖片做測試樣本。所選用的機器是Dell筆記本電腦，Genuine Intel CPU 1.66 GHz，1 G內存。

1）兩種算法的對比。為了對比經典的OMP算法與改進的OMP算法的優劣，我們為每樣本類選擇15個光照圖片，選擇的原則是盡量考慮各種光照角度的圖片，從而構建一個大小為8 064×8 214 的訓練字典。隨機選擇不在字典中的300幅人臉圖片用于測試，設置稀疏閥值從5變化到50，在相同條件下應用這兩種算法進行人臉識別實驗，分別記錄下兩種算法平均100幅人臉識別時間以及對應的識別率。所得到的曲線圖如圖1所示。

由圖1可知，改進的FOMP 算法100幅人臉識別時間少于經典OMP 算法，并且隨著稀疏閥值的增加，兩種算法的人臉識別時間的差距加大，當稀疏閥值K=50 時，兩種算法的100幅人臉識別時間相差達到14秒多。

2）影響識別率的主要因素。在實驗中我們發現增加稀疏閥值，相應地人臉識別率隨著提高。圖2是設置字典大小為8 064×8 214（每樣本類15張圖片），并給測試圖片增加不同比例椒鹽噪聲的情況下，人臉識別率也隨稀疏閥值的變化曲線，由圖2可知，在稀疏閥值較小時，增加稀疏閥值可明顯提高識別率，但稀疏閥值增加到一定值時（如K＞15），識別率趨于穩定，分析其原因可知字典中每樣本類的原子數目決定了稀疏閥值的設置。

圖1 FOMP算法與OMP算法運行速度的對比Fig.1 The speed comparison between the OMP algorithm and the FOMP algorithm

圖2 不同噪聲下人臉識別率隨稀疏閥值的變化情況Fig.2 Face recognition rate changes with the sparse threshold under different noise

為了進一步提高人臉識別率，需對訓練字典進行調整。為每個樣本類提供各種角度的光照圖片，特別是極端光照條件下的人臉圖片，能明顯提高人臉識別率，見圖3（a）。圖4是設置稀疏閥值為20，分別為測試人臉添加10%，30%，55%的椒鹽噪聲的情況下，人臉識別率隨訓練字典變化的曲線。由圖4可知，在字典大小達到一定值時（每樣本類20幅圖片），人臉識別率基本穩定下來，添加了55%椒鹽噪聲的測試樣本的識別率仍可達到99.5%以上，這遠遠超過了人類肉眼的識別能力。圖3（b）是為測試圖像分別添加10%，30%，55%的椒鹽噪聲后的圖片。從圖3可知，噪聲達30%及以上的圖片，人類肉眼已很難識別了。

由圖3和圖4可知，在噪聲較小的情況下（30%以下噪聲），每樣本類的光照圖片只需20張，也就是說在光照變動不超過30°的情況下，人臉圖片是可以完全正確識別的，Yale B 人臉庫光照的左右變動范圍為-130°～130°，上下變動范圍為-40°～90°，光照角度并不全，如果補全數據，性能將可以進一步得到提高。

圖3 訓練圖片和測試圖片Fig.3 training picture and testing picture

圖4 不同噪聲下人臉識別率隨訓練字典大小的變化情況Fig.4 Face recognition rate changes with the size of dictionary under different noise

5 結論

研究提出了一種改進的FOMP算法，此算法是將重量級的矩陣求逆或大矩陣乘積運算轉變為輕量級的向量運算或向量矩陣運算，從而提高了算法的運算速度。此算法可廣泛應用于稀疏分解或壓縮重構，特別適合于人臉識別以及類似的高維數據的分類。將此算法用于人臉識別實驗，分析了影響人臉識別率的因素，通過實驗驗證了在光照角度的變動不超過30°的條件下，可以實現人臉的完全正確識別。如果進一步考慮人臉的表情、姿態等的變化，需要對訓練字典的選擇做進一步研究。

［1］戴瓊海，付長軍，季向陽.壓縮感知研究［J］.計算機學報，2011，34（3）：425-434.

［2］李樹濤，魏丹.壓縮傳感綜述［J］.自動化學報，2009，35（11）：1369-1377.

［3］楊榮根，任明武，楊靜宇.基于稀疏表示的人臉識別方法［J］.計算機科學，2010，37（9）：266-269.

［4］TROPP J A，GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53（12）：4655-4665.

［5］WEI E，SHA I. Orthogonal matching pursuit algorithm for compressive sensing［EB/OL］.（2008-08-01）［2011-09-01］http：//www.eee.hku.hk/～wsha/Freecode/freecode.htm.

［6］KARABULUT G Z，MOURA L，PANARIO D，et al. Flexible tree search based orthogonal matching pursuit algorithm［C］//IEEE International Conference on Acoustics，Speech，and Signal Processing，2005：673-676.

［7］DEANNA N，ROMAN V. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit［J］.IEEE journal of selected topics in signal processing，2010，4（2）：310-316.

［8］劉亞新，趙瑞珍，胡紹海，等.用于壓縮感知信號重建的正則化自適應匹配追蹤算法［J］.電子與信息學報，2010，82（11）：2713-2717.

［9］DO T T，L GAN，NGUYEN N，TRAN T D. Sparsity adaptive matching pursuit algorithm for practical compressed sensing［C］//Asilomar Conference on Signals，Systems and Computers，2008：581-587.

［10］WRIGHT J，GANESH A，YANG A，et al. Robust face recognition via sparse representation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（2）：210-227.

［11］GEORGHIADES A S，BELHUMEUR P N，KRIEGMAN D J.From few to many：illumination cone models for face recognition under variable lighting and pose［J］.IEEE Trans Pattern Anal Mach Intelligence，2001，23（6）：643-660.