Denoising images¶

Modelling¶

All models are wrong, but some are useful.

- George Box

What is an image¶

  • Mathematicians like to think of images as vector-valued functions
  • Computer scientists like to think of images as multi-dimensional arrays
  • We can even think of images as graphs

For today, we focus on grey-scale images represented as 2D arrays $F \in \mathbb{R}^{n\times n}$ or 1D arrays $\mathbf{f}\in\mathbb{R}^{n^2}$.

  • Images are typically represented as piece-wise constant on a grid of square pixels
  • This leads to issues when representing objects with sharp boundaries
circles

Types of noise¶

  • We can think of noise as any feature in the image that diminishes its scientific usefulness
  • This could include measurement noise, distortions, pre-processing artifacts, quantization, ...
  • We will focus on noise that can be modelled stochastically, as perturbation of underlying "clean" image.

Additive Gaussian noise:

$$f_i\sim N (\overline{f}_i,\sigma^2)$$

Poisson noise:

$$f\sim P(\overline{f}_i)$$

Salt-and-Pepper:

$$f_i = \begin{cases} 0 & \text{with probability } p/2 \\ 1 & \text{with probability } p/2\\ \overline{f}_i & \text{with probability } 1-p \end{cases}$$

noisy images

How do we compare images?¶

We need a way to judge the quality of an image. Which metric is suitable is highly application (and community) dependent.

We discern methods with and without a reference:

  • Without : resolution, contrast, ...
  • With : SNR, MSE, SSIM, Log-likelihood
image metrics

Getting rid of noise¶

Getting rid of noise is easy, it's keeping the useful bits that is hard.

- This lecture

Bias and variance¶

Suppose we have a noisy version, $F^\delta$, of $\overline{F}$ and a method to denoise the image: $$\widetilde{F} = \mathcal{R}(F^\delta).$$

If $\mathcal{D}$ is a metric we can decompose the error as $$\mathbb{E} \mathcal{D}\bigl(\mathcal{R}(F^\delta),\overline{F}\bigr) \leq \underbrace{\mathcal{D}\bigl(\mathcal{R}(\overline{F}),\overline{F}\bigr)}_{\text{bias}} + \underbrace{\mathbb{E} \mathcal{D}\bigl(\mathcal{R}(F^\delta),\mathcal{R}(\overline{F})\bigr)}_{\text{variance}}.$$

The ideal denoiser has both a small bias and is stable.

  • These are conflicting goals
  • The stability of classical approaches is well-understood, but they may have a large bias
  • Learned approaches (next tutorial) may have a smaller bias but can be very unstable

Filtering and smoothing¶

  • Local (Gaussian) smoothing
  • Median filtering
  • Frequency-domain filtering

Local (Gaussian) smoothing:

  • Noise fluctuates on a pixel-by-pixel basis, while the underlying image is highly correlated
  • This motivates local smoothing $$\widetilde{F}_{ij} = \sum_{k\ell} G_{|i-k|,|j-\ell|} F_{k\ell}^\delta$$
  • For example: $G_{pq} = c\cdot \exp(-(\alpha p^2 + \beta q^2) )$
Gaussian smoothing

Based on assumptions that we make on the noise, we can analyse the accuracy of such a filter.

For example, let: $$\widetilde{F}_{i,j} =(1-4\alpha)F_{i,j}^\delta + \alpha(F_{i+1,j}^\delta + F_{i-1,j}^\delta + F_{i,j+1}^\delta + F_{i,j-1}^\delta)$$

  • Assuming that $F^\delta_{ij} \sim N(\overline{F}_{ij},\sigma^2)$ we have $$\mathbb{E}\|\widetilde{F} - \overline{F}\|_2^2 \leq \left(1 - 8\alpha + 20\alpha^2\right)n^2\sigma^2 + \alpha^2 \|\nabla^2 \overline{F}\|_2^2.$$

  • Assuming that $F^\delta_{ij} \sim \text{Poisson}(\overline{F}_{ij})$ we have $$\mathbb{E}\|\widetilde{F} - \overline{F}\|_2^2 \leq \left(1 - 8\alpha + 20\alpha^2\right)\|\overline{F}\|_1 + \alpha^2 \|\nabla^2 \overline{F}\|_2^2.$$

Median filter

  • A disadvantage of the previous approach is that it also smoothes out edges in the image.
  • An alternative method is the median filter, which replaces the value in each pixel with the median of its neighborhood (in stead of the weighted mean).
Median smoothing

Fourier domain

An alternative view on the Gaussian filter is to consider it as weighting in the Fourier domain:

  • Convolution in the spatial domain is equivalent to multiplication in the Fourier domain
  • This enables to efficiently filter large images with a wide variety of filters.
Fourier filtering

Transform-domain methods¶

  • So far, we have treated image in the natural pixel-basis and the Fourier basis.
  • We have also seen both linear and non-linear filters.
  • These ideas can be extended to transform-domain filters.

Wavelet transform

  • Decompose the image per scale, in a way that combined spatial location and frequency content
  • Tresholding the image to keep only the coefficients with highest energy compresses the image (and hopefully reduces noise)
  • Can be implemented efficiently
wavelet decomposition
wavelet decomposition

Singular value decomposition

  • The wavelet decomposition uses a fixed basis to decompose the image
  • We can also make the basis dependent on the image
  • Viewing the image as matrix, we can decompose it as $$F = \sum_{i} \sigma_i u_iv_i^\top$$
SVD spectrum
SVD components
SVD denoising

Variational denoising¶

  • Explicitly model the trade-off between bias and variance, and minimize it: $$\min_{F} \mathcal{D}(F,F^\delta) + \lambda \mathcal{R}(F),$$
  • Here $\mathcal{D}$ compares images (bias) and $\mathcal{R}$ tells you how "noisy" it is (variance).
  • solving them may not be trivial (contact your local mathematician 🙂)
  • most algorithms solve iteratively, and contain algorithmic parameters that need to be chosen carefully
  • care needs to be taken when picking $\lambda$

Many of the approaches mentioned earlier can be modelled in this way:

  • Linear filters: $$\min_\mathbf{f} \|\mathbf{f} - \mathbf{f}^\delta\|_2^2 + \lambda \|L\mathbf{f}\|_2^2$$
  • Wavelet tresholding: $$\min_\mathbf{f} \|\mathbf{f} - \mathbf{f}^\delta\|_2^2 + \lambda \|W\mathbf{f}\|_1$$
  • SVD tresholding: $$\min_F \|F - F^\delta\|_\text{frobenius}^2 + \lambda \|F\|_*$$

We can adapt these formulations based on the noise model. In that case, $\lambda$ the balances noise level and regularity.

Assume that $\mathbf{f}^\delta \sim N(\mathbf{f}, \sigma^2 I)$ and $\mathbf{f} \sim N(0, (LL^T)^{-1})$. Then a (Bayesian) MAP estimate is obtained by solving $$\min_{\mathbf{f}} {\textstyle\frac{1}{2\sigma^2}} \|\mathbf{f}-\mathbf{f}^\delta\|_2^2 + {\textstyle\frac{1}{2}}\|L\mathbf{f}\|_2^2.$$

A well-known example is Total Variation denoising with

$$\mathcal{D}(\mathbf{f},\mathbf{f}^\delta) = \|\mathbf{f} - \mathbf{f} ^\delta\|_2^2, \quad \mathcal{R}(\mathbf{f}) = \|\nabla \mathbf{f}\|_1.$$

  • robust algorithms exist, but are relatively slow compared to explicit filters
  • care needs to be taken with algorithmic parameters (tolerance, number of iterations)
TV denoising

Beyond...¶

  • Patches: Apply any of the methods to local patches of the image
  • Dictionary learning: Learn a representation based on a training data set
  • Deep learning: Can be seen a generalisation that learns a representation and how to treshold it

Wrap-up¶

  • We can generally classify methods as linear and non-linear, local and global
  • Many of the methods can be formulated as an optimization problem
  • Whichever method you use, it strikes a balance between bias and variance
  • Many well-understood classical methods for denoising exist -> try those first!
  • If you have training data, a next step could be to fine-tune a classical method to it (filter choice, parameter tuning, freeform learned filter)