局部保持的稀疏表示字典學(xué)習(xí)*

陳思寶 趙令 羅斌

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601;2.安徽省工業(yè)圖像處理與分析重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230039)

稀疏編碼［1］理論和算法已成功應(yīng)用于圖像恢復(fù)［2］和壓縮傳感［3］領(lǐng)域.近年來(lái)，稀疏表示技術(shù)在圖像分類方面(如人臉識(shí)別(FR)［4］、數(shù)字和紋理分類［5］等)也取得了不錯(cuò)的效果.在稀疏表示分類中，利用最小化l0或l1范式，一個(gè)高維圖像測(cè)試樣本可以被其同一類的少量具有代表性的訓(xùn)練圖像樣本線性地表示或編碼，進(jìn)而進(jìn)行分類和識(shí)別.

稀疏表示可以預(yù)先定義字典，如Wright 等［4］所提出的稀疏表示分類(SRC)，使用所有類的訓(xùn)練樣本作為一個(gè)字典，并通過(guò)最小重構(gòu)誤差來(lái)實(shí)現(xiàn)待查詢?nèi)四槇D像的分類.最初訓(xùn)練樣本的不確定性以及噪聲方面的因素，使很多情況下的最初訓(xùn)練樣本并不能有效地表示所要查詢的圖像.即使是使用最初的訓(xùn)練樣本作為所要學(xué)習(xí)的字典，也不能充分地利用隱含在訓(xùn)練樣本中的判別信息.此外，現(xiàn)有的基礎(chǔ)分析設(shè)計(jì)字典(如Huang 等［5］將Haar 小波和Gabor小波用作字典)并不適用于特定類型的圖像(如人臉、數(shù)字和紋理圖像).如果將所有的訓(xùn)練樣本均作為字典且訓(xùn)練樣本非常多，那么會(huì)增大編碼的復(fù)雜度.因此，需要根據(jù)訓(xùn)練樣本學(xué)習(xí)出一個(gè)較小的且更加適合分類的字典.

字典學(xué)習(xí)(DL)是指在訓(xùn)練樣本中學(xué)習(xí)一個(gè)字典以更好地表示原始的訓(xùn)練樣本，從而便于后期的壓縮編碼和分類識(shí)別.近年來(lái)，出現(xiàn)了許多針對(duì)圖像處理［2］和分類［5］的DL 方法.Yang 等［6］提出了基于Fisher 判別準(zhǔn)則的稀疏表示字典學(xué)習(xí)(FDDL)方法.該方法利用不同類別訓(xùn)練樣本之間的判別信息，使學(xué)習(xí)出的字典中不同類別的字典原子具有最小的類內(nèi)離散度和最大的類間離散度，從而讓字典具有更強(qiáng)的判別能力.

然而，字典是為了用較少的原子更好地表示原始訓(xùn)練樣本，其原始訓(xùn)練樣本的局部數(shù)據(jù)結(jié)構(gòu)至關(guān)重要.增加Fisher 判別約束并不能得出保持局部信息的字典.保局投影(LPP)［7］是流形數(shù)據(jù)線性化降維的經(jīng)典方法，LPP 不僅能保持原始數(shù)據(jù)的局部結(jié)構(gòu)，而且能使變換后的數(shù)據(jù)更加具有判別信息，其局部保持的準(zhǔn)則被證明是Fisher 判別準(zhǔn)則的某種推廣形式.為使所學(xué)習(xí)的字典更加保持原始訓(xùn)練樣本的局部信息，文中借助LPP 的局部保持特性，在稀疏表示的字典學(xué)習(xí)中增加局部保持的約束，提出了一種基于局部保持準(zhǔn)則的稀疏表示字典學(xué)習(xí)(LPDL)方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了所提LPDL 方法的有效性.

1 稀疏表示分類簡(jiǎn)介

SRC 最早由Wright 等［4］提出并應(yīng)用于魯棒性人臉識(shí)別.假定有c 個(gè)類別的訓(xùn)練集A=(A1，A2，…，Ac)，Ai是第i 類的訓(xùn)練樣本子集，x 是測(cè)試樣本，則SRC 尋求x 基于訓(xùn)練樣本的稀疏線性重構(gòu)，并根據(jù)各類的重構(gòu)誤差最小進(jìn)行分類，其過(guò)程如下:

(1)利用l1范式最小化稀疏編碼x，即

式中，調(diào)節(jié)參數(shù)γ＞0 .

(2)分類

2 LPDL 的目標(biāo)函數(shù)

在訓(xùn)練樣本比較多時(shí)，SRC 求解稀疏系數(shù)非常耗時(shí).因此，出現(xiàn)了很多字典學(xué)習(xí)的方法(如KSVD［8］)來(lái)為稀疏表示學(xué)習(xí)原子數(shù)較少但又能充分表示原始訓(xùn)練樣本集的字典.

為提高現(xiàn)有字典學(xué)習(xí)的性能，且希望學(xué)習(xí)出的字典保持局部信息，文中提出了基于局部保持準(zhǔn)則的稀疏表示字典學(xué)習(xí)方法.設(shè)稀疏表示字典D=［D1D2… Dc］，Di是對(duì)應(yīng)于第i 類的子字典，訓(xùn)練樣本集為A，Y 為訓(xùn)練樣本A 在字典D 上的編碼系數(shù)矩陣，Y= ［Y1Y2… Yc］，即A ≈DY，Yi是Ai在D 上的編碼系數(shù)子矩陣.希望D 不僅具有A 的有效重構(gòu)能力，而且具有保持A 中樣本的局部信息能力.因此，文中提出如下的LPDL 模型:

2.1 判別保真項(xiàng)

由前面定義可知，Yi是Ai在D 上的表示，記為，其中是Ai在子字典Dj上的編碼系數(shù).設(shè)Ai在子字典Dj上的表示為Rj=Dj.首先，Ai可以由D 表示，即

其次，因?yàn)镈i是對(duì)應(yīng)于第i 類的子字典，所以希望Ai能更好地由Di表示，而不是由Dj(j ≠i)表示.也就是說(shuō)，希望系數(shù)接近于0，即足夠小.而所有有效的系數(shù)均在中，故也足夠小.因此，文中定義最小判別保真項(xiàng):

2.2 局部保持約束項(xiàng)

Nk(xi)為xi的k 近鄰集合.為使經(jīng)過(guò)編碼后的系數(shù)yi保持原數(shù)據(jù)點(diǎn)xi的局部信息，文中采用如下最小的目標(biāo)函數(shù):

即如果xi和xj在原始空間中的距離較近，那么希望編碼后的系數(shù)yi與yj的距離也很近。

記L= S -W，為邊權(quán)矩陣W 的拉普拉斯矩陣，對(duì)角矩陣，則

定義字典學(xué)習(xí)中的局部保持約束項(xiàng)f(Y)為tr(YLYT)，則f(Y)是非負(fù)定的.為了使f(Y)是正定的且更加平滑，文中在f(Y)中加入一個(gè)平滑項(xiàng)，則f(Y)可表示為

式中，Y= ［y1y2… yn］，調(diào)節(jié)參數(shù)η＞0 .此f(Y)是一個(gè)凸函數(shù).

2.3 LPDL 模型

將式(4)和(5)代入式(3)中，可得到如下LPDL目標(biāo)函數(shù):

盡管式(7)中的目標(biāo)函數(shù)J 相對(duì)于(D，Y)并不總是凸的，但當(dāng)其他的項(xiàng)均被固定時(shí)，就D 和Y 中的每一個(gè)元素來(lái)說(shuō)，它是凸的.因此，可以交替地迭代優(yōu)化字典D 和稀疏系數(shù)矩陣Y，即將LPDL 目標(biāo)函數(shù)(式(7))劃分為兩個(gè)子問(wèn)題:固定D 來(lái)更新Y和固定Y 來(lái)更新D.

3 LPDL 的優(yōu)化求解

文中采用如下方法來(lái)交替迭代優(yōu)化求解字典D和稀疏系數(shù)矩陣Y.

首先，固定字典D 求解系數(shù)矩陣Y .可通過(guò)將式(7)中的目標(biāo)函數(shù)J(D，Y)簡(jiǎn)化為一個(gè)稀疏編碼問(wèn)題來(lái)求解Y=［Y1Y2… Yc］.文中通過(guò)類與類之間的關(guān)系來(lái)計(jì)算Yi.當(dāng)計(jì)算Yi時(shí)，所有的Yj(j ≠i)均固定，因此式(7)的目標(biāo)函數(shù)可進(jìn)一步簡(jiǎn)化為

其次，固定系數(shù)Y 求解字典D.即通過(guò)類與類之間的關(guān)系來(lái)更新Di.當(dāng)更新Di時(shí)，所有的Dj(j ≠i)均固定.因此，式(7)的目標(biāo)函數(shù)可簡(jiǎn)化為

其中，Yi是A 在Di上的編碼系數(shù).

一般來(lái)說(shuō)，要求字典Di的每一列dli 都是一個(gè)單位向量，即.式(9)是一個(gè)二次規(guī)劃問(wèn)題，可通過(guò)MLSRC［10］中的算法來(lái)求解，即通過(guò)原子與原子之間的關(guān)系來(lái)更新字典Di.

整個(gè)LPDL 優(yōu)化迭代算法步驟如下:

(1)初始化字典D，以隨機(jī)向量初始化字典Di中的每一個(gè)原子;

(2)更新稀疏系數(shù)矩陣Y=［Y1Y2… Yc］，即固定字典D，利用IPM［9］方法最小化式(8)來(lái)求解Yi(i= 1，2，…，c);

(3)更新字典D，即固定稀疏系數(shù)矩陣Y，使用MLSRC［10］中的算法來(lái)更新字典Di(i=1，2，…，c);

(4)若相鄰迭代中的J(D，Y)之間的誤差小于閾值s，或者已經(jīng)達(dá)到了最大迭代次數(shù)T，則算法停止，否則，轉(zhuǎn)步驟(2).

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

4.1 參數(shù)的選擇

LPDL 方法最重要的一個(gè)參數(shù)是字典Di中的原子數(shù)pi.為簡(jiǎn)化實(shí)驗(yàn)，文中將所有類別的原子數(shù)pi(i= 1，2，…，c)均設(shè)為相等，并以SRC 為基準(zhǔn)方法，分析LPDL 方法在取不同原子數(shù)pi時(shí)的分類性能.以在COIL20 數(shù)據(jù)庫(kù)［11］上實(shí)現(xiàn)的圖像分類為例，其中SRC 使用最初的訓(xùn)練樣本作為字典，在每一類訓(xùn)練樣本中隨機(jī)選擇pi個(gè)作為字典原子，并進(jìn)行10 次實(shí)驗(yàn)得到平均識(shí)別率Ri，LPDL、FDDL［6］、SRC［4］方法取不同字典原子數(shù)時(shí)的識(shí)別率如圖1 所示.從圖中可以看出，LPDL 方法的識(shí)別率較FDDL 方法提升了約3%，較SRC 提升了約6%，尤其是當(dāng)字典原子數(shù)pi=8 時(shí)，LPDL 方法較FDDL 和SRC 方法有更高的識(shí)別率;LPDL方法的識(shí)別率波動(dòng)程度小于FDDL 和SRC 方法.這表明LPDL 方法能夠計(jì)算出一個(gè)緊湊的且具有代表性的字典，從而使LPDL 方法的運(yùn)算量較FDDL和SRC 方法少，識(shí)別率更高.

圖1 LPDL 和FDDL、SRC 方法在不同原子數(shù)下的識(shí)別率Fig.1 Recognition accuracy of LPDL，F(xiàn)DDL and SRC methods with different numbers of dictionary atoms

文中采用擴(kuò)展YaleB［12］、AR［13］和COIL20［11］數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)，以驗(yàn)證所提出的LPDL 方法的性能.如果沒(méi)有特別說(shuō)明，LPDL 方法的調(diào)節(jié)參數(shù)和所比較方法的參數(shù)均是通過(guò)5 倍交叉實(shí)驗(yàn)得到的，從而有效地避免了過(guò)度學(xué)習(xí).LPDL 方法的參數(shù)設(shè)置如下:①在擴(kuò)展YaleB［12］人臉庫(kù)上，1= 0.005，2= 0.050，γ= 0.005，η=0.500;②在AR［13］人臉庫(kù)上，1=0.005，2=0.050，γ=0.005，η=0.500;③在COIL20［11］圖像庫(kù)上，1=2=0.005，γ=0.001，η=0.050.

4.2 圖像分類

4.2.1 擴(kuò)展YaleB 數(shù)據(jù)庫(kù)

該數(shù)據(jù)庫(kù)包含了不同光照條件下38 人的2 414幅正面圖像.所有的人臉圖像經(jīng)過(guò)手工剪裁并被縮放到32 ×32 大小.文中根據(jù)文獻(xiàn)［12］方法，將該數(shù)據(jù)庫(kù)劃分成5 個(gè)子集:子集1 包含了自然光照條件下的266 幅圖像(每人7 幅)，子集2 和3 分別包含了中等、輕度光照條件下每人的12 幅圖像，子集4(每人14 幅)和5(每人19 幅)則分別包含了在嚴(yán)重光照和較嚴(yán)重光照條件下的圖像，如圖2 所示.

圖2 擴(kuò)展YaleB 數(shù)據(jù)庫(kù)的子集劃分圖例Fig.2 Samples of subsets divided from extended YaleB database

采用子集1 作為訓(xùn)練集，其他子集作為測(cè)試集.LPDL、FDDL［6］、SRC［4］、PCA［14］、ICA-I［15］方法的分類結(jié)果如表1 所示.可以看出:在中等亮度光照條件下，LPDL、FDDL 和SRC 方法的識(shí)別率達(dá)到了100%，優(yōu)于PCA 和ICA-I 方法約2.00%;在輕度光照條件下，LPDL 和FDDL 方法的識(shí)別率均為89.43%，優(yōu)于SRC 方法約0.22%，優(yōu)于PCA 和ICA-I 方法約9.40%;在嚴(yán)重的光照條件下，LPDL方法的識(shí)別率較FDDL、SRC、PCA、ICA-I 方法分別提升了約0.20%、0.40%、72.00%、72.00%;在較嚴(yán)重的光照條件下，LPDL 方法的識(shí)別率較FDDL、SRC、PCA、ICA-I 方法分別提升了約0.30%、1.50%、2.60%、5.00%.

表1 各種方法在擴(kuò)展YaleB 數(shù)據(jù)庫(kù)上的識(shí)別率Table1 Recognition accuracy of various methods on extended YaleB database %

4.2.2 AR 數(shù)據(jù)庫(kù)

AR 數(shù)據(jù)庫(kù)包括126 人的4 000 幅正面人臉圖像.其中，每人的26 幅圖像均拍攝于兩個(gè)不同的場(chǎng)景.參考文獻(xiàn)［4］方法，選擇子集1 作為訓(xùn)練集，該子集包括50 個(gè)男性和50 個(gè)女性拍攝于不同光照和不同表情變化條件下的7 幅圖像;子集2 包括和子集1 相同背景條件下每人的7 幅圖像，用作測(cè)試集.所有的人臉圖像經(jīng)過(guò)手工剪裁并被縮放到60×43 大小.

在該數(shù)據(jù)庫(kù)上LPDL、FDDL［6］、SRC［4］、NN［16］和SVM［17］方法的分類識(shí)別率分別為93.85%、92.00%、88.80%、71.40%、87.10%，LPDL 方法的識(shí)別率較FDDL、SRC、NN、SVM 方法分別提升了約1.85%、5.00%、22.40%、6.70%，即LPDL 方法 是最優(yōu)的，F(xiàn)DDL方法稍次于LPDL 方法.

4.2.3 COIL20 數(shù)據(jù)庫(kù)

COIL20 圖像庫(kù)包含20 個(gè)物體的1440 幅圖像，每個(gè)物體旋轉(zhuǎn)一周，每隔5°采集一幅圖像，共有72幅圖像.圖3 是COIL20 圖像庫(kù)中的部分樣本.

圖3 COIL20 圖像庫(kù)中的部分樣本圖Fig.3 Some sample images in COIL20 database

所有的物體圖像經(jīng)手工剪裁并被縮放到32 ×32 大小，即用一個(gè)1024維的向量表示.文中僅選取每個(gè)物體的前10 幅圖像作為訓(xùn)練集，其余圖像作為測(cè)試集.LPDL 和FDDL 方法的分類識(shí)別率分別為59.68% 和59.44%，LPDL 方法的識(shí)別率略優(yōu)于FDDL方法.

5 結(jié)論

文中提出了一種基于局部保持準(zhǔn)則的稀疏表示字典學(xué)習(xí)(LPDL)方法.LPDL 方法旨在學(xué)習(xí)一個(gè)結(jié)構(gòu)化的字典，其子字典不僅有詳細(xì)的類標(biāo)簽，而且保持了原始訓(xùn)練數(shù)據(jù)的局部信息.從實(shí)驗(yàn)結(jié)果可以看出，LPDL 方法的判別能力是雙重的:每個(gè)特定類的子字典對(duì)相關(guān)類的訓(xùn)練樣本均有很好的表示能力，而對(duì)不相關(guān)類則有差的表示能力;LPDL 方法將局部保持準(zhǔn)則附加在編碼系數(shù)上，使得相近數(shù)據(jù)點(diǎn)的編碼系數(shù)也保持近鄰關(guān)系，從而保持?jǐn)?shù)據(jù)矩陣的局部信息.在擴(kuò)展YaleB、AR 和COIL20 數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果表明，LPDL 方法的分類識(shí)別結(jié)果優(yōu)于其他方法.隨著核技巧在稀疏表示中的應(yīng)用，今后將致力于研究核化的稀疏表示字典學(xué)習(xí)。

［1］Olshausen B A.Emergence of simple-cell receptive field properties by learning a sparse code for natural images［J］.Nature，1996，381(6583):607-609.

［2］Elad M，Aharon M.Image denoising via sparse and redundant representations over learned dictionaries［J］.IEEE Transactions on Image Processing，2006，15(12):3736-3745.

［3］Candès E J.Compressive sampling［C］∥Proceedings of the International Congress of Mathematicians.Madrid:European Mathematical Society，2006:1433-1452.

［4］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.

［5］Huang K，Aviyente S.Sparse representation for signal classification［M］∥Advances in Neural Information Processing Systems 19.Cambridge:MIT Press，2007:609-616.

［6］Yang M，Zhang L，F(xiàn)eng X，et al.Fisher discrimination dictionary learning for sparse representation ［C］∥Proceedings of 2011 IEEE International Conference on Computer Vision.Barcelona:IEEE，2011:543-550.

［7］He Xiaofei，Niyogi Partha.Locality preserving projections［M］∥Advances in Neural Information Processing Systems 16.Cambridge:MIT Press，2003:152-160.

［8］Zhang Q，Li B.Discriminative K-SVD for dictionary learning in face recognition［C］∥Proceedings of 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco:IEEE，2010:2691-2698.

［9］Rosasco L，Verri A，Santoro M，et al.Iterative projection methods for structured sparsity regularization ［R/OL］.(2009-10-14).http:∥hdl.handle.net/1721.1/49428.

［10］Yang M，Zhang L，Yang J，et al.Metaface learning for sparse representation based face recognition［C］∥Proceedings of the 17th IEEE International Conference on Image Processing.Hong Kong:IEEE，2010:1601-1604.

［11］Nene S A，Nayar S K，Murase H.Columbia object image library (coil-20)［R/OL］.(1996-01-01)［2013-05-20］.http:∥www.cs.columbia.edu/CAVE/software/softlib/coil-20.php.

［12］Naseem I，Togneri R，Bennamoun M.Linear regression for face recognition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(11):2106-2112.

［13］Martinez A，Benavente R.The AR face database［R］.Columbus:the Ohio State University，1998.

［14］Jolliffe I T.Principal component analysis ［M］.New York:Springer-Verlag，1986.

［15］Comon P.Independent component analysis，a new concept?［J］.Signal Processing，1994，36(3):287-314.

［16］Beyer K S，Goldstein J，Ramakrishnan R，et al.When is“nearest neighbor”meaningful?［C］∥Proceedings of the 7th International Conference on Database Theory.London:Springer-Verlag，1999:217-235.

［17］Cortes C，Vapnik V.Support vector machine［J］.Machine Learning，1995，20(3):273-297.