局部保持“字典對”學習算法及其應用

郭艷卿 王久君 郭 君

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

?

局部保持“字典對”學習算法及其應用

郭艷卿 王久君 郭 君

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

(guoyq@dlut.edu.cn)

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

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

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

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

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

1 相關的字典學習算法

本節將介紹幾種相關的字典學習算法.

1.1 綜合型字典學習算法

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

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

(1)

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

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

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

(2)

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

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

1.2 DPL算法的基本原理

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

PkXi≈0,?k≠i.

(3)

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

(4)

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

(5)

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

2 局部保持“字典對”學習算法

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

2.1 局部保持約束

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

(6)

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

權重矩陣Wi j定義為

(7)

為了能夠保持訓練樣本的局部結構信息，編碼系數A應該滿足下述的優化目標函數：

(8)

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

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

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

(9)

其中,lk是第k類的訓練樣本的個數.

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

(10)

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

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

(11)

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

(12)

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

(13)

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

(14)

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

(15)

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

(16)

其中，參數ρ可適當進行調整.

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

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

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

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

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

② WHILE 不收斂 DO

③ FORi=1:KDO

④ 根據式(12)更新Ak；

⑤ 根據式(14)更新Pk；

⑥ 根據式(16)更新Dk；

⑦ END FOR

⑧ END WHILE

2.3 分類識別方法的實現

(17)

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

3 實驗及結果

3.1 實驗設置及比較算法

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

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

表1 本文算法的主要參數

3.2 分類識別性能的比較結果

3.2.1 Extended YaleB庫的實驗結果

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

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

表3 在3個數據庫上的運行時間比較 s

3.2.2 AR庫的實驗結果

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

3.2.3 Caltech101庫的實驗結果

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

4 結 論

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

[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

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

TP391.41