Fast non-local means algorithm based on Krawtchouk moments

Abstract

Non-local means (NLM) method is a state-of-the-art denoising algorithm, which replaces each pixel with a weighted average of all the pixels in the image. However, the huge computational complexity makes it impractical for real applications. Thus, a fast non-local means algorithm based on Krawtchouk moments is proposed to improve the denoising performance and reduce the computing time. Krawtchouk moments of each image patch are calculated and used in the subsequent similarity measure in order to perform a weighted averaging. Instead of computing the Euclidean distance of two image patches, the similarity measure is obtained by low-order Krawtchouk moments, which can reduce a lot of computational complexity. Since Krawtchouk moments can extract local features and have a good antinoise ability, they can classify the useful information out of noise and provide an accurate similarity measure. Detailed experiments demonstrate that the proposed method outperforms the original NLM method and other moment-based methods according to a comprehensive consideration on subjective visual quality, method noise, peak signal to noise ratio (PSNR), structural similarity (SSIM) index and computing time. Most importantly, the proposed method is around 35 times faster than the original NLM method.

Keywords

image processing / image denoising / non-local means / Krawtchouk moments / similarity measure

References

[1] Easley G, Labate D, Lim W Q. Sparse directional image representations using the discrete shearlet transform[J]. Applied and Computational Harmonic Analysis, 2008, 25(1): 25-46.

[2] Lim W Q. The discrete shearlet transform: A new directional transform and compactly supported shearlet frames[J]. IEEE Transactions on Image Processing, 2010, 19(5): 1166-1180.

[3] Easley G R, Labate D, Colonna F. Shearlet-based total variation diffusion for denoising[J]. IEEE Transactions on Image Processing, 2009, 18(2): 260-268.

[4] Buades A, Coll B, Morel J M. The staircasing effect in neighborhood filters and its solution[J]. IEEE Transactions on Image Processing, 2006, 15(6): 1499-1505.

[5] Buades A, Coll B, Morel J M. A review of image denoising algorithms, with a new one[J]. Multiscale Modeling & Simulation, 2005, 4(2): 490-530.

[6] Buades A, Coll B, Morel J M. Image denoising methods: A new nonlocal principle[J]. SIAM Review, 2010, 52(1): 113-147.

[7] Mahmoudi M, Sapiro G. Fast image and video denoising via nonlocal means of similar neighborhoods[J]. IEEE Signal Processing Letters, 2005, 12(12): 839-842.

[8] Coupé P, Yger P, Barillot C. Larsen R. Fast Non-local means denoising for 3D MR images[C]. Medical Image Computing and Computer-Assisted Intervention-MICCAI 2006, 2006, 33-40.

[9] Tasdizen T. Principal neighborhood dictionaries for nonlocal means image denoising[J]. IEEE Transactions on Image Processing, 2009, 18(12): 2649-2660.

[10] Yan R, Shao L, Cvetkovic S D, et al. Improved nonlocal means based on pre-classification and invariant block matching[J]. Journal of Display Technology, 2012, 8(4): 212-218.

[11] Orchard J, Ebrahimi M, Wong A. Efficient nonlocalmeans denoising using the SVD[C]. 15th IEEE International Conference on Image Processing, 2008, 1732-1735.

[12] Ji Z, Chen Q, Sun Q S, et al. A moment-based nonlocalmeans algorithm for image denoising[J]. Information Processing Letters, 2009, 109(23/24): 1238-1244.

[13] Grewenig S, Zimmer S, Weickert J. Rotationally invariant similarity measures for nonlocal image denoising[J]. Journal of Visual Communication and Image Representation, 2011, 22(2): 117-130.

[14] Wang J, Yin C. A Zernike-moment-based non-local denoising filter for cryo-EM images[J]. Science China Life Sciences, 2013, 56(4): 384-390.

[15] Yap P-T, PARAMESRAN R, ONG S-H. Image analysis by Krawtchouk moments[J]. IEEE Transactions on Image Processing, 2003, 12(11): 1367-1377.

[16] Cha S H. Comprehensive survey on distance/similarity measures between probability density functions[J]. International Journal of Mathematical Models and Methods in Applied Sciences, 2007, 1(2): 300-307.

[17] Deledalle C A, Denis L, Tupin F. How to compare noisy patches? Patch similarity beyond Gaussian noise[J]. International Journal of Computer Vision, 2012, 99(1): 86-102.

[18] Goldfarb D, Yin W. Parametric maximum flow algorithms for fast total variation minimization[J]. SIAM Journal on Scientific Computing, 2009, 31(5): 3712-3743.

[19] Tomasi C, Manduchi R. Bilateral filtering for gray and color images[C]. Sixth International Conference on Computer Vision, 1998, 839-846.

[20] Salmon J, Willett R, Arias-Castro E. A two-stage denoising filter: The preprocessed Yaroslavsky filter[C]. 2012 IEEE Statistical Signal Processing Workshop (SSP), 2012, 464-467.