# An Improved Method of Training Overcomplete Dictionary Pair

Authors: Zhuozheng Wang; John R. Deller; Kebin Jia; Wenli Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Training overcomplete dictionary pair is a critical step of the mainstream superresolution methods. For the high time complexity and susceptible to corruption characteristics of training dictionary, an improved method based on lifting wavelet transform and robust principal component analysis is reported. The high-frequency components of example images are estimated through wavelet coefficients of 3-tier lifting wavelet transform decomposition. Sparse coefficients are similar in multiframe images. Accordingly, the inexact augmented Lagrange multiplier method is employed to achieve robust principal component analysis in the process of imposing global constraints. Experiments reveal that the new algorithm not only reduces the time complexity preserving the clarity but also improves the robustness for the corrupted example images.


---

## Body

## 1. Introduction

Superresolution (SR) reconstruction techniques produce high-resolution (HR) images from one or more low-resolution (LR) images, thereby increasing the high-frequency image detail and correcting degradation caused by LR sensors. SR technology is employed in numerous applications including medical imaging systems, face hallucination, remote sensing image processing, and military target reconnaissance and surveillance. There are three principal approaches achieving SR. Interpolation-based and reconstruction-based methods are traditional, examples of which include the Bicubic [1], IBP [2], POCS [3], and mixed ML/MAP/POCS methods [4]. In contrast, learning-based methods construct optimally weighted constraints inferred from training overcomplete dictionary pair. Learning-based methods are capable of extrapolating high-frequency image features that are not apparent in LR images. Instances of learning methods are found in the example-based method [5], in the support vector regression (SVR) approach [6], in neighbor embedding methods (NESR) [7], and in papers on sparse representation of superresolution (SRSR) methods [8, 9], which are the most effective SR algorithms.In the process of SR algorithms based on sparse representation, an overcomplete dictionary pair,D
H for high-resolution patches and D
L for low-resolution patches, will be trained to estimate the sparse coefficients. The accuracy of training dictionary will directly affect the performance of SR algorithms. However, the SR algorithms are often affected by corrupted acquired digital images including the lack of camera focus, faulty illumination, or missing data.Principal component analysis (PCA) has been widely applied to traditional denoising SR algorithms by solving the constrained optimization problem. This method works well in practice as long as the noise power is small. However, it breaks down when corruption is severe, even if only very few of the observations are affected. For example, there are two PCA simulation results shown in Figure1. For comparison, 100 sampled 2-dimensional arrays are represented by circle with some small noise in Figure 1(a) and with one error in Figure 1(b). On the bottom of Figure 1(a), circles can arrange by order of size. However, each circle has the same size in Figure 1(b). The results verify that PCA fails to estimate the correct order when data is corrupted by large errors. Furthermore, training dictionary has a high time complexity.PCA fails to reconstruct when data is corrupted by large errors.
(a)
Data with random noise
(b)
Data was brokenTo remedy these shortcomings, this paper presents an improved training dictionary algorithm based on lifting wavelet transform (LWT) and robust principal component analysis (RPCA). High-frequency wavelet coefficients are estimated by 3-tier LWT decomposition process, thereby reducing two-dimensional image data storage to about 75%. For low-frequency image components reflected in the LWT decomposition, scale coefficients are determined through robust principal component analysis (RPCA) instead of PCA. RPCA can preserve image detail and edge information and recovery of the broken data simultaneously. In the next section, this paper will explain the strategy of training dictionary in SR algorithm.


## 2. Training Dictionary Based on Sparse Representation

### 2.1. Sparse Representation Overview

Suppose that signalx
∈
R
n can be represented as a linear combination of elements in an overcomplete dictionary ∈
R
n
×
Q, where Q denotes the number of atoms in the dictionary. Then an observation of signal x, say y, can be expressed as follows:
(1)
y
=
S
x
=
S
D
α
0
,
in which α
0
∈
R
Q is a sparse vector and S
∈
R
m
×
n
(
m
<
n
) is the matrix used to downsample x. A similar model can be applied to digital images. Let X denote an original HR image and Y denote a degraded LR version of X.Now suppose thatX is partitioned into submatrices, calledpatches, of dimension n
×
n. Each patch in X is denoted by a lower case “x,” with a single integer index, say x
1
,
x
2
,
…. Similarly, Y is partitioned into m
×
m LR patches, y
1
,
y
2
,
…. For the purposes of this development, the relation between the index on patch x
i and its position in X is arbitrary and similarly for the index of y
i and its position in Y. However, there must be a one-to-one correspondence between patches x
i and y
i for a given i. The image degradation between X and Y is modeled by
(2)
y
i
=
S
H
x
i
+
n
i
,
in which H represents the blurring filter. The model is shown in Figure 2.Figure 2
Image degradation model.The process of image degradation (per patch) is viewed as a projection from a high- to a low-dimension spaceS
H
:
R
n
×
n
→
R
m
×
m. According to the theory of manifolds, the local characteristics of the image patches are essentially unchanged by projection [10]. Given sufficient sparsity of α
0, HR image patches can be perfectly recovered from the sparse representation of LR image patches with high probability. Similar to (1), the LR and HR image patches are represented as linear combinations of dictionary elements as follows:
(3)
x
i
≈
D
H
α
i
,
y
i
≈
D
L
α
i
,
α
i
0
≪
Q
,
where ·
0 indicates the l
0-norm. α
i denotes the sparse basis vector which is used to represent for patch i in both the HR and LR images. D
H
∈
R
n
2
×
Q and D
L
∈
R
m
2
×
Q are the overcomplete joint dictionary pair corresponding to the HR and LR patches, respectively.Since (3) is underdetermined, we use a Lagrange multiplier to solve the ill-posed problem [8] as follows:
(4)
α
i
*
=
min
⁡
α
i
D
~
α
i
-
y
~
i
2
2
+
λ
α
i
1
,
in which λ balances sparsity of the solution and fidelity of the approximation to y
~
i. Consider
(5)
D
~
=
F
D
L
P
D
H
,
y
~
i
=
F
y
~
i
ω
i
;F indicates the feature extraction operator which retains the high-frequency details in the image. P extracts the region of overlap between the current target patch and previously reconstructed HR image. ω
i contains the values of the previously reconstructed HR image on the overlap. Finally, HR image patches are reconstructed using the optimal α
i
* determined in the following equation:
(6)
x
i
=
D
H
α
i
*
.


### 2.2. Training Overcomplete Dictionary Pair

The joint dictionary pairD
H and D
L is trained using known example image patches. Given x
^
i
∈
R
n
×
n as HR image patches and y
^
i
∈
R
m
×
m as LR image patches, optimization problem becomes the following:
(7)
D
H
*
,
D
L
*
=
arg
min
⁡
{
D
H
,
D
L
}
1
n
x
^
i
-
D
H
α
^
i
2
2
+
1
m
y
^
i
-
D
L
α
^
i
2
2
+
λ
1
n
+
1
m
α
^
i
1
.The trained dictionary pairD
H
* and D
L
* is required to solve for the optimal sparse vector of (4).


### 2.3. LWT Strategies for Example Images

To reduce the time complexity of the SR algorithm, the LWT procedure is achieved before training the example images, which is calledx
^
i in (7). By adopting separate training strategies for high- and low-frequency components of example images, the LWT can differentially preserve the critical features that accompany these separate bandwidths.The example images are converted to low-frequency, horizontal-, vertical-, and diagonal- high-frequency domain coefficients by the LWT. For the three high-frequency components, wavelet coefficients on this layer can be accurately estimated by the next layer’s wavelet coefficients through strong correlation. Therefore, in the process of 3-tier LWT, the first layer’s high-frequency wavelet coefficients can be estimated by the second and the third layers’ high-frequency wavelet coefficients. The number of example image pixels involved in training dictionary is only 25% of the original ones, which leads to greatly reducing the iteration time and preserving the edge information simultaneously.For low-frequency components, RPCA discussed in the next section is employed to recover the corruption.


## 2.1. Sparse Representation Overview

Suppose that signalx
∈
R
n can be represented as a linear combination of elements in an overcomplete dictionary ∈
R
n
×
Q, where Q denotes the number of atoms in the dictionary. Then an observation of signal x, say y, can be expressed as follows:
(1)
y
=
S
x
=
S
D
α
0
,
in which α
0
∈
R
Q is a sparse vector and S
∈
R
m
×
n
(
m
<
n
) is the matrix used to downsample x. A similar model can be applied to digital images. Let X denote an original HR image and Y denote a degraded LR version of X.Now suppose thatX is partitioned into submatrices, calledpatches, of dimension n
×
n. Each patch in X is denoted by a lower case “x,” with a single integer index, say x
1
,
x
2
,
…. Similarly, Y is partitioned into m
×
m LR patches, y
1
,
y
2
,
…. For the purposes of this development, the relation between the index on patch x
i and its position in X is arbitrary and similarly for the index of y
i and its position in Y. However, there must be a one-to-one correspondence between patches x
i and y
i for a given i. The image degradation between X and Y is modeled by
(2)
y
i
=
S
H
x
i
+
n
i
,
in which H represents the blurring filter. The model is shown in Figure 2.Figure 2
Image degradation model.The process of image degradation (per patch) is viewed as a projection from a high- to a low-dimension spaceS
H
:
R
n
×
n
→
R
m
×
m. According to the theory of manifolds, the local characteristics of the image patches are essentially unchanged by projection [10]. Given sufficient sparsity of α
0, HR image patches can be perfectly recovered from the sparse representation of LR image patches with high probability. Similar to (1), the LR and HR image patches are represented as linear combinations of dictionary elements as follows:
(3)
x
i
≈
D
H
α
i
,
y
i
≈
D
L
α
i
,
α
i
0
≪
Q
,
where ·
0 indicates the l
0-norm. α
i denotes the sparse basis vector which is used to represent for patch i in both the HR and LR images. D
H
∈
R
n
2
×
Q and D
L
∈
R
m
2
×
Q are the overcomplete joint dictionary pair corresponding to the HR and LR patches, respectively.Since (3) is underdetermined, we use a Lagrange multiplier to solve the ill-posed problem [8] as follows:
(4)
α
i
*
=
min
⁡
α
i
D
~
α
i
-
y
~
i
2
2
+
λ
α
i
1
,
in which λ balances sparsity of the solution and fidelity of the approximation to y
~
i. Consider
(5)
D
~
=
F
D
L
P
D
H
,
y
~
i
=
F
y
~
i
ω
i
;F indicates the feature extraction operator which retains the high-frequency details in the image. P extracts the region of overlap between the current target patch and previously reconstructed HR image. ω
i contains the values of the previously reconstructed HR image on the overlap. Finally, HR image patches are reconstructed using the optimal α
i
* determined in the following equation:
(6)
x
i
=
D
H
α
i
*
.


## 2.2. Training Overcomplete Dictionary Pair

The joint dictionary pairD
H and D
L is trained using known example image patches. Given x
^
i
∈
R
n
×
n as HR image patches and y
^
i
∈
R
m
×
m as LR image patches, optimization problem becomes the following:
(7)
D
H
*
,
D
L
*
=
arg
min
⁡
{
D
H
,
D
L
}
1
n
x
^
i
-
D
H
α
^
i
2
2
+
1
m
y
^
i
-
D
L
α
^
i
2
2
+
λ
1
n
+
1
m
α
^
i
1
.The trained dictionary pairD
H
* and D
L
* is required to solve for the optimal sparse vector of (4).


## 2.3. LWT Strategies for Example Images

To reduce the time complexity of the SR algorithm, the LWT procedure is achieved before training the example images, which is calledx
^
i in (7). By adopting separate training strategies for high- and low-frequency components of example images, the LWT can differentially preserve the critical features that accompany these separate bandwidths.The example images are converted to low-frequency, horizontal-, vertical-, and diagonal- high-frequency domain coefficients by the LWT. For the three high-frequency components, wavelet coefficients on this layer can be accurately estimated by the next layer’s wavelet coefficients through strong correlation. Therefore, in the process of 3-tier LWT, the first layer’s high-frequency wavelet coefficients can be estimated by the second and the third layers’ high-frequency wavelet coefficients. The number of example image pixels involved in training dictionary is only 25% of the original ones, which leads to greatly reducing the iteration time and preserving the edge information simultaneously.For low-frequency components, RPCA discussed in the next section is employed to recover the corruption.


## 3. Matrix Completion and RPCA

### 3.1. Overview

The matrix completion problem has been the subject of intense research in recent years. In 2009, Candès and Recht [11] demonstrated exact matrix completion using convex optimization. As the rank of a matrix is not a convex function, the nuclear norm of the matrix can be used to approximate its rank, yielding a convex minimization problem for which there are numerous efficient solutions [11].In 2010, Lin et al. [12] published a fast scalable algorithm for solving the robust PCA problem. The method is based on recovering a low-rank matrix with an unknown fraction of its entries corrupted. The algorithm proceeds as follows: given a rank r matrix A
∈
∑
m
×
n, where r
≪
min
⁡
(
m
,
n
) is the target dimension of the subspace, the observation matrix is D. We can use
(8)
D
=
P
Ω
(
A
)
+
E
to model these sets of linear measurements, where P
Ω
(
·
) is a subsampling projection operator and E represents the matrix of perturbations including complex noise and large errors. It should be relatively sparse compared to A.


### 3.2. Matrix Completion

The objective of matrix completion is to recover the low-dimensional subspace the truly low-rank matrixA from D, under the assumption that E is zero
(9)
min
⁡
A
⁡
A
*
,
s
.
t
.
P
Ω
A
=
D
,
in which ·
* denotes the nuclear norm of a matrix. It has been shown that the solution to this convex relaxation can exactly recover the true low-rank matrix A under quite general conditions [11]. Furthermore, the recovery is stable to small and bounded noise [12], that is, when the entries of E are nonzero and small-bounded.


### 3.3. Robust Principal Component Analysis

The conventional PCA method is used to efficiently estimate a low-dimensional subspace from high-dimensional data. It can be written as follows:(10)
min
⁡
A
,
E
⁡
E
F
,
s
.
t
.
rank
⁡
A
≤
r
,
D
=
A
+
E
,
where ·
F is the Frobenius norm. That means input matrix A is corrupted to generate output matrix D by i.i.d. Gaussian noise. To use PCA, the singular value decomposition (SVD) of D is computed to project the columns of D onto the subspace spanned by the r principal left singular vectors of D.Robust principal component analysis (RPCA) has identity operatorP
Ω
· and sparse matrix E which is different from matrix completion and PCA. Wright [8, 13] has shown that a low-rank matrix A can be recovered exactly by solving the following convex optimization problem from observation matrix D, as long as the error matrix is sufficiently sparse. Consider
(11)
min
⁡
A
,
E
⁡
A
*
+
λ
E
1
,
s
.
t
.
D
=
A
+
E
,
where λ is a positive weighting parameter. RPCA has been used for background modeling, removal of shadows from face images, alignment of human face, and image denoising.


### 3.4. Training Dictionary Based on RPCA

Because the low-frequency part of an image has the main energy the LWT is achieved to example images before training dictionary. Then one uses RPCA to improve the effectiveness and robustness of the SR algorithms.There is little difference in the coefficient values of the low-frequency subimages after a LWT on different images of the same scene. RPCA coefficients are used to represent the low frequencies in an attempt to preserve fidelity and coherency between the subbands. Algorithms have been developed to solve the RPCA problem that has recovered low-rank matrixA and sparse matrix E from observation matrix D. In this paper, we employ theIALM method to compute the low-frequency subband coefficients of dictionary images.SupposeΓ
=
{
I
k
}
k
=
1
m denotes m multisensor corrupted image set. Corresponding to ready-to-be-fused images I
k, low-frequency subimages will be computed by using LWT. Let {
I
~
i
,
j
,
k
}
k
=
1
m be the low-frequency subimages where I
~
i
,
j
∈
R
n
1
×
n
2 denotes the gray values of each pixel whose coordinate is (
i
,
j
). If we represent I
~
i
,
j
,
k as a vector by concatenating all columns of the subimages, we define a n
1
×
n
2
×
m matrix I
~ as follows. The data are standardized. For convenience, let n
1
=
n
2
=
n.Then, we can express the subimages in an equation similar to (8):
(12)
I
~
=
I
~
A
+
I
~
E
,
where I
~
A
∈
R
n
2
×
m denotes the clean and integrated low-frequency subimage sequence matrix and I
~
E
∈
R
n
2
×
m denotes the sparse matrix including errors and noises even though low-pass filter will alternate most of the noise power. The coefficient values of the low-frequency subimages are similar after a LWT on the same scene. If the recovered matrix I
~
A was free of noise and those corrupted elements were fixed successfully, all column vectors in I
~
A should have similar underlying image structures, and the rank of I
~
A should be low which is the prerequisite to matrix completion and RPCA. In such an ideal case, a good estimation of I
~
A may be found by matrix completion and RPCA as indicated by the following equation:
(13)
min
⁡
I
~
A
,
I
~
E
⁡
I
~
A
*
+
λ
P
Ω
I
~
E
1
s
.
t
.
I
~
A
+
I
~
E
=
I
~
,
where augmented Lagrange multiplier is
(14)
L
I
~
A
,
I
~
E
,
Y
,
μ
=
I
~
A
*
+
λ
P
Ω
I
~
E
1
+
Δ
Y
,
I
~
-
I
~
A
-
I
~
E
+
μ
2
I
~
-
I
~
A
-
I
~
E
F
2
.In this equation,λ is a positive weighting parameter representing the ratio of the sparse matrix I
~
E to low-rank matrix I
~
A. μ is a positive value. Δ
(
A
,
B
) is the trace of A
T
B and Y is the iterated Lagrange multiplier.Augmented Lagrange multiplier method has excellent convergence and solution accuracy. In the proposed method of this paper, RPCA is coupled with the inexact augmented Lagrange multiplier (IALM) method to determine the low-frequency coefficients of LWT for corrupted example images. Firstly, we should define some notations to denote some variables which is shown in Notation ofIALM section. k is iteration time.Then, the result ofI
~
A
(
k
+
1
) and I
~
E
(
k
+
1
) will be computed by the following equation:
(15)
U
,
S
,
V
=
∇
I
D
-
I
~
E
k
+
Y
k
μ
k
,
I
~
A
(
k
+
1
)
=
U
S
1
/
μ
k
S
V
T
,
I
~
E
(
k
+
1
)
=
P
Ω
S
λ
/
μ
k
I
~
D
-
I
~
A
k
+
1
+
Y
k
μ
k
+
P
Ω
-
I
~
D
-
I
~
A
k
+
1
+
Y
k
μ
k
,
Y
(
k
+
1
)
=
Y
(
k
)
+
μ
k
(
I
~
D
-
I
~
A
k
+
1
-
I
~
E
k
+
1
)
.In summary, IALM is used to determine the low-frequency component to be fused, and self-adapting regional variance is employed to estimate the high-frequency contribution. The fused wavelet coefficients are combined by ILWT to create the final result.


## 3.1. Overview

The matrix completion problem has been the subject of intense research in recent years. In 2009, Candès and Recht [11] demonstrated exact matrix completion using convex optimization. As the rank of a matrix is not a convex function, the nuclear norm of the matrix can be used to approximate its rank, yielding a convex minimization problem for which there are numerous efficient solutions [11].In 2010, Lin et al. [12] published a fast scalable algorithm for solving the robust PCA problem. The method is based on recovering a low-rank matrix with an unknown fraction of its entries corrupted. The algorithm proceeds as follows: given a rank r matrix A
∈
∑
m
×
n, where r
≪
min
⁡
(
m
,
n
) is the target dimension of the subspace, the observation matrix is D. We can use
(8)
D
=
P
Ω
(
A
)
+
E
to model these sets of linear measurements, where P
Ω
(
·
) is a subsampling projection operator and E represents the matrix of perturbations including complex noise and large errors. It should be relatively sparse compared to A.


## 3.2. Matrix Completion

The objective of matrix completion is to recover the low-dimensional subspace the truly low-rank matrixA from D, under the assumption that E is zero
(9)
min
⁡
A
⁡
A
*
,
s
.
t
.
P
Ω
A
=
D
,
in which ·
* denotes the nuclear norm of a matrix. It has been shown that the solution to this convex relaxation can exactly recover the true low-rank matrix A under quite general conditions [11]. Furthermore, the recovery is stable to small and bounded noise [12], that is, when the entries of E are nonzero and small-bounded.


## 3.3. Robust Principal Component Analysis

The conventional PCA method is used to efficiently estimate a low-dimensional subspace from high-dimensional data. It can be written as follows:(10)
min
⁡
A
,
E
⁡
E
F
,
s
.
t
.
rank
⁡
A
≤
r
,
D
=
A
+
E
,
where ·
F is the Frobenius norm. That means input matrix A is corrupted to generate output matrix D by i.i.d. Gaussian noise. To use PCA, the singular value decomposition (SVD) of D is computed to project the columns of D onto the subspace spanned by the r principal left singular vectors of D.Robust principal component analysis (RPCA) has identity operatorP
Ω
· and sparse matrix E which is different from matrix completion and PCA. Wright [8, 13] has shown that a low-rank matrix A can be recovered exactly by solving the following convex optimization problem from observation matrix D, as long as the error matrix is sufficiently sparse. Consider
(11)
min
⁡
A
,
E
⁡
A
*
+
λ
E
1
,
s
.
t
.
D
=
A
+
E
,
where λ is a positive weighting parameter. RPCA has been used for background modeling, removal of shadows from face images, alignment of human face, and image denoising.


## 3.4. Training Dictionary Based on RPCA

Because the low-frequency part of an image has the main energy the LWT is achieved to example images before training dictionary. Then one uses RPCA to improve the effectiveness and robustness of the SR algorithms.There is little difference in the coefficient values of the low-frequency subimages after a LWT on different images of the same scene. RPCA coefficients are used to represent the low frequencies in an attempt to preserve fidelity and coherency between the subbands. Algorithms have been developed to solve the RPCA problem that has recovered low-rank matrixA and sparse matrix E from observation matrix D. In this paper, we employ theIALM method to compute the low-frequency subband coefficients of dictionary images.SupposeΓ
=
{
I
k
}
k
=
1
m denotes m multisensor corrupted image set. Corresponding to ready-to-be-fused images I
k, low-frequency subimages will be computed by using LWT. Let {
I
~
i
,
j
,
k
}
k
=
1
m be the low-frequency subimages where I
~
i
,
j
∈
R
n
1
×
n
2 denotes the gray values of each pixel whose coordinate is (
i
,
j
). If we represent I
~
i
,
j
,
k as a vector by concatenating all columns of the subimages, we define a n
1
×
n
2
×
m matrix I
~ as follows. The data are standardized. For convenience, let n
1
=
n
2
=
n.Then, we can express the subimages in an equation similar to (8):
(12)
I
~
=
I
~
A
+
I
~
E
,
where I
~
A
∈
R
n
2
×
m denotes the clean and integrated low-frequency subimage sequence matrix and I
~
E
∈
R
n
2
×
m denotes the sparse matrix including errors and noises even though low-pass filter will alternate most of the noise power. The coefficient values of the low-frequency subimages are similar after a LWT on the same scene. If the recovered matrix I
~
A was free of noise and those corrupted elements were fixed successfully, all column vectors in I
~
A should have similar underlying image structures, and the rank of I
~
A should be low which is the prerequisite to matrix completion and RPCA. In such an ideal case, a good estimation of I
~
A may be found by matrix completion and RPCA as indicated by the following equation:
(13)
min
⁡
I
~
A
,
I
~
E
⁡
I
~
A
*
+
λ
P
Ω
I
~
E
1
s
.
t
.
I
~
A
+
I
~
E
=
I
~
,
where augmented Lagrange multiplier is
(14)
L
I
~
A
,
I
~
E
,
Y
,
μ
=
I
~
A
*
+
λ
P
Ω
I
~
E
1
+
Δ
Y
,
I
~
-
I
~
A
-
I
~
E
+
μ
2
I
~
-
I
~
A
-
I
~
E
F
2
.In this equation,λ is a positive weighting parameter representing the ratio of the sparse matrix I
~
E to low-rank matrix I
~
A. μ is a positive value. Δ
(
A
,
B
) is the trace of A
T
B and Y is the iterated Lagrange multiplier.Augmented Lagrange multiplier method has excellent convergence and solution accuracy. In the proposed method of this paper, RPCA is coupled with the inexact augmented Lagrange multiplier (IALM) method to determine the low-frequency coefficients of LWT for corrupted example images. Firstly, we should define some notations to denote some variables which is shown in Notation ofIALM section. k is iteration time.Then, the result ofI
~
A
(
k
+
1
) and I
~
E
(
k
+
1
) will be computed by the following equation:
(15)
U
,
S
,
V
=
∇
I
D
-
I
~
E
k
+
Y
k
μ
k
,
I
~
A
(
k
+
1
)
=
U
S
1
/
μ
k
S
V
T
,
I
~
E
(
k
+
1
)
=
P
Ω
S
λ
/
μ
k
I
~
D
-
I
~
A
k
+
1
+
Y
k
μ
k
+
P
Ω
-
I
~
D
-
I
~
A
k
+
1
+
Y
k
μ
k
,
Y
(
k
+
1
)
=
Y
(
k
)
+
μ
k
(
I
~
D
-
I
~
A
k
+
1
-
I
~
E
k
+
1
)
.In summary, IALM is used to determine the low-frequency component to be fused, and self-adapting regional variance is employed to estimate the high-frequency contribution. The fused wavelet coefficients are combined by ILWT to create the final result.


## 4. Experimental Results and Analysis

### 4.1. Time Complexity Experiments

To assess the accuracy and robustness of training overcomplete dictionary pair, 100000 standard LR and HR image patches were partitioned and trained from image libraries (http://decsai.ugr.es/cvg/dbimagenes/). To validate the new procedure, the four numbers of atoms were setting, respectively: Q
1
=
256, Q
2
=
512, Q
3
=
1024, and Q
4
=
2048. The size of each atom is 9
×
9 pixels. Different from the SRSR algorithm, the proposed method, namely, SRS
R
∂, processed the 3-tier LWT to the example images. By adopting inverse lifting wavelet transform (ILWT), reconstructed HR image patches preserve the high-frequency critical features. The 75% example image pixels involved in the training dictionary are reduced. Experiment result is shown in Figure 3.Figure 3
Comparison of time complexity.Obviously, the computation training dictionary seconds ofSRS
R
∂ are shorter 61.32%, 62.00%, 60.40%, and 62.67% than SRSR by increasing the number of atoms Q. A larger number of atoms indicate that overcomplete dictionary pair includes more reconstructed accuracy, in the meanwhile, spending more time to train. In this study, balancing the training accuracy and time complexity, the value of Q is set to 1024.


### 4.2. Robustness Experiments

As mentioned in Section1, PCA failed to estimate the original data when data was broken severely. To solve this problem, sparse coefficients are determined through RPCA instead of PCA.To verify the reported methodSRS
R
∂ robustness to some missing data and errors, the 10% random errors and the 10% missing data were applied to HR image patches for training dictionary. Therefore, the downsampling rate to original images reaches 20%. An overcomplete dictionary pair D
L and D
H were estimated to process SR. Test images called “bookshelf,” “girl face,” “lena,” “flower,” and “building” were processed by three mainstream SR algorithms—Bicubic, NESR, SRSR, and SRS
R
∂.The peak signal-to-noise ratio (PSNR) is an expression for the ratio between the maximum possible power of a signal and the power of distorting noise that affects the quality of its representation. This objective metric is used to compare the robustness of algorithms by measuring the proximity of the SR reconstructed image and the original image.Table1 shows the PSNR (dB) performance evaluation measures for the four SR algorithms. The results reveal that Bicubic has the worst reconstructed performance. NESR and SRSR have been severely affected by broken data in training dictionary, ranging from 21.3871 dB to 31.4007 dB. Relative to the other three algorithms, SRS
R
∂ has the most robustness to broken data in the process of training dictionary.Table 1
PSNR comparisons of SR algorithms.
Image
Bicubic
NESR
SRSR
SRSR
∂
Bookshelf
19.5365
21.3871
25.7684
32.0384
Girl face
20.7177
24.3363
27.5486
33.7557
Lena
19.5539
24.6899
25.4578
32.8545
Flower
20.1793
26.0911
31.4007
34.1617
Building
21.9827
22.5101
27.7380
34.2074The results of the four comparative SR algorithms are shown in Figures4, 5, 6, 7, and 8. The required HR resolution is four times that of the LR images.SR result for “bookshelf” (128 × 96 upscale to 512 × 384).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “girl face” (70 × 70 upscale to 280 × 280).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “lena” (64 × 64 upscale to 256 × 256).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “flower” (80 × 80 upscale to 320 × 320).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “building” (100 × 80 upscale to 400 × 320).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR image


## 4.1. Time Complexity Experiments

To assess the accuracy and robustness of training overcomplete dictionary pair, 100000 standard LR and HR image patches were partitioned and trained from image libraries (http://decsai.ugr.es/cvg/dbimagenes/). To validate the new procedure, the four numbers of atoms were setting, respectively: Q
1
=
256, Q
2
=
512, Q
3
=
1024, and Q
4
=
2048. The size of each atom is 9
×
9 pixels. Different from the SRSR algorithm, the proposed method, namely, SRS
R
∂, processed the 3-tier LWT to the example images. By adopting inverse lifting wavelet transform (ILWT), reconstructed HR image patches preserve the high-frequency critical features. The 75% example image pixels involved in the training dictionary are reduced. Experiment result is shown in Figure 3.Figure 3
Comparison of time complexity.Obviously, the computation training dictionary seconds ofSRS
R
∂ are shorter 61.32%, 62.00%, 60.40%, and 62.67% than SRSR by increasing the number of atoms Q. A larger number of atoms indicate that overcomplete dictionary pair includes more reconstructed accuracy, in the meanwhile, spending more time to train. In this study, balancing the training accuracy and time complexity, the value of Q is set to 1024.


## 4.2. Robustness Experiments

As mentioned in Section1, PCA failed to estimate the original data when data was broken severely. To solve this problem, sparse coefficients are determined through RPCA instead of PCA.To verify the reported methodSRS
R
∂ robustness to some missing data and errors, the 10% random errors and the 10% missing data were applied to HR image patches for training dictionary. Therefore, the downsampling rate to original images reaches 20%. An overcomplete dictionary pair D
L and D
H were estimated to process SR. Test images called “bookshelf,” “girl face,” “lena,” “flower,” and “building” were processed by three mainstream SR algorithms—Bicubic, NESR, SRSR, and SRS
R
∂.The peak signal-to-noise ratio (PSNR) is an expression for the ratio between the maximum possible power of a signal and the power of distorting noise that affects the quality of its representation. This objective metric is used to compare the robustness of algorithms by measuring the proximity of the SR reconstructed image and the original image.Table1 shows the PSNR (dB) performance evaluation measures for the four SR algorithms. The results reveal that Bicubic has the worst reconstructed performance. NESR and SRSR have been severely affected by broken data in training dictionary, ranging from 21.3871 dB to 31.4007 dB. Relative to the other three algorithms, SRS
R
∂ has the most robustness to broken data in the process of training dictionary.Table 1
PSNR comparisons of SR algorithms.
Image
Bicubic
NESR
SRSR
SRSR
∂
Bookshelf
19.5365
21.3871
25.7684
32.0384
Girl face
20.7177
24.3363
27.5486
33.7557
Lena
19.5539
24.6899
25.4578
32.8545
Flower
20.1793
26.0911
31.4007
34.1617
Building
21.9827
22.5101
27.7380
34.2074The results of the four comparative SR algorithms are shown in Figures4, 5, 6, 7, and 8. The required HR resolution is four times that of the LR images.SR result for “bookshelf” (128 × 96 upscale to 512 × 384).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “girl face” (70 × 70 upscale to 280 × 280).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “lena” (64 × 64 upscale to 256 × 256).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “flower” (80 × 80 upscale to 320 × 320).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR imageSR result for “building” (100 × 80 upscale to 400 × 320).
(a)
LR image
(b)
Bicubic
(c)
NESR
(d)
SRSR
(e)
SRS
R
∂
(f)
HR image


## 5. Summary

For the computational complexity of training overcomplete dictionary pair, this paper proposes the 3-tier LWT to decompose the trained example images into low-frequency, horizontal, vertical, and diagonal high-frequency components. The high-frequency components in the example images can be accurately estimated through the second and the third layers’ wavelet coefficients.PCA fails to estimate the gray value of broken pixels in the example images when corruption is severe, even if only very few of the observations are affected. For similarity of multiframe observation images, this research uses RPCA coupled with the IALM method instead of PCA to solve the robustness problem.Experimental results show that the new algorithm not only shortens effectively the training overcomplete dictionary pair time of up to 60% but also provides significantly improved clarity for the reconstructed SR images.



---

*Source: 386835-2014-11-23.xml*