基于稀疏表示的图像分类字典学习*

何小卫, 张 莉

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)



基于稀疏表示的图像分类字典学习*

何小卫, 张 莉

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

针对K-SVD算法学习得到的字典结构性不强的问题，利用图像的非局部自相似性，提出了基于稀疏表示的图像分类字典学习方法(NLC-DL).该方法利用K-means对图像块进行聚类并对每个子类进行字典学习，增强字典的有效性.根据正交匹配追踪算法(OMP)求得稀疏系数，迭代优化字典，最终利用优化后字典和稀疏系数矩阵重构图像.实验结果表明：生成的学习字典对训练样本的表达误差更小，能够有效地保持图像的结构信息，重构后的图像在峰值信噪比和视觉效果方面均优于传统方法.

非局部；自相似性；稀疏表示；字典学习;K-均值

0 引 言

图像的稀疏表示是通过引入过完备冗余字典，实现对信号的最优逼近.基于图像稀疏表示的过完备信号稀疏表示理论最早是由Mallat等[1]提出的，使用Gabor字典并引入匹配追踪算法，通过逐步逼近的方法对信号进行稀疏表示.近年来，基于过完备冗余字典的信号稀疏表示被广泛应用于图像处理的各个领域：利用形状自适应字典块对三维医学图像进行去噪处理[2]；通过抑制噪声的稀疏编码进行图像恢复[3]；基于位置分类选择合适加权分解人脸词典并进行稀疏编码用于人脸识别[4]；利用稀疏表示进行目标检测实现背景分离进而实现目标跟踪[5]；基于压缩感知构造超完备稀疏字典进行稀疏降维[6]；强调任务驱动字典学习算法以提高高光谱分类的效果[7].

文献[8]提出K-SVD字典学习算法，将观测图像作为训练原子库进行字典学习，能够较好地保护图像的细节信息.但在初始字典选择不当的情况下，由于字典某些列可能不被更新，降低了字典原子的有效利用率，可能导致算法陷入局部最小值，并且算法在处理高维数据及运算复杂度上都有一定的局限性[9].为解决这些问题，近年来，有学者在K-SVD算法的基础上进行了一些改进.在降低字典大小的问题上，Mazhar等[10]提出了增强K-SVD算法(EK-SVD)，在不影响逼近精度的前提下，从大量的字典原子中逐步修剪掉类似的原子，进而产生一个较小尺寸的优化字典，从一定程度上降低了K-SVD算法运算的复杂度；在对选择合适大小的字典问题上，文献[11]进行了探索并提出子聚类K-SVD算法，采用子聚类的方法保留最重要的原子，同时去除多余原子，通过引入错误驱动机制完成字典的更新；在提高字典原子参与图像重构的使用率问题上，Ribhu等[12]提出了稀疏贝叶斯学习方法，在K-SVD算法最初的几次迭代过程中，使用稀疏贝叶斯学习方法进行稀疏编码完成信号从非稀疏表示逐步收敛到稀疏表示，从而解决了字典原子的利用不足问题.

上述基于K-SVD的图像处理方法在字典大小、字典原子利用率和算法时间复杂度方面进行了改善，但这并没有有效解决K-SVD算法对初始字典的随机选取问题.文献[3]指出,用K-SVD方法得到的稀疏编码系数并不是随机分布的，它们之间存在高度的相关性，提出了非局部中心化稀疏表示模型，并取得了非常好的图像恢复效果.考虑到各图像块之间可能存在的几何结构相似性[13]，对需要处理的图像块进行聚类，再对聚类后的图像块进行字典学习.一方面，使得各个子字典更有针对性，每类子字典只恢复与之相对应的图像块信息，增强了字典学习的有效性；另一方面，聚类使得并行计算成为可能，加快了图像处理速度.在过完备稀疏表示问题的求解方面，贪婪追踪算法在求解优化问题时不需要考虑整体最优性，总在当前的最好结果的条件下做选择.主要算法有：匹配追踪(MP)算法[1]、正交匹配追踪(OMP)算法[14]等.OMP算法是对MP算法的一种改进，在分解的每一步对所选择的全部原子进行正交化处理，使得在精度要求相同的情况下，OMP算法的收敛速度更快.

利用图像的非局部自相似性，本文提出了基于稀疏表示的图像分类字典学习方法(NLC-DL)：用K-means方法对图像块进行聚类，利用主成分分析(PCA)具有很好方向性的特性,对子类图像块进行子字典学习；对于每一子类图像，利用OMP算法得出对应稀疏系数，迭代计算所得图像与原始图像之间的差距，优化字典直至达到优化条件；并通过实验方法完成算法的相关参数设定和字典类数选择，利用优化字典和稀疏系数实现图像重构.

1 基于稀疏表示的图像分类字典学习模型

1.1 基于稀疏分解理论的图像表示

稀疏分解是将信号或图像在过完备的字典下分解，寻找最匹配的原子重构信号或图像.图像的稀疏表示理论研究主要分为稀疏分解重建算法和字典的设计，而字典的设计将直接影响到图像是否能有效地进行稀疏表示.稀疏编码是对训练字典进行线性组合，从而最大限度地逼近给定数据集[15].

或者

式(1)和式(2)中，范数‖5‖0表示向量非零元素的个数.由于l0的最小化是NP-hard问题，所以在a足够稀疏的条件下，可用l1范数对其进行凸放松[17].模型(1)等价于

1.2 图像分类字典学习模型

由于自然图像在结构上存在自相似性[19]，即图像上很多信息是相似的、冗余的，并且它们不是局部分布的，可以在整个图像的任意位置，所以不同图像块之间也会存在结构上的相似性.图像块之间的相似性可以通过它们的灰度值的欧式距离来度量，欧式距离越小，结构越相似.将图像块利用K-means聚类后的原始图像可表述为：Y=[y1,y2,…,yk]，其中yi={y(1),y(2),…,y(j)}表示聚类后每一类数据，再对每一子类数据块进行稀疏编码和字典学习，以实现图像恢复的目的.在式(3)的基础上引入分类的思想，模型可表述为

利用图像非局部自相似性对图像进行聚类，最终获得的子类字典之间可能包含有相似的原子信息，比如图像的边缘、轮廓、纹理等特征信息，都有可能出现在不同子类字典的原子信息中.因此，通过计算不同子类字典之间的相似度，把相似度较高的子字典合成一个特征字典，再用特征字典对相关图像块进行重构以实现对图像特征信息的保护，可以进一步提高本文方法对图像恢复的效果.

2 算法实现

利用图像的非局部自相似性，充分考虑图像块间的相互联系，对图像块进行结构聚类，并对聚类后的图像块做类内字典学习，有效地捕捉了图像的内部结构特征，增强了字典的有效性，加快了收敛速度，从而更好地实现图像的重构.具体的类字典学习过程如下:

NLC-DL算法

输入：训练样本Y

1)利用K-means对训练样本进行聚类Y=[y1,y2,…,yk],yi={y(1),y(2),…,y(j)}.

①随机选取k个聚类质心点π1,π2,…,πk；

2)利用PCA方法对每一类样本进行降维处理，得出初始特征类字典Dk.

③对原图像进行降维处理，得到Dk=(Y-υ)Ak.

3)利用OMP算法计算第i类样本的稀疏系数ai.

4)通过以下步骤进行J次迭代：对于字典D中的每一列l=1,2,…,m，

①计算残差El=yi-Diai；

②利用SVD算法分解得El=UΛVT；

④矩阵V的第1列乘以Λ(1,1)后所得的结果更新系数ai.

5)如果不能达到停止迭代的标准，那么返回第4步.

6)更新第i类图像块xi=Diai.

输出：第i类数据对应的子字典Di及恢复图像X.

算法的重点在于构造子类字典，以获得对图像信号更加准确的稀疏表示.首先，对图像块信息利用K-means方法，即通过计算它们的灰度值之间的欧式距离进行聚类，并对子类图像块利用PCA方法进行降维处理作为初始子类字典，可有效地避免传统K-SVD算法对初始字典随机选取不当情况下可能陷入局部最小值的问题.然后，采用OMP算法根据每一子类对应的PCA字典进行图像信号的稀疏分解，分解过程的每一步均将图像信号投影到特征子字典所构成的空间上，获取信号的各个已选原子上的投影分量和残余分量，再循环对残差分量进行分解.在每次迭代时，在字典中选择与残余信号最相关的原子,再将信号残余正交投影到所选的原子上;然后重新计算稀疏系数并更新信号残余，重复计算直到信号残余小于设定的阈值；最后，利用类特征字典Di获得相应稀疏系数重构图像X.

3 实验结果与分析

3.1 分类子字典

为了验证上述字典学习方法的有效性，使用一些经典的图像作为实验用例.以512×512像素的灰度图像Lena为例，在加入σ=20的高斯噪声之后，定义图像块大小为8×8像素，并按不同步长(step=1，2，4，6，8和10)，共生成424 204个图像块进行训练，其中类数cls=15，迭代结束条件(即设定的误差阈值)T=1.15σ，最大迭代次数num=10.按照本文算法得到的子类字典如图1和图2所示，图3是相同图像数据利用K-SVD算法得到的字典，视觉上看字典块信息排列杂乱无章，字典的维数相对较高，列字典原子之间表现出一定的相似性，在一定程度上降低了字典的有效性，不利于对图像结构特征进行保护，可能影响到图像的恢复效果.图1是图像Lena利用本文算法生成的15类子字典.由图1～3观察比较可知，本文NLC-DL算法对图像整体信息进行分类细化，由于不同类数据信息具有一定的差异性，最终获得的n个分类字典与传统算法获得的一个字典相比，能够更有效地捕捉图像不同结构的细节纹理特征，如图1中第4，5类字典及图2中第1，2，14类字典虽然看起来极其相似，但是字典内部数据块的纹理结构倾斜度又有一定的差别，能够表现出图像不同结构间的差异性.本文利用图像非局部自相似性对图像整体进行K-means聚类，用欧式距离衡量图像块间的相似性，由于每一类图像块数量不固定，使得类内图像块数量相对较少，且结构相对简单的子类图像构造的类内字典块存在一些冗余信息，如图1中第7，12，13，14类字典和图2中第1，2，4，12类字典.

3.2 图像去噪效果

自然图像的多样性使得同一算法可能会在不同图像上表现出不同的性能，为了克服这一问题，笔者使用大量具有代表性的图像进行测试.选取大小为512×512的Lena，Barbara，Cameraman，Boat，Peppers及Bridge图像，并叠加不同标准差σ=10，20和30的高斯噪声，利用DCT[20]，Global[16]，K-SVD[8]及本文NLC-DL算法分别进行测试，去噪结果如表1所示.

表1显示所选图像在不同噪声水平下的PSNR值.通过对比可知，本文方法在图像去噪方面优于DCT,Global算法0.27～2.69 dB，优于与本文框架结构类似的K-SVD算法0.11～0.76 dB.并且对于纹理丰富的Lena，Barbara及Boat图像，通过不同方法的比较结果可见，对所选图像施加的噪声越大，本文算法的PSNR值增加得越多.说明本文利用结构聚类进行字典学习的方法更有利于保护图像的纹理特征，在图像恢复方面更为成功.

为了更加形象、直观地表述本文算法在图像恢复方面的效果，以细节纹理比较丰富的图像Barbara为例，施加σ=20的高斯噪声并运用不同方法进行图像去噪，效果对比如图4所示.从图4中的具体细节放大信息来看，其他3种算法将图像整体化处理使得图像的明暗对比度减低，而本文算法在图像对比度方面更接近原始图像；对于一些细小纹理特征，其他算法都丢失了部分纹理信息，但本文方法恢复的纹理信息明显比传统算法更多、更清晰；在边缘保护方面，其他算法均将边缘平滑掉了，而本文方法基本上保持了边缘的原有特征.由此说明,本文利用分类字典学习方法对图像进行分类处理有助于保护图像的纹理、边缘等结构特征.

本文算法不论是从PSNR值还是细节结构特征方面，都优于其他3种方法.

4 结 论

本文利用非局部的思想对图像进行结构聚类和字典学习，提出了基于稀疏表示的图像分类字典学习方法.一方面，利用图像的非局部自相似性对图像块进行结构聚类，有效地保持了图像的结构信息；另一方面，对聚类后的图像块单独进行字典学习，使得字典更有针对性，可以提高图像的重构效果.实验结果表明，本文算法与其他传统算法相比，随着图像噪声逐渐增大，无论是从平滑效果，还是对于边缘、纹理等结构信息，本文算法所产生的学习字典结构性更强，能较好地表示训练样本，在峰值信噪比和视觉效果方面都优于传统方法.

[1]Mallat S G,Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.

[2]Thilagavathi M,Deepa P.An efficient dictionary learning algorithm for 3d medical image denoising based on sadct [C]//2013 International Conference on ICICES.Chennai:IEEE,2013:442-447.

[3]Dong Weisheng,Zhang Lei,Shi Guangming,et al.Nonlocally centralized sparse representation for image restoration[J].IEEE Transactions on Image Processing,2013,22(4):1620-1630.

[4]Thavalengal S,Mandal S,Sao A K.Significance of dictionary for sparse coding based pose invariant face recognition[C]//2014 Tewentieth National Conference on Communications.Kanpur:IEEE,2014:1-5.

[5]Lu Weizhi,Bai Cong,Kpalma K,et al.Multi-object tracking using sparse representation[C]//2013 IEEE International Conference on ICASSP.Vancouver:IEEE,2013:2312-2316.

[6]Tang Yufang,Li Xueming,Liu Yang,et al.Sparse dimensionality reduction based on compressed sensing[C]//2014 IEEE WCNC.Istanbul:IEEE,2014:3373-3378.

[7]Sun X,Nasrabadi N M,Tran T D.Task-driven dictionary learning for Hyperspectral Image classification with structured sparsity constraints[C]//2015 IEEE Geoscience and Remote Sensing Society.Milan:IEEE,2015:1-15.

[8]Aharon M,Elad M,Bruckstein A.K-SVD:An algorithm for designing overcomplete dictionary for sparse representation[J].IEEE Transactions on Singal Processing,2006,54(11):4311-4322.

[9]Sahoo S K,Makur A.Enhancing image denoising by controlling noise incursion in learned dictionaries[J].IEEE Signal Processing Letters,2015,22(8):1123-1126.

[10]Mazhar R,Gader P D.EK-SVD:Optimized dictionary design for sparse representations[C]//19th ICPR.Valparaiso:IEEE,2008:1-4.

[11]Feng Jianzhou,Song Li,Yang XiaoKang,et al.Sub clusteringK-SVD:Size variable dictionary learning for sparse representations[C]//2009 16th IEEE ICIP.Cairo:IEEE,2009:7-10.

[12]Ribhu R,Ghosh D.Dictionary design for sparse signal representations usingK-SVD with sparse Bayesian learning[C]//2012 IEEE 11th ICSP.Beijing:IEEE,2012:21-25.

[13]Gu Shuhang,Zhang Lei,Zuo Wangmeng,et al.Weighted nuclear norm minimization with application to image denoising[C]//2014 IEEE CVPR.Columbus:IEEE,2014:2862-2869.

[14]Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthonormal matching pursuit:Recursive function approximation with applications to wavelet decomposition[C]//1993 Conference Record of The Twenty-Seventh Asilomar Conference on Signals,Systems and Computers.Pacific Grove:IEEE,1993:40-44.

[15]Tillmann A M.On the computational Intractability of exact and approximate dictionary learning[J].IEEE Signal Processing Letters,2015,22(1):45-49.

[16]Elad M.Sparse and pedundant representations:From theory to applications in signal and image processing[M].London:Springer,2010:227-244.

[17]Donoho D L,Huo X.Uncertainty principles and ideal atomic decomposition[J].IEEE Transactions on Information Theory,2001,47(7):2845-2862.

[18]Lin Y,Lee D.BayesianL1-norm sparse learning[C]//2006 IEEE ICASSP.Toulouse:IEEE,2006:605-608.

[19]Ram I,Elad M,Cohen I.Image denosing using NL-means via smooth patch ordering[C]//2013 IEEE ICASSP.Vancouver:IEEE,2013:1350-1354.

[20]Srivastava V K.A DCT based algorithm for blocking artifact reduction from DCT coded images[C]//2006 IEEE ICIT.Mumbai:IEEE,2006:2815-2820.

(责任编辑 陶立方)

Imageclassificationdictionarylearningbasedonsparserepresentation

HE Xiaowei, ZHANG Li

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

In order to deal with the weak structure of dictionary in theK-SVD algorithm, an nonlocal classification dictionary learning method (NLC-DL) based on sparse representation was proposed by taking advantage of image nonlocal self-similarity. The method clustered image patches with structural similarity by theK-means algorithm, then the dictionaries for each class were learned to reinforce the effectiveness. The sparse coefficients obtained by the Orthogonal Matching Pursuit algorithm (OMP) were used to optimize all the dictionaries alternately. Both the sparse coefficients and the optimized dictionaries were used for reconstructing the true image. Experimental results showed that the obtained dictionaries achieved a better effect with less error on representing the training sample and maintained the structural information effectively. Furthermore, the proposed method for reconstructing images performed better than the traditional ones in terms of PSNR and visual effect.

nonlocal; self-similarity; sparse representation; dictionary learning;K-means

10.16218/j.issn.1001-5051.2015.04.008

2015-04-07；

：2015-05-07

浙江省自然科学基金资助项目(LY14F010008)

何小卫(1968-),男，浙江金华人，副教授.研究方向：稀疏和低秩；机器学习.

TP391

：A

：1001-5051(2015)04-0402-08