Bayesian Non-Local Means Filter, Image Redundancy and Adaptive Dictionaries for Noise Removal

The 2D Adaptive Non-Local Means filter can be tested online here .

 
Ch. Kervrann, J. Boulanger, P. Coupé. Bayesian non-local means filter, image redundancy and adaptive dictionaries for noise removal. In Proc. Conf. Scale-Space and Variational Meth. (SSVM' 07), pages 520-532, Ischia, Italy, June 2007.  

Abstract.  Partial Differential equations (PDE), wavelets-based methods and neighborhood filters were proposed as locally adaptive machines for noise removal. Recently, Buades, Coll and Morel proposed the Non-Local (NL-) means filter for image denoising (see Buades, A., Coll, B., Morel, J.M.: A review of image denoising algorithms, with a new one. Multiscale Modeling and Simulation. 4 (2005) 490-530). This method replaces a noisy pixel by the weighted average of other image pixels with weights reflecting the similarity between local neighborhoods of the pixel being processed and the other pixels. The NL-means filter was proposed as an intuitive neighborhood filter but theoretical connections to diffusion and non-parametric estimation approaches are also given by the authors. In this paper we propose another bridge, and show that the NL-means filter also emerges from the Bayesian approach with new arguments. Based on this observation, we show how the performance of this filter can be significantly improved by introducing adaptive local dictionaries and a new statistical distance measure to compare patches. The new Bayesian NL-means filter is better parametrized and the amount of smoothing is directly determined by the noise variance (estimated from image data) given the patch size. Experimental results are given for real images with artificial Gaussian noise added, and for images with real image-dependent noise.

 

Adaptive (block-wise) Non-Local means filter  Consider a gray-scale image $z = (z(x))_{x \in \Omega}$ defined over a bounded domain $\Omega\subset \mathbb{R}^2$, (which is usually a rectangle) and $z(x) \in \mathbb{R}_+$ is the noisy observed intensity at pixel $x \in \Omega$. The proposed Adaptive NL-means filter (ANL) is defined as

$$\begin{eqnarray*} \mbox{\it ANL}_{\sigma,n}{\bf z}(x) ~=~ \frac{\displaystyle{{... ...x) - {\bf z}(x_i)\Vert}{\sigma} - \sqrt{2n-1} \right)^2 }}}.~~~ \end{eqnarray*}$$

• $\Vert \cdot \Vert$ denotes the Euclidean distance
• ${\bf z}(x) := (z(x_k), x_k \in B(x)) \in \mathbb{R}^n$ is a vectorized image patch
• $B(x)$ is a $\sqrt{n} \times \sqrt{n}$ neighborhood centered at pixel $x$ (${n=7}$)
• $\Delta(x)$ is a square neighborhood of $N = \vert\Delta(x)\vert$ pixels ( ${N= 15 \times 15}$)
• ${\bf z}(x_i)$ is a vectorized image patch such that $x_i \in \Delta(x)$
• $\sigma^2$ is the noise variance (white Gaussian noise) assumed to be known or estimated
• $N(x) = \char93 {\cal{D}}(x)$ is the size of dictionary ${\cal{D}}(x) = \{{\bf z}(x_1), \cdots, {\bf z}(x_{N(x)})\}$ around $x$ is reliably obtained using an off-line procedure.

 
Iterative (plugin estimator) Adaptive Non-Local means filter  We are free to substitute the vector $\widetilde{{\bf u}}_{\mbox{\it\scriptsize ANL}}(x)$ of aggregated estimators (computed from the set of restored blocks $\{\mbox{\it ANL}_{\sigma,n}{\bf z}(x_i)\}$. The corresponding plugin and iterative ANL filter defined as

$$\begin{eqnarray*} \mbox{\it ANL}_{\sigma,n} \widetilde{{\bf u}}_{\mbox{\it\scri... ...}}(x_i) \right\Vert}{\sigma} - \sqrt{2n-1} \right)^2 }}}~~~ \end{eqnarray*}$$

is expected to improve the restored image. The restored image is recycled but the weights is a re-scaled function of the distance between $\widetilde{{\bf u}}_{\mbox{\it\scriptsize ANL}}(x_i)$ and the input vector ${\bf z}(x)$. The estimators are finally aggregated to produce the final restored image.

 

Experimental results

Figure 1: Comparisons of different NL-means filters. From top to bottom: part of noisy images (Barbara, Lena, $\sigma =20$), NL-means filter, vectorial NL-means filter, Adaptive NL-means filter, plugin Adaptive NL-means filter; numerical results for each filter.

noisy image ($\sigma =20$)	$\mbox{\it NL}_h z$	$\mbox{\it NL}_h {\bf z}$	$\mbox{\it ANL}_{\sigma,n} {\bf z}$	$\mbox{\it ANL}_{\sigma,n} \widetilde{{\bf u}}_{\mbox{\it\tiny ANL}}$

 
 

	Timings	Lena	Barbara
		$512 \times 512$	$512 \times 512$
$\mbox{\it NL}_h z$	58.1 sec	31.85 db	30.27 db
$\mbox{\it NL}_h {\bf z}$	96.2 sec	32.04 db	30.49 db
$\mbox{\it ANL}_{\sigma,n} {\bf z}$	75.2 sec	32.51 db	30.79 db
$\mbox{\it ANL}_{\sigma,n} \widetilde{{\bf u}}_{\mbox{\it\tiny ANL}}$	173.3 sec	32.63 db	30.88 db
Fast $\mbox{\it ANL}_{\sigma,n} {\bf z}$	10.6 sec	32.36 db	30.61 db
Fast $\mbox{\it ANL}_{\sigma,n} \widetilde{{\bf u}}_{\mbox{\it\tiny ANL}}$	21.2 sec	32.49 db	30.71 db

Figure 2: Denoising with the plugin Adaptive NL-means filter $\mbox{\it ANL}_{\sigma,n} \widetilde{{\bf u}}_{\mbox{\it \tiny ANL}}$ of the artificially corrupted Lena image (WGN, $\sigma =20$) with different estimations of the noise variance and experiments with the ``method noise'' (bottom).

$\sigma = 15$	$\sigma = 18$	$\sigma =20$	$\sigma = 22$	$\sigma = 25$
PSNR = 28.91 db	PSNR = 32.03 db	PSNR = 32.63 db	PSNR = 32.29 db	PSNR = 31.29 db

Table 1: Performance of the plugin Adaptive NL-means filter $\mbox{\it ANL}_{\sigma,n} \widetilde{{\bf u}}_{\mbox{\it \tiny ANL}}$ for different signal-to-noise ratios (WGN).

$\sigma$ / PSNR	Lena	Barbara	Boats	House	Peppers
	$512 \times 512$	$512 \times 512$	$512 \times 512$	$256 \times 256$	$256 \times 256$
5 / 34.15	37.98	36.93	36.39	38.89	37.13
10 / 28.13	35.25	33.82	33.18	35.67	33.87
15 / 24.61	33.68	32.21	31.45	34.23	32.06
20 / 22.11	32.63	30.88	30.16	33.24	30.75
25 / 20.17	31.55	29.77	29.11	32.30	29.77
50 / 14.15	27.51	24.91	25.13	27.64	23.84