袁 超 李海洋

（西安工程大學(xué)理學(xué)院 西安 710048）

基于TL1范數(shù)的改進K-SVD字典學(xué)習(xí)算法?

袁 超 李海洋

（西安工程大學(xué)理學(xué)院 西安 710048）

K-SVD字典學(xué)習(xí)算法通過稀疏編碼和字典更新兩步迭代學(xué)習(xí)得到訓(xùn)練樣本的字典，用OMP（Orthogonal Matching Pursuit）算法求解稀疏表示，用SVD分解算法對字典更新。但應(yīng)用在圖像重構(gòu)時，OMP算法運行速度比較慢，且恢復(fù)的準(zhǔn)確度不夠高。針對該問題，為了提高字典訓(xùn)練速度與性能，在稀疏編碼階段用TL1范數(shù)代替了l0范數(shù)，用迭代閾值算法求解稀疏表示。為考察改進算法的恢復(fù)準(zhǔn)確率，在不同稀疏度下進行數(shù)據(jù)合成實驗，結(jié)果表明改進算法比K-SVD算法訓(xùn)練恢復(fù)的準(zhǔn)確率高。進一步考察改進算法的圖像重構(gòu)能力，選取標(biāo)準(zhǔn)圖像進行仿真，實驗結(jié)果表明改進算法比K-SVD算法能更快得到訓(xùn)練字典，獲得更高的峰值信噪比（PSNR），具有更好的重構(gòu)性能。

字典學(xué)習(xí)；KSVD；稀疏編碼；閾值迭代算法；TL1范數(shù)；圖像重構(gòu)

1 引言

近些年，以圖像的稀疏先驗求解圖像重構(gòu)引起了廣泛關(guān)注［1～3］。根據(jù)壓縮感知理論，信號在字典下的表示系數(shù)越稀疏則重構(gòu)質(zhì)量越高，因此字典的選擇十分重要，它決定了圖像重構(gòu)的質(zhì)量。目前字典構(gòu)造方法有兩種：解析方法和學(xué)習(xí)方法。基于解析方法構(gòu)造的字典通過定義好的數(shù)學(xué)變換或調(diào)和分析來構(gòu)造，字典中的每個原子可用數(shù)學(xué)函數(shù)來刻畫，如小波變換、離散余弦變換、輪廓波變換、Shear?let等。雖然解析方法構(gòu)造字典相對簡單且計算復(fù)雜度低，但原子的基本形狀固定，形態(tài)不夠豐富，因此不能與圖像本身的復(fù)雜結(jié)構(gòu)進行最佳匹配?；趯W(xué)習(xí)方法是根據(jù)圖像本身來學(xué)習(xí)過完備字典，這類字典中的原子與訓(xùn)練集中的圖像本身相適應(yīng)。因此通過學(xué)習(xí)獲得的字典原子數(shù)量更多，形態(tài)更豐富，能更好地與圖像本身的結(jié)構(gòu)匹配，具有更稀疏的表示。

1993 年，Mallat［4］等闡述了過完備字典的概念，并提出了解決過完備字典稀疏表示問題的匹配追蹤算法，從而奠定了字典學(xué)習(xí)理論的基礎(chǔ)，但沒有給出具體求解字典的方法。1996年Olshausen［5］在《Nature》上發(fā)表了Sparsenet字典學(xué)習(xí)算法，提出了用l1范數(shù)作為系數(shù)稀疏性度量，這一算法是基于字典學(xué)習(xí)重構(gòu)圖像的基礎(chǔ)，但該算法容易陷入局部最優(yōu)。為訓(xùn)練全局最優(yōu)字典，Mailhe［6］等對Olshausen的算法進行了改進，將梯度下降中的固定步長改為自適應(yīng)步長，從而越過局部最優(yōu)點，最終以較大的概率保證在全局最優(yōu)點收斂。Engan［7］也對Sparsenet字典學(xué)習(xí)算法進行了改進，提出了MOD（Method of optimal directions）字典學(xué)習(xí)算法。MOD算法采用l0范數(shù)衡量信號的稀疏性，利用交替優(yōu)化求解字典。該算法的缺點是需要進行矩陣的求逆計算，對存儲容量的要求高。

為減小 MOD算法的復(fù)雜度，2006 年 Elad［8］等提出了 K-SVD（K-singular value decomposition）字典學(xué)習(xí)算法，實現(xiàn)了基于K-SVD字典學(xué)習(xí)的圖像重構(gòu)，K-SVD字典學(xué)習(xí)是一種交替迭代算法，首先固定當(dāng)前字典稀疏編碼求解稀疏表示系數(shù)，然后根據(jù)稀疏系數(shù)對字典的列進行迭代更新。K-SVD算法更新字典時不是對整個字典一次更新，而是逐個原子更新。該算法不需要矩陣求逆計算，運算復(fù)雜度比MOD算法低，并且在字典更新步驟中對系數(shù)矩陣與字典原子聯(lián)合更新，提高了算法收斂速度。K-SVD算法在實際中有廣泛應(yīng)用，隨后許多 學(xué) 者 對 其 進 行 了 改 進 ，Rubinsteind［9］用Batch-OMP替代OMP稀疏編碼，比K-SVD字典訓(xùn)練效率更高，但圖像重構(gòu)效果卻有所下降。Smith［10］在字典更新中加入了支撐的先驗信息，提出了MDU多重字典更新算法，有效地減小了字典學(xué)習(xí)的目標(biāo)函數(shù)，但訓(xùn)練計算量較大。

當(dāng)前字典學(xué)習(xí)存在的主要問題是訓(xùn)練時間長，恢復(fù)的準(zhǔn)確度不夠高。針對這一問題，為提高字典學(xué)習(xí)的速度與性能，本文在稀疏編碼階段用TL1范數(shù)代替l0范數(shù)，用迭代閾值算法求解稀疏表示，提出TL1-KSVD字典學(xué)習(xí)算法。事實上，早在2000年Nikolola［11］在 研 究 變 量 選 擇 時 定 義 了 TL1范 數(shù)（transformedl0penalty），2009 年 Lv［12］研究了 TL1范數(shù)的稀疏性，2014年 Xin［13～14］等把 TL1范數(shù)應(yīng)用到壓縮感知，并給出了TL1范數(shù)的閾值迭代算法。

2 K-SVD字典學(xué)習(xí)模型

假設(shè)給定訓(xùn)練圖像Y∈RN×L包含 L個信號，字典學(xué)習(xí)的實質(zhì)是找到恰當(dāng)?shù)奈粗值?D∈RN×M（N＜M）并使得每個信號 yi可用字典D∈RN×M稀疏表示，其模型為

2.1 稀疏編碼

在該階段，固定字典D，尋找訓(xùn)練樣本Y在字典D上的稀疏表示系數(shù)X。稀疏表示的重構(gòu)稱為稀疏編碼，訓(xùn)練樣本Y上每一個信號 y∈RN可用字典D的原子線性表示。其稀疏表示模型［15］為

其中 D∈RN×M（N＜M）是一個字典，是 x∈RM稀疏的，式中：‖‖x0是為x中非零的個數(shù)。

可以使用貪婪追蹤算法求解問題（2），如正交匹配追蹤（OMP）［17～18］，但需要將原始信號內(nèi)的元素逐一稀疏表示，但OMP算法收斂速度較慢，且圖像重構(gòu)質(zhì)量差。求解問題（2）的精確解是一個NP［16］難問題，而且對噪音非常敏感。壓縮感知理論指出，如果觀測矩陣D滿足約束等距RIP［3］（Restrict?ed Isometry Proper）性質(zhì)，則可高概率重構(gòu)原始信號x，即：

式中，δk∈(0，1)稱為 RIP常數(shù)。

Donoho等［19］提出利用 l1范數(shù)代替 l0范數(shù)，變成線性規(guī)劃的凸優(yōu)化問題，找出最稀疏的系數(shù)矩陣。其模型為

式中：‖‖x1為x中元素的絕對值之和。

解決問題（4）可以通過無約束凸優(yōu)化問題近似求解，模型為

轉(zhuǎn)化為無約束凸優(yōu)化求解l1范數(shù)問題。使用基 追 蹤（BP，Basis Pursuit）［20］，F(xiàn)OCUSS［21］，LARS-Lasso［22］等算法求解，或者利用軟閾值截取運算（Soft-thresholding）［23］求解。然而基于 l1范數(shù)的求解稀疏表示至少仍存在兩個方面的不足：第一，圖像信號之間可能存在冗余難以去除；第二，無法區(qū)分稀疏尺度的位置。相關(guān)研究表明，用1/2范數(shù)等非凸函數(shù)代替l0范數(shù)時，有更好的效果。

2.2 字典更新

在字典更新階段應(yīng)用SVD的更新字典［6］，固定稀疏系數(shù)X，對字典D中的原子按列進行迭代更新。

3 基于TL1-KSVD的字典學(xué)習(xí)

我們?nèi)园阉Q作范數(shù)。另外因為滿足以下性質(zhì)：

1）ρ(x)遞增且在x∈[0，∞ )是凹的。

2）ρ′(x )在 ρ′(0 +)∈(0 ，∞ )是連續(xù)的。

因此‖*‖TL能產(chǎn)生稀疏的效果。

用TL1懲罰項代替式（5）中的l1懲罰項，則式（5）模型變?yōu)?/p>

為了求解優(yōu)化問題（6），J Xin等在文獻［25］中提出用閾值迭代算法，算法的迭代格式為

式中：xn為第 n 次近似值，μn為參數(shù)，Sp，λ:RN→RN是由特定的閾值函數(shù)誘導(dǎo)出的對角非線性閾值算子。并給出了該問題的閾值迭代函數(shù)，其閾值迭代函數(shù)如下

式中：

3.1 稀疏編碼

為了縮短稀疏編碼時間，提高字典訓(xùn)練速度和性能，引入速度較快的閾值迭代算法解決問題（6），算法流程如算法1所示。

算法1 基于TL1閾值迭代函數(shù)的稀疏編碼

輸入：信號Y∈RN×L，字典 D∈RN×M

初始化：x0，給一個合適的a，ε，μ0；

迭代步驟1：計算 zn=Bμ(xn)=xn+μDT(y-Dxn)，令 λ=λ0，μ=μ0；

3.2 字典更新

在字典更新階段應(yīng)用SVD的更新字典［8］，固定稀疏系數(shù)X，對字D中的原子按列進行迭代更新，字典列的更新結(jié)合稀疏表示的一個更新，使字典和稀疏系數(shù)同步更新。字典更新過程可表示優(yōu)化模型：

式中：‖‖xi0是計算xi中非零元素的個數(shù)：

通過對Ek進行SVD分解得到秩為1的矩陣近似值用于更新原子dk和稀疏表示對應(yīng)的系數(shù)，同步更新大大加速了訓(xùn)練算法的收斂速度?；赥L1-KSVD的字典學(xué)習(xí)算法的步驟，如算法2所示。

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

輸入：訓(xùn)練樣本集Y∈RN×L

迭代步驟1初始化字典：賦初始值給字典D；

2稀疏編碼：根據(jù)已知字典D，運用算法1求解樣本Y的稀疏系數(shù)X；

3字典更新：根據(jù)稀疏系數(shù) X，更新字典D。設(shè)為dk要更新的字典D的第k列原子，Ek代表抽取字典原子dk后的誤差矩陣。定義分解用到原子dk時所有 yi的索引集合。則：Ek=Y-(DX-dkxk)；

選取僅與ωk相關(guān)的列約束Ek，得到Eωkk，對其進行奇異值分解（SVD），更新 dk=u1，xk=?(1，1)·v1；

輸出：學(xué)習(xí)字典D，稀疏表示系數(shù)X。

4 實驗結(jié)果及分析

為了驗證本文算法重構(gòu)性能，對本文算法與K-SVD算法進行數(shù)據(jù)合成實驗和圖像重構(gòu)實驗對比分析。利用CPU為4GHz，內(nèi)存為16GB的計算機，通過Matlab R2010a仿真實現(xiàn)。實驗圖像為512×512像素，圖像分塊為8×8，字典大小為64×256。

采用字典訓(xùn)練時間、用峰值信噪比（PSNR）和圖像的重構(gòu)成功率作為衡量兩個算法性能評價標(biāo)準(zhǔn)。峰值信噪比（PSNR）：

其中MSE是原圖像與壓縮重建后圖像之間的均方誤差。圖像的重構(gòu)成功率：Aharon提出了計算成功恢復(fù)的準(zhǔn)則，這個準(zhǔn)則是為了計算兩個正則化元素之間的距離。用di來表示原始矩陣的第i列，di來表示重構(gòu)矩陣的第i列。如果1-|＜0.01，可以認為矩陣的第i得到了成功恢復(fù)。實驗圖像為512×512像素，圖像分塊為8×8，字典大小為64×256。下面列出了圖像的實驗結(jié)果對比。

4.1 數(shù)據(jù)合成實驗

為了驗證本文算法的成功恢復(fù)率，在不同稀疏度下反復(fù)實驗。并在相同稀疏度下與K-SVD算法的重構(gòu)效果進行比較。實驗中，用標(biāo)準(zhǔn)的Lena圖像進行采樣重構(gòu)，以加權(quán)的高斯隨機矩陣作為觀測矩陣，稀疏度K從10開始，每次增大5，用兩種算法對每個稀疏度K各進行100次實驗比較，并對求其平均值，實驗結(jié)果如圖1所示。

實驗分析：隨著稀疏度的增大，兩種算法的重構(gòu)成功率逐漸減小。與OMP算法相比，當(dāng)稀疏度較大時本文算法有著較為明顯的優(yōu)勢（如稀疏度K在40時，本文算法仍能恢復(fù)出原圖）。本文算法在重構(gòu)成功率上也有較大程度的提高，稀疏度K在20～35之間，其優(yōu)勢更為凸顯，比OMP重構(gòu)算法提高了6.8%～56.8%。

圖1 K-稀疏信號重構(gòu)準(zhǔn)確率

4.2 圖像重構(gòu)實例

為了考察本文算法重構(gòu)時間與重構(gòu)效果，在不同采樣率下反復(fù)實驗，并在相同采樣率下與K-SVD算法的重構(gòu)時間與重構(gòu)效果進行比較。對Lena圖像和peppers圖像進行8×8的分塊，以高斯隨機矩陣作觀測矩陣，最后對每個分塊圖像進行重構(gòu)恢復(fù)。

實驗中分別在0.4，0.6，0.8不同采樣率下進行測試。在同一采樣率下對每種算法反復(fù)進行150次試驗，獲得峰值信噪比PSNR值和運行時間，并對求其平均值，其測試結(jié)果，如表3、表4所示。

表3 Lena圖像在不同采樣率兩種算法PSNR值和運行時間比較

表4 peppers圖像在不同采樣率兩種算法PSNR值和運行時間比較

實驗分析：通過表3可以看出，在相同稀疏度時，隨著采樣率的增大，兩種算法的PSNR值均相應(yīng)增大，且在不同采樣率下本文算法的PSNR值較K-SVD算法均有較大程度的提高，在較小采樣率下效果尤為明顯，在采樣率為0.4時提高了2.12dB。同時，本文算法的運行速度也有了較大程度的提高，采樣率在0.4，0.6，0.8對比K-SVD算法提高了5.56s、7.14s、11.34s。表明隨著采樣率增大，本文算法的運行速度的增幅相對于K-SVD算法的運行速度的增幅越來越大。

二維圖像的重建仿真源圖像為512×512的Le?na圖和peppers圖，分別基于K-SVD算法和本文算法進行恢復(fù)重構(gòu)，其重構(gòu)結(jié)果如下圖所示，可見不同的采樣率下，本文算法重構(gòu)效果都好于K-SVD算法的重構(gòu)效果。如圖2所示。

圖2 二維圖像的重建仿真

5 結(jié)語

針對于K-SVD在圖像重構(gòu)中所存在的恢復(fù)準(zhǔn)確度不夠高以及稀疏編碼時間過長的問題，本文提出了基于TL1范數(shù)的改進的K-SVD字典學(xué)習(xí)模型。首先本文建立非凸極小化模型，提出了改進的字典學(xué)習(xí)算法，該方法利用非凸‖*‖TL范數(shù)求得的1稀疏表示，提升了字典訓(xùn)練速度與性能。其次圖像重構(gòu)實例結(jié)果表明與K-SVD字典學(xué)習(xí)算法相比，本文算法稀疏編碼速度更快，恢復(fù)的準(zhǔn)確度更高，重構(gòu)效果更好。由于完備字典的訓(xùn)練時間過長，因此如何訓(xùn)練更快速、更有效的字典是下一步工作的內(nèi)容。

［1］Dong Wei-sheng，Zhang Lei，Shi Guang-ming，et al.Non?locally centralized sparse representation for image restora?tion［J］.Image Processing，IEEE Transactions on，2013，22（4）：1620-1630.

［2］Yang M，Zhang L，F(xiàn)eng X，et al.Fisher Discrimination Dictionary Learning for sparse representation［C］//IEEE International Conference on Computer Vision，ICCV 2011，Barcelona，Spain，November.DBLP，2011：543-550.

［3］Candes E J，Romberg J，Tao T.Robust uncertainty princi?ples：exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Informa?tion Theory，2006，52（2）：489-509.

［4］Mallat S，Zhang Z.Matching pursuits with time-frequen?cy dictionaries［J］.IEEE Transactions on Signal Process?ing，1993，41（12）：3397-3415.

［5］Olshausen B A，F(xiàn)ield D J.Emergency of simple-cell re?ceptive field properties by learning a sparse code for natu?ral images［J］.Nature，1996，381（6583）：607-609.

［6］Mailhé B，Plumbley M D.Dictionary learning with large step gradient descent for sparse representations［C］//In：Proceedings of the 10th International Conference on La?tent Variable Analysis and Signal Separation.Berlin，Hei?delberg：Springer，2012.231-238.

［7］Engan K，Aase S O，Husoy J H.Method of optimal direc?tions for frame design［C］//IEEE International Conference on Acoustics，Speech，and Signal Processing，1999.Pro?ceedings.IEEE，1999：2443-2446 vol.5.

［8］Aharon M，Elad M，Bruckstein A M.The K-SVD：an algo?rithm for designing of over complete dictionaries for sparse representation［J］.IEEE Transactions on Signal Process?ing，2006，54（11）：4311-4322．

［9］Rubinstein R，Zibulevsky M，Elad M.Efficient implemen?tation of the K-SVD algorithm using batch orthogonal matching pursuit［J］.CS Technion，2008，40（8）：1-15．

［10］Smith L N，Elad M.Improving dictionary learning：Multi?ple dictionary updates and coefficient reuse［J］.Signal Processing Letters IEEE，2013，20（1）：79-82．

［11］NIKOLOVAM.Local strong homogeneity of a regularized estimator［J］.SIAM J Appl Math，2000，61（2）：633-658.

［12］Lv J，F(xiàn)an Y.A unified approach to model selection and sparse recovery using regularized least squares［J］.An?nals of Statistics，2009，37（6A）：3498-3528.

［13］Zhang S，Xin J.Minimization of Transformed$L_1$Pen?alty：Closed Form Representation and Iterative Thresh?oldingAlgorithms［J］.Mathematics，2014.

［14］S Zhang，J Xin.Minimization of Transformed L1 Penalty：Theory Difference of Covex Function Algorithm，and Ro?bust Application in CompressedSensing［EB/OL］.Eprint?Arwiv，2016.https：//arxiv.org/abs/1411.573.

［15］BrucksteinA M，Donoho D L，Elad M.From sparse solu?tions of systems of equations to sparse modeling of sig?nals and images［J］.SIAM Review，2009，51（1）：34-81.

［16］Donoho D L，Elad M，Temlyakov V N.Stable recovery of sparse over complete representations in the presence of noise［J］.Information Theory，IEEE Transactions on，2006，52（1）：6-18．

［17］Mallat S G，Zhang Z.Matching pursuits with time-fre?quency dictionaries［J］.Signal Processing，IEEE Trans?actions on，1993，41（12）：3397-3415．

［18］Tropp J.Greed is good：Algorithmic results for sparse ap?proximation［J］.Information Theory，IEEE Transactions on，2004，50（10）：2231-2242．

［19］Donoho D L.For most large underdeterzmined systems of linear equations the minimal 1-norm solution is also the sparsest solution［J］.Communicationson Pure and Ap?plied Mathematics，2006，59（6）：797-829．

［20］Chen S S，Donoho D L，Saunders M A.Atomic decompo?sition by basis pursuit［J］.SIAM Journal on Scientific Computing，1998，20（1）：33-61.

［21］Gorodnitsky I F，Rao B D.Sparse signal reconstruction from limited data using FOCUSS：A re-weighted mini?mum norm algorithm［J］.Signal Processing，IEEE Trans?actions on，1997，45（3）：600-616．

［22］Efron B，Hastie T，Johnstone I，et al.Least angle regres?sion［J］.The Annals of Statistics，2004，32（2）：407-499.

［23］戴瓊海，付長軍，季向陽.壓縮感知研究［J］.計算機學(xué)報，2011，34（3）：425-434.DAI Qionghai，F(xiàn)U Changjun，JI Xiangyang.Research on compressed sensing［J］.Chinese journal of computers，2011，34（3）：425-434.

［24］S Zhang，J Xin.Minimization of Transformed L1 Penalty：Closed Form Representation and Iterative Thresholding Algorithms， Mathematics， 2016https：//arxiv.org/abs/1412.5240.

K-SVD Dictionary Learning Algorithm Based on TL1Norm

YUAN Chao LI Haiyang
（School of Science，Xi'an Polytechnic University，Xi'an 710048）

K-SVD dictionary learning algorithm is employed to obtain the training dictionary by using sparse coding and dic?tionary updating iteratively，in which Orthogonal Matching Pursuit algorithm（OMP）is used to get the sparse expressions in the sparse coding stage，while the SVD algorithm is utilized to update the dictionary.However，when it is applied into the image recon?struction，the Orthogonal Matching Pursuit algorithm（OMP）is slower and its accuracy is not satisfied.Aiming at this problem，To improve the speed and performance of training dictionary，l0is replaced with TL1in the sparse coding stage，and the iterative thresh?old algorithm is used to the sparse expressions.To test the performance of the proposed algorithm，date synthesis experiment is con?ducted under different sparse degree，and these results show that the proposed algorithm is better than the K-SVD.To further test the performance of the proposed algorithm，the standard image is used to simulate and the experimental results show that the pro?posed algorithm is faster than K-SVD to obtain the training dictionary，and has higher PSNR and better reconstruction performance.

dictionary learning，K-SVD，threshold iterative algorithm，TL1norm，image reconstruction

Class Number TP301.6

TP301.6

10.3969/j.issn.1672-9722.2017.12.001

2017年6月5日，

2017年7月23日

國家自然科學(xué)基金項目（編號：11271297）；陜西省自然科學(xué)基金項目（編號：2015JM1012）資助。

袁超，男，碩士研究生，研究方向：圖像處理，機器學(xué)習(xí)。李海洋，博士，教授，研究方向：稀疏信息處理，量子邏輯及格上拓撲學(xué)。