# American Institute of Mathematical Sciences

August  2018, 12(4): 853-881. doi: 10.3934/ipi.2018036

## 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

Received  March 2017 Revised  December 2017 Published  June 2018

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.

Citation: Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems and Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036
##### References:

show all references

##### References:
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$
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$
The evolution of the PSNR as a function of the parameter $H$
The evolution of the PSNR as a function of the size of similarity patches $d$
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$
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$
The evolution of the PSNR as a function of the size of a search window $D$
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$
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$
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$
Denoising results with the "Lena" $512\times 512$ image
Denoising results with the "Boat" $512\times 512$ image
Denoising results with the "Pepper" $256\times 256$ image
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
 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
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
 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
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
 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
 [1] Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337 [2] Anugu Sumith Reddy, Amit Apte. Stability of non-linear filter for deterministic dynamics. Foundations of Data Science, 2021, 3 (3) : 647-675. doi: 10.3934/fods.2021025 [3] Stig-Olof Londen, Hana Petzeltová. Convergence of solutions of a non-local phase-field system. Discrete and Continuous Dynamical Systems - S, 2011, 4 (3) : 653-670. doi: 10.3934/dcdss.2011.4.653 [4] Valerii Maltsev, Michael Pokojovy. On a parabolic-hyperbolic filter for multicolor image noise reduction. Evolution Equations and Control Theory, 2016, 5 (2) : 251-272. doi: 10.3934/eect.2016004 [5] Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems and Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721 [6] Mojtaba F. Fathi, Ahmadreza Baghaie, Ali Bakhshinejad, Raphael H. Sacho, Roshan M. D'Souza. Time-resolved denoising using model order reduction, dynamic mode decomposition, and kalman filter and smoother. Journal of Computational Dynamics, 2020, 7 (2) : 469-487. doi: 10.3934/jcd.2020019 [7] Kazuhisa Ichikawa, Mahemauti Rouzimaimaiti, Takashi Suzuki. Reaction diffusion equation with non-local term arises as a mean field limit of the master equation. Discrete and Continuous Dynamical Systems - S, 2012, 5 (1) : 115-126. doi: 10.3934/dcdss.2012.5.115 [8] Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems and Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409 [9] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems and Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [10] Wei Wan, Weihong Guo, Jun Liu, Haiyang Huang. Non-local blind hyperspectral image super-resolution via 4d sparse tensor factorization and low-rank. Inverse Problems and Imaging, 2020, 14 (2) : 339-361. doi: 10.3934/ipi.2020015 [11] Levon Nurbekyan. One-dimensional, non-local, first-order stationary mean-field games with congestion: A Fourier approach. Discrete and Continuous Dynamical Systems - S, 2018, 11 (5) : 963-990. doi: 10.3934/dcdss.2018057 [12] Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems and Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511 [13] Olivier Bonnefon, Jérôme Coville, Guillaume Legendre. Concentration phenomenon in some non-local equation. Discrete and Continuous Dynamical Systems - B, 2017, 22 (3) : 763-781. doi: 10.3934/dcdsb.2017037 [14] Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177 [15] Alexander Bibov, Heikki Haario, Antti Solonen. Stabilized BFGS approximate Kalman filter. Inverse Problems and Imaging, 2015, 9 (4) : 1003-1024. doi: 10.3934/ipi.2015.9.1003 [16] Russell Johnson, Carmen Núñez. The Kalman-Bucy filter revisited. Discrete and Continuous Dynamical Systems, 2014, 34 (10) : 4139-4153. doi: 10.3934/dcds.2014.34.4139 [17] Jin-Won Kim, Amirhossein Taghvaei, Yongxin Chen, Prashant G. Mehta. Feedback particle filter for collective inference. Foundations of Data Science, 2021, 3 (3) : 543-561. doi: 10.3934/fods.2021018 [18] Hai Huyen Dam, Wing-Kuen Ling. Optimal design of finite precision and infinite precision non-uniform cosine modulated filter bank. Journal of Industrial and Management Optimization, 2019, 15 (1) : 97-112. doi: 10.3934/jimo.2018034 [19] Sung Ha Kang, Berta Sandberg, Andy M. Yip. A regularized k-means and multiphase scale segmentation. Inverse Problems and Imaging, 2011, 5 (2) : 407-429. doi: 10.3934/ipi.2011.5.407 [20] Marius Tucsnak. Control of plate vibrations by means of piezoelectric actuators. Discrete and Continuous Dynamical Systems, 1996, 2 (2) : 281-293. doi: 10.3934/dcds.1996.2.281

2021 Impact Factor: 1.483