改進的BOMP算法在人臉識別中的應用

殷愛菡，姜輝明，朱明

華東交通大學信息工程學院，南昌 330013

改進的BOMP算法在人臉識別中的應用

殷愛菡，姜輝明，朱明

華東交通大學信息工程學院，南昌 330013

采用組稀疏表示分類方法時，同類樣本同時參與對測試樣本的表示，忽略了類內樣本間的相關性。提出了一種改進方法，該方法在塊正交匹配追蹤算法基礎上，將樣本間的相干系數作為參數，設置適當的閾值，對每次選取的樣本進行判別，剔除與測試樣本相關性較差的樣本，優化算法的重建性能。在Yale B和ORL的數據庫上的實驗表明，與原有方法相比，改進后的方法得到的識別率較高，實驗結果證明了該方法的有效性。

人臉識別；組稀疏表示；塊正交匹配追蹤

1 引言

人臉識別技術作為機器視覺研究領域中一個研究熱點，在公共安全、視頻監控，圖像檢測等領域具有廣泛的應用前景。在理想情況下，現有的人臉識別系統能夠取得較好的識別效果，但是大部分人臉識別系統的魯棒性較差，當使用環境發生改變時，比如受到光照、表情、姿態和遮擋等因素影響，系統的識別率下降很快[1-2]。

最近Allen Y.Yang等[3]結合壓縮感知的原理提出了基于稀疏表示的人臉識別方法（SRC）。該方法假設測試樣本可以被來自同一類的訓練樣本的線性組合來表示，借助L1范數[4]獲得測試樣本的稀疏解，完成測試樣本的歸類判別，系統具有良好的魯棒性[5]。但是采用L1范數求解時，每次只選取該類中的一個測試樣本進行表示，忽略了類內樣本間的相關性，如果類中的測試樣本相關性很高，會得到錯誤的稀疏解，降低系統的識別率。對此Majumdar等[6]提出了基于組稀疏表示的分類方法（GSR），該方法要求同類訓練樣本同時參與或同時不參與對測試樣本的表示。然而由于光照、表情變化等因素的影響，同類中樣本的相關性差別很大，將每類訓練樣本作為整體來考慮，忽略了類內樣本間的差異，也會影響系統的識別率。

由上可知，理想的分類方法是找出同類樣本中相關性較高的訓練樣本去參與對測試樣本的表示。因此本文在基于組稀疏表示方法的原理上，提出了一種改進的塊正交匹配追蹤算法（BOMP）。該方法對BOMP算法的原子選取策略進行改進，利用樣本之間的相干系數作為參數，對選取的原子（測試樣本）進行篩選，優化該算法的重建性能，提高了人臉識別精度。

2 稀疏分類方法的基本原理

稀疏表示和組稀疏表示的分類方法都是基于同一假設：測試樣本可以用來自同一類的訓練樣本的線性組合表示，每一類樣本都有足夠多的訓練樣本，第i類訓練樣本用矩陣表示為Ai=[vi，1，vi，2，…，vi，ni]，則來自同一類別的測試樣本向量y可以用第i類訓練樣本的矩陣表示為：

將k類的訓練樣本組合成樣本集A=[A1,…，Ai,…，Ak]，這樣測試樣本y可以表示為：

其中x為系數ai，j的集合，即待求解的稀疏值。因此只需要獲得x的值，就能對測試樣本進行分類。

2.1 稀疏表示方法

基于上述假設，Y.Yang指出x系數向量是稀疏的，只有第i類的系數值是非0元素，即x=[0，…，0，ai，1，ai，2，…，ai，nj，0，…，0]，因此式（2）的問題，可以采用L0范數優化算法進行求解：

式（3）的優化問題是一個非確定多項式問題（NP難題），根據Donoho等提出的壓縮感知理論[7]，當系數向量x足夠稀疏可以用L1范數取代L0范數優化問題，即可通過下式求解：

式（4）的求解可通過Lasso算法實現[8]。實驗結果表明SRC方法有著較好的識別效果，但在人臉識別中，同類樣本之間的相關性非常高，Lasso方法每次只從類中選擇一個樣本，這樣的選擇方式會導致得到的稀疏系數不太理想，導致錯誤的判別結果。同時每次迭代過程中，只選取一個樣本，效率非常低，應盡可能地讓同類中相關性較高訓練樣本同時來參與表示。

2.2 組稀疏表示方法

針對SRC方法存在的缺陷，Majumdar等人提出了基于組稀疏表示的分類方法。GSR方法要求一個類的所有樣本同時參與或不參與對測試樣本的表示，式（2）的優化問題可以轉變為下式：

式（6）是一個凸優化問題，針對該問題的研究，主要有Elastic Net[6]和Group Lasso[8]兩種實現方法，但相應的算法比較復雜，計算速度較慢。通過對式（6）的求解，最終可以得到測試樣本的稀疏系數，完成對測試樣本進行歸類判別。

與SRC方法相比，GSR方法能夠取得較好的識別效果，它主要采用混合范數進行求解，能有效地保證稀疏系數穩定地恢復出來，但GSR同樣存在著缺陷，它每次選擇一個類的所有樣本對測試樣本進行表示，缺少對類中的樣本進行合理的篩選過程。在人臉識別中，人臉圖像通常受到姿態，光照等因素的影響，同類樣本之間的相關性差別很大，而將每個類作為整體同時參與對測試樣本表示的方式，忽略了同類樣本間的差異性，會影響樣本的歸類判別，降低系統的識別率。

為了能夠有效地解決這一問題，本文采用塊正交匹配追蹤算法（BOMP）對式（6）進行快速求解，同時利用樣本間的相關性，改進算法的原子選取策略，對選取的原子進行篩選。

3 算法實現

塊正交匹配追蹤算法[9]是架構在正交匹配追蹤算法（OMP）基礎上的一種方法，能夠有效地解決組稀疏信號的重建問題，獲得較好的重建效果。

3.1 BOMP算法

由于組稀疏信號中的非零元素是按組出現的，因此BOMP與OMP算法的不同之處，在于迭代過程中不是選擇單一的原子，而是尋找一個與殘差最接近的一個組，同時獲得測試樣本在索引集上的最優投影來逐步逼近原始信號，保證殘差最小，求得式（6）的組稀疏解。其基本思想是假定訓練樣本集A已進行歸一化處理，BOMP算法是在每一步迭代過程中，選擇和當前迭代殘差rt最大線性相關的原子組（A的某一類樣本），選定原子組以后，將信號正交投影到這些原子組擴張成的索引集中，并重新計算殘差，由此循環直到滿足約束條件rt＜θ，逐步逼近原始信號。

算法實現過程如下：

（1）初始化：余量r0=y，索引集V=?，迭代次數t=1。

（2）在A中選出與余量最相關的原子組：

（3）更新已選列空間：Vt=[Vt-1，Akt]。

（4）求解最小二乘問題，保證殘差最小，獲得在已選列向量上的最優投影，更新已選各列的稀疏系數值：

（5）更新余量：rt=y-Vt。

（6）t=t+1，判斷rt＜θ（θ為設定的最大殘差值）滿足則停止，輸出，否則跳到步驟2。

BOMP算法可分為三個階段：原子選擇、最小二乘求解和殘差更新。其中原子選擇階段對于信號的稀疏表示是最為重要的，BOMP的策略是每次選擇與殘差最大線性相關的組。由上節可知，組內原子之間的相關性是差別很大的，BOMP算法沒有對組內的原子進行區別對待，將與測試樣本相關性較差的原子刪除。

3.2 改進的BOMP算法

由上節可知BOMP算法有效地利用了信號的組稀疏特點，同OMP算法相比，重建性能得到了很大的提高。然而由于受到光照，噪聲等因素的影響，同類樣本之間的相關性差別很大。BOMP算法的原子策略是每次選取一個類的所有樣本，這種選取策略會將那些對測試樣本表示有害的原子引入索引集，隨著迭代次數的增加，索引集包含了過多的不利于判別信息，必將導致重構結果失敗。

因此需要在BOMP算法引入淘汰機制，對每次迭代選取的樣本進行篩選，將那些對測試樣本表示有害的原子給淘汰出去，優化最終的重構結果。對此本文引入相干系數作為一個判別參數，對每次迭代選擇的原子進行篩選。相干系數作為描述原子之間相關特性的一個物理量，表示原子間的最大絕對內積[10]。假設訓練樣本已經歸一化處理，兩個原子之間的相干系數定義為：

相干系數描述了兩個樣本間的最大相似性，相干參數的取值范圍是0＜μ＜1。與測試樣本相干系數越大的原子，通常與測試樣本所含的主要成份最相關，同樣地，與測試樣本相干系數越小的原子，與測試樣本所含的主要成分無關。

根據相干系數這一特點，改進的BMOP算法的具體思路是，首先計算測試樣本與訓練樣本的相干系數，設置一個合適的閾值th，然后對每次選取的組內原子進行閾值判斷，剔除與測試樣本相關性較差的原子（在實驗結果中詳細討論），保證參與線性表示的訓練樣本與測試樣本間存在較高的相關性。

改進算法具體實現過程如下：

（3）在A中選出與余量最相關的組：

（4）對組內的原子進行閾值判斷：nt=(μkt，n＞th)。

（5）更新已選列空間：Vt=[Vt-1，vnt]。

（6）求解最小二乘問題，保證殘差最小，獲得在已選列向量上的最優投影，更新已選各列的稀疏系數值：=argmin||y-Vtx||2。

（7）更新余量：rt=y-Vt。

（8）t=t+1，判斷rt＜θ（θ為設定的最大殘差值）滿足則停止，輸出，否則跳到步驟3。

從上述步驟可以看出，改進的BOMP算法與原有算法的流程基本相同，根本區別在于原子的選取階段，通過設置一個合理的相關系數閾值，對選出的組內原子進行篩選，將那些與測試樣本相干性差的原子剔除，降低索引集的維數，盡量保證參與表示的訓練樣本最相關。

4 實驗結果及分析

為了比較改進BOMP算法和原有算法識別效果，本文采用Yale B和ORL人臉數據庫進行實驗。Yale B人臉數據庫共有38個人在不同光照條件下共2 432張人臉圖像，每張圖像都是經過統一裁剪和規范，其圖像分辨率為192×168。為了保證實驗的公平性，實驗中隨機選取每個人的一半圖像（32幅）作為訓練圖像，另外32幅作為測試圖像。將圖像分辨率采樣降至為6×5，8×7，12×10和24×21，這樣得到的訓練樣本矩陣的特征維數分別為30，56，120和504。ORL人臉庫一共有40個樣本，每樣本有10張圖像，總共400張圖像，圖像分辨率為112×92。實驗時，選取每個類的一半圖像作為訓練圖像（5幅），對圖像進行采樣，最終維數分別為30，56，120，168。

圖1給出了人臉庫中的同一個人臉在不同光照下的6幅圖像，對圖中第一行圖像分別編號為A、B和C；第二行圖像分別編號為D、E和F。將圖像采樣至24×21，同時進行歸一化，計算6幅圖像兩兩之間的相關系數，其結果如表1所示。

圖1 不同光照下的同一人臉圖像

表1 同一類樣本之間的相關系數

從表1的結果可以看出，不同光照條件下的樣本之間的相關性差別很大。假設C為測試樣本，A、B都與C的相關性較高（0.665 6和0.793 4）；D、E、F三個樣本與C的相關性非常差，在0.16到0.29之間。采用SRC方法時，每次只選擇一個樣本，A和B不能同時參與表示。采用GSR方法時，同一類的樣本都需要參與表示。但從圖1可以看出，用右側光照的圖像（D和E）去表示左側光照的圖像（C），這顯然是不合理的，它們的相關系數也很小，因此需要設置一個閾值，將相關性較差的樣本給剔除。

閾值設置是否合理，會影響最后的識別效果。然而不同數據庫的拍攝環境又不一致，在本文使用的兩個人臉庫中，Yale B人臉庫中圖像主要是基于光照情況的變化，ORL人臉庫相對比較標準。本文通過多次實驗發現閾值設為：

表2和表3分別給出了三種方法在Yale B和ORL人臉數據庫上的識別效果。由兩個表中的數據結果可知，與SRC和GSR算法相比，改進的BOMP算法的識別效果最佳。

表2 三種算法在Yale B人臉庫的識別效果（%）

表3 三種算法在ORL人臉庫的識別結果（%）

5 結束語

針對組稀疏表示分類方法的缺陷，本文在塊正交匹配追蹤算法的基礎上，提出了一個可行的改進方法。在Yale B人臉數據庫上的實驗結果表明，與SRC和GRS兩種方法相比，改進的方法是有效的。該方法通過對每次選取的原子進行合理篩選，提高了人臉識別的效率，然而該方法的運算復雜度較高，有待于進一步的優化。

[1]Hui Kanghua，Li Chunli，Zhang Lei.Sparse neighbor representation for classification[J].Pattern Recognition Letters，2012，33（5）：661-669.

[2]Qiu Huining，Duc P，Venkatesh S，et al.A fast extension for sparse representation on robust face recognition[C]// IEEE Pattern Recognition（ICPR），2010：1023-1027.

[3]Wright J，Yang Y，Ganesh A，et al.Robust face recognition via sparse representation[J].Pattern Analysis and Machine Intelligence，2009，31（2）：210-227.

[4]Yang A，Sastry S，Ganesh A，et al.Fast ?1-minimization algorithms and an application in robust face recognition：a review，technical report No.UCB/EECS-2010-13[R].2010.

[5]Yang Meng，Zhang Lei，Yang Jian，et al.Robust sparse coding for facerecognition[C]//IEEEComputer Vision and Pattern Recognition（CVPR），2011：625-632.

[6]Majumdar A，Ward R K.Classification via group sparsity promoting regularization[C]//IEEE Acoustics，Speech and Signal Processing，2009：861-864.

[7]Donoho D L.Compressive sensing[J].IEEE Trans on Inf Theory，2006，52（4）：1289-1306.

[8]Tibshirani R.Regression shrinkage and selection via the lasso[J].J Royal Statist Soc B，1996，58（1）：267-288.

[9]Eldar Y C，Bolcskei H.Block sparsity：uncertainty relations and efficient recovery[J].IEEE Speech and Signal Processing，2010，58（6）：3042-3054.

[10]Tropp J.Greed is good：algorithmic results for sparse approximation[J].IEEE Trans on Inf Theory，2004，50（10）：2231-2242.

YIN Aihan,JIANG Huiming,ZHU Ming

School of Information Engineering,East China Jiaotong University,Nanchang 330013,China

When the group sparse representation is used to face recognition,the same samples take part in representation of the test sample at the same time.The original method ignores the correlation between the samples.To solve this problem, an improved block orthogonal matching pursuit algorithm is presented.The presented algorithm uses the coherent coefficient of the samples as a parameter,setting the proper threshold value to select sample discrimination.Therefore,the reconstruction of the algorithm is optimized.Experiments on the Yale B database and the ORL database show that the recognition rate of improved algorithm is higher than the original one.The experiment results verify the validity of the proposed algorithm.

face recognition;group sparse representation;block orthogonal matching pursuit

A

TP391

10.3778/j.issn.1002-8331.1204-0646

YIN Aihan,JIANG Huiming,ZHU Ming.Application of improved BOMP algorithm in face recognition.Computer Engineering and Applications,2014,50（6）：175-178.

國家自然科學基金（No.61262079）。

殷愛菡（1962—），女，博士，教授，研究領域為信號處理；姜輝明（1989—），男，碩士研究生；朱明（1988—），男，碩士研究生。E-mail：yinaihan@126.com

2012-05-04

2012-08-31

1002-8331（2014）06-0175-04

CNKI網絡優先出版：2012-09-07，http://www.cnki.net/kcms/detail/11.2127.TP.20120907.1626.021.html