基于優化字典設計的MOD字典學習算法

周 航，董西偉,2，荊曉遠

(1.南京郵電大學 自動化學院，江蘇 南京 210023;2.九江學院 信息科學與技術學院,江西 九江 332005)

1 概 述

近年來，隨著壓縮感知理論的發展，稀疏表示受到國內外眾多學者的廣泛研究。稀疏表示最初應用于信號處理領域，并成功地解決了很多該領域的問題，比如圖像去噪[1-2]、圖像壓縮[3-5]、圖像重構[6-7]等。Yang等[8]使用稀疏表示來解決信號的分類問題，通過將Fisher判別準則加入其目標函數，得到了具有良好判別性能并且可以重構信號的稀疏系數。在人臉識別[9-10]研究領域中，WRIGHT等[11]提出基于稀疏表示的分類(Sparse Representation based Classification，SRC)。SRC算法的基本原理是用訓練樣本構造過完備字典，然后用該字典中原子的線性組合來表示測試樣本，最后通過計算重構誤差進行分類識別。而為了解決SRC算法在處理非線性樣本時的不足，GAO等[12]提出基于核稀疏表示的分類(Kernel SRC，KSRC)。KSRC的基本原理是將非線性的樣本映射到高維的核空間中，在該空間中訓練樣本可以更輕易地線性表示出測試樣本。

在SRC算法中，字典學習是其關鍵環節，經過眾多學者的研究，現階段的字典構造方式主要有兩種：通過先驗知識構造字典；通過訓練樣本的自適應學習構造字典。ENGAN等[13]提出的最優方向法(Method of Optimal Directions，MOD)，是比較經典的字典學習算法之一。MOD是一種期望最大值的字典學習算法，該算法通過迭代在訓練過程中不斷更新字典原子，使稀疏表示的殘差不斷減小來滿足收斂條件，最終得到具有良好判別性能的字典。

在SRC算法中，字典性能的優異對于算法的識別率影響很大，因此在字典學習過程中，如何去除冗余的原子，得到性能更佳的字典是非常值得研究和探索的。基于此，文中通過在經典的MOD算法中加入聚類算法來優化字典的設計，提出一種增強型MOD算法(E-MOD)。傳統的MOD算法雖然可以通過迭代學習得到性能不錯的字典，但是在原始樣本集規模很大時，其并不能很好地解決字典過于冗余的問題。E-MOD算法在字典學習階段加入競爭聚集聚類算法(Competitive Agglomeration，CA)[14]，CA算法可以將原始數據集劃分為最少的簇數，并且簇中數據更加集中，因此通過CA算法的優化后，可以得到最優的劃分簇數。接著使用正交匹配追蹤算法(Orthogonal Matching Pursuit，OMP)[15]來逼近得到稀疏表示系數，最終得到的字典性能優越。

2 相關算法描述

2.1 OMP算法

OMP算法是匹配追蹤(MP)算法的改進，其選取最佳原子的方式類似于MP算法，都是用字典中與信號殘差最小的原子，不同的是其之后采用Gram-Schmidt進行正交化處理。

R0=gγj+R1

(1)

其中，gγj為字典中與信號殘差最小的原子。

選定原子，采用Gram-Schmidt做正交化處理：

(2)

此時，殘差Rj投影到pj上，得到：

(3)

上述過程經過t次迭代后，信號可以表示為：

(4)

2.2 CA算法

目前存在的聚類算法形式主要有兩種，一種是層次式聚類，一種是劃分式聚類。前者通過將數據按照一定的層次級別劃分為不同的簇，其可以細分為自頂向下分裂方式和自底向上的凝聚方式；后者通過預先指定聚類的數目或聚類的中心，然后在滿足迭代終止條件時結束聚類過程，得到最終的聚類結果。

CA算法從基本屬性上來看是屬于劃分式聚類的一種，而劃分式聚類是預先指定聚類中心，但CA算法聚類中心的確定方式類似于層次式聚類中的凝聚方式。由此可以得知，在充分利用兩種聚類方式的優點后，CA算法的性能更加優秀，因此聚類后的效果更佳。

(5)

其中，d2(xi,βj)表示樣本xi到中心βj的距離；uij表示樣本xi對聚類中心βj的隸屬度。

由上式可以看到，目標函數的前半部分與模糊C均值聚類算法(FCM)的目標函數相似，用來確定聚類簇中樣本的分布情況；后半部分是一個偏移項，用來尋找最佳的簇數。偏移項中參數α計算如下：

(6)

η(k)=η0exp(-k/τ)

(7)

其中，k為算法迭代次數；η0和τ為固定取值。

基于此，相較于其他聚類算法，通過優化CA算法的目標函數能得到更佳的聚類效果，即經過CA算法聚類后的簇集相對較少，并且其內部的距離也相對較小。因此，CA算法可以達到去除簇集過于冗余的效果，最終得到更佳的簇集。

2.3 MOD算法

(8)

其中，D=[g1,g2,…,gN]T為字典矩陣，gj為字典原子；wi為xi對應字典原子gj的稀疏系數；T0為稀疏表示系數中非零元素的個數。

MOD算法通過反復迭代來更新系數矩陣W和字典矩陣D。先使用OMP算法逼近結果，以此更新稀疏系數wi，再根據樣本X和稀疏系數矩陣W更新字典：

(9)

當滿足迭代停止條件時，輸出最終的字典D。

3 增強型MOD算法

在MOD算法中加入CA算法來優化字典的設計，利用CA算法的去除冗余能力得到性能更佳的字典。在MOD算法的稀疏編碼階段，用CA算法代替OMP算法來更新稀疏系數wj，將字典原子gj作為聚類中心，uij為樣本xi對字典原子gj的隸屬度，由此得到優化字典設計階段的目標函數為：

(10)

(11)

xi和gj間的歐氏距離為：

d2(xi,gj)=‖xi-gj‖2

(12)

MOD算法和CA算法之間由uij來聯系，uij和wj的關系定義如下：

(13)

(14)

固定D和X，得到：

(15)

為方便計算，假設τt值在連續迭代后沒有發生明顯的改變，將式(15)代入目標函數的約束中求解λs：

(16)

整理后得到：

(17)

將式(17)代入式(15)：

(18)

(19)

其中，u(update)和u(prune)由式(18)來定義。當u(update)占主導地位時，通過更新可以得到uij；當u(prune)占主導地位時，uij根據使用的gj增加或減少。

E-MOD算法的具體流程如下：

(1)給定訓練樣本集X∈Rn×N，字典矩陣D∈Rn×M，單位化X和D的每一列；

(2)稀疏編碼階段：通過式(19)計算隸屬度uij，再通過式(13)計算系數wj；

(3)字典學習階段：用上面計算得到的wj和式(8)來更新字典原子dj；

(4)滿足終止條件時停止迭代，得到系數矩陣W和字典D。

4 實 驗

本節將在AR以及CAS-PEAL人臉庫上進行實驗，通過對比實驗來驗證文中算法的有效性，使用的對比方法包括SRC、KSRC以及MOD。

4.1 圖像數據庫

AR庫中包含126人共4 000多張人臉圖像，為節約計算成本以及存儲空間，選取庫中100個人，每個人的26張圖片全部選取，對選取的圖片按行展開排成一列再進行降維操作，維數降到600。在E-MOD算法中，設置參數η0=5，τ=10。

CAS-PEAL人臉數據庫包含106個人共1 060張人臉圖像，同樣為節約計算成本，選取庫中80個人，并且對選取的圖片進行降維操作，將圖片降維到480。在E-MOD算法中，設置參數η0=6，τ=10。

4.2 實驗結果及分析

在AR數據庫中，隨機選取每個人的20張圖像作為訓練樣本，其余作為測試樣本；在CAS-PEAL數據庫中，隨機選取每個人的6張圖像作為訓練樣本，其余作為測試樣本。圖1和圖2分別為AR和CAS-PEAL數據庫上所有方法20次隨機實驗的識別率對比圖；表1為所有方法的平均識別率和方差。

圖1 AR數據庫上的識別率對比

方法平均識別率/%AR庫CAS-PEAL庫SRC83.31±4.3485.11±3.21KSRC85.14±3.6787.35±2.47MOD87.96±3.2589.69±2.93E-MOD91.67±2.4392.78±1.79

從圖1、圖2以及表1可以看出，文中算法有更好的分類性能。在AR庫上，E-MOD算法比SRC、KSRC以及MOD三個對比方法的平均識別率至少提高了8.36%(91.67%-83.31%)；在CAS-PEAL庫上，E-MOD算法比三個對比方法的平均識別率至少提高了7.67%(92.78%-85.11%)。實驗結果充分驗證了文中算法能有效地提高識別率。

5 結束語

在模式識別領域，通過大量的研究已經證實了在圖像分類問題上SRC算法的有效性。在SRC算法中，字典學習是其關鍵環節，文中在MOD算法的基礎上，引入一種優化字典設計的技術，提出一種增強字典學習能力的MOD算法(E-MOD)。先在稀疏編碼階段，通過CA算法來更新目標函數，以得到稀疏表示系數；然后在字典學習階段，根據稀疏系數更新字典，得到性能優異的字典。通過在AR以及CAS-PEAL人臉數據庫上的對比實驗對E-MOD算法進行了充分的驗證。

[1] 劉帥奇,胡紹海,肖 揚.基于稀疏表示的Shearlet域SAR圖像去噪[J].電子與信息學報,2012,34(9):2110-2115.

[2] 王金金,宋余慶,桂長青.基于小波變換和稀疏表示的圖像去噪[J].測控技術,2015,34(8):23-26.

[3] 蔡 紅.基于稀疏表示的SAR圖像壓縮方法研究[J].計算機工程與應用,2012,48(24):177-181.

[4] 雷 萌,張 環,王 弘.基于哈希表的稀疏圖像壓縮算法研究[J].軟件導刊,2013,12(9):50-52.

[5] 閆雪南,鄒建成.基于稀疏表示的人臉圖像壓縮方法[J].北方工業大學學報,2014,26(3):6-10.

[6] 李 雪,蔣愛民,劉小峰,等.基于稀疏表示的圖像超分辨率重構算法[J].微處理機,2014,35(1):41-45.

[7] 路錦正,吳 斌,張啟衡.正則化恢復聯合稀疏表示的圖像超分辨率重構[J].光電工程,2013,40(9):1-7.

[8] YANG J,WANG J,HUANG T.Learning the sparse representation for classification[C]//International conference on multimedia & expo.[s.l.]:IEEE,2011:1-6.

[9] 王東李.一種新的人臉識別算法[J].計算機技術與發展,2009,19(5):138-144.

[10] 趙振勇,王保華,王 力,等.人臉圖像的特征提取[J].計算機技術與發展,2007,17(5):221-224.

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

[12] GAO S,TSANG I W H,CHIA L T.Kernel sparse representation for image classification and face recognition[C]//European conference on computer vision.[s.l.]:[s.n.],2010:1-14.

[13] ENGAN K,AASE S O,HUSOY J H.Method of optimal directions for frame design[C]//International conference on acoustics,speech,and signal processing.[s.l.]:IEEE,1999:2443-2446.

[14] FRIGUI H,KRISHNAPURAM R.Clustering by competitive agglomeration[J].Pattern Recognition,1997,30(7):1109-1119.

[15] TROPP J A,GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4666.