牛秀秀，華敏杰，狄燕飛，相鵬

(中國傳媒大學(xué) 理工學(xué)部，北京 100024)

字典學(xué)習(xí)的K-SVD算法分析

牛秀秀，華敏杰，狄燕飛，相鵬

(中國傳媒大學(xué) 理工學(xué)部，北京 100024)

分析了字典學(xué)習(xí)的K-SVD算法，通過引入K-Means計(jì)算方法，將K-Means方法推廣到用于字典學(xué)習(xí)的K-SVD計(jì)算方法中；分析和描述了K-SVD計(jì)算過程，指出了K-SVD方法與K-Means方法之間的關(guān)系，最后觀察圖像數(shù)據(jù)訓(xùn)練用于稀疏表示的字典。

K-Means方法；字典學(xué)習(xí)；稀疏表示；K-SVD方法

1 引言

圖像去噪問題是非常重要的，不僅僅是因?yàn)樵诔绦蛏系膽?yīng)用，而且作為最簡(jiǎn)單的反問題，給圖像處理在技術(shù)和理念上提供了一個(gè)方便的平臺(tái)。在過去的50年左右，許多人有著不同的觀點(diǎn)，各種統(tǒng)計(jì)估計(jì)、空間自適應(yīng)濾波器、偏微分方程、樣條函數(shù)等等很多方向都在研究這個(gè)問題。在本文中主要專注一個(gè)特定的方法來解決圖像去噪問題：在稀疏表示下的字典學(xué)習(xí)。

K-SVD算法是2006年由以色列理工學(xué)院Michal Aharon、Michael Elad等人[1]提出來的，是一種非常經(jīng)典的字典訓(xùn)練算法，并且達(dá)到了很好的訓(xùn)練效果。其目的是解決下列等式的解：

Y=DX，

(1)

其中D是要訓(xùn)練的字典，X是字典D對(duì)應(yīng)的稀疏系數(shù)向量。當(dāng)矩陣的維數(shù)過高時(shí)，即使在Matlab中也很難求得(1)的解。研究表明，K-SVD算法可以比較簡(jiǎn)便的求解問題(1)。

2 K-Means算法

在矢量量化(VQ)中，可以通過K-Means方法來對(duì)碼本進(jìn)行訓(xùn)練，假定碼本為C=[c1，c2，.....cK]，代碼是C中的列ci。當(dāng)碼本C給定時(shí)，每個(gè)信號(hào)用最近(l2范數(shù)下)的一個(gè)代碼表示。我們也可以寫作yi=Cxi，其中xi=ej是自然基中的一個(gè)向量(除了第j個(gè)值為1，其余為0)。j滿足

我們可以發(fā)現(xiàn)K-Means算法就是一個(gè)對(duì)碼本C進(jìn)行更新迭代的過程。

3 K-SVD算法——廣義K-Means算法

在講述K-SVD算法之前，我們首先要了解奇異值分解。奇異值分解就是假設(shè)M是一個(gè)m×n階矩陣，其中的元素全部屬于域K(實(shí)數(shù)域或復(fù)數(shù)域)。如此則存在一個(gè)分解使得M=UΔV*，其中U是m×m階酉矩陣；Δ是半正定m×n階對(duì)角矩陣；而V*，即V的共軛轉(zhuǎn)置，是n×n階酉矩陣。這樣的分解就稱作M的奇異值分解。Δ對(duì)角線上的元素Δi，Δi即為M的奇異值。

本文我們研究方程

(2)

(3)

我們可以發(fā)現(xiàn)求解(3)的過程就是一個(gè)迭代過程，具體迭代過程如下：

(4)

(5)

總結(jié)下來得到K-SVD算法過程：

2.給出初始字典D(0)∈Rn×K，其中的列向量都是l2范數(shù)下的標(biāo)準(zhǔn)形式。給定J=1。

3.對(duì)D(J-1)中的每列k=1，2，....K進(jìn)行迭代：

最后，J=J+1繼續(xù)重復(fù)迭代過程，直到滿足停止條件。

我們看到K-SVD可以看做K-Means的一種泛化形式，K-Means算法中每個(gè)信號(hào)只能用一個(gè)原子來近似表示，而K-SVD算法可看做廣義的矢量量化(VQ)，其中每個(gè)信號(hào)可以用多個(gè)原子的線性組合來表示。因此，我們可以發(fā)現(xiàn)當(dāng)K-SVD算法中要求的每個(gè)信號(hào)只用一個(gè)原子來近似時(shí)，K-SVD算法就退化為K-Means算法。

4 數(shù)值實(shí)驗(yàn)

我們用Matlab對(duì)K-SVD算法進(jìn)行了編程，從臉圖像數(shù)據(jù)庫中找到訓(xùn)練數(shù)據(jù)，其由11000例像素為8×8的小塊構(gòu)成，按照他們的方差隨機(jī)抽500個(gè)構(gòu)成訓(xùn)練的圖像如圖1。

圖1

為了運(yùn)行K-SVD算法，我們還要給出要字典的大小為64×256，得到訓(xùn)練字典的圖像如圖2。

然后，利用K-SVD算法得到的字典對(duì)觀察圖像進(jìn)行去噪，此時(shí)選取兩個(gè)圖像的大小為512×512，從而得到去噪后的圖像如圖3。

圖2

圖3

5 結(jié)論

本文重點(diǎn)分析了K-SVD算法的計(jì)算過程，由于K-SVD算法針對(duì)不同的圖像均有較好的適應(yīng)性，并且能獲得更好的恢復(fù)效果，因此，在圖像學(xué)習(xí)中得到普遍運(yùn)用。

[1]AharonM，EladM，BrucksteinAM.TheK-SVD：Analgorithmfordesigningofovercompletedictionariesforsparserepresentation[J].IEEETransSignalProcess，2006，54(11)：4311-4322.

[2]PatiYC，RezaiifarR，KrishnaprasadPS.Orthogonalmatchingpursuit：Recursivefunctionapproximationwithapplicationstowaveletdecomposition[C].27thAnnuAsilomarConfSignals，Systems，andComputers，1993.

[3]MallatS，ZhangZ.Matchingpursuitswithtime-frequencydictionaries[J].IEEETransSignalProcess，1993，41(12)：3397-3415.

[4]GershoA，GrayRM.VectorQuantizationandSignalCompression[M].NewYork：Springer，1991.

(責(zé)任編輯：王謙)

The K-SVD Analysis of Dictionary Learning

NIU Xiu-xiu，HUA Ming-jie，DI Yan-fei，XIANG Peng

(Science of School，Communication University of China，Beijing 100024，China)

The dictionary learning method i.e.the K-SVD algorithm has been analyzed.We have also ex-tended to K-means to K-SVD method through using some ideas in K-means algorithm.The K-SVD algorithm to solve real problems has been analyzed and given in detailed steps.The differences and similarities between K-SVD and K-Means have been provided.The learned dictionary has been obtained by theobserved image data based on the numerical experiments.

K-Means algorithm；dictionary learning；sparse representations；K-SVD algorithm

2016-4-15

牛秀秀(1991-)，女，(漢族)，安徽省淮北人，中國傳媒大學(xué)碩士研究生.E-mail：393908086@qq.com

TN911.73

A

1673-4793(2017)01-0047-04