Image Denoising via Sparse approximation using
Eigenvectors of Graph Laplacian
Yibin Tang
#
, Ying Chen
*
, Ning Xu
#
, Aimin Jiang
#
, Yuan Gao
#
#
College of IOT Engineering, Hohai University
Changzhou, China
*
School of Information Science and Engineering, Southeast University
Nanjing, China
Abstract—In this paper, a sparse approximation algorithm
using eigenvectors of the graph Laplacian is proposed for image
denoising, in which the eigenvectors of the graph Laplacian of
images are incorporated in the sparse model as basis functions.
Here, an eigenvector-based sparse approximation problem is
presented under a set of residual error constraints. The
corresponding relaxed iterative solution is also provided to
efficiently solve such problem in the framework of the double
sparsity model. Experiments show that the proposed algorithm
can achieve a better performance than some state-of-art
denoising methods, especially measured with the SSIM index.
Index Terms—Double sparsity, eigenvector, graph
Laplacian, image denoising, sparse approximation
I. INTRODUCTION
Image denoising plays an important role in image
processing. It is viewed as an inverse problem in which clean
images are estimated from the noisy images. A number of
methods have been well presented to deal with this practical
problem in the past decades [1]. However, with the advances
of sparse signal representation, more methods are developed
to resolve this image denoising problem based on the sparse
consumption, and achieve the better denoising performances
compared with the traditional methods. Sparse approximation,
as an important issue in sparse representation, is devoted to
represent the signal as a linear combination of a small number
of atoms from an over-complete dictionary. Early methods via
sparse approximation [2] usually treat the denoising problem
as a pure mathematical problem, in which each patch is
separately taken into account with the neglect of the
relationship among patches. Later, numerous improved
denoising methods are developed to exploit such relationship,
and often model the connection among sparse coefficients.
For example, a nonlocally centralized sparse representation
method [3] is presented to centralize the sparse coefficients
into various categories, and achieves a comparable
performance with the block-matching and 3D filtering
(BM3D) method.
On the other hand, graph theory has been well employed in
a variety of image applications in the past decades. As for
image denoising via sparse approximation, recent reports also
show that the denoising performance can be improved
combined with the graph theory. For example, a graph
regularized sparse approximation method [4] is proposed to
perform a manifold embedding on sparse coefficients, in
which the graph Laplacian matrix is viewed as a useful tool to
exploit the geometrical structures for image patches.
According to this idea, a denoising method with eigenvectors
of the graph Laplacian (EGL) is currently developed [5]. In
this literature, the eigenvectors of the graph Laplacian of
patches do not only represent the global features of images,
but also are used as a set of basis functions to reconstruct
images.
Motivated by the recent process, a sparse approximation
algorithm using eigenvectors of the graph Laplacian (EGL-SA)
is proposed for image denoising. In detail, the eigenvectors of
the graph Laplacian of image patches are employed in the
sparse model to exploit the global structures of the noisy
image. The eigenvector-based sparse approximation problem
is also presented, where the corresponding relaxed iterative
solution is provided in the framework of the double sparsity
model.
II. R
ELATED WORK
Given a measurement data matrix
12
[...]
N
=Yyyy, the
basic sparse approximation problem can be described as two
forms which are subject to the sparsity and residual error
constraints respectively. The sparse approximation problem
under the residual error constraint is expressed as
0
2
2
sa.rg t.min , 1, 2,... ,,
i
iiii
iN
ε
−=≤=
x
xxyDx (1)
where
12
[ ... ]
K
=
dd d is the dictionary with the atoms { }
i
d ,
12
[ ... ]
N
=
xx x is the coefficient matrix with the sparse
coefficients { }
i
x ,
ε
is a threshold of the residual error. In
image denoising, each
i
represents a noisy image patch, and
N is the number of the total patches. Here, in (1), the number
of the entries in
i
is smaller than the number of the atoms,
and the dictionary is assumed to be a full-rank matrix. Thus,
the solution of (1) is always available, where the residual error
constraint only provides a searching area for
i
x [6]. Moreover,
since (1) is known as a NP-hard problem, a number of
effective algorithms, such as matching pursuit, basis pursuit
and iterative shrinkage methods, are developed to tackle
sparse approximation problems in different forms.
As for the EGL method, the basic idea is to estimate clean
patches from the noisy ones on a set of the eigenvectors of the
graph Laplacian. More specifically, the normalized Laplacian
matrix
L is firstly obtained as
1/2 1/2
,
−−
=−LIBWB (2)
978-1-4673-7314-2/15/$31.00 ©2015 IEEE IEEE VCIP 2015