# Salt and Pepper Noise Removal with Noise Detection and a Patch-Based Sparse Representation

Authors: Di Guo; Xiaobo Qu; Xiaofeng Du; Keshou Wu; Xuhui Chen
Journal: Advances in Multimedia
 (2014)

---

## Abstract

Images may be corrupted by salt and pepper impulse noise due to noisy sensors or channel transmission errors. A denoising method by detecting noise candidates and enforcing image sparsity with a patch-based sparse representation is proposed. First, noise candidates are detected and an initial guide image is obtained via an adaptive median filtering; second, a patch-based sparse representation is learnt from this guide image; third, a weightedl1-l1 regularization method is proposed to penalize the noise candidates heavier than the rest of pixels. An alternating direction minimization algorithm is derived to solve the regularization model. Experiments are conducted for 30%∼90% impulse noise levels, and the simulation results demonstrate that the proposed method outperforms total variation and Wavelet in terms of preserving edges and structural similarity to the noise-free images.


---

## Body

## 1. Introduction

Noise is an evitable problem in image processing and computer vision. Images may be corrupted by impulse noise due to noisy sensors or channel transmission errors [1]. To improve the image quality, it is important to remove these noises.Median [1] or adaptive median filtering (AMF) [2] is usually adopted to remove the impulse noise. Noise detection and pixel restoration are two main steps in impulse noise removal. In noise detection stage, noise candidates may be found in the spatial domain [2] or multiscale decomposition domain [3, 4]. In the spatial domain, the size of local window is adaptively set [5, 6] in a noise-aware way and a hypergraph can be defined as model relationship of a central pixel and its neighbor pixels [7]. In the multiscale decomposition domain, Wavelet transform has been adopted [3]. In pixel restoration stage, recovery methods can be applied in the spatial domain [2] or multiscale decomposition domain [4, 8]. In the spatial domain, pixels will be better recovered in the optimal direction if directional edges are taken into account [9, 10]. Fuzzy rules are also applied both in the spatial [11] or Wavelet domain [8] to deal with the uncertainty of inaccurate recovery. When 50% pixels are corrupted by impulse noise, methods in [9, 10] have shown promising results, but these methods produce unsatisfactory images when noise level is higher than 50%. Methods in both [4, 5] restored reasonable images when 90% pixels are contaminated.Images are recovered much better than typical impulse denoising methods if appropriate sparsity priors are applied [12–14]. Beyond traditional multiscale decomposition methods, for example, Wavelet [3, 4, 12], sparse representations of image model wider image priors such as geometric directions [15–17] or redundancy [18] among images. In impulse noise removal, noise is detected by a sparse representation in identity matrix [13], or images are restored by enforcing their sparsity in Wavelet domain [12] or finite difference domain [19]. Rather than using fixed basis or dictionary, data-driven dictionaries have been proposed to provide an adaptive sparse representation for a specific image [20, 21]. To further reduce the reconstruction error in impulse noise removal, adaptive sparse representation has been explored under the framework of dictionary learning [14, 22]. However, the dictionary training in iterations is time consuming.Recently, a fast adaptive sparse representation of images, called patch-based nonlocal operator (PANO) [23], has been proposed to make use of image self-similarity [24–26]. PANO searches similar patches in neighborhood; thus, the training phase is relatively fast. In our previous work, PANO was explored to reconstruct images from impulse noise corruption using an l1-l1 regularization model. By learning the similarity from images restored by median filtering, both strong edges and textures are recovered much better than total variation or Wavelet [27]. However, the denoising performance dropped when 50% pixels are contaminated with impulse noise.In our experiments, we found two reasons for the reduction of denoising performance. First, many image structures are lost in the guide image thus affect learning the proper similarity. Second, noise-free pixels are also changed since the original PANO-basedl1-l1 regularization model did not distinguish the noisy or noise-free pixels. Based on the two reasons, adaptive median filtering [2] is used to obtain a good guide image and to detect the noise candidates first. And a new model penalizing the noisy pixels more than noise-free ones is proposed to preserve the noise-free pixels.In this paper, a novel denoising framework is proposed for salt and pepper noise removal based on adaptive sparse representation of similar image patches. The contributions of this paper are summarized as follows.(1)
Detect the noise candidate first, and only noisy pixels are heavily penalized in a weightedl1-l1 regularization model.(2)
Improve the similarity learning with a proper guide image, thus producing more accurate adaptive sparse representation of image patches.(3)
A numerical algorithm, alternating direction minimization with continuation, is developed to solve the new model accordingly.The rest of this paper is organized as follows. The original PANO-basedl1-l1 regularization model will be reviewed in Section 2.1. The new denoising approach is presented in Section 2.2. Experiments and results analysis are given in Section 3. Finally, Section 4 presents the conclusions.


## 2. Method

### 2.1. Review of PANO-Based Impulse Noise Removal Method

In the original PANO-based noise removal method [27], the image x is recovered from noisy observation y by solving a l1-l1 minimization model
(1)min⁡xλ∥y-x∥1+∑j=1J∥Ajx∥1,
where ∑j=1J∥Ajx∥1 promotes the sparsity of J groups of similar patches using PANO Aj(j=1,2,…,J), ∥y-x∥1 removes the outliers, that is, impulse noise in images, and λ balances between the sparsity and outliers removal. A larger λ should be assigned since it is expected to smoothen images harder for heavier noise.However, all the pixels of noisy observationy are penalized equally. This may change the pixels uncorrupted by noise. If the noise candidates are detected, the denoising performance is expected to be improved [28].


### 2.2. PANO-Based Impulse Noise Removal with Noise Detection and a Weightedl1-l1 Regularization Model (PANO-ND)

In the proposed method, the salt and pepper noise are detected first and the locations of noise candidates are marked. With the location information, a weightedl1-l1 regularization model is proposed to preserve the noise-free pixels while removing noise. We call the proposed method PANO with noise detection (PANO-ND).


#### 2.2.1. Noise Detection

For the salt and pepper noise, the adaptive median filter (AMF) can be used to detect the noise candidatesyi,j and replace each yi,j with the median of the pixels in a local window [2]. As shown in Figure 2, an adaptive structure of the filter ensures that most of the impulse noise is detected even at a high noise level provided that the window size is large enough [28].LetSi,jw be a window of size w×w centered at (i,j), and let wmax⁡×wmax⁡ be the maximum allowable window size. Initialize w=3 and compute Si,jmin⁡,w,Si,jmed,w,Si,jmax⁡,w which denote the minimum, median, and maximum of the pixel values in Si,jw, respectively. When Si,jmed,w∈(Si,jmin⁡,w,Si,jmax⁡,w), that is, impulse noise does not dominate the window, we can judge yi,j is not a noise candidate if yi,j∈(Si,jmin⁡,w,Si,jmax⁡,w), else we replace yi,j by Si,jmed,w (Median Filtering); that is,
(2)y~i.j={yi,j,ifyi,j∈(Si,jmin⁡,w,Si,jmax⁡,w)Si,jmed,w,else.
When Si,jmed,w∉(Si,jmin⁡,w,Si,jmax⁡,w), that is, impulse noise dominates this window, we set w=w+2 (Adaptive) and repeat the above steps.Whenw≥wmax⁡, we replace yi,j by Si,jmed,wmax⁡ (the algorithm is terminated when the maximum window size is reached). Notice that except for the noise candidates that are replaced by the median Si,jmed,w, the remaining pixels are left unchanged. The flowchart of AMF is summarized in Figure 3. In the proposed scheme, the noise candidates are detected using AMF.The locations of detected noise candidates are stored in a setΩ whose complementary set Ω- stores locations of the rest of pixels. For an image x∈ℝn×1, Ω and Ω- will be used to generate a diagonal matrix W∈ℝn×n whose entries stand for weights on pixels in the regularization model.


#### 2.2.2. Weightedl1-l1 Regularization Model

In this paper, a weightedl1-l1 regularization model is proposed to solve the image reconstruction problem as follows:
(3)x^=argmin⁡xλ∥W(y-x)∥1+∑j=1J∥Ajx∥1,
where y is the noisy observation and x is the original image to be recovered; ∑j=1J∥Ajx∥1 promotes the sparsity of J groups of similar patches using PANO Aj(j=1,2,…,J); ∥y-x∥1 removes the outliers, that is, impulse noise in images; W is a diagonal matrix whose entries stand for weights on pixels; λ balances between the sparsity and outliers removal.Letwm be the mth diagonal entry of W; a small weight wi(i∈Ω) is assigned for noise candidates and a large weight wk(k∈Ω¯) for the rest of pixels; that is,
(4)wi∈Ω>wk∈Ω¯,
where Ω and Ω¯ contain the indexes of noise candidates and the rest of pixels, respectively. In this paper, we set wk∈Ω¯=1 for simplicity. The effect of wi∈Ω will be analyzed in Section 3.3.Compared with (1), noise candidates are distinguished from pixels and are expected to be suppressed according to the new model in (3). Therefore, the rest of the pixels are relatively preserved in the image reconstruction.To solve the new regularization model, the alternating direction minimization with continuation [23] is modified to solve the minimization problem with two l1 regularization terms. A relaxed unconstraint form of (3) is written as
(5)min⁡x,α,z∑j=1J(∥αj∥1+β2∥αj-Ajx∥22)+λ(∥z∥1+β2∥z-W(y-x)∥22).The solution of (5) approaches that of (3) as β→∞ [7]. For practical implementation, as β gradually increases, we use the previous solution as a “warm start” for the next alternating optimization.Whenβ is fixed, (5) can be solved in an alternating fashion as follows.(1)
For a fixedx, solve
(6)min⁡α∑j=1J(∥αj∥1+β2∥αj-Ajx∥22),
whose solution is obtained via soft thresholding for each αj(7)α^j=S(Ajx,1β)=max⁡(|Ajx|-1β,0)Ajx|Ajx|,
and solve
(8)min⁡z∥z∥1+β2∥z-W(y-x)∥22,
whose solution is obtained via soft thresholding
(9)z^=S(W(y-x),1β)=max⁡(|W(y-x)|-1β,0)W(y-x)|W(y-x)|.(2)
For fixedαj(j=1,2,…,J) and z, solve
(10)min⁡x∑j=1J∥αj-Ajx∥22+λ∥z-W(y-x)∥22,
which can be written as
(11)min⁡x∑j=1J∥αj-Ajx∥22+λ∥Wy-z-Wx∥22.
The minimizer of (11) is given by the solution of the normal equation
(12)(∑j=1JAjTAj+λWTW)x=∑j=1JAjTαj+λWT(Wy-z),
which can be simplified as
(13)(O+λWTW)x=vα+λWTWy-λWTz,
and the term  vα=∑j=1JAjTαj is an assembled image reconstructed from patches in all groups. One can use conjugate gradient to solve (13).The algorithm is summarized in Algorithm1 where x is updated in the subsequent iterations by following Step 1, 2, and 3.Algorithm 1:PANO-based salt and pepper noise removal with noise detection.
Initialization: Input the noise contaminated image y, the PANO Aj(j=1,…,J), regularization parameter λ and tolerance of
inner loopμ=10-3. Initialize x=y, z=0, αj=0 for j=1,2,…,J, β=24 and xlast=0.
Main:
While  β≤214,
Step  1.  solve (7) to get αj;
Step  2.  solve (9) to get z;
Step  3.  solve (13) to get x;
Step  4.  If ∥xlast-x∥>μ∥xlast∥, go to Step  1;
otherwise, go toStep  5;
Step  5.β←2β, x^←x, go to Step  1.
End While
Output:
x
^


## 2.1. Review of PANO-Based Impulse Noise Removal Method

In the original PANO-based noise removal method [27], the image x is recovered from noisy observation y by solving a l1-l1 minimization model
(1)min⁡xλ∥y-x∥1+∑j=1J∥Ajx∥1,
where ∑j=1J∥Ajx∥1 promotes the sparsity of J groups of similar patches using PANO Aj(j=1,2,…,J), ∥y-x∥1 removes the outliers, that is, impulse noise in images, and λ balances between the sparsity and outliers removal. A larger λ should be assigned since it is expected to smoothen images harder for heavier noise.However, all the pixels of noisy observationy are penalized equally. This may change the pixels uncorrupted by noise. If the noise candidates are detected, the denoising performance is expected to be improved [28].


## 2.2. PANO-Based Impulse Noise Removal with Noise Detection and a Weightedl1-l1 Regularization Model (PANO-ND)

In the proposed method, the salt and pepper noise are detected first and the locations of noise candidates are marked. With the location information, a weightedl1-l1 regularization model is proposed to preserve the noise-free pixels while removing noise. We call the proposed method PANO with noise detection (PANO-ND).


### 2.2.1. Noise Detection

For the salt and pepper noise, the adaptive median filter (AMF) can be used to detect the noise candidatesyi,j and replace each yi,j with the median of the pixels in a local window [2]. As shown in Figure 2, an adaptive structure of the filter ensures that most of the impulse noise is detected even at a high noise level provided that the window size is large enough [28].LetSi,jw be a window of size w×w centered at (i,j), and let wmax⁡×wmax⁡ be the maximum allowable window size. Initialize w=3 and compute Si,jmin⁡,w,Si,jmed,w,Si,jmax⁡,w which denote the minimum, median, and maximum of the pixel values in Si,jw, respectively. When Si,jmed,w∈(Si,jmin⁡,w,Si,jmax⁡,w), that is, impulse noise does not dominate the window, we can judge yi,j is not a noise candidate if yi,j∈(Si,jmin⁡,w,Si,jmax⁡,w), else we replace yi,j by Si,jmed,w (Median Filtering); that is,
(2)y~i.j={yi,j,ifyi,j∈(Si,jmin⁡,w,Si,jmax⁡,w)Si,jmed,w,else.
When Si,jmed,w∉(Si,jmin⁡,w,Si,jmax⁡,w), that is, impulse noise dominates this window, we set w=w+2 (Adaptive) and repeat the above steps.Whenw≥wmax⁡, we replace yi,j by Si,jmed,wmax⁡ (the algorithm is terminated when the maximum window size is reached). Notice that except for the noise candidates that are replaced by the median Si,jmed,w, the remaining pixels are left unchanged. The flowchart of AMF is summarized in Figure 3. In the proposed scheme, the noise candidates are detected using AMF.The locations of detected noise candidates are stored in a setΩ whose complementary set Ω- stores locations of the rest of pixels. For an image x∈ℝn×1, Ω and Ω- will be used to generate a diagonal matrix W∈ℝn×n whose entries stand for weights on pixels in the regularization model.


### 2.2.2. Weightedl1-l1 Regularization Model

In this paper, a weightedl1-l1 regularization model is proposed to solve the image reconstruction problem as follows:
(3)x^=argmin⁡xλ∥W(y-x)∥1+∑j=1J∥Ajx∥1,
where y is the noisy observation and x is the original image to be recovered; ∑j=1J∥Ajx∥1 promotes the sparsity of J groups of similar patches using PANO Aj(j=1,2,…,J); ∥y-x∥1 removes the outliers, that is, impulse noise in images; W is a diagonal matrix whose entries stand for weights on pixels; λ balances between the sparsity and outliers removal.Letwm be the mth diagonal entry of W; a small weight wi(i∈Ω) is assigned for noise candidates and a large weight wk(k∈Ω¯) for the rest of pixels; that is,
(4)wi∈Ω>wk∈Ω¯,
where Ω and Ω¯ contain the indexes of noise candidates and the rest of pixels, respectively. In this paper, we set wk∈Ω¯=1 for simplicity. The effect of wi∈Ω will be analyzed in Section 3.3.Compared with (1), noise candidates are distinguished from pixels and are expected to be suppressed according to the new model in (3). Therefore, the rest of the pixels are relatively preserved in the image reconstruction.To solve the new regularization model, the alternating direction minimization with continuation [23] is modified to solve the minimization problem with two l1 regularization terms. A relaxed unconstraint form of (3) is written as
(5)min⁡x,α,z∑j=1J(∥αj∥1+β2∥αj-Ajx∥22)+λ(∥z∥1+β2∥z-W(y-x)∥22).The solution of (5) approaches that of (3) as β→∞ [7]. For practical implementation, as β gradually increases, we use the previous solution as a “warm start” for the next alternating optimization.Whenβ is fixed, (5) can be solved in an alternating fashion as follows.(1)
For a fixedx, solve
(6)min⁡α∑j=1J(∥αj∥1+β2∥αj-Ajx∥22),
whose solution is obtained via soft thresholding for each αj(7)α^j=S(Ajx,1β)=max⁡(|Ajx|-1β,0)Ajx|Ajx|,
and solve
(8)min⁡z∥z∥1+β2∥z-W(y-x)∥22,
whose solution is obtained via soft thresholding
(9)z^=S(W(y-x),1β)=max⁡(|W(y-x)|-1β,0)W(y-x)|W(y-x)|.(2)
For fixedαj(j=1,2,…,J) and z, solve
(10)min⁡x∑j=1J∥αj-Ajx∥22+λ∥z-W(y-x)∥22,
which can be written as
(11)min⁡x∑j=1J∥αj-Ajx∥22+λ∥Wy-z-Wx∥22.
The minimizer of (11) is given by the solution of the normal equation
(12)(∑j=1JAjTAj+λWTW)x=∑j=1JAjTαj+λWT(Wy-z),
which can be simplified as
(13)(O+λWTW)x=vα+λWTWy-λWTz,
and the term  vα=∑j=1JAjTαj is an assembled image reconstructed from patches in all groups. One can use conjugate gradient to solve (13).The algorithm is summarized in Algorithm1 where x is updated in the subsequent iterations by following Step 1, 2, and 3.Algorithm 1:PANO-based salt and pepper noise removal with noise detection.
Initialization: Input the noise contaminated image y, the PANO Aj(j=1,…,J), regularization parameter λ and tolerance of
inner loopμ=10-3. Initialize x=y, z=0, αj=0 for j=1,2,…,J, β=24 and xlast=0.
Main:
While  β≤214,
Step  1.  solve (7) to get αj;
Step  2.  solve (9) to get z;
Step  3.  solve (13) to get x;
Step  4.  If ∥xlast-x∥>μ∥xlast∥, go to Step  1;
otherwise, go toStep  5;
Step  5.β←2β, x^←x, go to Step  1.
End While
Output:
x
^


## 2.2.1. Noise Detection

For the salt and pepper noise, the adaptive median filter (AMF) can be used to detect the noise candidatesyi,j and replace each yi,j with the median of the pixels in a local window [2]. As shown in Figure 2, an adaptive structure of the filter ensures that most of the impulse noise is detected even at a high noise level provided that the window size is large enough [28].LetSi,jw be a window of size w×w centered at (i,j), and let wmax⁡×wmax⁡ be the maximum allowable window size. Initialize w=3 and compute Si,jmin⁡,w,Si,jmed,w,Si,jmax⁡,w which denote the minimum, median, and maximum of the pixel values in Si,jw, respectively. When Si,jmed,w∈(Si,jmin⁡,w,Si,jmax⁡,w), that is, impulse noise does not dominate the window, we can judge yi,j is not a noise candidate if yi,j∈(Si,jmin⁡,w,Si,jmax⁡,w), else we replace yi,j by Si,jmed,w (Median Filtering); that is,
(2)y~i.j={yi,j,ifyi,j∈(Si,jmin⁡,w,Si,jmax⁡,w)Si,jmed,w,else.
When Si,jmed,w∉(Si,jmin⁡,w,Si,jmax⁡,w), that is, impulse noise dominates this window, we set w=w+2 (Adaptive) and repeat the above steps.Whenw≥wmax⁡, we replace yi,j by Si,jmed,wmax⁡ (the algorithm is terminated when the maximum window size is reached). Notice that except for the noise candidates that are replaced by the median Si,jmed,w, the remaining pixels are left unchanged. The flowchart of AMF is summarized in Figure 3. In the proposed scheme, the noise candidates are detected using AMF.The locations of detected noise candidates are stored in a setΩ whose complementary set Ω- stores locations of the rest of pixels. For an image x∈ℝn×1, Ω and Ω- will be used to generate a diagonal matrix W∈ℝn×n whose entries stand for weights on pixels in the regularization model.


## 2.2.2. Weightedl1-l1 Regularization Model

In this paper, a weightedl1-l1 regularization model is proposed to solve the image reconstruction problem as follows:
(3)x^=argmin⁡xλ∥W(y-x)∥1+∑j=1J∥Ajx∥1,
where y is the noisy observation and x is the original image to be recovered; ∑j=1J∥Ajx∥1 promotes the sparsity of J groups of similar patches using PANO Aj(j=1,2,…,J); ∥y-x∥1 removes the outliers, that is, impulse noise in images; W is a diagonal matrix whose entries stand for weights on pixels; λ balances between the sparsity and outliers removal.Letwm be the mth diagonal entry of W; a small weight wi(i∈Ω) is assigned for noise candidates and a large weight wk(k∈Ω¯) for the rest of pixels; that is,
(4)wi∈Ω>wk∈Ω¯,
where Ω and Ω¯ contain the indexes of noise candidates and the rest of pixels, respectively. In this paper, we set wk∈Ω¯=1 for simplicity. The effect of wi∈Ω will be analyzed in Section 3.3.Compared with (1), noise candidates are distinguished from pixels and are expected to be suppressed according to the new model in (3). Therefore, the rest of the pixels are relatively preserved in the image reconstruction.To solve the new regularization model, the alternating direction minimization with continuation [23] is modified to solve the minimization problem with two l1 regularization terms. A relaxed unconstraint form of (3) is written as
(5)min⁡x,α,z∑j=1J(∥αj∥1+β2∥αj-Ajx∥22)+λ(∥z∥1+β2∥z-W(y-x)∥22).The solution of (5) approaches that of (3) as β→∞ [7]. For practical implementation, as β gradually increases, we use the previous solution as a “warm start” for the next alternating optimization.Whenβ is fixed, (5) can be solved in an alternating fashion as follows.(1)
For a fixedx, solve
(6)min⁡α∑j=1J(∥αj∥1+β2∥αj-Ajx∥22),
whose solution is obtained via soft thresholding for each αj(7)α^j=S(Ajx,1β)=max⁡(|Ajx|-1β,0)Ajx|Ajx|,
and solve
(8)min⁡z∥z∥1+β2∥z-W(y-x)∥22,
whose solution is obtained via soft thresholding
(9)z^=S(W(y-x),1β)=max⁡(|W(y-x)|-1β,0)W(y-x)|W(y-x)|.(2)
For fixedαj(j=1,2,…,J) and z, solve
(10)min⁡x∑j=1J∥αj-Ajx∥22+λ∥z-W(y-x)∥22,
which can be written as
(11)min⁡x∑j=1J∥αj-Ajx∥22+λ∥Wy-z-Wx∥22.
The minimizer of (11) is given by the solution of the normal equation
(12)(∑j=1JAjTAj+λWTW)x=∑j=1JAjTαj+λWT(Wy-z),
which can be simplified as
(13)(O+λWTW)x=vα+λWTWy-λWTz,
and the term  vα=∑j=1JAjTαj is an assembled image reconstructed from patches in all groups. One can use conjugate gradient to solve (13).The algorithm is summarized in Algorithm1 where x is updated in the subsequent iterations by following Step 1, 2, and 3.Algorithm 1:PANO-based salt and pepper noise removal with noise detection.
Initialization: Input the noise contaminated image y, the PANO Aj(j=1,…,J), regularization parameter λ and tolerance of
inner loopμ=10-3. Initialize x=y, z=0, αj=0 for j=1,2,…,J, β=24 and xlast=0.
Main:
While  β≤214,
Step  1.  solve (7) to get αj;
Step  2.  solve (9) to get z;
Step  3.  solve (13) to get x;
Step  4.  If ∥xlast-x∥>μ∥xlast∥, go to Step  1;
otherwise, go toStep  5;
Step  5.β←2β, x^←x, go to Step  1.
End While
Output:
x
^


## 3. Results

The proposed method is compared with AMF [2], sparsity-based denoising methods including TV [28, 29] and dual-tree complex Wavelet [12]. A suffix “ND” means that noise detection is applied in denoising. The proposed method PANO-ND is also compared with the original PANO [23]. Typical parameters of PANO-ND are the same as [23], including 16 similar patches in a group, patch size 8×8 and search region size 39×39. The similarity is first learnt form a denoised image using adaptive median filter, and then learnt twice from the denoised image for further reconstructions.To quantitatively measure the denoising performance, the peak signal-to-noise ratio (PSNR) and mean measure of structural similarity (MSSIM) [30] are used. PSNR mainly measures the average pixel difference of the denoised and noise-free images. MSSIM focuses on the image structure consistency of denoised images to the original image. Higher PSNR and MSSIM mean better denoising performance. The regularization parameter λ of all sparsity-based methods is optimized to achieve the highest MSSIMs. Maximum window size of AMF is chosen as 39×39 since its performance is stable under all noise levels [28].


### 3.1. Effect of Noise Detection

Although edges are reconstructed better by exploring the image self-similarity in the original PANO (Figure1(d)), all sparsity-based denoising methods fail to recover the image structures (Figures 4(d)–4(f)) when 50% or more pixels are corrupted without noise detection. By assigning noise candidates with a small weight, for example, 0.1 in experiments, all these methods have greatly improved the edge reconstruction (Figures 4(g)–4(i)). Thus, noise detection is necessary for salt and pepper noise removal.Restored image from 50% salt and pepper noise using median filtering and PANO. (a) Noise-free image, (b) noisy image with 50% salt and pepper noise, and (c) and (d) restored images using median filtering and PANO.
(a)
(b)
(c)
(d)Figure 2
Window size of adaptive median filter (Initializew=3).Figure 3
Flowchart of adaptive median filter.ReconstructedBarbaraimages from 50% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, and (c)–(i) reconstructed images using AMF, TV, Wavelet, PANO, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)PANO-ND produces the most faithful images (Figure4(i)) by clearly preserving edges ofBarbara image among these methods. ForHouse image (Figure 5) with more flat regions, between which exists a longer strong edge such as eave of the house, or pole inBoat image (Figure 6), they have more similar image groups; thus, the proposed method shows more advantage visually in restoring these edges.ReconstructedHouse images from 50% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, and (c)–(i) reconstructed images using AMF, TV, Wavelet, PANO, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)ReconstructedBoat images from 50% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(i) reconstructed images using AMF, TV, Wavelet, PANO, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)In Table1, we compared the performance of the AMF, Wavelet, PANO, and these methods with noise detection and weighted l1-l1 (w=0.1). The proposed method achieves highest PSNRs and MSSIMs, indicating it performs better than the already existing ones. Therefore, PANO-ND significantly improves the edges and achieves better quantitative measures than other methods.Table 1
Quantitative measures for 50% salt and pepper impulse noise.
Images
Quantitative measure
Methods
l
1-l1
Noise detection and weightedl1-l1
TV
Wavelet
PANO
AMF
TV
Wavelet
PANO
Barbara
PSNR
32.30
32.47
32.47
34.61
35.35
34.96
36.18
MSSIM
0.6687
0.8884
0.7486
0.8080
0.8647
0.8991
0.9262
House
PSNR
35.52
32.14
35.87
37.61
39.32
37.08
39.98
MSSIM
0.8096
0.7551
0.8537
0.8676
0.9293
0.9172
0.9385
Boat
PSNR
34.38
31.75
34.12
36.33
37.88
36.34
37.99
MSSIM
0.7797
0.7167
0.822
0.8715
0.9266
0.9121
0.9367


### 3.2. Different Noise Levels

How the performance varies for different noise levels is discussed. All the compared methods are with noise detection since its importance has been demonstrated. The denoising performance is quantitatively compared in Figure7.Quantitative measure at different noise levels. (a)–(c) PSNRs ofBarbara,House, andBoatimages, respectively; (d)–(f) MSSIMs ofBarbara,House, andBoatimages, respectively.
(a)
(b)
(c)
(d)
(e)
(f)Under all noise levels, TV-ND achieves higher PSNRs and MSSIMs than AMF. Wavelet-ND obtains higher PSNRs than AMF for less than 50% noise and lower PSNRs when the noise level is further increased. But the MSSIMs of Wavelet-ND are consistently larger than AMF for all noise levels, which implies that the image structures are better preserved. Comparing Wavelet-ND with TV-ND, the former leads to higher MSSIMs forBarbara image (Figure 7(d)) embedding fruitful textures while the latter obtains higher MSSIMs forHouse (Figure 7(e)) andBoat (Figure 7(f)) with more flat regions. The repeated small and directional patterns in clothes ofBarbara image are usually considered as texture [31, 32]. Due to the directional Wavelet functions of the adopted dual-tree complex Wavelet, the Wavelet transform provides sparse representation of texture [33, 34]. On the contrary, total variation is good at sparsifying piece-wise constant image features [32, 35] and thus favors recovering flat regions inHouse andBoat images. Texture is easy to be lost when total variation is applied in noise removal [36]. Therefore, TV-ND is more suitable for images with flat regions while Wavelet-ND is better for image with fruitful textures.The proposed PANO-ND outperforms both TV-ND and Wavelet-ND in terms of MSSIMs. PANO-ND achieves larger or comparable PSNRs when the noise level is below 90%. Besides, higher MSSIMs using PNAO-ND imply that image structures recovered by PANO-ND are more consistent to those of noise-free images. As shown in Figures8, 9, and 10, edges are recovered much clearer using PANO-ND than TV-ND. When the noise level approaches 90%, an extremely heavy noise, the PSNRs (lower than 34 dB) and MSSIMs (lower than 0.75) performance of all the methods are unsatisfactory since very limited information is available.ReconstructedBarbaraimages from 70% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(f) reconstructed images using AMF, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)ReconstructedHouseimages from 70% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(f) reconstructed images using AMF, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)ReconstructedBoatimages from 70% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(f) reconstructed images using AMF, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)


### 3.3. Effect of Weight for Noise Candidates

A smallerwi∈Ω should be assigned to achieve better denoising performance. As shown in Figure 11, when wi∈Ω becomes larger than 0.1, the quantitative measures reduce dramatically. One explanation is that, when wi∈Ω and wk∈Ω¯ are comparable, meaning 0.1<wi∈Ω/wk∈Ω¯<1, the penalization on noise candidates and the rest of pixels are in the same order; thus, noise candidates are not heavily suppressed in reconstruction. Therefore, wi∈Ω≤10-1 is suggested.Quantitative measures versus the weight for noise candidates. Note:Houseimage with 70% salt and pepper impulse noise is used in simulation and λ is 2.6.
(a)
(b)


### 3.4. Complexity Analysis

In this section, we tested the computation time of different methods in Table2. The AMF is the fastest method, while PANO-ND is the most time-consuming method. Wavelet-ND runs faster than TV-ND but much slower than AMF.Table 2
Computational time of different methods (units: seconds).
Images
Image size
Methods
AMF
TV-ND
Wavelet-ND
PANO-ND
1st recon.
2nd recon.
3rd recon.
Total
Barbara
512
×
512
0.37
49.21
11.34
40.15
28.89
28.86
97.90
Boat
512
×
512
0.37
42.32
10.39
37.56
25.80
25.74
89.10
House
256
×
256
0.07
7.61
3.00
9.19
6.29
6.19
21.67
Note: computations were performed on 2 Cores 2.7 GHz CPU desktop computer with 4 GB RAM. The alternating direction minimization with continuation is used to solve TV-ND, Wavelet-ND, and PANO-ND.Figure12 shows the improvement in the MSSIM scores of these methods with increased complexity. The curve of PANO-ND undergoes 3 peaks because the nonlocal similarity is learnt followed by reconstruction for 3 times. As to the first peak, PANO-ND gets higher or at least comparable MSSIM scores than other methods when the initial guide image is obtained using AMF. When this reconstructed image is further adopted as a guide image, PANO-ND keeps on achieving even higher MSSIM on the next two peaks forBarbara image. ForBoatandHouseimage, it seems enough to only perform PANO-based reconstruction once.Figure11 MSSIMs versus computation time from 50% salt and pepper noise. (a), (c), and (e) are MSSIMs forBarbara,Boat, andHouse images and (b), (d), and (f) are the zoom out part of (a), (c), and (e) when MSSIMs are greater than 0.8.
(a)
(b)
(c)
(d)
(e)
(f)


### 3.5. Effect ofλ

Effect ofλ is discussed in Figure 13. MSSIMs versus λ are evaluated in Figure 13(a). With the increasing of λ, the MSSIMs increase first. Then MSSIMs hold similar for a range of λ (λ∈[2,4] for 50% noise level). When λ becomes too large (λ>4 for 50% noise level), the MSSIMs decrease significantly. Reconstructed images with typical λ are shown in Figures 13(b)–13(d). The optimal result is achieved when λ=2. The λ=1 leads to oversmooth image in Figure 13(c) since a smaller λ encourages higher sparsity and fine image structures are lost. The λ=7 results in some noise are not removed since the consistency between a noisy image y and its denoised version x is highly enforced. How to set an optimal λ is still unsolved which would be an interesting future work.Effect of regularization parameterλ for the proposed approach. (a) The curve of MSSIM versus λ; (b)–(d) reconstructed images when λ=2,1,7, respectively. Note: tests are performed at 50% impulse noise level.
(a)
(b)
(c)
(d)


## 3.1. Effect of Noise Detection

Although edges are reconstructed better by exploring the image self-similarity in the original PANO (Figure1(d)), all sparsity-based denoising methods fail to recover the image structures (Figures 4(d)–4(f)) when 50% or more pixels are corrupted without noise detection. By assigning noise candidates with a small weight, for example, 0.1 in experiments, all these methods have greatly improved the edge reconstruction (Figures 4(g)–4(i)). Thus, noise detection is necessary for salt and pepper noise removal.Restored image from 50% salt and pepper noise using median filtering and PANO. (a) Noise-free image, (b) noisy image with 50% salt and pepper noise, and (c) and (d) restored images using median filtering and PANO.
(a)
(b)
(c)
(d)Figure 2
Window size of adaptive median filter (Initializew=3).Figure 3
Flowchart of adaptive median filter.ReconstructedBarbaraimages from 50% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, and (c)–(i) reconstructed images using AMF, TV, Wavelet, PANO, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)PANO-ND produces the most faithful images (Figure4(i)) by clearly preserving edges ofBarbara image among these methods. ForHouse image (Figure 5) with more flat regions, between which exists a longer strong edge such as eave of the house, or pole inBoat image (Figure 6), they have more similar image groups; thus, the proposed method shows more advantage visually in restoring these edges.ReconstructedHouse images from 50% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, and (c)–(i) reconstructed images using AMF, TV, Wavelet, PANO, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)ReconstructedBoat images from 50% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(i) reconstructed images using AMF, TV, Wavelet, PANO, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)In Table1, we compared the performance of the AMF, Wavelet, PANO, and these methods with noise detection and weighted l1-l1 (w=0.1). The proposed method achieves highest PSNRs and MSSIMs, indicating it performs better than the already existing ones. Therefore, PANO-ND significantly improves the edges and achieves better quantitative measures than other methods.Table 1
Quantitative measures for 50% salt and pepper impulse noise.
Images
Quantitative measure
Methods
l
1-l1
Noise detection and weightedl1-l1
TV
Wavelet
PANO
AMF
TV
Wavelet
PANO
Barbara
PSNR
32.30
32.47
32.47
34.61
35.35
34.96
36.18
MSSIM
0.6687
0.8884
0.7486
0.8080
0.8647
0.8991
0.9262
House
PSNR
35.52
32.14
35.87
37.61
39.32
37.08
39.98
MSSIM
0.8096
0.7551
0.8537
0.8676
0.9293
0.9172
0.9385
Boat
PSNR
34.38
31.75
34.12
36.33
37.88
36.34
37.99
MSSIM
0.7797
0.7167
0.822
0.8715
0.9266
0.9121
0.9367


## 3.2. Different Noise Levels

How the performance varies for different noise levels is discussed. All the compared methods are with noise detection since its importance has been demonstrated. The denoising performance is quantitatively compared in Figure7.Quantitative measure at different noise levels. (a)–(c) PSNRs ofBarbara,House, andBoatimages, respectively; (d)–(f) MSSIMs ofBarbara,House, andBoatimages, respectively.
(a)
(b)
(c)
(d)
(e)
(f)Under all noise levels, TV-ND achieves higher PSNRs and MSSIMs than AMF. Wavelet-ND obtains higher PSNRs than AMF for less than 50% noise and lower PSNRs when the noise level is further increased. But the MSSIMs of Wavelet-ND are consistently larger than AMF for all noise levels, which implies that the image structures are better preserved. Comparing Wavelet-ND with TV-ND, the former leads to higher MSSIMs forBarbara image (Figure 7(d)) embedding fruitful textures while the latter obtains higher MSSIMs forHouse (Figure 7(e)) andBoat (Figure 7(f)) with more flat regions. The repeated small and directional patterns in clothes ofBarbara image are usually considered as texture [31, 32]. Due to the directional Wavelet functions of the adopted dual-tree complex Wavelet, the Wavelet transform provides sparse representation of texture [33, 34]. On the contrary, total variation is good at sparsifying piece-wise constant image features [32, 35] and thus favors recovering flat regions inHouse andBoat images. Texture is easy to be lost when total variation is applied in noise removal [36]. Therefore, TV-ND is more suitable for images with flat regions while Wavelet-ND is better for image with fruitful textures.The proposed PANO-ND outperforms both TV-ND and Wavelet-ND in terms of MSSIMs. PANO-ND achieves larger or comparable PSNRs when the noise level is below 90%. Besides, higher MSSIMs using PNAO-ND imply that image structures recovered by PANO-ND are more consistent to those of noise-free images. As shown in Figures8, 9, and 10, edges are recovered much clearer using PANO-ND than TV-ND. When the noise level approaches 90%, an extremely heavy noise, the PSNRs (lower than 34 dB) and MSSIMs (lower than 0.75) performance of all the methods are unsatisfactory since very limited information is available.ReconstructedBarbaraimages from 70% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(f) reconstructed images using AMF, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)ReconstructedHouseimages from 70% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(f) reconstructed images using AMF, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)ReconstructedBoatimages from 70% salt and pepper impulse noise. (a) Noise-free image, (b) noisy image, (c)–(f) reconstructed images using AMF, TV-ND, Wavelet-ND, and PANO-ND, respectively.
(a)
(b)
(c)
(d)
(e)
(f)


## 3.3. Effect of Weight for Noise Candidates

A smallerwi∈Ω should be assigned to achieve better denoising performance. As shown in Figure 11, when wi∈Ω becomes larger than 0.1, the quantitative measures reduce dramatically. One explanation is that, when wi∈Ω and wk∈Ω¯ are comparable, meaning 0.1<wi∈Ω/wk∈Ω¯<1, the penalization on noise candidates and the rest of pixels are in the same order; thus, noise candidates are not heavily suppressed in reconstruction. Therefore, wi∈Ω≤10-1 is suggested.Quantitative measures versus the weight for noise candidates. Note:Houseimage with 70% salt and pepper impulse noise is used in simulation and λ is 2.6.
(a)
(b)


## 3.4. Complexity Analysis

In this section, we tested the computation time of different methods in Table2. The AMF is the fastest method, while PANO-ND is the most time-consuming method. Wavelet-ND runs faster than TV-ND but much slower than AMF.Table 2
Computational time of different methods (units: seconds).
Images
Image size
Methods
AMF
TV-ND
Wavelet-ND
PANO-ND
1st recon.
2nd recon.
3rd recon.
Total
Barbara
512
×
512
0.37
49.21
11.34
40.15
28.89
28.86
97.90
Boat
512
×
512
0.37
42.32
10.39
37.56
25.80
25.74
89.10
House
256
×
256
0.07
7.61
3.00
9.19
6.29
6.19
21.67
Note: computations were performed on 2 Cores 2.7 GHz CPU desktop computer with 4 GB RAM. The alternating direction minimization with continuation is used to solve TV-ND, Wavelet-ND, and PANO-ND.Figure12 shows the improvement in the MSSIM scores of these methods with increased complexity. The curve of PANO-ND undergoes 3 peaks because the nonlocal similarity is learnt followed by reconstruction for 3 times. As to the first peak, PANO-ND gets higher or at least comparable MSSIM scores than other methods when the initial guide image is obtained using AMF. When this reconstructed image is further adopted as a guide image, PANO-ND keeps on achieving even higher MSSIM on the next two peaks forBarbara image. ForBoatandHouseimage, it seems enough to only perform PANO-based reconstruction once.Figure11 MSSIMs versus computation time from 50% salt and pepper noise. (a), (c), and (e) are MSSIMs forBarbara,Boat, andHouse images and (b), (d), and (f) are the zoom out part of (a), (c), and (e) when MSSIMs are greater than 0.8.
(a)
(b)
(c)
(d)
(e)
(f)


## 3.5. Effect ofλ

Effect ofλ is discussed in Figure 13. MSSIMs versus λ are evaluated in Figure 13(a). With the increasing of λ, the MSSIMs increase first. Then MSSIMs hold similar for a range of λ (λ∈[2,4] for 50% noise level). When λ becomes too large (λ>4 for 50% noise level), the MSSIMs decrease significantly. Reconstructed images with typical λ are shown in Figures 13(b)–13(d). The optimal result is achieved when λ=2. The λ=1 leads to oversmooth image in Figure 13(c) since a smaller λ encourages higher sparsity and fine image structures are lost. The λ=7 results in some noise are not removed since the consistency between a noisy image y and its denoised version x is highly enforced. How to set an optimal λ is still unsolved which would be an interesting future work.Effect of regularization parameterλ for the proposed approach. (a) The curve of MSSIM versus λ; (b)–(d) reconstructed images when λ=2,1,7, respectively. Note: tests are performed at 50% impulse noise level.
(a)
(b)
(c)
(d)


## 4. Conclusion

A new salt and pepper impulse noise removal method is proposed by first detecting noise candidates and then enforcing image sparsity with a patch-based sparse representation. A weightedl1-l1 regularization model is proposed to penalize the noise candidates heavier than other pixels. The proposed scheme significantly improves the denoising performance than the original PANO-based method under heavy noise. Compared with traditional impulse denoising methods, including adaptive median filtering, total variation and Wavelet, the new method shows obvious advantages on preserving edges and achieving higher structural similarity to the noise-free images. However, the nonlocal similarity is not accurate when noise level is high, for example, 90% noisy image, since initial guide image estimated from traditional adaptive median filtering is unsatisfactory. Future work includes the following.(1)
Taking advantage of nonlocal similarity in both noise detection and image restoration. A sparsity-based model to simultaneously extract impulse noise [13] and recover image will avoid introducing traditional adaptive median filtering; thus, it may improve the denoising performance when noise is heavy.(2)
Wedding adaptive geometric information [15, 16, 37] with image patch similarity may further improve the denoising performance.(3)
Given a specific image, how to automatically set the regularization parameters to trade the data consistency with sparsity remains open.(4)
Accelerate the proposed approach with advanced numerical algorithms [38–40] and hardware, for example, graphic processing units.



---

*Source: 682747-2014-03-13.xml*