局部保持“字典對”學(xué)習算法及其應(yīng)用

郭艷卿 王久君 郭 君

(大連理工大學(xué)信息與通信工程學(xué)院 大連 116024)

?

局部保持“字典對”學(xué)習算法及其應(yīng)用

郭艷卿 王久君 郭 君

(大連理工大學(xué)信息與通信工程學(xué)院 大連 116024)

(guoyq@dlut.edu.cn)

字典學(xué)習(DL)方法近年來被廣泛應(yīng)用于解決各種計算機視覺領(lǐng)域的問題.現(xiàn)有的大部分字典學(xué)習算法均旨在學(xué)習一個綜合型字典來表示輸入信號，并使表示系數(shù)或表示誤差具有一定的判別能力.這些字典學(xué)習算法大都需要對稀疏表示系數(shù)采用l0或者l1范數(shù)的約束，所以學(xué)習過程比較耗時.解析型字典學(xué)習的提出較為有效地解決了字典學(xué)習算法效率低的問題.在分類識別任務(wù)中，聯(lián)合學(xué)習一個綜合型字典和一個解析型字典正在成為一個熱門的研究趨勢，這不僅很大程度上降低了學(xué)習過程中的計算復(fù)雜度，而且在分類識別性能上也能有一定的提升.借鑒了最新提出的“字典對”學(xué)習思想，利用訓(xùn)練數(shù)據(jù)的局部結(jié)構(gòu)信息，提出了局部保持的綜合型-解析型“字典對”學(xué)習算法.在3個國際公開測試數(shù)據(jù)庫(人臉識別庫Extended YaleB、AR和圖像分類庫Caltech101)上的實驗結(jié)果表明，局部保持的綜合型-解析型“字典對”學(xué)習算法在準確率和效率方面都具有很好的性能.

字典學(xué)習；綜合型-解析型字典對；局部保持；分類；識別

近年來，基于過完備字典的稀疏模型在圖像處理和計算機視覺領(lǐng)域中得到了廣泛的應(yīng)用.該模型的核心就是利用過完備字典中的少量原子的線性組合盡量精確地描述信號[1].這種能夠描述信號的字典又被稱為綜合型字典.最初提出的傳統(tǒng)字典模型并不是應(yīng)用于分類識別的，而是用于解決信號重構(gòu)的相關(guān)問題.為了試圖利用字典學(xué)習來解決分類識別問題，研究者們提出了多種方法，這些方法可以將傳統(tǒng)的字典學(xué)習修正為比較適合于分類識別任務(wù)的監(jiān)督字典學(xué)習.典型的基于字典學(xué)習的分類識別方法大致可以分為2類：一類是直接學(xué)習具有判別力的字典，利用表示誤差來進行最終的判決，其中具有代表性的方法有Meta-face學(xué)習[2]和結(jié)構(gòu)不相干的字典學(xué)習(DLSI)[3];另一類是稀疏化系數(shù)，使得到的字典更具可判別力，利用稀疏系數(shù)作為新的用于分類識別的表示特征，該類別中具有代表性的方法有監(jiān)督字典學(xué)習[4]、判決KSVD(D-KSVD)字典學(xué)習[5]、標簽一致的KSVD[6]和基于Fisher準則的字典學(xué)習(FDDL)[7].

在傳統(tǒng)的基于字典學(xué)習的分類識別方法中，通常都是利用綜合型字典和稀疏系數(shù)來表示一個信號，因此需要對編碼系數(shù)增加lp范數(shù)的約束(其中p≤1)，而這種范數(shù)約束的特點是計算復(fù)雜度較高.又因為稀疏編碼系數(shù)越稀疏分類識別結(jié)果越準確，所以在大部分的字典學(xué)習算法中，正則化稀疏表示系數(shù)均采用l0或者l1范數(shù)約束.易知，在字典學(xué)習的迭代過程中通常含有稀疏編碼的步驟，即每次迭代都需要處理編碼系數(shù)的l0或者l1范數(shù)，因此，這類算法的計算量都比較大，樣本訓(xùn)練和測試的效率都比較低.

在字典學(xué)習算法的效率提升研究方面，解析型字典學(xué)習逐漸引起廣大學(xué)者的關(guān)注.它是綜合型字典學(xué)習的對偶形式，核心思想是學(xué)習一個映射矩陣，使得信號在新的映射空間進行表示時能夠具有稀疏性.目前，這種模型還沒有較多地應(yīng)用到分類識別問題.最初，Gu等人[1]提出了DPL(dictionary pair learning)算法，該算法同時學(xué)習一個綜合型字典和解析型字典.其中，訓(xùn)練得到的綜合型字典用來實現(xiàn)特定類別的判別重構(gòu)，而訓(xùn)練得到的解析型字典通過對原始數(shù)據(jù)樣本進行線性映射來產(chǎn)生編碼系數(shù)，因而通過對解析型字典的約束就可以取代對稀疏編碼系數(shù)的l0或者l1范數(shù)約束，進而提升算法的效率.然而，DPL算法雖然提高了算法的整體運行效率，在準確率上也有很好的競爭力，但是該算法忽略了訓(xùn)練數(shù)據(jù)的局部特征對于分類識別的意義，本文在此基礎(chǔ)上提出了局部保持的綜合型-解析型字典對學(xué)習算法.該算法將字典對和訓(xùn)練樣本的局部結(jié)構(gòu)信息融合在一個學(xué)習框架內(nèi)，既提升了算法的分類識別準確率，也保證了算法的高效性.本文在3個國際公開測試圖像庫上驗證了本文所提出算法的性能.

1 相關(guān)的字典學(xué)習算法

本節(jié)將介紹幾種相關(guān)的字典學(xué)習算法.

1.1 綜合型字典學(xué)習算法

最初提出的DL模型并非應(yīng)用于分類識別，而是應(yīng)用于解決信號重構(gòu)的相關(guān)問題.學(xué)習一個自適應(yīng)的過完備字典，就是提供一個基本的集合，利用這個集合中的少量原子的線性組合可以近似描述一個輸入信號.

設(shè)一個樣本集合為X=[x1,…,xi,…,xN]，其中xi是樣本集中的第i個樣本.解析型字典學(xué)習方法旨在得到一個綜合型字典D和編碼系數(shù)A對樣本進行重構(gòu)表示，其過程可由式(1)實現(xiàn)：

(1)

其中，編碼系數(shù)矩陣A=[a1,…,aN]，ai是矩陣A的第i個列向量.矩陣A的1范數(shù)等價于A的各個列向量的1范數(shù)之和.

上述的傳統(tǒng)的綜合型DL方法并不是應(yīng)用于分類識別的，所以其在處理分類識別問題時產(chǎn)生的結(jié)果并不理想.為了專門解決分類識別問題，科研工作者們提出了有判別力的字典學(xué)習算法.

設(shè)X=[X1,…,Xk,…,XK]是所有類別的訓(xùn)練樣本的集合，每個樣本均是p維的特征，一共K個類別，Xk∈p×n是第k個類別的訓(xùn)練樣本的集合，n是每個類別中訓(xùn)練樣本的數(shù)量.利用訓(xùn)練數(shù)據(jù)的類別信息可以提升綜合型字典D的判別能力，進而改善傳統(tǒng)算法的分類識別性能，其表現(xiàn)在目標函數(shù)中是對D增加一個約束，可表示為式(2)模型：

(2)

上面已經(jīng)提到，基于綜合型DL的分類識別方法大致可以分為2類：一類是直接學(xué)習具有判別力的字典，利用各自的重構(gòu)誤差即可進行分類識別；另一類是通過提升稀疏表示系數(shù)的判別力來增強字典的判別力，并利用稀疏系數(shù)作為分類識別的新特征.無論是哪一類方法都需要對編碼系數(shù)矩陣A增加l0或者l1范數(shù)的稀疏正則項約束，進而導(dǎo)致算法的計算量較大，效率過低.

為了解決上述由于l0或者l1范數(shù)的稀疏正則項而產(chǎn)生的效率過低問題，解析型字典學(xué)習應(yīng)運而生.它通過學(xué)習一個映射矩陣，使得信號在新的映射空間具有稀疏的特性.這種模型還沒有較多地應(yīng)用到分類識別問題.Gu等人[1]提出了DPL模型，聯(lián)合學(xué)習綜合型字典D和解析型字典P.在DPL模型中，由于編碼系數(shù)可以由解析型字典P映射得到，于是系數(shù)矩陣A的l0或者l1范數(shù)約束就可以被忽略.實驗證明，DPL模型明顯地提高了訓(xùn)練樣本和測試樣本的編碼效率，同時仍然保持著較高的分類識別準確率.

1.2 DPL算法的基本原理

結(jié)構(gòu)化的綜合型字典D=[D1,…,Dk,…,DK]，結(jié)構(gòu)化的解析型字典P=[P1;…;Pk;…;PK]，則第k類樣本集合對應(yīng)的子字典對為{Dk∈p×m,Pk∈m×p}，這種字典對也叫作綜合型-解析型字典對.稀疏子空間聚類[8]的相關(guān)研究已經(jīng)證明，如果輸入數(shù)據(jù)滿足特定的不相干條件，則不同類別的樣本可以由它相應(yīng)的字典表示.由于解析型字典P是結(jié)構(gòu)化的，所以我們希望解析型子字典Pk對類別i(i≠k)中樣本的映射集合近似為空集合，即

PkXi≈0,?k≠i.

(3)

由式(3)可知，系數(shù)矩陣PX是分塊對角矩陣.此外，結(jié)構(gòu)化的綜合型字典D的子字典Dk可以通過映射得到的系數(shù)矩陣PkXk重構(gòu)數(shù)據(jù)矩陣Xk.由綜合型-解析型字典對表示的重構(gòu)誤差的最小化公式可表示為

(4)

繼而得到下面的映射字典對模型：

(5)

Gu等人[1]已經(jīng)證明，基于DPL算法的分類識別方法不僅有較高的分類識別準確率，還有非常高的運行效率.

2 局部保持“字典對”學(xué)習算法

為了提升傳統(tǒng)的有判別力的DL算法的分類識別準確率和運行效率，本文提出了局部保持的綜合型-解析型字典對學(xué)習算法，這個新提出的算法將高效的綜合型-解析型字典對學(xué)習算法與訓(xùn)練數(shù)據(jù)的局部結(jié)構(gòu)信息緊密地結(jié)合在一起.

2.1 局部保持約束

設(shè)N(xi)是樣本xi的C近鄰的集合，并且這C個近鄰指選自樣本xi所在的類別集合的樣本，近鄰數(shù)量C可以根據(jù)需要設(shè)定.為了保持訓(xùn)練樣本的局部近鄰信息，需要樣本xi的編碼系數(shù)ai在空間距離上接近同類別樣本的編碼系數(shù).又因為任意的樣本xj距離樣本xi的空間距離越遠，則對樣本xi的影響越小，即任意2個樣本之間的權(quán)重函數(shù)w(xi,xj)與2個樣本向量之間的空間距離成反比，所以我們定義2個樣本之間的權(quán)重函數(shù)為

(6)

其中，dist(xi,xj)表示樣本xi和樣本xj之間的歐氏距離，參數(shù)t可以調(diào)整權(quán)重函數(shù)的衰減速度，不失一般性，本文設(shè)置t的值為1.

權(quán)重矩陣Wi j定義為

(7)

為了能夠保持訓(xùn)練樣本的局部結(jié)構(gòu)信息，編碼系數(shù)A應(yīng)該滿足下述的優(yōu)化目標函數(shù)：

(8)

其中，編碼系數(shù)A=[a1,…,aN].

2.2 局部保持的綜合型-解析型字典對學(xué)習算法

基于上述的介紹，局部保持的綜合型-解析型字典對學(xué)習算法的目標函數(shù)可以表示為

(9)

其中,lk是第k類的訓(xùn)練樣本的個數(shù).

利用圖論里關(guān)于拉普拉斯矩陣的定義與性質(zhì)，可以在目標函數(shù)(9)中引入拉普拉斯矩陣，得到的化簡公式如下：

(10)

其中，Lk為拉普拉斯矩陣，τ，λ和β均為標量參數(shù).這3個參數(shù)數(shù)值的選擇對模型的訓(xùn)練有很直接的影響，后面的實驗部分會介紹最終確定的最優(yōu)參數(shù)組合.由于矩陣的跡與矩陣的Frobenious范數(shù)在特定條件下可以互相轉(zhuǎn)換，因而式(10)的目標函數(shù)很容易求解.首先初始化綜合型字典D和解析型字典P，令2個字典的初始矩陣是Frobenious范數(shù)等于1的任意矩陣，然后交替更新編碼系數(shù)矩陣A和綜合型-解析型字典對{D,P}.通過交替執(zhí)行以下步驟即可得到目標函數(shù)(10)的最優(yōu)解.

1) 固定D和P，更新A：

(11)

這是一個標準最小平方問題，可以得到閉式解：

(12)

2) 固定A，更新D和P：

(13)

由式(13)可以得到解析型字典P的閉式解：

(14)

其中γ=10-4是一個比較小的常數(shù)，I是單位陣，γI是為了保證求逆運算有解而增加的.求D的最優(yōu)解相對復(fù)雜，引入一個變量S后，D的優(yōu)化問題可以表示為

(15)

利用ADMM算法可以求得問題(15)的最優(yōu)解：

(16)

其中，參數(shù)ρ可適當進行調(diào)整.

綜上所述，求解優(yōu)化函數(shù)(10)，變量A和P均可得到閉式解，利用ADMM方法求D的優(yōu)化結(jié)果是迅速收斂的.算法1給出了局部保持的綜合型-解析型字典對學(xué)習算法的實現(xiàn)流程.當相鄰兩次迭代的結(jié)果差值小于0.01時，迭代停止.優(yōu)化結(jié)果輸出的解析型字典P和綜合型字典D可用于之后分類識別的判決.

算法1. 局部保持的綜合型-解析型字典對學(xué)習算法.

輸入：K個類別的訓(xùn)練樣本特征X=[X1,…,Xk,…,XK]，參數(shù)m，τ，λ，β，C，t;

輸出：解析型字典P，綜合型字典D.

① 初始化D(0)和P(0)，初始為Frobenious范數(shù)為1的隨機矩陣；

② WHILE 不收斂 DO

③ FORi=1:KDO

④ 根據(jù)式(12)更新Ak；

⑤ 根據(jù)式(14)更新Pk；

⑥ 根據(jù)式(16)更新Dk；

⑦ END FOR

⑧ END WHILE

2.3 分類識別方法的實現(xiàn)

(17)

由式(17)可知，基于局部保持的綜合型-解析型字典對學(xué)習算法的分類器的參數(shù)只需給定綜合型字典D和解析型字典P即可，所以在獲得各個類別的最優(yōu)綜合型子字典和最優(yōu)解析型子字典后，就能得到分類器的模型，從而可以對測試圖像進行分類識別.

3 實驗及結(jié)果

3.1 實驗設(shè)置及比較算法

本文選擇3個數(shù)據(jù)庫來評估局部保持的綜合型-解析型字典對學(xué)習算法的分類識別性能，分別是2個人臉庫(Extended YaleB人臉庫和AR人臉庫)，以及一個目標庫(Caltech101庫).在這3個數(shù)據(jù)庫中，本文將所提出的算法與許多效果較好的分類識別算法進行了比較，包括基本的最近子空間分類器(NSC)、線性支持向量機(SVM)、稀疏表示分類(SRC)和協(xié)同表示分類(CRC)，以及最先進的DL算法DLSI，F(xiàn)DDL，LC-KSVD.對比內(nèi)容不僅有分類識別準確率，還有訓(xùn)練時間和測試時間.由文獻[1]可知，Gu等人提出的DPL算法具有最高的效率，因此本文提出的算法的效率僅與DPL算法的效率進行比較.對比實驗的軟硬件環(huán)境為：工作頻率為2.6 GHz、內(nèi)存為128 GB的服務(wù)器； MATLAB R2013a計算平臺.

在實驗中，本文直接利用文獻[9]中Jiang等人提取好的特征進行訓(xùn)練和分類識別，各個比較算法中的實驗設(shè)置均與文獻[9]中的設(shè)置一致.本文所提出的局部保持的綜合型-解析型字典對學(xué)習算法在各個圖像庫中的參數(shù)設(shè)置如表1所示:

表1 本文算法的主要參數(shù)

3.2 分類識別性能的比較結(jié)果

3.2.1 Extended YaleB庫的實驗結(jié)果

Extended YaleB數(shù)據(jù)庫中有38人的人臉圖像，共2 414張.在每個類別中，隨機選擇32張人臉圖像作為訓(xùn)練樣本，剩下的作為測試樣本.在其他對比的DL算法中，每個類別的綜合型子字典的原子數(shù)都設(shè)為32.Jiang等人[9]提供的Extended YaleB庫的圖像特征是504維的.如表2所示，與各個算法相比，在Extended YaleB庫中，本文所提出的算法得到了最高的分類識別準確率.表3表明該算法的運行效率與DPL算法相當，且均遠高于其他算法.

表2 在3個數(shù)據(jù)庫上的分類識別準確率比較 %

表3 在3個數(shù)據(jù)庫上的運行時間比較 s

3.2.2 AR庫的實驗結(jié)果

AR數(shù)據(jù)庫共有2 600張人臉圖像，其中男女各50人，共有100類，每個類別中有26張圖像.在每個類別中，隨機選擇20張圖像作為訓(xùn)練樣本，剩下的6張圖像作為測試樣本.在其他對比的DL算法中，每個類別的綜合型子字典的原子數(shù)設(shè)為20.Jiang等人[9]提供的AR庫的圖像特征是540維的.如表2所示，在AR庫中，與其他算法相比，本文提出的算法有最高的分類識別準確率.并且由表3可知，該算法的運行效率與DPL算法的效率非常接近.

3.2.3 Caltech101庫的實驗結(jié)果

Caltech101數(shù)據(jù)庫中共有9 144張圖像，分為102個類別(包含101個普通的目標類別和一個背景類別).每個類別中的樣本圖像數(shù)量是不固定的，從31～800不等.在每個類別中隨機選擇30張圖像作為訓(xùn)練樣本，剩余圖像作為測試樣本，在其他對比的DL算法中，每個類別的綜合型子字典的原子數(shù)設(shè)為30.該實驗利用標準的詞包(BOW)+空間金字塔匹配(SPM)來提取Caltech101庫中圖像的特征.在3種不同大小的網(wǎng)格中提取SIFT算子來計算SPM特征，3種網(wǎng)格分別是1×1，2×2和4×4的.此外，采用基于編碼方式的矢量量化來提取中層特征，并用標準的最大池化方式來建立高維的池化特征.最后，通過主成分分析(PCA)將原始21 504維的高維數(shù)據(jù)降到3 000維.實驗結(jié)果如表2、表3所示，本文的方法依然可以達到DPL算法的性能.

4 結(jié) 論

本文將高效的綜合型-解析型字典對學(xué)習算法與訓(xùn)練數(shù)據(jù)的局部結(jié)構(gòu)信息結(jié)合在一個框架內(nèi)，提出了局部保持的綜合型-解析型字典對學(xué)習算法，并將其應(yīng)用在分類識別問題上.局部保持的綜合型-解析型字典對學(xué)習算法將綜合型-解析型字典對學(xué)習和訓(xùn)練數(shù)據(jù)的局部結(jié)構(gòu)關(guān)系結(jié)合在一起，每一步都能夠利用閉式解或快速迭代解，保證了該算法的高效性和準確率.在3個國際公開測試圖像庫中的分類識別實驗充分證明了本文的算法在解決人臉識別和圖像分類等問題上具有很好的性能，保持訓(xùn)練樣本的局部結(jié)構(gòu)信息可在一定程度上提高分類和識別的準確率.

[1]Gu Shuhang, Zhang Lei, Zuo Wangmeng, et al. Projective dictionary pair learning for pattern classification[C]Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2014: 793-801

[2]Yang M, Zhang L, Yang J, et al. Metaface learning for sparse representation based face recognition[C]Proc of the 17th IEEE Int Conf on Image Processing. Piscataway, NJ: IEEE, 2010: 1601-1604

[3]Ramirez I, Sprechmann P, Sapiro G. Classification and clustering via dictionary learning with structured incoherence and shared features[C]Proc of IEEE CVPR. Piscataway, NJ: IEEE, 2010: 3501-3508

[4]Mairal J, Ponce J, Sapiro G, et al. Supervised dictionary learning[C]Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2009: 1033-1040

[5]Zhang Q, Li B. Discriminative K-SVD for dictionary learning in face recognition[C]Proc of IEEE CVPR. Piscataway, NJ: IEEE, 2010: 2691-2698

[6]Jiang Z, Lin Z, Davis L S. Learning a discriminative dictionary for sparse coding via label consistent K-SVD[C]Proc of IEEE CVPR. Piscataway, NJ: IEEE, 2011: 1697-1704

[7]Yang M, Zhang L, Feng X, et al. Fisher discrimination dictionary learning for sparse representation[C]Proc of IEEE ICCV. Piscataway, NJ: IEEE, 2011: 543-550

[8]Soltanolkotabi M, Elhamifar E, Candes E J. Robust subspace clustering[J]. The Annals of Statistics, 2014, 42(2): 669-699

[9]Jiang Z, Lin Z, Davis L S. Label consistent K-SVD: Learning a discriminative dictionary for recognition[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2651-2664

郭艷卿

博士，副教授，主要研究方向為多媒體信息安全、計算機視覺、模式識別.

guoyq@dlut.edu.cn

王久君

碩士研究生，主要研究方向為圖像分類.

jiujun_wang@foxmail.com

郭 君

碩士研究生，主要研究方向為圖像分類.

eeguojun@foxmail.com

Locality Preserving Dictionary Pair Learning Algorithm for Classification and Recognition

Guo Yanqing, Wang Jiujun, and Guo Jun

(SchoolofInformationandCommunicationEngineering,DalianUniversityofTechnology,Dalian116024)

Dictionary learning (DL) has been widely applied in various computer vision problems. Most existing DL methods aim to learn a synthesis dictionary to represent the input signal while enforcing the representation coefficients andor representation residuals to be discriminative. However, thel0orl1-norm sparsity constraint on the representation coefficients adopted in most DL methods makes the learning phase time consuming. Hence, a new DL framework, namely analysis dictionary learning, has been proposed to deal with this problem. Besides, jointly learning a synthesis dictionary and an analysis dictionary has also drawn much attention recently, which can not only reduce the time complexity in the learning phase, but also lead to very competitive accuracy in a variety of classification and recognition tasks. This paper is motivated by the recently proposed dictionary pair learning algorithms. Our proposed novel Locality Preserving Discriminative Synthesis-Analysis Dictionary Pair Learning Algorithm integrates the local structure of training data, which is totally ignored in most applications of dictionary pair learning. We evaluate the proposed algorithm on three databases, including two face databases (Extended YaleB and AR) and one image categorization database (Caltech101). Based on the experiment results, we conclude that our algorithm can largely reduce the computational burden and improve the accuracies.

synthesis-analysis dictionary pair learning; Locality preserving; classification; recognition

2015-07-30

國家自然科學(xué)基金項目(61402079)

TP391.41