Convergence theorems for the Non-Local Means filter

Qiyu Jin; Ion Grama; Quansheng Liu

doi:10.3934/ipi.2018036

Article Contents

2018, Volume 12, Issue 4: 853-881. Doi: 10.3934/ipi.2018036

This issue Previous Article Geometric mode decomposition Next Article Use of an optimized spatial prior in D-bar reconstructions of EIT tank data

Convergence theorems for the Non-Local Means filter

1.
School of mathematical science, Inner Mongolia University, No.235 Daxuexilu Road, 010021 Hohhot, Inner Mongolia, China
2.
UMR 6205, Laboratoire de Mathématiques de Bretagne Atlantique, Université de Bretagne-Sud, Campus de Tohannic, BP 573, 56017 Vannes, France
3.
School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China

* Corresponding author: quansheng.liu@univ-ubs.fr
* Corresponding author: quansheng.liu@univ-ubs.fr

Received: March 2017

Revised: December 2017

Published: August 2018

Abstract Full Text(HTML) Figure(13) / Table(3) Related Papers Cited by

Abstract

We introduce an oracle filter for removing the Gaussian noise with weights depending on a similarity function. The usual Non-Local Means filter is obtained from this oracle filter by substituting the similarity function by an estimator based on similarity patches. When the sizes of the search window are chosen appropriately, it is shown that the oracle filter converges with the optimal rate. The same optimal convergence rate is preserved when the similarity function has suitable errors-in measurements. We also provide a statistical estimator of the similarity which converges at a convenient rate. Based on our convergence theorems, we propose some simple formulas for the choice of the parameters. Simulation results show that our choice of parameters improves the restoration quality of the filter compared with the usual choice of parameters in the original algorithm.

Keywords:

Mathematics Subject Classification: 62H35.

Citation:

Full Text(HTML)

Figure 4. The restored image (left) and it its square error (right) with different similarity patch sizes $d = 7, 9, 21, 41$ and the same search window size $D = 13.$ The original image Lena was polluted by a Gaussian noise with $\sigma = 20$

Download: Full-size image PowerPoint slide

Figure 1. Approximation of $H = \sqrt{a_0 \sigma^2 + b_0}$ (red line) by $H = a \sigma +b$ (black line) with $a = 0.4$, $b = 2$, $a_0 = 0.2,$ $b_0 = 10$

Download: Full-size image PowerPoint slide

Figure 2. The evolution of the PSNR as a function of the parameter $H$

Download: Full-size image PowerPoint slide

Figure 3. The evolution of the PSNR as a function of the size of similarity patches $d$

Download: Full-size image PowerPoint slide

Figure 5. The restored image (left) and it its square error (right) with different similarity patch sizes $d = 7, 9, 21, 41$ and the same search window size $D = 13.$ The original image Boat was polluted by a Gaussian noise with $\sigma = 20$

Download: Full-size image PowerPoint slide

Figure 6. The restored image (left) and it its square error (right) with different similarity patch sizes $d = 7, 9, 21, 41$ and the same search window size $D = 13.$ The original image Peppers was polluted by a Gaussian noise with $\sigma = 20$

Download: Full-size image PowerPoint slide

Figure 7. The evolution of the PSNR as a function of the size of a search window $D$

Download: Full-size image PowerPoint slide

Figure 8. The restored image (left) and it its square error (right) with the same similarity patch size $d = 21$ and different search window sizes $D = 9,13, 17, 21$. The original image Boat was polluted by a Gaussian noise with $\sigma = 20$

Download: Full-size image PowerPoint slide

Figure 9. The restored image (left) and it its square error (right) with the same similarity patch size $d = 21$ and different search window sizes $D = 9,13, 17, 21$. The original image Peppers was polluted by a Gaussian noise with $\sigma = 20$

Download: Full-size image PowerPoint slide

Figure 10. The restored image (left) and it its square error (right) with the same similarity patch size $d = 21$ and different search window sizes $D = 9,13, 17, 21$. The original image Lena was polluted by a Gaussian noise with $\sigma = 20$

Download: Full-size image PowerPoint slide

Figure 11. Denoising results with the "Lena" $512\times 512$ image

Download: Full-size image PowerPoint slide

Figure 12. Denoising results with the "Boat" $512\times 512$ image

Download: Full-size image PowerPoint slide

Figure 13. Denoising results with the "Pepper" $256\times 256$ image

Download: Full-size image PowerPoint slide

Table 1. The PSNR when the oracle estimator $u^{\ast }$ is applied with different values of $D$

Image Size	Lena $512\times512$	Barbara $512\times512$	Boats $512\times512$	House $256\times256$	Peppers $256\times256$

$\sigma /PSNR$	10/28.12db	10/28.12db	10/28.12db	10/28.11db	10/28.11db
$9 \times 9$	38.98db	37.26db	37.66db	38.93db	37.85db
$11 \times 11$	40.12db	38.49db	38.80db	40.04db	38.85db
$13 \times 13$	41.09db	39.55db	39.78db	40.98db	39.64db
$15 \times 15$	41.92db	40.45db	40.63db	41.77db	40.39db
$17 \times 17$	42.64db	41.23db	41.39db	42.40db	41.00db
$19 \times 19$	43.29db	41.93db	42.06db	43.06db	41.58db
$21 \times 21$	43.88db	42.57db	42.67db	43.61db	42.14db

$\sigma /PSNR$	20/22.11db	20/22.11db	20/22.11db	20/28.12db	20/28.12db
$9 \times 9 $	33.61db	31.91db	32.32db	33.72db	32.62db
$11 \times 11$	34.78db	33.20db	33.49db	34.92db	33.65db
$13 \times 13$	35.80db	34.28db	34.49db	35.98db	34.51db
$15 \times 15$	36.69db	35.22db	35.40db	36.80db	35.26db
$17 \times 17$	37.48db	36.05db	36.20db	37.48db	35.89db
$19 \times 19$	38.17db	36.74db	36.90db	38.07db	36.45db
$21 \times 21$	38.80db	37.40db	37.54db	38.67db	36.98db

$\sigma /PSNR$	30/18.60db	30/18.60db	30/18.60db	30/18.61db	20/28.12db
$9 \times 9$	30.65db	28.89db	29.25db	30.69db	29.51db
$11 \times 11$	31.83db	30.23db	30.45db	31.90db	30.51db
$13 \times 13$	32.85db	31.33db	31.49db	32.92db	31.34db
$15 \times 15$	33.74db	32.27db	32.37db	33.76db	32.08db
$17 \times 17$	34.50db	33.09db	33.16db	34.48db	32.74db
$19 \times 19$	35.20db	33.81db	33.85db	35.13db	33.32db
$21 \times 21$	35.79db	34.46db	34.48db	35.71db	33.85db

| Show Table

DownLoad: CSV

Table 2. Comparison between the Non-Local Means filter with the parameters in Buades et al. [5] and our parameters

Image Size	Lena $512\times512$	Barbara $512\times512$	Boats $512\times512$	House $256\times256$	Peppers $256\times256$

$\sigma/PSNR$	10/28.12db	10/28.12db	10/28.12db	10/28.11db	10/28.11db
PSNR/Buades et al. [5]	34.99db	33.82db	32.85db	35.50db	33.13db
PSNR/Ours	35.22db	33.55db	33.00db	35.35db	33.16db
$\Delta$PSNR	0.23db	-0.27db	0.15db	-0.15db	0.03db

$\sigma/PSNR$	20/22.11db	20/22.11db	20/22.11db	20/28.12db	20/28.12db
PSNR/Buades et al. [5]	31.51db	30.38db	29.32db	32.51db	29.73db
PSNR/Ours	32.41db	30.62db	30.02db	32.57db	30.30db
$\Delta$PSNR	0.82db	0.24db	0.70db	0.08db	0.57db

$\sigma/PSNR$	30/18.60db	30/18.60db	30/18.60db	30/18.61db	30/18.61db
PSNR/Buades et al. [5]	28.86db	27.65db	27.38db	29.17db	27.67db
PSNR/Ours	30.20db	28.06db	28.60db	30.49db	28.28db
$\Delta$PSNR	1.34db	0.41db	1.22db	1.32db	0.61db

| Show Table

DownLoad: CSV

Table 3. Comparison of the Non-Local Means filter with our choice of parameters and other algorithms. By $^*$ we mark the algorithms for which the results were reported by their authors

	Images Sizes	Lena $512 \times 512$	Barbara $512 \times 512$	Boat $512 \times 512$	House $256 \times 256$	Peppers $256 \times 256$

$\sigma$	Method	PSNR	PSNR	PSNR	PSNR	PSNR
20	Non-Local Means with $D=13$ and $d=21$	32.41db	30.62db	30.02db	32.57db	30.30db
	Buades et al. [5]	31.51db	30.38db	29.32db	32.51db	29.73db
	Deledalle et al. [11]$^*$	31.92db	30.41db	29.67db	32.49db	30.77db
	Katkovnik et al. [24]$^*$	30.74db	27.38db	29.03db	31.24db	29.58db
	Foi et al. [15]$^*$	31.43db	27.90db	39.61db	31.84db	30.30db
	Roth et al. [37]$^*$	31.89db	28.28db	29.86db	32.29db	30.47db
	Hirkawa et al. [17]$^*$	32.69db	31.06db	30.25db	32.58db	30.21db
	Kervrann et al. [27]	32.64db	30.37db	30.12db	32.90db	30.59db
	Jin et al. [21]	32.68db	31.04db	30.30db	32.83db	30.61db
	Hammond et al. [16]	32.81db	30.76db	30.41db	32.52db	30.40db
	Aharon et al. [1]$^*$	32.39db	30.84db	30.39db	33.10db	30.80db
	Arias-Castro et al. [2]$^*$	31.17db	29.47db	28.62db	31.91db	29.21db
	Van De Ville et Kocher [41]$^*$	31.33db	29.48db	29.82db	31.80db	29.65db
	Dabov et al. [9]	33.05db	31.78db	30.88db	33.77db	31.29db
	Lebrun et al. [28,29]	32.91db	31.51db	30.71db	33.55db	31.22db

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Aharon, M. Elad and A. Bruckstein, rmk-svd: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process., 54 (2006), 4311-4322. doi: 10.1109/TSP.2006.881199.
[2]	E. Arias-Castro, J. Salmon and R. Willett, Oracle inequalities and minimax rates for non-local means and related adaptive kernel-based methods, Siam Journal on Imaging Sciences, 5 (2012), 944-992. doi: 10.1137/110859403.
[3]	R. C. Bilcu and M. Vehvilainen, Fast nonlocal means for image denoising, In Proc. of SPIE Conf. on Digital Photography III, 6502 (2007), 65020R. doi: 10.1117/12.695079.
[4]	J. Boulanger, C. Kervrann, P. Bouthemy, P. Elbau, J. B. Sibarita and J. Salamero, Patch-based nonlocal functional for denoising fluorescence microscopy image sequences, IEEE Transactions on Medical Imaging, 29 (2010), 442-454. doi: 10.1109/TMI.2009.2033991.
[5]	A. Buades, B. Coll and J. M. Morel, A review of image denoising algorithms, with a new one, Multiscale Model. Simul., 4 (2005), 490-530. doi: 10.1137/040616024.
[6]	A. Buades, B. Coll and J. M. Morel, The staircasing effect in neighborhood filters and its solution, IEEE Trans. Image Process., 15 (2006), 1499-1505. doi: 10.1109/TIP.2006.871137.
[7]	T. Buades, Y. Lou, J. M. Morel and Z. Tang, A note on multi-image denoising, In Int. workshop on Local and Non-Local Approximation in Image Processing, pages 1–15, August 2009. doi: 10.1109/LNLA.2009.5278408.
[8]	P. Chatterjee and P. Milanfar, A generalization of non-local means via kernel regression, In Proc. of SPIE Conf. on Computational Imaging, Citeseer, 6814 (2008), 6814Op. doi: 10.1117/12.778615.
[9]	K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising by sparse 3-D transform-domain collaborative filtering, IEEE Trans. Image Process., 16 (2007), 2080-2095. doi: 10.1109/TIP.2007.901238.
[10]	K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Bm3d image denoising with shape-adaptive principal component analysis, In Proc. Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS 09), volume 49, Citeseer, 2009.
[11]	C. A. Deledalle, V. Duval and J. Salmon, Non-local methods with shape-adaptive patches (nlm-sap), Journal of Mathematical Imaging and Vision, 43 (2012), 103-120. doi: 10.1007/s10851-011-0294-y.
[12]	D. L. Donoho and J. M. Johnstone, Ideal spatial adaptation by wavelet shrinkage, Biometrika, 81 (1994), 425-455. doi: 10.1093/biomet/81.3.425.
[13]	V. Duval, J.-F. Aujol and Y. Gousseau, A bias-variance approach for the nonlocal means, SIAM Journal on Imaging Sciences, 4 (2011), 760-788. doi: 10.1137/100790902.
[14]	J. Q. Fan and I. Gijbels, Local Polynomial Modelling and Its Applications, Chapman & Hall, London, 1996.
[15]	A. Foi, V. Katkovnik, K. Egiazarian and J. Astola, A novel anisotropic local polynomial estimator based on directional multiscale optimizations, In Proc. 6th IMA Int. Conf. Math. in Signal Process, pages 79–82, Citeseer.
[16]	D. K. Hammond and E. P. Simoncelli, Image modeling and denoising with orientation-adapted gaussian scale mixtures, IEEE Trans. Image Process., 17 (2008), 2089-2101. doi: 10.1109/TIP.2008.2004796.
[17]	K. Hirakawa and T. W. Parks, Image denoising using total least squares, IEEE Trans. Image Process., 15 (2006), 2730-2742. doi: 10.1109/TIP.2006.877352.
[18]	H. Hu, B. Li and Q. Liu, Removing mixture of gaussian and impulse noise by patch-basedweighted means, Journal of Scientific Computing, 67 (2016), 103-129. doi: 10.1007/s10915-015-0073-9.
[19]	J. Immerkaer, Fast noise variance estimation, Computer vision and image understanding, 64 (1996), 300-302. doi: 10.1006/cviu.1996.0060.
[20]	Q. Jin, I. Grama, C. Kervrann and Q. Liu, Nonlocal means and optimal weights for noise removal, SIAM Journal on Imaging Sciences, 10 (2017), 1878-1920. doi: 10.1137/16M1080781.
[21]	Q. Jin, I. Grama and Q. Liu, Removing gaussian noise by optimization of weights in non-local means, preprint, arXiv: 1109.5640.
[22]	Q. Jin, I. Grama and Q. Liu, A new poisson noise filter based on weights optimization, Journal of Scientific Computing, 58 (2014), 548-573. doi: 10.1007/s10915-013-9743-7.
[23]	V. Karnati, M. Uliyar and S. Dey, Fast non-local algorithm for image denoising, In IEEE International Conference on Image Processing (ICIP), 2009 16th, pages 3873–3876, IEEE, 2009. doi: 10.1109/ICIP.2009.5414044.
[24]	V. Katkovnik, A. Foi, K. Egiazarian and J. Astola, Directional varying scale approximations for anisotropic signal processing, In Proc. XII European Signal Proc. Conf., EUSIPCO 2004, Vienna, pages 101–104, 2004.
[25]	V. Katkovnik, A. Foi, K. Egiazarian and J. Astola, From local kernel to nonlocal multiple-model image denoising, Int. J. Comput. Vis., 86 (2010), 1-32. doi: 10.1007/s11263-009-0272-7.
[26]	C. Kervrann and J. Boulanger, Optimal spatial adaptation for patch-based image denoising, IEEE Trans. Image Process., 15 (2006), 2866-2878. doi: 10.1109/TIP.2006.877529.
[27]	C. Kervrann and J. Boulanger, Local adaptivity to variable smoothness for exemplar-based image regularization and representation, Int. J. Comput. Vis., 79 (2008), 45-69. doi: 10.1007/s11263-007-0096-2.
[28]	M. Lebrun, A. Buades and J. M. Morel, Implementation of the "Non-Local Bayes" (NL-bayes) image denoising algorithm, Image Processing On Line, 2013 (2013), 1-42.
[29]	M. Lebrun, A. Buades and J. M. Morel, A nonlocal bayesian image denoising algorithm, SIAM Journal on Imaging Sciences, 6 (2013), 1665-1688. doi: 10.1137/120874989.
[30]	A. Levin and B. Nadler, Natural image denoising: Optimality and inherent bounds, In Computer Vision and Pattern Recognition, pages 2833–2840, 2011. doi: 10.1109/CVPR.2011.5995309.
[31]	B. Li, Q. Liu, J. Xu and X. Luo, A new method for removing mixed noises, Science China Information Sciences, 54 (2011), 51-59. doi: 10.1007/s11432-010-4128-0.
[32]	Y. Lou, X. Zhang, S. Osher and A. Bertozzi, Image recovery via nonlocal operators, J. Sci. Comput., 42 (2010), 185-197. doi: 10.1007/s10915-009-9320-2.
[33]	M. Mahmoudi and G. Sapiro, Fast image and video denoising via nonlocal means of similar neighborhoods, IEEE Signal. Proc. Let., 12 (2005), 839-842. doi: 10.1109/LSP.2005.859509.
[34]	A. Maleki, M. Narayan and R. Baraniuk, Suboptimality of Nonlocal Means on Images with Sharp Edges, In Annual Allerton Conference on Communication, Control, and Computing, 2011.
[35]	A. Maleki, M. Narayan and R. Baraniuk, Anisotropic nonlocal means denoising, Applied and Computational Harmonic Analysis, 35 (2013), 452-482. doi: 10.1016/j.acha.2012.11.003.
[36]	J. Polzehl and V. Spokoiny, Propagation-separation approach for local likelihood estimation, Probab. Theory Rel. Fields, 135 (2006), 335-362. doi: 10.1007/s00440-005-0464-1.
[37]	S. Roth and M. J. Black, Fields of experts, Int. J. Comput. Vision, 82 (2009), 205-229. doi: 10.1007/s11263-008-0197-6.
[38]	J. Salmon and E. Le Pennec, Nl-means and aggregation procedures, In IEEE Int. Conf. Image Process. (ICIP), pages 2977–2980. IEEE, 2009. doi: 10.1109/ICIP.2009.5414512.
[39]	N. A. Thacker, P. A. Bromiley and J. V. Manjonb, A quantitative theory of the non-local means algorithm, In Proc. MIUA 2008, Dundee, Scotland, pages 174–178. Citeseer, 2008.
[40]	C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, In Proc. Int. Conf. Computer Vision, pages 839–846, 1998. doi: 10.1109/ICCV.1998.710815.
[41]	D. Van De Ville and M. Kocher, Non-local means with dimensionality reduction and sure-based parameter selection, IEEE Trans. Image Process., 20 (2010), 2683-2690. doi: 10.1109/TIP.2011.2121083.
[42]	R. Vignesh, B. T. Oh and C. C. J. Kuo, Fast non-local means (nlm) computation with probabilistic early termination, IEEE Signal. Proc. Let., 17 (2010), 277-280. doi: 10.1109/LSP.2009.2038956.
[43]	Y. Q. Wang, The implementation of sure guided piecewise linear image denoising, Image Processing On Line, 2013 (2013), 43-67. doi: 10.5201/ipol.2013.52.
[44]	L. P. Yaroslavsky, Digital Picture Processing. An Introduction, In Springer-Verlag, Berlin, 1985. doi: 10.1007/978-3-642-81929-2.