改進(jìn)的BOMP算法在人臉識別中的應(yīng)用

殷愛菡，姜輝明，朱明

華東交通大學(xué)信息工程學(xué)院，南昌 330013

改進(jìn)的BOMP算法在人臉識別中的應(yīng)用

殷愛菡，姜輝明，朱明

華東交通大學(xué)信息工程學(xué)院，南昌 330013

采用組稀疏表示分類方法時，同類樣本同時參與對測試樣本的表示，忽略了類內(nèi)樣本間的相關(guān)性。提出了一種改進(jìn)方法，該方法在塊正交匹配追蹤算法基礎(chǔ)上，將樣本間的相干系數(shù)作為參數(shù)，設(shè)置適當(dāng)?shù)拈撝?，對每次選取的樣本進(jìn)行判別，剔除與測試樣本相關(guān)性較差的樣本，優(yōu)化算法的重建性能。在Yale B和ORL的數(shù)據(jù)庫上的實驗表明，與原有方法相比，改進(jìn)后的方法得到的識別率較高，實驗結(jié)果證明了該方法的有效性。

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

1 引言

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

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

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

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

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

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

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

2.1 稀疏表示方法

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

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

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

2.2 組稀疏表示方法

針對SRC方法存在的缺陷，Majumdar等人提出了基于組稀疏表示的分類方法。GSR方法要求一個類的所有樣本同時參與或不參與對測試樣本的表示，式（2）的優(yōu)化問題可以轉(zhuǎn)變?yōu)橄率剑?/p>

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

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

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

3 算法實現(xiàn)

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

3.1 BOMP算法

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

算法實現(xiàn)過程如下：

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

（2）在A中選出與余量最相關(guān)的原子組：

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

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

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

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

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

3.2 改進(jìn)的BOMP算法

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

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

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

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

改進(jìn)算法具體實現(xiàn)過程如下：

（3）在A中選出與余量最相關(guān)的組：

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

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

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

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

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

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

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

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

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

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

表1 同一類樣本之間的相關(guān)系數(shù)

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

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

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

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

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

5 結(jié)束語

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

[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.

國家自然科學(xué)基金（No.61262079）。

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

2012-05-04

2012-08-31

1002-8331（2014）06-0175-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-09-07，http://www.cnki.net/kcms/detail/11.2127.TP.20120907.1626.021.html