字典學習的K-SVD算法分析

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

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

字典學習的K-SVD算法分析

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

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

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

K-Means方法；字典學習；稀疏表示；K-SVD方法

1 引言

圖像去噪問題是非常重要的，不僅僅是因為在程序上的應用，而且作為最簡單的反問題，給圖像處理在技術和理念上提供了一個方便的平臺。在過去的50年左右，許多人有著不同的觀點，各種統計估計、空間自適應濾波器、偏微分方程、樣條函數等等很多方向都在研究這個問題。在本文中主要專注一個特定的方法來解決圖像去噪問題：在稀疏表示下的字典學習。

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

Y=DX，

(1)

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

2 K-Means算法

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

我們可以發現K-Means算法就是一個對碼本C進行更新迭代的過程。

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

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

本文我們研究方程

(2)

(3)

我們可以發現求解(3)的過程就是一個迭代過程，具體迭代過程如下：

(4)

(5)

總結下來得到K-SVD算法過程：

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

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

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

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

4 數值實驗

我們用Matlab對K-SVD算法進行了編程，從臉圖像數據庫中找到訓練數據，其由11000例像素為8×8的小塊構成，按照他們的方差隨機抽500個構成訓練的圖像如圖1。

圖1

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

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

圖2

圖3

5 結論

本文重點分析了K-SVD算法的計算過程，由于K-SVD算法針對不同的圖像均有較好的適應性，并且能獲得更好的恢復效果，因此，在圖像學習中得到普遍運用。

[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.

(責任編輯：王謙)

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-)，女，(漢族)，安徽省淮北人，中國傳媒大學碩士研究生.E-mail：393908086@qq.com

TN911.73

A

1673-4793(2017)01-0047-04