# The Nonlocal Sparse Reconstruction Algorithm by Similarity Measurement with Shearlet Feature Vector

Authors: Wu Qidi; Li Yibing; Lin Yun; Yang Xiaodong
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Due to the limited accuracy of conventional methods with image restoration, the paper supplied a nonlocal sparsity reconstruction algorithm with similarity measurement. To improve the performance of restoration results, we proposed two schemes to dictionary learning and sparse coding, respectively. In the part of the dictionary learning, we measured the similarity between patches from degraded image by constructing the Shearlet feature vector. Besides, we classified the patches into different classes with similarity and trained the cluster dictionary for each class, by cascading which we could gain the universal dictionary. In the part of sparse coding, we proposed a novel optimal objective function with the coding residual item, which can suppress the residual between the estimate coding and true sparse coding. Additionally, we show the derivation of self-adaptive regularization parameter in optimization under the Bayesian framework, which can make the performance better. It can be indicated from the experimental results that by taking full advantage of similar local geometric structure feature existing in the nonlocal patches and the coding residual suppression, the proposed method shows advantage both on visual perception and PSNR compared to the conventional methods.


---

## Body

## 1. Introduction

The reasonable representation is the basis of many tasks in image processing. The meaning of “reasonable” is to express the important information in image with less coefficients, which is called sparse representation [1]. We always want to express the signal in a cost-effective way, which could reduce the cost in signal processing. However, the emerging of sparse representation satisfied the requirements exactly. Wavelet is the landmark work, which is the most optimal expression of one-dimension signal. But it shows weak ability to express the high-dimension signal for its limited directions. For solving the problem, Donoho proposed the multiscale geometric analysis theory, which contains Ridgelet, Curvelet [2], Bandlet, and Contourlet [3] mainly, and then applied them to image restoration, which achieved good effect.As for the sparse representation in image restoration, there are two main approaches, including multiscale geometric analysis (MGA) and dictionary learning. With the MGA, Donoho proposed the pioneer wavelet threshold shrinking method. After that, Yin designed a non-gaussian bivariate Shrinkage function [4] under the MAP norm, which got the better performance. In 2006, as the limited directions in wavelet, Arthur proposed the NSCT transformation [5, 6] and applied it in the restoration area by Bayesian framework. But these conventional restoration models may not be accurate enough when the image is degraded seriously for their fixed over-completed dictionary, which is not sufficient to present the abundant structures in nature images. So, a new concept is proposed, which is called dictionary learning [7–9]. Besides, many methods about how to sparse coding are proposed, such as MP [10], OMP [11], and GP [12], which is called sparse coding. Further, a method called K-SVD [13, 14] is proposed by Aharon, which updates the dictionary by making SVD decomposition to the residual signal, and is applied to precision image restoration.The goal of this paper is to research the sparse construction algorithm for image restoration based on the dictionary learning framework. We propose a nonlocal block sparse reconstruction scheme by shearlet feature vector, by which we measure the similarity between image patches and classify them for learning cluster dictionary. Then, we propose a new objective function for sparse coding to realize the high accuracy image restoration.


## 2. Image Restoration with Dictionary Learning

Suppose that the model among the observation signaly, original signal x, and noise n satisfied
(1)y=x+n.According to the sparse representation theory in [1], the sparse coding is equal to solving the optimization problem in (2):
(2)min⁡∥α∥0s.t∥y-Dα∥22≤ε.In which,D is the sparse dictionary of x and α is the coding vector. Then, we can get the original signal by x^=Dα^. ε is a constant with the noise standard deviation, ε=(Cσ)2.For the general restoration algorithm based on the sparse theory, dictionaryD is fixed. So a new design for dictionary learning called K-SVD is proposed in reference [13] and good results have been achieved in image restoration. In the K-SVD, we implement the sparse coding and dictionary learning simultaneously. And, the optimization task in (2) can be changed to
(3)(α^x,D^)=argmin⁡α,D{∥y-Dα∥22+λ∥α∥0},x^=Dα^x.Elad et al. divided the image into many patches for not increasing the dictionary dimension and got the block-based sparse codingα^i,j with
(4)α^i,j=argmin⁡{∥yi,j-Dα∥22+λ∥α∥0}.In which,yi,j presents the patch whose central is (i,j). The size of patch is 7 × 7. They are gained by sliding a squared windows in the image. Then, we can get the restored image by averaging these patches.Generally, K-SVD learns the dictionary with some random training examples from the image, so the learned atoms show some weakness in presenting certain local structure in image, which makes the coding not sparsity enough. So, the paper has two contributions. The first is that we proposed a dictionary learning scheme based on clustering, which trained subdictionary for each cluster and then produced the universal dictionary with them. Secondly, we proposed a novel objective function for sparse coding, which added a coding residual item compared to the traditional ones. The detail for the two contributions will be introduced as follows.


## 3. A Novel Scheme for Image Restoration

### 3.1. Nonsubsampling Shearlet Transform

Nonsubsampling Shearlet [15] is a multiscale geometric analytical method advanced by Lim and Kutyniok. It consisted of laplacian pyramid and direction filter bands with multidirections and shift invariant. For its parabola scale principle, Nonsampling Shearlet has excellent performances on capturing geometrical feature and singularity in high-dimension, which makes it widely used in image restoration.


### 3.2. Similarity Measurement

As to the many advantages with Shearlet, we propose a similarity measurement method. Implement the Shearlet transform withl levels and construct the feature vector for each pixel as
(5)V=(sv1,0,…,sv1,ε1,…,svl,0,…,svl,εl)T.Here,εl is the number of subband in lth level and svl,ε is the Shearlet coefficient. With the anisotropy feature, the coefficient for signal is large while the local geometric structure is similar to the basis function. Conversely, the coefficient is small, while the noise has the isotropy feature, so the coefficients are uniform in each primary function. Due to the above two reasons, the vector in (5) has the better antinoise ability, according to which, we take (5) to measure the similarity between the two patches. Suppose the size of patch is 5 × 5, we get the vector in (5) for all the 25 pixels. Then, we construct some subvector Vsub,k generated by the kth dimension of V:
(6)Vsub,k=(V1(k),V2(k),…,V25(k))T.In which, theVi(k) presents the kth element of Vi (i is the order number of the pixel in each patch, i=1,…,25). Suppose Vsub,k1 and Vsub,k2 are from two patches to be measured, we compute the index Si as follows:
(7)Si=exp⁡{-∑k∥Vsub,k1-Vsub,k2∥22vk2}.In which,vk is called shearlet wave coefficient vk=γσk (σk is the coefficient standard deviation with kth sub-band). With the formulation in (6), we can measure the similarity between two patches better than the Euclidean distance of gray in spatial domain.


### 3.3. Nonlocal Dictionary Learning

#### 3.3.1. Nonlocal Dictionary Learning

The restoration algorithm consisted of two main parts that are dictionary learning and sparse coding, respectively. In this paper we improve the algorithm with the method for similarity measurement in Section3.2. It is different to the conventional methods that we did not simply select the training patches from different example images to train the dictionary, while we select the nonlocal similar patches from the degraded image we want to restoration. And then, we cluster these patches to train the cluster subdictionary, which is more sufficient to make the universal dictionary better adapt to local geometrical feature than global K-SVD. Besides, the training data in the same cluster is similar to each other, so there is no need to produce an over-completed dictionary. So each subdictionary size is half of the size of corresponding cluster. Now we present the concrete description for learning scheme as follows.Step 1.
Implement the Shearlet transform to the imageY.Step 2.
Construct the Shearlet feature vector according to the formula (5) (The patch size is 5×5).Step 3.
Calculate the standard deviation ofkth subband (σk=(1/N2)∑i=1N2(yi-y-)2) and gain the wave coefficient vk, yi and y- is the shearlet coefficient and the mean value of coefficients; N is the total number of coefficients in kth subband.Step 4.
Cluster the patches by method in [16] with the index Si in formula (6) and then produce the cluster Ωi (i=1,2,…,K is the cluster indicator).Step 5.
Take the patches inΩi as the training data and learning the cluster subdictionary with K-SVD.Step 6.
By cascading all the cluster dictionaries, we can get the universal dictionary for the whole image.With the ability of capturing the local geometrical feature, the patches in the same set are highly similar by their geometry structure, which makes atoms in subdictionary have the strong adaptability to local structure. So, they can sufficiently present the local geometrical feature. Cascaded by all the subdictionaries, the universal dictionary realizes the goal that presents all kinds of features in the whole image.Now we show a simple example to show the advantage of clustering-based dictionary learning. We list a set of training examples:(8)[100,200,0]T,[110*randn(1),120*randn(1),0]T,[100*randn(1),80*randn(1),0]T,[0,150*randn(1),200*randn(1)]T.Here, “randn” means produce a Gaussian stochastic variable, and then, we take the above two groups of training data to learn a dictionary with two atoms. We adopt the proposed algorithm and K-SVD, respectively. Set the Maximum iteration number with KSVD to be 10 and we show the learned dictionary in Table1.Table 1
Learned Dictionary with different methods.
Method
Learned Dictionary
KSVD
[
-
0.5630
-
0.0459
-
0.7995
0.2835
-
0.2096
-
0.9579
]
Proposed algorithm
[
-
0.5375
0
-
0.8432
0.3294
0.0000
-
0.9442
]As can be seen in Table1, the atoms by proposed algorithm have the more similar structure with the training data.


#### 3.3.2. Sparse Coding

For improving the coding accuracy, we proposed a novel optimization called coding residual suppression optimization, which is more sufficient thanl1-norm sparse coding. When dictionary is given, the l1-norm sparse coding for original signal can be realized as follows:
(9)α^x=argmin⁡{∥x-Dα∥2+λ∥α∥1}.In the restoration problem, we can only get the observationy. So the sparse coding can be rewritten as
(10)α^y=argmin⁡{∥y-Dα∥2+λ∥α∥1}.Comparing (9) and (10), we can see that if we want to reconstruct x with high accuracy, the coding α^y is expected to be as close as possible to the true sparse coding α^x. So we introduce the residual coding αδ as follows:
(11)αδ=αy-αx.Then we change the object function (10) into the residual suppression form:
(12)α^y=argmin⁡{∥y-Dα∥2+λ∑k∥αk∥1+μ∑k∥αδk∥1},αδk=αk-η^i,
where k is the indicator of kth patch. In addition, we cannot get the true sparse coding practically, so the η^i is a good estimation of the true sparse coding and can be calculated from weighted average of sparse coding of patches in the same cluster; λ and μ are the regularization parameters. If kth patch is from Ωi, we calculate η^i:
(13)η^i=∑pωi,pα^i,p,ωi,p=cexp⁡{-∥x^i-x^i,p∥22}(cisthenormalizationparameter).The second term in optimization equation (12) is used to ensure the local sparsity that only part of atoms are selected for the dictionary. But, in our scheme, we select one subdictionary for each patch in a certain cluster, which means that the coding of another subdictionary is zero. So our scheme guarantees the sparsity naturally; that is, we can move the second term in (12) and rewrite it as follows:
(14)α^y=argmin⁡{∥y-Dα∥2+μ∑k∥αδk∥1}.With (14), we can compact the optimization only with coding residual constraint, which means that the coding from the observed signal by (14) is close to that from the original signal by (9).


#### 3.3.3. Scheme Summary

The whole scheme consisted of two-level iterative algorithm; now we present the brief steps as follows.Initial: set the initial imageX^=Y (Y is the degraded image); D(0) is the DCT complete dictionary and calculate the initial sparse coding for each patch with any pursuit algorithm.Outer Loop:(a)
on the (OL)th iteration: learn the dictionaryD(OL) by X^ with the algorithm proposed in Section 3.3.1 (L is the maximum iterative number, OL=1,2…,L);(b)
compute the good estimation set{ηi}i=1,…,K for all the clusters under the D(OL).(c)
Inner Loop:
(i)
for each patch, we get its codingα^y by (14), which can be solved with the method in [17];(ii)
repeat (i) until all the patches are processed;(d)
estimate all the restoration patches byx^=D(OL)α^y;(e)
OL=OL+1, repeat.On one hand, theη^i is more and more approach to the true sparse coding, which makes the residual suppression more sufficient. On the other hand, by alternating the sparse coding and dictionary learning, coding and dictionary are all improved and promote each other.


#### 3.3.4. Parameter Selection

In conventional models, the regularization parameter is generally a constant. Hence, for making (14) more sufficient, we give the derivation of self-adaptive regularization parameter μ under the Bayes framework.For written convenience, we takeδ=αk-η^i as the residual coding vector. Under the Bayes framework, the MAP estimation of δ can be computed as
(15)δ=argmax⁡{log⁡(p(δ∣y))}=argmax⁡{log⁡(p(y∣δ))+log⁡(p(δ))}.
And the p(y∣δ) is
(16)p(y∣δ)=p(y∣α,η^)=12πσnexp⁡{-12σn2∥y-Dα∥22},
where σn is the standard deviation of noise.As forp(δ), with some statistics experiments, we gain the experience model with the i.i.d Laplacian distribution:
(17)p(δ)=∏k∏ip(δk(i))=∏k∏i12σk,iexp⁡{-1σk,i|δk(i)|}.In which,δk(i) is the ith element of the residual vector of the kth patch and σk,i is the standard deviation of δk(i).Combining (15), we can obtain the following:
(18)α^y=argmin⁡{12σn2∥y-Dα∥22+1σk,i∑k∑i|δk(i)|}.For a givenη^i(αk=η^i+δk), the optimal sparse coding α can be obtained as follows:
(19)α^y=argmin⁡{∥y-Dα∥22+2σn2σk,i∑k∑i|δk(i)|}.Compared to the regularization in (14), we can set the μ to be the following self-adaptive form:
(20)μk,i=2σn2σk,i.


## 3.1. Nonsubsampling Shearlet Transform

Nonsubsampling Shearlet [15] is a multiscale geometric analytical method advanced by Lim and Kutyniok. It consisted of laplacian pyramid and direction filter bands with multidirections and shift invariant. For its parabola scale principle, Nonsampling Shearlet has excellent performances on capturing geometrical feature and singularity in high-dimension, which makes it widely used in image restoration.


## 3.2. Similarity Measurement

As to the many advantages with Shearlet, we propose a similarity measurement method. Implement the Shearlet transform withl levels and construct the feature vector for each pixel as
(5)V=(sv1,0,…,sv1,ε1,…,svl,0,…,svl,εl)T.Here,εl is the number of subband in lth level and svl,ε is the Shearlet coefficient. With the anisotropy feature, the coefficient for signal is large while the local geometric structure is similar to the basis function. Conversely, the coefficient is small, while the noise has the isotropy feature, so the coefficients are uniform in each primary function. Due to the above two reasons, the vector in (5) has the better antinoise ability, according to which, we take (5) to measure the similarity between the two patches. Suppose the size of patch is 5 × 5, we get the vector in (5) for all the 25 pixels. Then, we construct some subvector Vsub,k generated by the kth dimension of V:
(6)Vsub,k=(V1(k),V2(k),…,V25(k))T.In which, theVi(k) presents the kth element of Vi (i is the order number of the pixel in each patch, i=1,…,25). Suppose Vsub,k1 and Vsub,k2 are from two patches to be measured, we compute the index Si as follows:
(7)Si=exp⁡{-∑k∥Vsub,k1-Vsub,k2∥22vk2}.In which,vk is called shearlet wave coefficient vk=γσk (σk is the coefficient standard deviation with kth sub-band). With the formulation in (6), we can measure the similarity between two patches better than the Euclidean distance of gray in spatial domain.


## 3.3. Nonlocal Dictionary Learning

### 3.3.1. Nonlocal Dictionary Learning

The restoration algorithm consisted of two main parts that are dictionary learning and sparse coding, respectively. In this paper we improve the algorithm with the method for similarity measurement in Section3.2. It is different to the conventional methods that we did not simply select the training patches from different example images to train the dictionary, while we select the nonlocal similar patches from the degraded image we want to restoration. And then, we cluster these patches to train the cluster subdictionary, which is more sufficient to make the universal dictionary better adapt to local geometrical feature than global K-SVD. Besides, the training data in the same cluster is similar to each other, so there is no need to produce an over-completed dictionary. So each subdictionary size is half of the size of corresponding cluster. Now we present the concrete description for learning scheme as follows.Step 1.
Implement the Shearlet transform to the imageY.Step 2.
Construct the Shearlet feature vector according to the formula (5) (The patch size is 5×5).Step 3.
Calculate the standard deviation ofkth subband (σk=(1/N2)∑i=1N2(yi-y-)2) and gain the wave coefficient vk, yi and y- is the shearlet coefficient and the mean value of coefficients; N is the total number of coefficients in kth subband.Step 4.
Cluster the patches by method in [16] with the index Si in formula (6) and then produce the cluster Ωi (i=1,2,…,K is the cluster indicator).Step 5.
Take the patches inΩi as the training data and learning the cluster subdictionary with K-SVD.Step 6.
By cascading all the cluster dictionaries, we can get the universal dictionary for the whole image.With the ability of capturing the local geometrical feature, the patches in the same set are highly similar by their geometry structure, which makes atoms in subdictionary have the strong adaptability to local structure. So, they can sufficiently present the local geometrical feature. Cascaded by all the subdictionaries, the universal dictionary realizes the goal that presents all kinds of features in the whole image.Now we show a simple example to show the advantage of clustering-based dictionary learning. We list a set of training examples:(8)[100,200,0]T,[110*randn(1),120*randn(1),0]T,[100*randn(1),80*randn(1),0]T,[0,150*randn(1),200*randn(1)]T.Here, “randn” means produce a Gaussian stochastic variable, and then, we take the above two groups of training data to learn a dictionary with two atoms. We adopt the proposed algorithm and K-SVD, respectively. Set the Maximum iteration number with KSVD to be 10 and we show the learned dictionary in Table1.Table 1
Learned Dictionary with different methods.
Method
Learned Dictionary
KSVD
[
-
0.5630
-
0.0459
-
0.7995
0.2835
-
0.2096
-
0.9579
]
Proposed algorithm
[
-
0.5375
0
-
0.8432
0.3294
0.0000
-
0.9442
]As can be seen in Table1, the atoms by proposed algorithm have the more similar structure with the training data.


### 3.3.2. Sparse Coding

For improving the coding accuracy, we proposed a novel optimization called coding residual suppression optimization, which is more sufficient thanl1-norm sparse coding. When dictionary is given, the l1-norm sparse coding for original signal can be realized as follows:
(9)α^x=argmin⁡{∥x-Dα∥2+λ∥α∥1}.In the restoration problem, we can only get the observationy. So the sparse coding can be rewritten as
(10)α^y=argmin⁡{∥y-Dα∥2+λ∥α∥1}.Comparing (9) and (10), we can see that if we want to reconstruct x with high accuracy, the coding α^y is expected to be as close as possible to the true sparse coding α^x. So we introduce the residual coding αδ as follows:
(11)αδ=αy-αx.Then we change the object function (10) into the residual suppression form:
(12)α^y=argmin⁡{∥y-Dα∥2+λ∑k∥αk∥1+μ∑k∥αδk∥1},αδk=αk-η^i,
where k is the indicator of kth patch. In addition, we cannot get the true sparse coding practically, so the η^i is a good estimation of the true sparse coding and can be calculated from weighted average of sparse coding of patches in the same cluster; λ and μ are the regularization parameters. If kth patch is from Ωi, we calculate η^i:
(13)η^i=∑pωi,pα^i,p,ωi,p=cexp⁡{-∥x^i-x^i,p∥22}(cisthenormalizationparameter).The second term in optimization equation (12) is used to ensure the local sparsity that only part of atoms are selected for the dictionary. But, in our scheme, we select one subdictionary for each patch in a certain cluster, which means that the coding of another subdictionary is zero. So our scheme guarantees the sparsity naturally; that is, we can move the second term in (12) and rewrite it as follows:
(14)α^y=argmin⁡{∥y-Dα∥2+μ∑k∥αδk∥1}.With (14), we can compact the optimization only with coding residual constraint, which means that the coding from the observed signal by (14) is close to that from the original signal by (9).


### 3.3.3. Scheme Summary

The whole scheme consisted of two-level iterative algorithm; now we present the brief steps as follows.Initial: set the initial imageX^=Y (Y is the degraded image); D(0) is the DCT complete dictionary and calculate the initial sparse coding for each patch with any pursuit algorithm.Outer Loop:(a)
on the (OL)th iteration: learn the dictionaryD(OL) by X^ with the algorithm proposed in Section 3.3.1 (L is the maximum iterative number, OL=1,2…,L);(b)
compute the good estimation set{ηi}i=1,…,K for all the clusters under the D(OL).(c)
Inner Loop:
(i)
for each patch, we get its codingα^y by (14), which can be solved with the method in [17];(ii)
repeat (i) until all the patches are processed;(d)
estimate all the restoration patches byx^=D(OL)α^y;(e)
OL=OL+1, repeat.On one hand, theη^i is more and more approach to the true sparse coding, which makes the residual suppression more sufficient. On the other hand, by alternating the sparse coding and dictionary learning, coding and dictionary are all improved and promote each other.


### 3.3.4. Parameter Selection

In conventional models, the regularization parameter is generally a constant. Hence, for making (14) more sufficient, we give the derivation of self-adaptive regularization parameter μ under the Bayes framework.For written convenience, we takeδ=αk-η^i as the residual coding vector. Under the Bayes framework, the MAP estimation of δ can be computed as
(15)δ=argmax⁡{log⁡(p(δ∣y))}=argmax⁡{log⁡(p(y∣δ))+log⁡(p(δ))}.
And the p(y∣δ) is
(16)p(y∣δ)=p(y∣α,η^)=12πσnexp⁡{-12σn2∥y-Dα∥22},
where σn is the standard deviation of noise.As forp(δ), with some statistics experiments, we gain the experience model with the i.i.d Laplacian distribution:
(17)p(δ)=∏k∏ip(δk(i))=∏k∏i12σk,iexp⁡{-1σk,i|δk(i)|}.In which,δk(i) is the ith element of the residual vector of the kth patch and σk,i is the standard deviation of δk(i).Combining (15), we can obtain the following:
(18)α^y=argmin⁡{12σn2∥y-Dα∥22+1σk,i∑k∑i|δk(i)|}.For a givenη^i(αk=η^i+δk), the optimal sparse coding α can be obtained as follows:
(19)α^y=argmin⁡{∥y-Dα∥22+2σn2σk,i∑k∑i|δk(i)|}.Compared to the regularization in (14), we can set the μ to be the following self-adaptive form:
(20)μk,i=2σn2σk,i.


## 3.3.1. Nonlocal Dictionary Learning

The restoration algorithm consisted of two main parts that are dictionary learning and sparse coding, respectively. In this paper we improve the algorithm with the method for similarity measurement in Section3.2. It is different to the conventional methods that we did not simply select the training patches from different example images to train the dictionary, while we select the nonlocal similar patches from the degraded image we want to restoration. And then, we cluster these patches to train the cluster subdictionary, which is more sufficient to make the universal dictionary better adapt to local geometrical feature than global K-SVD. Besides, the training data in the same cluster is similar to each other, so there is no need to produce an over-completed dictionary. So each subdictionary size is half of the size of corresponding cluster. Now we present the concrete description for learning scheme as follows.Step 1.
Implement the Shearlet transform to the imageY.Step 2.
Construct the Shearlet feature vector according to the formula (5) (The patch size is 5×5).Step 3.
Calculate the standard deviation ofkth subband (σk=(1/N2)∑i=1N2(yi-y-)2) and gain the wave coefficient vk, yi and y- is the shearlet coefficient and the mean value of coefficients; N is the total number of coefficients in kth subband.Step 4.
Cluster the patches by method in [16] with the index Si in formula (6) and then produce the cluster Ωi (i=1,2,…,K is the cluster indicator).Step 5.
Take the patches inΩi as the training data and learning the cluster subdictionary with K-SVD.Step 6.
By cascading all the cluster dictionaries, we can get the universal dictionary for the whole image.With the ability of capturing the local geometrical feature, the patches in the same set are highly similar by their geometry structure, which makes atoms in subdictionary have the strong adaptability to local structure. So, they can sufficiently present the local geometrical feature. Cascaded by all the subdictionaries, the universal dictionary realizes the goal that presents all kinds of features in the whole image.Now we show a simple example to show the advantage of clustering-based dictionary learning. We list a set of training examples:(8)[100,200,0]T,[110*randn(1),120*randn(1),0]T,[100*randn(1),80*randn(1),0]T,[0,150*randn(1),200*randn(1)]T.Here, “randn” means produce a Gaussian stochastic variable, and then, we take the above two groups of training data to learn a dictionary with two atoms. We adopt the proposed algorithm and K-SVD, respectively. Set the Maximum iteration number with KSVD to be 10 and we show the learned dictionary in Table1.Table 1
Learned Dictionary with different methods.
Method
Learned Dictionary
KSVD
[
-
0.5630
-
0.0459
-
0.7995
0.2835
-
0.2096
-
0.9579
]
Proposed algorithm
[
-
0.5375
0
-
0.8432
0.3294
0.0000
-
0.9442
]As can be seen in Table1, the atoms by proposed algorithm have the more similar structure with the training data.


## 3.3.2. Sparse Coding

For improving the coding accuracy, we proposed a novel optimization called coding residual suppression optimization, which is more sufficient thanl1-norm sparse coding. When dictionary is given, the l1-norm sparse coding for original signal can be realized as follows:
(9)α^x=argmin⁡{∥x-Dα∥2+λ∥α∥1}.In the restoration problem, we can only get the observationy. So the sparse coding can be rewritten as
(10)α^y=argmin⁡{∥y-Dα∥2+λ∥α∥1}.Comparing (9) and (10), we can see that if we want to reconstruct x with high accuracy, the coding α^y is expected to be as close as possible to the true sparse coding α^x. So we introduce the residual coding αδ as follows:
(11)αδ=αy-αx.Then we change the object function (10) into the residual suppression form:
(12)α^y=argmin⁡{∥y-Dα∥2+λ∑k∥αk∥1+μ∑k∥αδk∥1},αδk=αk-η^i,
where k is the indicator of kth patch. In addition, we cannot get the true sparse coding practically, so the η^i is a good estimation of the true sparse coding and can be calculated from weighted average of sparse coding of patches in the same cluster; λ and μ are the regularization parameters. If kth patch is from Ωi, we calculate η^i:
(13)η^i=∑pωi,pα^i,p,ωi,p=cexp⁡{-∥x^i-x^i,p∥22}(cisthenormalizationparameter).The second term in optimization equation (12) is used to ensure the local sparsity that only part of atoms are selected for the dictionary. But, in our scheme, we select one subdictionary for each patch in a certain cluster, which means that the coding of another subdictionary is zero. So our scheme guarantees the sparsity naturally; that is, we can move the second term in (12) and rewrite it as follows:
(14)α^y=argmin⁡{∥y-Dα∥2+μ∑k∥αδk∥1}.With (14), we can compact the optimization only with coding residual constraint, which means that the coding from the observed signal by (14) is close to that from the original signal by (9).


## 3.3.3. Scheme Summary

The whole scheme consisted of two-level iterative algorithm; now we present the brief steps as follows.Initial: set the initial imageX^=Y (Y is the degraded image); D(0) is the DCT complete dictionary and calculate the initial sparse coding for each patch with any pursuit algorithm.Outer Loop:(a)
on the (OL)th iteration: learn the dictionaryD(OL) by X^ with the algorithm proposed in Section 3.3.1 (L is the maximum iterative number, OL=1,2…,L);(b)
compute the good estimation set{ηi}i=1,…,K for all the clusters under the D(OL).(c)
Inner Loop:
(i)
for each patch, we get its codingα^y by (14), which can be solved with the method in [17];(ii)
repeat (i) until all the patches are processed;(d)
estimate all the restoration patches byx^=D(OL)α^y;(e)
OL=OL+1, repeat.On one hand, theη^i is more and more approach to the true sparse coding, which makes the residual suppression more sufficient. On the other hand, by alternating the sparse coding and dictionary learning, coding and dictionary are all improved and promote each other.


## 3.3.4. Parameter Selection

In conventional models, the regularization parameter is generally a constant. Hence, for making (14) more sufficient, we give the derivation of self-adaptive regularization parameter μ under the Bayes framework.For written convenience, we takeδ=αk-η^i as the residual coding vector. Under the Bayes framework, the MAP estimation of δ can be computed as
(15)δ=argmax⁡{log⁡(p(δ∣y))}=argmax⁡{log⁡(p(y∣δ))+log⁡(p(δ))}.
And the p(y∣δ) is
(16)p(y∣δ)=p(y∣α,η^)=12πσnexp⁡{-12σn2∥y-Dα∥22},
where σn is the standard deviation of noise.As forp(δ), with some statistics experiments, we gain the experience model with the i.i.d Laplacian distribution:
(17)p(δ)=∏k∏ip(δk(i))=∏k∏i12σk,iexp⁡{-1σk,i|δk(i)|}.In which,δk(i) is the ith element of the residual vector of the kth patch and σk,i is the standard deviation of δk(i).Combining (15), we can obtain the following:
(18)α^y=argmin⁡{12σn2∥y-Dα∥22+1σk,i∑k∑i|δk(i)|}.For a givenη^i(αk=η^i+δk), the optimal sparse coding α can be obtained as follows:
(19)α^y=argmin⁡{∥y-Dα∥22+2σn2σk,i∑k∑i|δk(i)|}.Compared to the regularization in (14), we can set the μ to be the following self-adaptive form:
(20)μk,i=2σn2σk,i.


## 4. Experimental Results and Analysis

To verify the performance of the algorithm proposed in the paper, we show some contrast restoration experiments for image denoising. The contrast algorithms are, respectively, NSCT method in [6], SSBM3D in [18], MK-SVD in [14], and the proposed algorithm in this paper. The noisy image is generated by adding the Gaussian noise with different standard deviation (σ=15,20). The size of test images is all 256 × 256 and we set the parameters as follows.ε
=
3, l=3 (mentioned in Section 3.2); K=50 (mentioned in Section 3.3.1); p=5, (mentioned in Section 3.3.2).To show the objective evaluation for restoration image, we take the PSNR as the indicator for different algorithms. Meanwhile, we show part of the experiment results to view the denoising performance. Supposex and x^ are the original image and restoration image, respectively, the definition of PSNR is
(21)PSNR=10log⁡2552∥x-x^∥22.Figures1 and 2 are the restoration performance with the standard deviation σ=15, while Figures 3 and 4 are the performance with σ=20. As for the other images we only show the PSNR value reported in Tables 2 and 3.Table 2
The PSNR (dB) indicator withσ=15.
Noisy
NSCT
BM3D
K-SVD
Proposed
House
24.89
33.11
34.67
33.92
34.22
Barbara
24.63
30.49
32.33
31.40
31.97
Peppers
24.61
31.51
32.70
31.77
32.16
Bridge
24.70
27.71
28.83
28.55
28.62
Butterfly
24.63
29.17
30.64
29.89
30.18Table 3
The PSNR (dB) indicator withσ=20.
Noisy
NSCT
BM3D
K-SVD
Proposed
House
22.10
31.78
33.76
32.67
32.89
Barbara
22.05
28.95
30.68
29.75
30.19
Peppers
22.09
30.12
31.36
30.46
31.12
Bridge
22.13
26.41
27.25
26.87
27.02
Butterfly
21.11
27.65
29.46
28.32
28.96Restoration performance comparison on house (σ=15).
(a)
Noisy
(b)
Original
(c)
NSCT
(d)
SSBM3D
(e)
MK-SVD
(f)
ProposedRestoration performance comparison on Barbara (σ=15).
(a)
Noisy
(b)
Original
(c)
NSCT
(d)
SSBM3D
(e)
MK-SVD
(f)
ProposedRestoration performance comparison on Bridge (σ=20).
(a)
Noisy
(b)
Original
(c)
NSCT
(d)
SSBM3D
(e)
MK-SVD
(f)
ProposedRestoration performance comparison on Butterfly (σ=20).
(a)
Noisy
(b)
Original
(c)
NSCT
(d)
SSBM3D
(e)
MK-SVD
(f)
ProposedFor each group, by the local detail image, we can get some conclusion. Though all the four methods can achieve the denoising task, there are some differences between each other. For the NSCT method, the ability of capturing structure is not adaptive to different image due to its fixed dictionary. Additionally, some scratches appeared in the restoration results, which did not exist in the original image and the PSNR is lowest among the four methods. Compared to the other method, BM3D shows advantage on PSNR value. But its restoration results are smoothed excessively, which leads to lose much detail texture. Owing to the dictionary that is learned by the random example patches from different images, the K-SVD algorithm generates some visual artifacts and cannot recover the local geometry feature sufficiently. So the restoration results of K-SVD are only better than the NSCT in the four methods. The proposed method in this paper shows advantage both on the restoration performance and PSNR value. Though its PSNR is lower than the BM3D, the detail recovered ability is stronger than the other three methods.


## 5. Conclusion

Owing to that the abundant geometry information and the self-similarity are the important influencers to be utilized in the image restoration by sparse representation, the paper proposed a novel scheme that restores the image by the nonlocal sparse reconstruction with similarity measurement. We cluster the patches from the degraded image by similarity measurement with Shearlet feature vector, which is good at capturing the local geometry structure in image and then take them to train the cluster dictionary and get good estimation of true sparse coding for original image. Additionally, we also show the derivation of regularization parameter under the Bayes framework. By the cluster dictionary learning and the coding residual suppression, the proposed scheme shows advantages both on the visual performance and PSNR value compared to the leading denoising methods. Besides the image denoising, the proposed model can be extensive to other restoration tasks such as deblurring and superresolution.



---

*Source: 586014-2014-03-04.xml*