# Removal of Salt and Pepper Noise in Corrupted Image Based on Multilevel Weighted Graphs and IGOWA Operator

Authors: Qin Xu; Qiang Zhang; Duo Hu; Jinpei Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper proposes a novel iterative two-stage method to suppress salt and pepper noise. In the first phase, a multilevel weighted graphs model for image representation is built to characterize the gray or color difference between the pixels and their neighbouring pixels at different scales. Then the noise detection is cast into finding the node with minimum node strength in the graphs. In the second phase, we develop a method to determine the order-inducing variables and weighted vectors of the induced generalized order weighted average (IGOWA) operator to restore the detected noise candidate. In the proposed method, the two stages are not separate, but rather alternate. Simulated experiments on gray and color images demonstrate that the proposed method can remove the noise effectively and keep the image details well in comparison to other state-of-the-art methods.


---

## Body

## 1. Introduction

Images are easily corrupted by impulse noise during the signal acquisition, transmission, or storage [1]. There are two types of impulse noise, salt and pepper noise and random valued noise. Salt and pepper noise randomly alters a certain amount of pixels into two extremes, either 0 or 255, for an 8-bit image. The noise significantly damages the image information which leads to difficulties in succeeding image processing tasks such as edge detection or image segmentation and image recognition tasks. Because the noise pixel differs from most of its local neighbours, it has large gradient value the same as the edge pixel [2]. How to effectively restore the noisy image is still a challenging problem.Numerous techniques have been proposed to suppress the salt and pepper noise. The most simple and well-known methods are the standard median filter [3] and its variants [4–6] which are nonlinear filters whose responses are based on reordering the intensity values in the neighbourhood of the corrupted pixel. The nonlinear operation exhibits good denoising power [7], but when the noise level increases, the edges and other details of the image cannot be restored. This is because the median filter simply replaces every pixel’s value. Switching or decision based filters are proposed and have become a hotspot of removal of salt and pepper noise; their strategy in common is using a two-stage technique which first detects the possible noise pixels in an image and then replaces the noise pixels [8–19]. For example, Chan et al. used the adaptive median filter to detect the noise pixels and an objective function with an l1 data-fidelity term and edge-preserved regularization term to denoise, while preserving the edges [9]. The NAFSMF method uses the image histogram to find the salt and pepper noise pixels and computes the number of noise-free pixels to avoid selecting a noise pixel as the median pixel for restoration [10]. The MDBUTMF method regards the maximum or minimum gray level as the noise pixel and replaces the noise pixel with the median of remaining elements in the selected window or with the mean of the selected window if the selected window contains all 0’s or 255’s or both [11]. The AWMF uses a size alterable window to judge whether the given pixel is noise pixel or not and computes the weighted mean of the current window to restore the noise pixel [12].Most recently, Veerakumar et al. used the Rank Ordered Logarithmic Difference which is the logarithmic function on the absolute difference to detect the noise and restore the noise pixels by the adaptive anisotropic diffusion filter [13]. Ahmed proposed a two-stage iterative filter which detects the noisy pixels with an adaptive fuzzy detector and uses weighted mean filter on the uncorrupted pixels [14]. Vijaykumar et al. developed a fast switching filter which identifies the extreme minimum value and extreme maximum value as the noise pixels and replaced the noise pixels by either median value or mean value [15]. Li et al. developed an image block-based noise density estimation method to guide noise detection and noise restoration and used the global image information for noise rectification [16]. Wang et al. explored the similar patches with repeat patterns in images and proposed an iterative nonlocal means filter (INLM) for salt and pepper noise removal [17]. The ANCLPVMF judges the noise pixels based on the linear prediction error and uses adaptive window based vector median filtering operation to restore the noise [18]. In [19], two approaches have been provided for detecting the noise pixels based on means and variance, and a novel type-1 fuzzy approach is presented for denoising.It can be concluded that two aspects of problems in salt and pepper noise removal are how to retain the uncorrupted pixels and how to use the uncorrupted pixels to estimate the corrupted pixel precisely [20]. In order to solve the two aspects of problems effectively, in this paper, we investigate the graph theory for image noise detection and information aggregation operators for image restoration. Studies indicate that the image processing and analysis performance are dependent on the choice of data representation on which they are applied [21]. Recently, graph-based representation for image has been applied to image processing and recognition successfully [22–26]. Inspired by these, on the one hand, we build a multilevel weighted graphs model for image representation to characterize the relationship between the pixels and their neighbouring pixels at different scales. Because the gray or color difference between the noise pixel and its neighbours is large, the node strength of the weighted graphs is utilized to detect the noise candidates. On the other hand, the ordered weighted averaging (OWA) operators provide a parameterized family of mean type aggregation operators [27–32]. They learn the associated weighting vector from observational data to obtain an optimal aggregation result. The generalized OWA (GOWA) [28] operator uses generalized means in the OWA operator. The induced generalized OWA (IGOWA) [29] operator is an extension of the GOWA operator, with the difference that the reordering step of the IGOWA operator is not defined by the values of the arguments, but rather by order-inducing variables, where the ordered position of the arguments depends upon the values of the order-inducing variables. It is a more general formulation of the reordering process that is able to consider more complex situations. Thus, we develop a restoration method based on the IGOWA operator to aggregate the uncorrupted pixels. It has high flexibility and could restore the noise pixel accurately even when the 0’s and 255’s are not balanced in the local neighbourhood of the noise pixel. The proposed noise detection and restoration are not separate, but rather alternate, and iterative, which can deal with the single-point (single-pixel) and noise patches. This is the first attempt of employing the graph theory for solving the noise detection and the information aggregation operator for removing salt and pepper noise. Hopefully, this is an initial work of graph theory and information aggregation operator for image restoration.The rest of the paper is structured as follows. The proposed method and the flow diagram of the proposed algorithm are described in Section2. Section 3 provides the simulation results with different images in comparison with the six state-of-the-art methods. Finally conclusions are drawn is Section 4.


## 2. The Proposed Method

### 2.1. Multilevel Weighted Graphs Modeling for Noise Detection

To detect the noise in an image we model the image as multilevel weighted graphs{Gl=(V,E,W)},l=1,2,…,L, which are a series of graphs G1,G2,…,GL. At each level l, each vi∈V corresponds to a pixel in the image, an edge (vi,vj)∈E connects vertices vi and vj, wij represents the weight on that edge connecting vi and vj, and l denotes the level version. The edges are created by connecting the nodes, whose corresponding pixels are in the neighbour pixel sets.In this paper, we define three different neighbour pixel sets given a pixel, which is illustrated in Figure1, for a given pixel yi, the pixels labeled “1” are the 8-neighbour pixels, labeled “2” are the 12-neighbour pixels, and labeled “3” are the 16-neighbour pixels. We denote the pixel set as N8(yi), N12(yi), and N16(yi), respectively. For a pixel, we connect its corresponding node and the nodes corresponding to its 8-neighbour pixels to create the edges in G1, connect its corresponding node and the nodes corresponding to its 12-neighbour pixels to create the edges in G2, and connect its corresponding node and the nodes corresponding to its 16-neighbour pixels to create the edges in G3. The weight connecting two nodes should reflect the difference of the corresponding pixels’ gray or color in G1, G2, and G3. The edge weight connecting node vi and node vj in the multilevel weighted graphs is defined as(1)wij=1-fyi-fyjfmax-fminifyj∈Nσyi0otherwise,where f(yi) denotes the gray or RGB value of pixel yi, fmax and fmin represent the maximum and minimum gray or RGB value of the image, σ=8 in G1, σ=12 in G2, and σ=16 in G3. The weight wij in all the weighted graphs satisfies wij∈[0,1].Figure 1
Eight-neighbour, 12-neighbour, and 16-neighbour pixel sets ofyi.The node strength of nodevi is defined by(2)si=∑j=1nwij,where n is node number of the graph. The node strength integrates the information on the number (degree) and the weights of links incident in a node [33]. With the defined multilevel weighted graphs for image above, the noise pixels’ corresponding node’s strength is much smaller than the noise-free pixels in the graphs. For this reason, different shaped noise can be detected through finding the corresponding nodes with the minimum node strength in the multilevel weighted graphs. The first level weighted graph is effective in detecting the single-point noise, and when the noise density increases, the second- and third-level weighted graphs are needed to detect the noise patches or blob noise. Therefore, the proposed method can detect the single-point and irregularly shaped noise.To illustrate, take a subimage in Lena image corrupted with50% salt and pepper noise for example, the gray values are shown in Figure 2. Using the proposed detection method, the first noise candidate detected in the dashed-line box is the pixel in row 4, column 2 (noted in yellow), whose corresponding node strength is minimum in the first level weighted graph. Noted that the value of the detected pixel is 0, and it is exactly a noise pixel.Figure 2
Noise detection by minimum node strength.In our algorithm, the noise detection and restoration are alternate. We replace the noise pixel once it is detected, and to detect the next noise pixel, the weighted graph should be constructed again. This procedure is repeated till the pixel corresponding to the minimum strength node is not extreme. The flowchart of the proposed algorithm is shown in Section2.3.


### 2.2. Noise Restoration by Developed IGOWA Operator

When restoring a detected noise pixel, it is appealing to utilize the uncorrupted pixels as correctly as possible to void the information distortion since the entire algorithm is unsupervised. An IGOWA operator aggregatesn inputs into one output with an associated weighting vector ω of dimension n such that the sum of the weight is 1 and ωi∈[0,1], and a set of order-inducing variables xi, and a parameter λ∈(-∞,+∞). The IGOWA operator is defined as follows:(3)fωx1,a1,x2,a2,…,xn,an=∑i=1nωiax-indexiλ1/λ,where xi are the order-inducing variables, ai are the argument variables, and x-index(i) is the index of the ith largest element in the {x1,x2,…,xn}. To restore a noise pixel y, ai(i=1,2,…,n) are the pixel values of the neighbouring n pixels of the noise pixel y. However, there are noise pixels in the n pixels, which should be excluded when restoring using (3).Firstly, we define the set of order-inducing variablesxi as follows:(4)xi=ai-OWAua1,a2,…,an-1,where(5)OWAua1,a2,…,an=∑j=1nujbjand b=b1,b2,…,bn is the reordering of ai; in other words, bj is the jth largest one among {a1,a2,…,an}. OWAu(a1,a2,…,an) in (5) is the representative value of {a1,a2,…,an}. Equation (4) indicates that if ai approximates the value of representative value, then the order-inducing variables xi will be large; on the contrary, the larger the distance between ai and the representative value is, the more possibly ai is noise, and the smaller the order-inducing variables xi will be.Secondly, to avoid the influence of the noise when computing the representative value, the two ends of the weight vectoru={u1,u2,…,un}T are set as zero. The nonzero elements of u are defined as follows. Assume there exist k(k≤n) pixels, whose noise density is p, among the neighbouring n pixels of the noise pixel y. Let random variable ξ denote the number of the noise pixels among the k pixels; then ξ follows binomial distribution; that is, the probability of ξ equals i which is Pξ=i=kipi(1-p)k-i,i=1,2,…,k. The probability that the number of the noise pixels ξ less than or equal to h is(6)Fh=Pξ⩽h=∑i=0hkipi1-pk-i.To denoise with the significant level α, we seek the minimal value q satisfying F(q)≥1-α. The weighted vector u can be computed by(7)uj=n-g-1j-g2+1·0.5n-g-1ifj=g2+1,…,n-g20otherwise,where g=q if q is even and g=q+1 if q is odd.Finally, the weighted vectorω=(ω1,ω2,…,ωn)T is defined by basic unit-interval monotonic (BUM) function [34] Q(x)=xβ(0<β<1); here(8)ωi=Qin-q-Qi-1n-qi=1,2,…,n-q0i=n-q+1,…,n;obviously, ∑i=1n‍ωi=1, and 1≥ω1≥ω2≥⋯≥ωn≥0. Consequently, the original value of the corrupted pixel can be predicted by (3).From the above analysis, algorithm of the developed IGOWA for restoration is summarized as follows.Step 1.
Computeq by (6) and obtain the weighted vector u by (7).Step 2.
Substitute the weighted vectoru to (5) to compute OWAu(a1,a2,…,an).Step 3.
Based on (4), we get the order-inducing variables xi.Step 4.
Use (8) to compute the weighted vector ω.Step 5.
The restored value of the noise pixel is obtained through (3).


### 2.3. The Proposed Algorithm

From the principles, in comparison with the previous methods, the proposed method has two advantages which can be concluded as follows.(i)
The proposed method utilizes both the structure features and gray level of image to detect the noise candidates. Therefore, the detection method can detect the noise accurately and keep the uncorrupted pixels which are in themselves extremely unchanged. Whereas the previous methods either use the gray level or the statistical information of image which possibly bring detection errors.(ii)
For restoration, the IGOWA operator is adopted and developed for the first time to predict the corrupted pixel using the local neighbouring pixels in our method. We design the order-inducing variables of the operators to produce the appropriate pixel value for denoising. This method is easy to understand and effective, whereas the previous denoising methods are either too easy to give a good result or ambiguous to understand and carry out.For implementation, the images are restored from top to bottom and left to right. Initially, we denoise a4×4 subimage in the top left of the image, as described in Sections 2.1 and 2.2. When the pixel corresponding to the node with minimum node strength in the multilevel weighted graphs is not extreme, the denoising procedure of the current subimage completes. Then we construct the next subimage which consists of part of the restored image and part of the contaminated image to denoise. These are repeated till the entire image is processed. The flow diagram of proposed algorithm is shown in Figure 3.Figure 3
Algorithm flowchart of the proposed method.


## 2.1. Multilevel Weighted Graphs Modeling for Noise Detection

To detect the noise in an image we model the image as multilevel weighted graphs{Gl=(V,E,W)},l=1,2,…,L, which are a series of graphs G1,G2,…,GL. At each level l, each vi∈V corresponds to a pixel in the image, an edge (vi,vj)∈E connects vertices vi and vj, wij represents the weight on that edge connecting vi and vj, and l denotes the level version. The edges are created by connecting the nodes, whose corresponding pixels are in the neighbour pixel sets.In this paper, we define three different neighbour pixel sets given a pixel, which is illustrated in Figure1, for a given pixel yi, the pixels labeled “1” are the 8-neighbour pixels, labeled “2” are the 12-neighbour pixels, and labeled “3” are the 16-neighbour pixels. We denote the pixel set as N8(yi), N12(yi), and N16(yi), respectively. For a pixel, we connect its corresponding node and the nodes corresponding to its 8-neighbour pixels to create the edges in G1, connect its corresponding node and the nodes corresponding to its 12-neighbour pixels to create the edges in G2, and connect its corresponding node and the nodes corresponding to its 16-neighbour pixels to create the edges in G3. The weight connecting two nodes should reflect the difference of the corresponding pixels’ gray or color in G1, G2, and G3. The edge weight connecting node vi and node vj in the multilevel weighted graphs is defined as(1)wij=1-fyi-fyjfmax-fminifyj∈Nσyi0otherwise,where f(yi) denotes the gray or RGB value of pixel yi, fmax and fmin represent the maximum and minimum gray or RGB value of the image, σ=8 in G1, σ=12 in G2, and σ=16 in G3. The weight wij in all the weighted graphs satisfies wij∈[0,1].Figure 1
Eight-neighbour, 12-neighbour, and 16-neighbour pixel sets ofyi.The node strength of nodevi is defined by(2)si=∑j=1nwij,where n is node number of the graph. The node strength integrates the information on the number (degree) and the weights of links incident in a node [33]. With the defined multilevel weighted graphs for image above, the noise pixels’ corresponding node’s strength is much smaller than the noise-free pixels in the graphs. For this reason, different shaped noise can be detected through finding the corresponding nodes with the minimum node strength in the multilevel weighted graphs. The first level weighted graph is effective in detecting the single-point noise, and when the noise density increases, the second- and third-level weighted graphs are needed to detect the noise patches or blob noise. Therefore, the proposed method can detect the single-point and irregularly shaped noise.To illustrate, take a subimage in Lena image corrupted with50% salt and pepper noise for example, the gray values are shown in Figure 2. Using the proposed detection method, the first noise candidate detected in the dashed-line box is the pixel in row 4, column 2 (noted in yellow), whose corresponding node strength is minimum in the first level weighted graph. Noted that the value of the detected pixel is 0, and it is exactly a noise pixel.Figure 2
Noise detection by minimum node strength.In our algorithm, the noise detection and restoration are alternate. We replace the noise pixel once it is detected, and to detect the next noise pixel, the weighted graph should be constructed again. This procedure is repeated till the pixel corresponding to the minimum strength node is not extreme. The flowchart of the proposed algorithm is shown in Section2.3.


## 2.2. Noise Restoration by Developed IGOWA Operator

When restoring a detected noise pixel, it is appealing to utilize the uncorrupted pixels as correctly as possible to void the information distortion since the entire algorithm is unsupervised. An IGOWA operator aggregatesn inputs into one output with an associated weighting vector ω of dimension n such that the sum of the weight is 1 and ωi∈[0,1], and a set of order-inducing variables xi, and a parameter λ∈(-∞,+∞). The IGOWA operator is defined as follows:(3)fωx1,a1,x2,a2,…,xn,an=∑i=1nωiax-indexiλ1/λ,where xi are the order-inducing variables, ai are the argument variables, and x-index(i) is the index of the ith largest element in the {x1,x2,…,xn}. To restore a noise pixel y, ai(i=1,2,…,n) are the pixel values of the neighbouring n pixels of the noise pixel y. However, there are noise pixels in the n pixels, which should be excluded when restoring using (3).Firstly, we define the set of order-inducing variablesxi as follows:(4)xi=ai-OWAua1,a2,…,an-1,where(5)OWAua1,a2,…,an=∑j=1nujbjand b=b1,b2,…,bn is the reordering of ai; in other words, bj is the jth largest one among {a1,a2,…,an}. OWAu(a1,a2,…,an) in (5) is the representative value of {a1,a2,…,an}. Equation (4) indicates that if ai approximates the value of representative value, then the order-inducing variables xi will be large; on the contrary, the larger the distance between ai and the representative value is, the more possibly ai is noise, and the smaller the order-inducing variables xi will be.Secondly, to avoid the influence of the noise when computing the representative value, the two ends of the weight vectoru={u1,u2,…,un}T are set as zero. The nonzero elements of u are defined as follows. Assume there exist k(k≤n) pixels, whose noise density is p, among the neighbouring n pixels of the noise pixel y. Let random variable ξ denote the number of the noise pixels among the k pixels; then ξ follows binomial distribution; that is, the probability of ξ equals i which is Pξ=i=kipi(1-p)k-i,i=1,2,…,k. The probability that the number of the noise pixels ξ less than or equal to h is(6)Fh=Pξ⩽h=∑i=0hkipi1-pk-i.To denoise with the significant level α, we seek the minimal value q satisfying F(q)≥1-α. The weighted vector u can be computed by(7)uj=n-g-1j-g2+1·0.5n-g-1ifj=g2+1,…,n-g20otherwise,where g=q if q is even and g=q+1 if q is odd.Finally, the weighted vectorω=(ω1,ω2,…,ωn)T is defined by basic unit-interval monotonic (BUM) function [34] Q(x)=xβ(0<β<1); here(8)ωi=Qin-q-Qi-1n-qi=1,2,…,n-q0i=n-q+1,…,n;obviously, ∑i=1n‍ωi=1, and 1≥ω1≥ω2≥⋯≥ωn≥0. Consequently, the original value of the corrupted pixel can be predicted by (3).From the above analysis, algorithm of the developed IGOWA for restoration is summarized as follows.Step 1.
Computeq by (6) and obtain the weighted vector u by (7).Step 2.
Substitute the weighted vectoru to (5) to compute OWAu(a1,a2,…,an).Step 3.
Based on (4), we get the order-inducing variables xi.Step 4.
Use (8) to compute the weighted vector ω.Step 5.
The restored value of the noise pixel is obtained through (3).


## 2.3. The Proposed Algorithm

From the principles, in comparison with the previous methods, the proposed method has two advantages which can be concluded as follows.(i)
The proposed method utilizes both the structure features and gray level of image to detect the noise candidates. Therefore, the detection method can detect the noise accurately and keep the uncorrupted pixels which are in themselves extremely unchanged. Whereas the previous methods either use the gray level or the statistical information of image which possibly bring detection errors.(ii)
For restoration, the IGOWA operator is adopted and developed for the first time to predict the corrupted pixel using the local neighbouring pixels in our method. We design the order-inducing variables of the operators to produce the appropriate pixel value for denoising. This method is easy to understand and effective, whereas the previous denoising methods are either too easy to give a good result or ambiguous to understand and carry out.For implementation, the images are restored from top to bottom and left to right. Initially, we denoise a4×4 subimage in the top left of the image, as described in Sections 2.1 and 2.2. When the pixel corresponding to the node with minimum node strength in the multilevel weighted graphs is not extreme, the denoising procedure of the current subimage completes. Then we construct the next subimage which consists of part of the restored image and part of the contaminated image to denoise. These are repeated till the entire image is processed. The flow diagram of proposed algorithm is shown in Figure 3.Figure 3
Algorithm flowchart of the proposed method.


## 3. Simulation Results

### 3.1. Configuration

In this section, the performance of our proposed method is tested with different gray-scale and color images (Lena, Boat, Baboon, Cornfield, Flower, Fruits, and Pens) whose dynamic ranges are[0255]. The test images considered in this work have both low and high frequency content. We use the signal-to-noise ratio (PSNR) and the correlation factor (CF) to quantitatively measure the restoration results.The PSNR is defined as(9)PSNR=10log102552MN∑i,jri,j-oi,j2=10log102552MSE,where oi,j is the pixel value of the original noise-free image, ri,j is the pixel value of the restored image, and M×N is the size of the input image. The MSE is the mean-square-error between the original and restored images. The correlation factor is defined as(10)CF=∑i=0M-1∑j=0N-1ri,j-r¯oi,j-o¯∑i=0M-1∑j=0N-1ri,j-r¯2∑i=0M-1∑j=0N-1oi,j-o¯2,where oi,j is the pixel value of the original noise-free image, o¯ is the mean pixel value of the original image, ri,j is the pixel value of the restored image, r¯ is the mean pixel value of the restored image, and M×N is the size of the input image. The correlation factor R=1 if the two images are absolutely identical, R=0 if they are completely uncorrelated, and R=-1 if they are anticorrelated.Our proposed method is compared to other state-of-the-art salt and pepper noise filters, which include NAFSMF [10], MDBUTMF [11], AWMF [12], FSMMF [15], LGF [16], and ANCLPVMF [18]. All the experiments are implemented in MATLAB and executed on a Core i7-4790 CPU@4.00 GHz with 16.0 GB of memory and no effort made to optimize algorithm speed.Parameters of the proposed method and the compared algorithms are sets as below. In the developed IGOWA for restoration, we set the significant levelα=0.05 when the noise density is lower than 0.5, α=0.1 when the noise density is equal or higher than 0.5, the exponent of the BUM function β=0.55, and the λ=2. Parameters of the compared methods are set as below. In method NAFSMF, the maximum of window size ωmax=3, lower bound T1=10, and upper bound T2=30. In method MDBUTMF, window size ω=3. In method AWMF, the w=1, h=1, and wmax=39. In method in LGF, w=9 in the noise density estimation stage, β=400 in the noise detection rectification stage, Ld=7 and r=1 in the first noise detection stage, and m=7 in the second noise detection stage. We either use the recommended parameters as in the original papers or tune the parameters to obtain the optimal results for the six compared methods.


### 3.2. Denoising Performance

Firstly, to verify the efficiency of the proposed denoising method, among the commonly tested512×512 8-bit gray-scale images, the image (Lena) with homogeneous region and image (Boat) with high activity are taken as testing samples. Each sample is randomly corrupted by salt and pepper noise with varying densities from 10% to 90% with increment of 10%. The PSNR and CF values of the proposed method in comparison to the state-of-the-art methods for different noise densities for Lena and Boat image are illustrated in Tables 1–4. From Tables 1 and 3, we can see that although the AWMF, ANCLPVMF, and LGF can provide a good PSNR value, the proposed method can give much better PSNR values than the compared six methods. Actually, the proposed method can significantly improve the restoration in slight noise corruptions, such as the noise density less than 40%. Moreover, it is evident that the proposed method can give much greater CF values than the compared six methods from Tables 2 and 4.Table 1
Comparison of restorations in PSNR (dB) for Lena image.
Methods Noise density 10% 20% 30% 40% 50% 60% 70% 80% 90% NAFSMF 36.71 34.53 32.55 30.26 27.94 25.88 23.32 21.41 19.26 MDBUTMF 37.96 34.77 32.29 30.33 28.20 26.46 24.27 21.60 18.33 AWMF 38.90 36.30 35.07 33.86 32.62 31.17 29.50 27.67 25.04 FSMMF 38.78 36.41 34.32 32.40 30.39 28.40 26.56 24.92 23.10 LGF 38.62 36.90 34.76 32.87 31.44 30.22 28.85 27.02 24.71 ANCLPVMF 39.97 37.62 35.31 33.74 32.40 31.16 29.25 27.39 25.13 Proposed 42.86 39.14 36.75 34.26 32.73 31.21 29.54 27.70 25.32Table 2
Comparison of restorations in CF for Lena image.
Methods Noise density 10% 20% 30% 40% 50% 60% 70% 80% 90% NAFSMF 9.677 9.596 9.449 9.154 8.733 8.428 8.009 7.601 7.186 MDBUTMF 9.782 9.574 9.232 8.824 8.471 8.020 7.570 7.099 6.548 AWMF 9.841 9.802 9.696 9.552 9.376 9.201 8.893 8.541 8.274 FSMMF 9.865 9.736 9.701 9.621 9.438 9.211 8.880 8.579 8.266 LGF 9.811 9.753 9.638 9.526 9.397 9.256 9.021 8.835 8.472 ANCLPVMF 9.815 9.618 9.532 9.327 9.048 8.889 8.653 8.477 8.268 Proposed 9.993 9.987 9.974 9.944 9.926 9.875 9.710 9.53 9.240Table 3
Comparison of restorations in PSNR(dB) for Boat image.
Methods Noise density 10% 20% 30% 40% 50% 60% 70% 80% 90% PSNR values (dB) NAFSMF 35.19 32.64 30.72 29.28 28.00 26.57 24.34 22.69 21.02 MDBUTMF 35.56 32.88 30.88 28.91 27.06 25.19 23.39 21.72 19.88 AWMF 36.42 34.71 33.17 31.77 30.24 28.97 27.54 25.78 23.81 FSMMF 36.43 34.47 32.82 30.76 29.20 27.54 25.85 23.9 22.00 LGF 37.06 35.11 33.12 31.26 29.83 28.13 26.53 24.62 22.80 ANCLPVMF 36.37 34.62 33.18 31.09 29.37 28.01 26.99 25.34 23.48 Proposed 39.68 36.72 34.36 32.55 31.02 29.73 28.20 26.39 24.12Table 4
Comparison of restorations in CF for Boat image.
NAFSMF 9.756 9.479 9.190 8.910 8.697 8.468 8.196 7.943 7.769 MDBUTMF 9.827 9.551 9.315 8.991 8.699 8.371 8.054 7.759 7.484 AWMF 9.793 9.684 9.582 9.402 9.232 9.015 8.742 8.466 8.265 FSMMF 9.876 9.749 9.625 9.474 9.307 9.137 8.833 8.580 8.363 LGF 9.843 9.814 9.711 9.558 9.373 9.235 8.973 8.745 8.478 ANCLPVMF 9.892 9.785 9.692 9.567 9.413 9.246 9.076 8.846 8.642 Proposed 9.985 9.964 9.930 9.885 9.822 9.759 9.728 9.631 9.508For visual comparison, Figures4 and 5 show the restored images of various methods for the Lena and Boat corrupted by 70% noise density, respectively. From Figure 4, it can be found that the AWMF, ANCLPVMF, FSMMF, and LGF reveal superior performance to the NAFSMF and MDBUTMF, which deteriorate the quality of the restored images. Our proposed method slightly outperforms the AWMF, ANCLPVMF, FSMMF, and LGF, among which the method in LGF suffers from blurred effect in the restored image. The restored images through the AWMF, ANCLPVMF, and FSMMF still have different amounts of residual noise, and the restored image by the proposed method has better image details, where the edges and textures are preserved well. These results are consistent with that for the Boat image as shown in Figure 5.Figure 4
Restored images of various results for the Lena image with 70% noise density. (a) Noisy image; (b) restored image using the NAFSMF; (c) restored image using the MDBUTMF; (d) restored image using the AWMF; (e) restored image using the method in FSMMF (f) restored image using the method in LGF; (g) restored image using the ANCLPVMF; (h) restored image using the proposed image; and (i) original image.
(a) (b) (c) (d) (e) (f) (g) (h) (i)Figure 5
Restored images of various results for the Boat image with 70% noise density. (a) Noisy image; (b) restored image using the NAFSMF; (c) restored image using the MDBUTMF; (d) restored image using the AWMF; (e) restored image using the method in FSMMF; (f) restored image using the method in LGF; (g) restored image using the ANCLPVMF; (h) restored image using the proposed image; and (i) original image.
(a) (b) (c) (d) (e) (f) (g) (h) (i)To further demonstrate the excellent performance of the proposed method, we also use the proposed method to process color images that are corrupted by salt and pepper noise. The color images taken into account are Baboon, Cornfield, Flower, and Fruits. To perform image denoising on a color image, we respectively apply our method to the separate color channels (RGB) of noisy color images and recombining them. Visual restored Baboon images corrupted by 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, and 90% noise density are shown in Figure6. We can see that the proposed method can obtain good visual effects and also perfectly protects the detail of the restored image. Figure 7 has shown visual observation of different restored images by the proposed method with 60% noise density. These images can be downloaded by the link http://www.hlevkin.com/06testimages.htm. It can be seen that the proposed method also provides satisfactory performance and is suitable for processing color image at high noise density. In brief, visual quality of the proposed method is excellent not only for low frequency image, but also for high frequency image.Figure 6
Restoration results of Baboon in different noise densities. From top left to bottom right: original image, noise density equals 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, and 90%.Figure 7
Restoration results of color images with 60% noise density (left to right): original images, noisy images, and restored image used by the proposed method.


## 3.1. Configuration

In this section, the performance of our proposed method is tested with different gray-scale and color images (Lena, Boat, Baboon, Cornfield, Flower, Fruits, and Pens) whose dynamic ranges are[0255]. The test images considered in this work have both low and high frequency content. We use the signal-to-noise ratio (PSNR) and the correlation factor (CF) to quantitatively measure the restoration results.The PSNR is defined as(9)PSNR=10log102552MN∑i,jri,j-oi,j2=10log102552MSE,where oi,j is the pixel value of the original noise-free image, ri,j is the pixel value of the restored image, and M×N is the size of the input image. The MSE is the mean-square-error between the original and restored images. The correlation factor is defined as(10)CF=∑i=0M-1∑j=0N-1ri,j-r¯oi,j-o¯∑i=0M-1∑j=0N-1ri,j-r¯2∑i=0M-1∑j=0N-1oi,j-o¯2,where oi,j is the pixel value of the original noise-free image, o¯ is the mean pixel value of the original image, ri,j is the pixel value of the restored image, r¯ is the mean pixel value of the restored image, and M×N is the size of the input image. The correlation factor R=1 if the two images are absolutely identical, R=0 if they are completely uncorrelated, and R=-1 if they are anticorrelated.Our proposed method is compared to other state-of-the-art salt and pepper noise filters, which include NAFSMF [10], MDBUTMF [11], AWMF [12], FSMMF [15], LGF [16], and ANCLPVMF [18]. All the experiments are implemented in MATLAB and executed on a Core i7-4790 CPU@4.00 GHz with 16.0 GB of memory and no effort made to optimize algorithm speed.Parameters of the proposed method and the compared algorithms are sets as below. In the developed IGOWA for restoration, we set the significant levelα=0.05 when the noise density is lower than 0.5, α=0.1 when the noise density is equal or higher than 0.5, the exponent of the BUM function β=0.55, and the λ=2. Parameters of the compared methods are set as below. In method NAFSMF, the maximum of window size ωmax=3, lower bound T1=10, and upper bound T2=30. In method MDBUTMF, window size ω=3. In method AWMF, the w=1, h=1, and wmax=39. In method in LGF, w=9 in the noise density estimation stage, β=400 in the noise detection rectification stage, Ld=7 and r=1 in the first noise detection stage, and m=7 in the second noise detection stage. We either use the recommended parameters as in the original papers or tune the parameters to obtain the optimal results for the six compared methods.


## 3.2. Denoising Performance

Firstly, to verify the efficiency of the proposed denoising method, among the commonly tested512×512 8-bit gray-scale images, the image (Lena) with homogeneous region and image (Boat) with high activity are taken as testing samples. Each sample is randomly corrupted by salt and pepper noise with varying densities from 10% to 90% with increment of 10%. The PSNR and CF values of the proposed method in comparison to the state-of-the-art methods for different noise densities for Lena and Boat image are illustrated in Tables 1–4. From Tables 1 and 3, we can see that although the AWMF, ANCLPVMF, and LGF can provide a good PSNR value, the proposed method can give much better PSNR values than the compared six methods. Actually, the proposed method can significantly improve the restoration in slight noise corruptions, such as the noise density less than 40%. Moreover, it is evident that the proposed method can give much greater CF values than the compared six methods from Tables 2 and 4.Table 1
Comparison of restorations in PSNR (dB) for Lena image.
Methods Noise density 10% 20% 30% 40% 50% 60% 70% 80% 90% NAFSMF 36.71 34.53 32.55 30.26 27.94 25.88 23.32 21.41 19.26 MDBUTMF 37.96 34.77 32.29 30.33 28.20 26.46 24.27 21.60 18.33 AWMF 38.90 36.30 35.07 33.86 32.62 31.17 29.50 27.67 25.04 FSMMF 38.78 36.41 34.32 32.40 30.39 28.40 26.56 24.92 23.10 LGF 38.62 36.90 34.76 32.87 31.44 30.22 28.85 27.02 24.71 ANCLPVMF 39.97 37.62 35.31 33.74 32.40 31.16 29.25 27.39 25.13 Proposed 42.86 39.14 36.75 34.26 32.73 31.21 29.54 27.70 25.32Table 2
Comparison of restorations in CF for Lena image.
Methods Noise density 10% 20% 30% 40% 50% 60% 70% 80% 90% NAFSMF 9.677 9.596 9.449 9.154 8.733 8.428 8.009 7.601 7.186 MDBUTMF 9.782 9.574 9.232 8.824 8.471 8.020 7.570 7.099 6.548 AWMF 9.841 9.802 9.696 9.552 9.376 9.201 8.893 8.541 8.274 FSMMF 9.865 9.736 9.701 9.621 9.438 9.211 8.880 8.579 8.266 LGF 9.811 9.753 9.638 9.526 9.397 9.256 9.021 8.835 8.472 ANCLPVMF 9.815 9.618 9.532 9.327 9.048 8.889 8.653 8.477 8.268 Proposed 9.993 9.987 9.974 9.944 9.926 9.875 9.710 9.53 9.240Table 3
Comparison of restorations in PSNR(dB) for Boat image.
Methods Noise density 10% 20% 30% 40% 50% 60% 70% 80% 90% PSNR values (dB) NAFSMF 35.19 32.64 30.72 29.28 28.00 26.57 24.34 22.69 21.02 MDBUTMF 35.56 32.88 30.88 28.91 27.06 25.19 23.39 21.72 19.88 AWMF 36.42 34.71 33.17 31.77 30.24 28.97 27.54 25.78 23.81 FSMMF 36.43 34.47 32.82 30.76 29.20 27.54 25.85 23.9 22.00 LGF 37.06 35.11 33.12 31.26 29.83 28.13 26.53 24.62 22.80 ANCLPVMF 36.37 34.62 33.18 31.09 29.37 28.01 26.99 25.34 23.48 Proposed 39.68 36.72 34.36 32.55 31.02 29.73 28.20 26.39 24.12Table 4
Comparison of restorations in CF for Boat image.
NAFSMF 9.756 9.479 9.190 8.910 8.697 8.468 8.196 7.943 7.769 MDBUTMF 9.827 9.551 9.315 8.991 8.699 8.371 8.054 7.759 7.484 AWMF 9.793 9.684 9.582 9.402 9.232 9.015 8.742 8.466 8.265 FSMMF 9.876 9.749 9.625 9.474 9.307 9.137 8.833 8.580 8.363 LGF 9.843 9.814 9.711 9.558 9.373 9.235 8.973 8.745 8.478 ANCLPVMF 9.892 9.785 9.692 9.567 9.413 9.246 9.076 8.846 8.642 Proposed 9.985 9.964 9.930 9.885 9.822 9.759 9.728 9.631 9.508For visual comparison, Figures4 and 5 show the restored images of various methods for the Lena and Boat corrupted by 70% noise density, respectively. From Figure 4, it can be found that the AWMF, ANCLPVMF, FSMMF, and LGF reveal superior performance to the NAFSMF and MDBUTMF, which deteriorate the quality of the restored images. Our proposed method slightly outperforms the AWMF, ANCLPVMF, FSMMF, and LGF, among which the method in LGF suffers from blurred effect in the restored image. The restored images through the AWMF, ANCLPVMF, and FSMMF still have different amounts of residual noise, and the restored image by the proposed method has better image details, where the edges and textures are preserved well. These results are consistent with that for the Boat image as shown in Figure 5.Figure 4
Restored images of various results for the Lena image with 70% noise density. (a) Noisy image; (b) restored image using the NAFSMF; (c) restored image using the MDBUTMF; (d) restored image using the AWMF; (e) restored image using the method in FSMMF (f) restored image using the method in LGF; (g) restored image using the ANCLPVMF; (h) restored image using the proposed image; and (i) original image.
(a) (b) (c) (d) (e) (f) (g) (h) (i)Figure 5
Restored images of various results for the Boat image with 70% noise density. (a) Noisy image; (b) restored image using the NAFSMF; (c) restored image using the MDBUTMF; (d) restored image using the AWMF; (e) restored image using the method in FSMMF; (f) restored image using the method in LGF; (g) restored image using the ANCLPVMF; (h) restored image using the proposed image; and (i) original image.
(a) (b) (c) (d) (e) (f) (g) (h) (i)To further demonstrate the excellent performance of the proposed method, we also use the proposed method to process color images that are corrupted by salt and pepper noise. The color images taken into account are Baboon, Cornfield, Flower, and Fruits. To perform image denoising on a color image, we respectively apply our method to the separate color channels (RGB) of noisy color images and recombining them. Visual restored Baboon images corrupted by 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, and 90% noise density are shown in Figure6. We can see that the proposed method can obtain good visual effects and also perfectly protects the detail of the restored image. Figure 7 has shown visual observation of different restored images by the proposed method with 60% noise density. These images can be downloaded by the link http://www.hlevkin.com/06testimages.htm. It can be seen that the proposed method also provides satisfactory performance and is suitable for processing color image at high noise density. In brief, visual quality of the proposed method is excellent not only for low frequency image, but also for high frequency image.Figure 6
Restoration results of Baboon in different noise densities. From top left to bottom right: original image, noise density equals 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, and 90%.Figure 7
Restoration results of color images with 60% noise density (left to right): original images, noisy images, and restored image used by the proposed method.


## 4. Conclusion

In this paper, we have proposed multilevel weighted graphs for noise detection and developed IGOWA operator for noise restoration. Moreover, a novel iterative algorithm for denoising is provided. By simulated experiments, not only the single-point noise can be discovered and restored, but also the blob noise or noise patch can be found and diminished by iterations of the proposed algorithm. Moreover, experiment results show that the proposed method outperforms other six state-of-the-art methods and keeps image details well, such as edges and texture. One can further improve our method by using other graph properties and other information aggregation operators to extent the method to random valued impulse noise.



---

*Source: 7975248-2018-05-15.xml*