key: cord-0162467-x9n0mjjo
authors: Bodduna, Kireeti; Weickert, Joachim
title: Image denoising with less artefacts: Novel non-linear filtering on fast patch reorderings
date: 2020-02-03
journal: nan
DOI: nan
sha: e80de126b3116600518381194bf1003bdee1c6b8
doc_id: 162467
cord_uid: x9n0mjjo

Leading denoising methods such as 3D block matching (BM3D) are patch-based. However, they can suffer from frequency domain artefacts and require to specify explicit noise models. We present a patch-based method that avoids these drawbacks. It combines a simple and fast patch reordering with a non-linear smoothing. The smoothing rewards both patch and pixel similarities in a multiplicative way. We perform experiments on real world images with additive white Gaussian noise (AWGN), and on electron microscopy data with a more general additive noise model. Our filter outperforms BM3D in 77% of the experiments, with improvements of up to 29% with respect to the mean squared error.

Non-local patch-based methods [1] [2] [3] [4] [5] [6] have been producing superior image denoising results since quite a few years now. These models offer two main advantages: Firstly, the assumption that similar pixels have similar neighbourhoods around them, is quite robust in a noisy scenario. Secondly, one can access similar data from distant regions in the image.

The non-local Bayes (NLB) [2, 7] and BM3D [3, 8] approaches produce state-of-the-art results. NLB uses Bayesian modelling while BM3D employs Fourier domain filtering. However, it is well known that when the assumptions about noise-free images are violated, one can see artefacts in the denoised images. The idea that we can find completely similar patches within an image in general need not be satisfied. Thus, there is a risk that data from dissimilar regions can diffuse into each other, which leads to the above mentioned artefacts. This observation is well documented for both NLB and BM3D [6] . J.W. has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 programme (grant agreement no. 741215, ERC Advanced Grant INCOVID). We thank Utz Ermel, Lasse Sprankel and Prof. Achilleas Frangakis from the Electron Microscopy Group at the University of Frankfurt for providing us with data. We also thank our colleague Tobias Alt for useful comments on a draft version of the paper.

One remedy to eliminate these artefacts is to use an additional post-processing step [6] . Another possibility which was proposed by Ram et al. [4, 5] is to employ a smooth reordering of patches for subsequent filtering. However, the underlying reason why the latter method is better than BM3D is not well understood. It appears plausible to us that it minimises information exchange between dissimilar regions with the help of patch reordering, thus reducing the artefacts and consequently leading to better results. However, this comes at a computationally very expensive reordering step, which basically requires to solve a travelling salesman problem.

Our Contribution. We introduce a new method to solve the above artifact problem without the need of an additional post-processing step and also within a relatively low computational time. In contrast to the methods of Ram et al. [4, 5] , we use a simpler and much faster patch reordering, and combine it with a more sophisticated non-linear filtering. Hence, we call our method non-linear filtering on fast patch reorderings (NFPR). In particular, we employ a filtering technique which is a novel combination of weights that reward both patch and pixel similarities. Moreover, we always use disc-shaped windows, thus leading to a rotationally invariant model. In contrast to NLB and BM3D, we avoid an explicit AWGN assumption and hence are more robust with respect to the noise type.

Paper Structure. In Section 2, we introduce our proposed NFPR framework for noise elimination along with proper motivations. In Section 3, we showcase a comparative evaluation of NFPR with NLB, BM3D and the method of Ram et al. [4] , for both real-world test images and electron microscopy data. Finally, in Section 4, we conclude with a summary of our contribution and an outlook to future work.

Our NFPR technique consists of two parts: The goal of the first step is to achieve a fast patch-based reordering of the pixels. In the second step, we employ a non-linear smoothing on the reordered pixels which yields the denoised image. In the following we describe these steps in detail. Step 1 : Fast Patch Reordering. In order to compute a smooth reordering of pixels, we employ a patch-based similarity approach: We first consider a disc-shaped search region B search of radius ρ search around every pixel u i in the 2D image domain. We then compute the L 2 norm d ij between discshaped patches of radius ρ sim , centered around u i and u j , for all j ∈ B search . This is followed by constructing a set P i of N pixels within B search which have the least distance from u i according to d ij . This set characterises the desired smooth reordering of pixels. In contrast to Ram et al. [4, 5] who solve instances of the NP-hard travelling salesman problem, we compute the reordering using just a simple sort operation. Ideally, when we average noisy versions of the same greyvalue, we should not introduce artefacts. However, we have noisy versions of approximately equal grey values in the set P i . Moreover, the above simple reordering is achieved at the cost of some disordered pixels in P i , that come from areas of dissimilar greyvalues. In the second step of the algorithm, we employ a very robust non-linear smoothing technique, to deal with both problems.

Step 2 : Non-linear Smoothing. The goal of this step is to optimally combine the set of pixels P i , obtained from the first step, and compute a final denoised image. To this end, Table 2 : MSE values of denoised images including NFPR parameters. Abbreviations as in Table 1 , REC -Ram et al. [4] .

we apply a non-linear smoothing process on this set. This can be thought of as diffusing information between pixels in a space defined by the neighbourhood similarity distances d ij instead of the generally used spatial distances. We utilise two assumptions which form the core of our structure preserving smoothing technique: Firstly, similar pixels have relatively smaller absolute tonal differences |u j − u i |. Secondly, they also have similar neighbourhoods around them. Although we have already used such an idea for patch reordering, we will be re-using the distances d ij through a multiplicative combination of both assumptions. This gives us an advantage in scenarios where one of the assumptions might be violated in the presence of noise. The discrete evolution equation for our smoothing process is given by

This equation has two terms on the right hand side, which model two types of information exchange: Remember that P i denotes the set of pixels which are closest to pixel u i according to the distance d ij . Every pixel in the image will have its own reordered set. Thus, the pixel u i could also be part of sets other than P i . The symbol P add i denotes an additional set of pixels in whose corresponding reordered sets, u i is present. The two terms mentioned in the above equation represent interactions with these two sets of pixels P i and P add i , respectively. This can also be seen as collaborative filtering similar to BM3D and NLB.

Let us now discuss the details of the above two individual terms: The functions g and h model the above mentioned tonal and neighbourhood similarity assumptions, respectively. However, if we look closely at the argument of g, we have u σj − u σi instead of u j − u i which are the real tonal differences. This idea of calculating the tonal differences on a denoised image u σ , for a robust performance, is inspired from diffusion-based methods [9] . We have chosen a collaborative version of the non-local means approach [1] for this initial noisy NLB BM3D NFPR original denoising process:

The symbols a i and b i in (1) and (2), respectively, are the normalisation constants. The functions g [10] and h in (1) are chosen as

The time step size τ in (1) is selected such that the maximumminimum principle is not violated. This means that the dynamic range of the denoised image does not exceed that of the initial noisy image. We can achieve this by choosing a i = b i /M i , where M i is the sum of number of elements in P i and P add i , and τ ≤ 1. Finally, we iterate NFPR for k max times.

We initialise the non-linear smoothing with the initial noisy image f and the patch reordering using a Gaussian smoothed version of f with standard deviation σ G .

In order to test the robustness of our method with respect to the noise type, we have performed denoising experiments on both real-world test images and electron microscopy data. For saving time, we have restricted the usage of our patch reordering step to just two iterations. This has negligible effect on the denoising output. We have fixed the following parameters: ρ search = 10, ρ sim = 10, σ G = 2.5, τ = 0.95 and the number of elements in the reordered set N = 35. In order to have a correspondence for the parameter σ between real-world and electron microscopy data, we have performed an affine rescaling of the distances d ij within the set P i , to [0, 255]. Thus, we just optimise the parameters σ, λ and k max . As already mentioned, our denoising experiments employ NLB, BM3D, Ram et al. [4] for comparison purposes with available imple-noisy NFPR FRC plot For NLB and BM3D we have optimised the unknown σ noise with respect to FRC.

mentations and detailed parameter studies in [4, 7, 8, 11] . We first present our results on the real-world images Lena, Bridge, House and Peppers 1 , which have been corrupted with AWGN. We use the mean squared error (MSE) for both measuring the quality of the denoised images and optimising the parameters. Figure 1 and Table 1 show the comparison with NLB and BM3D. Visual advantages in terms of less artefacts and more pleasant edges are larger than MSE advantages would suggest. From Table 2 , we can conclude that our method is competetive with the approach of Ram et al. [4] .

Experiments on a GPU 2 show that our method takes just 2 and 6.5 seconds for denoising the 256 × 256 sized House and 512 × 512 sized Lena images (σ noise = 100), respectively. This implementation could further be improved with precomputing the weighting functions and also through faster implementations of patch-similarity computations. The available non-parallel CPU 3 implementation of [4] takes 1128 and 7021 seconds in the above scenarios. This is very expensive, even if we take into account the technical differences in the implementations.

We have also considered ribosomal data in yeast cells acquired using an electron microscope. For measuring the quality of the denoised images, we use a popular frequency domain measure in electron microscopy called Fourier ring correlation (FRC). It computes a cross-correlation coefficient between the denoised versions of two different images of the same scene at different frequency levels [12, 13] . Figure 2 shows the corresponding results. We observe higher correlation coefficients for NFPR in the FRC curves. This indicates that it does a better job in preserving image structures during the denoising process.

All the above results can be attributed to the previously mentioned modelling advantages of NFPR. In contrast to NLB and BM3D, it also benefits by avoiding an explicit 1 http://sipi.usc.edu/database/ 2 NVIDIA GeForce GTX 970 graphics card using C++ and CUDA 3 Intel(R) Core(TM) i7-6700 CPU 3.4 GHz machine using MATLAB/C AWGN noise approach. This leads to even better NFPR results for electron microscopy data, as such kind of data is generally approximated with a more general additive noise model (see Chapter 11 of [14] ). On the other hand, there are certainly some cases when NLB, BM3D and Ram et al. [4] are better than NFPR for real-world images like Lena and Bridge which have some amount of texture.

We observe that an important message from the above results is in accordance with the conclusion in our multi-frame denoising research [11] : The process of choosing the combination of pixels that undergo non-linear smoothing is as important as choosing the type of non-linearity itself. In BM3D and NLB, we filter a group of similar patches altogether. In NFPR, we utilise a carefully chosen set of pixels and subsequently filter them using a robust procedure. This is superior although we do not use any explicit spatial context in the filtering process. Unlike NLB and BM3D, we apply it only for patch reordering. In [11] , we observed that a linear temporal filter can outperform a non-linear one, but only if the pixels that undergo the denoising process are chosen carefully.

Although most people would agree that artifact avoidance is desirable in denoising, this goal has hardly been addressed in practice. It appears that smooth patch reordering is helpful in that aspect, but its computational workload is usually very high. The message of our paper is that this patch reordering can be fairly simplistic and therefore fast, provided that one comes up with more sophisticated non-linear filters that reward pixel and patch similarities in a multiplicative manner. Moreover, refraining from explicit noise models can be beneficial in real-world applications that may deviate from ideal noise assumptions. We believe that these are fairly general design principles that deserve further exploration in the future. This is also part of our ongoing work.

A non-local algorithm for image denoising

A nonlocal Bayesian image denoising algorithm

Image denoising by sparse 3D transform-domain collaborative filtering

Image processing using smooth ordering of its patches

Image denoising using NL-means via smooth patch ordering

DA3D: Fast and data adaptive dual domain denoising

Implementation of the Non-Local Bayes (NL-Bayes) image denoising algorithm

An analysis and implementation of the BM3D image denoising method

Image selective smoothing and edge detection by nonlinear diffusion

Anisotropic Diffusion in Image Processing

Removing Multi-frame Gaussian Noise by Combining Patch-based Filters with Optical Flow

The correlation averaging of a regularly arranged bacterial cell envelope protein

Resolution measures in molecular electron microscopy

Electron Tomography: Methods for Threedimensional Visualisation for Structures in the Cell