Signal Processing - September 2017 - 173

years and discuss the future develop-
ments. This lecture note can be used
as a tutorial to IR methods for senior
undergraduate students, graduate stu-
dents, and researchers in the related
areas. The slides associated with this
lecture note are available at http://www
.comp.polyu.edu.hk/~cslzhang/IR_
lecture.pdf.

Prerequisites
Knowledge of statistical signal process-
ing, linear algebra, and convolutional
neural networks (CNNs) will be helpful
in understanding the content of this lec-
ture note.

Problem statement
Denote by x the latent image and y
the degraded observation of it. A typ-
ical image degradation model can be
written as
y = Hx + y,

(1)

where H denotes the degradation
matrix and y denotes the additive noise.
In the literature, y is often assumed
to be additive white Gaussian noise
(AWGN) with zero mean and standard
deviation v. Based on the forms of H,
different IR problems can be defined.
For example, in image denoising, H
is an identity matrix. In image deblur-
ring, we have Hx = k 7 x, where k is
the blur kernel and 7 denotes the two-
dimensional (2-D) convolution operator.
In image inpainting, H is a diagonal 0-1
matrix. In image superresolution, H is
the composition of blurring and downs-
ampling operators.
The linear system in (1) is generally
ill posed, i.e., we cannot obtain x by
directly solving the linear system. State-
of-the-art IR methods exploit image
prior information and optimize an
energy function to estimate the desired
image x. From the Bayesian perspec-
tive, (1) defines a likelihood function
P ( y x) = exp " - y - Hx 22 /2v 2 , of
x. Given the image prior P ( x), we can
estimate the unknown latent image x
from the observation y by maximizing
the posterior probability P ( x y), and
the widely used maximum a posterior
(MAP) model is

xt = arg max x " log P ( x y)
? ^log P ( y x) + log P ^ xhh,
= arg min x " 1/2 y - Hx

2
2

+ m R (x) ,,
(2)

where R (x) = - log P (x) denotes the
regularization term and m is the regular-
ization parameter. Under the MAP frame-
work, one key problem is how to model
the image priors P (x) [or regularizers
R (x) ]. Successful prior models include
sparse and low-rank priors. Recently,
deep learning techniques have also been
used to learn discriminative prior models.

Solutions
Sparse representation
Many IR methods exploit the sparsity
prior of natural images. For example,
image gradient exhibits long-tailed dis-
tribution, with which the total variation
methods have been widely used for solv-
ing IR problems. The wavelet transform
of an image has sparsely distributed coef-
ficients, and, therefore, soft-thresholding
in wavelet domain is a simple yet effective
denoising technique. An image patch can
be well represented as the linear combi-
nation of a few atoms sparsely selected
from a dictionary. The sparse represen-
tation (also known as sparse coding)-
based methods encode an image patch
over an overcomplete dictionary D with
, 1 -norm (or , p -norm, 0 # p # 1) spar-
sity regularization on the coding vector,
i.e., min a a 1 s.t. x = Da, leading to
a general sparse representation-based
IR model
at = arg min y - HDa + m a 1, (3)
a

which turns the estimation of x in (2)
into the estimation of a. Table 1 sum-
marizes the major steps in sparse repre-
sentation-based IR.

Figure 1 shows an example of
image denoising by sparse representa-
tion. One can see that the noise is rap-
idly removed during the iteration, and the
image is well reconstructed in five itera-
tions. The success of sparse representa-
tion in IR can be explained from different
perspectives. First, from the Bayesian
perspective, it solves a MAP problem
with a good sparsity prior. Second, it
has neuroscience explanations that the
receptive fields of simple cells in pri-
mary visual cortex can be characterized
as spatially localized, oriented, and
bandpass. Third, from the perspective
of compressed sensing, image patches
are K -sparse signals, which can be well
reconstructed using sparse optimization.

The selection of a dictionary

The dictionary D plays an important
role in sparse representation-based
IR. Early methods usually adopt some
analytical dictionaries, such as dis-
crete cosine transform bases, wavelets,
curvelets, or the concatenation of them.
Nonetheless, these analytically de-
signed dictionaries have limited capa-
bility in matching the complex natural
image structures. More atoms have to
be selected to represent the given im-
age, making the representation less
sparse. To address this issue, research-
ers proposed to learn dictionaries from
natural images. Given a set of train-
ing samples Y = 6 y 1, y 2, f, y n@, where
y i is a vectorized image patch, dic-
tionary learning aims to learn a dic-
tionary D = 6d 1, d 2, f, d m@ from Y,
where d j is an atom and m 1 n, such
that Y . DK and K = 6a 1, a 2, f, a n@
is the set of sparse codes. One classi-
cal dictionary learning method is the
K-SVD [1] algorithm, which imposes
, 0 -norm sparsity on each coding vector
a i, i = 1, 2, f, n.

Table 1. Major steps in sparse representation-based IR.
1)

Partition the degraded image into overlapped patches.

For each patch, solve the nonlinear , 1-norm sparse coding problem in (3).

Reconstruct each patch by xt = Dat .

Put the reconstructed patch back to the original image. For overlapped pixels between patches,
average them.

Iterate the above procedures for a better restoration.

IEEE SIGNAL PROCESSING MAGAZINE

September 2017

173

http://www http://comp.polyu.edu.hk/~cslzhang/IR_

Table of Contents for the Digital Edition of Signal Processing - September 2017