1 Introduction

Due to defected equipment, electromagnetic interference, and interfered channels in acquisition and transmission, digital images are often corrupted by impulse noise [15]. Let u0 be an original image, where (u0)i,j is the gray level of u0 at location (i,j). The noisy image contaminated by impulse noise is defined by

$$ \begin{array}{@{}rcl@{}} f_{i,j}= \left\{ \begin{array}{ll} n_{i,j}, \quad & \text{with probability } s,\\ (u_{0})_{i,j}, & \text{with probability } 1-s, \end{array} \right. \end{array} $$

where ni,j is the impulse noise and s is the noise level [12]. The problem of image denoising under impulse noise is to find an approximation u of the true image u0 from the observed noisy image f such that important structures like edges and details are preserved but impulse noise is removed. Two common types of impulse noise are salt-and-pepper noise the random-valued noise. Assume that the dynamic range of u0 is [dmin,dmax]. For images corrupted by salt-and-pepper noise, ni,j can take only two values dmin and dmax, while for images corrupted by random-valued noise, ni,j can take any random value between dmin and dmax. Generally, random-valued noise is harder to deal with than salt-and-pepper noise. In this paper, we focus on the problem of removing random-valued impulse noise from images.

According to the definition of impulse noise, only a portion of pixels in images are corrupted. Commonly used algorithms for removing impulse noise are the two-stage method, i.e., detection followed by filtering. More precisely, an impulse noise detector is applied to identify corrupted pixels, then different types of filters are employed to restore the corrupted pixels and leave the noise-free pixels unchanged.

Median filter and its variations [10, 11, 19,20,21, 27] have been widely used in the literature for restoring corrupted pixels. These filters are nonlinear and preserve edges well for low density impulse noise suppression. With the increase of the noise level, the filtering window is getting larger. As a result, edges and some details in images are smeared. The main advantage of the median filter and its variations is the very fast execution speed [2, 19]. Another well-known method for restoring corrupted pixels is the weighted mean filter [14, 17, 18, 23, 30, 45, 47], which exploits the correlation among neighboring pixels to restore the corrupted pixels. Also, it adaptively determines the filtering window and utilizes only uncorrupted pixels for the restoration. Recently, the fuzzy technique was considered to improve the denoising results [3, 9, 12, 22, 26, 32, 39]. In this method, the authors determined how impulse-like a pixel is rather than determining whether it is corrupted. It s well suited for removing random-valued noise since random-valued noise is difficult to detect [13, 25, 40].

It is worth mentioning that many outstanding methods for removing impulse noise are inspired by ideas for removing Gaussian noise. The functional with the total variation (TV) regularization and the L2 data fitting term is efficient for many image processing problems [5, 31, 33]. By observing that the L1 norm is more robust in the presence of outliers, TV-L1 functionals were proposed for removing impulse noise [28, 42]. Recently, TV-nonconvex models were proposed [1, 24, 41, 43, 44, 46] since TV-L1 model will only lead to a sub-optimal solution. Nonlocal means filter [6] was first introduced to preserve textural information in images. It was also extended for removing impulse noise [12, 35, 39, 40]. The main challenge of applying the nonlocal mean filter to the case of impulse noise is the calculation of the nonlocal weights. In [40], the authors proposed to calculate the nonlocal weights based on a reference image that is obtained by the median filter. The more common approach of calculating the weights is to utilize only the noise-free pixels[12, 35, 39].

Diffusion equations have become a powerful tool for image denoising since the introduction of the Perona-Malik equation [29]. In [38], the authors proposed a PDE (Partial Differential Equation) model based on diffusion coefficients that take different values for interior pixels, edges, and noise pixels. However, the denoising results generally have low quantitative evaluation values and poor visual quality, especially when the noise level is high. In [36], a non-divergence equation was proposed for removing impulse noise, which first detects the noise pixels and then removes these noise by a diffusion equation. The equation, as well as the aforementioned nonlocal methods, are the two-stage method. Consequently, the results depend heavily on the accuracy of the noise detection.

Recently, we proposed a gray level indicator to estimate the amplitude of Cauchy noise in images [34]. Note that both Cauchy noise and random-valued noise have a very impulsive character. In this paper, we modify the gray level indicator to estimate the amplitude of random-valued noise. A nonlinear diffusion equation is proposed based on the gray level indicator under the framework of diffusion equations in the non-divergence form [34, 36]. By introducing the gray level indicator, we estimate how impulse-like pixels in images are and avoid the step of noise detection. It achieves the goal of fuzzy estimation for random-valued noise [12]. A pixel with a large gray level indicator has a larger diffusion coefficient than a pixel with a small gray level indicator. Consequently, small random-valued impulse noise that is difficult to be detected by two-stage methods can be removed efficiently by the new equation. Finding an appropriate stopping time for diffusion equations is a crucial problem in image processing. We propose a robust stopping criteria based on the complexity of the restored image and the noise level.

The rest of this paper is organized as follows. In Section 2, we discuss details of the proposed equation and the implementation of it for removing random-valued impulse noise. Numerical experiments are provided in Section 3 to demonstrate the efficiency of the equation. We conclude the paper in Section 4.

2 The proposed equation

2.1 Related works and the proposed diffusion equation

Nonlinear diffusion equation

$$ \begin{array}{@{}rcl@{}} \frac{\partial u}{\partial t}=\text{div}(c(|\nabla u|) \nabla u) \end{array} $$
(1)

has attracted a lot of attention in image restoration under Gaussian noise [4]. In many real-world applications, images are often corrupted by non-Gaussian noise that has a very impulsive character. Typical examples include impulse noise and Cauchy noise. In both problems, the gradient-based adaptive edge detector c(|∇u|) can not distinguish pixels corrupt by large noise from isolated edges. As a result, (1) fails to remove noise without smearing details of images.

In [36], we proposed to handle impulsive pixels and non-impulse pixels in different ways. To this end, an impulse noise indicator λ(x) was introduced for (1), and the equation for removing impulse noise has the following non-divergence form

$$ \frac{\partial u}{\partial t}=\lambda(x)\text{div}(c(|\nabla u|) \nabla u). $$
(2)

Here λ(x) is a characteristic function that equals 1 for noisy pixels and 0 for noise-free pixels. Consequently, only noisy pixels are processed by the equation. As we have mentioned in the introduction, this is a two-stage method, and the results depend heavily on the accuracy of noise detection.

Recently, we proposed a new gray level based diffusivity for the removal of Cauchy noise [34]. The proposed equation has the following form

$$ \frac{\partial u}{\partial t}=\left( \frac{|u_{0}(x)-f(x)|}{\max_{x\in{\Omega}}\{|u_{0}(x)-f(x)|\}}\right)^{\alpha}\text{div}(c(|\nabla u|) \nabla u), $$
(3)

where α is a positive parameter. Here the gray level based diffusivity |u0 − f| estimates the amplitude of the noise. Consequently, the larger the noise, the larger the diffusion coefficient is used in (3). It was verified in [34] that (3) restores the impulsive part of the noisy image efficiently.

We call both λ(x) in (2) and |u0 − f| in (3) the gray level indicator. The difference is that λ(x) indicates whether a pixel is corrupted while |u0 − f| indicates how impulse-like a pixel is. |u0 − f| can be viewed as the continuous generalization of λ(x). They have the same effect for noise-free pixels but a slightly different effect for noisy pixels.

Notice that both Cauchy noise and impulse noise are impulsive. It is straightforward to consider the removal of impulse noise under the framework of (3). Equation (3) has two advantages over (2) for the removal of random-valued noise. First, although both equations have the same effect for noise-free pixels, (3) is able to avoid over smoothness for noisy pixels that have small value |u0 − f| (see Fig. 1). Second, as we shall see in the next section, (3) is no longer a two-stage method. Consequently, it is able to remove small random-valued noise that is difficult to be detected (see Fig. 6).

Fig. 1
figure 1

Denoising results of (2) and (3) for restoring Boat image corrupted by 90% random-valued noise. The second row shows the enlarged subimages

Full size image

The function c(⋅) needs to be determined in advance. In this paper, we utilize the widely used Perona-Malik type diffusivity [7]

$$ c(|\nabla u|)=\frac{1}{1+(|\nabla u_{\sigma}|/K)^{2}}, $$
(4)

for (3). Here uσ is the convolution of u with a Gaussian of standard deviation σ, K is a positive constant. The utilization of convolution for (3) is based on the fact that images corrupted by impulse noise are highly oscillating. The convolution operator smoothes noisy images and reduces the effects of noise on the coefficient [36].

Before proceeding, we compare (3) with (2) through an experiment. Let us assume for a moment that the original image u0 is given. Then both λ(x) and |u0 − f| are known. We let the noisy image f be the initial condition for (2) and (3), respectively. By evolving these two equations with the homogeneous Neumann boundary condition, the solutions are the denoised images. All the parameters except the iteration numbers in both equations are set as suggested in Section 3.1. Since the original image is given, we manually select the iteration numbers for them such that the PSNR values of the denoised images achieve the highest.

Table 1 lists the PSNR results of (2) and (3) for restoring Boat image corrupted by 10%–90% random-valued noise. We observe that (3) performs better than (2) for all noise levels. The advantage of (3) is becoming more apparent with the increase of the noise level. In Fig. 1, we show the denoising results for Boat image corrupted by 90% random-valued noise. Both equations restore homogeneous regions perfectly. It is observed that (3) outperforms (2) in restoring edges and small details in images.

Table 1 PSNR results of (2) and (3) for restoring Boat image corrupted by random-valued noise
Full size table

2.2 Implementation

In the image denoising problem, the original image u0 is always unknown. Consequently, we need to substitute u0 in (3) by a reference image v. The finial diffusion equation for removing random-valued impulse noise is given by

$$ \frac{\partial u}{\partial t}=g(x)\text{div}\left( \frac{1}{1+(|\nabla u_{\sigma}|/K)^{2}} \nabla u\right), $$
(5)

where \(g(x)=\left (\frac {|v(x)-f(x)|}{\max \limits _{x\in {\Omega }}\{|v(x)-f(x)|\}}\right )^{\alpha }\) is the gray level indicator.

By using the half-point scheme [8], (5) can be discretized as

$$ \begin{array}{@{}rcl@{}} u_{i,j}^{(n+1)}&=&u_{i,j}^{(n)}+ \tau g_{i,j}\cdot\left[c^{(n)}_{i+\frac{1}{2},j}\left( u_{i+1,j}^{(n)}-u_{i,j}^{(n)}\right)+c^{(n)}_{i-\frac{1}{2},j}\left( u_{i-1,j}^{(n)}-u_{i,j}^{(n)}\right)\right.\\ &&{\kern4.5pc} \left.+c^{(n)}_{i,j+\frac{1}{2}}\left( u_{i,j+1}^{(n)}-u_{i,j}^{(n)}\right)+c^{(n)}_{i,j-\frac{1}{2}}\left( u_{i,j-1}^{(n)}-u_{i,j}^{(n)}\right)\right], \end{array} $$
(6)

where τ is the time step, n ≥ 0, u(n) is the denoised image at the n th iteration, \(u^{(n)}_{i,j}\) denotes the gray value of u(n) at pixel (i,j), u(0) = f is the observed noisy image, and

$$ \begin{array}{@{}rcl@{}} g_{i,j}&=&\left( \frac{|v_{i,j}-f_{i,j}|}{\max\{|v_{i,j}-f_{i,j}|\}}\right)^{\alpha},\\ c^{(n)}_{i+\frac{1}{2},j}&=&\frac{1}{1+\left( \left|(u_{\sigma})_{i+1,j}^{(n)}-(u_{\sigma})_{i,j}^{(n)}\right|/K\right)^{2}}. \end{array} $$

\(c^{(n)}_{i-\frac {1}{2},j}\), \(c^{(n)}_{i,j+\frac {1}{2}}\), and \(c^{(n)}_{i,j-\frac {1}{2}}\) are defined in a similar way. Notice that an anisotropic scheme [16, 29] is used for the calculation of the Perona–Malik type diffusivity.

In the rest of this section, we discuss the construction of the reference image v. In the case of Cauchy noise, we can simply use the Gaussian filter and let v = uσ. However, it cannot give satisfied results for random-valued noise. A straightforward approach is to restore noisy image f by median type filters. In fact, we are able to use the classical adaptive center-weighted median filter (ACWMF) [10] and the median filter to create v and update v by (5) automatically. The proposed model for removing random-valued noise is summarized in Algorithm 1. The selection of parameters that arose in the algorithm will be discussed in Section 3.1.

figure a

In the following, we give some remarks on the details of Algorithm 1. A two-level iterative method is used in Algorithm 1. The reason for updating v in the external iteration is based on the fact that the performance of median type filters drops rapidly with the increase of noise level. Consequently, the updating strategy can improve the denoising results remarkably. In Fig. 2, we illustrate the role of the external iteration. All parameters expect N are selected according to the discussion in Section 3.1. When N = 1, median type filters can not give a satisfied approximation of the original image. Consequently, the gray level indicator g is not accurate. With the increase of the iteration number N, it can be observed from the figure that both the PSNR value and the visual quality improve by a large margin.

Fig. 2
figure 2

Denoising results of Algorithm 1 with different N for Boat image corrupted by 60% random-valued noise. The second row are enlarged subimages

Full size image

In step 4, we use ACWMF to remove impulse noise in images and obtain the reference image v. The utilization of the median filter in step 5 is based on the observation that ACWMF cannot identify some obvious noisy pixels and pixels with small |u0 − f|, especially when the noise level is high. Another possible approach is to construct v by a state-of-the-art method. But there exists a problem with this approach: If the state-of-the-art method cannot restore pixels with small details and small |u0 − f|, then our algorithm can also not restore these pixels by the given v.

A stopping criteria (step 9-11) is proposed in the internal iteration. The threshold T in step 9 depends on the complexity of the restored image (estimated by the mean value of \(|u^{(n+1)}-u_{\sigma }^{(n)}|\)) and the noise level s. We estimate the noise level r according to the given u(n+ 1) and stop the iteration when r > s.

In Fig. 3 we compare the denoising performance of ‘NLM’, ‘Optimal’, and Algorithm 1. Here ‘NLM’ denotes the algorithm that replace the median type filters in step 4-5 of Algorithm 1 by the nonlocal means filter [12]. ‘Optimal’ denotes the algorithm that finds the optimal iteration numbers according to the PSNR value. We observe that NLM performs better than Algorithm 1 in individual cases. Generally, using a state-of-the-art method instead of median-filters to obtain v does not improve the results for our method. It is verified from the results of ‘Optimal’ and our algorithm that the proposed stopping criteria is robust and efficient.

Fig. 3
figure 3

Denoising results of NLM and the proposed equation for six test images (see Fig. 4). From left to right, from top to bottom: Pepper, Boat, Bridge, Mandrill, Couple and Plane. Legend ‘NLM-Proposed’ (‘Optimal-Proposed’, respectively) denotes the difference of PSNR between NLM and the proposed equation (Optimal and the proposed equation, respectively)

Full size image

Algorithm 1 contains two parts: calculating the reference image by median-type filters and removing noise by (5). From this point of view, Algorithm 1 is a two-stage method. However, we prefer not to regard our method as a two-stage method, since there exist essential differences between Algorithm 1 and the existing two-stage method, which utilizes the approach of detection followed by filtering.

3 Numerical experiments

In this section, numerical results are presented to demonstrate the performance of the proposed equation for removing random-valued noise in images. Six commonly used 512×512 8-bit depth test images from the USC-SIPI Image DatabaseFootnote 1, which are shown in Fig. 4, are selected for simulations. Peak Signal-to-Noise Ratio (PSNR) and Structural-SIMilarity (SSIM) index [37] are employed for the quantitative evaluation of the denoised images. The following algorithms are considered for the comparison.

  • NSDD, a PDE-based method that takes different values of diffusion coefficients for interior pixels, edges, and noise pixels [38].

  • AOP, the TV blind inpainting using adaptive outlier pursuit [41]. For the regularization parameter λ, we swept over

    $$ \{10, 50, 100, 500, 1000, 5000, 10000, 50000\} $$

    and choose the best one for each test image and each noise level.

  • L0TV, a sparse optimization method based on the l0-norm and the TV regularization [43]. For the regularization parameter λ, we swept over {0.1,0.6,0.11,…,9.6} and choose the best one for each test image and each noise level.

  • ROR-NLM, A two-stage method based on the nonlocal means filter [40]. The nonlocal weights are calculated by reference images.

  • SAFE, a two-stage method. It detects random-valued noise by the iterative structure-adaptive fuzzy estimation and restores corrupted pixels by the nonlocal means filter [12].

Fig. 4
figure 4

Test images Pepper, Boat, Bridge, Mandrill, Couple and Plane. The regions in red squares will be displayed in Fig. 5 and Fig. 6 for better visual comparison

Full size image

The codes of NSDD and L0TV are available on the original authors’ webpages. The code of AOP and SAFE are provided by the original authors. All parameters of the five methods are set as suggested by the original authors. For NSDD, AOP, L0TV, and ROR-NLM, we assume that the original images are given. Then the parameter λ and iteration number in these methods are manually selected to achieve the highest PSNR values of the restored images.

3.1 Experimental setup for Algorithm 1

The proposed Algorithm 1 contains a few free parameters. Fortunately, these parameters are robust to test images and noise levels. We are able to use almost the same parameters for all experiments presented in this paper. In the following, we give some guidelines on choosing them.

The stability of scheme (6) is favored with time step 0 < τ ≤ 0.25. We let τ = 0.25. The constant K needs to be small so that edges and small details are preserved in the restored images. We choose K = 7 for all experiments. The Perona–Malik type diffusivity involves the convolution operator. We use the MATLAB function “H = fspecial(’gaussian’, h,σ)” to create the Gauss kernel and the MATLAB function “G=imfilter(IMG, H)” to create the smooth version of image “IMG”. Two parameters h and σ are needed to be selected in the function “fspecial”. Numerical experiments show that the proposed filter is not sensitive to both parameters. We use h = 3 and σ = 1.5 for all experiments presented in this paper. It should be noticed that the denoising results can be improved by using h = 5 for extremely high level impulse noise. α = 2 is selected based on empirical observation for better performance.

The MATLAB function “medfilt2” is used for the median filter in step 5. The filter window ω of “medfilt2” depends slightly on the noise level. We can simply choose ω = 3 for noise level s < 50% and choose ω = 5 for s ≥ 50%. The convolution operator in step 9 is set precisely the same as that of in the Perona–Malik type diffusivity. At last, we observe that the iteration number N increases with the increasing noise level s. We set N = 20 × s.

3.2 Image denoising results

We now present the denoising results of all methods when test images are corrupted by 10% − 60% random-valued noise.

Table 2 lists the PSNR values and SSIM values of denoised images for all methods, where the highest values are shown in boldface. The PDE-based method NSDD performs not bad when the noise level is high. However, with the decrease of the noise level, the performance of NSDD drops rapidly. The variational method AOP has higher PSNR and SSIM values than another variational method L0TV for low noise level. This is because the noise candidate set \(\mathcal {D}\) is updated in AOP. While with the increase of the noise level, the advantage of the l0-norm in L0TV begins to emerge, which leads to higher PSNR and SSIM values than AOP. Nonlocal means filters SAFE and ROR-NLM both outperform variational methods for high noise level. And the results of SAFE are slightly better than the results of ROR-NLM. It can be observed that the proposed model has the highest PSNR and SSIM values in most cases.

Table 2 PSNR and SSIM values of restoration results for images corrupted by random-valued noise
Full size table

The visual results of different methods for four test images corrupted by 60% random-valued noise is shown in Figs. 5 and 6. NSDD restores edges well. However, impulse noise is removed incompletely. Both AOP and L0TV use the TV regularization. Consequently, edges are well restored. They also cause the over smoothness of homogeneous regions. The utilization of the nonlocal means filter leads to good visual equality, especially for Mandrill image that contains texture information. The proposed equation has the best compromise between noise suppression and dege/detail preserving.

Fig. 5
figure 5

Restoration results of different methods for test images Pepper, Boat and Bridge corrupted by 60% random-valued noise. From top to bottom: NSDD, AOP, L0TV, ROR-NLM, SAFE and Algorithm 1

Full size image
Fig. 6
figure 6

Restoration results of different methods for test images Mandrill, Couple and Plane corrupted by 60% random-valued noise. From top to bottom: NSDD, AOP, L0TV, ROR-NLM, SAFE and Algorithm 1

Full size image

The main advantage of the proposed equation is the ability to remove random-valued noise that is difficult to be detected. In Fig. 7, we observe that small impulse noise has remained in the result of the two-stage method ROR-NLM. SAFE, which uses the iterative structure-adaptive fuzzy estimation, can also not remove small impulse noise perfectly. No noise is observed in the result of the proposed equation.

Fig. 7
figure 7

Denoising results of ROR-NLM, SAFE and Algorithm 1 for restoring Boat image corrupted by 60% random-valued noise. The displayed region is (358 : 428,183 : 253)

Full size image

4 Conclusion and discussion

A nonlinear diffusion equation with the regularized Perona–Malik diffusivity and a gray level based diffusivity has been proposed for the removal of random-valued impulse noise in images. The gray level based diffusivity has been constructed to estimate the amplitude of the noise, which is particularly suitable for removing random-valued noise. Numerical experiments showed that our equation removes random-valued noise that is difficult to be detected and outperforms recent PDE-based methods and nonlocal methods.

The proposed equation utilizes local information (i.e., four nearest pixels) for the restoration. It is not surprising that it has unsatisfied results compared to the nonlocal methods in particular cases. Nonlocal diffusion model that restores noisy images by the high degree of redundancy of natural images, is a straightforward generalization of the classical diffusion model. By replacing the classical diffusion operator in the proposed equation by the corresponding nonlocal diffusion operator, we expect to deduce a new model that inherits the advantage of nonlocal methods and has better denoising performance.