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

（1.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津300401；2.天津市電子材料與器件重點(diǎn)實(shí)驗(yàn)室，天津市300401）

一種改進(jìn)的K-SVD字典學(xué)習(xí)算法

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

（1.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津300401；2.天津市電子材料與器件重點(diǎn)實(shí)驗(yàn)室，天津市300401）

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

字典學(xué)習(xí)；K-SVD；稀疏編碼；增廣拉格朗日乘子法；ALM

0 引言

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

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

1 稀疏表示模型

稀疏表示模型[21]是假設(shè)1個(gè)信號(hào)可以描述為y Dx，其中是1個(gè)字典，是稀疏

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

式中：‖x‖0是l0范數(shù)為x中非零的個(gè)數(shù)；T0是非零數(shù)目的最大值．問(wèn)題 (1)可以被擴(kuò)展到一個(gè)集合的信號(hào)

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

式中：l1范數(shù)為x中非零元素的絕對(duì)值之和；T0是非零數(shù)目的最大值．問(wèn)題 (3)也可以擴(kuò)展到一個(gè)集合的信號(hào)

式中l(wèi)1范數(shù)為X中非零元素的絕對(duì)值之和．解決問(wèn)題 (3)和問(wèn)題 (4)可以通過(guò)無(wú)約束凸優(yōu)化問(wèn)題近似求解，模型為轉(zhuǎn)化為無(wú)約束凸優(yōu)化求解l1范數(shù)問(wèn)題．式中是一個(gè)很小的正數(shù)，表示權(quán)重的大?。?/p>

2 基于ALM-KSVD的字典學(xué)習(xí)

首先介紹增廣拉格朗日乘子法（ALM），對(duì)于一個(gè)約束優(yōu)化問(wèn)題：

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

2.1 稀疏編碼

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

其拉格朗日函數(shù)為

式 (10)是強(qiáng)凸函數(shù)，可以通過(guò)求解其偏微分函數(shù)來(lái)求解其最小值，解得

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

式 (12)可以化簡(jiǎn)為

解得

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

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

2.2 字典更新

在該階段應(yīng)用經(jīng)典K-SVD的字典更新[6]，根據(jù)稀疏系數(shù)X，對(duì)字典D中的原子進(jìn)行迭代更新，字典列的更新結(jié)合稀疏表示的一個(gè)更新，使字典和稀疏系數(shù)同步更新．K-SVD字典學(xué)習(xí)的本質(zhì)是范數(shù)的稀疏約束和奇異值分解（SVD）交替進(jìn)行，字典學(xué)習(xí)過(guò)程可用優(yōu)化問(wèn)題表示

式中：‖xi‖0是l0范數(shù)計(jì)算xi中非零元素的個(gè)數(shù)，T0是非零元素個(gè)數(shù)的最大值．

綜上，基于ALM-KSVD的字典學(xué)習(xí)算法的步驟如

表2 基于ALM-KSVD的字典學(xué)習(xí)Tab.2 Dictionary learning based on ALM-KSVD

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中，利用CPU為2GHz，內(nèi)存為2GB的計(jì)算機(jī)，通過(guò)MATLABR2010a仿真實(shí)現(xiàn)，取參數(shù)．對(duì)本文算法ALM-KSVD與經(jīng)典K-SVD算法進(jìn)行對(duì)比分析，采用字典訓(xùn)練時(shí)間、平均表示誤差（RMSE）、峰值信噪比（PSNR）作為性能評(píng)價(jià)標(biāo)準(zhǔn)．

3.1 數(shù)據(jù)合成實(shí)驗(yàn)

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

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

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

接下來(lái)選取L=1500個(gè)數(shù)據(jù)信號(hào)，對(duì)生成的信號(hào)加入不同等級(jí)SNR=10 dB，20dB，30dB，40dB，50 dB的高斯噪聲，迭代50次，測(cè)試結(jié)果如表4和圖2所示．實(shí)驗(yàn)結(jié)果表明噪聲在SNR=10dB，20dB，30 dB問(wèn)題時(shí)本文算法和經(jīng)典K-SVD算法的RMSE都減小了，而且本文算法RMSE比經(jīng)典K-SVD算法?。畯膱D2可以看到經(jīng)典K-SVD算法在SNR=40dB，50 dB時(shí)RMSE又增大，而本文算法RMSE值變化不大，說(shuō)明本文算法比經(jīng)典K-SVD算法穩(wěn)定性好，尤其是在小信噪比體現(xiàn)更明顯．

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

圖1 字典訓(xùn)練速度的比較Fig.1 Comparison of dictionary training speed

3.2 圖像去噪實(shí)例

為解決圖像去噪問(wèn)題，文獻(xiàn) [23]所采取的方法是使用稀疏和冗余表示訓(xùn)練字典，應(yīng)用K-SVD算法獲得一個(gè)字典有效地描述圖像內(nèi)容．為考察本文算法的去噪能力，進(jìn)行了實(shí)驗(yàn)驗(yàn)證并與經(jīng)典K-SVD算法比較．圖3顯示了5幅標(biāo)準(zhǔn)測(cè)試圖像分別為“barbara”，“boat”，“l(fā)ena”，“house”，“peppers”．對(duì)測(cè)試圖像g （256×256）加入均值為0標(biāo)準(zhǔn)差為的噪聲得到含噪圖像I，從含噪圖像中提取大小為8×8，L=62001的樣本集．為保證公平初始字典都為 DCT，迭代5次，得到近似去噪值，并將其在恰當(dāng)?shù)奈恢眠M(jìn)行加權(quán)平均取值得到輸出圖像 f．性能評(píng)級(jí)指標(biāo)峰值信噪比（PSNR）定義為．

表5 5幅測(cè)試圖像去噪結(jié)果Tab.5 The resultof five imagesaftervarious denoising tests

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

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

圖3 5幅用于測(cè)試的圖片F(xiàn)ig.3 Five imagesused for variousdenoising tests

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

以上的實(shí)驗(yàn)結(jié)果是在字典原子個(gè)數(shù)M=256的情形下得到的，為進(jìn)一步驗(yàn)證本文算法的有效性，對(duì)字典學(xué)習(xí)中的主要參數(shù)如字典大小進(jìn)行實(shí)驗(yàn)驗(yàn)證．考察一下在噪聲=15時(shí)不同字典原子數(shù)如64，128，256，512對(duì)去噪結(jié)果的影響．表6是不同字典大小的去噪結(jié)果比較，實(shí)驗(yàn)圖像是“barbara”和“l(fā)ena”，圖5展示了其PSNR值．

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

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

4 結(jié)論

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

[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，F(xiàn)ENG 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，F(xiàn)ield 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]戴瓊海，付長(zhǎng)軍，季向陽(yáng)．壓縮感知研究 [J]．計(jì)算機(jī)學(xué)報(bào)，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．

[責(zé)任編輯 代俊秋]

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

國(guó)家自然科學(xué)基金（61203245）；河北省自然科學(xué)基金（F2012202027）；河北省高等學(xué)?？茖W(xué)技術(shù)研究項(xiàng)目（Z2011142）

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

數(shù)字出版日期：2016-04-19 數(shù)字出版網(wǎng)址：http://www.cnki.net/kcms/detail/13.1208.T.20160419.1019.002.htm l