1 June 2010 Automatic stopping criterion in fields-of-experts image denoising
Author Affiliations +
Optical Engineering, 49(6), 060504 (2010). doi:10.1117/1.3456368
Abstract
Fields of experts (FoE) image denoising is one of the most promising high-order Markov random field (MRF)-based image denoising methods. However, the original algorithm by Roth and Black did not consider the parameter selection problem in its iteration, so it cannot be directly applied to real image denoising tasks. An automatic stopping criterion in FoE image denoising is introduced, through which the denoised image can be obtained without reference image and noise variance estimation. Experimental results validate its better performance than the classic FoE method, both on synthetic and real noisy images.
Zhang, Zhang, Zhong, and Wang: Automatic stopping criterion in fields-of-experts image denoising

1.

Introduction

In many scientific applications, images are often corrupted by noise because of either data acquisition or data transmission. Therefore, the problem of recovering an original image from noisy data has received ever-increasing attention in recent years, but it is still very challenging.1 It has been popular to denoise an image by Markov random field (MRF)-based methods. Recently, a new fields of experts (FoE)-based approach2 was introduced that considered high-order MRF cliques to grasp the complex structural information in image data and utilized a maximum-a-posteriori (MAP) framework to get the clean image. It is one of the most promising methods in generic MRF-based image denoising approaches.3

The typical objective in denoising problems is a recovery of an image with minimal mean-squared error (MSE). However, in practice, we do not have the original image to compare to, and thus we cannot know what choice of parameters minimizes the MSE. Therefore, the parameters are often tuned manually by looking at the reconstructed result.

In FoE image denoising algorithms, the tradeoff parameter and stopping criterion must be specified before iteration. However, tuning of the parameters is not an easy task. Assuming that the noise level is known a priori, Roth and Black adopted a fixed number of iterations and experientially determined the appropriate tradeoff parameter between the likelihood term and the FoE prior term using a complicate training procedure. But in real image denoising, accurate noise variance estimation is unavailable, even though there are many types of noise variance estimate algorithms.4

In this work, we have developed an automatic blind method in FoE real image denoising, which can take effect without accurate noise variance estimation and automatically terminate at a good result.

2.

Brief Review of Field of Experts Image Denoising

The basic problem of image denoising is the recovery of a latent clear image X from an observed noisy image Y:Y=HX+N , where N represents additive noise, assumed to be white Gaussian noise (WGN) with zero mean and known standard deviation σ . Using MAP rules to estimate the clear image X , we can maximize the posterior probability X̂MAP=ArgmaxXP(X|Y)=ArgmaxXP(Y|X)P(X) , in which the conditional possibility is

1

P(Y|X)kexp[12σ2(ykxk)2],
where k ranges over the pixels in the image. Modeling image X as a MRF, and according to the Hammersley-Clifford theorem, we can write the probability density of this graphical model as a Gibbs distribution,
P(X)=1Z(X)exp[kVk(X(k))],
where Vk[X(k)] is the potential function for clique X(k) , and Z(X) is the normalized constant, called the partition function. In the FoE framework, the probability density of image P(X) can be written as,
PFoE(X)=1Z(Θ)ki=1Nϕi(JiTX(k);ai).
From Eq. 1, the gradient of the log-likelihood is written as xlogp(Y|X)=(YX)σ2 , and the gradient of the log-prior is

2

Xlogp(X)=i=1NJ(i)ψi[J(i)X].
J(i)X denotes the convolution of image X with filter J(i) ; ψi(Y) is the log differential of experts, that is, ψi(Y)=logϕi(Y;ai)Y ; J(i) denotes the filter obtained by mirroring J(i) around its center pixel; ϕi obeys the function form of the Student t-distribution as in Ref. 2. By introducing an iteration index t , an update rate η , and an optional weight λ , we can write the gradient descent algorithm as:

3

X(t+1)=X(t)+η{i=1NJ(i)ψi[J(i)X(t)]+λσ2(YX(t))}.
It could be seen that the denoised image can be obtained by gradient descent optimization in the FoE image denoising method (Roth-FoE). More details can be found in Ref. 2.

3.

Parameter Selection in Roth/Field-of-Experts

In Roth-FoE, two important parameters, the tradeoff parameter λ and stopping criterion, have an important impact on the final image quality and its computational complexity, so they must be specified before iteration begins. However, tuning of the parameters is not an easy task. In computer vision tasks, two stopping criteria were widely used: a fixed number of iterations or a predefined threshold, which the difference between adjacent iterations becoming smaller. However, these two strategies both have to choose the threshold or the number of iterations by experience, so they cannot be done completely automatically for all images.

Assuming a known noise distribution in synthetic image denoising, Roth experimentally determined the appropriate λ using a complicated training procedure with synthetic data and specified a fixed number of iterations. The Roth-FoE can generate satisfied results in the synthetic experiment with known noise variance.

We simulated noisy data by adding WGN to the same test image Castle from the Berkeley segmentation dataset, as in Roth’s work. The true noise level we added was σ=15 , and the noise levels while using Roth-FoE are four different hypotheses with σ̂{10,15,30,75} . Other parameters were selected as recommended in Ref. 2. The peak signal-to-noise ratio (PSNR) curves of four experiences with 5000 iterations are given in Fig. 1. It shows that the noise variance estimation is vital in the performance of the final results using the stopping criterion for fixed numbers of iterations. However, if we can find an effective automatic stopping criterion to stop the algorithm at optimal times, such as using σ̂{30,75} , we can get the satisfied results, or even better than the results by using the perfect noise variance estimation with σ̂=15 . Unfortunately, in real image denoising, there is no ground truth and the accurate noise variance is unavailable, even though there are many types of noise variance estimate algorithms.4 So the Roth-FoE is restricted to simulated experiments, and cannot be directly applied to real image denoising applications.

Fig. 1

Denoising performance of noisy image (σ=15) using the 5×5 FoE models with varying noise level (σ̂{10,15,30,75}) shown in terms of PSNR.

060504_1_1.jpg

4.

Automatic Stopping Criterion

According to Eq. 3, Roth-FoE can be understood as a regularization algorithm in inverse problems, and λσ2 can be considered as the regularization factor to balance the impact between the two terms: a data fidelity term that measures the likelihood of the input image given the output, and a prior term that encodes prior assumptions about the output. In this work, motivated by Fig. 1, we considered the parameter λσ2 as fixed and adopted a no-reference image quality assessment based on singular value decomposition (SVD) to design an optimal automatic stopping criterion for FoE-based image denoising.

Considering an n×n window ωk at point (i,j) of image X , the gradient matrix is defined as

G=[gi(k)gj(k)],kωk,
where [gi(k),gj(k)]T denotes the gradient of the image at point (i,j) . Computing the SVD of G and assuming s1s20 , it can be obtained that
G=USVT=U[s100s2][v1v2]T.
The singular values s1 and s2 represent the energy in the directions v1 and v2 , respectively, and they reflect the strength of the gradients along the dominant direction and its perpendicular direction. Image patches can be classified into four types of idealized patches: flat, linear, quadratic, and edged regions. Define the image content metric of image patch ωk as
Qk=s1s1s2s1+s2.
Zhu and Milanfar5, 6 demonstrated that for anisotropic patches (s1s2) , including the linear, anisotropic quadratic, and edged regions, the proposed metric Qk is able to detect both blur and random noise. So in practice, when measuring the true content of an image as a whole, we can calculate Q in all anisotropic areas as

4

Q=1KkQk.
We distinguish between isotropic and anisotropic areas by employing significance testing6 based on local coherence R=(s1s2)(s1+s2) . In our experiments, we set the significance level to be 0.001, and use it to determine image patch labels. In the iteration, Q is computed every time as a sign of whether to stop the iteration to get the optimal results. The FoE denoising method with automatic stopping criterion (ASC-FoE) can be described as follows.
  • 1. Initialization: set λσ2=0.001 , η=0.1 , and the initial iteration value X(0)=Y . Compute its image quality measurement Q(0) according to Eq. 4. Set Qmax=Q(0) and optimal iteration time Iopt=0 .

  • 2. Iteration: update X(t+1) and corresponding Q(t+1) from Eqs. 3, 4. If Q(t+1)> Qmax , let Qmax=Q(t+1) , Iopt=t+1 .

  • 3. Stopping criterion: if Q(t+1+n)<Qmax , for n=1,,N , the iteration terminates, and let X(t+1) be the denoised image.

5.

Experimental Results

We design an experimental scheme to illustrate the image quality performance of the proposed method on both synthetic and real images. For the synthetic data, we simulated noisy data by adding WGN (σ=30) to the test image Castle. We denoised it by Roth-FoE and the proposed ASC-FoE under seven different noise-level hypotheses with σ̂{25,30,35,40,50,75,100} . We used the 5×5 FoE model with 24 filters, and other parameters were selected as recommend in Ref. 2. Table 1 shows the performance comparison in terms of PSNR and structural similarity (SSIM) index as measured between the denoised image and the ground truth. Also, the iteration numbers are given out. It can be seen that the ASC-FoE outperforms the Roth-FoE and has less computational cost. It should be noted that, for fair comparison of the two methods in the synthetic ASC-FoE experiment, we used six different noise level hypotheses the same as the Roth-FoE instead of setting λσ2=0.001 , as described in ASC-FoE. In addition, using λσ2=0.001 is almost equal to using σ̂=75 , and the result is also satisfied.

Table 1

PSNR, SSIM, and iteration number for Roth-FoE and ASC-FoE.

σ̂ PSNR (dB)SSIMIteration Number
ASC-FoERoth-FoEASC-FoERoth-FoEASC-FoERoth-FoE
2523.224523.22540.50880.508949995000
3026.892626.89260.80410.804150005000
3527.654627.65460.80470.804750005000
4027.732827.61330.80500.791642905000
5027.781427.12810.80470.791637045000
7527.797726.34260.80670.745531635000
10027.793326.04310.80660.736430435000

For the real noise image, the experimental results are shown in Fig. 2. We use the test image JFK (367×343) 7 that suffers from the real noise shown in Fig. 2. The noise comes from film grain, scanning, and compression processes, and may not be pure Gaussian—indeed, it may be space variant. We estimated the standard deviation of the noise through the commonly used median absolute deviation (MAD) method for Roth-FoE. The measured value is σ=4.2 . The results of Roth-FoE and ASC-FoE are shown in Figs. 2 and 2, respectively. It can be seen that the ASC-FoE outperforms the Roth-FoE in noise-suppressing capability, and obtains a more pleasant result. Moreover, the Roth-FoE requires 5000 iterations according to recommended parameter settings, while in this experiment we terminated the ASC-FoE at iteration 208 when the image quality achieved the best. Therefore, the iteration time reduction of ASC-FoE scores around 96% and would result in a speedup factor of more than 24.

Fig. 2

Denoised images and partially magnified images of Roth-FoE and ASC-FoE compared in this experiment on an image with real noise. (a) Real noisy image. (b) Roth-FoE (Q=27.3598) . (c) Proposed ASC-FoE (Q=28.5272) .

060504_1_2.jpg

6.

Conclusion

For real image denoising applications, we develop an automatic stopping criterion in FoE image denoising. We demonstrate that our ASC-FoE can obtain a faster and more pleasant result than the original Roth-FoE without the explicit need to know the noise variance a priori.

Acknowledgments

The authors are grateful to the associate editor Eddie Jacobs and the anonymous reviewers for their efforts, comments, and recommendations, which have led to a substantial improvement of this work. This study was partially supported by the National Natural Science Foundation of China (Grant No. 60902088) and NDTF Project of the ATR Laboratory (Grant No. 9140C8004011005).

References

1.  C. Liu, R. Szeliski, S. B. Kang, C. L. Zitnick, and W. T. Freeman, “Automatic estimation and removal of noise from a single image,” IEEE Trans. Pattern Anal. Mach. Intell.0162-8828 30, 299–314 (2008). 10.1109/TPAMI.2007.1176 Google Scholar

2.  S. Roth and M. J. Black, “Fields of experts,” Int. J. Comput. Vis.0920-5691 82, 205–229 (2009). 10.1007/s11263-008-0197-6 Google Scholar

3.  V. Katkovnik, A. Foi, K. Egiazarian, and J. Astola, “From local kernel to nonlocal multiple-model image denoising,” Int. J. Comput. Vis.0920-5691 86, 1–32 (2010). 10.1007/s11263-009-0272-7 Google Scholar

4.  D. Zoran and Y. Weiss, “Scale invariance and noise in natural images,” in Proc. IEEE Intl. Conf. on Computer Vision (ICCV09), Tokyo, Japan, pp. 64–69, IEEE, Piscataway, NJ (2009). Google Scholar

5.  X. Zhu and P. Milanfar, “A no-reference sharpness metric sensitive to blur and noise,” presented at 1st Intl. Workshop on Quality of Multimedia Experience (QoMEX), San Diego, 2009. Google Scholar

6.  X. Zhu and P. Milanfar, “Automatic parameter selection for denoising algorithms using a no-reference measure of image content,” IEEE Trans. Image Process.1057-7149 (in press). Google Scholar

7.  H. Takeda, S. Farsiu, and P. Milanfar, “Kernel regression for image processing and reconstruction,” IEEE Trans. Image Process.1057-7149 16, 349–366 (2007). 10.1109/TIP.2006.888330 Google Scholar

Zhi Zhang, Peng Zhang, Ping Zhong, Runsheng Wang, "Automatic stopping criterion in fields-of-experts image denoising," Optical Engineering 49(6), 060504 (1 June 2010). https://doi.org/10.1117/1.3456368
JOURNAL ARTICLE
3 PAGES


SHARE
Back to Top