A Survey of Non Local Means Algorithm

A Survey of Non Local Means Algorithm

Sumana T1, S. Nathelda Mary Navina 2

1 PG Scholar, Department of Computer Science and Engineering, Karunya University ,Coimbatore, Tamil Nadu, India

2 Assisstant Professor, Department of Computer Science and Engineering, Karunya University, Coimbatore, Tamil Nadu, India

Abstract

Image denoising is the process which is used to remove the noise from the image. Different filters are used for performing denoising. Non-local means (NLM) filter is one of the algorithms which are used for image denoising. The main problem of basic NLM is the high computational cost and complexity. The basic NLM algorithm is improved in different ways. In this paper we are comparing these different methods.

1. Introduction

   Image noise can be defined as the random variation of brightness or color information in images. Necessary details are hidden due to the presence of noise in image. Image denoising is the process which is used to remove the noise from the image. Different filters are used for performing denoising. A large number of different image denoising algorithms are used and they are classified as spatial domain filtering and transform domain filtering. The transform domain filtering can achieve better performance but it needs higher computational cost

   NLM

   Restored Image

   Input image added with white Gaussian noise

   Algorithm

   Figure 1 Denoising

2. NLM Algorithm

   The NLM is used for denoising an image. Several changes are performed in the basic NLM to improve the performance.

   2.1 Original NLM Algorithm [1],[2]

   1. Buades et al. [1] [2] proposed a non-local means algorithm for image denoising. To measure, the method noise, to evaluate and compare the performance of digital image denoising methods. If

      v vi i I is the noisy image, then the

      estimated value will be NL[v](i), for a pixel i, is computed as a weighted average of all the pixels in the image [2],

      also. Spatial domain filtering is further classified into linear and nonlinear filters. Linear filters were easy to design and implement. Non-local means filter is one of the filter in spatial domain filtering. Non-local

      NL[v](i)=

      w(i,

      jI

      j)v( j)

      means filter is averaging all observed pixels to recover a single pixel. The performance of NLM is enhanced by fast NLM [3], adaptive NLM [4], NLM with PCA [5], NLM with SURE [6], mean conservation NLM [7] and NLM with variable window size [8]. The figure Figure1 shows NLM algorithm.

      Where the weights wi, j depend on the

      j

      similarity between the pixels i and j. And the similarity between the two pixels i and j depends on the similarity of the intensity grey level vectors v(Ni ) and v(N j ) . Where N k denotes a square neighbourhood of fixed size and centered at a pixel k as a decreasing function of the weighted Euclidean

      distance. The weighted Euclidean distance can be

      2

      expressed as following [2] compared with the predefined threshold value. If the

      j

      || v(Ni ) v(N

      deviation.

      ) ||2 , where a>0 is the standard

      statistical feature exceeds the predefined threshold value then the window will be excluded from the further calculation. This technique is the fast way to exclude the dissimilar windows, which needs less

      i

      j

      The Euclidean distance for the noisy neighborhoods will raise the following equality [2],

      computation time. The preclassification with the skewness feature increases the total computation time

      i

      j

      E vN vN

      2

      2,a

      uN uN

      2

      2,a

      2 2

      with a couple of seconds that is because of the fact

      that the original noiseless image consists merely of black and white pixels. The gain in computation time

      And the weight can be calculated as in [1],

      ||v( Ni )v( N j )||2 ,a

      2

      is depends on the image content. This algorithm produces much sharper denoised images with few artifacts. Fast NLM even outperforms state-of-the-art

      w(i, j)

      1 e p

      z(i)

      wavelet denoising techniques in both visual quality and PSNR values for images containing a lot of

      Where Z (i) is the normalizing constant and can be expressed as in [2],

      || v(N ) v(N ) ||2 , a

      repetitive structures such as textures: the denoised

      images are much sharper and contain few artifacts. And it can also be applied in other image processing tasks which employ the concept of repetitive

      Z (i) e

      j

      i i 2

      p

      structures such as intra-frame super-resolution or detection of digital image forgery. The performance

      The parameter h will be acts as a degree of filtering.

      And h controls the decay of the exponential function and therefore the decay of the weights as a function of the Euclidean distances. The NL-means filter estimates a noise-free intensity as a weighted average of all pixel intensities in the image, and the weights are proportional to the similarity between the local neighbourhood of the pixel being processed and the local neighbourhoods of the surrounding pixels. The main advantage of this technique is to redundancy to be restored by NL-means and very powerful of preserving image details when denoising. The disadvantage of this techniques more complex and computationally expensive, if this method is directly used to the impulse noise, the weights would be wrong because the impulse noisy pixels are very different to their neighbours and do not contain any useful information unlike to the Gaussian noise.

      1. Fast NLM [3]

         Fast NLM is the method which is used to improve the basic NLM algorithm. The original NLM algorithm has high computational cost because of the enormous amount of weight computations. It calculates weights for both similar and dissimilar windows. In this algorithm the dissimilar windows are ignored. The dissimilar widows are eliminated by setting their corresponding weights to zero because there is no use to compute the zero-weights of dissimilar windows. A preclassification technique is needed to compute the most of the pixel. Then the similar windows are selected. Three statistical moments of the pixel intensities located in the window such as mean, variance and skewness is

         of NLM algorithm can be improved by using this method.

      2. Adaptive NLM [4]

         The Adaptive NLM (ANL) algorithm first employs the SVD method and the K-means clustering (K- means) technique for robust block classification in noisy images. And the local window is adaptively adjusted to match the local property of the block. Finally, a rotated block matching algorithm is used for better similarity matching. The block classification is achieved by applying the Singular Value Decomposition (SVD). The K-means clustering is used for classifying the acquired data, because there is no preferred direction for noise. It is easy to classify each noisy block effectively based on its singular value. Based on the denoising results from various experimental settings, ANL-means algorithm is shown to have a superior performance in both PSNR and perceptual quality compared to the traditional NL-means algorithm. The performance of NLM algorithm can be improved by using this method. The computational complexity can be reduced by this method.

      3. NLM with PCA [5]

         The Principal Component Analysis (PCA) is used with the NLM. PCA is one of the dimensionality reduction methods. By using this methodthe neighbourhood vectors are projected onto a lower dimensional subspace. And then the neighbourhood

         similarity weights are computed using the distance in this subspace instead using the distance in full space. The drawback of the original NLM algorithm is the high computational cost. The image neighbourhood vectors are typically high dimensional. For example, if 7 X 7 neighbourhoods are used then it will be 49 dimensional. Therefore the computation of similarities between features vectors lead to large computational cost. When the neighbourhood vectors are projected onto lower subspace it will save the computational cost. The lower-dimensional projections are not only used as a search criteria but also can be for computing neighborhood similarities resulting in increased accuracy in addition to reduced computational cost. And can also be easily applied to other denoising and segmentation algorithms that use similarity measures based on image neighborhood vectors. In all cases, NLM with PCA outperforms the standard non-local means algorithm.

      4. NLM with SURE [6]

         SURE stands for Steins Unbiased Risk Estimate. The SURE is used for monitoring the Means Square Error (MSE) of the NLM algorithm which is used for restoring an image that is corrupted with additive white Gaussian noise. By using the SURE it is possible to assess the MSE without the knowledge of noise free signal.

      5. Mean conservation NLM [7]

         In this method the constraint of mean conservation is imposed on NLM through adding to the restored image of NLM with a compensation image. The compensation image is obtained by processing the method noise of NLM. To impose the constraint of mean conservation on NLM, a compensation procedure is proposed as post process of NLM. The compensation procedure generates an image such as compensation from method noise and then compensates it to the restored noise free image. The constraint of mean conservation can help to recover the part of meaningful content that wrongly removed by NLM. The compensation procedure can be viewed as a denoising process applied on the method noise. Instead of applying denoising algorithm directly, the proposed denoising process is not performed independently on the method noise but tightly coupled with NLM. Experiments show that the compensation procedure can significantly improve the performance of NLM. This method is capable of imposing mean conservation on NLM by compensating the restored image of NLM with a compensation image, which is obtained from the

         method noise through a weighted distributing process. The remaining noise of NLM can be effectively identified through the compensation. The compensation procedure improves the performance of NLM significantly.

      6. NLM with variable window size [8]

      Non-Local means (NL-means) filter is used for removing the noise. Most of image denoising techniques require a region size called neighborhood window for denoising. The window-size selection is usually done by visual inspection based upon experience or hit and trial. In this technique the window-size for each pixel is varying according to the window variance and which results better performance. There are some problems with the fixed size similarity window. In case of large window, some details could be removed from the image, blurring singular points that are pixels with no similar patches, like image corners and peaks or valleys. And averaging them with non-similar patches, otherwise, in case of small window, there will be a lot of patches that are similar to the current patch, and that will results to non-accurate estimation. Which means that, in flat regions , large similarity window is needed, in other regions containing a lot of details (high variance), small window size is needed in order to find similar patches and to estimate the current pixel more accurately. The optimum h parameter is proportional to the noise standard deviation and inversely proportional to the window size. And the results show that the performance is very close and in some cases even surpasses state-of-art denoising techniques. .

      Figure2 shows the result of different NLM filtering methods. Figure Figure 2(a) shows the original image [2], 2(b) image added with white Gaussian noise [3], 2(c) image shows the restored image after the original NLM algorithm [3], 2(d) shows the restored image after the fast NLM [3],2(e) shows the restored image after the adaptive NLM [4] and finally 2(f) shows performance measures in [6].

      And table TABLE1 compare the PSNR value of various NLM methods [2],[3],[4],[7],[8] on lena image.

3. Conclusion

   In this paper, we discussed different NLM filtering techniques for denoising the image. The original NLM is compared with other different techniques that are used for improving the performance of basic NLM.

   (a) Original Image (b) Image added with white Gaussian noise

   (c) Original NLM (d) Fast NLM

   (e) Adaptive NLM (f) Performance measures Figure 2 Denoised Image

   International Journal of Engineering Research & Technology (IJERT)

   ISSN: 2278-0181

   Vol. 1 Issue 10, December- 2012

   Table 1.Comapare the PSNR values of various NLM methods in lena image

   S.NO	Method	PSNR value
   [2.1]	Original NLM	29.56
   [2.2]	Fast NLM	31.00
   [2.3]	Adaptive NLM	31.98
   [2.4]	MCNLM	32.00
   [2.5]	NL-means with Adaptive similarity window size	32.273

4. References

1. A. Buades, B. Coll, and J. Morel,, A review of image denoising algorithms, with a new one, SIAM Interdisciplinary J.: Multiscale Model Simulat., vol. 4, no. 2, pp. 290530, 2005.

2. A. Buades, B. Coll, and J. M. Morel, A non-local algorithm for image denoising, in Proc. Int. Conf. Computer. Vis. Pattern Recognit., 2005, pp. 6065.

3. A. Dauwe, B. Goossens, H.Q. Luong and W. Philips, A Fast Non-Local Image Denoising Algorithm, Proc. of SPIE-IS&T Electronic Imaging,Vol. 6812, 681210, 2008.

4. Tanaphol Thaipanich, Byung Tae Oh, Ping-Hao Wu and C.-C. Jay Kuo,Adaptive Nonlocal Means Algorithm for Image Denoising, CA 90089-2564, USA

5. Tolga Tasdizen, Principal components for non-local means image denoising, Electrical and Computer Engineering Department, University of Utah

6. Dimitri Van De Ville, Michel Kocher, SURE-Based Non-Local Means, IEEE signal Processing letters, vol. 16, no. 11, November2009.

7. Hao Xu, Jizheng Xu, Feng Wu , A Post- Compensation Scheme For Nonlocal Means Filter Based Image Restoration , 15th IEEE International Conference on Image Processing (ICIP 2008), 2008.

8. Ammar M. Alhosainy and Ehab F. Badran, Adapted Non-Local Means Filter using Variable Window Size,International Conference for Image and Signal Processing (ICIT09).