Image Denoising Method Using the Gradient Matching Pursuit

Image Denoising Method Using the Gradient Matching Pursuit

Ling Tang* Mingju Chen

College of Automation and Electronic Information, Sichuan University of Science & Engineering, Zigong, China

Corresponding Author Email:
| |
| | Citation



Image denoising method based on sparse decomposition means the useful information in the image is taken as the sparse component and noises in the image as the residuals after the removal of sparse component, which is the basis for image denoising. In this paper, a new image denoising algorithm using the gradient matching pursuit is proposed based on the study of image sparse decomposition. It firstly constructs an over complete atomic library in the image, then the optimal atom is found by the sparse decomposition method with gradient tracking. At last reconstruct the image with using the optimal atomic. The simulation results show that the convergence of the improved algorithm is fast and stable, and it can effectively eliminate the noise.


Image denoising, The gradient, Matching pursuit, Sparse decomposition

1. Introduction

In 1993, Zhang and Mallet first mentioned the concept of sparse decomposition, after a year, Mallet found the matching pursuit algorithm to achieve sparse signal decomposition. At present, with the gradual deepening of the study of sparse decomposition, it is not only used in one-dimensional signal, but also has been greatly developed in the two-dimensional image. The image can be decomposed on the over complete dictionary of atoms to find the most matched atomic to reconstruct the image. The atoms can be adapted according to the characteristics of the image, and the image can be expressed by a linear combination of the atoms, which means the sparse representation of the image. Sparse decomposition for image denoising is based on that the basis is useful information can be taken as sparse component, and the noise as the residuals (image information minus the sparse component). The visual effect of this method is better, and do not need the information of noise. At present the most commonly used algorithm for image sparse decomposition is matching pursuit (MP). Considering the complexity and convergence of the algorithm, in this paper we combine the idea of gradient tracking with MP algorithm, and proposes a gradient matching pursuit algorithm which obtains the better denoising effect.

2. Image Sparse Decomposition

Assuming the image is $f$ with the size of $M1\times M2$. If the image is decomposed into a set of complete orthogonal bases, the number of the bases is$M1\times M2$. Due to the orthogonality of the bases, the distribution in the space is sparse. And the energy of the image will be distributed in different groups after the decomposition. The dispersion of this energy distribution is not positive on image processing when represented by a combination of the bases. In order to get the sparse representation of the image, the structure of the bases must be sufficiently dense in the combined space of the image. The orthogonality of the bases is no longer guaranteed, so the base is called an atom. The collection of these atoms are called over complete dictionary. And the results of the decomposition of the image in the over complete dictionary must be sparse.

Consider $D={{\left\{ {{g}_{\gamma }} \right\}}_{\gamma \in \Gamma }}$ is over complete dictionary, ${{g}_{\gamma }}$ is the atom defined by a parameter group$\gamma $. With different methods to construct atoms, the parameters and the number  of the parameters in the sets $\gamma $ are not the same. Atoms should be normalized as $\left\| {{g}_{\gamma }} \right\|=1$.$\Gamma $ is the sets of $\gamma $. In this paper, the Gabor atom is used as the basis function which is composed by the Gauss window function modulated:

${{g}_{\gamma }}(t)=\frac{1}{\sqrt{s}}g(\frac{t-u}{s}){{e}^{(j\xi t+w)}}$             (1)

where $g(t)={{e}^{-\text{ }\!\!\pi\!\!\text{ }{{t}^{2}}}}$ is the Gauss window function, $\gamma =(s,u,\xi ,w)$ is the time frequency parameter.

One-dimensional form of the basis function can be given by the following formula:

${{g}_{\gamma }}(t)=\frac{1}{\sqrt{s}}g(\frac{t-\frac{N}{2}-1}{s})\cos (\frac{2\pi \xi (t-\frac{N}{2}-1)}{s}+\omega )$           (2)

where, N is the length of the basis function.

According to the image $f$ to be decomposed, select the best matching atom from the over complete dictionary, and meet the following conditions:

$\left| \left\langle f,{{g}_{{{\gamma }_{0}}}}(t) \right\rangle  \right|=\underset{\gamma \in \Gamma }{\mathop \sup }\,\left| \left\langle f,{{g}_{\gamma }}(t) \right\rangle  \right|$        (3)

Thus the weighted coefficient of the atom is the inner product of matching image and best atom: ${{P}_{0}}=\left\langle f,{{g}_{{{\gamma }_{0}}}}(t) \right\rangle $. The original image after the first decomposition can be expressed as $f={{P}_{0}}{{g}_{{{\gamma }_{0}}}}(t)+{{R}_{1}}f$(${{R}_{1}}f$ is the residual). After the decomposition of N times, the final form of the image can be obtained:

$f=\sum\limits_{n=1}^{K}{{{P}_{n}}{{g}_{{{\gamma }_{n}}}}(t)}+{{R}_{n}}f$         (4)

where $K$ is the number of iterations. The first item is the extracted denoised image which is ${{f}_{\_recon}}=\sum\limits_{n=1}^{K}{{{P}_{n}}{{g}_{{{\gamma }_{n}}}}(t)}$. The second item${{R}_{n}}f$ is identified as the noise eliminated from the original image, so as to increase the output signal to noise ratio.

3. Denosing Method Based on Gradient Matching Pursuit

3.1 Image matching pursuit

In the literature[7], a denoising method using gradient tracking is proposed, which can converge faster with small computational complexity.

During the N iterations the main parameters need to be extracted from the image step by step, so as to update the residual${{R}_{n}}f$. In gradient tracking, image decomposition is achieved by minimizing twice cost function, which can be expressed as:

${{y}_{n}}={{y}_{n-1}}+{{a}_{n}}{{d}_{n}}$                          (5)

where, ${{d}_{n}}$ is the updated direction, that is the gradient; ${{a}_{n}}$is the updated step. Consider ${{d}_{n}}$ is the gradient of the cost function in the direction of vector $y$, which can be given by the following formula:                        

${{d}_{n}}=\left\langle {{g}_{{{\gamma }_{n}}}},y-\left\langle {{g}_{{{\gamma }_{n}},}}{{y}_{n-1}} \right\rangle  \right\rangle $                  (6)

The updated step ${{a}_{n}}$ is calculated from ${{d}_{n}}$,                 

${{a}_{n}}=\frac{\left\langle {{R}_{n}}f,{{c}_{n}} \right\rangle }{\left\| {{c}_{n}} \right\|_{2}^{2}}$                    (7)

where, ${{c}_{n}}=\left\langle {{g}_{{{\gamma }_{n}}}},{{d}_{n}} \right\rangle $

Combining the above gradient tracking with the matching pursuit algorithm, the basic flow of the denoising method based on the gradient matching pursuit is:

1) Initialize ${{r}_{0}}=f$, ${{y}_{0}}=0$;

2) Set the threshold$\delta $, with the recycling process: $n=1,2,\cdots ,K$

1.Calculate the maximum projection ${{P}_{n}}=\underset{{{g}_{{{\gamma }_{n}}}}}{\mathop{\sup }}\,\left| \left\langle {{r}_{0}},{{g}_{{{\gamma }_{n}}}} \right\rangle  \right|$ on the direction of the atoms and the optimal atom ${{g}_{{{\gamma }_{0}}}}$

2. Calculate ${{d}_{n}}$, ${{c}_{n}}=\left\langle {{g}_{{{\gamma }_{n}}}},{{d}_{n}} \right\rangle $

3. Update the step ${{a}_{n}}=\frac{\left\langle {{r}_{n}},{{c}_{n}} \right\rangle }{\left\| {{c}_{n}} \right\|_{2}^{2}}$

4. As${{y}_{n}}={{y}_{n-1}}+{{a}_{n}}{{d}_{n}}$, ${{r}_{n}}={{r}_{n-1}}-{{a}_{n}}{{d}_{n}}$, then output${{y}_{n}}$,${{r}_{n}}$

5. Determine whether the condition value  reaches to$\delta $or not.

3) The denoised image is ${{f}_{\_recon}}={{y}_{n}}$, Residual${{r}_{n}}$can be identified as the eliminated noise.

3.2 Assumption for iterative decomposition terminated

In the sparse decomposition process, the residual image can be expressed as:

$Rf=f-{{f}_{\_recon}}$               (8)

With the process of the standard deviation ${{\delta }_{Rf}}$ in $Rf$ changed, it can be found that ${{\delta }_{Rf}}$ will gradually decrease with the increase of the number of iterations. After reaching a certain minimum ${{\delta }_{\min }}$, it tends to be a stable value (in fact, the standard deviation ${{\delta }_{{{f}_{n}}}}$ of the noise).

Figure 1. The curve of signal residual $\delta $             

Therefore, we can identify that when $\delta ={{\delta }_{\min }}$ the signal to noise ratio has a maximum value:                

$SN{{R}_{\max }}=20\log 10(\frac{{{\left\| f \right\|}^{2}}}{{{\left\| f-{{f}_{\_recon}} \right\|}^{2}}})$                    (9)

Calculate the energy ratio of the signal residual and the reconstructed signal, and the ratio is defined as follows:

         $\sigma =\frac{{{\left\| f-{{f}_{\_recon}} \right\|}^{2}}}{{{\left\| f \right\|}^{2}}}$                           (10)

If the value meets ${{\sigma }_{i+1}}-{{\sigma }_{i}}<{{\delta }_{i}}$ at twice(${{\delta }_{i}}$ is the threshold for the iterative termination)or the value of $\sigma$ is less than the threshold value, the main energy of the image signal decomposition is completed, and the reconstructed image ${{f}_{\_recon}}$ is the denoised image.

4. Experiment and Result Analysis

Lena image with the size of 256×256 is used in the experiment. Adding Gauss noise in the image, then compare MP algorithm with the gradient MP algorithm proposed in this paper for the denosing effect. In this paper, the non symmetric atomic dictionary is used as the over-complete dictionary.

1. Energy ratio $\sigma $ changes with the iterations.

Consider 100 iterations, and the variation of the energy ratio $\sigma$ with the iteration number is observed, as shown in Figure 2.

Figure 2. Energy ratio $\sigma$ changes with the iterations

It is obvious that the iterations reach to a certain, the change of energy ratio $\sigma$ tends to be gentle, which can be determined that the main energy component of the image signal is decomposed completely, thus the denoised image can be obtained. With many experiments, the threshold  for ending the sparse decomposition is generally 0.03. By setting the threshold, the gradient MP denoising method can be used for iterations and reconstruction, so as to achieve the denosing image.

2. Denosing effect of the image adding Gauss noise

Figure 3 is Lean original image, adding Gauss noise with standard deviation of 10 and 30. Figure 4 is the processing results using two different methods.

Figure 3. Lena original image

According to Figure 4-5, the gradient MP algorithm proposed in this paper can remove the noise in the image better, recover the main structural features of the original image well. With the increase of the variance of Gauss noise, the denoisng effect of two algorithms is decreased, but the  proposed algorithm varies less.

Figure 4. Lena image denoising renderings using different methods when standard deviation is 10

Figure 5. Lena image denoising renderings using different methods when standard deviation is 30

3. Comparison analysis of the denoising effect

Consider Gauss white noise with the same type and intensity (standard deviation is 10), the performance of the proposed algorithm and MP algorithm is compared in table 1.

Table 1. Denoising effect comparison









The proposed




From the table 1, we can see that the algorithm can get a higher PSNR and smaller MSE, so the denoising effect is better. And through CPU running time for 50 images denoising (the data is the average of 10 times experiments) , the proposed method has shorter running time than MP algorithm, which confirms that the new algorithm can effectively improve the efficiency of sparse decomposition.

5. Conclusions

Image denoising based on sparse decomposition means decomposing the noisy image into sparse components and the other components. The sparse component corresponds to the useful information of the image, while the other components correspond to the noise in the image. Noise can be effectively removed from the image through reconstructing image by the sparse component. Based on the commonly existing algorithms, we proposes the gradient MP algorithm in this paper. The efficiency of sparse decomposition is effectively improved. To a certain extent, it improves the values of  PSNR, which confirms the better denoising effect.


This work was supported by projects of Sichuan Provincial Department of Education (13ZB0138), projects of Artificial Intelligence Key Laboratory of Sichuan Province (2013RYY02), and projects of Sichuan University of Science & Engineering Teaching Reform (JG-1625).


[1] Mallet S. and Zhang Z., “Matching pursuit with time-frequency dictionaries.” IEEE Trans. On Signal Processing, vol. 41, no. 12, pp. 3397-3415, 1993. DOI: 10.1109/78.258082

[2] Bergeau F. and Mallet S., “Matching pursuit of image,” Proceedings of IEEE-SP, Piladephia, 1994.

[3] YIN Zhong-ke, XIE Mei and WANG Jian-ying, “Image Denoising Based on Its Sparse Decomposition,” Journal of University of Electronic Science and Technology of China, vol. 35, no. 6, pp. 876-878, 2006.

[4] Wang Xiu-ying, Sparse Decomposition Research in Image Denoising, Anhui university, 2014.

[5] LI Heng-jian, ZHANG Jia-shu and CHEN Huai-xin, “A fast image denoising method based on space decomposition,” Acta Photonica Sinica, vol. 38, no. 11, pp. 3009-3015, 2009.

[6] Rauhut H., Schnass K. and Vandergheynst P., “Compressed sensing and redundant dictionaries,” IEEE Transactions on Information Theory, vol. 54, no. 5, pp. 2210-2219, 2008. DOI: 10.1109/TIT.2008.920190.