# Image Denoising Algorithm Combined with SGK Dictionary Learning and Principal Component Analysis Noise Estimation

Authors: Wenjing Zhao; Yue Chi; Yatong Zhou; Cheng Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

SGK (sequential generalization ofK-means) dictionary learning denoising algorithm has the characteristics of fast denoising speed and excellent denoising performance. However, the noise standard deviation must be known in advance when using SGK algorithm to process the image. This paper presents a denoising algorithm combined with SGK dictionary learning and the principal component analysis (PCA) noise estimation. At first, the noise standard deviation of the image is estimated by using the PCA noise estimation algorithm. And then it is used for SGK dictionary learning algorithm. Experimental results show the following: (1) The SGK algorithm has the best denoising performance compared with the other three dictionary learning algorithms. (2) The SGK algorithm combined with PCA is superior to the SGK algorithm combined with other noise estimation algorithms. (3) Compared with the original SGK algorithm, the proposed algorithm has higher PSNR and better denoising performance.


---

## Body

## 1. Introduction

In the image acquisition and transmission, noise is inevitably carried, which will reduce image quality, so image denoising has a very important significance. Image denoising algorithms can be divided into space domain denoising and frequency domain denoising. The former includes the mean filtering, median filtering, and Wiener filtering. The latter includes Fourier transform [1], Laplace transform [2], and wavelet transform [3]. A series of postwavelet multiscale tools have been developed based on the wavelet theory to filter noise effectively such as curvelet [4], directionlet [5], bandelet [6], and shearlet [7].In recent years, there are some novel denoising algorithms such as nonlocal mean [8] denoising, Gaussian mixture model denoising [9], and dictionary learning denoising [10] based on sparse representation [11]. An image denoising method based on wavelet and SVD transforms improves denoising performance [12]. Moreover, K-singular value decomposition (K-SVD) [13] based on overcomplete sparse representation has recently been the subject of intense research activity within the denoising community [14, 15]. However, K-SVD increases the iteration number when dealing with large data. So Sujit proposed the SGK [13] dictionary learning algorithm in 2013, which not only overcomes the drawbacks of ordinary dictionary learning that breaks the sparse coefficient structure but also can be applied to a variety of sparse representations, with the low complexity and fast calculation ability [10].At present, many image denoising algorithms need to foreknow the noise standard deviation [16], but it is usually unknown in practice. So the noise estimation has been developed in the image denoising community. The classic image filtering in [17] estimates the noise standard deviation by the convolution of image and filter. The DCT of the image patch [18] concentrates the image structure in the low frequency coefficient region, so that the noise estimation can be performed by the high frequency coefficient. It is also common to estimate noise level by the grayscale value of the image [19]. Patch-based local variance [20] generally estimates noise level by robust statistical algorithms. The Bayesian contraction algorithm [21] is used to denoise the image and analyze the autocorrelation of residuals in the range of noise standard deviation to find the true value. The distribution of the sideband filter response [22] can be divided into two parts according to the difference of the image and noise, which is calculated by the expected maximization [23]. The kurtosis of the edge sideband filter response distribution [24] is constant for the noisy image, and a kurtosis model can be established and the noise standard deviation can be evaluated by finding the best parameters of the model. However, the above algorithms mostly assume that the image is uniform. For images with abundant textures, Pyatykh et al. [25] proposed PCA noise estimation based on the data patch, where the noise standard deviation can be estimated as the minimum eigenvalue of the image patch covariance matrix.Based on the above considerations, a denoising algorithm combined with SGK dictionary learning and PCA noise estimation is proposed. Firstly, the image with additive Gaussian white noise is segmented, and the noise level is estimated by calculating the minimum eigenvalue of the image patch covariance matrix. Then the estimated noise standard deviation is entered into SGK dictionary learning algorithm to denoise the image. During the denoising process, each image patch is sparse and the sparse representation coefficient is calculated by pursuit algorithm. The dictionary atom is updated with the sparse representation coefficient; therefore a more accurate approximation of the image patch is obtained. The experimental results show that the proposed algorithm is superior to other algorithms in noise level estimation and has better denoising performance.


## 2. SGK Dictionary Learning Denoising Algorithm

### 2.1. Image Denoising Problem and SGK Dictionary Learning

SGK dictionary learning algorithm is a generalization of theK-means clustering. It mainly consists of two stages: sparse coding stage and dictionary update stage when using SGK dictionary learning algorithm to perform denoising [13], and the flow chart is shown in Figure 1. SGK algorithm firstly processes image through the original DCT dictionary and then updates dictionary with the sparse representation coefficient. Each local patch extracted in the image is sparse-coded by new training dictionary to achieve the denoising performance.Figure 1
SGK algorithm denoising flow chart.


### 2.2. Sparse Coding Stage

For an imageA of sizeT×T added to additive white Gaussian noise W∈RT×T, it constitutes a noisy image B:(1)B=A+W.Assume that the dictionaryD∈Rt×l consists of image atoms dl∈Rt, where l=1,2,…,L. Qij represents a t×T matrix that extracts patches of size t×t in image A, which is ∀ijQijA∈Rt. For each local patch, the sparse representation a=QijA can be represented by a dictionary D:(2)β^=arg⁡minβηβ0+Dβ-a22.For any patch in the image,(3)β^ij=arg⁡minβijηijβij0+Dβij-QijA22∀ij.Therefore the global image representation is shown as(4)A^,β^ij=arg⁡minA,βijρB-A2+∑ijηijβij0+∑ijDβij-QijA2.For the solution of (4), βij can be obtained by (3), and then B is represented as sparse approximation of A by choosing appropriate ηij, so it can be obtained as(5)β^ij=argminβijβij0s.t.QijB-Dβij22≤Cσ2∀ij.


### 2.3. Dictionary Update Stage

In the dictionary update stage, updating each image’s atoms sequentially can minimize sparse representation error, which is denoted as(6)gij=QijA-Dβij=QijA-∑rdmβijr.In (6), βij(r) is the rth component of βij. And the error matrix G is composed of all these elements gij. So the error of the image patch dl can be expressed as(7)gijl=QijA-∑r≠ldmαijr=gij+dlαijl.All thesegijl form the error matrix Gl and also form vector βl containing corresponding βij(l), so it has(8)Gl=E+dlβl⟹GF2=Gl-dlβlF2.And·F is Frobenius norm in (8). According to the sequential generalization of K-means [12], the solution of (8) is(9)dlt+1=arg⁡mindlGF2=arg⁡mindl⁡Gl-dlβlF2.The closed-form solution of (9) is(10)d^l=GlβlTβlβlT-1.It replaces all atoms withd=d^l and SGK training dictionary D^ is used to obtain the final sparse representation of the component β^ij for each extracted local patch. A^ is obtained as(11)A^=arg⁡minAρB-A2+∑ijDβ^ij-QijA2.The final solution of the sparse representation error minimization problem is(12)A^=λIN+∑ijQijTQij-1λB+∑ijQijTDβ^ij.


## 2.1. Image Denoising Problem and SGK Dictionary Learning

SGK dictionary learning algorithm is a generalization of theK-means clustering. It mainly consists of two stages: sparse coding stage and dictionary update stage when using SGK dictionary learning algorithm to perform denoising [13], and the flow chart is shown in Figure 1. SGK algorithm firstly processes image through the original DCT dictionary and then updates dictionary with the sparse representation coefficient. Each local patch extracted in the image is sparse-coded by new training dictionary to achieve the denoising performance.Figure 1
SGK algorithm denoising flow chart.


## 2.2. Sparse Coding Stage

For an imageA of sizeT×T added to additive white Gaussian noise W∈RT×T, it constitutes a noisy image B:(1)B=A+W.Assume that the dictionaryD∈Rt×l consists of image atoms dl∈Rt, where l=1,2,…,L. Qij represents a t×T matrix that extracts patches of size t×t in image A, which is ∀ijQijA∈Rt. For each local patch, the sparse representation a=QijA can be represented by a dictionary D:(2)β^=arg⁡minβηβ0+Dβ-a22.For any patch in the image,(3)β^ij=arg⁡minβijηijβij0+Dβij-QijA22∀ij.Therefore the global image representation is shown as(4)A^,β^ij=arg⁡minA,βijρB-A2+∑ijηijβij0+∑ijDβij-QijA2.For the solution of (4), βij can be obtained by (3), and then B is represented as sparse approximation of A by choosing appropriate ηij, so it can be obtained as(5)β^ij=argminβijβij0s.t.QijB-Dβij22≤Cσ2∀ij.


## 2.3. Dictionary Update Stage

In the dictionary update stage, updating each image’s atoms sequentially can minimize sparse representation error, which is denoted as(6)gij=QijA-Dβij=QijA-∑rdmβijr.In (6), βij(r) is the rth component of βij. And the error matrix G is composed of all these elements gij. So the error of the image patch dl can be expressed as(7)gijl=QijA-∑r≠ldmαijr=gij+dlαijl.All thesegijl form the error matrix Gl and also form vector βl containing corresponding βij(l), so it has(8)Gl=E+dlβl⟹GF2=Gl-dlβlF2.And·F is Frobenius norm in (8). According to the sequential generalization of K-means [12], the solution of (8) is(9)dlt+1=arg⁡mindlGF2=arg⁡mindl⁡Gl-dlβlF2.The closed-form solution of (9) is(10)d^l=GlβlTβlβlT-1.It replaces all atoms withd=d^l and SGK training dictionary D^ is used to obtain the final sparse representation of the component β^ij for each extracted local patch. A^ is obtained as(11)A^=arg⁡minAρB-A2+∑ijDβ^ij-QijA2.The final solution of the sparse representation error minimization problem is(12)A^=λIN+∑ijQijTQij-1λB+∑ijQijTDβ^ij.


## 3. Noise Estimation Theory

### 3.1. Noise Estimation Theory Based on PCA

Suppose thatA is a clean image with size of T×T, and Β represents an image with additive white Gaussian noise W. The noise variance is unknown, so it needs to be estimated. For A, B, and W, each image contains H=(T-M+1)(T-M+1) patches with size M=M×M. Since W is the independent additive white Gaussian noise, there is W~NM(0,σ2I) and cov(A,W)=0.Suppose thatJA and JB are, respectively, the sample covariance matrices of A and B. Meanwhile, μ~A,1≥μ~A,2≥⋯≥μ~A,M are the eigenvalues of JA, and the corresponding eigenvectors are W~A,1,…,W~A,M. Similarly, μ~B,1≥μ~B,2≥⋯≥μ~B,M are the eigenvalues of JB, and corresponding eigenvectors are W~B,1,…,W~B,M.W~B,1TB,…,W~B,MTB represent the sample principal component of B [26], and S2 represents the sample variance, so it is shown as follows:(13)S2W~B,kTB=μ~B,k,k=1,2,…,M,where S2 represents the sample variance.In order to apply PCA to noise variance estimation, it defines positive integerc. The clean image A satisfies Ai∈WM-c⊂RM, and its dimension M-c is less than the number of coordinates M. So there is(14)Eμ~B,h-σ2=Oσ2H,H⟶∞.And it is held for allh=M-c+1,…,M. When considering the overall principal component, cov(A,W)=0 represents ∑B=∑A+∑W, where ∑B, ∑A, and ∑W, respectively, represent the overall covariance matrices ofB,A, andW. Meanwhile, the minimum eigenvalues of ∑W=σ2I and ∑A are zero, so the minimum eigenvalue of ∑B is σ2. With the sample size N tending to infinity, it meets(15)limN→∞⁡Eμ~B,M-σ2=0,which represents the fact thatμ~B,M converges to σ2, so the noise variance can be estimated as μ~B,M and it is a consistent estimation of the noise level.If the above assumptions hold, the expected values ofμ~B,M-c+1-μ~B,M can be calculated from the trigonometric inequality and (15):(16)Eμ~B,M-c+1-μ~B,M=Oσ2H.The condition of (16) is(17)μ~B,M-c+1-μ~B,M<Tσ2H,where T is a fixed value and it satisfies T>0.For the estimation of noise varianceσest2, it can be verified by (17). If (17) holds, σest2 is the final estimation. But if (17) cannot hold, it is necessary to extract a subset of the image patches with a small standard deviation. Performing noise estimation again to satisfy (17) is satisfied until the final noise estimation is obtained.


### 3.2. Estimate the Noise Level Based on PCA: An Example

Figure2 is a PCA noise estimation example of the house image. Figure 2(a) is the house image, and Figure 2(b) shows the noise estimation results under the different noise standard deviation. It can be seen that the PCA noise estimation value is very close to the true value.Figure 2
Noise estimation based on principal component analysis.
(a)
House image (b)
Noise level estimation results


## 3.1. Noise Estimation Theory Based on PCA

Suppose thatA is a clean image with size of T×T, and Β represents an image with additive white Gaussian noise W. The noise variance is unknown, so it needs to be estimated. For A, B, and W, each image contains H=(T-M+1)(T-M+1) patches with size M=M×M. Since W is the independent additive white Gaussian noise, there is W~NM(0,σ2I) and cov(A,W)=0.Suppose thatJA and JB are, respectively, the sample covariance matrices of A and B. Meanwhile, μ~A,1≥μ~A,2≥⋯≥μ~A,M are the eigenvalues of JA, and the corresponding eigenvectors are W~A,1,…,W~A,M. Similarly, μ~B,1≥μ~B,2≥⋯≥μ~B,M are the eigenvalues of JB, and corresponding eigenvectors are W~B,1,…,W~B,M.W~B,1TB,…,W~B,MTB represent the sample principal component of B [26], and S2 represents the sample variance, so it is shown as follows:(13)S2W~B,kTB=μ~B,k,k=1,2,…,M,where S2 represents the sample variance.In order to apply PCA to noise variance estimation, it defines positive integerc. The clean image A satisfies Ai∈WM-c⊂RM, and its dimension M-c is less than the number of coordinates M. So there is(14)Eμ~B,h-σ2=Oσ2H,H⟶∞.And it is held for allh=M-c+1,…,M. When considering the overall principal component, cov(A,W)=0 represents ∑B=∑A+∑W, where ∑B, ∑A, and ∑W, respectively, represent the overall covariance matrices ofB,A, andW. Meanwhile, the minimum eigenvalues of ∑W=σ2I and ∑A are zero, so the minimum eigenvalue of ∑B is σ2. With the sample size N tending to infinity, it meets(15)limN→∞⁡Eμ~B,M-σ2=0,which represents the fact thatμ~B,M converges to σ2, so the noise variance can be estimated as μ~B,M and it is a consistent estimation of the noise level.If the above assumptions hold, the expected values ofμ~B,M-c+1-μ~B,M can be calculated from the trigonometric inequality and (15):(16)Eμ~B,M-c+1-μ~B,M=Oσ2H.The condition of (16) is(17)μ~B,M-c+1-μ~B,M<Tσ2H,where T is a fixed value and it satisfies T>0.For the estimation of noise varianceσest2, it can be verified by (17). If (17) holds, σest2 is the final estimation. But if (17) cannot hold, it is necessary to extract a subset of the image patches with a small standard deviation. Performing noise estimation again to satisfy (17) is satisfied until the final noise estimation is obtained.


## 3.2. Estimate the Noise Level Based on PCA: An Example

Figure2 is a PCA noise estimation example of the house image. Figure 2(a) is the house image, and Figure 2(b) shows the noise estimation results under the different noise standard deviation. It can be seen that the PCA noise estimation value is very close to the true value.Figure 2
Noise estimation based on principal component analysis.
(a)
House image (b)
Noise level estimation results


## 4. Experimental Results’ Analysis

The standard Kodak Photo CD benchmark was used to evaluate the performance of denoising algorithm. The size of some images is256∗256, and the size of other images is 512∗512. The patches sizes of all images are 8 × 8.


### 4.1. Comparison of Four Dictionary Learning Denoising Algorithms

We conduct experiments for image denoising by using SGK, DCT, Global, K-SVD dictionary learning algorithms, and BM3D algorithms. The similarity of the first four algorithms is to build a dictionary and then use the dictionary to denoise. DCT algorithm denoises an image by sparsely representing each block with the overcomplete DCT dictionary, thus averaging the represented parts [11]. Global algorithm denoises an image by training a dictionary on patches from the noisy image, sparsely representing each block with this dictionary and averaging the represented parts [11]. K-SVD algorithm uses DCT dictionary to initialize and then uses singular value decomposition for dictionary updating [11]. BM3D algorithm is an image signal denoising method based on transform domain enhancement sparse representation [26].Throughout this experiment, we use SGK, DCT, Global, K-SVD, and BM3D algorithms to denoise the Barbara image withσ=25 as an example. As shown in Figures 3(b)–3(f), the denoising results of five different algorithms are basically the same, and the image’s details are basically well preserved. In the following, we do quantitative comparisons between five algorithms, and the experimental data is shown in Table 1. The PSNR of the SGK is similar to that of K-SVD, and it is superior to Global, DCT, and BM3D algorithms. Encouragingly, we see that SGK runs much faster than K-SVD. As to the value of MSE, SGK is smaller than Global, DCT, and BM3D algorithms. With all the above-mentioned results, the denoising supremacy of SGK over the rest algorithms is demonstrated.Table 1
Image denoising results of five dictionary learning algorithms.
Algorithms Time/s PSNR/dB MSE SGK 17.378 32.077 77.470 DCT 83.884 31.079 113.873 Global 100.479 31.734 89.435 K-SVD 284.181 32.171 72.383 BM3D 12.256 30.717 119.478Figure 3
Using five kinds of dictionary learning algorithm for image denoising.
(a)
Original Barbara image (b)
SGK denoised image (c)
DCT denoised image (d)
Global denoised image (e)
K-SVD denoised image (f)
BM3D denoised image


### 4.2. Comparison of SGK Combined with Different Noise Estimation Algorithms

In order to analyze the sensitivity of SGK algorithm to the noise level, the noise standard deviation is set asσ=5,10,15,20,25, respectively. SGK algorithm is used to denoise the Peppers image with different noise standard deviation.Figure4 shows the denoising experiment’s results using the SGK algorithm with different offsets. The five different colors curves, respectively, represent the case where the PSNR varies with the noise offsets if the noise standard deviation is given. It can be found in Figure 4 that the PSNR of denoised image is basically invariant when the noise standard deviation has negative offset of 0~−5% and the forward offset of 0~+5%. When the offset of noise standard deviation continues to increase, it shows a significant downward trend in −5%~−25% of the negative offset and 5% to 25% of forward offset, which indicates that the image’s PSNR is significantly reduced. Therefore the PSNR would be changed when the noise standard deviation has negative or forward offset, which shows that the SGK algorithm is sensitive to the offsets of the noise standard deviation. So it is necessary to estimate noise level before image denoising. If the estimated noise level is close to the true noise, the denoising results will be more accurate.Figure 4
SGK denoising performance with different noise offset.In order to analyze the performances of SGK dictionary denoising combined with different noise estimation algorithms, this paper also introduces four noise estimation algorithms: Kurtosis [25], local standard deviation distribution mode (Mode) [27], local standard deviation (Med) [27], and local standard deviation minimum (Min) [27].Kurtosis assumes that the corresponding distribution of the kurtosis edge bandpass filter should be a constant for the noise-free images. However, the kurtosis at the entire scale of a noisy image may vary. Under this assumption, the noise standard deviation can be estimated by the kurtosis model.Mode can divide image and the noise standard deviation is estimated according to the distribution pattern of the image’s local standard deviation. As the variance of noise is constant throughout the picture, it will affect every local variance value equally. As a result, the maximum of the bell-shaped distribution will reflect the local variance of the degraded image within homogeneous areas. This value is the mode of the distribution, and it is very close to the mode, so we can use the mode to estimate it.Med estimates noise standard deviation based on the median of the image’s local standard deviation. If practical difficulties to properly estimate the mode arise, it may be useful to use the median operator instead, due to its greater simplicity and the fact that both parameters, albeit different, are not far apart in practice. So an alternative estimation procedure can be done.Min estimates the noise standard deviation based on the minimum value of the local standard deviation of the images. Within a uniform area, the variance of the degraded image equals the variance of noise. According to the previous statement, one straightforward way to estimate standard deviation is to calculate the variance within homogeneous regions, where the variance of the original image is close to zero.The above noise estimation algorithms are all combined with the SGK dictionary learning algorithm in this paper. Now we combine the five noise estimation algorithms mentioned above with SGK, respectively. The combined algorithms are referred to as PCA + SGK, Kurtosis + SGK, Mode + SGK, Med + SGK, and Min + SGK. Figure5 shows the denoising results of the Lena image, where the noise standard deviation is set to σ=15. Analysis of Figure 5 leads to the following observation: the denoising performance of Mode + SGK in Figure 5(d) is slightly the worst, while the remaining four algorithms are basically the same. They all retain the details of the image in the denoising process.Figure 5
Comparison of five kinds of algorithms.
(a)
Original Lena image (b)
PCA + SGK (c)
Kurtosis + SGK (d)
Mode + SGK (e)
Med + SGK (f)
Min + SGKIn order to analyze the denoising performance of five algorithms quantitatively, additive Gaussian white noise images withσ=2,5,10,20,30,40 are, respectively, denoised and compared in Table 2. The best results are shown in boldface. Experiments performed on noisy Lena image indicate that the proposed algorithm outperforms, in terms of estimation accuracy |σest-σ|, estimation time, PSNR, and MSE, the four existing algorithms.Table 2
Denoising indicators on SGK combined with five noise estimation algorithms.
σ Algorithms σ e s t σ e s t - σ σ e s t - σ Time/s PSNR/dB MSE σ = 2 PCA + SGK 2.733 +0.733 0.733 1.799 43.385 2.983 Kurtosis + SGK 2.841 +0.841 0.841 4.699 43.378 2.987 Mode + SGK 2.768 +0.768 0.768 0.070 43.222 3.010 Med + SGK 4.063 +2.063 2.063 0.051 41.811 4.286 Min + SGK 0.496 −1.504 1.504 0.037 42.119 3.993  σ = 5 PCA + SGK 5.510 +0.510 0.510 1.829 38.383 9.436 Kurtosis + SGK 5.166 +0.166 0.166 5.865 38.302 9.614 Mode + SGK 4.480 −0.520 0.520 0.091 38.139 9.981 Med + SGK 6.194 +1.194 1.194 0.047 38.251 9.727 Min + SGK 0.674 −4.326 4.326 0.035 34.175 24.865  σ = 10 PCA + SGK 10.342 +0.342 0.342 1.604 35.177 19.201 Kurtosis + SGK 9.576 +0.424 0.424 4.848 34.795 21.559 Mode + SGK 8.809 +1.191 1.191 0.090 34.074 25.447 Med + SGK 10.463 +0.463 0.463 0.051 35.149 19.869 Min + SGK 1.640 −18.360 18.360 0.037 28.244 97.417  σ = 15 PCA + SGK 15.153 +0.147 0.147 1.995 34.269 30.632 Kurtosis + SGK 14.196 +0.804 0.804 5.208 33.899 30.760 Mode + SGK 12.494 +2.506 2.506 0.084 31.381 47.311 Med + SGK 14.838 −0.162 0.162 0.082 33.221 30.971 Min + SGK 1.807 −13.193 13.193 0.029 28.274 96.766  σ = 20 PCA + SGK 20.071 +0.071 0.071 1.618 31.911 41.876 Kurtosis + SGK 18.943 −1.057 1.057 4.818 31.574 45.256 Mode + SGK 17.038 −2.963 2.963 0.094 30.186 62.300 Med + SGK 19.319 −0.681 0.681 0.055 31.777 43.193 Min + SGK 1.877 −18.123 18.123 0.028 22.152 396.153  σ = 30 PCA+SGK 29.672 −0.328 0.328 1.393 29.917 66.286 Kurtosis + SGK 28.480 −1.520 1.520 5.126 29.724 69.292 Mode + SGK 23.356 −6.644 6.644 0.084 29.044 161.709 Med + SGK 28.199 −1.801 1.801 0.054 29.614 71.074 Min + SGK 3.292 −26.708 26.708 0.029 18.675 882.180  σ = 40 PCA + SGK 39.546 −0.454 0.454 1.865 28.371 94.630 Kurtosis + SGK 38.238 −1.762 1.762 5.134 28.305 96.062 Mode + SGK 33.463 −6.537 6.537 0.087 25.813 170.526 Med + SGK 37.068 −2.932 2.932 0.053 27.910 105.212 Min + SGK 5.385 −34.615 34.615 0.034 16.222 1152.049Figure6 illustrates the performance of algorithms more intuitively varying with standard deviation. Figure 6(a) shows variation of noise estimation absolute error with the noise standard deviation. It can be seen that PCA + SGK has the least value, which is superior to the other four algorithms. So the estimation of PCA + SGK is the most accurate. Figure 6(b) shows the variation of the noise estimation time with the noise standard deviation. For the noise estimation time, Mode + SGK, Med + SGK, and Min + SGK are the least accurate, followed by PCA + SGK and Kurtosis + SGK. Figure 6(c) shows the variation of PSNR with the noise standard deviation. With the increase of standard deviation, PCA + SGK and Kurtosis + SGK keep the PSNR higher, followed by Med + SGK and Mode + SGK, and Min + SGK has the lowest PSNR. Figure 6(d) shows the variation of MSE with the noise standard deviation. In this experiment, PCA + SGK owns the lowest value of MSE, which means that the denoising performance is better than any of the other four algorithms.Figure 6
Variation of denoising performance with noise standard deviation on five algorithms.
(a)
Variation of noise estimation absolute (b)
Variation of noise estimation time (c)
Variation of PSNR (d)
Variation of MSE


### 4.3. Denoising Experiment of Noisy Image with Unknown Standard Deviation

The above experiments presumably assumed that the standard deviation of the noise contained in the image is known. In order to demonstrate the advantage of the proposed PCA + SGK algorithm, it is used to denoise the noisy image with unknown standard deviation and compare it with the original SGK algorithm. Twelve classic original images are shown in Figure7. These images are mixed into additive white Gaussian noise with unknown standard deviation. After that, we do PCA + SGK denoising and SGK denoising, respectively. When SGK is used for denoising, the standard deviation can only be guessed based on the noisy image or given a random value because the noise standard deviation is unknown. When PCA + SGK is used for denoising, the noise standard deviation is first estimated by PCA and thus is entered into SGK for denoising. Denoising results of the Cameraman image using these two algorithms are shown in Figure 8. Figure 8(a) shows the noise image with σ=10. Figure 8(b) shows the denoised image by SGK and Figure 8(c) shows the denoised image by PCA + SGK. The experiment testifies for the good performance of our approach. It can be seen that the denoising performance of PCA + SGK is better than SGK, which retains more details of the original image.Figure 7
Twelve classic images.Figure 8
Comparison of two denoising algorithms on the Cameraman image.
(a)
Noisy Cameraman image (b)
SGK denoised image (c)
PCA + SGK denoised imageThe denoising results of 12 images are shown in Table3. It is seen that the PSNR of SGK is less than that of PCA + SGK; that is, PCA + SGK has better denoised performance than PCA. Because the standard deviation of noisy image is not given when using SGK, the noise level can only be guessed and entered into SGK for denoising. While using PCA + SGK to deal with noisy image, PCA is first used to estimate the standard deviation, and then the estimated value is entered into SGK for denoising, so the denoising performance is better. Quantitative comparisons with traditional SGK illustrate the benefits of PCA + SGK.Table 3
Denoising results of two algorithms for 12 images.
Image Guessed noise valueσ′ PSNR of SGK PCA estimated valueσest PSNR of PCA + SGK Barbara 12.15 31.5826 3.25 40.8875 Boat 20.02 31.0877 4.96 36.9938 Bridge 29.78 24.7522 8.67 32.1713 Cameraman 35.11 27.5935 10.22 33.7171 Couple 30.45 26.1943 12.30 32.2721 Fingerprint 20.10 28.0063 15.06 29.7811 Flintstones 4.98 23.4492 19.10 29.0998 Hill 5.23 22.5119 20.21 29.9451 House 10.00 22.8280 22.58 32.4558 Lena 15.15 23.7830 24.34 30.8314 Man 15.50 21.8376 28.04 28.3323 Peppers 18.24 22.4973 30.38 28.7696


## 4.1. Comparison of Four Dictionary Learning Denoising Algorithms

We conduct experiments for image denoising by using SGK, DCT, Global, K-SVD dictionary learning algorithms, and BM3D algorithms. The similarity of the first four algorithms is to build a dictionary and then use the dictionary to denoise. DCT algorithm denoises an image by sparsely representing each block with the overcomplete DCT dictionary, thus averaging the represented parts [11]. Global algorithm denoises an image by training a dictionary on patches from the noisy image, sparsely representing each block with this dictionary and averaging the represented parts [11]. K-SVD algorithm uses DCT dictionary to initialize and then uses singular value decomposition for dictionary updating [11]. BM3D algorithm is an image signal denoising method based on transform domain enhancement sparse representation [26].Throughout this experiment, we use SGK, DCT, Global, K-SVD, and BM3D algorithms to denoise the Barbara image withσ=25 as an example. As shown in Figures 3(b)–3(f), the denoising results of five different algorithms are basically the same, and the image’s details are basically well preserved. In the following, we do quantitative comparisons between five algorithms, and the experimental data is shown in Table 1. The PSNR of the SGK is similar to that of K-SVD, and it is superior to Global, DCT, and BM3D algorithms. Encouragingly, we see that SGK runs much faster than K-SVD. As to the value of MSE, SGK is smaller than Global, DCT, and BM3D algorithms. With all the above-mentioned results, the denoising supremacy of SGK over the rest algorithms is demonstrated.Table 1
Image denoising results of five dictionary learning algorithms.
Algorithms Time/s PSNR/dB MSE SGK 17.378 32.077 77.470 DCT 83.884 31.079 113.873 Global 100.479 31.734 89.435 K-SVD 284.181 32.171 72.383 BM3D 12.256 30.717 119.478Figure 3
Using five kinds of dictionary learning algorithm for image denoising.
(a)
Original Barbara image (b)
SGK denoised image (c)
DCT denoised image (d)
Global denoised image (e)
K-SVD denoised image (f)
BM3D denoised image


## 4.2. Comparison of SGK Combined with Different Noise Estimation Algorithms

In order to analyze the sensitivity of SGK algorithm to the noise level, the noise standard deviation is set asσ=5,10,15,20,25, respectively. SGK algorithm is used to denoise the Peppers image with different noise standard deviation.Figure4 shows the denoising experiment’s results using the SGK algorithm with different offsets. The five different colors curves, respectively, represent the case where the PSNR varies with the noise offsets if the noise standard deviation is given. It can be found in Figure 4 that the PSNR of denoised image is basically invariant when the noise standard deviation has negative offset of 0~−5% and the forward offset of 0~+5%. When the offset of noise standard deviation continues to increase, it shows a significant downward trend in −5%~−25% of the negative offset and 5% to 25% of forward offset, which indicates that the image’s PSNR is significantly reduced. Therefore the PSNR would be changed when the noise standard deviation has negative or forward offset, which shows that the SGK algorithm is sensitive to the offsets of the noise standard deviation. So it is necessary to estimate noise level before image denoising. If the estimated noise level is close to the true noise, the denoising results will be more accurate.Figure 4
SGK denoising performance with different noise offset.In order to analyze the performances of SGK dictionary denoising combined with different noise estimation algorithms, this paper also introduces four noise estimation algorithms: Kurtosis [25], local standard deviation distribution mode (Mode) [27], local standard deviation (Med) [27], and local standard deviation minimum (Min) [27].Kurtosis assumes that the corresponding distribution of the kurtosis edge bandpass filter should be a constant for the noise-free images. However, the kurtosis at the entire scale of a noisy image may vary. Under this assumption, the noise standard deviation can be estimated by the kurtosis model.Mode can divide image and the noise standard deviation is estimated according to the distribution pattern of the image’s local standard deviation. As the variance of noise is constant throughout the picture, it will affect every local variance value equally. As a result, the maximum of the bell-shaped distribution will reflect the local variance of the degraded image within homogeneous areas. This value is the mode of the distribution, and it is very close to the mode, so we can use the mode to estimate it.Med estimates noise standard deviation based on the median of the image’s local standard deviation. If practical difficulties to properly estimate the mode arise, it may be useful to use the median operator instead, due to its greater simplicity and the fact that both parameters, albeit different, are not far apart in practice. So an alternative estimation procedure can be done.Min estimates the noise standard deviation based on the minimum value of the local standard deviation of the images. Within a uniform area, the variance of the degraded image equals the variance of noise. According to the previous statement, one straightforward way to estimate standard deviation is to calculate the variance within homogeneous regions, where the variance of the original image is close to zero.The above noise estimation algorithms are all combined with the SGK dictionary learning algorithm in this paper. Now we combine the five noise estimation algorithms mentioned above with SGK, respectively. The combined algorithms are referred to as PCA + SGK, Kurtosis + SGK, Mode + SGK, Med + SGK, and Min + SGK. Figure5 shows the denoising results of the Lena image, where the noise standard deviation is set to σ=15. Analysis of Figure 5 leads to the following observation: the denoising performance of Mode + SGK in Figure 5(d) is slightly the worst, while the remaining four algorithms are basically the same. They all retain the details of the image in the denoising process.Figure 5
Comparison of five kinds of algorithms.
(a)
Original Lena image (b)
PCA + SGK (c)
Kurtosis + SGK (d)
Mode + SGK (e)
Med + SGK (f)
Min + SGKIn order to analyze the denoising performance of five algorithms quantitatively, additive Gaussian white noise images withσ=2,5,10,20,30,40 are, respectively, denoised and compared in Table 2. The best results are shown in boldface. Experiments performed on noisy Lena image indicate that the proposed algorithm outperforms, in terms of estimation accuracy |σest-σ|, estimation time, PSNR, and MSE, the four existing algorithms.Table 2
Denoising indicators on SGK combined with five noise estimation algorithms.
σ Algorithms σ e s t σ e s t - σ σ e s t - σ Time/s PSNR/dB MSE σ = 2 PCA + SGK 2.733 +0.733 0.733 1.799 43.385 2.983 Kurtosis + SGK 2.841 +0.841 0.841 4.699 43.378 2.987 Mode + SGK 2.768 +0.768 0.768 0.070 43.222 3.010 Med + SGK 4.063 +2.063 2.063 0.051 41.811 4.286 Min + SGK 0.496 −1.504 1.504 0.037 42.119 3.993  σ = 5 PCA + SGK 5.510 +0.510 0.510 1.829 38.383 9.436 Kurtosis + SGK 5.166 +0.166 0.166 5.865 38.302 9.614 Mode + SGK 4.480 −0.520 0.520 0.091 38.139 9.981 Med + SGK 6.194 +1.194 1.194 0.047 38.251 9.727 Min + SGK 0.674 −4.326 4.326 0.035 34.175 24.865  σ = 10 PCA + SGK 10.342 +0.342 0.342 1.604 35.177 19.201 Kurtosis + SGK 9.576 +0.424 0.424 4.848 34.795 21.559 Mode + SGK 8.809 +1.191 1.191 0.090 34.074 25.447 Med + SGK 10.463 +0.463 0.463 0.051 35.149 19.869 Min + SGK 1.640 −18.360 18.360 0.037 28.244 97.417  σ = 15 PCA + SGK 15.153 +0.147 0.147 1.995 34.269 30.632 Kurtosis + SGK 14.196 +0.804 0.804 5.208 33.899 30.760 Mode + SGK 12.494 +2.506 2.506 0.084 31.381 47.311 Med + SGK 14.838 −0.162 0.162 0.082 33.221 30.971 Min + SGK 1.807 −13.193 13.193 0.029 28.274 96.766  σ = 20 PCA + SGK 20.071 +0.071 0.071 1.618 31.911 41.876 Kurtosis + SGK 18.943 −1.057 1.057 4.818 31.574 45.256 Mode + SGK 17.038 −2.963 2.963 0.094 30.186 62.300 Med + SGK 19.319 −0.681 0.681 0.055 31.777 43.193 Min + SGK 1.877 −18.123 18.123 0.028 22.152 396.153  σ = 30 PCA+SGK 29.672 −0.328 0.328 1.393 29.917 66.286 Kurtosis + SGK 28.480 −1.520 1.520 5.126 29.724 69.292 Mode + SGK 23.356 −6.644 6.644 0.084 29.044 161.709 Med + SGK 28.199 −1.801 1.801 0.054 29.614 71.074 Min + SGK 3.292 −26.708 26.708 0.029 18.675 882.180  σ = 40 PCA + SGK 39.546 −0.454 0.454 1.865 28.371 94.630 Kurtosis + SGK 38.238 −1.762 1.762 5.134 28.305 96.062 Mode + SGK 33.463 −6.537 6.537 0.087 25.813 170.526 Med + SGK 37.068 −2.932 2.932 0.053 27.910 105.212 Min + SGK 5.385 −34.615 34.615 0.034 16.222 1152.049Figure6 illustrates the performance of algorithms more intuitively varying with standard deviation. Figure 6(a) shows variation of noise estimation absolute error with the noise standard deviation. It can be seen that PCA + SGK has the least value, which is superior to the other four algorithms. So the estimation of PCA + SGK is the most accurate. Figure 6(b) shows the variation of the noise estimation time with the noise standard deviation. For the noise estimation time, Mode + SGK, Med + SGK, and Min + SGK are the least accurate, followed by PCA + SGK and Kurtosis + SGK. Figure 6(c) shows the variation of PSNR with the noise standard deviation. With the increase of standard deviation, PCA + SGK and Kurtosis + SGK keep the PSNR higher, followed by Med + SGK and Mode + SGK, and Min + SGK has the lowest PSNR. Figure 6(d) shows the variation of MSE with the noise standard deviation. In this experiment, PCA + SGK owns the lowest value of MSE, which means that the denoising performance is better than any of the other four algorithms.Figure 6
Variation of denoising performance with noise standard deviation on five algorithms.
(a)
Variation of noise estimation absolute (b)
Variation of noise estimation time (c)
Variation of PSNR (d)
Variation of MSE


## 4.3. Denoising Experiment of Noisy Image with Unknown Standard Deviation

The above experiments presumably assumed that the standard deviation of the noise contained in the image is known. In order to demonstrate the advantage of the proposed PCA + SGK algorithm, it is used to denoise the noisy image with unknown standard deviation and compare it with the original SGK algorithm. Twelve classic original images are shown in Figure7. These images are mixed into additive white Gaussian noise with unknown standard deviation. After that, we do PCA + SGK denoising and SGK denoising, respectively. When SGK is used for denoising, the standard deviation can only be guessed based on the noisy image or given a random value because the noise standard deviation is unknown. When PCA + SGK is used for denoising, the noise standard deviation is first estimated by PCA and thus is entered into SGK for denoising. Denoising results of the Cameraman image using these two algorithms are shown in Figure 8. Figure 8(a) shows the noise image with σ=10. Figure 8(b) shows the denoised image by SGK and Figure 8(c) shows the denoised image by PCA + SGK. The experiment testifies for the good performance of our approach. It can be seen that the denoising performance of PCA + SGK is better than SGK, which retains more details of the original image.Figure 7
Twelve classic images.Figure 8
Comparison of two denoising algorithms on the Cameraman image.
(a)
Noisy Cameraman image (b)
SGK denoised image (c)
PCA + SGK denoised imageThe denoising results of 12 images are shown in Table3. It is seen that the PSNR of SGK is less than that of PCA + SGK; that is, PCA + SGK has better denoised performance than PCA. Because the standard deviation of noisy image is not given when using SGK, the noise level can only be guessed and entered into SGK for denoising. While using PCA + SGK to deal with noisy image, PCA is first used to estimate the standard deviation, and then the estimated value is entered into SGK for denoising, so the denoising performance is better. Quantitative comparisons with traditional SGK illustrate the benefits of PCA + SGK.Table 3
Denoising results of two algorithms for 12 images.
Image Guessed noise valueσ′ PSNR of SGK PCA estimated valueσest PSNR of PCA + SGK Barbara 12.15 31.5826 3.25 40.8875 Boat 20.02 31.0877 4.96 36.9938 Bridge 29.78 24.7522 8.67 32.1713 Cameraman 35.11 27.5935 10.22 33.7171 Couple 30.45 26.1943 12.30 32.2721 Fingerprint 20.10 28.0063 15.06 29.7811 Flintstones 4.98 23.4492 19.10 29.0998 Hill 5.23 22.5119 20.21 29.9451 House 10.00 22.8280 22.58 32.4558 Lena 15.15 23.7830 24.34 30.8314 Man 15.50 21.8376 28.04 28.3323 Peppers 18.24 22.4973 30.38 28.7696


## 5. Conclusions

In this paper, the algorithm of PCA noise estimation combined with SGK dictionary learning was proposed to denoise image. The noisy image is first divided into patches, and the noise standard deviation is estimated by calculating the minimum eigenvalue of the image patch covariance matrix. After that, the estimated noise standard deviation is entered into SGK dictionary learning algorithm. The sparse representation of each training sample is obtained by sparse coding, and the dictionary atoms are updated by dictionary updating to denoise the image. This algorithm effectively solves the problem that the SGK algorithm requires a prior noise standard deviation for image denoising. This paper has the following three conclusions.Firstly, the SGK dictionary learning algorithm is compared with K-SVD, DCT, Global, and BM3D algorithms. The PSNR of SGK algorithm and those of the other four algorithms do not have much difference, and the MSE of SGK algorithm is only higher than K-SVD algorithm. SGK algorithm owns great advantage in denoising time, which is much faster than K-SVD, DCT, and Global algorithms. Therefore, the SGK algorithm has the best denoising performance.Secondly, the PCA algorithm is compared with the other four noise estimation algorithms: Kurtosis, Mode, Mad, and Min. The five algorithms are, respectively, combined with the SGK algorithm to denoise the additive Gaussian white noise images with different standard deviation. The absolute deviation of the noise estimated by PCA + SGK is the smallest, and it is better than the other four algorithms; that is, the noise standard deviation estimation of this algorithm is the most accurate. For the noise estimation time, Min + SGK, Med + SGK, and Mode + SGK all have a faster estimation and then it is PCA + SGK algorithm proposed in this paper and Kurtosis + SGK is the slowest. On the other hand, PCA + SGK and Kurtosis + SGK keep the high PSNR, followed by Med + SGK and Mode + SGK. The lowest PSNR is that of Min + SGK. At the same time, the MSE value of PCA + SGK is the lowest. So the denoising performance of proposed algorithm is better than the other four algorithms. It is found that the proposed algorithm is more accurate to estimate the noise standard deviation with faster denoising speed and good denoising performance.Thirdly, PCA + SGK and SGK are, respectively, used to denoise the image with different standard deviation. Experiments show that PSNR of PCA + SGK is much higher than that of SGK. When using SGK for denoising, the noise standard is unclear, so the denoising performance is not good, while PCA + SGK firstly uses the PCA to estimate the noise standard deviation, which is close to the true value of the noise level, so the denoising performance is more ideal and the image’s details are better preserved. While performance improvement is different for different images, the results nonetheless indicate the potential of proposed algorithm over original SGK algorithms.



---

*Source: 1259703-2018-03-14.xml*