Image denoising via a non-local patch graph total variation

Autoři: Yan Zhang aff001;  Jiasong Wu aff001;  Youyong Kong aff001;  Gouenou Coatrieux aff004;  Huazhong Shu aff001
Působiště autorů: LIST, the Key Laboratory of Computer Network and Information Integration, Southeast University, Ministry of Education, Nanjing, China aff001;  Centre de Recherche en Information Biomédicale Sino-Français, Nanjing, China aff002;  International Joint Research Laboratory of Information Display and Visualization, Southeast University, Ministry of Education, Nanjing, China aff003;  IMT Atlantique, Inserm, LaTIM UMR, Brest, France aff004
Vyšlo v časopise: PLoS ONE 14(12)
Kategorie: Research Article
doi: 10.1371/journal.pone.0226067


Total variation (TV) based models are very popular in image denoising but suffer from some drawbacks. For example, local TV methods often cannot preserve edges and textures well when they face excessive smoothing. Non-local TV methods constitute an alternative, but their computational cost is huge. To overcome these issues, we propose an image denoising method named non-local patch graph total variation (NPGTV). Its main originality stands for the graph total variation method, which combines the total variation with graph signal processing. Schematically, we first construct a K-nearest graph from the original image using a non-local patch-based method. Then the model is solved with the Douglas-Rachford Splitting algorithm. By doing so, the image details can be well preserved while being denoised. Experiments conducted on several standard natural images illustrate the effectiveness of our method when compared to some other state-of-the-art denoising methods like classical total variation, non-local means filter (NLM), non-local graph based transform (NLGBT), adaptive graph-based total variation (AGTV).

Klíčová slova:

Algorithms – Baboons – Boats – Gaussian noise – Image processing – Imaging techniques – Optimization – Scientific publishing


1. Milanfar P. A tour of modern image filtering: New insights and methods, both practical and theoretical. IEEE Signal Process Mag. 2013;30: 106–128.

2. Karahanoglu FI, Bayram I, Van De Ville D. A signal processing approach to generalized 1-D total variation. IEEE Trans Signal Process. 2011;59: 5265–5274.

3. Kheradmand A, Milanfar P. A general framework for kernel similarity-based image denoising. Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE. pp. 415–418.

4. Buades A, Coll B, Morel J-M. A non-local algorithm for image denoising. Computer Vision and Pattern Recognition, CVPR 2005 IEEE Computer Society Conference on. IEEE; 2005. pp. 60–65.

5. Rudin LI, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Phys D Nonlinear Phenom. 1992;60: 259–268.

6. Buades A, Coll B, Morel J-M. A review of image denoising algorithms, with a new one. Multiscale Model Simul. 2005;4: 490–530.

7. Easley GR, Labate D, Colonna F. Shearlet-based total variation diffusion for denoising. IEEE Trans Image Process. 2009;18: 260–268. doi: 10.1109/TIP.2008.2008070 19095539

8. Zhang F, Hancock ER. Graph spectral image smoothing using the heat kernel. Pattern Recognit. 2008;41: 3328–3342.

9. Sandryhaila A, Moura JMF. Discrete signal processing on graphs. IEEE Trans signal Process. 2013;61: 1644–1656.

10. Pang J, Cheung G, Hu W, Au OC. Redefining self-similarity in natural images for denoising using graph signal gradient. Asia-Pacific Signal and Information Processing Association, 2014 Annual Summit and Conference (APSIPA). IEEE; 2014. pp. 1–8.

11. Mahmood F, Shahid N, Skoglund U, Vandergheynst P. Adaptive graph-based total variation for tomographic reconstructions. IEEE Signal Process Lett. 2018;25: 700–704.

12. You Y-L, Xu W, Tannenbaum A, Kaveh M. Behavioral analysis of anisotropic diffusion in image processing. IEEE Trans Image Process. 1996;5: 1539–1553. doi: 10.1109/83.541424 18290071

13. Smolka B, Wojciechowski KW. Random walk approach to image enhancement. Signal Processing. 2001;81: 465–482.

14. Black MJ, Sapiro G, Marimont DH, Heeger D. Robust anisotropic diffusion. IEEE Trans image Process. 1998;7: 421–432. doi: 10.1109/83.661192 18276262

15. Tomasi C, Manduchi R. Bilateral filtering for gray and color images. Computer Vision, 1998 Sixth International Conference on. IEEE; 1998. pp. 839–846.

16. Belkin M, Niyogi P. Towards a theoretical foundation for Laplacian-based manifold methods. COLT. Springer; 2005. pp. 486–500.

17. Grady LJ, Polimeni JR. Discrete calculus: Applied analysis on graphs for computational science. Springer Science & Business Media; 2010.

18. Shuman DI, Narang SK, Frossard P, Ortega A, Vandergheynst P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process Mag. 2013;30: 83–98.

19. Liu G, Huang T-Z, Liu J, Lv X-G. Total variation with overlapping group sparsity for image deblurring under impulse noise. PLoS One. 2015;10: e0122562. doi: 10.1371/journal.pone.0122562 25874860

20. Berger P, Hannak G, Matz G. Graph signal recovery via primal-dual algorithms for total variation minimization. IEEE J Sel Top Signal Process. 2017;11: 842–855.

21. Chen S, Sandryhaila A, Moura JMF, Kovačević J. Signal recovery on graphs: Variation minimization. IEEE Trans Signal Process. 2015;63: 4609–4624.

22. Hu W, Li X, Cheung G, Au O. Depth map denoising using graph-based transform and group sparsity. Multimedia Signal Processing (MMSP), 2013 IEEE 15th International Workshop on. IEEE; 2013. pp. 1–6.

23. Shakhnarovich G. Learning task-specific similarity. Massachusetts Institute of Technology; 2005.

24. Parikh N, Boyd S. Proximal algorithms. Found Trends® Optim. 2014;1: 127–239.

25. Combettes PL, Wajs VR. Signal recovery by proximal forward-backward splitting. Multiscale Model Simul. 2005;4: 1168–1200.

26. Combettes PL, Pesquet J-C. A Douglas–Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J Sel Top Signal Process. 2007;1: 564–574.

27. Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math with Appl. 1976;2: 17–40.

28. Zhu M, Chan T. An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Rep. 2008;34.

29. Combettes PL, Pesquet J-C. Proximal splitting methods in signal processing. Fixed-point algorithms for inverse problems in science and engineering. Springer; 2011. pp. 185–212.

30. Chaux C, Pesquet J-C, Pustelnik N. Nested iterative algorithms for convex constrained image recovery problems. SIAM J Imaging Sci. 2009;2: 730–762.

31. Dupé F-X, Fadili JM, Starck J-L. A proximal iteration for deconvolving Poisson noisy images using sparse representations. IEEE Trans Image Process. 2009;18: 310–321. doi: 10.1109/TIP.2008.2008223 19131301

32. Durand S, Fadili J, Nikolova M. Multiplicative noise removal using L1 fidelity on frame coefficients. J Math Imaging Vis. 2010;36: 201–226.

33. Setzer S, Steidl G, Teuber T. Deblurring Poissonian images by split Bregman techniques. J Vis Commun Image Represent. 2010;21: 193–199.

34. Bot RI, Hendrich C. A Douglas—Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators. SIAM J Optim. 2013;23: 2541–2565.

35. Muja M, Lowe DG. Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans Pattern Anal Mach Intell. 2014;36: 2227–2240. doi: 10.1109/TPAMI.2014.2321376 26353063

36. Juang Y-S, Ko L-T, Chen J-E, Shieh Y-S, Sung T-Y, Hsin HC. Histogram modification and wavelet transform for high performance watermarking. Math Probl Eng. 2012;2012.

37. Vogel CR, Oman ME. Iterative methods for total variation denoising. SIAM J Sci Comput. 1996;17: 227–238.

38. Wang Z, Bovik AC, Sheikh HR, Simoncelli EP. Image quality assessment: from error visibility to structural similarity. IEEE Trans image Process. 2004;13: 600–612. doi: 10.1109/tip.2003.819861 15376593

39. Cao X, Miao J, Xiao Y. Medical image segmentation of improved genetic algorithm research based on dictionary learning. World J Eng Technol. 2017;5: 90–96.

40. Kong Y, Deng Y, Dai Q. Discriminative clustering and feature selection for brain MRI segmentation. IEEE Signal Process Lett. 2014;22: 573–577.

41. Kong Y, Wu J, Yang G, Zuo Y, Chen Y, Shu H, et al. Iterative spatial fuzzy clustering for 3D brain magnetic resonance image supervoxel segmentation. J Neurosci Methods. 2019;311: 17–27. doi: 10.1016/j.jneumeth.2018.10.007 30315839

Článek vyšel v časopise


2019 Číslo 12