一種改進的K-SVD字典學習算法

劉雅莉，馬 杰，王曉云，苑煥朝

（1.河北工業大學 電子信息工程學院，天津300401；2.天津市電子材料與器件重點實驗室，天津市300401）

一種改進的K-SVD字典學習算法

劉雅莉1,2，馬 杰1,2，王曉云1,2，苑煥朝1,2

（1.河北工業大學 電子信息工程學院，天津300401；2.天津市電子材料與器件重點實驗室，天津市300401）

提出了一種ALM-KSVD字典學習算法，通過稀疏編碼和字典更新兩步迭代學習得到訓練樣本的字典．為了提高字典訓練速度與性能，在稀疏編碼引入增廣拉格朗日乘子法（ALM，Augmented LagrangeMultipliers）求解，更新字典則使用經典K-SVD的字典更新算法．為考察算法的字典訓練速度和平均表示誤差（RMSE），選取了不同樣本數和噪聲標準進行數據合成實驗，結果表明本文算法比經典的K-SVD算法字典訓練速度快、RMSE低．進一步考察算法的圖像去噪能力，選取不同的輸入圖像噪聲標準和字典原子數進行仿真，實驗結果表明本文算法比經典的K-SVD算法獲得更高的峰值信噪比（PSNR），具有良好的去噪性能．

字典學習；K-SVD；稀疏編碼；增廣拉格朗日乘子法；ALM

0 引言

近年來信號的稀疏表示研究引起了越來越多的關注[1-2]．為了實現信號的稀疏表示，給定一組訓練信號，使用一個包含信號信息的字典，信號由少量的字典原子線性組合表示．字典可以通過預先定義的一組基函數（DCT基、Gabor基等）產生，也可以通過某種算法學習得到．學習型字典能夠自適應的根據訓練樣本構造基函數，而且稀疏重構誤差小于固定基字典．1996年Olshausen等[3]在《Nature》上發表了著名的Sparsenet字典學習算法，該算法奠定了字典學習的基礎．Engan等[4]對Olshausen的字典學習算法進行了改進，提出了MOD（Method ofoptimaldirections）字典學習算法，并將其應用在語音數據和心電圖數據重構上，取得了良好效果．為減小MOD算法的復雜度，Elad等5在2006年提出了K-SVD（K-singular value decomposition）算法，實現了基于K-SVD字典學習的填寫缺失像素、壓縮及圖像去噪、修復等．K-SVD字典學習是1種迭代算法，固定當前字典進行稀疏編碼求解稀疏系數，根據稀疏系數對字典的列進行迭代更新，字典列的更新結合稀疏表示一個更新，從而加速收斂．在稀疏編碼求解稀疏系數時，在當前固定字典下是1個NP難問題6．一種簡單的方法是使用貪婪追蹤算法，如匹配追蹤（MP，Matching Pursuit）或正交匹配追蹤（OMP，Orthogonal Matching Pursuit）[7-8]等，直接求解l0范數問題．另一種方法是使用l1范數近似代替l0范數,如基追蹤（BP，Basis Pursuit）[9]及其變形FOCUSS[10]，LARS-Lasso[11]等．經典K-SVD字典學習在實際中應用最廣，許多學者對其進行了改進．Rubinsteind等[12]在稀疏編碼步驟中采用Batch-OMP（Batch-OrthogonalMatching Pursuit）替代OMP（Orthogonal Matching Pursuit)，比經典K-SVD字典訓練效率更高，但圖像去噪效果卻有所下降．Smith等[13]在字典更新中加入支撐完整的先驗信息，提出了多重字典更新（DUC，Dictionary UpdateCycles）算法，有效地減小了字典學習的目標函數，提升了字典訓練速度與性能．

前面提到的稀疏表示問題涉及到了最小化l1范數問題，最小化l1范數往往涉及軟閾值截取運算（Softthresholding）[14]．具體的算法包括加速近似梯度算法（APG，Accelerated ProximalGradient）[15]、交替方向乘子法（ADMM，Alternating Direction Method of Multipliers）[16]、Bregman迭代法[17]和增廣拉格朗日乘子法（ALM，Augmented LagrangeMultiplier）[18]等．Honglak等[19]在求解字典更新時采用拉格朗日對偶算法，加快了收斂速度．Adler[20]等在稀疏編碼異常檢測時引入交替方向乘子法（ADMM）求解，充分利用ADMM使目標函數可分離的結構特點，對其中兩項交替求最小化，該算法與增廣拉格朗日乘子法類似．增廣拉格朗日乘子法（ALM，Augmented Lagrange Multipliers）[17-18]經研究證明，該算法比其他算法收斂速度快，而且可以達到更高的精度，同時需要較低的存儲空間．當前字典學習特別是K-SVD方法存在的主要問題是字典訓練時間長，計算量大．針對這一問題，為提高字典學習的收斂速度與性能，本文提出一種ALM-KSVD字典學習算法．在稀疏編碼引入速度快的增廣拉格朗日乘子法（ALM）求解，更新字典則使用經典K-SVD的字典更新，通過稀疏編碼和字典更新兩步迭代學習得到字典．

1 稀疏表示模型

稀疏表示模型[21]是假設1個信號可以描述為y Dx，其中是1個字典，是稀疏

的．因此，y被D的一些原子的線性組合表示．稀疏表示的重構稱為稀疏編碼，其模型為

式中：‖x‖0是l0范數為x中非零的個數；T0是非零數目的最大值．問題 (1)可以被擴展到一個集合的信號

求解問題 (1)或 (2)的精確解是一個NP難問題，典型的做法是應用追蹤算法尋找近似解．最簡單的方法是使用貪婪追蹤算法（如MP或OMP）直接求解l0范數，但是需要將原始信號內的元素逐一稀疏表示，而且重構時每次恢復都有微小的誤差，信號重構質量差．Donoho等[22]提出利用l1范數代替l0范數，變成線性規劃的凸優化問題，找出最稀疏的系數矩陣，這種方法稱為松弛法．其模型為

式中：l1范數為x中非零元素的絕對值之和；T0是非零數目的最大值．問題 (3)也可以擴展到一個集合的信號

式中l1范數為X中非零元素的絕對值之和．解決問題 (3)和問題 (4)可以通過無約束凸優化問題近似求解，模型為轉化為無約束凸優化求解l1范數問題．式中是一個很小的正數，表示權重的大?。?/p>

2 基于ALM-KSVD的字典學習

首先介紹增廣拉格朗日乘子法（ALM），對于一個約束優化問題：

其中：f:RnR；h:RnRm．其增廣拉格朗日函數為

2.1 稀疏編碼

在該階段，字典D固定，尋找訓練樣本Y在字典D上的稀疏系數X．貪婪算法的計算復雜度低，但是信號重構質量差．松弛法雖然比貪婪算法信號重構的質量好，缺點是計算復雜度較高，收斂速度慢．為了縮短稀疏編碼時間，提高字典訓練速度和性能，引入速度較快的增廣拉格朗日乘子法（ALM）解決問題 (5)．加入輔助變量Z，無約束優化問題轉化為有約束優化問題．問題 (5)轉化為

其拉格朗日函數為

式 (10)是強凸函數，可以通過求解其偏微分函數來求解其最小值，解得

Zk+1的更新方式是固定最小化以下方程

式 (12)可以化簡為

解得

其中Suf表示軟閾值算子，定義如下

表1 基于ALM的稀疏編碼的算法流程Tab.1 Flow chartof sparse coding based on ALM

2.2 字典更新

在該階段應用經典K-SVD的字典更新[6]，根據稀疏系數X，對字典D中的原子進行迭代更新，字典列的更新結合稀疏表示的一個更新，使字典和稀疏系數同步更新．K-SVD字典學習的本質是范數的稀疏約束和奇異值分解（SVD）交替進行，字典學習過程可用優化問題表示

式中：‖xi‖0是l0范數計算xi中非零元素的個數，T0是非零元素個數的最大值．

綜上，基于ALM-KSVD的字典學習算法的步驟如

表2 基于ALM-KSVD的字典學習Tab.2 Dictionary learning based on ALM-KSVD

3 實驗結果及分析

實驗中，利用CPU為2GHz，內存為2GB的計算機，通過MATLABR2010a仿真實現，取參數．對本文算法ALM-KSVD與經典K-SVD算法進行對比分析，采用字典訓練時間、平均表示誤差（RMSE）、峰值信噪比（PSNR）作為性能評價標準．

3.1 數據合成實驗

為了檢測本文算法的性能，首先使用仿真合成數據測試字典訓練時間和平均表示誤差（RMSE），并將其與經典K-SVD進行比較．應用文獻 [6]中的實驗，首先生成一組基，由M=50個維數為N=20的基向量組成，每一列都標準化．然后取L個數據信號組成樣本集，每個信號由3個不同生成字典原子的線性組合表示，其稀疏系數的位置和值都是隨機獨立同分布的．對生成的信號加入等級SNR=30dB的高斯噪聲，選取不同數目的樣本集L，迭代50次．實驗結果如表3和圖1所示．

表3 不同樣本集字典訓練速度與RMSETab.3 The valuesof dictionary training speed and RMSE with differentsample sets

實驗分析：本文算法比經典K-SVD算法字典訓練速度快，當加入SNR=30dB的高斯噪聲時本文算法RMSE比經典K-SVDS算法減0.01．圖1表明樣本集數目越大本文算法比經典K-SVD速度快體現的越明顯，當選取L=62 001，本文算法比經典K-SVD算法快3倍．

接下來選取L=1500個數據信號，對生成的信號加入不同等級SNR=10 dB，20dB，30dB，40dB，50 dB的高斯噪聲，迭代50次，測試結果如表4和圖2所示．實驗結果表明噪聲在SNR=10dB，20dB，30 dB問題時本文算法和經典K-SVD算法的RMSE都減小了，而且本文算法RMSE比經典K-SVD算法?。畯膱D2可以看到經典K-SVD算法在SNR=40dB，50 dB時RMSE又增大，而本文算法RMSE值變化不大，說明本文算法比經典K-SVD算法穩定性好，尤其是在小信噪比體現更明顯．

表4 不同SNR值字典訓練速度與RMSETab.4 The valuesof dictionary training speed and RMSE with different SNR SNR/dB

圖1 字典訓練速度的比較Fig.1 Comparison of dictionary training speed

3.2 圖像去噪實例

為解決圖像去噪問題，文獻 [23]所采取的方法是使用稀疏和冗余表示訓練字典，應用K-SVD算法獲得一個字典有效地描述圖像內容．為考察本文算法的去噪能力，進行了實驗驗證并與經典K-SVD算法比較．圖3顯示了5幅標準測試圖像分別為“barbara”，“boat”，“lena”，“house”，“peppers”．對測試圖像g （256×256）加入均值為0標準差為的噪聲得到含噪圖像I，從含噪圖像中提取大小為8×8，L=62001的樣本集．為保證公平初始字典都為 DCT，迭代5次，得到近似去噪值，并將其在恰當的位置進行加權平均取值得到輸出圖像 f．性能評級指標峰值信噪比（PSNR）定義為．

表5 5幅測試圖像去噪結果Tab.5 The resultof five imagesaftervarious denoising tests

實驗分析：比較本文算法和經典K-SVD算法在加入不同等級噪聲時的去噪效果．表5顯示了本文算法和K-SVD算法在噪聲范圍[5～100]之間得到的去噪結果，可以發現在大部分噪聲等級下本文算法要比K-SVD好，獲得較高的PSNR．算法在噪聲=15時5幅測試圖像輸出PSNR平均值比經典K-SVD算法高0.26 dB．圖4顯示了在噪聲=15時2種算法對“barbara”的去噪效果，只截取了圖像一部分，算法明顯比經典K-SVD算法效果好，去噪后得到的圖像清晰．

圖2 RMSE的比較Fig.2 Comparison of RMSE between ALM-KSVD and OMP-KSVD

圖3 5幅用于測試的圖片Fig.3 Five imagesused for variousdenoising tests

圖4 去噪效果Fig.4 The image denoised

以上的實驗結果是在字典原子個數M=256的情形下得到的，為進一步驗證本文算法的有效性，對字典學習中的主要參數如字典大小進行實驗驗證．考察一下在噪聲=15時不同字典原子數如64，128，256，512對去噪結果的影響．表6是不同字典大小的去噪結果比較，實驗圖像是“barbara”和“lena”，圖5展示了其PSNR值．

表6 不同字典大小去噪結果Tab.6 The denoising resultof the dictionary w ith differentsizes

圖5 不同字典大小去噪結果的PSNR值Fig.5 PSNR of the dictionaryw ith differentsizesafter denoising test

4 結論

本文提出了一種ALM-KSVD字典學習算法，在稀疏編碼引入增廣拉格朗日乘子法（ALM）求解，更新字典則使用經典K-SVD的字典更新，稀疏編碼和更新字典兩步迭代學習得到字典．本文算法提升了字典訓練速度與性能，圖像去噪實例結果表明與經典K-SVD算法相比，本文算法去噪效果更好．由于超完備字典的訓練受諸多因素影響，且訓練時間長，因此如何訓練更快速、更有效地字典是下一步工作的內容．

[1]Dong Wei-sheng，Zhang Lei，ShiGuang-m ing，etal．Nonlocally centralized sparse representation for image restoration[J]．Image Processing，IEEE Transactionson，2013，22（4）：1620-1630．

[2]YANG Meng，ZhANG Lei，FENG Xiang-chu，et al．Fisher discrim ination dictionary learning for sparse representation[C]//Computer Vision （ICCV），2011 IEEE InternationalConferenceon．IEEE，2011：543-550．

[3]Olshausen BA，Field D J．Emergency ofsimple-cell receptive field propertiesby learning asparse code fornatural images[J]．Nature，1996，381 （6583）：607-609．

[4]Engan K，Aase SO，Hakon Husoy J．Method of optimal directions for frame design[C]//Acoustics，Speech and Signal Processing，1999．Proceedings．1999 IEEE InternationalConferenceon．IEEE，1999，5：2443-2446．

[5]Aharon M，Elad M，Bruckstein A M．The K-SVD：an algorithm for designing of over complete dictionaries for sparse representation[J]．IEEE Transactionson SignalProcessing，2006，54（11）：4311-4322．

[6]Donoho D L，Elad M，Tem lyakov V N．Stable recovery of sparseover complete representations in the presenceof noise[J]．Information Theory，IEEE Transactionson，2006，52（1）：6-18．

[7]MallatSG，Zhang Z．Matchingpursuitsw ith time-frequency dictionaries[J]．SignalProcessing，IEEETransactionson，1993，41（12）：3397-3415．

[8]Tropp J．Greed isgood：A lgorithmic results forsparseapproximation[J]．Information Theory，IEEETransactionson，2004，50（10）：2231-2242．

[9]Chen SS，DonohoD L，SaundersM A．Atomic decompositionbybasispursuit[J]．SIAM Journalon Scientific Computing，1998，20（1）：33-61．

[10]Gorodnitsky IF，Rao B D．Sparse signal reconstruction from limited data using FOCUSS：A re-weightedm inimum norm algorithm[J]．Signal Processing，IEEETransactionson，1997，45（3）：600-616．

[11]Efron B，Hastie T，Johnstone I，etal．Leastangle regression[J]．The Annalsof Statistics，2004，32（2）：407-499．

[12]RubinsteinR，Zibulevsky M，EladM．Efficientimplementationof theK-SVD algorithm usingbatchorthogonalmatchingpursuit[J]．CSTechnion，2008，40（8）：1-15．

[13]Sm ith LN，Elad M．Improving dictionary learning：Multipledictionary updatesand coefficientreuse[J]．SignalProcessing Letters，IEEE，2013，20（1）：79-82．

[14]戴瓊海，付長軍，季向陽．壓縮感知研究 [J]．計算機學報，2011，34（3）：425-434．

[15]Beck A，TeboulleM．A fastiterativeshrinkage-thresholding algorithm for linear inverseproblems[J]．SIAM journalon imaging sciences，2009，2（1）：183-202．

[16]Yuan X，Yang J．Sparseand low-rankmatrix decomposition viaalternating directionmethods[J]．Pacific JournalofOptim ization，2009，9（1）．

[17]YinW，Osher S，Goldfarb D，etal．Bregman iterativealgorithms for1-m inim izationw ith applications to compressed sensing[J]．SIAM Journal on Imaging Sciences，2008，1（1）：143-168．

[18]Lin Z，ChenM，MaY．Theaugmented lagrangemultipliermethod forexactrecoveryofcorrupted low-rankmatrices[J]．EprintArxiv，2010，9．

[19]LeeH，BattleA，RainaR，etal．Efficientsparse codingalgorithms[C]//Advances in Neural Information Processing Systems．2006：801-808．

[20]Adler A，Elad M，Hel-Or Y，etal．Sparse codingw ith anomaly detection[C]//Machine Learning for Signal Processing（MLSP），2013 IEEE InternationalWorkshop on．IEEE，2013：1-6．

[21]Bruckstein AM，Donoho D L，Elad M．From sparsesolutionsofsystemsofequations to sparsemodelingofsignalsand images[J]．SIAM Review，2009，51（1）：34-81．

[22]Donoho D L．Formost largeunderdetermined systemsof linearequations them inimal1-norm solution isalso thesparsestsolution[J]．Communications on Pureand Applied Mathematics，2006，59（6）：797-829．

[23]Elad M，AharonM．Imagedenoising viasparseand redundantrepresentationsover learned dictionaries[J]．ImageProcessing，IEEETransactions on，2006，15（12）：3736-3745．

[責任編輯 代俊秋]

An improved K-SVD dictionary learning algorithm

LIU Yali1,2，MA Jie1,2，WANG Xiaoyun1,2，YUAN Huanchao1,2

(1.Schoolof Electronic and Information Engineering,HebeiUniversity of Technology,Tianjin300401,China;2.Key Laboratory of Tianjin Electronic Materialsand Devices,Tianjin 300401,China)

Animprovementof K-SVD dictionary learning algorithm has been proposed,through the two-stage iteration of sparse coding and dictionary update.In order to improve the dictionary training speed and performance,Augmented Lagrangianmultipliermethod(ALM)is introduced in the sparse coding stage,while the standard K-SVD dictionary updating algorithm isused in thedictionary updating stage.In thiswork,the dictionary training speed and root-mean-square error(RMSE)of the algorithm are investigated in the synthesis date experimentby selecting different sample sets and noisestandards.The resultsshow thatthealgorithm isbetter than thestandard K-SVD dictionary learning,which receives faster training speed and lowerRMSE.In order to investigate the image denoising ability of thealgorithm,simulation experiment is carried outby selecting different input image noise standards and the atomic numbers of the dictionary.The algorithm showshigherpeak signal-to-noise ratio(PSNR)and betterdenoising performance than thestandard K-SVD algorithm.

dictionary learning;K-SVD;sparse coding;Augmented Lagrangianmultipliermethod;ALM

TP391.9

A

1007-2373(2016)02-0001-08

10.14081/j.cnki.hgdxb.2016.02.001

2015-09-11

國家自然科學基金（61203245）；河北省自然科學基金（F2012202027）；河北省高等學?？茖W技術研究項目（Z2011142）

劉雅莉（1989-），女（漢族），碩士生．通訊作者：馬杰（1978-），男（回族），副教授，博士．

數字出版日期：2016-04-19 數字出版網址：http://www.cnki.net/kcms/detail/13.1208.T.20160419.1019.002.htm l