字典原子优化的图像稀疏表示及其应用

李洪均 谢正光 胡 伟 王 伟

(南通大学电子信息学院，南通 226019)

字典原子优化的图像稀疏表示及其应用

李洪均 谢正光 胡 伟 王 伟

(南通大学电子信息学院，南通 226019)

摘 要:为了提高图像稀疏表示性能，提出了一种有效的结构化字典图像稀疏表示方法.针对过完备字典构造和稀疏分解中原子筛选问题，提出了一种基于灰色关联度的字典原子筛选和结构聚类方案.首先，对测试图像分块处理，利用块作为原子样本;然后，计算原子间的灰色关联度，并设置原子灰色关联度的筛选准则;最后，利用结构特征对原子聚类，构造图像稀疏字典.算法利用灰色关联度选择表征能力强的原子，提高字典的表征能力，缓解了传统字典设计对原子个数的依赖;同时，降低了算法的复杂度.将该方法得到的字典用于图像去噪，结果表明，视觉效果明显优于同类算法，峰值信噪比提高2 dB左右，且算法复杂度显著降低.

关键词:图像稀疏表示;原子优化;灰色关联度;原子聚类

图像稀疏表示能够利用很少的元素组合来快速且有效地刻画图像，解决图像传输和压缩等研究中数据量的问题，在实际应用中能够节省空间，提高效率，提升图像处理的质量，有利于推动图像处理领域各项研究的深入与发展.图像稀疏表示研究主要集中在稀疏分解算法和稀疏字典设计2个方面.稀疏表示的核心在于字典的选择，字典的性能决定了是否能对自然图像形成简洁的表示.图像稀疏字典设计方面，国内外学者提出过多种设计方案，如联合基的字典设计、基于图像块特点的多字典构造、基于群稀疏的结构化字典设计以及利用结构聚类的字典设计等［1-2］.这些学习字典方法均仅在某些方面或一定程度上解决图像结构表征的问题.如何寻找图像的最优表示字典、获得高质量的重构图像，是当前图像稀疏表示研究者亟待解决的问题.为获得理想的特征原子，从而更为精确、自适应地匹配图像特征，研究者们提出从自然图像中通过学习构建字典，如最优方向法、推广主成分分析(principal component analysis，PCA)、K-奇异值分解(K-singular value decomposition，K-SVD)算法［3］等.传统的学习字典包含有大量与图像结构不相关的原子，这些不相关原子的学习会降低图像稀疏表示的有效性.而K-SVD算法虽然构建灵活多变，但只考虑了表示向量的整体稀疏性，并没有考虑到稀疏表示向量中任何隐藏的结构.目前结构化稀疏受到广泛关注，学者们开始尝试结构化字典的训练，反映隐藏在数据中的结构，提高稀疏表示的精度.联合基的字典优化设计［1］、群稀疏的结构化字典设计［4］以及利用结构聚类的字典设计［5］等方法可部分解决图像结构表征的问题，但图像字典原子特性研究还不够成熟，在字典原子数目冗余、算法复杂度高、图像退化等因素下，字典的稳健性有待提高.

目前大部分研究主要集中在稀疏编码和原子库训练算法，而对于原子库提取环节的报道并不多，寻找高效的原子库存在困难.因此，选择准确的原子是图像稀疏表示至关重要的环节.本文将试图从原子库中提取高效的原子构建最优的原子库，从而更好地对图像进行稀疏表示，不仅效果有所提升，也缓解了后续环节的压力.

1 字典原子的优化

式中，α为x的稀疏表示系数;D为过完备字典;ε为逼近误差容限.

在图像处理中，利用测试图像随机提取子图像，构成训练样本集F={fi}Li=1，并利用这些样本集训练获得能够很好地稀疏逼近样本块的字典.D={d1，d2，…，dL}为待构造的过完备字典，di为字典原子，则稀疏问题的目标函数为

式中，αi为对应样本的稀疏表示系数.

由式(2)可知，参与图像重构的原子性能直接决定重构图像的主客观效果.本文借助原子包含的结构先验信息，利用原子相似性进行重新组织，试图从训练的原子库中移出表征能力弱的原子并利用聚类的方式降低同类原子的冗余.

1.1 原子量对字典性能的重要性

文献［3］提出了基于K-SVD原子库训练和稀疏表示方法，并运用于图像去噪领域.当图像噪声较大时，K-SVD存在收敛性问题.文献［6］提出了多尺度的K-奇异值分解原子训练和稀疏表示方法，与K-SVD相比，多尺度域的图像恢复效果明显提升;文献［7］提出了基于块的K-SVD的稀疏表示，利用聚类算法寻找结构相似的原子，设计了原子块的K-SVD算法，提高了算法的效率.但对于原子块的大小以及原子数的研究还仅仅局限于固定值的设定，对于结构丰富的图像来说是不合理的.

表 1 给出了 K-SVD［3］，BKSVD-SAC［7］，BKSVD［7］三种算法中原子个数对图像稀疏表示效果的影响.其中，K表示原子个数，峰值信噪比(PSNR)越大表示去噪的效果越好，图像越清晰.图像稀疏表示的效果与原子个数之间存在关联.由表1中的数据可看出，原子个数不同，获得的结果也有所不同，在某个数值下会达到最优值.因此，原子个数的选取是字典设计的关键问题.

表1 稀疏原子个数对算法的影响

1.2 字典原子特性分析

对于图像处理而言，图像退化等因素引起图像信息相对原始图像信息的不确定，使得原有的原子关联度分析受到限制.因此，需要引入不确定性分析方法，以提高原子分类抗噪性能，提升分类结果的精确性［8］.以灰色理论为代表的不确定性系统研究方法，对先验知识要求不高，样本量小，能够提高原子分类性能，保证分类结果的精确性，提高算法的效率，为解决字典原子特性描述提供了新的技术［9-10］.

图像信号的稀疏度以及冗余字典原子间的关联特性是稀疏表示的决定因素［11］，字典原子特性直接决定了图像字典性能，影响图像稀疏表示的效果.因此，描述和衡量冗余字典的相关特性尤其重要.针对这个问题，本文将在原子库的筛选中引入原子关联度方法.原子关联度ξk定义为

式中，ai为原子库第i个原子;ξ为原子间的灰色关联度.

①c:j和c:j+1为相邻两个原子，则系数序列为

②对序列进行处理，获得初值序列和差值序列，即

③用ξ表示2个序列的灰色关联度，即

式中，分辨率系数λ为常数;差序列中最大值为max(Δi)，同理，最小值为 min(Δi).两原子序列的总体关联度可以定义为

式中，ξ:j～j+1为相邻原子的灰色关联度值.

原子灰色关联度表征算法是基于图像结构信息之间的相关性，计算原子间的灰色关联度，并依据关联度的大小重新对原子排列.灰色关联度高则原子间的结构特性相似，关联度低则原子间的结构特性弱相似.

1.3 字典原子的聚类

在原子排列的基础上对原子进行聚类分析，有利于更好地研究原子间关联度与结构特性之间的联系.目前常用聚类算法直接利用相似性进行数据组织，不取其他的额外信息，如层次聚类算法、AP聚类算法、加性聚类算法、谱聚类算法、K-means算法等.

如何利用其他类别先验信息，如图像结构特点，自适应地选择聚类尺度的规模，提高图像块的表征能力，以及设计符合图像字典原子相似度测量的准则，提高原子之间评价的精度是研究的目标.本文将利用灰色关联度来表征字典原子结构相似度对相似结构信息的原子进行聚类.

基于灰色关联度的原子聚类算法，能够解决K-means算法对初始聚类中心及样本输入顺序敏感的问题.本文的聚类算法首先计算所有原子间的关联度值，选择关联度值的平均值作为聚类原则，构成初始聚类;根据原子之间的关联度大小，把测试原子归类到最关联的类中，然后重新计算所有原子的灰色关联度得到新的聚类中心，最后利用类间关联度的差值作为聚类停止的依据.本文构造的字典规模并不固定，依据测试图像原子关联度的分布情况，自适应地调整原子个数，因此，具有更好的适应性.

为了保证原子个数不变，在对原子库中部分原子进行不同类型抽取的同时复制同类原子.图1给出了不同原子聚类尺度下的原子分布.由图可知，聚类尺度的增加，使得原子之间的聚集程度增强.

图1 不同原子聚类尺度下的原子分布图

为了更好地说明本文提出的字典优化算法的有效性，将优化的字典算法运用于K-SVD，BKSVD-SAC，BKSVD三种算法中.图2给出了不同聚类尺度下，训练字典的示意图.由图可知，原始算法获得的字典，原子分布较散，大系数不足且分布不均;而优化后的各个聚类尺度下的字典，原子明显集中，大系数分布均匀.由字典原子分布的特点大致可以判断出，聚类尺度J=2，8的字典稀疏效果较好，能够较好地表征图像.

1.4 算法流程

将灰色关联理论运用到字典原子的优化中，充分利用灰色理论在不确定性分析中的优点，不仅能够更好地刻画原子间的关联度，同时也解决了原子量选取的问题.本文字典原子优化的图像稀疏表示算法流程如下:

①测试图像随机划分为8×8大小的相互重叠的图像块，并获得Y={c1，c2，…，cn}，每一列为一个训练样本.

②对Y的每一列原子进行相似度分析，利用式(4)～(10)计算原子间的灰色关联度值;将原子按照灰色关联度进行排序，并利用原子的灰色关联度作为原子块聚类的依据.

③将灰色关联度两等分，并计算其各自区域的关联度均值;当相邻类的关联度均值小于聚类数的倒数值，则继续分类，否则停止分类.

④结合聚类尺度对字典的影响，选择合适的聚类尺度，获得优化字典Doptimal={G1，G2，…，GJ}.

⑤将优化字典代入稀疏表示的公式求解，实现图像的稀疏表示.

2 算法的试验结果及分析

本文实验是在Window 7的计算机(Inter(R)Core(TM)2 Duo CPU T5670@1.80 GHz)上进行的，使用Matlab 2011b编程.所有仿真均采用相同的参数配置.本文先将测试图像随机划分为8×8大小相互重叠的图像块，对这些子图像进行训练得到自适应过完备字典;然后，对字典原子进行优化处理，将优化后的字典Doptimal进行稀疏编码和更新;最后获得 Improved-K-SVD(I-K-SVD)算法，Improved-BKSVD-SAC(I-BKSVD-SAC)算法和Improved-BKSVD(I-BKSVD)算法.

选取了256×256像素的 Lena，Barbara，Baboon，Peppers图像作为测试图像.并从2个方面进行比较:① 通过利用视觉效果对比I-K-SVD，I-BKSVD-SAC，I-BKSVD和原始算法;图3给出了主观视觉比较结果，改进算法明显在图像边缘和纹理等特征上优于原始重构图像.② 以图像的峰值信噪比和结构相似度(structural SIMilarity，SSIM)［12］进行定量分析比较.表2给出不同聚类尺度下3种改进算法的定量比较.由表可见，3种改进算法的PSNR和SSIM都要大于原始算法的PSNR和SSIM，并且在聚类尺度为8时，算法的效果要好于其他聚类尺度.

图3 不同原子聚类尺度下的图像重构效果比较

表2 各算法比较结果

K-SVD算法的收敛性依赖于追踪算法的收敛性，在稀疏编码阶段具有收敛性.而K-SVD方法在噪声较大时，不能确保算法的收敛性.主要原因是不能保证字典原子更新过程中，误差减小或者不变.而 I-K-SVD，I-BKSVD-SAC，I-BKSVD 算法中字典原子优化以灰色关联度为依据，采用类间关联度差作为更新原则，该差值与聚类尺度成反比，差值为定值.因此，改进后的算法不存在收敛问题.

3 算法在图像去噪中的应用

将优化字典的稀疏表示算法运用于图像去噪领域.在实验仿真中统一采用原子聚类尺度8，对含噪声的图像进行去噪处理，结果如图4所示.由图可见，优化字典的稀疏表示算法能更好地去除图像中的噪声，更好地恢复了图像.

图4 图像去噪效果比较

为了研究字典大小对算法的影响，图5(a)给出了优化算法的比较.由图可见，I-K-SVD算法的去噪效果要优于其他算法，而且算法受字典原子个数的影响远小于其他算法.为了进一步说明本文优化字典稀疏算法的适用性，将该优化字典运用于BKSVD和BKSVD-SAC算法，去噪结果如图5(b)所示.对比原始算法，改进后的算法去噪效果较好，并且受字典原子个数波动小.因此，优化字典的图像稀疏表示算法不仅稀疏能力有所提升，同时也解决了原子个数设置的问题.

图5 字典原子个数对算法的影响

4 结语

图像字典中的冗余因子一直是字典研究的热点.为了使冗余字典能够自适应地表征图像，利用字典原子之间的灰色关联度作为优化依据，提出了字典原子优化算法.该方法能够更好地刻画图像信息，字典原子的效率高，解决了字典选择的问题.稀疏性实验结果分析表明，该算法优化后的字典性能高，将该字典运用在图像稀疏表示中，获得很好的重构效果.同时，本文的优化字典算法具有较好的适用性，将优化字典用于不同的稀疏算法中，改进的算法具有更好的去噪效果，同时算法稳定性要优于原算法.本文仅针对原子库筛选进行了研究，并没有对后续字典编码和更新进行研究，同时，对于聚类尺度的研究还处在尝试阶段.下一步工作将进一步研究聚类尺度如何自适应地选取以及将原子优化运用于字典更新算法中.

表3 算法去噪比较

［1］Smith L N，Elad M.Improve dictionary learning:multiple dictionary updates and coefficient reuse［J］.IEEE Signal Processing Letter，2013，20(1):79-82.

［2］练秋生，张伟.基于图像块分类稀疏表示的超分辨率重构算法［J］.电子学报，2012，40(5):920-925.

Lian Qiusheng，Zhang Wei.Image super-resolution algorithms based on sparse representation of classified image patches［J］.Acta Electronica Sinica，2012，40(5):920-925.(in Chinese)

［3］Aharon M，Elad M，Bruekstein A.K-SVD:an algorithm for designing overcomplete dictionaries for sparse representation［J］.IEEE Transaction on Signal Processing，2006，54(11):4311-4322.

［4］郭景峰，李贤.基于群稀疏的结构化字典学习［J］.中国图象图形学报，2012，17(11):1347-1352.

Guo Jingfeng，Li Xian.Structured dictionary learning based on group sparsity［J］.Journal of Image and Graphics，2012，17(11):1347-1352.(in Chinese)

［5］Chatterjee P，Milanfar P.Clustering-based denoising with locally learned dictionaries［J］.IEEE Transactionson Image Processing，2009，18(7):1438-1451.

［6］Mairal J，Sapiro G，Elad M.Learning multiscale sparse representations for image and video restoration［J］.SIAM Multiscale Modeling and Simulation，2008，7(1):214-241.

［7］Kevin R，Lihi Z M，Yonina C E.Dictionary optimization for block-sparse representations［J］.IEEE Transactions on Signal Processing，2012，60(5):2386-2395.

［8］武森，冯小东，单志广.基于不完备数据聚类的缺失数据填补方法［J］.计算机学报，2012，35(8):1726-1738.

Wu Sen，Feng Xiaodong，Shan Zhiguang.Missing data imputation approach based on incomplete data clustering［J］.Chinese Journal of Computers，2012，35(8):1726-1738.(in Chinese)

［9］Dang J L.Control problems of grey system［J］.System and Control Letters，1982，1(5):288-294.

［10］马苗，田红鹏，张艳宁.灰色理论在图像工程中的应用研究进展［J］.中国图象图形学报，2007，12(11):1943-1951.

Ma Miao，Tian Hongpeng，Zhang Yanning.Research Progress on the application of grey theory in image engineering［J］.Journal of Image and Graphics，2007，12(11):1943-1951.(in Chinese)

［11］Yu Guoshen，Sapiro G，Mallat S.Solving inverse problemswith piecewise linearestimators:from Gaussian mixture models to structured sparsity［J］.IEEE Transactions on Image Processing，2012，21(5):2481-2498.

［12］Wang Z，Bovik A C.A universal image quality index［J］.IEEE Signal Processing Letters，2002，9(3):81-84.

Optimization of dictionary atoms in image sparse representations and its application

Li Hongjun Xie Zhengguang Hu Wei Wang Wei
(School of Electronic Information Engineering，Nantong University，Nantong 226019，China)

Abstract:In order to improve the performance of image sparse representation，an effective representation method based on a structured image sparse dictionary is proposed.For the atomic selecting problem in constructing an over-complete dictionary and sparse decomposition，a kind of images dictionary atom selecting and structure clustering method based on the grey relation is proposed.First，atoms are selected by the blocking test image.Then the grey relation between atoms is calculated，and the rule of atom selection is set up.Finally，atoms are clustered by characteristics of structures，and a sparse representation dictionary is constructed.In this method，atoms with high representative performance are selected by the grey relation，improving the ability of capturing the image structure.The method solves the problem of a traditional dictionary designed depending on the number of selected atoms and also reduces the complexity.The simulation results show that the proposed method is superior to other algorithms in objective quality.The peak signal to noise ratio value increases about 2 dB.And the complexity of the algorithm is decreases greatly.

Key words:image sparse representation;atomic optimization;grey relation;atomic cluster

中图分类号:TN216

A

1001－0505(2014)01-0116-07

doi:10.3969/j.issn.1001 －0505.2014.01.021

收稿日期:2013-07-03.

李洪均(1981—)，男，博士，讲师，lihongjun@ntu.edu.cn.

基金项目:国家自然科学基金资助项目(61171077)、江苏省高校自然科学研究资助项目(12KJB510025，12KJB510026)、南通市引进人才资助项目(03080415)、南通大学创新人才基金资助项目(2009).

李洪均，谢正光，胡伟，等.字典原子优化的图像稀疏表示及其应用［J］.东南大学学报:自然科学版，2014，44(1):116-122.［doi:10.3969/j.issn.1001 －0505.2014.01.021］