低字典相干性K-SVD算法研究?

牛 彪 李海洋

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

1 引言

圖像是一種重要的信息源，隨著科學(xué)技術(shù)的發(fā)展，越來(lái)越多高質(zhì)量的圖片被社會(huì)所需要，因此圖像去噪是廣大研究工作者最為關(guān)心的問(wèn)題。圖像去噪的基本思想為通過(guò)抑制噪聲，提高圖像質(zhì)量從而來(lái)滿足對(duì)圖片更高層次的要求，針對(duì)該問(wèn)題，國(guó)內(nèi)外研究學(xué)者展開(kāi)了一系列的研究，而基于圖像稀疏表示理論的方法一直被廣泛關(guān)注，如Donoho等［1］提出了著名的小波閾值方法；2001年Romberg等［2］在小波域下利用隱馬爾可夫模型達(dá)到了去噪的目的；Portilla［3］則通過(guò)建立一種高斯混合模型來(lái)實(shí)現(xiàn)去噪；06年Arthur等［4］提出了一種新的MGA方法：無(wú)下采樣Contourlet變換（NSCT），并通過(guò)Bayesian估計(jì)方法實(shí)現(xiàn)圖像去噪。這些方法都取得了初步的成效。

2006年 Elad等［5］提出了 K-SVD（K-singular value decomposition，K-SVD）字典學(xué)習(xí)算法，它的目的主要是通過(guò)固定當(dāng)前字典進(jìn)行稀疏編碼求解稀疏系數(shù)，進(jìn)一步根據(jù)稀疏系數(shù)對(duì)字典的原子進(jìn)行更新，采用交替迭代的思想，從而訓(xùn)練得到一個(gè)新的過(guò)完備字典（over complete-dictionary）。該字典是通過(guò)學(xué)習(xí)訓(xùn)練得到的，若直接應(yīng)用于圖像去噪，由于字典相干性較高，會(huì)導(dǎo)致學(xué)習(xí)字典中噪音原子和無(wú)噪原子相似度高，去噪后的圖像有噪音殘留或者圖像較平滑，并且K-SVD字典學(xué)習(xí)算法計(jì)算復(fù)雜度較高［6］。而相干性約束是過(guò)完備字典學(xué)習(xí)算法中不可忽視的一個(gè)重要因素。一般而言，字典的相干性和其稀疏編碼性能有緊密的關(guān)系，在相同的冗余度條件下，低相干性可加快稀疏編碼的速度，改善信號(hào)的重構(gòu)性能［7］。此外，低相干性還有助于避免字典原子對(duì)訓(xùn)練樣本的過(guò)擬合，避免字典中出現(xiàn)過(guò)于相似的原子對(duì)。

為降低字典的自相干性，Mailhe［8］提出非相干K-SVD（Incoherent K-SVD，INK-SVD）字典學(xué)習(xí)算法，在字典更新步驟中，對(duì)原子進(jìn)行操作，如果發(fā)現(xiàn)某一對(duì)原子的相干性大于指定的相關(guān)性門(mén)限，則對(duì)兩個(gè)原子進(jìn)行旋轉(zhuǎn)達(dá)到降低其相干性的目的，但是該算法在字典學(xué)習(xí)過(guò)程中相似的原子進(jìn)行旋轉(zhuǎn)比較耗時(shí)，且其計(jì)算復(fù)雜度較高。Barchiesi等提出了迭代投影和旋轉(zhuǎn)的低相干性字典學(xué)習(xí)算法［9］與INK-SVD算法的思想類(lèi)似，它是對(duì)整個(gè)字典而不是原子進(jìn)行降低相干性和旋轉(zhuǎn)操作，但是該算法訓(xùn)練得到的字典，其稀疏表示性能有所下降。2012年 Christian D.Sigg 等［10］在《Learning Dictionaries with Bounded Self-Coherence》一文中提出 IDL（Incoherent Dictionary Learning）的字典學(xué)習(xí)算法，但是該算法不能保證信號(hào)的稀疏表示性能，且需要計(jì)算矩陣的梯度。

本文在K-SVD算法極小化目標(biāo)函數(shù)下，添加一項(xiàng)刻畫(huà)字典相干性的懲罰項(xiàng)以降低字典相干性，稱(chēng)該方法為低字典相干性K-SVD算法。在給最大化所得的稀疏度的前提下盡可能有效地控制訓(xùn)練字典的自相關(guān)性。具體而言，本文在IDL字典學(xué)習(xí)算法基礎(chǔ)上對(duì)K-SVD算法進(jìn)行改進(jìn)，采用對(duì)字典原子逐一更新的優(yōu)化目標(biāo)，從最大化所得稀疏編碼到 逼 近 一 個(gè) 等 角 緊 框 架［11］（Equiangular Tight Frame，ETF）的過(guò)程，這是一個(gè)對(duì)于給定原子數(shù)量基于實(shí)現(xiàn)最小相干性的字典過(guò)程。限制字典的相干性其優(yōu)勢(shì)在于更好地編碼支持恢復(fù)和改進(jìn)的泛化性能，其中字典自相干的界限直接在原子更新步驟中執(zhí)行，通過(guò)改變拉格朗日乘子γ，進(jìn)而實(shí)現(xiàn)代碼稀疏度最大化和字典相干性最小化的目標(biāo)。

通過(guò)實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，低字典相干性K-SVD算法在一定程度上減少了算法迭代更新的時(shí)間，降低了原子的自相干性，從而使得圖像在去噪過(guò)程中可以更好地恢復(fù)重構(gòu)。

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

在圖像去噪的相關(guān)研究中，基于字典學(xué)習(xí)可以提取樣本數(shù)據(jù)的內(nèi)部結(jié)構(gòu)特征的這一特點(diǎn)，通常采用該方法達(dá)到圖像去噪的目的。

2.1 字典學(xué)習(xí)

字典學(xué)習(xí)最早是由 Olshausen（1996）［12］提出，發(fā)展至今該方法已經(jīng)有了較為成熟的理論與較為豐富的實(shí)踐運(yùn)用。字典學(xué)習(xí)也可簡(jiǎn)單地稱(chēng)其為稀疏編碼，字典學(xué)習(xí)較偏向于學(xué)習(xí)字典，從矩陣的角度來(lái)看，字典學(xué)習(xí)的基本過(guò)程為，通過(guò)給定樣本數(shù)據(jù)集X，其中X的每一列代表每個(gè)樣本，字典學(xué)習(xí)的主要目的是通過(guò)將樣本數(shù)據(jù)集X分解成如下形式的矩陣進(jìn)行操作：

其中，D代表字典矩陣，D的每一列稱(chēng)之為原子，C代表對(duì)應(yīng)的系數(shù)矩陣，式（1）需同時(shí)滿足以下約束條件，即系數(shù)矩陣C要盡可能的稀疏，字典矩陣D的每一列即每一個(gè)原子是一個(gè)歸一化向量。

通過(guò)上述分析可知，字典學(xué)習(xí)的主要目的是極小化如下目標(biāo)函數(shù)：

其中，X∈RM×N為信號(hào)的樣本數(shù)據(jù)矩陣且滿足，M,N分別代表樣本數(shù)據(jù)的維數(shù)和個(gè)數(shù)；D∈RM×K(M＜K)為過(guò)完備字典矩陣且有，其中該矩陣的第k列dk稱(chēng)為字典的原子；C∈RK×N為信號(hào)的稀疏表示系數(shù)矩陣且有，‖c‖代表的為稀疏系數(shù)矩陣中每一列i0的非零元素個(gè)數(shù)，S表示為稀疏度。

綜合稀疏模型一直以來(lái)受到廣大研究學(xué)者的關(guān)注，基于這一模型的字典學(xué)習(xí)方法也是字典學(xué)習(xí)理論研究中相對(duì)成熟的部分，大多數(shù)求解式（2）的算法采用的都是系數(shù)更新和字典更新交替迭代優(yōu)化的方法。算法在系數(shù)更新部分沒(méi)有較大的差異，主要不同之處在于對(duì)字典的更新方式上，固定字典D更新稀疏系數(shù)矩陣X是常見(jiàn)的稀疏編碼問(wèn)題。通俗的來(lái)說(shuō)，任何一種稀疏編碼方法都可以用于系數(shù)更新，所以近些年來(lái)有越來(lái)越多的稀疏編碼方法被大家所提出，因此通過(guò)固定稀疏系數(shù)矩陣X進(jìn)而更新字典D是研究字典學(xué)習(xí)算法較為關(guān)注的一個(gè)重點(diǎn)。

2.2 K-SVD算法

基于上述分析本文主要對(duì)K-SVD字典學(xué)習(xí)模型展開(kāi)詳細(xì)的論述。K-SVD算法是Elad等提出的一種新的字典學(xué)習(xí)算法，該方法是根據(jù)K均值聚類(lèi)發(fā)展而來(lái)的，因此可將其視為廣義的K均值算法。該算法主要分為稀疏分解和字典更新兩個(gè)部分，稀疏分解階段，首先得到訓(xùn)練樣本的字典D，再通過(guò)OMP（Orthogonal Matching Pursuit）［13］算法求解稀疏表示，具體通過(guò)優(yōu)化如下函數(shù)：

在此基礎(chǔ)上，采用SVD分解算法對(duì)字典進(jìn)行更新。該算法主要是通過(guò)對(duì)字典的每一列進(jìn)行更新，從而求得最優(yōu)字典的過(guò)程，字典更新階段，該算法主要通過(guò)如下目標(biāo)函數(shù)進(jìn)行描述：

其中，X為圖像信號(hào)所對(duì)應(yīng)的矩陣，D為需要訓(xùn)練的字典矩陣，C為字典矩陣D所對(duì)應(yīng)的稀疏表示系數(shù)矩陣，dj和dk分別為字典矩陣D所對(duì)應(yīng)的第j個(gè)和第k個(gè)列向量，cj和ck分別為稀疏系數(shù)矩陣所對(duì)應(yīng)的第 j個(gè)和第k個(gè)行向量，E為對(duì)應(yīng)的誤差矩陣。

K-SVD算法使非參數(shù)字典適應(yīng)訓(xùn)練數(shù)據(jù)，在算法的每次迭代中，這些原子被更新替換，若原子之間的相干性過(guò)高，則會(huì)導(dǎo)致替換原子與字典不一致的概率增大，因此這種策略并不能夠保證字典的自相干性低于一般的門(mén)限閾值。所以為了更好地解決這一問(wèn)題，本文通過(guò)如下方式對(duì)字典學(xué)習(xí)算法進(jìn)行改進(jìn)，從而達(dá)到在稀疏度最大化前提下降低原子相干性這一目的。

2.3 IDL字典學(xué)習(xí)算法

假設(shè)給定訓(xùn)練圖像 X∈RN×M包含M 個(gè)信號(hào)，IDL字典學(xué)習(xí)的實(shí)質(zhì)是找到恰當(dāng)?shù)那以又g相干性較小的字典D∈RM×K( )M?K 并使得每個(gè)信號(hào)xi可用字典D表示，其模型表示如下：

其中拉格朗日乘子γ用于控制最小化逼近誤差和最小化自相關(guān)性之間的權(quán)衡。式（5）中的第二部分懲罰項(xiàng)用于平衡原子之間的相干性。

第二項(xiàng)可寫(xiě)為

由式（6）和式（7）可知，將式（5）對(duì) D 求導(dǎo)，其梯度表示如下：

對(duì)式（5）的求解采用的是有限存貯擬牛頓法［12］LBFGS（Limited-memory BFGS）。

3 低字典相干性K-SVD算法

目前主流的字典學(xué)習(xí)算法，大都無(wú)法有效地降低字典的相干性，但字典的相干性對(duì)圖像去噪的效果又起著重要的作用。本文主要在K-SVD算法極小化目標(biāo)函數(shù)下，添加一項(xiàng)刻畫(huà)字典相干性的懲罰項(xiàng)以降低字典相干性，稱(chēng)該方法為低字典相干性K-SVD算法。

3.1 算法相關(guān)知識(shí)

一般來(lái)說(shuō)，通常采用互相關(guān)這一概念來(lái)刻畫(huà)矩陣列之間的相干性?；ハ嚓P(guān)定義如下：矩陣A的互相關(guān)是A中不同列的歸一化內(nèi)積的絕對(duì)值中的最大值［14］，主要用于刻畫(huà)矩陣列之間的相關(guān)性，具體表達(dá)式如下：

其中，aj表示矩陣A的第 j列。

相干性約束是過(guò)完備字典學(xué)習(xí)算法中需要考慮的一個(gè)重要因素。正交字典的相干性為0，過(guò)完備字典由于原子數(shù)量大于信號(hào)維數(shù)，原子之間的相干性大于0。一般來(lái)說(shuō)，字典的冗余度越大其相干性也越大，字典的相干性對(duì)其稀疏編碼性能十分關(guān)鍵，在相同冗余度的前提下，低相干性可加快稀疏編碼速度，改善信號(hào)重構(gòu)性能，另外低相干性還有助于避免字典原子對(duì)訓(xùn)練樣本的過(guò)擬合，避免字典中出現(xiàn)過(guò)于相似的原子對(duì)。

對(duì)于一般過(guò)完備字典的相干性，可以證明其存在一定的范圍，即存在一個(gè)下界（Welch Bound）值，通過(guò)如下定理進(jìn)行描述。

定理1 假設(shè)字典D∈RM×K且M＜K，列向量歸一化，則字典D的相干性滿足：

當(dāng)式（10）等式成立時(shí)，字典D的相干性達(dá)到最小，這樣越接近于正交基。所以，如何將字典的相干性逼近于其邊界值，就成為了稀疏信號(hào)恢復(fù)的關(guān)鍵。Tropp等［14］提出當(dāng)且僅當(dāng)字典D是等角緊框 架（Equiangular Tight Frame，ETF），且 滿 足K≤M(M+12)時(shí)式（10）中的等號(hào)成立，即。同時(shí)若D為ETF時(shí)，則D是行滿秩矩陣，且具有M個(gè)非零的奇異值，其值均為。等角度緊框架的具體定義如下：

定 義 1［15～16］假 設(shè) D∈RM×K且 M＜K ，，列向量歸一化，若滿足：

且

其中I是一個(gè)N×N的單位矩陣，K,M分別對(duì)應(yīng)字典矩陣D的列數(shù)和行數(shù)，即字典矩陣D的列向量構(gòu)成一個(gè)等角緊框架，那么D或者D的列向量組成的集合稱(chēng)為等角緊框架。

基于等角度緊框架具有最小相干性的這一特點(diǎn)，本文考慮通過(guò)逼近等角度緊框架（Equiangular Tight Frame，ETF）的方法，從而達(dá)到降低相干性的目的。

3.2 算法模型

本文為了解決降低基于K-SVD算法下的字典自相干性問(wèn)題，在K-SVD算法的極小化目標(biāo)函數(shù)下，添加了一項(xiàng)有關(guān)字典D的自相干性懲罰項(xiàng)，具體表達(dá)形式如下：

其中，xi為圖像信號(hào)所對(duì)應(yīng)第i個(gè)訓(xùn)練樣本，即圖像塊內(nèi)像素展開(kāi)的列向量，X={x1,x2,…xi}∈RN×M，D∈RN×K為需要訓(xùn)練的字典矩陣，ci是樣本xi所對(duì)應(yīng)的稀疏表示系數(shù)，λ,γ為拉格朗日乘子，用于控制重構(gòu)誤差，極小化字典相干性與稀疏度之間的權(quán)衡。

基于改進(jìn)K-SVD降低過(guò)完備字典原子相干性的算法流程

算法：改進(jìn)K-SVD降低過(guò)完備字典原子相干性的算法。

2）初始化：

初始化字典：構(gòu)造 D(0)∈Rn×m，可以使用隨機(jī)矩陣，或隨機(jī)選取m個(gè)樣本作為字典。然后對(duì)字典D(0)的列標(biāo)準(zhǔn)化。

3）迭代步驟：

（1）稀疏編碼階段：固定字典D，上式的稀疏編碼可重新定義如下，

（2）固定稀疏編碼系數(shù)矩陣C，則字典更新目標(biāo)函數(shù)如下：

寫(xiě)成矩陣形式，如下：

對(duì)目標(biāo)任務(wù)中的D進(jìn)行奇異值分解（svd），即D=UΣVT并簡(jiǎn)化式子如下：

（3）字典更新：同理K-SVD算法，但是不在使用u1，v1更新字典，而是使用使得上式最小的ui，vi更新字典和稀疏系數(shù)矩陣。

4）輸出：得到訓(xùn)練字典D。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文所改進(jìn)的算法對(duì)字典原子相干性的影響，應(yīng)用本文算法與K-SVD算法進(jìn)行圖像去噪實(shí)驗(yàn)對(duì)比分析。利用CPU為4GHz，內(nèi)存為8GB的計(jì)算機(jī)，通過(guò)Matlab R2016a仿真實(shí)現(xiàn)。實(shí)驗(yàn)圖像為512×512像素，圖像分塊為8×8，字典大小為64×256。

采用字典訓(xùn)練時(shí)間、峰值信噪比（PSNR）和字典原子間的相干性作為衡量?jī)蓚€(gè)算法性能評(píng)價(jià)標(biāo)準(zhǔn) 。 峰 值 信 噪 比 （PSNR）：。其中MSE是原圖像與去噪后重建圖像之間的均方誤差。實(shí)驗(yàn)圖像為512×512像素，圖像分塊為8×8，字典大小為64×256。下面列出了圖像的實(shí)驗(yàn)結(jié)果對(duì)比。

4.1 字典相干性的測(cè)量

為了驗(yàn)證本文所采用的算法對(duì)字典相干性是否有所改進(jìn)，將本文所改進(jìn)的算法與K-SVD算法所構(gòu)造的字典進(jìn)行相干性對(duì)比分析。實(shí)驗(yàn)中，初始字典D∈RN×K是隨機(jī)生成的，列向量歸一化的，每列向量中非零元素位置隨機(jī)分布，其值服從高斯分布。最小相干性邊界值μ=0.1085。則在不同的高斯噪聲標(biāo)準(zhǔn)差下由本文算法所訓(xùn)練的字典的相干性與K-SVD算法的字典相干性表1所示。

表1 字典相干性對(duì)比分析

由圖1可知，在γ一定的情況下，本文所改進(jìn)的K-SVD算法與傳統(tǒng)的K-SVD算法相比較，在噪音水平一致的條件下，由K-SVD算法訓(xùn)練得到的字典，其相干性比本文算法訓(xùn)練出的字典的相干性大，即本文算法的字典相干性明顯低于傳統(tǒng)的K-SVD算法。上述分析表明本文所改進(jìn)的算法在降低字典相干性問(wèn)題上具有較大的優(yōu)勢(shì)。

4.2 圖像去噪實(shí)例

比較本文算法與傳統(tǒng)的K-SVD算法應(yīng)用于圖像去噪，在噪音水平相同的條件下，進(jìn)行比較去噪效果。下列是標(biāo)準(zhǔn)的Lena圖在σ=25的高斯白噪音的干擾下去噪的效果圖。

圖1 本文算法與K-SVD算法對(duì)Lena圖去噪對(duì)比

圖2 本文算法與K-SVD算法訓(xùn)練的字典

圖3 本文算法與K-SVD算法對(duì)house圖去噪對(duì)比

圖4 本文算法與K-SVD算法訓(xùn)練的字典

通過(guò)上述去噪實(shí)例的對(duì)比，可以看出在噪音水平相同的情況下，本文改進(jìn)的算法有良好的去噪效果。

實(shí)驗(yàn)中分別在高斯噪聲標(biāo)準(zhǔn)差σ=5，10，15，20，25不同噪音水平下進(jìn)行圖像去噪測(cè)試。獲得峰值信噪比PSNR值和運(yùn)行時(shí)間，其測(cè)試結(jié)果，如表2所示。

表2 兩種去噪方法對(duì)Lena圖像去噪后的峰值信噪比PSNR（dB）

表3 兩種去噪方法對(duì)house圖像去噪后的峰值信噪比PSNR（dB）

由上表的PSNR值，可以看出在相同的噪音水平下，兩種算法都可以有效地去除噪音，改進(jìn)后的算法能夠更加有效地去除噪音，在不同標(biāo)準(zhǔn)差下本文算法還是有一定的優(yōu)勢(shì)。

下面給出lena圖像和house圖像在噪音水平分別為5，10，15，20，25時(shí)，運(yùn)行30次實(shí)驗(yàn)得到的平均時(shí)間。

表4 Lena圖像在不同噪音水平下兩種算法運(yùn)行時(shí)間比較

表5 house圖像在不同噪音水平下兩種算法運(yùn)行時(shí)間比較

實(shí)驗(yàn)分析：通過(guò)表4、5可以看出，在噪音水平σ =5，10，15，20，25對(duì)比K-SVD算法，本文算法的運(yùn)行速度有了較大程度的提高，

5 結(jié)語(yǔ)

針對(duì)于K-SVD算法學(xué)習(xí)的字典有較高的相干性這一問(wèn)題，本文提出了低字典相干性K-SVD算法。首先本文對(duì)K-SVD中的字典構(gòu)造進(jìn)行了改進(jìn)，不在單一的選取以最大奇異值對(duì)應(yīng)的特征向量去更新字典的列，而是對(duì)原有的模型增加刻畫(huà)字典相干性的約束項(xiàng)，在字典更新階段選取能使得模型極小化的特征向量去更新字典的列。這樣改進(jìn)的方法有效地降低了字典的相干性，由于相同的冗余度下，低相干性可加快稀疏編碼速度，改善信號(hào)的重構(gòu)性能，另外，低相干性有助于避免字典對(duì)訓(xùn)練樣本的過(guò)擬合，即有效地避免字典出現(xiàn)過(guò)于相似的原子對(duì)。本文算法有效地降低了字典的相干性，使得圖像去噪效果更好。