用于超分辨率重建的同构过完备字典学习方法*

谢宝陵，徐国明,2

(1.陆军军官学院基础部，安徽 合肥 230031；2.合肥工业大学计算机与信息学院，安徽 合肥 230009)

用于超分辨率重建的同构过完备字典学习方法*

谢宝陵1，徐国明1,2

(1.陆军军官学院基础部，安徽 合肥 230031；2.合肥工业大学计算机与信息学院，安徽 合肥 230009)

构造合适的过完备字典是基于稀疏表示的超分辨率重建中的关键问题之一。在最大似然估计准则下，建立基于混合高斯的同构过完备字典学习模型。模型采用加权的l2范数来刻画分解残差，由分解残差设计权值矩阵，并且将同构的双字典学习问题转化为单字典的学习。采用稀疏编码和字典更新的交替迭代策略完成目标函数的求解，由内点法进行稀疏编码，采用拉格朗日对偶法完成字典更新。最后将学习得到的字典用于超分辨率重建实验，并与其他方法进行比较。实验结果验证了该模型和算法的有效性。

超分辨率；过完备字典；混合高斯；稀疏编码

1 引言

最近几年，基于稀疏表示的图像超分辨率重建引起了国内外众多研究者的关注。其基本思想是：需要重建的高分辨率图像块通过与高分辨率过完备字典的线性组合来求得，而表示系数则通过观测图像在低分辨率过完备字典下进行稀疏编码来求得。在此过程中，如何构造合适的高/低分辨率的过完备字典，使得图像的主要特征和结构能够用稀疏的非零系数来表示，这对于重建效果具有重要影响，不同的算法采用了不同的字典构造方法。

在文献[1]中，Yang J C等人用线性规划求解低分辨率图像块的稀疏表示，并通过与高分辨率字典的线性组合得到高分辨率的图像块，其高分辨率字典是简单地采用随机的高分辨率样本图像块组合而成，而低分辨率字典是由对应的高分辨率样本块经下采样及加噪声后生成的低分辨率样本组合而成。然后在文献[2]中，他们又对自己的方法进行了改进，采用联合字典训练的方法同时训练出高/低分辨率字典，训练的样本集通过低分辨率图像块的特征提取获得。Zeyde R等人[3]在文献[12]方法的基础上，分别对高/低分辨率字典采用不同的方法进行离线训练，低分辨率字典采用K-SVD算法[4]直接训练，而高分辨率字典则通过进一步的优化(采用共轭梯度法)求得。Pu Jian等人[5]则针对高/低分辨率图像块对的异构特点，通过求解在稀疏表示下的同构图像块对，从而利用异构数据集构造出同构字典。Sun Yu-bao等人[6]针对图像不同结构形态，提出选取紧框架系统分别建立多成份子字典，分别利用Curvelet变换和Wave-Atom变换作为几何结构和纹理成份子字典，形成图像的多形态稀疏表示模型，采用交替迭代收缩数值算法求解各子成份字典下的稀疏表示。而Lian Qiu-sheng等人[7]则利用图像局部特征将图像块分为平滑、边缘和不规则结构三种类型，其中边缘块细分为多个方向，然后对边缘和不规则结构块分别训练各自对应的低分辨率和高分辨率字典，通过正交匹配追踪算法重建。

然而，上述重建方法所采用的字典或多或少都存在不足。采用随机字典简单快速，对于特定目标效果较好，显然有失一般性；多成份子字典虽然能够更好地保持图像的多种结构形态，但是缺少相应的快速分解和重构算法；通过学习或训练算法得到的字典能够具有更稀疏的表示，并取得了较好的重建效果，但是通常采用l1范数或l2范数来刻画分解误差，也就是假设分解误差符合拉普拉斯或高斯分布，而这种假设并不完全符合实际。由于采用l2范数来刻画分解误差进行稀疏编码是个带稀疏性约束的最小二乘问题，显然，不同的图像块其分解误差是不一样的，在这种情况下，应该给误差较小的图像块(精度较高)较大的权值，才能够获得更精确的稀疏分解系数，从而能够重建出更好的效果。

受鲁棒性稀疏编码方法[8]和离线字典训练[3]思想启发，本文提出同构的高/低分辨率过完备字典学习方法。首先建立基于混合高斯稀疏编码的同构字典学习模型，在最大似然估计准则下，假设分解误差符合混合高斯分布，由l2范数正则化进行约束，而稀疏性则由带参数的l1范数正则化进行约束。然后根据分解误差设计权值矩阵，字典学习由稀疏编码和字典更新两个过程完成，采用l1正则化的最小二乘内点法[9]完成稀疏编码,而字典更新则采用拉格朗日对偶法[10]。最后，将学习得到的高/低分辨率同构字典用于Yang J C等人[2]和Zeyde R等人[3]的超分辨率重建，并与之进行比较。实验结果表明，本文方法学习的字典能够更有效地描述图像的结构信息，从而重建出更好的效果，验证了本文方法的有效性。

2 同构字典学习模型

对于一组给定的训练样本X={x1,x2,…,xn}∈Rn，字典学习的任务就是通过稀疏编码学习出一过完备字典D∈Rn×m，其列向量记为di(i=1,2,…,m)，使训练样本在D中具有稀疏表示。此优化问题的目标函数可以表示如下：

(1)

(2)

对于此式的求解，目前提出了大量算法[11,12]。当同时求解D和α时，此问题是个非凸优化问题，但是当固定其中一个而求另一个时，就可以转化为凸优化问题进行求解，故此问题通常由两个过程完成：稀疏编码和字典更新。在稀疏编码阶段，认为字典已经求得，当完成稀疏编码后，再由此稀疏表示系数来进行字典更新。两个过程交替进行，从而完成字典的学习，同时得到稀疏表示系数矩阵。

在基于稀疏表示的超分辨率重建过程中需要两个过完备字典：高分辨率字典Dh和低分辨率字典Dl。由观测图像求解在Dl下的表示系数，由此表示系数与Dh的线性组合得到高分辨率图像，所以必须保证图像在Dh和Dl上具有相同的表示系数，也就是Dh和Dl的学习必须是同构的。为此，首先构造训练样本对P={Xh,Yl}，其中Xh={x1,x2,…,xn}表示高分辨率图像样本集，而Yl={y1,y2,…,yn}表示对应的低分辨率图像样本集(或特征提取)。同构字典学习在这两个训练样本集上进行，以保证稀疏表示系数是相同的。由式(2)，此问题可以描述如下：

(3)

和

(4)

将式(3)和式(4)合并，从而有：

(5)

其中，N和M分别表示高分辨率和低分辨率样本写成列向量形式的维数，而1/N和1/M用以平衡式(3)和式(4)的代价项。为了利用式(2)的求解策略求解式(5),将式(5)写成如下形式：

(6)

其中，

(7)

在文献[5]和文献[2]的超分辨率重建过程中，都采用了式(6)的模型来完成字典的学习，不同之处在于前者采用K-SVD算法[4]直接求解，而后者采用文献[10]中的方法直接求解。

(8)

其中，W是对角的权值矩阵，对于不同的分解残差定义不同的权值。根据式(8),则式(6)转换为：

(9)

在文献[8]中，YangM等人针对人脸识别中的鲁棒性稀疏编码问题，给出了W的定义方法：

(10)

3 交替迭代字典学习算法

对于模型(9)的双变量优化问题的求解，本文采用K-SVD字典学习[4]的策略，其基本思想是由训练样本和初始字典开始，通过稀疏编码和字典更新两个过程的交替迭代完成求解。在稀疏编码阶段，固定字典Dc，求解α，即：

(11)

对于此式，由于数据规模较大，采用文献[9]提出的适合求解大尺度l1正则化约束的最小二乘问题的内点法进行求解，以提高算法效率。

在字典更新阶段，固定α，更新字典Dc，即：

(12)

同样基于效率考虑，利用拉格朗日对偶法[10]进行求解。最后，Dh和Dl由Dc拆分得到。

由于字典的训练是对图像块进行的，所以对于训练所需的样本集Xc，首先由高分辨率的样本图像Xh逐行取其图像块，而低分辨率的图像样本则由Xh下采样得到。为了使稀疏编码得到的表示系数能够更精确地表达观测图像的结构特征，对下采样得到的低分辨率图像样本进行特征提取，采用文献[2]中的四个1-D滤波器，如式(13)所示：

(13)

由此构成低分辨率图像样本集Yl，然后由式(7)垂直串联成Xc。对低分辨率的字典Dc的初始值可以是随机数，也可以由训练样本进行离散余弦变换等得到。具体算法描述如下：

初始化：由训练样本图像的图像块根据式(7)构成样本集Xc，Dc由随机值构成，设置迭代次数T。

步骤1重复执行；

步骤2稀疏编码，由式(10)计算权值矩阵Wi,i；

步骤3由Wi,i及式(11)求各样本图像块在字典Dc下的表示系数αi，当求得所有样本在当前字典下的表示系数后，则获得稀疏表示系数矩阵α=(α1,α2,…,αN)；

步骤4字典更新，根据式(12)完成字典Dc的更新；

步骤5T=T-1，若T≠0,转步骤1，否则转步骤6；

步骤6列数不变，根据下采样倍数，将Dc拆分成两个相同列数的字典Dh和Dl。

4 实验结果与分析

为了验证本文方法的有效性，将本文方法学习的字典分别用于Yang J C等人[2](以下简称为Yang)和Zeyde R等人[3](以下简称为Zeyde)的基于稀疏表示的超分辨率重建过程中，采用不同的图像数据进行重建实验，并从视觉效果、峰值信噪比(PSNR)等方面进行比较。实验环境为：MatLab 7.9.0运行于P4 3.0 GHz，1.25 GB RAM的PC机的Windows XP SP3平台。字典学习过程中λ=0.15，图像块大小为5×5，图像块数量为100 000个，字典大小为512，得到的3倍率高/低分辨率字典如图1所示。原始字典大小分别为25×512和100×512，由于低分辨率样本集进行了四个特征提取，故字典行数是高分辨率字典的四倍，为方便显示，处理成图中所示形状。以下实验不做说明，都是在此参数下进行的。

Figure 1 Learned isomorphic over-complete dictionary图1 学习得到的同构过完备字典

4.1 与Yang 的方法进行比较

图2a～图2d是部分测试图像，其中图2a和图2b是标准灰度图像，图2c是伪装目标的偏振图像，图2d是模拟坦克的红外图像，图2a～图2c的实际大小是384×384，图2d的实际大小是480×480。图3是对应的三倍下采样低分辨率图像。重建时λ=0.2，进行三倍超分辨率重建。为保证比较的客观性，当图1的字典用于Yang的重建过程时，保持参数设置不变。

图4是重建结果的局部图像，从帽檐、人脸及坦克模型的轮廓可以看出，采用本文方法能够更好地保持图像的大尺度边缘和轮廓结构，其边缘的锯齿效应明显减少；通过对局部结果的观察不难发现，无论是头发、眼睛，还是坦克模型前端的设备等，其纹理等小尺度细节内容也保持得更加完整。

Figure 2 Testing images图2 测试图像

Figure 3 Down-sampled images图3 下采样图像

Figure 4 Comparison with Yang’s method图4 与Yang的重建结果比较

为进一步客观评价本文方法的结果，对多幅图像进行超分辨率重建，并对实验结果计算其PSNR值，PSNR定义如下：

其中，yij和xij分别是大小为m×n的原始高分辨率图像和超分辨率重建结果。表1是计算结果，表中图像除了图2显示的图像外，其余的都是标准灰度测试图像。表2中数据表明，本文方法无论是对灰度图像、偏振图像，还是红外图像，在客观指标上都取得了更好的效果，表2中平均数据提高约0.7dB。

Table 1 PSNR(dB) for different methods表1 重建结果1的PSNR值 dB

4.2 与Zeyde的方法进行比较

采用图2的实验图像将图1的字典应用于Zeyde的重建过程，并同样进行三倍超分辨率重建，实验中λ=0.1。图5a～图5d是三倍超分辨率重建结果的局部图像，从人脸五官、台布和桌腿边缘、以及台布花纹等可以看出，本文方法的重建结果无论是大尺度的边缘和轮廓结构还是小尺度的细节内容同样都保持得更加完整。

Figure 5 Comparison with Zeyde’s method图5 与Zeyde的重建结果比较

表2是PSNR值计算结果，表中数据表明当本文方法训练的字典用于Zeyde的重建过程时，在客观指标上同样取得了更好的效果，表中数据平均约提高0.6 dB。

4.3 主要参数对重建结果的影响

为进一步验证本文方法的有效性，对字典学习中的主要参数如字典大小、图像样本块数量等进行实验验证。表3是不同字典大小的重建结果比较，实验图像是lena，表中“本文方法1”指本文字典用于Yang的超分辨率重建，而“本文方法2”指本文字典用于Zeyde重建过程。可以看出，字典越大，重建效果越好，在两种重建方法下，本文字典能够在较小的情况下取得与Yang和Zeyde相当的重建效果。这表明本文字典对图像更具有表现力，这对于提高超分辨率重建效率具有意义。另外，经实验表明样本块数量的增加对重建效果影响很小，由于样本块数量与样本块大小及重叠区域也有关系，同时样本块大小及重叠区域对重建结构有影响，经实验验证，样本块大小在3～5、重叠区域在大于样本大小一半以上(上取整)、样本块数量在50 000～1 000 000，会在字典学习效率和重建效果之间取得比较好的平衡。

Table 2 PSNR(dB) for different methods表2 重建结果2的PSNR值 dB

Table 3 PSNR(dB) for different dictionary size表3 不同字典大小重建结果的PSNR值 dB

5 结束语

针对稀疏表示下的图像超分辨率重建的字典学习问题，本文提出基于混合高斯稀疏编码模型的同构的过完备字典学习方法。模型在最大似然估计准则下假设分解误差符合混合高斯分布，以使字典能够更精确描述图像结构信息，根据分解误差设计权值矩阵，使问题转换成加权的范数逼近问题，数值求解算法则由稀疏编码和字典更新两个过程的交替迭代完成。实验结果验证了本文方法的有效性。

[1] Yang J C, Wright J, Huang T, et al. Image super-resolution as sparse representation of raw image patches[C]∥Proc of IEEE Computer Vision and Pattern Recognition(CVPR),2008:1-8.

[2] Yang J C, Wright J, Huang T, et al. Image super-resolution via sparse representation[J]. IEEE Transactions on Image Processing, 2010, 19(11):2861-2873.

[3] Zeyde R, Elad M, Protter M. On single image scale-up using sparse-representations[C]∥Proc of the 7th International Conference on Curves and Surfaces, 2010:1-22.

[4] Aharon M, Elad M, Bruckstein A M. The K-SVD:An algorithm for designing of over-complete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11):4311-4322.

[5] Pu Jian, Zhang Jun-ping. Super-resolution through dictionary learning and sparse representation[J]. PR&AI, 2010, 23(3):335-340. (in Chinese)

[6] Sun Yu-bao, Wei Zhi-hui, Xiao Liang, et al. Multimorphology sparsity regularized image super-resolution[J]. Acta Electronica Sinica, 2010, 38(12):2898-2903. (in Chinese)

[7] Lian Qiu-sheng,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)

[8] Yang M, Zhang L, Yang J, et al. Robust sparse coding for face recognition[C]∥Proc of CVPR’11, 2011:625-632.

[9] Kim S J, Koh K, Lustig M, et al. An interior-point method for large-scale l1-regularized least squares[J]. IEEE Journal on Selected Topics in Signal Processing, 2007, 1(4):606-617.

[10] Lee H, Battle A, Raina R, et al. Efficient sparse coding algorithms[C]∥Proc of 2006 Conference on Advanced in Neural Information Processing Systems, 2007:801-808.

[11] Yang Jing-yu, Peng Yi-gang, Xu Wen-li, et al. Ways to sparse representation:An overview[J]. Science in China Se

ries F:Information Science, 2009, 52(4):695-703.

[12] Rubinstein R, Zibulevsky A M, Elad M. Dictionaries for sparse representation modeling[J]. IEEE Transactions on Signal Process, 2010, 98(6):1045-1057.

[13] Wright J, Ma Y. Dense error correction via l1 minimization[J]. IEEE Transactions on Information Theory, 2010, 56(7):3540-3560.

[14] Boyd S,Vandenberghe L. Convex optimization[M]. New York:Cambridge University Press, 2009.

附中文参考文献：

[5] 浦剑，张军平. 基于词典学习和稀疏表示的超分辨率方法[J]. 模式识别与人工智能, 2010, 23(3):335-340.

[6] 孙玉宝，韦志辉，肖亮，等.多形态稀疏性正则化的图像超分辨率算法[J].电子学报, 2010,38(12):2898-2903.

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

XIEBao-ling,born in 1960,professor,his research interests include software engineering, and parallel algorithm design.

徐国明(1979-),男，安徽太和人，博士生，讲师，研究方向为图像稀疏表示和超分辨率重建。E-mail:xgm121@163.com

XUGuo-ming,born in 1979,PhD candidate,lecturer,his research interests include image sparse representation, and super-resolution reconstruction.

Anisomorphicover-completedictionarylearningmethodforsuper-resolutionreconstruction

XIE Bao-ling1,XU Guo-ming1,2

(1.Department of Basic Sciences,Army Officer Academy,PLA,Hefei 230031;2.School of Computer and Information,Hefei University of Technology,Hefei 230009,China)

Constructing an appropriate over-complete dictionary is one of the key problems of super-resolution based on sparse representation. In the maximum likelihood estimation principle, an isomorphic over-complete dictionary learning model based on mixture Gaussian is proposed. Firstly, the sparse coding residual of the model is described by the weight l2-norm and the weight matrix is designed by the residual. Secondly,the isomorphic coupled dictionary learning problem is translated into the single dictionary learning problem. The dictionary is learned by the alternate and iterative strategy using sparse coding and dictionary updating. An interior-point method is used in sparse coding and Lagrange dual is used in dictionary updating. Finally, the learned dictionary is used in the super-resolution experiment,and compared with other methods.The experimental results demonstrate the effectiveness of the proposed method.

super-resolution;over-complete dictionary;mixture Gaussian;sparse coding

1007-130X(2014)08-1441-06

2012-10-31;

：2013-02-25

安徽省自然科学基金资助项目(1208085QF115)

TP391.9;TN911.73

：A

10.3969/j.issn.1007-130X.2014.08.004

谢宝陵(1960-),男，安徽滁州人，教授，研究方向为软件工程和并行算法设计。E-mail:89662550@qq.com

通信地址：230031 安徽省合肥市蜀山区黄山路451号055信箱

Address:P.O.Box 055,451 Huangshan Rd,Shushan District,Hefei 230031,Anhui,P.R.China