基于正則化模型的K—SVD算法及其應(yīng)用

劉堅橋 唐加山

摘要：提出一種基于正則化方法的K均值奇異值分解（K-SVD）算法。新算法在更新字典階段，建立一種正則化模型，針對經(jīng)典K-SVD算法中每次原子更新，引入正則項參與字典更新過程，將每次更新原子所產(chǎn)生的誤差限制在設(shè)定范圍內(nèi)完成原子更新。在K-SVD算法正則化模型基礎(chǔ)上，對K-SVD的衍生算法近似K-SVD（Approximate K-SVD）進(jìn)行了研究，提出了適用于AK-SVD的正則化模型。實驗結(jié)果表明，新模型訓(xùn)練字典的誤差相較于傳統(tǒng)算法縮小了13.8%。將訓(xùn)練字典用于圖像去噪時發(fā)現(xiàn)，新模型下字典重構(gòu)出圖像的峰值信噪比（PSNR）比傳統(tǒng)算法提升0.5dB左右。

關(guān)鍵詞：K-SVD；正則化方法；字典學(xué)習(xí)；稀疏表示；圖像去噪

DOIDOI：10.11907/rjdk.173177

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）008-0114-04

英文摘要Abstract：A method of K Singular Value Decomposition （K-SVD） based on regularized model is proposed.The regularized term is introduced into the algorithm at the stage of updating atoms，which limits the training error to optimal level.Furthermore，some other algorithms improved from K-SVD can also be combined with the regularized model to promote their performance.The new model is implemented in signal reconstruction and image denoising in experiments.Simulation results show that compared with the traditional K-SVD，the RMSE of new method decrease by about 13.8% in signal set reconstruction，and the Peak Signal to Noise Ratio （PSNR） increase about 0.5dB in image denoising.

英文關(guān)鍵詞Key Words：K-SVD； regularization method； dictionary learning； sparse representation；image denoising

收稿日期收稿日期：2017-12-11

基金項目基金項目：

作者簡介作者簡介：劉堅橋（1993-），男，南京郵電大學(xué)通信與信息工程學(xué)院碩士研究生，研究方向為信號處理、壓縮感知；唐加山（1968-），男，博士，南京郵電大學(xué)理學(xué)院教授，研究方向為應(yīng)用概率統(tǒng)計、現(xiàn)代通信中的智能信號處理技術(shù)、信道辨識與均衡、復(fù)雜網(wǎng)絡(luò)。

0 引言

在稀疏表示領(lǐng)域，基于超完備冗余字典的信號稀疏分解[1]理論應(yīng)用較多，而字典學(xué)習(xí)算法優(yōu)化了冗余字典結(jié)構(gòu)，使得構(gòu)造出的字典能更好地適應(yīng)模型，極大提高了冗余字典的靈活性與實用性。

K-SVD字典學(xué)習(xí)算法是字典學(xué)習(xí)的經(jīng)典算法之一，由Aharon等[2]于2006年提出，在壓縮感知[3]、稀疏分解等領(lǐng)域得到廣泛應(yīng)用。與其它字典學(xué)習(xí)算法如MOD[4]等不同，K-SVD算法在更新字典時，對字典原子逐列進(jìn)行更新而非直接更新整個字典。在更新原子方式上，K-SVD采用了K-Means聚類算法[5]思想，結(jié)合SVD（奇異值分解）對原子進(jìn)行更新。SVD分解時間復(fù)雜度和空間復(fù)雜度都很高，而K-SVD每次原子更新都要進(jìn)行一次SVD分解，導(dǎo)致算法運行時費時費力。對此，Hartigan [6]等提出了一種近似K-SVD算法（AK-SVD）。AK-SVD算法以一定的精度損失換取算法在運行速度上的提升。

機器學(xué)習(xí)中經(jīng)常用正則化方法對學(xué)習(xí)模型進(jìn)行優(yōu)化[7]，通過對模型引入不同范數(shù)的正則項達(dá)到目的，F(xiàn)范數(shù)能防止學(xué)習(xí)模型過擬合[8]。本文通過將K-SVD算法與F范數(shù)正則化相結(jié)合，提出一種基于F范數(shù)正則化的K-SVD算法。

1 研究背景

K-SVD算法求解分為稀疏表示階段和字典學(xué)習(xí)階段。

3 實驗

本實驗的硬件環(huán)境是（4.0GHz，16GB），所有算法均采用MATLAB2016a實現(xiàn)。實驗分為信號集訓(xùn)練測試和算法的圖像去噪兩個部分。

實驗1：信號集訓(xùn)練測試。給定大小為20×50的初始字典，分別用K-SVD 、AK-SVD以及相應(yīng)的正則化模型進(jìn)行字典訓(xùn)練。通過改變算法迭代次數(shù)計算截止到第k次更新時所積累的均方根誤差RMSE：

其中，size表示字典大小，實驗中值為100，訓(xùn)練集Y的稀疏度為3，正則化參數(shù)設(shè)為0.05。整個算法重復(fù)30次，取平均值得到RMSE隨迭代次數(shù)的關(guān)系如圖1所示。

實驗2：將正則化K-SVD算法應(yīng)用到圖像去噪。實驗中正則化參數(shù)設(shè)為0.1，實驗先隨機構(gòu)造冗余DCT字典，再將字典進(jìn)行基于待處理圖片進(jìn)行在線字典學(xué)習(xí)，并將得到的字典用于圖像去噪。實驗處理了3幅帶噪聲圖片，采用峰值信噪比（PSNR）[15]衡量去噪水平，去噪效果如圖2所示。

由圖1可知，隨著迭代次數(shù)增加，所有算法字典訓(xùn)練的RMSE不斷縮小。當(dāng)?shù)螖?shù)達(dá)到128次左右時，所有算法的RMSE都減小到一個穩(wěn)定值，表明所有算法都已收斂。在收斂狀態(tài)時，R-KSVD （正則化K-SVD）的RMSE最小，而R-AKSVD （正則化AK-SVD）與K-SVD的RMSE比較接近且都大于正則化K-SVD，AK-SVD算法的RMSE遠(yuǎn)大于其它3種算法。實驗結(jié)果表明，正則化模型使得原有算法在字典訓(xùn)練時誤差更小，給K-SVD和AK-SVD帶來了精度上的提升，從而提高了字典的表達(dá)能力。

由圖2可知，正則化K-SVD在圖像去噪中表現(xiàn)良好。3幅帶噪聲圖去噪處理后信噪比提升明顯，處理后的圖片相較于原圖亮度雖有所下降，但原圖的細(xì)節(jié)都得到了恢復(fù)。實驗2表明正則化模型下的K-SVD在圖像去噪中保留了經(jīng)典K-SVD優(yōu)勢，能夠出色完成圖像去噪處理。

4 結(jié)語

本文提出一種K-SVD字典學(xué)習(xí)算法以及它的衍生算法AK-SVD的正則化模型。對模型進(jìn)行求解然后應(yīng)用到仿真實驗，實驗結(jié)果表明，正則化K-SVD算法能夠縮小訓(xùn)練誤差，提升原算法所得字典的表達(dá)能力。此外，正則化模型結(jié)合AK-SVD算法能夠在一定程度上彌補AK-SVD算法在字典表達(dá)能力上的不足。在圖像去噪中，正則化K-SVD性能稍優(yōu)于傳統(tǒng)K-SVD算法。正則化參數(shù)的選取一般在0.05～0.1之間效果較好，不同應(yīng)用場景下正則化參數(shù)的選取還有待進(jìn)一步研究。

參考文獻(xiàn)：

[1] 余南南.基于稀疏表示的圖像融合與去噪算法研究[D].大連：大連理工大學(xué)，2012.

[2] AHARON M，ELAD M，BRUCKSTEIN A.K-SVD：an algorithm for designing overcomplete dictio- naries for sparse representation [J].IEEE Transactions on Signal Process，2006，54（11）：4311-4322.

[3] DONOHO D L.Compressed sensing[J].IEEE Transactions on Information Theory，2006，52（4）：1289-1306.

[4] 練秋生，石保順，陳書貞.字典學(xué)習(xí)模型、算法及其應(yīng)用研究進(jìn)展[J].自動化學(xué)報，2015，41（2）：240-260.

[5] HARTIGAN J A，WONG M A.Algorithm AS 136：a K-means clustering algorithm[J].Journal of the Royal Statistical Society，Series C （Applied Statistics），1979，28（1）：100-108.

[6] RUBINSTEIN R， ZIBULEVSKY M，ELAD M.Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[C].Haifa：Cs Technion，2008.

[7] 朱軍，胡文波.貝葉斯機器學(xué)習(xí)前沿進(jìn)展綜述[J].計算機研究與發(fā)展，2015，52（1）：16-26.

[8] 吳頡爾.正則化方法及其在模型修正中的應(yīng)用[D].南京： 南京航空航天大學(xué)，2007 .

[9] 魏雅麗，溫顯斌，鄒永廖，等.基于稀疏分解和聚類的自適應(yīng)圖像去噪新方法[J].計算機應(yīng)用，2013，33（2）：476-479.

[10] 劉建偉，崔立鵬，劉澤宇，等.正則化稀疏模型[J].計算機學(xué)報，2015 （7）：1307-1325.

[11] 農(nóng)秀麗.齊次等式約束線性回歸模型回歸系數(shù)的綜合條件嶺估計[J].湖南師范大學(xué)自然科學(xué)學(xué)報，2012，35（2）：7-13.

[12] 呂琪.不適定問題的迭代正則化方法研究[D].武漢：武漢理工大學(xué)，2012.

[13] GOLUB G H，VAN LOAN C F.Matrix computations[M].fourth edition，Baltimore：JHU Press，2012.

[14] 豐明坤，趙生妹，邢超.一種基于視覺特性的PSNR圖像評價方法[J].南京郵電大學(xué)學(xué)報：自然科學(xué)版，2015，35（4）：33-38.

（責(zé)任編輯：杜能鋼）