分塊組合搜索的結構稀疏人臉識別模型

蔡體健，徐君，謝昕

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

分塊組合搜索的結構稀疏人臉識別模型

蔡體健1，2，徐君2，謝昕2

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

摘要：介紹一種新的稀疏表示人臉識別模型，在經典的稀疏表示分類模型基礎上，利用數據字典的結構信息，考慮算法實現的可行性，提出了一種分塊組合搜索的稀疏表示人臉識別模型，主要思想是將數據字典按類別自然分塊，然后在數據塊內進行組合搜索，再聯合不同類別的組塊，以尋找表示能力最強的組塊。為驗證模型的性能，使用結構貪婪算法實現分塊組合搜索方法和其他的結構稀疏方法，并進行比較，實驗顯示分塊組合搜索的人臉識別率高于其他結構稀疏方法，且此方法性能穩定，不受數據字典排列的影響。

關鍵詞：人臉識別；壓縮感知；結構稀疏；組合搜索；結構貪婪算法

隨著壓縮感知理論的發展，基于稀疏表示人臉識別方法得到廣泛的關注，基于稀疏表示的人臉識別方法是將待識別的人臉圖像yRn表示成訓練樣本圖像DRn×p的稀疏線性組合，即：y=D，其中Rp是y在字典D下的表示系數，在已知y和D的條件下，可通過壓縮感知重構算法求解稀疏表示系數，然后通過分析稀疏表示系數對樣本進行判別歸類。SRC（sparse representation-based classification）［1］模型是經典的基于稀疏表示的分類模型，SRC模型合并各類別的表示子空間，構成聯合子空間，來共同表示測試數據，在聯合字典中每個類的數據都為待測數據的表示做貢獻，如果某個類貢獻得多，則其他類就貢獻得少，分類的依據就是判斷到底哪個類在競爭表示中貢獻得多。在SRC的基礎上，文獻［1-3］提出了魯棒的SRC模型（R-SRC），R-SRC添加了一個單位矩陣到SRC的聯合字典，形成了一個過完備字典，并利用這個單位矩陣來表示異常數據，使得模型對噪聲和遮擋具有很強的魯棒性能。文獻［4］綜合了此類稀疏分類模型，將各種保真函數與懲罰函數相結合，得到適合不同條件的人臉識別模型，統稱為競爭表示模型（collaborative representation based classification，CRC）。文獻［5］提出了擴展的SRC模型（ESRC），ESRC模型假設各類別共享相同的環境條件，其字典不僅包含訓練樣本，還包括各類別的類內差異，ESRC模型可以應用于單個訓練樣本的情況下。

稀疏表示分類模型在人臉圖像遮擋和噪聲處理方面具有較好的識別性能，但傳統的稀疏分類模型在數據重構時，僅利用了數據稀疏性的先驗知識，大量的結構信息有待挖掘利用。已有文獻［6-7］提出組結構的稀疏表示分類模型（group sparse representation-based classification，GSRC），此模型利用了數據字典的組塊特性，限制了搜索空間，從而提高了人臉識別的性能。但同時人們也發現這種預定義的、定長的組結構僅適合于類內差異較小的數據字節典；如果類內差異較大，則這種定長組結構不僅不能改善系統性能，而且可能會起到相反的作用。因此人們考慮更細致的組劃分方式，文獻［7-8］提出將類內樣本進一步劃分成若干個更小的組塊，一定程度上減輕了組塊劃分不當所造成的影響，但這種方式所得到的仍然是定長的組結構，仍存在組內差異較大的問題。圖結構［9-11］是比組結構更一般的數據結構，其組劃分是動態的、可重疊的，并不需要預先知道組劃分情況，而是根據數據之間的關系動態地形成數據組。動態線性組結構是一種一維的圖結構，其動態的組劃分特性使得它具有更大的靈活性，更能準確地描述數據之間的關系。

1　從經典稀疏分類模型到結構稀疏分類模型

1.1經典的稀疏分類模型

經典的SRC模型將一個人臉識別問題轉變為一個稀疏表示問題，即將測試數據表示成數據字典的稀疏線性組合。SRC的數據字典可由所有類別的訓練樣本構成，假設訓練樣本有m個類別，每類別有q個訓練數據，則D=[d11,…,d1q,…,di1…diq,…,dm1,…,dmq]，其中[di1,…,diq]是第i類的訓練樣本，如果y是第i類的測試數據，則在理想的情況下，通過稀疏重構所獲得的表示系數中，字典原子[di1,…,diq]所對應的系數項為非0，而其他項為0，即表示系數=[0,…,0,i1,…,iq,0,…,0]應該是稀疏的，應該只有1/m個非0項，測試數據可表示為y=[di1,…,diq][i1,…,iq]T。SRC模型通過尋找測試數據在訓練樣本基下的最稀疏的線性表示來進行分類，當表示系數足夠稀疏時，以上稀疏表示問題可等價于以下最優化問題

在有噪聲的情況下，測試數據y=y0+e，y0可表示為訓練字典D的稀疏線性組合，噪聲eRn可表示為單位矩陣ΛRn×n的稀疏線性組合，將訓練字典和單位矩陣合并可構成新的字典基[D Λ]，y可表示為新基下的稀疏線性組合，通過以下的稀疏重構可以獲得y的稀疏表示系數：

1.2組結構稀疏分類模型

經典的SRC模型將每個字典原子分隔開來，獨立處理，沒有考慮各原子之間的關系，所產生的稀疏是非結構的。近年來，研究人員發現除了稀疏以外，如果引入字典原子之間的相關性先驗信息，可提高稀疏表示的精度以及增強識別的魯棒性，所產生的稀疏被稱為結構化稀疏。

在SRC模型中，訓練樣本按類排列，同類的樣本排列在一起，使數據字典具有明顯的組塊結構，在類內樣本差異不大時，同類的數據劃分為一個組，可制約數據的選擇，進而提高系統性能；但是當類內樣本之間存在較大的差異時，如果仍強制這些數據在一個組，則組內數據的影響互相抵消，反而會降低數據的分類結果。因此人們考慮采用聚類方法或非線性流行學習的方法，將類內樣本進一步劃分為多個等長的小組，如圖1所示，Dij是表示第i類第j個小組，一個類會被劃分為多個小組。

圖1　每個類別的訓練數據被進一步劃分為更小的組塊Fig.1 The training images in one class being further divided into multiple small group spaces

若數據字典的每個類別被分為g個等長的小組，則對應的表示系數將有m×g組塊，組結構稀疏重構可以表示成以下最優化問題

1.3分塊組合搜索的稀疏分類模型

以上細分小組的方法在一定程度上減輕了組塊劃分不當所造成的影響，但這種方式所得到的仍然是定長的組結構，小組劃分仍然不夠靈活，組內的差異仍然會影響分類效果。為此可以采用動態可重疊的組合搜索方式，搜索所有可能的組合來尋找表示能力最強的組塊。但是如果對搜索不加限制，很容易產生組合爆炸，造成不可行計算。為了減少搜索空間，可以僅搜索固定長度的小組塊，例如長度為2或長度為3的組塊，把這些小組塊作為基塊，以基塊的聯合來表示其他形式的組塊。若基塊的索引集合稱為基子集B，它是表示系數索引集I的子集，I=b，則任何一個組塊的索引F都能表示為基子集的并集，F=b。因此通過限制搜索空間，僅搜索基子集空間，可將一個NP的組合搜索問題變為一個可行計算。

此外，還可以進一步采用以下策略減少搜索空間［9-10］：滑動窗口法和分塊組合搜索法。以下以一維的表示系數[i1,i2,...,ij,...,iq,(i+1)1,...,(i+1)q,...]（表示系數ij對應著第i類第j個訓練樣本）為例，介紹兩種策略如何獲得動態可重疊組塊。

1.3.1滑動窗口法

滑動窗口法使用一個定長的窗口，在表示系數上滑動以截取組塊。如圖2所示所截取的是大小為3的組塊，包括：[i1,i2,i3]、[i2,i3,i4]、[i3,i4,i5]……，這樣截取的組塊是有重疊的，且每個組塊是由相鄰連續的元素構成。這種分組方法比較適合自然數據，因為自然數據都具有一定的連續性。對于SRC模型其數據字典是人為排列的，并沒有這樣的連續性，因此數據字典的排列會嚴重影響系統性能。滑動窗口分組方法利用了數據的連續性，但顯而易見，它是一種近似方法，還有許多組塊并沒有考慮到，例如[i2,i5,i8]等這些非相鄰元素構成的組塊。

圖2　滑動窗口在表示系數上截取組塊Fig.2 Sliding window intercepts chunks in the coefficient

1.3.2分塊組合搜索法

在數據維數較大時，組合搜索會產生非常大的計算量；但數據量不大時，組合搜索是有可能的。為此人們考慮將數據進行分塊，然后在數據塊內進行組合搜索，再聯合各數據塊的搜索結果。由于SRC模型的數據字典是按類排列，對應的表示系數可以按類別自然分塊，在每個類別的訓練樣本數不多的情況下，可以對類內系數進行組合搜索，搜索指定長度的所有組合，假如第i類有5個訓練樣本，則長度為3的組塊包括：[i1,i2,i3]、[i1,i2,i4]、[i1,i2,i5]、[i1,i3,i4]、[i1,i3,5]、[i1,i4,i5]、[i2,i3,i4]、[i2,i3,i5] [i2,i4,i5]、[i3,i4,i5]共10個組，其中包括不相鄰元素構成的組塊。

以上兩種動態分組的方法都是以類別為界線，對類內數據進行動態分組，而類間仍然是固定長度的組劃分，將類間的定長組結構與類內的動態線性組結構相結合，形成了一種混合的結構，為了正式地描述混合組結構稀疏模型，假設數據字典有m個類別，i[1,m]，若第i類有gi個不相鄰組，ij表示第i類第j個組的表示系數，則混合組結構稀疏重構可表示為

為了區分兩種動態分組方法：滑動窗口法和分塊組合搜索法，我們分別用Pstruct1和Pstruct2表示它們的稀疏模型。相應的帶噪聲的混合組結構稀疏重構可表示為：

2　實現算法

實現可重疊的動態組稀疏重構的算法較多，在此選用結構貪婪算法（structured greedy algorithm，SGA）［12］。SGA算法是正交匹配追蹤（orthogonal matching pursuit，OMP）算法對結構稀疏的擴展。OMP算法在每次迭代中總是選擇局部最優的一個原子進入活動集；而SGA算法在每次迭代中總是選擇局部最優的基塊進入活動集。

SGA算法在預處理階段，需要確定有限的基子集空間。不同要求的結構稀疏具有不同的基子集空間：對于標準稀疏，其基子集空間是由單元素構成；對于組結構稀疏，其基子集空間是由定長的組塊構成，例如長度為3的組塊；對于動態可重疊組結構稀疏，可通過滑動窗口法或分塊組合搜索法獲得其基子集空間；對于魯棒的稀疏分類模型，其噪聲部分的表示系數可以采用標準稀疏類似的方式處理，然后將兩部分基子集聯合構成搜索空間B=B?Be，其中B是表示系數所對應的基子集空間，而Be是噪聲部分的表示系數所對應的基子集空間。

SGA算法在每次迭代過程中，需要選擇局部最優的基塊進入活動集，由于基塊的大小可以不同，因此不能僅考慮數據的逼近尺度，還應考慮此基塊對稀疏度的影響。為此引入了編碼復雜度的概念，利用編碼復雜度反襯數據的稀疏度。表示系數的復雜度可以簡單地用公式：c()=gln(p)+||來計算，其中p為表示系數的維數，g為動態組個數，如果基塊與已有的活動集的元素相鄰，則動態組個數g不會增加，編碼復雜度僅增加了表示系數的支撐集大小；但如果基塊沒有與活動集相鄰，則動態組個數增加，編碼復雜度增加較大，因此可以通過對編碼復雜度的懲罰來限制此類基塊的選擇。通常用以下公式計算結果作為基塊選擇的依據

3　實驗與結果分析

實驗選擇了AR剪裁的人臉庫［13］和擴展的YaleB［14］人臉庫。AR庫中共有100個人的2 600張圖像，被平分為兩個子集，每個子集中每人有一張標準照，以及不同表情、光照、帶墨鏡、戴圍巾的照片各三張。擴展的YaleB人臉庫中共有38個人，每人64張圖像，共2 414張（其中有18張圖像損壞）不同光照的人臉圖像，根據光照角度不同，被分為五個子集。為運行方便，所有圖片用下采樣方式降維，每個訓練樣本被堆疊為一維數據，數據字典進行了二范數規格化處理。實驗所選用的機器是華碩筆記本電腦，CPU為i7-4700HQ，四核2.4 G，4 G內存，基于x64處理器的windows8操作系統。

3.1不同結構稀疏的比較與分析

為了比較不同組塊劃分方式所形成的結構稀疏對人臉識別性能的影響，以下使用SGA算法分別實現動態組結構（包括滑動窗口法Pstruct1和分塊組合搜索法Pstruct2）、定長組結構P?2/?1和單元素結構P?1的稀疏重構，實驗的訓練集中每人有8張圖片，來自AR庫的子集1，包括不同表情、光照、帶墨鏡、戴圍巾的照片各兩張，測試集為AR庫的子集2中的不同表情、光照、帶墨鏡、戴圍巾的照片。根據字典的數據結構特點，我們將基塊的大小設置為2，定長組結構的組塊大小也設置為2，比較4組結構稀疏的人臉識別性能，實驗結果如圖3、圖4所示，圖3是各類樣本在不同結構稀疏下，所產生的平均人臉識別錯誤率；圖4是對應的平均人臉識別時間。由圖可知，分塊組合搜索法所得到的人臉識別錯誤率最低，在相近的運行時間內，Pstruct2所得到的人臉識別錯誤率與Pstruct1、P?2/?1、P?1相比較，分別降低了10%、12%、13%。分塊組合搜索法在更廣的范圍內尋找表示能力強的組塊，因而在人臉識別過程中，能找到與測試圖像最接近的樣本，人臉識別率能得到顯著提高。

圖3　AR庫中各類樣本在不同結構稀疏下，所產生的平均人臉識別錯誤率Fig.3 The average recognition error rates obtained by different structure sparse reconstruction in four types of samples of AR

圖4　圖3對應的平均人臉識別時間Fig.4 The average recognition time corresponding to Fig.3

3.2訓練樣本的排列順序對人臉識別的影響

為了驗證數據字典中類內樣本的排列順序對人臉識別性能的影響，本實驗使用與4.1相同的實驗環境，使用同樣的訓練集和測試集，僅改變訓練集類內樣本的排列順序，比較改變排列前后的人臉識別錯誤率，結果如表1所示。由表可知，改變樣本的排列不會影響分塊組合搜索和單元素的稀疏重構，因為數據字典類內樣本排列順序無論如何改變，分塊組合搜索法及標準稀疏的搜索空間都沒有改變，因此這兩種方法的人臉識別性能不受數據字典排列順序的影響，具有一定的穩定性；但類內樣本排列的改變會明顯影響滑動窗口和定長組結構的稀疏重構，嚴重時影響率達到24%。

表1　數據字典類內樣本改變排列前后的人臉識別錯誤率Tab. 1 Face recognition error rates before and after changing the arrangement of the intra-class sample in the dictionary

3.3含噪聲的人臉識別

為了驗證在含噪聲的情況下，不同的結構稀疏對人臉識別性能的影響，我們改進了魯棒的SRC模型，對R-SRC模型中噪聲部分所對應的表示系數，僅考慮其稀疏性，即其基子集空間僅包含單元素基塊，并與其他表示系數的基子集空間相聯合，構成混合的搜索空間。實驗中選擇了數據較豐富的擴展的YaleB人臉庫，每張圖像被處理為132×1像素，訓練集是從YaleB的子集1和子集2中隨機選擇的9張圖片，基塊大小設置為3，定長組大小也設置為3；測試集使用子集3，人為地為每個測試圖像添加10%到60%的噪聲，每個實驗做20次。實驗的結果如圖5所示。

3.4與其他算法的比較

本節實驗進一步使用SGA算法實現不同結構的稀疏重構，同時與一些經典的壓縮感知重構算法開展比較。對于AR庫，每人隨機抽取9張圖片構成訓練字典，字典中包括戴眼鏡、帶圍巾等各類樣本，將字典以外的樣本做測試集；對于擴展的YaleB庫，每人隨機抽取18張圖片構成訓練字典，其他的做測試集。應用SGA算法、譜投影梯度的l1最小化算法（spectral projected gradient for l1minimization，SPGL1）［15］、快速迭代收縮閥值算法（fast iterative shrinkage-thresholding algorithmn，FISTA）［16］、正交匹配追蹤算法（orthogonal matching pursuit，OMP）［17］實現不同結構稀疏重構，每個實驗做20次，平均的人臉識別的結果如表2所示。由表可知，定長組結構時，SGA算法能取得較好的識別率，分塊組合搜索的SGA算法又優于定長組結構的SGA算法；標準稀疏時，SPGL1算法的識別性能較好。但需要注意的是分塊組合搜索的運行時間較長，AR庫圖像分辨率為1 400×1，每類的訓練集大小為9，單位人臉識別時間達到2.830 2 s，可見分塊組合搜索方法并不適合數據字典較大的情況。

圖5　平均人臉識別率隨噪聲大小的變化曲線Fig.5 The average face recognition rates with a function of the percentage of corrupted

表2　SGA算法與其他算法的人臉識別率比較Tab. 2 The comparison of face recognition rates between SGA and other algorithms

4　　結語

由于數據字典組塊劃分的不確定性，需要使用搜索的方式尋找表示能力最強的組塊，在數據維數較大時，組合搜索會產生非常大的計算量，造成不可行計算。為此考慮先將數據進行分塊，然后在數據塊內進行組合搜索，再進行組塊聯合。根據SRC模型的數據字典的特點，將表示系數按類別自然分塊，然后對類內系數進行組合搜索，搜索指定長度的所有組合，以尋找局部最優的組塊，提高系統的識別性能。最后通過實驗驗證分塊組合搜索的方法其人臉識別率在不同樣本、不同分辨率、含噪聲等情況下都獲得最好的識別性能，且此方法性能穩定，不受數據字典排列順序的影響，但由于其基子集空間較大，人臉識別時間較長，僅適合數據字典不大的情況下使用。此外對于遮擋、噪聲等誤差的處理，僅考慮了其稀疏性，今后可以進一步考慮遮擋、噪聲的連續性等結構特征。

參考文獻：

[1] YANG A Y, ZHOU Z, MA Y, et al. Towards a Robust Face Recognition System Using Compressive Sensing[C]//Eleventh Annual Conference of the International Speech Communication Association. Chiba Makuhari, 2010: 2250-2253.

[2] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2009, 31(2): 210-227.

[3]鄭軼,蔡體健.稀疏表示的人臉識別及其優化算法[J].華東交通大學學報, 2012, 29(1): 10-14.

[4] ZHANG L, YANG M, FENG X, et al. Collaborative representation based classification for face recognition[J]. arXiv preprint arX?iv,1204, 2358, 2012.

[5] DENG W H, HU J N, GUO J. Extended SRC:undersampled face recognition via intraclass variant dictionary[J]. IEEE Transac?tions on Pattern Analysis and Machine Intelligence, 2012,34(9):1864-1870.

[6] MAJUMDAR A, WARD R K. Classification via group sparsity promoting regularization[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP, 2009: 861-864.

[7] ELHAMIFAR E, VIDAL R. Robust classification using structured sparse representation[C]//2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2011:1873-1879.

[8]胡正平,宋淑芬.原子稀疏結合塊結構稀疏的聯合表示圖像識別算法[J].信號處理, 2013,29(7):888-895.

[9] JENATTON R, AUDIBERT J Y, BACH F. Structured variable selection with sparsity-inducing norms[J]. Journal of Machine Learning Research, 2011,12:2777-2824.

[10] BACH F, JENATTON R, MAIRAL J, et al. Structured sparsity through convex optimization[J]. Statistical Science, 2012,27(4): 450-468.

[11] SCOTT S L, VARIAN H R. Predicting the present with bayesian structural time series[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2014,5(1):4-23.

[12] HUANG J, ZHANG T, METAXAS D. Learning with structured sparsity[J]. Journal of Machine Learning Research, 2011,12: 3371-3412.

[13] MARTINEZ A M, BENAVENTE R. The AR Face Database[R].CVC Technical Report#24, June 1998.

[14] 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 Transactions on Pattern Analysis and Machine Intelligence, 2001,23(6):643-660.

[15] FRIEDLANDER M, VAN D B, E SPGL1, a solver for large scale sparse reconstruction [J]. SIAM Journal on Scientific Comput?ing, 2008,31(2):890-912.

[16] YANG A Y, SASTRY S S, GANESH A, et al. Fast ?1-minimization algorithms and an application in robust face recognition: A review[C]//2010 17th IEEE International Conference on Image Processing (ICIP). IEEE, 2010:1849-1852.

[17]蔡體健,樊曉平.貪婪追蹤系列算法的分析與優化[J].小型微型計算機系統, 2014,35(5):1116-1119.

（責任編輯姜紅貴）

Face Recognition Model of Structural Sparse with Intra-class Combined Search

Cai Tijian1,2,Xu Jun2, Xie Xin2
(1.School of Information and Science Engineering, Central South University, Changsha 410075, China; 2. School of Information Engineering, East China Jiaotong University, Nanchang 330013, China)

Abstract:The paper introduces a new face recognition model of sparse representation, which is based on the clas?sical model of sparse representation-based classification (SRC), and utilizes the structure prior information of the data dictionary. Considering the feasibility of the algorithm, it proposes the face recognition model of structural sparse with intra-class combined search that the data dictionary is chunked by natural class, all combinations of specified length are searched in class and blocks in different class are combined to look for the block which can best represent test data. In order to verify the performance of the model, it uses the structured greedy algorithm to realize intra-class combined search and other structural sparse, and compares their performance of face recogni?tion. The experiments show face recognition rates of the model with intra-class combined search are higher than other structural sparse, and the model has stable performance which is not affected by the arrangement of the data dictionary.

Key words:face recognition; compressed sensing; structural sparse; combined search; structured greedy algorithm

作者簡介：蔡體健（1968—），女，副教授，博士研究生，主要研究方向為智能信息處理、壓縮感知、模式識別與人工智能。

基金項目：江西省自然科學基金（20132BAB201027，20142BAB207007）；教育部人文社會科學研究青年基金（14YJCZH172）；華東交通大學科研基金（09111004）

收稿日期：2014-11-08

文章編號：1005-0523（2015）03-0114-08

中圖分類號：TP391.4

文獻標志碼：A