A Survey of Non-Local Means based Filters for Image Denoising

A Survey of Non-Local Means based Filters for Image Denoising

A Survey of Non-Local Means based Filters for Image Denoising

Beshiba Wilson

Department of Information Technology Lourdes Matha College of Science & Technology

Thiruvananthapuram, Kerala, India

Dr.Julia Punitha Malar Dhas

Department of Computer Science & Engineering Noorul Islam University

Thuckalay, Tamilnadu, India

AbstractImage denoising involves the manipulation of the image data to produce a visually high quality image. The Non- Local means filter is originally designed for Gaussian noise removal and the filter is modified to adapt for speckle noise reduction. Speckle noise is a primary source of medical ultrasound imaging noise and it should be filtered out. This paper reviews the existing Non-Local Means based filters for image denoising.

C x, y = A x, y + B(x, y) (1) where A(x,y) is the original image pixel value, B(x,y) is the

noise in the image and C(x,y) is the resulting noise image.

1. Gaussian Noise

   The Gaussian noise has a Gaussian distribution [1] which has a bell shaped probability distribution function given by,

   2

   2

   2

   2

   (gm)2

   Keywordsdenoising; gaussian noise; speckle noise; Non- Local Means;

   F g = 1 e

   22

   (2)

   1. INTRODUCTION

      Noise represents unwanted information which deteriorates image quality. Non-Local based filters are mainly used to remove Gaussian and speckle noise. Gaussian noise is statistical noise that has a probability density function of the normal distribution. It is most commonly used as additive white noise to yield additive white Gaussian noise. Gaussian noise is evenly distributed over the signal [1]. Each pixel in the noisy image is the sum of the true pixel value and a random Gaussian distributed noise value.

      where g represents the gray level, m is the mean or average of the function and is the standard deviation of the noise.

2. Speckle noise

g

g

Speckle noise [3] is a multiplicative noise. This type of noise occurs in almost all coherent imaging systems such as laser, acoustics and SAR(Synthetic Aperture Radar) imagery. Speckle degrades the quality of ultrasound images and reduces the ability of a human observer to discriminate the fine details of diagnostic examination. Speckle noise follows a gamma distribution and is given as

Speckle noise is a granular noise that inherently exists in and degrades the quality of images. Speckle noise is modeled

1

g

g

F g =

1 !a

e a

(3)

as spatial correlated multiplicative noise [2]. Noise is introduced at all stages of Image acquisition. Speckle reduction is a critical preprocessing step for extraction of features, analysis and recognition from medical ultrasound image measurements. Commonly used linear low-pass filters, such as the mean filters are not suitable for reducing the speckle noise of ultrasound images since they eliminate the high frequencies and thus tend to smooth out the image edges.

The rest of the paper is organized as follows: Section II presents the Model of Gaussian and Speckle noise. Section III presents a survey of various Non-Local Means based filters for image denoising. Section IV illustrates various parameters used for analyzing the performance of denoising filters. Finally our conclusions are presented in Section V.

1. NOISE MODELING

   Noise may be modeled either by a histogram or a

   where the variance is 2 and g is the gray level.

2. NON-LOCAL MEANS BASED FILTERS FOR IMAGE DENOISING

   Spatial domain filtering is classified into linear and nonlinear filters. Non-Local means filter is one of the spatial domain filter. A single pixel is recovered by averaging all observed pixels in Non-local means filtering [4]. Many changes are performed in the original Non-local means filter to improve the performance.

   1. Original Non-Local means algorithm

      The non-local means algorithm for noise removal was proposed by A. Buades et al. [4][5]. The estimated value NL[v](i), for a pixel i, given a discrete noisy image v =

      v i | i I , is computed as a weighted average of all the pixels in the image[4],

      probability density function which is superimposed on the probability density function of the original image. A noisy image is modeled as,

      NL v i = jI w i, j v(j)

      (4)

      where the weights {w(i,j)}j depend on the similarity between the pixels i and j, and the conditions 0 w(i,j ) 1 and

      j w i, j = 1 are satisfied.

      Two pixels i and j are similar if the intensity gray level vectors v(Ni) and v(Nj) are similar, where Nk denotes a square neighborhood of fixed size and centered at a pixel k. This similarity is measured as a decreasing function of the weighted

      where g(i) is a noisy pixel, is the shape parameter.

      1. NL-means filter: For each pixel i in the ML filtered image f ML,

         1. Take the search window i and the neighborhood window Ni ;

         2. For each pixel j in the search window, compute d(i,j), Z(i) Compare the and w(i,j).

            2,

            2,

            Euclidean distance [4] v Ni v(Nj) 2 , where a>0 is the

            standard deviation of Gaussian kernel. The Euclidean distance when applied to noisy neighborhoods raises the following equality [4],

            2

            d i, j = G g Ni g Nj

            (3)

            E v N v(N ) 2

            = u N u(N ) 2

            + 22 (5)

            where G is a normalized Gaussian weighted function with

            i j 2,a

            i j 2,a

            zero mean and standard deviation.

            The weights are defined as [4],

            Then w(i,j) is calculated as,

            1 v Ni v Nj 2

            1 d(i,j)

            w i, j =

            e

            z i

            2,a

            p

            w i, j =

            . exp(

            Z i p

            ) (4)

            where Z(i) is the normalizing constant

            Z i = exp

            d(i,j))

            (5)

            v Ni v Nj 2

            j1

            ( p

            = e

            2,a

            p

            Here Z(i) is the normalized constant. The parameter h acts as a degree of filtering.

            and the parameter h acts as a degree of filtering. It controls the decay of the exponential function and therefore the decay of weights as a function of the Euclidean distances. The advantage of this method is that it preserves image details when denoising.

         3. Given a discrete noisy image g = {g(i) | i I}, the filtered value NL(g(i)) is calculated as a weighted average of all pixels in the image.

            The experiments were simulated by adding Gaussian white

            NL g i = j1 w i, j g(i)

            (6)

            noise of standard deviation to the true image [4]. The objective was to compare the visual quality of the restored images, the non presence of artifacts and the correct reconstruction of edges, textures and details.

   2. Non-local means filter with maximum likelihood estimator

      Nonlocal-Means (NL-means) filter removes noise and enhances edge information [5]. Y.Guo et al proposed Modified Nonlocal based (MNL) filter [6] to adapt for the speckle reduction with the Rayleigh distribution noise.

      The MNL method consists of two steps. The maximum likelihood (ML) estimation to calculate the initial noise-free intensity is done first. Then the NL-means algorithm is used to restore details. The ML estimator does not retain fine structure details and usually makes edge blurred. MNL speckle filter includes ML estimator and NL-means filter.

      1. ML estimator: For each pixel i in the noise image g,

         li>

         Take the window i, which is defined as the neighbourhood of pixel i and Mi which is defined as a square neighborhood of pixel i;

         1. Compare the average intensity in i to discard unwanted ones;

         2. Compute the initial noise-free value fML(i) using

      1 2

      To evaluate the performance of the MNL, Y.Guo et al [6] optimized three parameters of the MNL and tested it on synthetic images and clinical ultrasonic images. The three optimized parameters are h (decay of exponential function), radius of similar neighborhood and radius of search window. The MNL performance was compared with six other filters namely NL means filter, ML estimator, Lee filter, Median filter, SRAD and Med-wavelet filter. The MNL can preserve more true edges, discarding the false ones. It suppresses the speckle in ultrasonic images. Since the MNL filter makes use of the image redundancy, it is time-consuming in 2- dimensional case.

   3. Bayesian Non-Local means based filter

      Coupe et al [7] proposed an adapted method based on Bayesian formulation of non-local means filter for speckle noise reduction. To reduce the computational complexity of the algorithm, a blockwise approach is introduced in which a weighted average of patches is performed instead of weighted average of pixel intensities. This approach includes the following:

      1. Paritioning the image into overlapping blocks Bik of size P=(2+1)d (d is the dimensionality of image) such as =UkBik.

      2. Restoration of a block Bik based on a non-local means scheme defined as

         f i = g

         (

         )1 = 1

         2

         2

         2

         n

         .

         .

         k=1

         g2 (ik )

         (2)

         NL u (Bik ) = Bj Vik w xik , xj u(Bj)

         (7)

         2

         2

         u B ik u B j 2

         1

         E. Non-local means filter with optimized weight kernel and novel neighborhood pre-classification strategy

         w xik , xj =

         e

         Zik

         h 2 (8)

         Rui et al [10] introduced an optimized weight kernel of

         i i i

         i i i

         where u B = u 1 B , , u P (B ) T is an image patch containing the intensities of the block Bi, Zik is a normalization constant.

      3. Restoring the pixels values based on the restored intensities of the blocks they belong to. The final restored intensity of pixel xi is defined as

      non-local means filter and an improved neighborhood pre- classification strategy. In original non-local means method, the similarity between two pixels i and j (also called weight) depends on their neighborhoods Nd{i} and Nd{j} multiplied by a Gaussian kernel. In order to make the neighborhoods with similar structure receive a larger weight, the weght kernel is modified as [10],

      d

      d 2 2

      NL u x = 1

      j

      j

      A (l) (9)

      w i, j = exp y N

      i y N

      (14)

      i Ai

      iAi i

      p

      In the non-local means algorithm, the weight computation

      Based on Bayesian interpretation of the non-local means filter [8], the blockwise NL means can be written as

      of dissimilar patches reduces the precision and increases the computational costs. Rui et al [10] designed a new type of filter to pre-classify the image patches according to similarity. Each patch is divided into four sub-patches evenly and the non-local

      ik

      ik

      1 V

      p u B

      u B )p(u B )u(B )

      patches are pre classified according to the ratio of the sum of

      NL u B

      = V ik

      j=1

      ik j

      j j

      (10)

      diagonal sub-patches, followed that the similar patches are used

      V ik

      V ik

      ik 1 p u B

      u B )p(u B )

      V ik j=1

      ik j j

      to calculate the weight as,

      where

      B ) and ( ) respectively

      w i, j ,

      jPa ,Pd y(j)

      a

      a

      j

      denote the distribution of u(Bik)|u(Bj) and the prior

      1 jP ,P

      < <

      < <

      d

      y(j) 2

      < <

      < <

      distribution of patches.

      Wpre i, j =

      and

      jPb ,Pc y(j)

      (15)

      Evaluations were performed on synthetic data with

      3 jP

      ,P c

      y(j) 4

      b

      b

      different noise levels and different speckle simulations [7]. Experiments [7] shows that the filter outperforms the

      0, otherwise

      classical implementation of the NL means filter as well as SRAD (Speckle Reducing Anisotropic Diffusion)and the SBF (Squeeze Box Filter).

   4. Median Non-Local means based filter

   Chung et al [9] proposed a method that incorporates a median filtering operation indirectly in the non-local means method. This provides more robust estimation of the weights used to average the pixels in the image. In this approach the weights are estimated from a media filtered version of the image rather than the noisy image. The weights are then used to average the pixels of the original noisy image. An auxiliary vector m, is defined as [9],

   m=Median (x,s) (11)

   where x is the observed noisy image, s is the window size for the median operator. The non-local mean is computed as a weighted average of all the pixels in image x in the search window defined as [9],

   NL xi = jN i wij (mi)xj (12)

   with

   1 mi mj 2

   It is noted from the denoised results [10], that this method effectively suppresses the noise and preserves more details.

3. PARAMETERS USED FOR PERFORMANCE ANALYSIS OF NON-LOCAL MEANS BASED FILTERS

   To determine the performance of the denoising filters in terms of efficiency of removal of noise and enhancement of useful image information, the following parameters are analyzed. Table I provides the metrics used for performance analysis.

4. CONCLUSION

The Non-Local means algorithm not only compares the grey level in a single point but the geometrical configuration in a whole neighborhood. The non-local means filter with maximum likelihood estimator suppresses speckle noise in ultrasound images. It yields better noise attenuation and edge enhancement. It works better for images with fine structures.

Bayesian non-local means based filter introduces the Pearson distance as a relevant measure for patch comparison. This filter outperforms the classical implementation of non- local means filter as well as the SRAD and SBF filters. The median non-local means filter suppress noise effectively without sacrificing low contrast details. The incorporation of

wij mi =

Z(i)

exp

2,a (13)

p

anatomical knowledge using segmentation free approach aided in preserving organ boundaries. The measure of similarity of

where Z(i) is the normalizing factor, mi and mj are two

vectors on the auxiliary image m . The median non-local means filter when combined with the anatomical knowledge

neighborhood with an optimized weight kernel and pre- classification of neighborhoods in the filtering process results in precise and effective non-local means based filter.

TABLE I. PARAMETERS FOR ANALYSIS OF PERFORMANCE OF NON-LOCAL MEANS BASED FILTERS

REFERENCES

1. Scott E. Umbaugh, Computer vision and image processing: A practical approach using CVIP tools, Prentice Hall, 1998.

2. Yong Yue, Mihai M. Croitoru, Akhil Bidani, Joseph B. Zwischenberger and John W. Clark, Nonlinear multiscale diffusion for speckle suppression and edge enhancement in ultrasoun images, IEEE Transactions on Medical Imaging, vol.25, 2006, pp. 297-311.

3. Langis Gagnon, Wavelet filtering of speckle noise- some numerical results,Proceedings of the Conference Vision Interface 1999, TroisRiveres.

4. Antoni Buades, Jean Michel Morel, A non-local algorithm for image denoising, Proc. Int. Conf. Computer Vis. Pattern Recognition, 2005, pp. 60-65.

5. A. Buades, B. Coll and J. Morel, A review of image denoising algorithms, with a new one,SIAM Interdisciplinary Journal of Multiscale Model Simulation, vol.4, 2005, pp. 290-530.

6. Y. Guo, Y. Wang, T. Hou, Speckle filtering of ultrasonic images using a modified nonlocal-based algorithm, Biomedical Signal Processing and control, Elsevier, pp.129-138, 2011.

7. Pierrick Coupe, Pierre Hellier, Charles Kervram and Christian Barillot, Bayesian non local means-based speckle filtering,IEEE International Symposium on Biomedical Iamging,2008.

8. C. Kervrann, J. Boulanger, Pierrick Coupe, Bayesian non-local means filter, image redundancy and adaptive dictionaries for noise removal, SSVM07 Proc of the 1st International conference on scale space and variational methods in computer vision,2007, pp. 520-532.

9. Chung Chan, Roger Fulton, David Dagan Feng, Steven Meikle, Median non-local means filtering for low SNR image denoising: Application to PET with anatomical knowledge,Nuclaer Science Symposium Conference Record, IEEE 2010.

10. Rui Lai, Xuan-xuan Dou, Improved non-local means filtering algorithm for image denoising, 3rd International Congress on Image and Signal Processing (CISP) 2010.