Non-Linear Noise Filtering

    Noise can be introduced into a image signal via a multitude of sources, such as communication channels, faulty digital circuitry, and thermal noise.   Depending on  statistical properties of the corruption, the noise may be harmless to the visual assessment of the signal.  But, such noise may also result in an image that is visually disconcerting or unpleasant.  For this and other reasons, signal noise suppression via various filtering operations has therefore been the subject of extensive research.  In the following paper, the impulse noise suppression characteristics of several nonlinear denoising filters will be examined and compared.
 

Linear versus Nonlinear Filtering

    Filtering operations can be very generally subdivided into linear and nonlinear methods.   Linear filtering theory yields optimal results when the signal corruption can be modeled as a Gaussian process and the accuracy criterion is the mean square error (MSE)  [1];  however, designing a filter based on these assumption frequently results in a filtered image that is more visually displeasing than the original noisy signal, even though the filtering operation successfully reduces the MSE.  Consider digital systems, where signal corruption is often the result of random bit errors.  Here the noise behaves in a (impulsive) clearly non-Gaussian manner.  It is in those cases where the assumptions of the classical linear theory are violated that the nonlinear methods prove most useful.

    In order to better understand the reasons behind the general use of nonlinear filters over linear filters in impulse noise suppression, it is helpful to analyze the noise removal and edge preservation properties and gamma filters.
 

Gamma Filter

    In the introduction of this paper, it was stated without proof that linear filters generally performed poorly at impulse noise suppression relative to nonlinear filters.  In the following section, visual support for this argument will be provided by comparing the filtering properties of the median filter with those of the gamma filter.  Gamma filters are natural special cases of maximum-likehood estimator, or M, filters.  Thus, if we assume that g > 0, then Q*, the estimate of the original pixel value, will be equal to the value of Q minimizing:

         S |Xi - Q|^g    ,
                        where the summation is over all Xi Îx,where x is a random vector

                                     (a)                                                                          (b)                                                                            (c)                                                                            (d)
   Fig. 1.   Gamma filtered images of a noisy Lena, window = 5x5:   (a) g = 1.0, MSE =59.84; (b) g = 1.25, MSE ; MSE =69.92  (c) g = 1.75,  MSE =132.41; (d) g = 2.00,  MSE =193.40.
 

Noise Model

    As previously mentioned,  the scope of this project is limited to the study of impulse noise removal.  Several distinct models exist for impulse noise.    "Pure" impulsive noise, i.e., impulsive noise in which a corrupted pixel takes on a gray scale value of either 0 or 255, is relatively simple to remove, since such maximal and minimal gray scale values occur relatively infrequently in actual images.   A more realistic and challenging, from a noise removal standpoint, is "bit error" impulsive noise.

Bit error impulsive noise can be quantitatively described as follows:

        Given an uncorrupted two-dimensional signal, s, such that each signal value is quantized to B bits, each s( i , j ) can be written as:

                                   s( i , j ) = k₁( i , j ) 2^B-1 + k₂( i , j ) 2^B-2+...+ k_B-1( i , j ) 2 + k_B( i , j ) ,    where k_m ( i , j )Î [0,1]  for all 1 < m < B and all i , j.

        If we now assume that each coefficient of each s( i , j ) is corrupted with probability p independently of all other coefficients in s( i , j ) and of all other signal
        values, then the corrupted signal values, x( i , j ), are of the form:

                                    x( i , j ) = k₁^*( i , j ) 2^B-1 + k₂^*( i , j ) 2^B-2+...+ k_B-1^*( i , j ) 2 + k_B^*( i , j ) ,

                                                            where k_m*( i , j ) = {  k_m( i , j ),       with probability 1-p;
                                                                                               1-k_m( i , j ),    with probability p      }

Note that noise model cannot be expressed as signal independent additive noise.
 

Study Images

    In the following sections, the impulse noise suppression properties of several nonlinear filters will be analyzed with reference to the corrupted forms of test image "Lena."  (See Figure 2 below.)    Lena was selected as a reference test image for several reasons.  First, Lena contains details and edges that are often difficult for filters to preserve, such as the hat-ribbon (a smooth region with fine texture), the feather (a high frequency, irregularly detailed structure), and multidirectional and curved edges.  In particular, the irregular details of the feather should be difficult for any filter effective at noise suppression to preserve, since such a filter must dampen high frequency image components.
    The robustness of each filter with respect to suppressing impulse noise is analyzed based on the ability of the filter to effectively suppress a wide range of impulse noise densities.  The following three impulse noise levels, with p denoting the probability of a single bit error, are examined:   1.)  p = 0.01; 2.) p= 0.045; 3.) and p =0.068.  The noisy versions of the Lena test image are displayed, along with the corresponding mean square errors,  in Figure 2 below:
 

                                      (a)                                                                            (b)                                                                         (c)                                                                             (d)
   Fig. 2.  (a)  Original Lena;  (b)   Lena image corrupted with impulse noise p = 0.01, MSE = 485.8; (c) Lena corrupted with impulse noise  p = 0.045,  MSE = 1782.8;   (d)  Lena
                corrupted  with impulse noise  p = 0.068,  MSE = 2559.5.
 
 

Filter Performance Evaluation Criterion

    In this project, the main objective is to filter noise so as to "optimally" restore the original image.   For visual images corrupted by impulse noise, optimal noise removal does not have a simple quantitative measure, since a filtered image with distracting artifacts may still result in a relatively small MSE.   Thus, overall visual quality must also be examined.  For each of the implemented filters, visual evaluation of filter performance will be made with respect to noise attenuation and detail and edge preservation.   Although MSE is also listed for each processed image, the MSE values should generally serve as a secondary indicators of filter performance.
 
 

Filtering Algorithms and Results

    In the following sections, the algorithms for and the properties of the tristate median filter (TSM) and the local-information (LI) filter will be detailed and compared.  The TSM filter merges rank-order filtering with decision-based filtering, while the LI filter incorporates information theoretic concepts into a decision- based filter.  When reading and interpreting the results presented, one should bare in mind that the nonlinear filtering techniques presented address a very specific noise removal problem based on the following assumptions: 1.) the noise source is impulse and 2.) the signal and the noise occupy the same frequency band.
    Each filter studied will be applied to each of the three noisy Lena images in order to evaluate filter performance over a range of noise levels.  In addition, each noisy image will be processed by each given filter type using three different window sizes, namely 3x3, 5x5, and 7x7, so that the dependence of noise suppression and edge preservation on window size can be evaluated for each filter.   Throughout the remainder of this document, it will be assumed that the size, N, of the moving window is odd, i.e. N= 2*k+1 (k  ¹ 1).  The set of observation samples inside the moving window will be denoted by {X₁,X₂,...X_N}.  The sample around which the window is centered and the filtering operation is performed is denoted by X*.
 

Tristate Median Filter

    In designing a noise reduction filter, the tradeoff between noise suppression and detail preservation must be addressed.  Ideally, if one desires to maximize noise suppression while preserving image details, the filtering operation should only be applied to noisy pixels, i.e., the filter should apply a robust criterion to a specified operation on window image pixels in order to determine if the center window pixel is corrupted.  Numerous different window operations and criterion have been proposed in literature. In the  decision-based tristate median filter (TSM), proposed by Tao Chen, Kai-Kuang Ma, and Li Hui Chen, the center window pixel is compared to the window standard median (SM) as well as to the window center-weighted median (CWM) in order to make a tristate decision concerning the "noisiness" of the center pixel.Before the tristate median filter can be further developed, a few words must be said about the standard and center-weighted median filters.
 

Standard Median
      Since the basic principles of estimation are closely related with nonlinear image processing, point estimators can be interpreted as filters.  One widely used point estimator is known as the R-estimator.  An rth ranked order filter assigns a rank to each observation X_i, and outputs the observation with rank r, i.e.,

                        X*_new = Ranked Order({X₁,X₂,...X_N, r}).

The standard median filter is simply a special case of  a rank-order filter, with r = k +1, where k = (N-1)/2 and is best-suited for use when the input noise distribution is symmetric about zero.
    Figure 3 gives the results of SM filter application to each of the three noisy Lena test images.  Each row of images in the figure matrix corresponds to a given pre-filtered noise level, with impulse noise density increasing from top to bottom.   Each column documents the results of local median filtering of a specific sliding-window size, with window size increasing from left  to right.  By analyzing these filtered images, one observes that SM filtering results in significant noise suppression at each of the three impulsive noise levels, although the degree of impulse noise removal is dependent on the sliding window size.
   One may also note that, although the median filters appears to preserve large, low frequency details quite well, finer details and irregular, high frequency details appear blurred.  In addition, sharp edges display square-like artifacts called "jaggies".

                                      (a)                                                                          (b)                                                                            (c)                                                                              (d)

 Fig. 3.    MSE's listed from top to bottom of each column; p values remain constant across rows:  (column a)  noisy images:  p = 0.01, p = 0.045, p = 0.068;  (column b)  SM filtered
                   images, 3x3 window:  MSE = 21.74,  MSE = 45.23, MSE =87.17;  (column c)  SM filtered images,  5x5 window:  MSE = 49.74, MSE = 59.84,  MSE = 71.37;  (column d)  SM
                   filtered images, 7x7 window:  MSE = 80.11, MSE =87.93, MSE =98.66.
 
 
 

Center Weighted Median Filter
  The CWM is a special case of  a weighted rank-order filter, of which the standard median is also a special case.   In the standard median filter, each sample within the filter window equally impacts the output of the median operation; however, the CWM filter achieves new filtering properties by giving enhanced emphasis to the center sample during the median operation.  The output of  the CWM filter can be described as follows:

                        Xnew* =  median({X₁,X₂,...X_N, c}) = median({X₁,X₂,..., X*, X*,..., X*,..., X_N}), where c copies of X* are including in the median operation
                                                                                                                                                        and c is a positive odd integer greater than 1.

    The results of the application of the center-weighted median filter to the noisy Lena images are shown in Figure 4.   The optimal weighting of the center pixel can be determined using a minimum MSE criterion.   The optimal c value for each of the processes images is listed along with the filtered image MSE  in Table 2 below.  As expected, the optimal value of c depends on the size of the sliding window and on the noise density.
    Note the significantly improved detail and edge preservation afforded by the CWM filter over the SM filter.  In particular, the irregular, high frequency details in the feather and the fine details of the hat-ribbon are well preserved relative to the same details in the uncorrupted Lena image; however, this increased detail and edge preservation comes at the expense of impulse noise removal.  By closely comparing the SM and CWM filter results for the noisy Lena images, one can see increased "graininess"  in the CWM-processed images over that observed in the SM-filtered images.  These optimized CWM filters are used in the tristate median filter operation.
 

                              (a)                                                                                (b)                                                                                (c)                                                                            (d)

 Fig. 4.   MSE and c pairs listed from top to bottom of each column; p values remain constant across rows:    (column a)  noisy images:  p = 0.01, p = 0.045, p=0.068;  (column b)
               CWM filtered images, 3x3 window:  MSE = 13.06,  c =3 , MSE = 43.29, c = 3, MSE = 87.76,  c =3 ;  (column c)  CWM filtered images, 5x5 window:  MSE = 17.51, c = 11,
               MSE = 41.17, c = 7, MSE = 56.30, c =5;  (column d)  CWM filtered images, 7x7 window:  MSE = 24.42, c = 27,  MSE = 56.98, c = 15, MSE =73.64, c = 9.
 
 

    The tristate median filter effectively combines the denoising properties of the SM filter with the edge/detail enhancement properties of the CWM filter by extracting the outputs of the SM and CWM filters for a given window and then comparing these values with the center window pixel value.  If the magnitude of the difference, d₁, between the SM output and the center pixel, is less than a user-specified threshold value TÎ[0,255], the center pixel value is assumed to be uncorrupted and remains unaltered during the filtering process; however, if the magnitude of the difference, d₂ , between the CWM output and the center pixel is greater than T, then the detector assumes a corrupted pixel.  Since the SM has improved noise suppression performance over the CWM filter, the TSM filter replaces the corrupted center pixel with the SM output.  The third state of the TSM filter corresponds to d₂ < T < d₁, in which the filter assumes that the pixel value is not sufficiently deviant to be noise, but most likely represents an edge or detail.  Since it is desirable to preserve details and edges during image filtering, the TSM filter substitutes the CWM output for the center pixel, effectively enhancing the edge or detail.  No further filter states exists, since it can be shown that d₂ is always less than or equal to d₁.
    From the above discussion, it should be clear that the performance of the tristate median filter depends intimately on the selected value of T.  Therefore, in order to optimize the selection of T, a minimum mean square error criterion was applied.  Based on these optimization results, the value of T can be said to display a clear dependence on noise level and window size.  The optimized values of T as well as the MSE values associated with the optimal T's are presented in Table 3 below.  Note that the values of the T's stay bounded between [10,30] for all window sizes and noise levels considered.  This indicates the T -comparison is a fairly robust criterion for determining if a pixel has been corrupted.  Also, since low MSE often does not correlate with high image quality,  a visual evaluation of the accuracy of the MSE optimization criterion for determining T was carried out.  Based on this subjective image quality evaluation, it appears that minimizing the MSE does indeed yield near optimal values of T.
 
 

    Figure 5 displays the images resulting from TSM processing of each of the three noisy image levels and for each of the three considered window sizes.  Comparison of  the overall noise suppression and detail preservation properties of the TSM filter with those of the CWM and SM filters indicates that for a relatively wide range of noise values, the TSM filter generally outperforms both the CWM and SM filters in subjective measure of noise removal and edge and detail preservation, although it sometimes results in greater MSE values than the CWM filter.
 

                                  (a)                                                                                (b)                                                                                (c)                                                                            (d)

    Fig. 5.   MSE and T pairs listed from top to bottom of each column; p values remain constant across rows:    (column a)  noisy images:  p = 0.01, p = 0.045, p=0.068;  (column b)
                  TSM filtered images, 3x3 window:  MSE = 9.10,  T =24 , MSE = 38.75, T = 12,  MSE = 82.97,  T = 12;  (column c)  TSM filtered images, 5x5 window:  MSE = 15.34, T = 27,
                  MSE = 43.29, T = 19, MSE = 60.01, T =12;  (column d)  TSM filtered images, 7x7 window:  MSE = 21.68, T = 27,  MSE = 58.78, T = 24, MSE =77.83, T = 24.
 
 

Local Information-Based Filtering Measure

As with the tristate median filter, the local information-based (LI) filter proposed by Azeddine Baghdadi and Ammar Khellaf represents a decision based filter; however, in contrast to the TSM filter, the LI filter decision criterion has its roots in an information theoretic quantity known as entropy.  Entropy is defined to be:

                 ^{H     =-} S ^{pi log( pi )},     where pi is the probability of event i.

In the case of image denoising, pi must be defined so that the resulting H yields a reliable measure of the degree of uncertainty that a pixel value is noise.  The LI filter introduced by Beghdadi and Khellaf attempts to identify corrupted pixels based on "local contrast entropy," i.e., the LI filter assumes a pixel to be corrupted if the local contrast is "significantly" different from the local contrast of the neighboring pixels.  The mathematical formulation of the local contrast, Ci, of the center window pixel is based on the Weber - Feschner law :

                                     Ci =   |gi - gi,avg|
                                                    gi,avg                where gi is the gray scale value of the center pixel,
                                                                                 and gi,avg is the mean gray scale value within the given sliding window.

Based on this local contrast measure,  pi can be defined as :        pi  =     Ci
                                                       S^Ci

Note that, with the above definition of Ci, the local contrast of a homogenous region is zero, and therefore the likelihood that a corrupted pixel will be identified within a homogenous local environment is zero.  On the other hand, an isolated noise pixel will have a relatively large impact on the resulting local entropy measure.  Maximum entropy corresponds to a local environment mimicking a sharp transition or ramp, where the number of gray scale values exceeding the mean equals the number of gray scale values below the mean.   We denote the local contrast probability of such a maximum entropy region as Pc.  Since the above definition of pi assumes that relatively homogenous regions are unlikely to contain corrupted pixels and since edge preservation is desirable, all pixels with pi < Pc  remain unaltered by the filtering operation, while all pixels with pi > Pc are identified as noise and are replaced by the local SM gray scale value.

Figure 6 illustrates the results of processing each of the noisy images with the proposed LI filter, while Table 4 lists the MSE values of each of the LI processed images.  Note that the LI filter performs extremely well in terms of noise suppression and detail preservation for p = 0.01; however, when the bit error probability is increased to p = 0.045, visually undesirable "graininess" becomes apparent in the filtered images.  This graininess is particularly pronounced for the case in which the probability of bit error equals 0.068.

Visual comparison of the performance of LI filter with those of the TSM, CWM, and S. filters indicates that the local information contrast measure is extremely effective at  edge and detail preservation and generally outperforms the TSM, CWM, and SM filters in this facet of image denoising; however, the relatively rapid decline in LI noise suppression capability with increasing bit error probability indicates that the noise suppression properties of the LI filter are clearly not as robust as those of the TSM.
 

                                (a)                                                                                (b)                                                                                (c)                                                                            (d)

    Fig. 6.   MSE and Pc pairs listed from top to bottom of each column; p values remain constant across rows:    (column a)  noisy images:  p = 0.01, p = 0.045, p=0.068;  (column b)
                  LI filtered images, 3x3 window:  MSE = 15.48,  Pc = 1/9 , MSE = 70.17, Pc = 1/25,  MSE = 154.54,  Pc = 1/49;  (column c)  LI filtered images, 5x5 window:  MSE = 32.49,
                  Pc = 1/9, MSE = 56.34, Pc = 1/25,  MSE = 98.42, Pc = 1/49;  (column d)  LI  filtered images, 7x7 window:  MSE = 55.38, Pc = 1/9,  MSE = 70.66, Pc = 1/25, MSE =109.25,
                  Pc = 1/49.
 
 

LI Filter Modification

In the above discussion on the LI filter, it was noted that the local contrast probability of a homogenous local region is zero.  Thus, according to the noise-decision criterion proposed by Bagdhadi and Khellaf, the probability of detecting noise in a homogenous local region is zero.  Although the assumption of "non-noisiness" of homogeneous regions holds quite well for relatively low noise densities (as demonstrated by the LI filter performance on the Lena image corrupted with impulse noise of  p = 0.01),  it represents a serious loophole in the decision criterion of the LI filter as noise levels increase.

As the noise density increases, the probability of clusters of  corrupted pixels with a diameter on the order of the window width also increases.  In addition, as the noise density increases, the probability of relatively homogenous noisy clusters also increases.  Noisy pixels central to such noise clusters will thus be assigned a local contrast probability less than Pc, implying that these noisy clusters will fail to be detected and suppressed.  In order for these relatively homogeneous noise clusters to be detected as noise, a second criterion or test must be applied to pixels with pi < Pc.

For homogenous noise clusters of diameter on the order of the window size,  the local contrast probabilities will be either zero or relatively small.  Thus, the variance of the local contrast probabilities for such a noise cluster will also be relatively small.   I therefore propose a "variance-test" criterion to detect and possibly suppress homogenous noise clusters.  As with the LI filter, pixels with pi > Pc will be replaced with the local window median; however, pixels with pi < Pc, will be subjected to a second criterion, namely if local variance of the local contrast probabilities window is below a user-optimized threshold, then the pixel is labeled as noise and its value is replaced by the local standard median of the next largest window size of which the current center pixel  is also the center.  The substituted median value is taken over a larger window size since it has been assumed that the homogenous cluster noise can have diameter on the order of the initial window size; thus, by expanding the window boundaries in calculating the replacement pixel value, we are effectively increasing the probability of replacing the noisy pixel with a more "accurate" image value.

It should be pointed out that the variance test fails to discriminate between noisy and non-noisy homogenous regions;  thus, non-noisy homogenous pixel clusters for which the local contrast probability variance falls below the defined threshold variance, will be replaced with the local SM of the next largest window.  This false positive will result in increased image blurring due to the nature of the SM filtering operation.   However, the threshold of the variance test can be designed so as to achieve an acceptable tradeoff between blurring and impulse noise cluster removal.

Figure 7 displays the result of the variance test as applied to the noisy Lena image with p = 0.045.  T , the variance threshold, equals 0.004 and the processing window size is  3x3.   Note that the presence of cluster impulse noise in has successfully been reduced, although not eliminated, by application of the modified LI filter.   This result is as expected since homogeneous clusters larger than the median window size cannot be eliminated by the standard median operation.  Also note that the modified LI filter shows increased detail blurring over the standard LI filter, as predicted.
 

                                    (a)                                                                                       (b)

Conclusions

In the above sections, the performance of the Standard Median, Center Weighted Median, Tristate Median, and Local Information Nonlinear filters in removing bit-error impulse noise was analyzed and compared.  Particular attention was paid to the ability of a filter to preserve edges and fine details while simultaneously suppressing impulse noise.  The tristate median filter effectively combines the edge preserving effects of the CWM filter with the denoising effects of the SM filter in a decision-based filter format, and generally outperforms the CWM and SM filters in subjective evaluations of noise suppression and detail preservation; however,
the effectiveness of the tristate median filter depends quite heavily on the selected decision threshold value.  The Local Information filter, which has its roots in the concepts of information theory, performed extremely well both in terms of noise suppression and detail and edge preservation at relatively low noise levels.  As noise levels increased, the noise suppression capabilities of the LI filter deteriorated quite rapidly.  Upon further examination of the filter decision criterion, I found that a loophole in the decision criterion allowed for relatively homogenous noise clusters, which become increasingly prevalent at higher noise densities, to pass through the LI filter undetected.  In order to improve the performance of the LI filter, a proposed and implemented a secondary decision loop based on the local variance of the local entropy probability.  Initial results indicate that this modified LI filter is able to effectively reduce the presence of impulse noise clusters while largely maintaining the detail preservation properties of the standard LI filter.
 
 
 
 
 
 
 
 

References
 

1.)Astola, Jaako and Pauli Kuosnanen. Fundamentals of Nonlinear Digital Filtering.   CRC Press.  New York, 1997.

2.)Beghdadi, Azeddine and Ammar Khellaf.  "A Noise Filtering Method Using a Local Information Measure."  IEEE Transactions on Image Processing.
    Vol. 6, No. 6.  June, 1997.

3.)Chen, Tao, Kai-Kuang Ma, and Lui-Hui Chen.  "Tristate Median Filter for Image Denoising."  IEEE Transactions on Image Processing,  Vol 8, No 12.
    Dec., 1999.