基于字典學(xué)習(xí)和結(jié)構(gòu)聚類(lèi)的圖像去噪算法研究

潘慧+霍智勇++陳詩(shī)雨++程成

摘要：針對(duì)K-SVD算法和BM3D算法的不足，本文提出了基于字典學(xué)習(xí)和結(jié)構(gòu)聚類(lèi)的圖像去噪算法。該算法首先通過(guò)字典學(xué)習(xí)得到含噪圖像的冗余字典，然后對(duì)相似的圖像塊進(jìn)行聚類(lèi)構(gòu)成塊群，并通過(guò)迭代收縮和L1正則化約束，對(duì)同類(lèi)的圖像塊在字典上進(jìn)行稀疏表示，以達(dá)到降噪的目的。實(shí)驗(yàn)結(jié)果表明，在常規(guī)的圖像處理上，本文提出的算法能較好的保留圖像的結(jié)構(gòu)信息，與K-SVD和BM3D等現(xiàn)有的流行算法相比，具有更高的峰值信噪比（PNSR）。

關(guān)鍵詞：字典學(xué)習(xí)；結(jié)構(gòu)聚類(lèi)；圖像去噪；稀疏表示

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）14-0155-04

Research in Image Denoising Algorithm based on Dictionary Learning and Structural Clustering

PAN Hui， HUO Zhi-yong， CHEN Shi-yu， CHENG Cheng

（Nanjing University of Posts and Telecommunications， Nanjing 210046， China）

Abstract： For the purpose of overcoming the weak points of K-SVD algorithm and BM3D algorithm， we propose the image denoising algorithm based on dictionary learning and structural clustering.It firstly get the redundant dictionary of a noised image by dictionary learning.Then，the image patches are gathered according to their similarities.Meanwhile，the similar patches get sparse representation showed in dictionaries by iterative shrinkage and L1 regularization constraints and eventually the image is restored and noise is removed.The experimental results indicate that the proposed algorithm can well preserve the structure information of the common image with a higher Peak Signal to Noise Ratio（PNSR），compared with state-of-the-art algorithms，such as K-SVD and BM3D.

Key words： dictionary learning；structural clustering；image denoising；sparse representaion

在傳輸和接收?qǐng)D像的過(guò)程中，由于噪聲的干擾，常常會(huì)導(dǎo)致圖像的結(jié)構(gòu)信息被破壞、清晰度降低、圖像質(zhì)量下降等問(wèn)題。因此，圖像去噪一直是圖像處理領(lǐng)域的重點(diǎn)研究對(duì)象。

針對(duì)圖像去噪的正則化問(wèn)題有局部和非局部?jī)煞N去噪算法。局部去噪算法表明：在希爾伯特空間（字典[Φ∈Rn×m]）中，一個(gè)信號(hào)[x∈Rn]可被分解為一個(gè)n維向量集合，即[xn×1=Φn×mαm×1]，其中[α]代表權(quán)重向量，[α]的稀疏性可由它的L0范數(shù)或更易計(jì)算的L1范數(shù)描述[1]，這種研究涉及了基函數(shù)的構(gòu)造，字典的自適應(yīng)學(xué)習(xí)（例如：K-SVD[2][3]，以及隨機(jī)逼近[4]）。非局部去噪算法表明：自然圖像含有自重復(fù)模式，利用重疊塊的自相似性可以得到許多非局部圖像去噪算法——例如，非局部中值[5]，BM3D[6][7]，局部學(xué)習(xí)字典K-LLD[8]（locally learned dictionaries），LSSC[9]（learned simultaneous sparse coding）。在這一系列的算法中，K-SVD算法和BM3D算法一直擁有較高的峰值信噪比（Peak Signal to Noise Ratio，PNSR）。因此，我們認(rèn)為，聯(lián)合稀疏性與聚類(lèi)性可能會(huì)更有效的解決圖像去噪問(wèn)題。

由此，本文提出了基于字典學(xué)習(xí)和結(jié)構(gòu)聚類(lèi)的圖像去噪算法。該算法提供了一種新模型——基于聚類(lèi)的稀疏表示（clustering-based sparse representation，CSR）。CSR模型的基本思想是把局部和非局部稀疏約束視作同類(lèi)，即合并字典學(xué)習(xí)和結(jié)構(gòu)聚類(lèi)。首先通過(guò)字典學(xué)習(xí)得到含噪圖像的冗余字典，然后對(duì)圖像塊進(jìn)行相似性的計(jì)算，并據(jù)此對(duì)圖像塊進(jìn)行聚類(lèi)，隨后通過(guò)迭代收縮和L1正則化約束，對(duì)同類(lèi)的圖像塊在字典上進(jìn)行稀疏表示，從而達(dá)到降噪的目的。實(shí)驗(yàn)結(jié)果表明，在常規(guī)的圖像處理上，本文提出的算法能較好的保留圖像的結(jié)構(gòu)信息，與K-SVD和BM3D等現(xiàn)有的流行算法相比，具有更高的峰值信噪比（PNSR）。

1 基于聚類(lèi)的稀疏表示基本思想

1.1基于聚類(lèi)的稀疏表示模型

沿用參考文獻(xiàn)[2]中使用的符號(hào)格式，首先建立圖像[X]與稀疏系數(shù)集合[α=αi]之間的聯(lián)系，用[xi]來(lái)表示從圖像[X]的空間位置[i]處選取的圖像塊。得到如下公式：

[xi=RiX] （1）

這里的[Ri]表示一個(gè)矩形的窗口操作，在發(fā)生重疊的情況下，這種基于塊的表示是高度冗余的。同時(shí)，[xi]復(fù)原成[X]可以用一個(gè)超定方程組來(lái)表示，同時(shí)，對(duì)于一個(gè)給定的詞典[Φ]，[xi=Φαι]，從而獲得如下的最小二乘解：

[X=Dα=iRTiRi-1iRTiΦαi] （2）

這里的[D]是對(duì)偶于[R]的算子，在圖像去噪的背景下，得到如下的變分問(wèn)題：

[α=argminα12Y-Dα22+λα1] （3）

通過(guò)觀(guān)察發(fā)現(xiàn)，稀疏系數(shù)[α]不是隨機(jī)分布的（如圖1所示），他們位置的不確定性常常與圖像信號(hào)的非局部自相似性相關(guān)，這意味著我們可以利用位置相關(guān)約束來(lái)增強(qiáng)圖像信號(hào)的稀疏性。

a）一張規(guī)則紋理的圖像 b）稀疏系數(shù)的空間分布

這種非線(xiàn)性約束是位置相關(guān)的，因此，聚類(lèi)是利用這種非線(xiàn)性約束的一種合理方法?，F(xiàn)存的文獻(xiàn)中也存在大量聚類(lèi)算法，例如：K-means算法、K-NN分類(lèi)算法、譜聚類(lèi)算法、圖像分割算法。然而，數(shù)據(jù)聚類(lèi)和稀疏表示是在不同層級(jí)下得出的方法（分別是高層級(jí)和低層級(jí)），為進(jìn)一步了解非局部自相似性如何能夠促進(jìn)稀疏性，提出以下的成本函數(shù)研究：

[α，μ=argminα，μk12Y-Dα22+λ1α1+λ2k=1Ki∈CkΦαi-μk22] （4）

[μk]代表系數(shù)[α]的第[k]個(gè)簇[Ck]的質(zhì)心，公式（4）表示基于聚類(lèi)的正則化項(xiàng)，加權(quán)系數(shù)[α]是相對(duì)于[μk]的重新編碼。隨著進(jìn)一步的壓縮，利用非局部自相似性的結(jié)果，可以得到更為稀疏的表示。此前關(guān)于BM3D和LSSC的研究都是基于聚類(lèi)和稀疏表示的類(lèi)似算法，但是它們的關(guān)聯(lián)性相對(duì)較弱。為了更好地表示新型正則化項(xiàng)的含義，重寫(xiě)公式（4），如下所示：

[α，β=argminα，μk12Y-Dα22+λ1α1+λ2k=1Ki∈CkΦαi-ΦβK22] （5）

這里[μk=Φβk]，受壓縮感知算法的影響（參考文獻(xiàn)[1]），在新型正則化項(xiàng)中用L1范數(shù)來(lái)替代L2范數(shù)，得到如下公式：

[α，β=argminα，μk12Y-Dα22+λ1α1+λ2k=1Ki∈Ckαi-βk1] （6）

由上述可知，CSR模型提供了一種將字典學(xué)習(xí)參數(shù)[αi]和結(jié)構(gòu)聚類(lèi)參數(shù)[βk]統(tǒng)一表示在一個(gè)變分框架下的新方法，該方法利用[αi]的結(jié)構(gòu)冗余來(lái)得到更高的稀疏性。基于對(duì)[βk]的理解，它是通過(guò)結(jié)構(gòu)聚類(lèi)學(xué)習(xí)得到的，并且在更高層級(jí)下進(jìn)行編碼形成的模型。

1.2 L1最小化的迭代加權(quán)和正則化

本文的一個(gè)主要技術(shù)貢獻(xiàn)是通過(guò)迭代算法交替更新[α]和[β]，解決了公式中的雙頭L1優(yōu)化問(wèn)題。借鑒替代函數(shù)[10]的思想，導(dǎo)出一個(gè)用于更新[α]和[β]的迭代收縮算子：

[α（i+1）j=ST1，T2（v（i）j）-ST1，T2（-v（i）j）βj≥0βj≤0] （7）

[V（i）=1cDT（x-Dα（i））+α（i）] （8）

其中，[Τ1=λ1c，T2=λ2c]（[c]是一個(gè)保證替代函數(shù)凸性的輔助參數(shù)），上標(biāo)[i]表示迭代次數(shù)，下標(biāo)[j]表示矢量中第[j]個(gè)向量的輸入。結(jié)果表明，迭代收縮同樣適用于分別相關(guān)于局部和非局部的兩個(gè)正則參數(shù)的情況，迭代收縮在計(jì)算上的高效性使CSR模型得以完善。

與此同時(shí)，借鑒變分圖像去噪[11]和加權(quán)L1優(yōu)化[12]等相關(guān)文獻(xiàn)中的思想，自適應(yīng)地調(diào)整兩個(gè)正則參數(shù)[T1，T2]。我們采用下述策略來(lái)更新[T1，T2]：

[T1=c1σ2wσα，T2=c2σ2wσγ] （9）

這里，[σ2w]是噪音方差，[γ=α-β]，[c1]和[c2]是兩個(gè)給定的常數(shù)（通常假設(shè)[c1

受最近的相關(guān)工作[13]的啟發(fā)，建議通過(guò)下式來(lái)更新恢復(fù)圖像算法：

[X（i+1）=S（（1-δ）X（i）+δY）] （10）

此處[S=D?S?R]表示正則約束集合上的投影。

[（1-δ）X（i）+δY=X（i）+δ（Y-X（i））] （11）

上式是實(shí)現(xiàn)迭代正則思想的算子，[δ]是一個(gè)控制反饋到迭代的噪聲級(jí)的的小正數(shù)。

1.3 CSR算法的貝葉斯解釋

[CSR]的基本思想是，假設(shè)可以將[K]個(gè)簇的質(zhì)心視作稀疏系數(shù)[α]的隱變量的對(duì)等物，其實(shí)質(zhì)是[β]用于解決構(gòu)成基礎(chǔ)圖像信號(hào)的不確定性問(wèn)題。因此，可以制定以下最大后驗(yàn)估計(jì)（MAP）：

[（α，β）=argmaxα，βlogP（Yα，β）+P（α，β）] （12）

上式兩項(xiàng)分別與可能性和先驗(yàn)分布相對(duì)應(yīng)，第一項(xiàng)可以簡(jiǎn)單地通過(guò)降解模型[Y=X+W]描述，即

[P（Yα，β）=12πσwexp（-12σ2wY-Dα22）] （13）

通過(guò)獨(dú)立同分布的拉普拉斯分布去建造[α]和[γ]的模型，先驗(yàn)?zāi)Ｐ涂梢酝ㄟ^(guò)下式給出：

[P（α，β）=i12σαexp（-αi1σα）×ki12σγexp（-α-βk1σγ）] （14）

此處[γ=α-β]定義了聚類(lèi)的偏差數(shù)，把公式（13）和公式（14）代入公式（12），得

[（α，β）=argminα，βY-Dα22+22σ2wσαiαi1+22σ2wσγkiαi-βk1] （15）

設(shè)[λ1=22σ2wσα，λ2=22σ2wσγ]，它等同于前面推導(dǎo)出的公式（4）。

2 基于聚類(lèi)的稀疏表示去噪算法

2.1算法完整描述

算法1：基于字典學(xué)習(xí)和結(jié)構(gòu)聚類(lèi)的圖像去噪算法

初始化：[X=Y]；

外循環(huán)（字典學(xué)習(xí)）：[i=1，2，…，I]；

-通過(guò)K-means 和 PCA更新[Φ]；

內(nèi)循環(huán)（結(jié)構(gòu)聚類(lèi)）：[j=1，2，…，J]；

-迭代正則化：[X=X+δ（Y-X）]；

-正則化參數(shù)更新：通過(guò)公式（12）獲得[T1，T2]的新估計(jì)值；

-質(zhì)心估計(jì)跟新：通過(guò)kNN聚類(lèi)獲得[βk]的新估計(jì)值；

-圖像估計(jì)更新：通過(guò)[X=D?S?RX]獲得[X]的新估計(jì)值；

2.2算法流程圖

首先，輸入原始圖像，并對(duì)其添加高斯噪聲以得到噪聲圖像。接著，進(jìn)入外循環(huán)，利用K-SVD算法思想進(jìn)行字典學(xué)習(xí)得到冗余字典[Φ]和稀疏系數(shù)[α]的表達(dá)式，并通過(guò)K-means和PCA來(lái)更新字典。隨后，進(jìn)入內(nèi)循環(huán)，利用BM3D算法思想進(jìn)行結(jié)構(gòu)聚類(lèi)以得到[β]的表達(dá)式，并通過(guò)迭代正則化進(jìn)一步更新正則化參數(shù)，更新質(zhì)心估計(jì)和圖像估計(jì)值，最后，輸出去噪后的圖像，算法流程圖如圖2所示。

3 實(shí)驗(yàn)與分析

3.1實(shí)驗(yàn)初始化

我們?cè)贛ATLAB上執(zhí)行了CSR去噪算法，實(shí)驗(yàn)使用了下列參數(shù)：block-size [B]= 7， [λ] = 0.03， dictionary-size [K]= 64 ，[I]= [J]= 3。簡(jiǎn)言之，我們的CSR算法可以看成是字典學(xué)習(xí)（類(lèi)似于K-SVD）和結(jié)構(gòu)聚類(lèi)（類(lèi)似于BM3D）的復(fù)合，在CSR算法中，字典的更新是通過(guò)K-means和PCA，進(jìn)行聚類(lèi)的變換系數(shù)為二級(jí)稀疏編碼。

3.2三種去噪算法去噪效果圖像和數(shù)據(jù)的比較

對(duì)于這種規(guī)則紋理圖形，CSR的表現(xiàn)顯著優(yōu)于BM3D和K-SVD。如圖3所示，CSR的PSNR增益分別高出1.97分貝和0.77分貝。當(dāng)圖片高度自我重復(fù)時(shí)，字典學(xué)習(xí)比結(jié)構(gòu)聚類(lèi)起著更重要的作用，如果把它們結(jié)合在一起，就可以得到更好的效果。

我們對(duì)12幅圖像在不同的噪聲級(jí)下比較了CSR和K-SVD，BM3D的去噪效果。圖3～5分別為其中的2幅圖像在[σw]= 20時(shí)的噪聲圖像?？疾靾D中的細(xì)節(jié)，如D34中的黑色噪點(diǎn)，C.Man中人像周?chē)妮喞?，House中房屋墻壁的紋理，本文算法得到的重構(gòu)圖像更加清晰。表1給出了其中6幅圖像在更多噪聲級(jí)下的PNSR比較結(jié)果。由表1可知，三種算法在圖像質(zhì)量的數(shù)學(xué)指標(biāo)上，本文的算法是最好的。

本次實(shí)驗(yàn)使用Monarch圖像進(jìn)行測(cè)試，比較了SA-DCT，K-SVD，BM3D和CSR四種去噪算法隨著噪聲均方差[σ]變化時(shí)的PSNR值。從圖6可以看出，隨著[σ]的增大，PSNR值逐漸降低，但是[σ]越大，其對(duì)去噪效果的影響越小。我們可以更加直觀(guān)地看出，與現(xiàn)有的流行算法（K-SVD，BM3D和SA-DCT）相比，CSR具有更高的峰值信噪比。

4 結(jié)束語(yǔ)

針對(duì)K-SVD算法和BM3D算法的不足，本文提出了基于字典學(xué)習(xí)和結(jié)構(gòu)聚類(lèi)的圖像去噪算法。該算法首先通過(guò)字典學(xué)習(xí)得到含噪圖像的冗余字典，然后對(duì)相似的圖像塊進(jìn)行聚類(lèi)構(gòu)成塊群，并通過(guò)迭代收縮和L1正則化約束，對(duì)同類(lèi)的圖像塊在字典上進(jìn)行稀疏表示，以達(dá)到降噪的目的。CSR算法體現(xiàn)了將全局思考與局部適配結(jié)合在一起的好處，實(shí)驗(yàn)結(jié)果表明，在常規(guī)的圖像處理上，本文提出的算法能較好的保留圖像的結(jié)構(gòu)信息，峰值信噪比（PSNR）也優(yōu)于現(xiàn)有的流行算法，具有較好的視覺(jué)效果。但是，本文提出的算法的計(jì)算量較大，需要進(jìn)一步改進(jìn)，與此同時(shí)，稀疏性與聚類(lèi)性的微妙關(guān)系仍然需要我們進(jìn)一步研究！

參考文獻(xiàn)：

[1] E. J. Cande`s， J. K. Romberg， and T. Tao.Robust uncertainty principles： exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Infor- mation Theory， 2006，52（2）：489–509.

[2] M. Elad and M. Aharon.Image denoising via sparse and redundant representations over learned dictionaries[J].IEEE Trans. on Image Proc.， 2006，15（12）：3736-3745.

[3] Romano Y，Elad M.Improving K-SVD denoise by post-processing its method-noise[C]//Proc of International Conference on Image Processing，2013：435-439.

[4] J. Mairal， F. Bach， J. Ponce， G. Sapiro.Online dic- tionary learning for sparse coding[J].in Proceedings of the 26th Annual International Conference on Machine Learning， 2009， ：689-696.

[5] A. Buades， B. Coll， and J.-M. Morel. A non-local algorithm for image denoising[J]. CVPR， ，2005（2）：60-65.

[6] K. Dabov， A. Foi， V. Katkovnik， K. Egiazarian.Image denoising by sparse 3-d transform-domain collaborative filtering[J].IEEE Trans. on Image Processing，2007，16（8）：2080-2095.

[7] Burger H C.Schuler C J.Harmeling.S.Image denoising：Can plain neural networks compete with BM3D[C]//Proc of International Conference of Computer Vision and Pattern Recognition，2012：2392-2399.

[8] P. Chatterjee and P. Milanfar. Clustering-based denoising with locally learned dictionaries，[J].Image Processing， IEEE Transactions on， 2009，18（7）：1438-1451.

[9] J. Mairal， F. Bach， J. Ponce， G. Sapiro， et al.Non-local sparse models for image restoration[C].in 2009 IEEE 12th International Conference on Computer Vision，2009：2272-2279.

[10] I. Daubechies， M. Defrise， and C. De Mol.An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[J]. Communications on Pure and Applied Mathematics， 2004，57（11）：1413-1457.

[11] N. Galatsanos and A. Katsaggelos.Methods for choosing the regularization parameter and estimating the noise vari- ance in image restoration and their relation[J]. IEEE Transac- tions on Image Processing， 1992，1（3）：322-336.

[12] E. Candes， M. Wakin， S. Boyd， et al.Enhancing sparsity by reweighted l1 minimization[J].Journal of Fourier Analy- sis and Applications， 2008，14（5）：877-905.

[13] S. Osher， M. Burger， D. Goldfarb， et al.An iterative regularization method for total variation-based image restoration[J]. Multiscale Modeling and Simulation， ，2005，4（2）：460–489.