Contact :
The presented 3D Optimized Non Local Means filter can be tested online here .
One critical issue in the context of image restoration is the problem of noise removal while keeping the integrity of relevant image information. Denoising is a crucial step to increase image conspicuity and to improve the performances of all the processings needed for quan- titative imaging analysis. The method proposed in this paper is based on an optimized version of the Non Local (NL) Means algorithm. This approach uses the natural redundancy of information in image to remove the noise.
First introduced by Buades et al. in [1], the Non Local (NL) means algorithm is based on the natural redundancy of information in images to remove noise. In this filter, the restored intensity of the voxel i, NL(v)(i), is a weighted average of all voxel intensities of voxel j in a "search volume" Vi. The weight of the voxel j quantifies the similarity of local neighborhoods Ni and Nj (see Schema)
The main disadvantage of the NL-means algorithm is the computational burden due to its complexity, especially on 3D data. For a classical MR image the computational time reaches up to 6 hours.
Voxel selection in the search volume. One recent study [2] investigated the problem of the computational burden with a neighborhoods classi cation. The aim is to reduce the number of voxels taken into account in the weighted average. In other words, the main idea is to select only the voxels j in V (i) that will have the highest weights w(i; j) in (1) without having to compute the Euclidean distance between Ni and Nj . In [2], Mahmoudi et al. propose a method to preselect a set of the most pertinent voxels j in V (i). This selection is based on the similarity of the mean and the gradient of v(Ni) and v(Nj ): intuitively, similar neighborhoods tend to have close means and close gradients. In our implementation, the preselection of the voxels in Vi that are expected to have the nearest neighborhoods to i is based on the first and second order moments of v(Ni) and v(Nj ). The gradient being sensitive to noise level, the standard deviation is preferable in case of high level of noise. In this way, the maps of local means and local standard deviations are precomputed in order to avoid repetitive calculations of moments for one same neighborhood. Neglecting a priori the voxels which are expected to have small weights, the algorithm can be speeded up, and the results are even improved.
Parallelized computation. Another way to deal with the problem of the com- putational time required is to share the operations on several processors via a cluster or a grid. In fact, the intrinsic nature of the NL-means algorithm allows to use multithreading, and thus to parallelize the operations. We divide the vol- ume into sub-volumes, each of them being treated separately by one processor. A server with eight Xeon processors at 3 GHz was used in our experiments.
In order to evaluate the performances of the NL-means algorithm on 3D T1 MR images, tests are performed on the Brainweb database composed of 181x217x181 images. The evaluation framework is based on comparisons with other denoising methods: Anisotropic Diffusion Filter (implemented in VTK) and the Rudin-Osher-Fatemi Total Variation (TV) approach. Several criteria are used to quantify the performances of each method: the Peak Signal to Noise Ratio (PSNR) obtained for di erent noise levels, histogram comparisons between the denoised images and the "ground truth", and nally the visual assessment. In the following, the noise is a white Gaussian noise, and the percent level is based on a reference tissue intensity, that is in this case the white matter. For the sake of clarity, the PSNR and the histograms are estimated by removing the background.
PSNR values for the three compared methods for di erent levels of noise.
The PSNR between the noisy images and the ground truth is called \No processing"
and is used as the reference for PSNR before denoising. For each level of noise, the
optimized NL-means algorithm outperforms the Anisotropic Di usion method, the
Total Variation method, and the classical NL-means. |
As we can see on this figure, our optimized NL- means algorithm produces the best values of PSNR whatever the noise level. In average, a gain of 2,6dB is observed compared to the best method among TV and Anisotropic Diffusion, and a gain of 1,2dB compared to the classical NL-means. The PSNR between the noisy images and the ground truth is called "No processing" and is used as the reference for PSNR before denoising
Histograms of the restored images and of the ground truth for 9% of noise. The histogram of
the NL-means restored image clearly better ts to the ground truth one. |
To better understand how these di erences in the PSNR between the three compared methods can be explained, we compared the histograms of the denoised images with the ground truth. The figure shows that the NL-means is the only method able to retrieve a similar histogram as the ground truth. The NL-means restoration distinguishes clearly the three main peaks representing the white matter, the gray matter and the cerebrospinal uid. The sharpness of the peaks shows how the NL-means increases the contrasts between denoised biological structures
Top: details of the Brainweb denoised images obtained via the three compared
methods for a noise level of 9%. Bottom: images of the removed noise, i.e. the di er-
ence between noisy images and denoised images, centered on 128. From left to right:
Anisotropic Diffusion, Total Variation and NL-means. |
Results
obtained for standard and optimized NL-means implementations on a
Brainweb T1 image of size 181x217x181 with 9% of noise. The time shown
for the standard NL-means is calculated on only one processor at 8 GHz.
The time given for our optimized and multithreaded version corresponds
to the time
with a server of eight 3Ghz CPUs, and the cumulative CPU time is shown
between brackets. |
To show the effciency of the NL-means algorithm on real data, tests have been performed on a high field MR system (3T). The restoration results, presented in Fig. 5, show good preservation of the basal ganglia. Fully automatic segmentation and quantitative analysis of such structures are still a challenge, and improved restoration-schemes could greatly improve these processings.
From left to right: Original image, denoised image, and difference
image centered on 128. The whole image is shown on top, and a detail is exposed on
bottom. |
We propose an optimized version of the Non Local (NL) means al- gorithm. The validations performed on Brainweb dataset bring to the fore how the NL-means denoising outperforms well estab- lished other methods, such as Anisotropic Diffusion and Total Variation. If the performances of this approach clearly appears, the reduction of its intrinsic complexity is still a challenging problem. Our proposed optimized implemen- tation, with voxel preselection and multithreading, considerably decreases the required computational time. The impact of this NL-means denoising on the performances of post-processing algorithms, like segmentation and registration schemes need also to be further investigated.
[1] A. Buades, B. Coll, and J. M. Morel. A review of image denoising algorithms, with a new one. Multiscale Modeling & Simulation, 4(2):490-530, 2005.
[2] M. Mahmoudi and G. Sapiro. Fast image and video denoising via non-local means of similar neighborhoods . IMA Preprint Series, 2052, 2005
|
| VisAGeS
| Map
| Team
| Publications
| Demonstrations
|
Irisa - Inria - Copyright 2004 © VisAGeS Team |