Impulsive noise filtering using a Median Redescending M-Estimator

Abstract

Salt and Pepper noise removal is an important image preprocessing task, it has two simultaneous demands: the suppression of impulses and the preservation of edges. To address this problem in gray scale images, we propose an efficient method which consists of introducing a Redescending M-Estimator within of the Median-Estimator scheme. The Redescending M-Estimator controls the magnitude of the Salt or Pepper impulses and deletes them when it is necessary; the remaining pixels in the neighborhood are processed by the Median-Estimator in order to obtain an estimation of a noise free pixel. The proposed scheme is applied on the entire image using sliding windows of size 5 $\times$ 5; the local information obtained by this window is used to calculate the thresholds and the parameters that characterize the influence functions tested in the Redescending M-Estimator. To improve the suppression ability of our proposal a pulse detector is used, it identifies when is necessary to submit each pixel to the denoising process. The effectiveness of our proposal is verified by quantitative and qualitative results.

Keywords

Salt and Pepper noise noise suppression grayscale images Redescending M-Estimator Median-Estimator

1. Introduction

The impulsive noise is a common problem in digital images; usually it is incorporated when they are acquired or transmitted through communication channels. This type of noise has been modeled in different ways, by means of fixed intensity pixel values (Salt and Pepper noise) or by random intensity pixel values (Random impulsive noise) [4, 6, 14, 22]. In the fixed valued noise, some pixels of the image are changed into 0 or 255, whereas random valued impulse noise changes the intensity value into a random value that goes from 0 to 255. These values are valid just when the images are in 8-bit mode.

High level image processing tasks demand noiseless images with a visual quality; this means that the noise has to be suppressed with no deterioration of the fine details. To suppress the Random impulsive noise some important methods have been proposed in the literature. In [21], a technique based on concepts derived from robust statistics is presented, which can be regarded as a generalization of median filter. In [26], an effective switching median-mean filter is proposed, this method is formed by two stages, in the first one the pixels are detected as noisy or noise-free, in the second one the filtering process is developed by the switching median-mean filter or switching mean-median filter. A fuzzy filtering approach based on turbulent particle swarm optimization is presented in [7], this filter contains a parallel fuzzy inference mechanism, a fuzzy mean process, and a fuzzy composition process. In [15], a neuro-fuzzy network is presented, this is constructed by combining two neuro-fuzzy filters with a postprocessor, each filter is a first order Sugeno type fuzzy inference system with 4-inputs and 1-output and it evaluates a different relation between the median value of all the pixels in a predefined selecting data window. On the other hand, to suppress the Salt and Pepper noise some interesting results have been proposed in the literature. In [10], an approach with the ability to remove high-density noise in images without deteriorating their edges is proposed, it is based on the benefits of non-local means and the efficiency of unsymmetric trimmed mean (applied by means of discrete wavelet transform). A recursive and enhanced median filter method to remove impulsive noise with high density is described by the authors in [19], this technique can detect and remove noise in a simultaneous way. An adaptive methodology formed by an efficient salt and pepper noise detector, an adaptive mean-median filter and the total variation inpainting method are joined to obtain a robust filtering technique in [9]. In [17], a technique to suppress impulsive noise with high density by using a recursive and adaptive median filter is introduced, in the proposal the adaptive operation is justified with the variation in size of working window, which is centered at noisy pixels. An Iterative Adaptive Fuzzy Filter Using Alpha-Trimmed Mean was presented in [1], the filter operated in two stages-detection of noisy pixels with an adaptive fuzzy detector followed by denoising using a weighted mean filter on the good pixels in the filter window.

Some algorithms aforementioned were variations of median and mean filters, the other ones were based on Fuzzy Logic or hybrid techniques. After exploring these filters, we found two shortcomings: (1) when they used impulse detectors, the variability among all the pixels in the square window was not consider, (2) most of them were focused simply in suppressing the impulses, without considering the magnitude reduction of extreme pixels (salt or pepper impulses). To cover both shortcomings, we implemented a methodology based on an impulse detector and robust estimators of location. The impulse noise detector considers the dispersion between pixels and their neighbors, to do this it sets some conditions, when they are satisfied the pixel of interest is considered as noise-free and therefore is not submitted to removal process; in the other case, the pixel being analyzed and its neighbors are processed by the robust estimators in order to calculate the best estimation of a noise free pixel. The robust estimation consists of a Redescending M-Estimator and a Median-Estimator. The first estimator analyzes all pixels into the neighborhood in order to decrease the contribution of salt or pepper impulses as well as to suppress them when is required, its performance is controlled by their influence function ( $\psi$ ); this function is related with the breakdown point ( $\varepsilon$ *). In the literature, there exists some popular Redescending M-Estimators [2, 12, 13, 16, 18], it has been shown that the Redescending M-Estimators attain the bound $\varepsilon$ * $=$ 0.5 [18], this means that they have good performance even when the images are degraded until a 50% of impulses. The remaining neighboring pixels are used to obtain the most representative pixel of the neighborhood; this process is done by the second estimator. It is well-known that the Median-Estimator has a breakdown point $\varepsilon$ * $=$ 0.5 [18]; besides, it has very good edge preservation properties [18], these skills were taking into account in our proposal. Each estimator has a good performance against impulsive noise by themselves, but when they are combined to form the Median Redescending M-Estimator, they can restore images corrupted by 70% of impulsive noise ( $\varepsilon$ * $=$ 0.7), without destroy the fine details of the images.

An outline of the remainder of the paper is as follows. In Section 2, a briefly discussion about the Salt and Pepper noise model and Robust Estimators is presented. The suggested proposal is described in detail in Section 3. Section 4 reports the experimental results of our scheme, as well as the comparisons with other state-of-art methods. The conclusion and the next effort are drawn in Section 5.

2. Background

This section describes the impulse noise model and the robust estimators of location considered in this study.

2.1 Impulsive noise model

In the well-known Salt and Pepper model some pixels of an image $x$ (with size $M\times N$ ) are destroyed and replaced by salt (255) or pepper (0) values, such as it is described by the next expression:

$\tilde{{x}}_{i,j}=\begin{cases}0&{\text{with probability∼{}}p/2}\\ {x_{i,j}}&{\text{with probability∼{}}1-p}\\ {255}&{\text{with probability∼{}}p/2}\\ \end{cases}$ (1)

where, $x$ is the noiseless image, $\tilde{{x}}$ is the noisy image, $(i,j)$ denotes the location of a pixel, $i$ and $j$ are indexes constrained by the image size ( $1\leqslant i\leqslant M$ and $1\leqslant j\leqslant N$ ) and $p$ is the probability of occurrence of a salt or pepper impulse (i.e. $0\leqslant p\leqslant 1$ ).

2.2 Robust estimators

Robust estimators were developed to overcome the noise sensitivity of least square method [8], the most popular robust estimators are: $M, R$ and $L$ [8, 18], they come from the pioneering work of Huber, Tukey, Lehman, David and other researchers in the sixties. These estimators have found applications in digital image processing as nonlinear filters. In this research, to suppress Salt and Pepper noise on grayscale images we consider the Redescending M-Estimators (a special type of M-Estimators of location) [8, 12, 13, 16, 18], and the Median-Estimator (it is considered as a prominent example of robust estimators) [18].

To introduce the M-Estimators of location it is convenient to consider a set of points distributed independently $X=\left\{{x_{i}|i=1,\ldots,n}\right\}$ with density $f\left({x_{i}-\mu}\right)$ . Their principle is to find an estimate $\hat{{\mu}}$ of $\mu$ such that:

$\hat{{\mu}}=\mathop{\arg\min}\limits_{\mu}\sum\limits_{i=1}^{n}{\rho\left({x_{% i}-\mu}\right)}$ (2)

where, the robust loss function $\rho$ is given by $\rho=-\log f$ [14, 15, 16, 18, 19], ${\rm argmin}$ stands for the value minimizing. One way to solve Eq. 3 is calculating the partial derivative of $\rho$ with respect to $\mu$ , which implies to introduce the influence function as $\psi\left({x,\hat{{\mu}}}\right)=\frac{\partial}{\partial\mu}\left({\rho\left(% {x,\mu}\right)}\right)$ , this constraint is valid only if the following conditions are met: $\rho$ is symmetric, positive-definite function with a unique minimum at zero, as well as differentiable with respect to $\mu$ , the solution can be obtained by:

$\sum\limits_{i=1}^{n}{\psi\left({x_{i}-\hat{{\mu}}}\right)=0}$ (3)

where, $\psi(x)$ is generally an odd, continuous and sign-preserving function that in most cases of interest considers that $\psi(0)=0$ and $\psi^{\prime}(0)$ exists. The major disadvantage of M-Estimators is their implicit definition, which requires iterative techniques to calculate the output. An intuitive solution can be derived by assuming $\lim\limits_{x\to 0}\frac{\psi(x)}{x}=c$ , this solution implies to write Eq. 3 as:

$\sum\limits_{i=1}^{n}{\psi\left({x_{i}-\hat{{\mu}}}\right)=\sum\limits_{x_{i}% \neq 0}{\frac{\psi\left({x_{i}-\hat{{\mu}}}\right)}{\left({x_{i}-\hat{{\mu}}}% \right)}}}\cdot\left({x_{i}-\hat{{\mu}}}\right)$ (4)

The expression Eq. 4 can be reformulated by using the weight function $w$ in the next way:

$\hat{{\mu}}^{k+1}=\frac{\displaystyle\sum\limits_{i=1}^{n}{w_{i,\hat{{\mu}}}^{% k}}\cdot x_{i}}{\displaystyle\sum\limits_{i=1}^{n}{w_{i,\hat{{\mu}}}^{k}}},∼{}% ∼{}∼{}w_{i,\hat{{\mu}}}=\begin{cases}{{\displaystyle\frac{\psi\left({x_{i}-% \hat{{\mu}}}\right)}{\left({x_{i}-\hat{{\mu}}}\right)}}}&{x_{i}\neq 0}\\ c&\text{otherwise}\\ \end{cases}$ (5)

This reformulation is usually referred as the W-Estimator, the weight function in Eq. 5 reflects the importance of the sample in its contribution to the estimate of $\hat{{\mu}}$ . In general, a point having a small residual has a weight close to one, whereas a point with a large, generally corresponding to an impulse (outlier) should have a small weight [18].

The expression Eq. 5 allows to get a single result. In [18], it was indicated that an iterative newton method required only five iterations to get a location estimate $\hat{{\mu}}$ , with an absolute error less than 0.01. In this study, we have considered using the M-Estimators to constrain the magnitude of all salt or pepper impulses, as well as to remove them when it is necessary, a better alternative for our purposes is to use the Redescending M-Estimators. To establish them, it is required a threshold $r$ , which suggests the bounds of the influence function [20], such that:

$\psi_{(r)}(x)=\left\{{\psi(x)=0∼{}∼{}\forall|x|\geqslant r}\right\}$ (6)

where, $r$ ranges from $0<r<\infty$ . The Redescending M-Estimators are designed to vanish outside of central region, their logic is that the very central observations receive the maximum weight, if they depart from the center, their weights are declined, and when they reach specified bounds, their function $\psi$ -function becomes 0. It is convenient to take note of the Winsor’s principle quoted by Tukey [23], which states: “All distributions are approximately normal in the middle”. If this consideration is done on the Redescending M-Estimators, it means that the central section of the $\psi$ -functions resembles with that of the mean that is linear, and this linearity is the main reason of highest efficiency of the mean under the assumption of normality. Thus, $\psi$ -functions with optimal efficiency will be approximately linear near the origin: $\psi(x)\approx x$ . Some of the earliest $\psi$ -functions presented in the literature were Huber Skipped Mean, Simple Cut, Tukey Biweight, Andrew’s Sine, Bernoulli, German-MacClure, Hampel’s Three Part Redescending [3, 5, 11, 18, 23]. Recently, Qadir Beta Function, Insha, Alamgir and Modified Tukey’s Biweight (Ali and Qadir) [2, 11] have been proposed. The most popular influence functions in the literature (Simple-Cut, Andrew’s Sine, Tukey Biweight, Hampel’s Three Part Redescending and Insha) are analyzed and evaluated in this study in order to identify which of them makes to the Redescending M-Estimator more effective in the task of removing salt or pepper impulses, their mathematical definitions and graphical representations are summarized in Table 1.

Table 1

Influence functions test in the Redescending M-Estimator

Influence function	Formulae	Graphical representation
Simple-Cut	$\psi_{\textit{SC}(r)}(x)=\begin{cases}x&{0\leqslant\|x\|\leqslant r}\\ 0&{r\leqslant\|x\|}\\ \end{cases}$
Andrew’s Sine	$\psi_{\textit{SIN}(r)}(x)=\begin{cases}{x\cdot\sin\left({{\displaystyle\frac{x% }{r}}}\right)}&{0\leqslant\|x\|\leqslant r\cdot\pi}\\ 0&{r\cdot\pi\leqslant\|x\|}\\ \end{cases}$
Tukey Biweight	$\psi_{\textit{BI}(r)}(x)=\begin{cases}{x\cdot\left[{1-\left({{\displaystyle% \frac{x}{r}}}\right)^{2}}\right]^{2}}&{0\leqslant\|x\|\leqslant r}\\ 0&{r\leqslant\|x\|}\\ \end{cases}$
Hampel’s Three Part Redescending	$\psi_{\textit{HAM}\left({a,b,r}\right)}(x)=\begin{cases}x&{0\leqslant\|x\|% \leqslant a}\\ {a\cdot{\rm sgn}(x)}&{a\leqslant\|x\|\leqslant b}\\ {a\cdot{\displaystyle\frac{r-\|x\|}{r-b}}}&{b\leqslant\|x\|\leqslant r}\\ 0&{r\leqslant\|x\|}\\ \end{cases}$
Insha	$\psi_{I(r)}(x)=\begin{cases}{x\cdot\left[{1+\left({{\displaystyle\frac{x}{c}}}% \right)^{4}}\right]^{2}}&{\|x\|\geqslant 0}\\ \end{cases}$

The Median-Estimator is a well-known robust estimator of location; it is based on the order statistics. This concept has played an important role in statistical data analysis and especially in the robust analysis of data contaminated with outlying observations, called outliers (impulses) [18]. The order statistics suggests that a data sample $x_{(1)},x_{(2)},\ldots,x_{(n)}$ can be arranged in ascending order of magnitude and then written as $x_{(1)}\leqslant x_{(2)}\leqslant\ldots\leqslant x_{(n)}$ ; where, $x_{\left(i\right)}$ is the so-called $i$ -th order statistic, $x_{(1)}$ is the minimum value and $x_{(n)}$ is the maximum value in the sample. The Median-Estimator is expressed by:

$\hat{{\mu}}=\begin{cases}{x_{\left({\frac{n+1}{2}}\right)}}&\text{for odd $n$}% \\ {{\displaystyle\frac{1}{2}}\cdot\left({x_{\left({\frac{n}{2}}\right)}+x_{\left% ({\frac{n+1}{2}}\right)}}\right)}&\text{for even $n$}\\ \end{cases}$ (7)

3. Proposed denoising scheme

A successful proposal to remove the Salt and Pepper noise in grayscale images involves both the noise suppression and the preservation of the fine details of the images. For this purpose, we propose a scheme based on robust estimators of location, in addition of an impulse detector. Accordingly, our method consists of two stages: detection and suppression. Both procedures are described in the following subsections.

3.1 Stage 1: Impulse noise detector

Each pixel of the noisy image $\tilde{{x}}_{i,j}$ and its neighboring pixels are analyzed by the impulse noise detector in order to identify it as noiseless or noisy, the impulse detector considers a sliding square window $h$ with size of $n\times n$ pixels and centered at $(i,j)$ . Besides, it is based on two conditions, the first one identifies if the pixel of interest has the minimum and maximum value in the window ( $\min(h)$ and $\max(h)$ , respectively), when this condition is satisfied the pixel can be considered as an impulse. However, marking all pixels with an extreme gray value as noisy pixels results in a false detection of some uncorrupted pixels as corrupted. Therefore, a second condition is established, this analyzes the variability among all the pixels in the square window, to determine this dispersion we considered the median of the absolute deviations around the median ( ${\rm mad}(h)$ ). Thus, if the pixel of interest is not an extreme value and its neighborhood has a variability smaller than 0.5, it can be considered as noiseless and then it is retained, by other hand if both conditions are not satisfied the pixel is considered as noisy. By convenience we call the pixel being analyzed as $x_{c}$ . The mathematical formulation of the impulse detector can be written as:

$\left({\left({\min(h)<x_{c}}\right)\wedge\left({x_{c}<\max(h)}\right)}\right)% \wedge\left({{\rm mad}(h)<0.5}\right)$ (8)

where, $h$ is a square window with size of 5 $\times$ 5 pixels, $x_{c}$ is the central pixel in each window $h$ (it implies that $x_{c}$ is $\tilde{{x}}_{3,3}$ ), $\min(h)$ obtains the smallest value of $h$ , $\max(h)$ calculates the largest value of $h$ , ${\rm mad}(h)$ determines the median of the absolute deviations around the median of all elements in $h$ and 0.5 is a threshold obtained by experimentation.

3.2 Impulse noise suppressor

The mathematical expression Eq. 6 considers both negative and positive $x$ values; however, in grayscale digital images this parameter ranges from 0 to 255. It means that just the positive part of the influence functions (as those suggested in Table 1) is used, in other words, we restrict the ability of the Redescending M-Estimators. We suggest two ways to compensate this limitation: (1) select the most appropriate pixels to the suppression process by using the absolute deviations around the median $|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}|$ instead of $|x|$ , where $\vec{{h}}$ is obtained after transforming the square window $h$ in a vector and $\tilde{{x}}_{i}$ is the $i$ -th element of the vector $\vec{{h}}$ ; (2) consider a more selective threshold $r$ or constant parameter $c$ . Taking into account the first remark we can rewrite Eq. 6 as:

$\psi_{(r)}\left({\tilde{{x}}_{i}}\right)=\left\{{\psi({\tilde{{x}}_{i}})=0∼{}∼% {}\forall|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}|\geqslant r}\right\}$ (9)

According to Eq. 9, the influence functions listed in Table 1 have to be rewritten in terms of the absolute deviations around the median; for this purpose, we propose to do it such as it is depicted in Table 2. In addition, we suggest some adaptive ways to compute more selective thresholds.

Table 2

Modified influence functions test in the redescending M-Estimator

Influence function	Formulae	Thresholds
Simple-Cut	$\psi_{\textit{SC}(r)}({\tilde{{x}}_{i}})=\begin{cases}{\tilde{{x}}_{i}}&{0% \leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|\leqslant r}\\ 0&{r\leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|}\\ \end{cases}$	$r=1.483\cdot{\rm MED}({\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|})$
Andrew’s Sine	$\psi_{\textit{SIN}(r)}\left({\tilde{{x}}_{i}}\right)=\begin{cases}{\tilde{{x}}% _{i}\cdot\sin\left({{\displaystyle\frac{\tilde{{x}}_{i}}{r}}}\right)}&{0% \leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|\leqslant r\cdot\pi}\\ 0&{r\cdot\pi\leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|}\\ \end{cases}$	$r={({2\cdot{\rm MED}\{{\vec{{h}}}\}})}/\pi$
Tukey Biweight	$\psi_{\textit{BI}(r)}\left({\tilde{{x}}_{i}}\right)=\begin{cases}{\tilde{{x}}_% {i}\cdot\left[{1-\left({{\displaystyle\frac{\tilde{{x}}_{i}}{r}}}\right)^{2}}% \right]^{2}}&{0\leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|\leqslant r% }\\ 0&{r\leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|}\\ \end{cases}$	$r=\sqrt{2}\cdot{\rm MED}\{{\vec{{h}}}\}$
Hampel’s Three Part Redescending	$\psi_{\textit{HAM}({a,b,r})}({\tilde{{x}}_{i}})=\begin{cases}{\tilde{{x}}_{i}}% &{0\leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|\leqslant a}\\ {a\cdot{\rm sgn}\left({\tilde{{x}}_{i}}\right)}&{a\leqslant\|{\tilde{{x}}_{i}-{% \rm MED}\{{\vec{{h}}}\}}\|\leqslant b}\\ {a\cdot{\displaystyle\frac{\tilde{{x}}_{i}-\|{\tilde{{x}}_{i}}\|}{r-b}}}&{b% \leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|\leqslant r}\\ 0&{r\leqslant\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|}\\ \end{cases}$	$r=1.483\cdot{\rm MED}({\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|})$ $a=0.05\cdot r$ $b=0.95\cdot r$
Insha	$\psi_{I(r)}({\tilde{{x}}_{i}})=\begin{cases}{\tilde{{x}}_{i}\cdot\left[{1+% \left({{\displaystyle\frac{\tilde{{x}}_{i}}{c}}}\right)^{4}}\right]^{2}}&{\|{% \tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|\geqslant 0}\\ \end{cases}$	$c=1.483\cdot{\rm MED}({\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|})$

As it can be seen in Table 2, the first four influence functions adjust the intensity of some pixels and stand at $0$ those bigger than the threshold $r$ , in contrast the last one just modifies the intensity of pixels. In order to not consider elements with a zero value, we select the $\psi_{(r)}\left({\tilde{{x}}_{i}}\right)>0$ elements, by simplicity we call them as $\psi_{(r)}\left({\tilde{{x}}_{sel}}\right)$ .

Finally, to obtain an estimate of a noiseless pixel, the expression Eq. 9 is introduced into the Median-Estimator Eq. 7, this procedure is done considering just the $\psi_{(r)}\left({\tilde{{x}}_{sel}}\right)$ elements, such that is suggested the next equation:

$\hat{{\mu}}_{\textit{MM}}=\begin{cases}{\psi_{r}\left({\tilde{{x}}_{sel_{\left% ({\frac{n+1}{2}}\right)}}}\right)}&\text{for odd $n$}\\ {{\displaystyle\frac{1}{2}}\cdot\left({\psi_{r}\left({\tilde{{x}}_{sel_{\left(% {\frac{n}{2}}\right)}}}\right)+\psi_{r}\left({\tilde{{x}}_{sel_{\left({\frac{n% }{2}+1}\right)}}}\right)}\right)}&\text{for even $n$}\\ \end{cases}$ (10)

where, $n$ is a parameter that depends on the quantity of selected elements. By joining the Redescending M-Estimator and the Median-Estimator we can guarantee the suppression of impulsive noise without destroy fine details on the images.

3.3 Proposed algorithm

The proposed algorithm is summarized as follows:

Algorithm 1. Impulse noise suppression scheme proposed
Input: $X$ : The noisy image with size $M\times N$
Initialize: $h_{\textit{size}}\leftarrow 2$ : Sliding window size $\left({2\times h_{\textit{size}}+1}\right)\times\left({2\cdot h_{\textit{size}% }+1}\right)$ . Select an influence function suggested in Table 1
1: for $i=1+h_{\textit{size}}$ to $M-h_{\textit{size}}$ do
2: for $j=1+h_{\textit{size}}$ to $M-h_{\textit{size}}$ do
3: $h\leftarrow$ Load pixels //sliding square window $h$ with a size of 5 $\times$ 5 pixels
4: if $\left({\left({\min(h)<x_{c}}\right)\wedge\left({x_{c}<\min(h)}\right)}\right)% \wedge\left({{\rm mad}(h)<0.5}\right)$ then
5: $Y\left({i-h_{\textit{size}},j-h_{\textit{size}}}\right)\leftarrow x_{c}$ // $x_{c}$ is considered as noiseless and is retained
6: else // $x_{c}$ must be filtered
7: $\vec{{h}}\leftarrow h$ //convert $h$ in a vector
8: for $i=1,\ldots,25$ do //5 $\times$ 5 implies 25 pixels
9: Calculate $\psi_{r}\left({\tilde{{x}}_{i}}\right)$ //apply the Redescending M-Estimator taking into account
$\|{\tilde{{x}}_{i}-{\rm MED}\{{\vec{{h}}}\}}\|$
10: end for
11: $\psi_{r}({\tilde{{x}}_{sel}})\leftarrow\psi_{r}({\tilde{{x}}_{i}})$ //select $\psi_{(r)}\left({\tilde{{x}}_{i}}\right)>0$
12: Calculate $n$ //count the number of elements in $\psi_{r}\left({\tilde{{x}}_{\textit{sel}}}\right)$
13: if $n$ is even then
14: $\hat{{\mu}}_{\textit{MM}}\leftarrow{\displaystyle\frac{1}{2}}\cdot\left({\psi_% {r}\left({\tilde{{x}}_{sel_{\left({\frac{n}{2}}\right)}}}\right)+\psi_{r}\left% ({\tilde{{x}}_{sel_{\left({\frac{n}{2}+1}\right)}}}\right)}\right)$
15: else
16: $\hat{{\mu}}_{\textit{MM}}\leftarrow\psi_{r}\left({\tilde{{x}}_{sel_{\left({% \frac{n+1}{2}}\right)}}}\right)$
17: end if
18: $Y\left({i-h_{\textit{size}},j-h_{\textit{size}}}\right)\leftarrow\hat{{\mu}}_{% \textit{MM}}$
19: end if
20: end for
21: end for
Output: $Y$ : The filtered image with size $M\times N$

To provide a better efficiency and performance of our proposal we recommend working with rectangular windows, with a size of 5 $\times$ 5 pixels. Smaller windows can be impractical due the Median-Estimator may not have enough information and therefore give a wrong result; on the other hand, larger windows do not guarantee better results than those obtained by the suggested size.

Table 3
Restoration results in PSNR (dB) terms, for the existing and proposed methods

Image	Noise	ETSS	REMF	RAMF	NLM-DBUTM	IAFF	MRME ${}_{\text{SC}}$	MRME ${}_{\text{AS}}$	MRME ${}_{\text{TB}}$	MRME ${}_{\text{HTPR}}$	MRME ${}_{\text{I}}$
	density
Lena	10%	43.322	34.588	44.484	36.325	43.800	46.320	45.992	46.460	47.117	46.717
	30%	38.989	28.999	40.323	30.870	39.254	40.988	40.492	40.759	43.350	41.000
	50%	34.105	25.481	35.044	26.548	34.313	38.343	37.788	38.261	40.548	38.538
	70%	30.766	22.112	33.997	22.382	31.612	36.368	36.066	35.876	37.763	36.649
Peppers	10%	41.213	33.716	43.219	34.007	42.073	44.675	44.102	44.425	46.178	44.788
	30%	37.085	28.947	39.087	29.449	36.625	41.425	40.625	40.867	43.615	41.391
	50%	32.413	25.262	35.034	26.901	32.783	38.640	37.758	38.684	40.644	39.089
	70%	29.107	21.653	32.109	22.149	29.704	36.708	36.043	36.686	37.979	36.948
Baboon	10%	32.155	32.317	38.296	33.905	31.816	39.096	38.799	39.220	40.640	39.076
	30%	27.161	27.830	36.224	28.305	27.818	35.598	35.395	35.279	37.388	35.463
	50%	24.015	24.050	30.304	25.862	24.581	33.162	32.706	33.078	34.794	33.213
	70%	22.492	20.002	23.507	20.684	22.282	31.659	31.388	31.454	32.757	31.687
Barbara	10%	33.615	32.697	37.523	33.080	34.577	41.685	41.412	41.669	42.894	41.447
	30%	28.135	28.872	30.227	29.362	28.114	37.888	37.530	37.467	39.471	37.891
	50%	23.215	24.622	28.681	25.823	23.655	35.419	34.884	35.146	37.085	35.278
	70%	22.173	20.952	27.490	21.875	24.153	33.534	33.319	33.484	35.127	33.804

Table 4

Restoration results in MAE terms, for the existing and proposed methods

Image	Noise	ETSS	REMF	RAMF	NLM-DBUTM	IAFF	MRME ${}_{\text{SC}}$	MRME ${}_{\text{AS}}$	MRME ${}_{\text{TB}}$	MRME ${}_{\text{HTPR}}$	MRME ${}_{\text{I}}$
	density
Lena	10%	0.442	0.880	0.442	0.763	0.502	0.219	0.358	0.252	0.210	0.229
	30%	0.956	1.866	0.956	1.808	0.967	0.733	0.903	0.779	0.496	0.750
	50%	1.544	2.880	1.544	2.844	1.580	1.291	1.496	1.321	0.848	1.259
	70%	2.473	3.608	2.473	3.547	2.491	2.079	2.384	2.385	1.545	2.078
Peppers	10%	0.552	0.963	0.552	0.949	0.580	0.288	0.355	0.345	0.206	0.286
	30%	1.080	2.069	1.080	2.049	1.116	0.740	0.899	0.766	0.441	0.720
	50%	1.807	2.703	1.807	2.562	1.870	1.278	1.548	1.353	0.893	1.210
	70%	2.725	4.113	2.725	3.970	2.732	2.059	2.439	2.159	1.504	1.995
Baboon	10%	1.273	1.704	1.273	1.618	1.408	1.101	1.215	1.134	0.778	1.143
	30%	3.750	3.944	3.750	3.935	3.892	2.475	2.817	2.526	1.569	2.482
	50%	5.488	5.997	5.488	5.962	5.562	4.226	4.769	4.314	2.713	4.200
	70%	8.237	8.874	8.237	8.821	8.310	6.364	7.177	6.479	4.388	6.323
Barbara	10%	0.948	1.395	0.948	1.272	0.999	0.723	0.788	0.738	0.470	0.704
	30%	2.128	2.446	2.128	2.444	2.263	1.583	1.815	1.607	0.957	1.570
	50%	3.837	4.018	3.837	4.012	3.892	2.757	3.144	2.818	1.749	2.712
	70%	6.846	7.396	6.846	7.371	6.863	4.117	4.669	4.216	2.801	4.058

4. Results and discussions

Experimental tests were carried out on the well-known grayscale images Lena, Peppers, Baboon and Barbara; all of them with a size of 512 $\times$ 512 pixels. In the simulation, images were corrupted by “salt” (with value 255) and “pepper” (with value 0) noise with equal probability, the noise levels considered were 10%, 30%, 50% and 70%.

The performance of our scheme (using different influence functions) was compared with five state-of-the-art filtering methods designed to suppress Salt and Pepper noise, such as the Efficient Three-Stage Scheme (ETSS) [10], Recursive and Enhanced Median Filtering (REMF) [19], Non Local Means-Decision Based Unsymmetric Trimmed Median (NLM-DBUTM) [9], Recursive and Adaptive Median Filter (RAMF) [17], Iterative Adaptive Fuzzy Filter (IAFF) [11]. We identified our scheme as Median Redescending M-Estimator (MRME), the influences functions analyzed Simple Cut (SC), Andrew’s Sine (AS), Tukey Biweight (TB), Hampel’s Three Part Redescending (HTPR) and Insha (I) were expressed as subscripts; therefore, the notation used was: MRME ${}_{\text{SC}}$ , MRME ${}_{\text{AS}}$ , MRME ${}_{\text{TB}}$ , MRME ${}_{\text{HTPR}}$ and MRME ${}_{\text{I}}$ .

Figure 1.

Graphical illustrations of the comparative PSNR (dB) for the existing and proposed method: (a) Lena image, (b) Peppers image, (c) Baboon image, (d) Barbara image.

Figure 2.

Graphical illustrations of the comparative MAE for the existing and proposed method: (a) Lena image, (b) Peppers image, (c) Baboon image, (d) Barbara image.

Figure 3.

Peppers images rendered by the proposed and competing algorithms: (a) original noise-free image, (b) 30% noise corrupted; (c) ETSS, (d) REMF, (e) RAMF, (f) NLM-DBUTM, (g) IAFF, (h) MRME ${}_{\text{SC}}$ , (i) MRME ${}_{\text{AS}}$ , (j) MRME ${}_{\text{TB}}$ , (k) MRME ${}_{\text{HTPR}}$ , (l) MRME ${}_{\text{I}}$ .

4.1 Quantitative evaluation

To evaluate the filtering quality two aspects are considered. The first one, is related with the performance of noise suppression and is evaluated using the peak signal-to-noise ratio (PSNR) [4, 25]. The second one, quantifies the fine detail preservation and is determined by the mean absolute error (MAE) [25]. Both criterions are given by next expressions:

$\textit{PSNR}=10\cdot\log\left[{\frac{\left({255}\right)^{2}}{\textit{MSE}}}\right]$ (11)

where, MSE is the mean square error and can be determined as:

$\textit{MSE}=\frac{1}{M\cdot N}\sum\limits_{i=1}^{M}{\sum\limits_{j=1}^{N}{% \left[{x\left({i,j}\right)-\hat{{e}}\left({i,j}\right)}\right]^{2}}}$ (12)

where, $M\cdot N$ is the image size, $x\left({i,j}\right)$ is the original image and $\hat{{e}}\left({i,j}\right)$ is the restored or filtered image. Moreover, the MAE is quantified by:

$\textit{MAE}=\frac{1}{M\cdot N}\sum\limits_{i=1}^{M}{\sum\limits_{j=1}^{N}{% \left|{x\left({i,j}\right)-\hat{{e}}\left({i,j}\right)}\right|}}$ (13)

After analyzing the simulation results summarized in Table 3, we can observe that in the PSNR (dB) judgment standard, the performance of our proposed method considering all influence functions was better than all comparative methods. In detail, the highest PSNR values were obtained when was evaluated the Hampel’s Three Part Redescending influence function, followed it by Insha, Simple Cut, Tukey Biweight and Andrew’s Sine. It should be highlighted that all comparative methods had a high performance; especially the Recursive and Adaptive Median Filter, since its skills to remove salt and pepper noise are nearly alike our method, when was evaluated whit the Andrew’s Sine influence function. On the other hand, the preservation of details was quantified by the MAE metric, in Table 4 are listed the results obtained. On the basis of these results we reaffirm the capacity of our proposal, because the lowest values were those obtained when the Hampel’s Three Part Redescending influence function was used into our scheme. An argument to justify its best performance is the fact that the pixels falling in the central region (that goes from $a$ to $b$ ) receive greater weight than those that fall in limiting regions (0 to $a$ or $b$ to $r$ ).

Figure 4.

Baboon images rendered by the proposed and competing algorithms: (a) original noise-free image, (b) 50% noise corrupted; (c) ETSS, (d) REMF, (e) RAMF, (f) NLM-DBUTM, (g) IAFF, (h) MRME ${}_{\text{SC}}$ , (i) MRME ${}_{\text{AS}}$ , (j) MRME ${}_{\text{TB}}$ , (k) MRME ${}_{\text{HTPR}}$ , (l) MRME ${}_{\text{I}}$ .

Graphical representations of the comparative PSNR and MAE results are depicted in Figs 1 and 2, respectively. Both illustrations reveal that the suggested scheme has a steadier performance than all comparative methods, regardless of the influence function evaluated into the Redescending M-Estimator. In addition, it can be seen that the efficiency of our proposal decreased proportionally when the noise density increased. The complexity of the analyzed images has a strong influence on the performance of all methods, this can be verified simply by analyzing the PNSR results obtained on Lena and Baboon images, since there exists a difference between 2 and 5 decibels in measurements.

Figure 5.

Lena images rendered by the proposed and competing algorithms: (a) original noise-free image, (b) 70% noise corrupted; (c) ETSS, (d) REMF, (e) RAMF, (f) NLM-DBUTM, (g) IAFF, (h) MRME ${}_{\text{SC}}$ , (i) MRME ${}_{\text{AS}}$ , (j) MRME ${}_{\text{TB}}$ , (k) MRME ${}_{\text{HTPR}}$ , (l) MRME ${}_{\text{I}}$ .

4.2 Qualitative evaluation

Besides the quantitative evaluation described in previous paragraph, a qualitative evaluation is necessary since the visual assessment of the processed images is ultimately the best subjective measure of the effectiveness of any method. For this purpose, the images Peppers, Baboon and Lena were considered to illustrate the noise suppression capability as well as the details preservation. In order to view the details, a zoomed-in section of each image restored is displayed in each figure.

In the first instance, the Peppers test image was corrupted with a density 30% of salt and pepper noise, the results obtained are depicted in Fig. 3, the visual inspection reveals that all algorithms have the capability of noise suppression; however, the proposed method has greater detail preservation than all comparative methods.

On the other hand, when the Baboon image was corrupted by a 50% of impulse noise, some comparative methods reduced their performance, since they allowed to some impulses remain after the suppression process, it can be seen in Figs 4(c), (d), (f) and (g). In contrast, our proposal and the REMF method were able to remove successfully the impulses, such as it is shown in Figs 4(d), (h)–(l). It is obvious that the proposed method has the excellent ability of noise attenuation because there is not impulse noise left in the restored image.

Figure 5 exhibits the restored images when Lena image was corrupted with 70% of impulsive noise. As we see it, all comparative methods were unable to suppress the noise; besides, they damaged the edges of the images filtered. In their own part, all influence functions evaluated in this study allowed our method to remove the salt and pepper impulses; however, only the Hampel’s Three Part Redescending influence function (MRME ${}_{\text{HTPR}}$ ) retained the fine image details.

Finally, numerous simulation results presented in this article show that the proposed method provides significantly good results in the testing images corrupted by different percentages of impulse noise, and outperforms the other conventional filters under consideration.

5. Conclusions

We introduced a scheme based on robust estimators to suppress Salt and Pepper noise in grayscale images. The proposed method not only achieved better noise suppression results than all comparative schemes, but also had better details preservation; both abilities were verified by quantitative and qualitative results obtained by extensive simulations. Looking at the detail, the best performance was obtained when the Hampel’s Three Part Redescending influence function was evaluated into our Median Redescending M-Estimator proposal, due this influence function has more control on the contribution of each pixel. The only drawback of our scheme is its time processing, it takes from 4 to 6 seconds denoising an image with a size of 512 $\times$ 512 pixels. As a future research, we will consider the possibility of decreasing the processing time, by using parallel processing implemented on a hybrid system conformed by a CPU together with a GPU; as well as enhance the capacity of suppression up to 80% of noise density, on the basis of the Redescending M-Estimators with a Hampel’s Three Part Redescending influence function.

Footnotes

Acknowledgments

The authors are grateful with the editor and with the reviewers for their valuable comments and insightful suggestions, which can help to improve this research significantly. The authors thank the Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET), Tecnológico Nacional de México (TecNM) and CONACYT for their financial support.

References

Ahmed

and Das

, Removal of high-density salt-and-pepper noise in images with an iterative adaptive fuzzy filter using alpha-trimmed mean, IEEE Transactions on Fuzzy Systems 22 (2014), 1352–1358.

Ali

and Qadir

M.F.

, A modified m-estimator for the detection of outliers, Pakistan Journal of Statistics and Operation Research 1 (2005).

Andrews

D.F.

and Hampel

F.R.

, Robust Estimates of Location: Survey and Advances, Princeton University Press, 2015.

Astola

and Kuosmanen

, Fundamentals of Nonlinear Digital Filtering, CRC press, 1997.

Beaton

A.E.

and Tukey

J.W.

, The fitting of power series, meaning polynomials, illustrated on band-spectroscopic data, Technometrics 16 (1974), 147–185.

Bovik

A.C.

, The Essential Guide to Image Processing, Academic Press, 2009.

Chou

H.-H.

Hsu

L.-Y.

and Hu

H.-T.

, Turbulent-PSO-based fuzzy image filter with no-reference measures for high-density impulse noise, IEEE Transactions on Cybernetics 43 (2013), 296–307.

Frigui

and Krishnapuram

, A robust algorithm for automatic extraction of an unknown number of clusters from noisy data, Pattern Recognition Letters 17 (1996), 1223–1232.

Gao

and Liu

, An efficient three-stage approach for removing salt & pepper noise from digital images, Optik-International Journal for Light and Electron Optics 126 (2015), 467–471.

10.

Gayathri

and Srinivasan

, An efficient algorithm for image denoising using NLM and DBUTM estimation, in: TENCON 2014–2014 IEEE Region 10 Conference, IEEE, (2014), 1–6.

11.

Hampel

F.R.

Ronchetti

E.M.

Rousseeuw

P.J.

and Stahel

W.A.

, Robust Statistics: The Approach Based on Influence Functions, John Wiley & Sons, 2011.

12.

Hodges

J.L.

, Jr. and Lehmann

E.L.

, Estimates of location based on rank tests, The Annals of Mathematical Statistics (1963), 598–611.

13.

Huber

P.J.

, The basic types of estimates, Robust Statistics (1981), 43–72.

14.

Ibrahim

Neo

K.C.

Teoh

S.H.

T.F.

Chieh

D.C.J.

and Hassan

N.N.

, Impulse noise model and its variations, International Journal of Computer and Electrical Engineering 4 (2012), 647.

15.

Sun

and Luo

, A neuro-fuzzy network based impulse noise filtering for gray scale images, Neurocomputing 127 (2014), 190–199.

16.

Maronna

Martin

R.D.

and Yohai

, Robust Statistics, John Wiley & Sons, Chichester, ISBN, 2006.

17.

Meher

S.K.

and Singhawat

, An improved recursive and adaptive median filter for high density impulse noise, AEU-International Journal of Electronics and Communications 68 (2014), 1173–1179.

18.

Pitas

and Venetsanopoulos

A.N.

, Order statistics in digital image processing, Proceedings of the IEEE 80 (1992), 1893–1921.

19.

Sharma

and Chaurasia

, Removal of high density salt-and-pepper noise by recursive enhanced median filtering, in: Emerging Technology Trends in Electronics, Communication and Networking (ET2ECN), 2014 2nd International Conference on, IEEE, (2014), 1–4.

20.

Shevlyakov

Morgenthaler

and Shurygin

, Redescending M-Estimators, Journal of Statistical Planning and Inference 138 (2008), 2906–2917.

21.

Smolka

Andrzejczak

Nabialkowski

and Nelip

, Thresholded median filter for the impulsive noise removal in digital images, in: Information, Intelligence, Systems and Applications, IISA 2014, The 5th International Conference on, IEEE, (2014), 355–360.

22.

Statistics

, The Approach Based on Influence Functions, New York, 1986.

23.

Tukey

J.W.

, A survey of sampling from contaminated distributions, Contributions to Probability and Statistics 2 (1960), 448–485.

24.

Ullah

Qadir

M.F.

and Ali

, Insha’s Redescending M-Estimator for Robust Regression: A Comparative Study, Pakistan Journal of Statistics and Operation Research 2 (2006).

25.

Vijaykumar

Vanathi

Kanagasabapathy

and Ebenezer

, Robust statistics based algorithm to remove salt and pepper noise in images, International Journal of Information and Communication Engineering 5 (2009), 164–173.

26.

Zhang

and Wang

, A switching median–mean filter for removal of high-density impulse noise from digital images, Optik-International Journal for Light and Electron Optics 126 (2015), 956–961.