Article Contents
Article Contents

# Convergence theorems for the Non-Local Means filter

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

Mathematics Subject Classification: 62H35.

 Citation:

• 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$

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$

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

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

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$

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$

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

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$

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$

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$

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

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

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

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

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

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

Figures(13)

Tables(3)

• on this site

/