 Open Access
 Total Downloads : 617
 Authors : Sumana T, S. Nathelda Mary Navina
 Paper ID : IJERTV1IS10243
 Volume & Issue : Volume 01, Issue 10 (December 2012)
 Published (First Online): 28122012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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. Nonlocal 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.

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

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]

Buades et al. [1] [2] proposed a nonlocal 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. Nonlocal means filter is one of the filter in spatial domain filtering. Nonlocal
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 stateoftheart
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 intraframe superresolution 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 NLmeans filter estimates a noisefree 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 NLmeans 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.

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 zeroweights 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.

Adaptive NLM [4]
The Adaptive NLM (ANL) algorithm first employs the SVD method and the Kmeans 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 Kmeans 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, ANLmeans algorithm is shown to have a superior performance in both PSNR and perceptual quality compared to the traditional NLmeans algorithm. The performance of NLM algorithm can be improved by using this method. The computational complexity can be reduced by this method.

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 lowerdimensional 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 nonlocal means algorithm.

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.

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.

NLM with variable window size [8]
NonLocal means (NLmeans) filter is used for removing the noise. Most of image denoising techniques require a region size called neighborhood window for denoising. The windowsize selection is usually done by visual inspection based upon experience or hit and trial. In this technique the windowsize 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 nonsimilar 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 nonaccurate 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 stateofart 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.



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: 22780181
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] NLmeans with Adaptive similarity window size
32.273

References

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.

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

A. Dauwe, B. Goossens, H.Q. Luong and W. Philips, A Fast NonLocal Image Denoising Algorithm, Proc. of SPIEIS&T Electronic Imaging,Vol. 6812, 681210, 2008.

Tanaphol Thaipanich, Byung Tae Oh, PingHao Wu and C.C. Jay Kuo,Adaptive Nonlocal Means Algorithm for Image Denoising, CA 900892564, USA

Tolga Tasdizen, Principal components for nonlocal means image denoising, Electrical and Computer Engineering Department, University of Utah

Dimitri Van De Ville, Michel Kocher, SUREBased NonLocal Means, IEEE signal Processing letters, vol. 16, no. 11, November2009.

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.

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