殷愛(ài)菡，姜輝明，朱明

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

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

殷愛(ài)菡，姜輝明，朱明

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

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

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

1 引言

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

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

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

2 稀疏分類(lèi)方法的基本原理

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

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

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

2.1 稀疏表示方法

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

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

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

2.2 組稀疏表示方法

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

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

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

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

3 算法實(shí)現(xiàn)

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

3.1 BOMP算法

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

算法實(shí)現(xiàn)過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 三種算法在Yale B人臉庫(kù)的識(shí)別效果（%）

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

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

針對(duì)組稀疏表示分類(lèi)方法的缺陷，本文在塊正交匹配追蹤算法的基礎(chǔ)上，提出了一個(gè)可行的改進(jìn)方法。在Yale B人臉數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果表明，與SRC和GRS兩種方法相比，改進(jìn)的方法是有效的。該方法通過(guò)對(duì)每次選取的原子進(jìn)行合理篩選，提高了人臉識(shí)別的效率，然而該方法的運(yù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.

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

殷愛(ài)菡（1962—），女，博士，教授，研究領(lǐng)域?yàn)樾盘?hào)處理；姜輝明（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