总第330期2017年第4期
计算机与数字工程
Computer /Digital Engineering
Vol.45 No.4
陈小陶1许道云2
!.贵州大学数学系贵阳550025)!.贵州大学计算机科学系贵阳550025)
摘要在利用稀疏表示技术重构图像的应用中，传统的方法是独立地计算一组重叠的图像块，在表示中只针对每个
图像块进行单独稀疏编码。利用卷积稀疏表示，可以将整个图像看做是一个整体，对其进行稀疏编码，由滤波器字典与相应
特征响应的卷积总和代替传统的字典矩阵与编码系数的乘积对图像进行分解。论文基于卷积稀疏表示方
法，提出一个图像重构算法，利用交替方向乘法器方法(ADMM)对输人图像进行稀疏逼近，得到特征响应系数，达到对图像卷积分解的目的。实验结果说明卷积分解机制稀疏性能较优，更适合于图像重构。
关键词稀疏表示；卷积稀疏表示&ADMM；图像重构
中图分类号TP391 DO# 10.3969/j.issn1672-9722. 2017. 04.029
Image Reconstruction Algorithm
Based on Convolution Sparse Representation
CHEN Xiaotao1XU Dao y un2
(1.Department of Mathematics?Guizhou University,Guiyang550025)
(2.Department of Computer Science,Guizhou University,Guiyang550025)
Abstract In the application of sparse representation in image reconstruction,the traditional method is to compute a set of overlapping image blocks independently.Using convolution sparse representatio
n,the whole image is seen as a whole,the of sparse coding and by the filter dictionary and corresponding characteristic response of product of traditional dictionary matrix and coding coefficients for image decomposition,In representation modll of convolution，an image reconstruction algorithm i s proposed，the input image is ap alternating direction multiplier method(ADMM)，and t he characteristic response coefficient is obtained.The experimental results show that the sparse performance of the convolution decomposition mechanism is bett image reconstruction
Key Words sparse representation，convolution sparse representation，ADMM，image reconstruction
Class Number TP391
1引言
稀疏表示（SparseRepresentation)[1~2]是通过 用尽可能少的原子系数线性表示原始信号，它与压 缩感知（CompressedSensing)(~4]有着直接的联系。压缩感知提出如果一个信号是稀疏的或者压 缩的，原始信号可以通过这些少量的测量值进行重构。信号可以稀疏表示是压缩感知的先验条件，由字典矩阵依据稀疏度量标准求解变换后得到的稀 疏向量再通过逆变换从而实现信号的精确重构或 近似
重构。由字典矩阵依据稀疏度量标准求解变 换后得到的稀疏向量求解变换的过程在稀疏表示 中叫做稀疏分解。依据压缩感知中的重构原理，可以先通过稀疏分解得到稀疏系数，再通过逆变换
"收稿日期：2016年10月5日，修回日期：2016年11月26日
基金项目：国家自然科学基金(编号$1262006)资助。
作者简介：陈小陶，女，硕士研究生，研究方向：密码学理论与工程。许道云，男，博士，教授，博士生导师，研究方向: SAT问题、可计算性与计算复杂性、算法设计与分析等。
732陈小陶等：一个基于卷积稀疏表示的图像重枸算法第45卷
重构图像。
稀疏分解问题是指，在字典张成的整个信号空 间下，依据稀疏度量标准寻信号的最优解，即稀 疏优化。典型稀疏度量标准包括/。范数、^范数、范数以及k(〇<^<i)范数。目前，国内外学者基 于传统的稀疏表示模型提出了很多有效的稀疏分 解算法，大体可以分为两大类：松弛优化算法和贪 婪追踪算法。基于松弛优化思想提出了梯度投影 稀疏重建算法(GPSR)5、内点法(IPM)()、交替方
向法(ADM)™等算法。这类算法简单易于实现，然而处理大尺度信号时，时间复杂度高。1993年，Ma
llat和Zhang在文献[8]中首次提出匹配追踪算 法(厦31(*62>+^1，厦>)，其主要思想是在、。范 数稀疏约束下，通过迭代，每次从冗余字典中寻
与残差信号最匹配的原子，逐步稀疏逼近信号。MP算法利用内积运算度量原子与信号之间的匹
配程度，计算复杂度低。针对M P算法，研究者们 进行了深入的探讨并提出了许多改进算法，主要有 正交匹配追踪（Orthogonal Matching Pursuit，OMP)、Stage-wiseOMP(StOMP)、基追踪等算法[1。]。
虽然基于传统的稀疏表示方法可以大大减小 问题的计算，也获得了很好的效果，但是以往的研 究通常是独立地处理重叠块，最后通过平均每一块 之间的重叠像素来获得结果。因为这种处理方法 使得每个像素的输出图像将被估计更多次，所以相 邻的块之间的重叠像素将提供更好的重构结果。然而，在解决块估计问题时，这种“重叠平均”机制 忽略了一个重要的约束，重叠区域中的像素相邻的 块应该是完全一样的，即一致性。一致性约束提供 了在处理每一个单一的估计问题的先验信息。最 近，文献[11]提出了一种聚合方法，以减轻重叠块 之间的不一致，并在图像恢复方面取得了较好的效 果。然而，对于图像重构方面，仍需要更好的方法 证明一致性约束的重要性。
因为图像块之间的一致性，2。1。年，Zeiler在 文献[12]最早提出卷积稀疏表示，利用带卷积的稀 疏编码实现稀疏表示整个图像，即利用滤波器与相 应特征响应的卷积总和，代替传统的字典矩阵与编
码系数的乘积对信号进行分解。同年，文献[13]提 出用卷积匹配追踪算法训练深层卷积网络。2014 年，文献[14]提出用交替方向乘法器的方法(ADMM)进行卷积分解，通过滤波器与对应特征 响应做卷积，减少相邻位置图像块的编码冗余度。尽管这些算法用来解决卷积稀疏表示问题，但很少
证卷 表 在 构方面优于
的基于块的稀疏表示。
针对传统的稀疏表亦算法一'般只是对图像块 进行单独编码，而忽略图像的整体性，本文构建了 一个基于卷积稀疏表示的重构算法，以此验证应用 一致性约束对整幅图像进行分解优于传统的稀疏 编码。用交替方向乘法器方法（AlternatingDirec-tionMethod ofMultipliers，ADMM)对输入图像
进行卷积稀疏分解。带卷积的ADMM算法根据 卷积独有的性质，只需要一个卷积核，就可表示图 像任意位置的相同特征，即能够用较少的原子个数 有效刻画图像的几何特征。通过实验验证与传统 的稀疏表示模型相比，卷积分解机制更适合于图像 构。
2卷积稀疏表示
基于传统的稀疏表示一幅图像s，由字典矩阵 与编码系数的线性结合对图像进行分解。其数学 表达式为
arg min1 ||Dx—s ||2十A ||x ||1(1)
+ 乙
式中D表示字典矩阵，+表示稀疏系数#表示原图像，A表示正则化参数，用来调整正则化程度。这种传统的基于块的稀疏编码方式在图像处理方 面应用广泛。
但是，在传统意义上的稀疏表示模型中，还存 在一些缺陷。如、。范数的可拓展性贫乏，在处理大 规模问题上限制了稀疏编码的应用。为了减少建 模 计算 #一 对 块 独 。其次，只针对一维信号进行单独编码，忽略了数据信 息二维空间结构和图像块之间的一致性，导致编码 高度冗余。这种稀疏表示方法忽视了图像块之间 的一致性，现有的聚合和平均策略只能缓解由此带 来的问题。
考虑到图像块之间的一致性，201。年，文献 [11]提出利用带卷积的稀疏编码实现稀疏表示整 个图像，即利用滤波器与相应特征响应的卷积总 和，代替传统的字典矩阵与编码系数的乘积对信号 进行分解。利用正则化公式表示该模型：
(2)其中/m}是一组滤波器构成的M维卷积字典，每 个滤波器的大小为《X w，K表示卷积符号，{}是 一组特征响应，每个特征响应的大小与s相同，s
表
2017年第4期计算机与数字工程733
示输入图像，为了表示上的方便$和工维向 量，iV
调度中心是图像中像素的个数。在这个带卷积的稀疏 表示模型中，充分考虑了图像块之间的相关性。本 文将基于这个模型，构建一个图像重构算法，并与 传统的基于块的稀疏表示重构图像进行比较。
3带卷积的ADMM 算法
带卷积的稀疏表示模型，对应的正则化问题可
以表示为式(2)。式(2
)利用一种图像先验，即对整
幅图像变换稀疏性。引入辅助变量{%}(其中 {：ym
}也是一个维向量)式(2
)变换成$
argmin1 I % K — s \2
+A %
\\ x m
{/}乙丨丨/
m
s . t .
+m — ./%〇, F m
(3)
再利用对偶变量，引入拉格朗日乘子M ，则约 束优化问题式(3)变为非约束等价形式$
m ^n -# || %C ?m ®X…—^|2 +-# %
m m
!
)在求解式（）中也就是更新特征响应系数，接下来 本文具体介绍求解子问题2)。表示如下：
arg min -$ || % d m
K +m 1
1| 2 $2 % l \ \'■X m } m
(10)
其中[m
= .!) —M ()。
vod点播
下面详细介绍子问题2)的求解：
在子问题2)中，出现了卷积的求解，又卷积定 理表明了两个傅里叶变换之间的关系构成了空 间域和频率域之间的基本关系，即一个域中卷积对 应于另一个域中的乘积，也就是说可以将卷积运算 转变成乘积运算。从而在求解子问题2)时，首先 应用D FT (离散傅里叶变换）卷积定理，将离散的
卷积运算转换成乘积运算。
定义线性算子D m
，如A X
m = d m K +m ，在DFT
域中用£*m 、X m 、S 以及[m 分另U 表亦D m 、X m 、S 以及 [m 。通过D F T 域中的卷积定理式(10)等同于
arpmin 1 || %D m +m — ■?! 2 $2 % I I X m —[m I I 2
{X m } m
式中：是一个正则化参数。本文用交替方向乘法器(ADMM )求解式（4) 描述的优化问题，交替方向乘法器是一种对偶凸优
化算法，其可以将可分结构的凸规划问题分解为若
干子问题交替地求解[15]。依据交替方向乘法器的
运算规则将本文中求解式（4)分为三个子问题，步 骤如下：1) 固定特征响应系数Xm }，乘子M 更新
辅助
变量{.m }。
{.m }(:+1) % arg min 又 ％ |\ y rn \ 1
$2 % I X(+1)—ym $M () I 2 (5)
式(5)为典型的^范数优化问题，处理该问题
较常用的方法是阈值法，采用阈值法可得：
y m +1 = s h rink (x /、$u /\%'") (6)式中O <n :(.，.），表亦软阈值函数，定义为
s h r in k ig ,u ) =s ig n (g )max {0, | & | —u } (7)
2) 固定辅助变量{.m }，乘子U 更新特征响应系数Xm }。
燃烧与灭火{Xm }(k +1、=argmin-1 I % dm K x / — s II2Xm 乙 '' m
$2 % I I Xm —$U () |\ (8 )
3) 按照ADMM 算法规则更新乘子u 。U k m +1 =U k ) $X k $v , —.^k $1、 !)在求解这些子问题的时候，最大的计算代价是
(11利用式！〇)中被给定的最小化{ X m }，通过式
(11)中的最小化{Xm }在D FT 中的逆变换。定义：r 入 、X 0[0 I D =(D0 D i •••);X =X 1i 2C =[1 ：.从而式(11)的问题可以表示为
argmin 1 I D x — s I 2$： I I x —z I 2 (13)
式(13)为二次优化问题，对X 求偏导数，并令
偏导数为0，可解得：
(.D T D $pI )x = D T s $p z (14)其中矩阵D 是由M 串级V X V 对角矩阵组成，M 为滤波器的维数，V 是图像s 的维数。D t D 是一
个MV XM V 维矩阵，且D t D 是对称矩阵，即式
(14)左边为Hessian 矩阵，因此可在频域用FFT
(快速傅里叶变换)求解。令A =:Z ，对式(14)两边同时进行FFT 可得： !(D )t 〇F T )+!(A )F i x "(15"\F {D )\2$p
基于上述讨论，本文引入一个图像重构算法，
称为CSR _ADMM 算法，具体步骤如下：
输入：样本T 滤波器字典{dm }，参数％:。
幼学纪事预计算：进行 FFT { dm } ;{Dm }，T —J 。
初始化:{.m } = {Um }=0。
步骤1通过引进辅助参数的拉格朗日函数，
构建问题(2)的限制最优化问题&
734陈小陶等：一个基于卷积稀疏表示的图像重构算法第45卷
2：计算进行FFT{〜};{〜}，{〜}; {'l^m}&
3：通过式(15)计算
4：进行 FFT的{im};{Xm}&步骤5：通过式(6)更新bm}&
6：通过式(9)更新Um}&
7：重复 2〜6%
4实验分析
在卷积稀疏表示模型下，应用上述的CSR-ADMM算法，计算出 的特征响应系数，并利用
的特征响应系数重构 ，与基于 的稀疏
表示算法ADMM的系数重构 的峰信 ％
在实验中，卷积分解机制使用一组12X12X 36的滤 字典[17]，其中A[0. 012，迭代次数为500次。机制使用一个64X256的DCT字典，A[0. 01，迭代次数同为500次，输入图 像采用标准图像—n a，h o u se，p e pp ers，b ir d，c it y，f r u its(大小均为512X512)，作为 。
⑷―butterfly (e)—city (f)—fruits
图1原始图像
(d)—butterfly (e)—city) (f)—fruits
图2基于卷积稀疏表示重构图像
其中图1表示上述六幅标准图像的原始图像，
2表 于卷 机制的重构 ，图3表示于块的 机制的重构 。表1给
出了针对不同的 ，基于带卷积的与 的于块的 机制下优化算法重构 的峰值信噪比（Peak Signal-to-Noise Ratio，PSNR)。
(d)—butterfly (e)—city (f)—fruits
图3基于传统稀疏表示重构图像
表1基于不同分解机制下的
重构图像峰值信噪比(PSNR) [dB]
图像CSR SR图像CSR SR
lena32.4030.89city41.7529.19 barbara32.3628.69fruits37.2130.25 bird39.0530.44均值36.9729.48 butterfly39.0827.41
从表1中它们的 看出，带卷积的ADMM重构 峰值信 不带卷 于块的提
高了 7.49dB。由此，说明在带卷积的 表示模型下，稀疏表示性能更优，卷 机制更适合图像重建。
为了进一步说明卷 机制更适合于图像重构，表2给出了在标准 lena(512X512)下，当，=0.01固定时，针对不同的迭代次数与不同的^的 取值CSR_ADMM重构图像峰值信噪比的对比。
表2基于不同的迭代次数与^〇的
取值CSR_ADMM重构图像PSNR[dB]
Intr X
10-210-110°101102103 10027.4728.1727.4227.6727.4127.58 20031.3131.3731.2731.3231.2231.27 30032.1832.1532.1732.1932.1532.17 40032.3932.3632.3932.4032.3832.38 50032.3832.4032.4032.4232.3932.40
从表2可以看出，当p的取值固定时，随着迭 代次数的增加，图像的峰值信 也在增加，当迭代次数固定时P的值从变化10Z2到103图像的峰
!下转第744
页）
744罗晶等：存储器测试图形算法概述第45卷
GUANFenglin，XIYoubao.Improved Test Algrithms of Embedded Memory[J].Microcontroller and Embedded Systems Applications#011,1(12) ：l-3. [10]周上.一种新的嵌人式系统存储器测试算法及应用
(].桂林电子科技大学学报，2013,33(3): 228-230,
(上接第734页）
值信噪比基本没有改变。从表2也可以看出当迭 代次数为200时，基于卷积的稀疏分解机制得到的 图像峰值信噪比，比传统的稀疏分解机制在迭代 500次时高。这也充分说明，基于卷积的稀疏分解机 制得到的特征响应系数优于传统的稀疏分解机制。
5结语
本文基于卷积稀疏表示模型，利用ADMM将 其分解为几个简单的非约束优化子问题，从而得到 特征响应系数。卷积稀疏表示直接把整个图像进 行滤波，充分考虑了重叠图像块像素之间的一致 性，较
之前传统的基于块的稀疏表示，卷积分解机 制可以保持特征响应中输入信号的空间信息，进而 达到较优的稀疏逼近，更有利于对图像进行重构。下一步可将本文的CSR_ADMM优化算法应用于 图像去噪，图像超分辨率等问题。
参考文献
[1] Elad M，Figueiredo M A T，Ma Y.On the role of sparse and redundant representations in image process-ing[J].Proceedings of the IEEE,2010, 98 (6)：972982.
(]ChengH，Liu Z，Yang L，et al.Sparse representation and learning in visual recognition：Theory and applications[J].Signal Processing,2013,93(6) ：1408-1425.
[3] Donoho D L.Compressed sensing[J].Information Theory，IEEE Transactions on, 2006, 52 (4)： 1289
1306.
[4] Baraniuk R G.Compressive sensing[J].IEEE signal processing magazine,2007,24(4) ：118-121.
[5] Figueiredo M AT，Nowak R D，Wright S J.Gradient projection for sparse reconstruction：Applic
ation to compressed sensing and other inverse problems[J].Selected Topics in Signal Processing，2007，1 (4): 586597.
[6]Kim S J，Koh K，Lustig M，et al.An interior-point method for larg--scale-regularized least squares[J].
235.
让朋友圈清清爽爽ZHOU Shangqun,Journal of Guilin University of E
lectronic Technology[J].A New Memory Testing A--
grithm of Embedded System and Its Application，2013,33(3)=228-230,235.
IEEE journal of selected topics in signal processing，2007,1(4) $06-617.
[7] Yang J，ZhangY.Alternating direction algorithms for li-problems in compressive sensing[J].SIAM journal on scientific computing，2011，33(1) :250-278. [8]Mallat S G，Zhang Z.Matching pursuits with time-frequency dictionaries [J].Signal Processing，IEEE Transactions on,1993,41(12) :3397-3415.荣事达洗衣机电路图
[9] EnganK，Aase S0，HakonHusoy J.Method of optimal directions for frame design [C]//Acoustics，Speech，and Signal Processing,1999 $443-2446. [10] Zhang Z，Xu Y，Yang J，et al.A survey of sparse
representation：algorithms and applications[J].Ac
cess，IEEE,2015,3：490-530.
[11] Kervrann C.PEW A：Patch-based Exponentially
Weighted Aggregation for image denoising[C]//Ad
vances in Neural Information Processing Systems，2014：2150-2158.
[12] Zeiler M D,Krishnan D，Taylor G W，et al.Decon
volutional networks[C]//Computer Vision and Pa-
tern Recognition(CVPR),2010：2528-2535.
[13] Szlam A，Kavukcuoglu K，LeCun Y.Convolutional
matching pursuit and dictionary training [J/OL].
[2010-10-3]. http：///abs/1010. 0422.
[14] Wohlberg B.Efficient convolutional sparse coding
[C]//International Conference on Acoustics，Speech
and Signa l Processing(ICASSP),2014:7173-7177.
[15] GabayD，Mercier B.A dual algorithm for the solu
tion of nonlinear variational problems via finite ele
ment approximation[J].Computers /Mathematics
with Applications?1976,2(1) ：17-40.
[6]杨帆.数字图像处理与分析[M].北京：北京航空航天
大学出版社,2010:39-44.
YANG Fan.Digital Image Processing and Analysis
[M].Beijing：Beijing University of Aeronautics and
Astronautics Press,2010：39-44.
[17] Wohlberg B.Convolutional sparse representation of
color images[C]//SouthweIt Symposium on Image A
nalysis and Interpretation(SSIAI),2016:57-60.
