# Image Recovery Algorithm Based on Learned Dictionary

Authors: Xinghui Zhu; Fang Kui
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We proposed a recovery scheme for image deblurring. The scheme is under the framework of sparse representation and it has three main contributions. Firstly, considering the sparse property of natural image, the nonlocal overcompleted dictionaries are learned for image patches in our scheme. And, then, we coded the patches in each nonlocal clustering with the corresponding learned dictionary to recover the whole latent image. In addition, for some practical applications, we also proposed a method to evaluate the blur kernel to make the algorithm usable in blind image recovery. The experimental results demonstrated that the proposed scheme is competitive with some current state-of-the-art methods.


---

## Body

## 1. Introduction

Image recovery has been a widely studied issue in the past decades, which remains an active area in low-level image processing [1, 2]. Many factors may cause blur, such as the imperfection of devices, atmospheric turbulence (for remote sensing image), and motion between the camera and scene. By assuming the blur model is linear and space invariant, the observation can be expressed as
(1)y=H⊗x+n,
where y and x denote the blurry image and the latent image, respectively, H is the blur kernel, and ⊗ and n represent the convolution operation and the additive white Gaussian noise. The mission of deblurring is to obtain the latent image x from the degradation observation y, which is usually solved by the regularization method due to its ill-posed property. The key idea of the regularization is to penalize the prior knowledge of latent image. In the past decades, many kinds of prior knowledge have been studied in literatures [3–5]. In recent years, the sparse regularization based modeling is employed to solve the recovery problems, which is proven to be more effective than the conventional regularization. Jalobeanu et al. proposed to deblur the satellite image with complex wavelet packet, which established a Gaussian model for the sparse coefficients [6]. Cho et al. [7] proposed a regression model by exploiting the sparsity of natural image to mitigate the ringing artifacts in the deblurred image, which can be seen as a natural generalization work of [8]. Based on the dictionary learning, Foi et al. proposed a shape adaptive DCT for high-quality image deblurring [9]. Recently, incorporating with the sparse representation, the NLM (nonlocal means) method is exploited in many image processing tasks successfully, such that [10, 11] all achieve the impressive recovery results based on this model. In this paper, inspired by the sparse representation and NLM techniques, we proposed a novel scheme for image deblurring, which will train many subdictionaries to better present the patches with different features and recover the whole latent image based on sparse model.The outline of the remainder of the paper is as follows. In Section2, we review the regularization framework for image deblurring and propose a novel optimization based on sparse representation. In Section 3, we show an iterative method to solve the optimization in Section 2 with the alternating direction method (ADM), and, additionally, a dictionary learning method with NLM is developed to better present the image. The numerical experiments are shown in Section 4 and we concluded the paper in Section 5.


## 2. Deblurring Framework with Sparse Model

To begin, following the conventional notation in many literatures, we denote the latent image byX∈RN and degradation image by Y∈RN; we show the blurry model as follows:
(2)Y=H⊗X+n,
where ⊗ indicates the convolution operator and H and n are the blurring kernel and additive white Gaussian noise, respectively.Based on the regularization, we can formulate the optimization to obtain the solution for (2) as follows:
(3)X^=argmin⁡{∥Y-H⊗X∥F2+λp(X)},
where ∥•∥F denotes the Frobenius norm and the p(•) presents regularization for latent image X, such as the TV norm and smoothness prior.To solve the optimization in (3), we still need to know the blur kernel. Nevertheless, in practice, it is unknown for blind image deblurring. A popular estimation method is developed in [12]; in their work, the authors proposed to estimate the blur kernel as follows:
(4)H^=argmin⁡{∥Y-H⊗X^∥F2+∥H∥22}.In our scheme, we incorporate the model in (3) and (4) into a novel unified variational framework as follows:
(5)(X^,H^)=argmin⁡{∥Y-H⊗X∥F2+λp(X)+ηφ(H)},
where p(•) and φ(•) denote the regularization penalty term of desired latent sharp image and blur kernel, respectively, which can stabilize the solution. λ and η are termed regularization parameters.Furthermore, assuming the image patch of sizen×n at location i by xi=RiX(xi∈Rn,n≪N) and the dictionary by D∈Rn×M(n≪M), we can propose a novel framework based on the sparse model in the following form:
(6)(X^,H^)=argmin⁡{∥Y-H⊗X∥F2+∑i(∥RiX-Dαi∥22+λi∥αi∥1)FFFfFfFFFFI+ηi∥H∥22∑i(∥RiX-Dαi∥22+λi∥αi∥1)},
where Ri is a matrix to extract the patch from the latent image at location i. The first term in (6) is called fidelity constraint, which guarantees that the latent image is consistent with the degradation observation. The second term constrains the sparsity of patches in image with the reasonable dictionary D. The third term is the l2-norm constraint on blur kernel to preserve the solution stability.As for the optimization in (6), the recent alternating direction method (ADM) [13] can be employed to obtain the solution, which is the popular method used in multivariables optimization. In addition, the dictionary D is also a valuable issue to be studied, because the more reasonable the dictionary is, the more effective the restoration result is. So, in the next section, we will present an iterative algorithm based on ADM to solve the minimization in (6).


## 3. Iterative Algorithm for Image Deblurring

### 3.1. Local Dictionary Learning

In recent years, there has been a growing interest in studying the sparse model and its application to image processing. And a key technique for spare model is to design a dictionary to better fit the above model, which is generated in two main methods. The first one is combining some predefined bases to generate a comprehensive dictionary, such as wavelet and DCT. Nevertheless, by this method, the generated dictionary is not data independent. In other words, the dictionary can be termed “fixed.” The other one is to learn a dictionary adaptive to a set of training examples from degradation image itself or some sample images. In our framework, we intend to adopt the second method, which will make the dictionary more adaptive and flexible. The recent method termed KSVD is introduced by Aharon et al. [14]. In their work, the author tended to learn a global dictionary and best presented the patches from the image. However, the training tends to generate a group of atoms that can present each patch in image, which leads to loss of some ability to present some local structure.Note that the patches with similar structure in image may be presented by the same dictionary ideally. Motivated by the NLM technique, our learning scheme is proposed to train many local dictionaries for similar patches in the same cluster. For low complexity, we can measure the distance between two patches as follows:(7)Dist(yi,yj)=exp⁡{-∥yi-yj∥22h},
where yi and yj denote the patch at locations i and j and h is the scale parameter to control the discrimination. And, then, we can take the distance in (7) as the measurement and cluster the patches by K-Mean algorithm.Next, given the train examples setCi={yji}j=1J corresponding to clustering i; we can learn the local dictionary adaptive to this clustering by the following minimization:
(8)D^=argmin⁡D,A{∥Ci-DA∥F2+λ∑j=1J∥aj∥1},
where A denotes the coding matrix and aj is its jth column corresponding to patch yj.


### 3.2. Deblurring Algorithm

In this section, we will propose an iterative algorithm to solve the novel framework in (6). By the ADM method, we can solve the minimization alternately and divide the optimization into three major parts.Firstly, by fixing all other variables withoutH, (6) can be reduced to the following form:
(9)H^=argmin⁡H{∥Y-H⊗X^∥F2+∥H∥22}.The minimization (9) is a strictly convex problem, which leads to a closed-form solution as follows:
(10)H^=F-1(conj(F(X^)∘F(Y))∥F(X^)∥F2+ηI),
where F(•) and F-1(•) denote the fast Fourier transform (FFT) and its inverse. conj(•) denotes the complex conjugate operator, the “∘” presents the pointwise product, and I is a unit matrix.Secondly, by fixing the code set{αj}j=1Jiand the estimation blur kernel H^, we can generate the second major part as follows:
(11)X^i=argmin⁡X{∥Yi-H^⊗Xi∥F2+∑jγj∥RjXi-Diαj∥},
where Di denotes the local learned dictionary for the patches in clustering i and footnote i presents the variable corresponding to clustering i.Given the sparse coding set and the blur kernel, (11) can be solved with the fast deconvolution method [15] as follows:
(12)X^i=F-1{conj(F(H^))∘F(Yi)+F(∑jγjRjTDiα^j)∥H^∥22+F(∑jγjRjTRjI)}.At last, we coded the patches fromX^i with the local dictionary to update the sparse coding set {αj}j=1Ji for the next iteration by the following minimization:
(13)α^j=argmin⁡αj{∥RjX^i-Diαj∥22+λ∥αj∥1}.The comprehensive deblurring scheme is summarized in Algorithm1.Algorithm 1
Input: The patches set{yj}j=1N from the degradation image Y(0).
Initialization:λ=0.1, η=1, the coarse estimation latent image X^(0)
by the method in  [11];
Fork=0 : T
Learn the local dictionary{Di}i=1K by  (8) with train set from Y(k);
Estimate the new kernelH^(k) by (10) with X^(k);
Fori=1 : K (K means the maximum clustering number)
Compute the latent imageX^i(k+1) by (12);
Compute the coding set{αji}j=1Ji of X^i(k+1) by solving  (13)
via the method in [12];
end
Update theY(k+1)=X^(k+1);
end
Output the comprehensive latent imageX^.In Algorithm1, the coding by (13) can be implemented by some recent sparse coding algorithms, such as “Basis Pursuit” and “Orthogonal Matching Pursuit”. With Algorithm 1, the proposed scheme solves our novel framework with the unified variational formulation, which shows some advantage in practice.


## 3.1. Local Dictionary Learning

In recent years, there has been a growing interest in studying the sparse model and its application to image processing. And a key technique for spare model is to design a dictionary to better fit the above model, which is generated in two main methods. The first one is combining some predefined bases to generate a comprehensive dictionary, such as wavelet and DCT. Nevertheless, by this method, the generated dictionary is not data independent. In other words, the dictionary can be termed “fixed.” The other one is to learn a dictionary adaptive to a set of training examples from degradation image itself or some sample images. In our framework, we intend to adopt the second method, which will make the dictionary more adaptive and flexible. The recent method termed KSVD is introduced by Aharon et al. [14]. In their work, the author tended to learn a global dictionary and best presented the patches from the image. However, the training tends to generate a group of atoms that can present each patch in image, which leads to loss of some ability to present some local structure.Note that the patches with similar structure in image may be presented by the same dictionary ideally. Motivated by the NLM technique, our learning scheme is proposed to train many local dictionaries for similar patches in the same cluster. For low complexity, we can measure the distance between two patches as follows:(7)Dist(yi,yj)=exp⁡{-∥yi-yj∥22h},
where yi and yj denote the patch at locations i and j and h is the scale parameter to control the discrimination. And, then, we can take the distance in (7) as the measurement and cluster the patches by K-Mean algorithm.Next, given the train examples setCi={yji}j=1J corresponding to clustering i; we can learn the local dictionary adaptive to this clustering by the following minimization:
(8)D^=argmin⁡D,A{∥Ci-DA∥F2+λ∑j=1J∥aj∥1},
where A denotes the coding matrix and aj is its jth column corresponding to patch yj.


## 3.2. Deblurring Algorithm

In this section, we will propose an iterative algorithm to solve the novel framework in (6). By the ADM method, we can solve the minimization alternately and divide the optimization into three major parts.Firstly, by fixing all other variables withoutH, (6) can be reduced to the following form:
(9)H^=argmin⁡H{∥Y-H⊗X^∥F2+∥H∥22}.The minimization (9) is a strictly convex problem, which leads to a closed-form solution as follows:
(10)H^=F-1(conj(F(X^)∘F(Y))∥F(X^)∥F2+ηI),
where F(•) and F-1(•) denote the fast Fourier transform (FFT) and its inverse. conj(•) denotes the complex conjugate operator, the “∘” presents the pointwise product, and I is a unit matrix.Secondly, by fixing the code set{αj}j=1Jiand the estimation blur kernel H^, we can generate the second major part as follows:
(11)X^i=argmin⁡X{∥Yi-H^⊗Xi∥F2+∑jγj∥RjXi-Diαj∥},
where Di denotes the local learned dictionary for the patches in clustering i and footnote i presents the variable corresponding to clustering i.Given the sparse coding set and the blur kernel, (11) can be solved with the fast deconvolution method [15] as follows:
(12)X^i=F-1{conj(F(H^))∘F(Yi)+F(∑jγjRjTDiα^j)∥H^∥22+F(∑jγjRjTRjI)}.At last, we coded the patches fromX^i with the local dictionary to update the sparse coding set {αj}j=1Ji for the next iteration by the following minimization:
(13)α^j=argmin⁡αj{∥RjX^i-Diαj∥22+λ∥αj∥1}.The comprehensive deblurring scheme is summarized in Algorithm1.Algorithm 1
Input: The patches set{yj}j=1N from the degradation image Y(0).
Initialization:λ=0.1, η=1, the coarse estimation latent image X^(0)
by the method in  [11];
Fork=0 : T
Learn the local dictionary{Di}i=1K by  (8) with train set from Y(k);
Estimate the new kernelH^(k) by (10) with X^(k);
Fori=1 : K (K means the maximum clustering number)
Compute the latent imageX^i(k+1) by (12);
Compute the coding set{αji}j=1Ji of X^i(k+1) by solving  (13)
via the method in [12];
end
Update theY(k+1)=X^(k+1);
end
Output the comprehensive latent imageX^.In Algorithm1, the coding by (13) can be implemented by some recent sparse coding algorithms, such as “Basis Pursuit” and “Orthogonal Matching Pursuit”. With Algorithm 1, the proposed scheme solves our novel framework with the unified variational formulation, which shows some advantage in practice.


## 4. Numerical Results and Analysis

We conduct some numerical experiments to demonstrate the performance of our proposed scheme. The compared method includes the BM3D proposed in [16], SA-DCT method in [9], FISTA in [17], and our scheme. The sizes of test images are all 256 × 256 and the pixel value ranges to [0,1]. The Gaussian blur kernel with the standard deviation 1.5 was used in our experiments and the additive white noise with different standard deviation was also adopted. The maximum iteration number T=10. For low computing complexity, the clustering number K is set to be 5 empirically. The zoomed local visual comparisons are shown in Figures 1 and 2, and we only show the deblurring results of Parrots and Cameraman with σ=1 due to the limited space. Also, the PSNR for test images is reported in Tables 1 and 2 as the objective evaluation.Table 1
PSNR (dB) results of the recovered image withσ=1.
Method/image
BM3D
SADCT
FISTA
Proposed
Lena
31.2615
28.8271
28.8129
30.9176
Cameraman
27.9001
26.2613
25.4112
27.1056
Parrots
31.3120
28.3765
28.5020
30.8230
Peppers
29.6203
28.3270
28.1644
29.1026Table 2
PSNR (dB) results of the recovered image withσ=2.
Method/image
BM3D
SADCT
FISTA
Proposed
Lena
30.3902
27.6494
26.8268
29.6937
Cameraman
26.9831
25.3297
24.0339
26.2203
Parrots
30.2611
27.1512
26.5932
29.3679
Peppers
28.7621
27.2626
26.3425
28.1023Figure 1
Recovery results of Cameraman.Figure 2
Recovery results of Parrots.From the visual comparison results, we can see that our novel scheme outperforms other methods in overcoming the staircase effect and also show some advance in recovering the texture and shaper edge. Also, the PSNR results also demonstrate that our method is competitive with the compared method and presents robustness with higher noise standard deviation. Though the BM3D obtains the highest PSNR, its visual results still leave some staircase effect in the part of smooth areas. The PSNR of our scheme is only a little lower than BM3D, but the visualization seems better, such as the texture, which means that our method shows synthesis advantage compared to BM3D. In addition, in the experiments, we found that the PSNR decreased with the increasing iterations, which can guarantee the convergence of our scheme empirically.


## 5. Conclusions

In this paper, we addressed the image deblurring problem. We proposed a scheme based on the sparse representation. To better present the image, we learned many dictionaries via the patches with nonlocal self-similarity. And, then, we incorporated the kernel estimation and sparse model into a novel unified framework. Additionally, an iterative algorithm was provided to solve the novel framework with the ADM. The experimental results demonstrate that our proposed scheme outperforms some leading methods. For further work, many possible extension researches can be explored, such as extending the framework to video deblurring and considering some other kinds of noise.



---

*Source: 964835-2014-08-12.xml*