字典学习的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