2023年7月29日发(作者：)

总第330期2017年第4期计算机与数字工程Computer /

Digital

EngineeringVol. 45

No. 4731一个基于卷积稀疏表示的图像重构算法$!摘要.贵州大学数学系贵阳陈小陶许道云550025)!.贵州大学计算机科学系贵阳550025)12在利用稀疏表示技术重构图像的应用中，传统的方法是独立地计算一组重叠的图像块，在表示中只针对每个

图像块进行单独稀疏编码。利用卷积稀疏表示，可以将整个图像看做是一个整体，对其进行稀疏编码，由滤波器字典与相应

特征响应的卷积总和代替传统的字典矩阵与编码系数的乘积对图像进行分解。论文基于卷积稀疏表示方法，提出一个图像

重构算法，利用交替方向乘法器方法实验结果说明卷积分解机制稀疏性能较优,更适合于图像重构。(ADMM)对输人图像进行稀疏逼近，得到特征响应系数，达到对图像卷积分解的目的。

关键词稀疏表示；卷积稀疏表示&

中图分类号

TP391

ADMM;图像重构DO#

10. 3969/j.

issn 1672-9722. 2017. 04. 029Image Reconstruction Algorithm

Based on Convolution Sparse Representationy(1.

Department

of

Mathematics?

Guizhou

University,

Guiyang 550025)(2.

Department

of

Computer

Science ,

Guizhou

University ,

Guiyang 550025)CHEN

Xiaotao1

XU

Daoun2of

overlapping

image

blocks

independently.

Using

convolution

sparse

representation,

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

is

proposed，the

input

image

is

apalternating

direction

multiplier

method (ADMM)，and

the

characteristic

response

coefficient

is

obtained.

The

experimentalresults

show

that

the

sparse

performance

of

the

convolution

decomposition

mechanism

is

bettimage

reconstructionKey Words

sparse

representation，convolution

sparse

representation，ADMM，image

reconstructionClass Number

TP3911引言稀疏表示（构。信号可以稀疏表示是压缩感知的先验条件，由

字典矩阵依据稀疏度量标准求解变换后得到的稀

疏向量再通过逆变换从而实现信号的精确重构或

近似重构。由字典矩阵依据稀疏度量标准求解变

换后得到的稀疏向量求解变换的过程在稀疏表示

中叫做稀疏分解。依据压缩感知中的重构原理，

可以先通过稀疏分解得到稀疏系数，再通过逆变换Abstract

In

the

application

of

sparse

representation

in

image

reconstruction ,

the

traditional

method

is

to

compute

a

setSparseRepresentation) [1~2]是通过

4用尽可能少的原子系数线性表示原始信号，它与压

缩感知 ) (~]有着直接的联

（CompressedSensing系。压缩感知提出如果一个信号是稀疏的或者压

缩的，原始信号可以通过这些少量的测量值进行重"收稿日期：2016年10月5日，修回日期：2016年11月26日

基金项目：国家自然科学基金(编号$1262006)资助。作者简介:陈小陶，女，硕士研究生，研究方向：密码学理论与工程。许道云，男，博士，教授，博士生导师，研究方向:

问题、可计算性与计算复杂性、算法设计与分析等。SAT732陈小陶等:一个基于卷积稀疏表示的图像重枸算法第45卷重构图像。稀疏分解问题是指，在字典张成的整个信号空

间下，依据稀疏度量标准寻找信号的最优解，即稀

疏优化。典型稀疏度量标准包括/。范数、^范数、

范数以及(〇<^<)范数。目前，国内外学者基

于传统的稀疏表示模型提出了很多有效的稀疏分

解算法，大体可以分为两大类:松弛优化算法和贪

婪追踪算法。基于松弛优化思想提出了梯度投影

稀疏重建算法()5、内点法()()、交替方

证卷 表 在 构方面优于的基于块的稀疏表示。针对传统的稀疏表亦算法一'般只是对图像块

进行单独编码，而忽略图像的整体性，本文构建了

一个基于卷积稀疏表示的重构算法，以此验证应用

一致性约束对整幅图像进行分解优于传统的稀疏

编码。用交替方向乘法器方法（-

kiGPSRIPMAlternatingDirectionMethod

ofMultipliers，ADMM)对输入图像

进行卷积稀疏分解。带卷积的ADMM算法根据

向法(ADM)™等算法。这类算法简单易于实现，

然而处理大尺度信号时，MallatZhang时间复杂度高。1993年，

和在文献[8]中首次提出匹配追踪算

法(厦31(*62>+^1，厦>)，其主要思想是在、。范

数稀疏约束下，通过迭代，每次从冗余字典中寻找

MP与残差信号最匹配的原子，逐步稀疏逼近信号。

算法利用内积运算度量原子与信号之间的匹

配程度，计算复杂度低。针对MP算法，研究者们

进行了深入的探讨并提出了许多改进算法，主要有

正OMP交匹Stage-wiseOMP配追踪（Orthogonal

Matching

Pursuit，

)、 (StOMP)、基追踪等算

法[1。]。虽然基于传统的稀疏表示方法可以大大减小

问题的计算，也获得了很好的效果，但是以往的研

究通常是独立地处理重叠块，最后通过平均每一块

之间的重叠像素来获得结果。因为这种处理方法

使得每个像素的输出图像将被估计更多次，所以相

邻的块之间的重叠像素将提供更好的重构结果。

然而，在解决块估计问题时，这种“重叠平均”机制

忽略了一个重要的约束，重叠区域中的像素相邻的

块应该是完全一样的，即一致性。一致性约束提供

了在处理每一个单一的估计问题的先验信息。最

近，文献[11]提出了一种聚合方法，以减轻重叠块

之间的不一致，并在图像恢复方面取得了较好的效

果。然而，对于图像重构方面，仍需要更好的方法

证明一致性约束的重要性。因为图像块之间的一致性，2。1。年，Zeiler在

文献[12]最早提出卷积稀疏表示，利用带卷积的稀

疏编码实现稀疏表示整个图像，即利用滤波器与相

应特征响应的卷积总和，代替传统的字典矩阵与编

码系数的乘积对信号进行分解。同年，文献[13]提

出用卷积匹配追踪算法训练深层卷积网络。2014

年，文献[14]提出用交替方向乘法器的方法

(ADMM)进行卷积分解，通过滤波器与对应特征

响应做卷积，减少相邻位置图像块的编码冗余度。

尽管这些算法用来解决卷积稀疏表示问题，但很少卷积独有的性质，只需要一个卷积核，就可表示图

像任意位置的相同特征，即能够用较少的原子个数

有效刻画图像的几何特征。通过实验验证与传统

的稀疏表示模型相比，卷积分解机制更适合于图像

构。2卷积稀疏表示基于传统的稀疏表示一幅图像s，由字典矩阵

与编码系数的线性结合对图像进行分解。其数学

表达式为arg

+

min

1乙 ||

Dx—s ||

2 十A ||

x ||

1 (1)式中D表示字典矩阵，+表示稀疏系数#表示原

图像，A表示正则化参数，用来调整正则化程度。

这种传统的基于块的稀疏编码方式在图像处理方

面应用广泛。但是，在传统意义上的稀疏表示模型中，还存

在一些缺陷。如、。范数的可拓展性贫乏，在处理大

规模问题上限制了稀疏编码的应用。为了减少建

模 计算 #一 对 块 独 。 其次，只针对一维信号进行单独编码，忽略了数据信

息二维空间结构和图像块之间的一致性，导致编码

高度冗余。这种稀疏表示方法忽视了图像块之间

的一致性，现有的聚合和平均策略只能缓解由此带

来的问题。考虑到图像块之间的一致性，201。年，文献

[11]提出利用带卷积的稀疏编码实现稀疏表示整

个图像，即利用滤波器与相应特征响应的卷积总

和，代替传统的字典矩阵与编码系数的乘积对信号

进行分解。利用正则化公式表示该模型：(2)其中/m}是一组滤波器构成的每

个滤波器的大小为《

X

w，KM维卷积字典，表示卷积符号，{}是

一组特征响应，每个特征响应的大小与s相同，s表2017年第4期计算机与数字工程733示输入图像，为了表示上的方便$和工维向

量，是图像中像素的个数。在这个带卷积的稀疏

表示模型中，充分考虑了图像块之间的相关性。本

文将基于这个模型，构建一个图像重构算法，并与

传统的基于块的稀疏表示重构图像进行比较。在求解式（）中也就是更新特征响应系数，接下来

本文具体介绍求解子问题2)。表示如下：arg

min-$ || %

d

'■Xm}

miVmK+m

11| 2 $2 %

l (10)3带卷积的ADMM算法其中[ = .!) —M()。下面详细介绍子问题2)的求解：在子问题2)中，出现了卷积的求解，又卷积定

理表明了两个傅里叶变换之间的关系构成了空

间域和频率域之间的基本关系，即一个域中卷积对

m带卷积的稀疏表示模型，对应的正则化问题可

以表示为式()。式()利用一种图像先验，即对整

22幅图像变换稀疏性。引入辅助变量{%}(其中

{：ym}也是一个维向量)式(2)变换成$argmin1{/}乙

丨I

丨%

K—

s2

+A %s/

m

xm.

t.

+m —

./%〇,

F

m (3)再利用对偶变量，引入拉格朗日乘子M，则约

束优化问题式(3)变为非约束等价形式$m^n-# || %mC?m ®X„—^|2m +-# %!)式中：是一个正则化参数。本文用交替方向乘法器(ADMM)求解式（4)

描述的优化问题，交替方向乘法器是一种对偶凸优

化算法，其可以将可分结构的凸规划问题分解为若

干子问题交替地求解[15]。依据交替方向乘法器的

运算规则将本文中求解式（4)分为三个子问题，步

骤如下：1) 固定特征响应系数Xm}，乘子M更新辅助

变量{.m}。{.m}(:+1) %

arg

min 又 ％ |

yrn

1$2 %

I

X(+1)—ym$M()

I 2 (5)式(5)为典型的^范数优化问题，处理该问题

较常用的方法是阈值法，采用阈值法可得：ym+1 =

shrink

(x/、$u/%'") (6)式中O

=sign(g)max{0, | & |

—u} (7)) 固定辅助变量{.m}，乘子U更新特征响应系数Xm}。{Xm}(k+1、=argmin-1Xm 乙

I''

%m

dm

Kx/ —

s

II2$2 %

II

Xm—$U() |

(8 )3) 按照ADMM算法规则更新乘子u。Ukm+1

=Uk)

$Xk$v, —.^k$1、 !)在求解这些子问题的时候，最大的计算代价是应于另一个域中的乘积，也就是说可以将卷积运算

转变成乘积运算。从而在求解子问题2)时，首先

应用DFT(离散傅里叶变换）卷积定理，将离散的

卷积运算转换成乘积运算。定义线性算子Dm，如AXm=

dm

K+m，在DFT

域m中用£*m、Xm、S以及[m分另U表亦Dm、Xm、S以及

[。通过DFT域中的卷积定理式(10)等同于arpmin{Xm}

1 || %mDm+m — ■?! 2 $2 %

II

Xm —[m

II 2(11利用式！〇)中被给定DFT的最小化{

Xm }，通过式

(11)中的最小化{Xm}在中的逆变换。定rDX义：入

0、[0

I=(D0

Di

•••);X =iX1C =[1

2：.从而式(11)的问题可以表示为

argmin

1

I

Dx

—

s

I

2$：

II

x—z

I 2 (13)

式(13)为二次优化问题，对X求偏导数，并令偏导数为0,可解得：(.DTD$pI)x =

DTs$pz (14)其中矩阵D是由M串级VXV对角矩阵组成，M

为滤波器的维数，MVV是图像s的维数。DtD是一

个

XMV维矩阵，且DtD是对称矩阵，即式(14)左边为Hessian矩阵，因此可在频域用FFT

(快速傅里叶变换)求解。令A=:Z，对式(14)两边同时进行FFT可得：

Fix"!(D)t〇FT)+!(A)F{D)2$p

(15"基于上述讨论，本文引入一个图像重构算法，

称为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:通过式(66)更新bm}&:通过式(9)更新26Um} &7:重复 〜%4实验分析ADMM在卷积稀疏表示模型下，应用上述的CSR-

算法，计算出 的特征响应系数，并利用的特征响应系数重构

ADMM，与基于 的稀疏表示算法 的 系数重构 的峰信 ％在实验中，卷积分解机制使用一组121236的滤 字典[17]，其中AXX

[0. 012,迭代次DCT数为500次。 机制使用一个64X256的字典，A[0. 01，迭代次数同为500次，输入图

像fu采用标准图像—na，house，peppers，bird，city，

rits(大小均为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]图像CSRSR图像CSRSRlena32.4030. 89city41. 7529.19barbara32. 3628. 69fruits37.2130.25bird39.0530.44均值36.9729.48butterfly39.0827.41ADMM从表1中它们的 看出，带卷积的重构 峰值信 不带卷 于块的提高了 7. 49dB。由此，说明在带卷积的 表示模型下，稀疏表示性能更优，卷 机制更适合图像重建。为了进一步说明卷

构，表2给出了在标准

lena机制更适合于图像重(512X512)下，当，=0.

01固定时，针对不同的迭代次数与不同的^的

取值CSR_ADMM重构图像峰值信噪比的对比。表2基于不同的迭代次数与^〇的取值CSR_ADMM重构图像PSNR[dB]Intr

X10-210-110°17.4728.1727.4227.6727.4127.5820031.3131.3731.2731.3231.2231.2730032.1832.1532.1732.1932.1532.1740032.3932.3632.3932.4032.3832.3850032.3832.4032.4032.4232.3932.40从表2可以看出，当p的取值固定时，随着迭

代次数的增加，图像的峰值信 也在增加，当迭代次数固定时P的值从变化10Z2到103图像的峰!下转第744页）744罗晶等:存储器测试图形算法概述第45卷[]周上群.一种新的嵌人式系统存储器测试算法及应用

(].桂林电子科技大学学报，2013,33(3): 228-230,10GUANFenglin，XIYoubao.

Improved

Test

Algrithms

of

Embedded

Memory[J].

Microcontroller

and

Embed­ded

Systems

Applications#011,1(12) ：

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.235.(上接第734页）值信噪比基本没有改变。从表代次数为200时，基于卷积的稀疏分解机制得到的

2也可以看出当迭

IEEE

journal

of

selected

topics

in

signal

processing，2007,1(4) $06-617.图像峰值信噪比，比传统的稀疏分解机制在迭代

500次时高。这也充分说明，基于卷积的稀疏分解机

制得到的特征响应系数优于传统的稀疏分解机制。5结语本文基于卷积稀疏表示模型，利用ADMM将

其分解为几个简单的非约束优化子问题，从而得到

特征响应系数。卷积稀疏表示直接把整个图像进

行滤波，充分考虑了重叠图像块像素之间的一致

性，较之前传统的基于块的稀疏表示，卷积分解机

制可以保持特征响应中输入信号的空间信息，进而

达到较优的稀疏逼近，CSR更有利于对图像进行重构。

下一步可将本文的_ADMM优化算法应用于

图像去噪，图像超分辨率等问题。参考文献[1]

Eladsparse

M，

Figueiredo

MAT，

Ma

Y.

On

the

role

of

ingJ

and

redundant

representations

in

image

process-

[].

Proceedings

of

the

IEEE, 2010, 98 (6) ： 972­(]ChengH，

Z，Yang

L，et

al.

Sparse

representation

tions

learning

in

visualProcessing

recognition：

Theory

and

applica­ [J].

Signal ,2013,93(6) ： 1408-1425.[3]

Theory，Donoho

DIEEE

L.

CompressedTransactions

sensing [J].

Information

on, 2006, 52 (4)： 1289­Baraniuk1306.[4]

processing

R

G.

Compressive

sensing[J].

IEEE

signal

magazine,2007,24(4) ： 118-121.[5]

Figueiredoprojection

MAT，Nowak

R

D，Wright

S

J.

Gradient

compressed

for

sparse

reconstruction：

Application

to

lected

sensingin

and

other

inverse

problems[J].

Se­

Topics

Signal

Processing，2007，1 (4): 586­6Kim597.[]

method

S

J，

forKoh

K，

Lustig

M，

et

al.

An

interior-point

larg--scale-regularized

least

squares [J].[7]

Yangli-problems

J，ZhangYincompressive.

Alternatingsensing

directionJ

algorithmsSIAMjournal

for

[].

8Mallaton

scientific ，2011，33(1) :250-278.[]

quency

S

dictionariesG，Zhangcomputing

Z.

JMatchingSignal

pursuitsProcessing

with

time-fre­ [ ]. ，

EnganK，Transactions

onIEEE

,1993,41(12) :3397-3415.[9]

mal 0 .

Speech，

directionsAaseS

for，HakonHusoy

frame

designJ [

CMethod ]//Acousticsofopti­ , 1999 $443-2446.[10]

representationZhang

Zand，

XuSignal

Y，YangProcessing，

J，

et

al.

A

survey

cess：

algorithms

and

applicationsof [Jsparse].

Ac­ ，,2015,3：490-530.[11]

WeightedKervrannIEEE

C.

PEW

A：

Patch-based

vancesin

AggregationNeuralInformation

for

imageProcessing

denoisingExponentially

[SystemsC]//Ad­ ，Zeiler2014：2150-2158.[12]

volutional

M

D , . ­tern

networksKrishnan [C]//ComputerD，TaylorGW，

Visionetal

andDecon -­Szlam

Recognition() ,2010：2528-2535.[13]

matching

A，

pursuitKavukcuogluCVPRPaand

dictionaryK，

LeCun

trainingY.

Convolutional

[/].

[2010-10-Wohlberg3]. ：//. //1010. 0422.[14]

C]//International

Bhttp.

EfficientarXivorgabsJOLConference

convolutionalonAcoustics

sparse

coding

[ ，

GabayD，and

Signal () ,2014:7173-7177.[15]

tion . ­ment

ofMercierProcessingSpeech

BICASSPAdualalgorithmforthesoluapproximation

nonlinear

variational

problems

via

finite

ele­ []. /

6with

ApplicationsJComputersMathematics

? 1 976,2(1)

M：17-40.[]杨帆.数字图像处理与分析[].北京:北京航空航天

YANG大学出版社,2010:39-44. .

Astronautics[M].

BeijingFanDigital：

BeijingImage

UniversityProcessing

of

AeronauticsandAnalysis

and

Wohlberg

Press,2010：39-44.[17]

color .

nalysis

imagesBandInterpretation[C]//SouthweItConvolutionalsparserepresentationof

SSIAI

Symposium

on

Image

A­ () ,2016:57-60.