Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

7. Denoising

CNRS & DMA, École Normale Supérieure

Chapter PDF · Complete book

Denoising estimates a clean signal from measurements corrupted by noise. Its central difficulty is to suppress random fluctuations without erasing edges, textures, or other features of the underlying signal. We model common acquisition noise, compare linear filters with nonlinear thresholding, analyze how regularity and sparsity govern reconstruction error, and adapt the methods to Poisson and multiplicative noise.

7.1 Noise Modeling

7.1.1 Noise in Images

Figure 7.1 illustrates the variety of imaging noise. Different acquisition devices produce different noise statistics, while the images themselves vary in smoothness and geometry.

Figure 7.1. Gaussian, Poisson, and multiplicative Gamma noise simulated on the same flower image.

The model should reflect both the acquisition process and the noise statistics. The regularity and geometry of the clean signal then guide the choice of a basis for its representation.

Since noise perturbs discrete measurements from acquisition devices, we consider only finite-dimensional real signals fRNf\in\mathbb{R}^N.

7.1.2 Image Formation

Figure 7.2 summarizes the model: a clean image f0f_0 combines with noise ww to produce the observation Y:=f0wY := f_0 \oplus w. The operation \oplus may be addition or multiplication. The observed image YY is modeled as a random vector.

Figure 7.2. Image acquisition, noise, and reconstruction by denoising.

In the statistical model, ww is a random vector with a specified distribution. A numerical experiment uses one realization, also written ww.

Additive Noise.

The simplest image formation model adds noise to a clean signal f0f_0

Y:=f0+wY := f_0 + w

where ww is the noise residual. Both ww and YY are random; an acquired image is one realization of YY, denoted by yy or ff below. Figures 7.3 and 7.4 illustrate additive noise on a signal and an image.

Figure 7.3. One-dimensional additive Gaussian noise at low, medium, and high levels, with a common clean signal and normalized noise realization.

Figure 7.4. Two-dimensional additive noise: the clean image f0f_0 and the observation f=f0+wf=f_0+w, with wN(0,σ2I)w\sim\mathcal N(0,\sigma^2 I).

The simplest model assumes independent centered Gaussian entries wnw_n with variance σ2\sigma^2: wN(0,σ2IdN)w\sim\mathcal{N}(0,\sigma^2\mathrm{Id}_N). This is Gaussian white noise.

Depending on the image acquisition device, other noise distributions may be appropriate, including uniform noise wn[a,a]w_n \in [-a,a] or heavy-tailed generalized Gaussian noise with density

pw(u)eu/sα,s>0,0<α<2.p_w(u)\propto e^{-|u/s|^\alpha},\qquad s>0,\quad0<\alpha<2.

In many situations, the noise is not additive; its intensity may, for instance, depend on the signal intensity. This is the case with the Poisson and multiplicative noise models considered in Section 7.4.

7.1.3 Denoiser

A denoiser produces an estimate f~=D(Y)\tilde f = \mathcal{D}(Y) of f0f_0 from the observation YY alone. The map D\mathcal{D} is deterministic, but its output is random because it depends on the noise ww. With centered additive noise, YY has mean f0f_0, so denoising estimates that mean from a single realization. Figure 7.5 illustrates the result.

The quality of a denoiser is measured using the mean squared risk Ew ⁣f0f~ ⁣2\mathbb E_w|\!| f_0-\tilde f |\!|^2, where Ew\mathbb E_w averages over the noise ww. This risk is a theoretical quantity because f0f_0 is unknown in practice. In experiments with known clean data, we instead evaluate one realization yY=f0+wy \sim Y = f_0 + w using the signal-to-noise ratio SNR(D(y),f0)\text{SNR}(\mathcal{D}(y),f_0), defined by

SNR(f,g):=20log10( ⁣fg ⁣/ ⁣g ⁣).\text{SNR}(f,g) := -20\log_{10}( |\!| f-g |\!|/|\!| g |\!| ).

The SNR is measured in decibels (dB). Computing it requires the clean signal f0f_0, so it serves as a benchmark in controlled experiments. Because an 2\ell^2 error does not fully describe perceptual quality, visual inspection should accompany the numerical comparison.

Figure 7.5. Left: clean image, center: noisy image, right: denoised image.

7.2 Linear Denoising by Filtering

7.2.1 Translation Invariant Estimators

A linear estimator D(Y)=f~\mathcal{D}(Y) = \tilde f of f0f_0 preserves addition, D(f+g)=D(f)+D(g)\mathcal{D}(f+g) = \mathcal{D}(f)+\mathcal{D}(g), and scalar multiplication. A translation-invariant estimator commutes with translations: D(fτ)=D(f)τ\mathcal{D}(f_\tau) = \mathcal{D}(f)_\tau, where fτ(t)=f(tτ)f_\tau(t) = f(t-\tau). We assume periodic boundary conditions, in either one or two dimensions.

An estimator with both properties is a convolution filter:

D(f)=fh\mathcal{D}(f) = f \star h

where hRNh\in\mathbb{R}^N is a filter. Denoising filters are usually low-pass. To preserve constant signals, one imposes

nhn=h^0=1\sum_n h_n = \hat h_0 = 1

where h^\hat h is the discrete Fourier transform.

Figure 7.6 illustrates denoising with a low-pass filter.

Figure 7.6. Gaussian filtering: noisy signal, kernel, and filtered signal (top), with their Fourier magnitudes below.

The filtering strength is usually controlled by the width ss of hh. A typical example is the (discretized) Gaussian filter

N/2<iN/2,hs,i=1Zsexp(i22s2)(7.1)\forall \,-N/2 < i \leqslant N/2, \quad h_{s,i} = \frac{1}{Z_s} \exp\left( -\frac{ i^2 }{ 2s^2} \right) \tag{7.1}

where ZsZ_s normalizes the filter so that ihs,i=1\sum_i h_{s,i}=1, preserving constant signals. Figure 7.6 shows the effect of Gaussian filtering in the spatial and Fourier domains.

Figure 7.7 shows the effect of increasing the filter width ss. Linear filtering works well on smooth signals, but removing more noise also blurs edges and other singularities.

Figure 7.7. Gaussian filtering with increasing width: three signals (top) and five images (bottom).

7.2.2 Optimal Filter Selection and Bias-Variance Tradeoff

The best filter depends on both the unknown signal f0f_0 and the noise level σ\sigma. Rather than optimize over all filters, we can tune a width parameter ss within a family such as the Gaussian filters in (7.1).

The triangle inequality separates the smoothing error from the remaining noise:

 ⁣f~f0 ⁣ ⁣hsf0f0 ⁣+ ⁣hsw ⁣|\!| \tilde f - f_0 |\!| \leqslant|\!| h_s \star f_0 - f_0 |\!| + |\!| h_s \star w |\!|

The filter width ss balances noise removal against excessive smoothing of singularities. A wider filter typically reduces  ⁣hsw ⁣|\!| h_s \star w |\!| while increasing  ⁣hsf0f0 ⁣|\!| h_s\star f_0-f_0 |\!|.

Figure 7.8 shows the SNR as a function of filter width, evaluated using the known clean signal.

Figure 7.8. SNR as a function of filter width for a signal (left) and an image (right).

Figure 7.9 uses the width ss^\star that maximizes SNR for the displayed observation. This choice uses the known clean signal to assess the best achievable result within the filter family.

Figure 7.9. Gaussian filtering at the SNR-optimal widths. From left to right: noisy signal, filtered signal, noisy image, and filtered image.

Some noise remains at the SNR-optimal width. Increasing the filter width introduces strong blur and reduces the SNR, although the result may look more pleasant.

7.2.3 Oracle Denoiser

To study the best possible choice of hh, first suppose that an oracle knows the clean signal f0f_0.

Recall the model Y=f0+wY = f_0 + w, where ww is Gaussian white noise: wkN(0,σ2)w_k \sim \mathcal{N}(0, \sigma^2) and the wkw_k are independent and identically distributed. The clean signal f0f_0 is fixed. Choose an orthonormal basis (ψk)k(\psi_k)_k, typically the Fourier basis, and restrict attention to linear estimators that are diagonal in it:

f~kλkY,ψkψk.(7.2)\tilde{f} \coloneqq \sum_k \lambda_k \langle Y,\,\psi_k\rangle \, \psi_k. \tag{7.2}

For the Fourier basis, this means f~=Yh\tilde{f} = Y \star h where h^=λ\hat h=\lambda. Note that f~\tilde{f} is a random vector.

The oracle may use f0f_0 to select the gains λ\lambda, but the estimator must still be linear in YY and have the displayed diagonal form. It cannot simply return f0f_0.

Denoting ckf0,ψkc_k \coloneqq \langle f_0,\,\psi_k\rangle (for the normalized discrete Fourier basis, c=f^0/Nc=\hat f_0/\sqrt N), the expected risk of this denoiser is

Ewf~f02=kEwf~f0,ψk2=kEwλk(ck+w,ψk)ck2.\mathbb{E}_w \|\tilde{f} - f_0\|^2 = \sum_k \mathbb{E}_w \left| \langle \tilde{f} - f_0,\,\psi_k\rangle \right|^2 = \sum_k \mathbb{E}_w \left| \lambda_k \left( c_k + \langle w,\,\psi_k\rangle \right) - c_k \right|^2 .

For a real orthonormal basis, the transformed noise is again independent Gaussian noise with variance σ2\sigma^2. For a complex unitary Fourier basis applied to real noise, each coefficient still has second moment σ2\sigma^2, which suffices here, although conjugate-frequency coefficients are dependent. By expanding the square and using E(w,ψk)=0\mathbb{E}(\langle w,\,\psi_k\rangle) = 0, we obtain

Ewf~f02=k(ck2λk12+λk2σ2).\mathbb{E}_w \|\tilde{f} - f_0\|^2 = \sum_k\left(|c_k|^2|\lambda_k-1|^2+|\lambda_k|^2\sigma^2\right) .

Knowing ckc_k, the oracle minimizes Ew(f~f02)\mathbb{E}_w \left( \|\tilde{f} - f_0\|^2 \right) over λ\lambda. The minimization separates over the indices kk:

minλk(ck2λk12+λk2σ2).\min_{\lambda_k} \left( |c_k|^2 |\lambda_k - 1|^2 + |\lambda_k|^2 \sigma^2 \right).

The solution thus satisfies

ck2(λk1)+λkσ2=0,|c_k|^2 (\lambda_k - 1) + \lambda_k \sigma^2 = 0,

i.e.,

λk=ck2ck2+σ2.\lambda_k = \frac{|c_k|^2}{|c_k|^2+\sigma^2}.

If σ=0\sigma = 0, choosing λ=1\lambda = 1 gives the identity map. When ck|c_k| decays, increasing σ\sigma suppresses the weaker coefficients more strongly, concentrating the gains on the dominant signal components.

7.2.4 Wiener Filter

We now replace access to the clean signal by a known probability model for it.

Suppose both the noise wWw \sim W and the clean signal f0Ff_0 \sim F have known distributions. We seek a filter minimizing the error averaged over both sources of randomness, assuming WW and FF are independent.

We assume D\mathcal{D} has the form (7.2).

The optimal hh thus minimizes

Ew,FD(F+w)F2\mathbb{E}_{w,F} \|\mathcal{D}(F+w) - F\|^2

Independence of WW and FF allows the same risk calculation:

Ew,FD(F+w)F2=k(αkλk12+λk2σ2)whereαk:=EFF,ψk2\mathbb{E}_{w,F} \|\mathcal{D}(F+w)-F\|^2=\sum_k\left(\alpha_k|\lambda_k-1|^2+|\lambda_k|^2\sigma^2\right) \quad\text{where}\quad \alpha_k := \mathbb{E}_{F} |\langle F,\,\psi_k\rangle|^2

The optimal filter thus has coefficients

λk=αkαk+σ2.(7.3)\lambda_k=\frac{\alpha_k}{\alpha_k+\sigma^2}. \tag{7.3}

Relative to the oracle filter, the individual energy ck2|c_k|^2 is replaced by the expected coefficient energy αk0\alpha_k\geqslant 0, the signal power spectrum in the Fourier basis.

This filter is known as the Wiener filter.

For the normalized discrete Fourier basis, αk=N1EF^k2\alpha_k=N^{-1}\mathbb E|\hat F_k|^2. Define the averaged autocorrelation

ηj=1NEn=0N1FnFnj,αk=η^k.\eta_j=\frac1N\mathbb E\sum_{n=0}^{N-1}F_n\overline{F_{n-j}}, \qquad\alpha_k=\hat\eta_k.

Here indices are periodic and η^\hat\eta uses the unnormalized DFT of Chapter 2. This normalization is needed because the Fourier atoms used in the risk calculation have unit norm.

So far, D\mathcal{D} has been restricted to the basis ψm\psi_m through the diagonal form (7.2). If FF is stationary, its law is unchanged by shifts: F(τ)F(\cdot-\tau) has the same law as FF. In that case, the Fourier Wiener filter (7.3) is optimal among all linear denoisers, even without imposing a diagonal form in advance.

An empirical estimate based on one noisy realization is N1y^k2N^{-1}|\hat y_k|^2. Its expectation is αk+σ2\alpha_k+\sigma^2, and its variance can be large. Empirical Wiener methods therefore need noise subtraction, nonnegativity constraints, and usually additional smoothing or a signal model.

7.2.5 Denoising and Linear Approximation

Approximation theory, developed in Chapter 5, provides a different route to denoising bounds. It requires a class of clean signals rather than a probability distribution on that class.

Fix an orthonormal basis B=(ψm)m\mathcal{B}= (\psi_m)_m of RN\mathbb{R}^N. A simple estimator retains only the first MM coefficients of the noisy observation in B\mathcal{B}:

D(f)=f~:=m=1Mf,ψmψm.(7.4)\mathcal{D}(f) = \tilde f \mathrel{:=}\sum_{m=1}^M \langle f,\,\psi_m\rangle \psi_m. \tag{7.4}

This is a linear projection onto the space spanned by (ψm)m=1M(\psi_m)_{m=1}^M.

This denoising scheme is parameterized by the number 1MN1\leqslant M\leqslant N of retained coefficients. Increasing MM retains more signal detail but also more noise.

For the discrete Fourier basis ordered by increasing frequency, this is ideal low-pass filtering by convolution with a discrete Dirichlet kernel.

This is the special case of (7.2) in which the gains λm\lambda_m are binary, λm{0,1}\lambda_m \in \{0,1\}. Although restrictive, this choice yields useful rates under the approximation assumptions of Theorem 7.1. It requires a regularity model for f0f_0, but does not assume a random signal distribution FF.

The proof is finite-dimensional, but its bound has no explicit dependence on NN. Extending it to a continuum model requires interpreting white noise as a generalized random process.

Several observations help interpret this result:

The Sobolev model in Section 5.2.1 provides a useful example. For discrete signals with an increasing sample count NN, especially as σ\sigma decreases, a compatible weighted coefficient bound gives the same approximation argument as Proposition 5.3.

For normalized Fourier atoms ordered by increasing physical frequency, an appropriately scaled discrete weighted-energy bound approximates the periodic Sobolev model. The sample normalization, frequency weights, and boundary convention must match those of the continuous signal. Under this compatibility, low-frequency projection efficiently denoises smooth signals and images.

7.3 Nonlinear Denoising by Thresholding

7.3.1 Hard Thresholding

We consider a real orthonormal basis {ψm}m\{\psi_m\}_m of RN\mathbb{R}^N, for instance a discrete wavelet basis.

The noisy coefficients satisfy

f,ψm=f0,ψm+w,ψm.(7.7)\langle f,\,\psi_m\rangle = \langle f_0,\,\psi_m\rangle + \langle w,\,\psi_m\rangle. \tag{7.7}

Orthogonal transforms preserve Gaussian white noise, so the coefficients w,ψm\langle w,\,\psi_m\rangle remain independent centered Gaussians with variance σ2\sigma^2. If the basis {ψm}m\{\psi_m\}_m represents f0f_0 sparsely, most clean coefficients f0,ψm\langle f_0,\,\psi_m\rangle are small, leaving many noisy coefficients dominated by noise; see Figure 7.10. Donoho and Johnstone systematically developed thresholding estimators based on this observation [17].

Figure 7.10. Denoising using thresholding of wavelet coefficients.

Hard thresholding retains only coefficients whose magnitude exceeds the threshold TT:

f~=f,ψm>Tf,ψmψm=mST(f,ψm)ψm.\tilde f = \sum_{ |\langle f,\,\psi_m\rangle|>T } \langle f,\,\psi_m\rangle \psi_m = \sum_{ m } S_T(\langle f,\,\psi_m\rangle) \psi_m.

where STS_T is defined in (5.4). Retaining the MM largest noisy coefficients gives the approximation f~=fM\tilde f = f_M of ff. Figure 7.10 illustrates how a suitable TT removes much of the noise while preserving sharp features.

7.3.2 Soft Thresholding

We recall that the hard thresholding operator is defined as

ST(x)=ST0(x)={xifx>T,0ifxT.(7.8)S_T(x) = S_T^0(x) = \left\{ \begin{array}{l} x \quad \text{if} \quad |x|>T, \\ 0 \quad \text{if} \quad |x|\leqslant T. \end{array} \right. \tag{7.8}

Hard thresholding makes a discontinuous keep-or-discard decision, which can create artifacts. Soft thresholding is a continuous alternative:

ST1(x)=max(1T/x,0)x.(7.9)S_T^1( x ) = \max( 1-T/|x|, 0 ) x. \tag{7.9}

Set ST1(0)=0S_T^1(0)=0 by continuity. Figure 7.11 compares the two nonlinear maps.

Figure 7.11. Hard and soft thresholding functions.

For q=0q=0 and q=1q=1, these thresholding rules define two different estimators

f~q=mSTq(f,ψm)ψm(7.10)\tilde f^q = \sum_m S_T^q( \langle f,\,\psi_m\rangle ) \psi_m \tag{7.10}

Figure 7.12. SNR as a function of T/σT/\sigma for hard and soft thresholding.

Preserving coarse-scale coefficients.

Soft thresholding ST1S_T^1 biases retained coefficients by reducing their magnitudes. Shrinking coarse wavelet coefficients can introduce unwanted low-frequency artifacts. At a coarsest scale 2j02^{j_0}, it is therefore common to retain the approximation coefficients unchanged. In one dimension, this gives

f~1=0n<2j0f,φj0,nφj0,n+j=J+1j00n<2jST1(f,ψj,n)ψj,n.\tilde f^1 = \sum_{0 \leqslant n < 2^{-j_0}} \langle f,\,\varphi_{j_0,n}\rangle \varphi_{j_0,n} + \sum_{j=J+1}^{j_0}\sum_{0\leqslant n<2^{-j}}S_T^1(\langle f,\,\psi_{j,n}\rangle)\psi_{j,n}.

Empirical choice of the threshold.

Figure 7.12 plots SNR against the threshold TT for a fixed natural image f0f_0. In this experiment, hard thresholding performs best near T3σT \approx 3\sigma, and soft thresholding near T3σ/2T\approx 3\sigma/2. The best soft-thresholded estimate has a slightly higher SNR.

Figure 7.13. Comparison of hard (left) and soft (right) thresholding.

These values describe the displayed experiments; the best threshold depends on the image, basis, noise level, and loss function.

7.3.3 Minimax Optimality of Thresholding

Estimating sparse coefficients.

To analyze the estimator and guide the choice of TT, we first assume that the coefficients

a0,m=f0,ψmR,a0RNa_{0,m}=\langle f_0,\,\psi_m\rangle\in\mathbb{R},\qquad a_0\in\mathbb{R}^N

are sparse: most entries a0,ma_{0,m} vanish, so the 0\ell^0 count

 ⁣a0 ⁣0=#{m  ;  a0,m0}|\!| a_0 |\!|_0 = \# \left\{ m \;;\; a_{0,m} \neq 0 \right\}

is small. As shown in (7.7), noisy coefficients

f,ψm=am=a0,m+zm\langle f,\,\psi_m\rangle = a_m = a_{0,m} + z_m

are perturbed by additive Gaussian white noise of variance σ2\sigma^2. Figure 7.14 shows an example of such a noisy sparse signal.

Figure 7.14. Left: clean sparse coefficients a0a_0; right: noisy coefficients aa.

Universal threshold value.

When all nonzero clean coefficients are well separated from the noise level, choosing a threshold comparable to the largest pure-noise coefficient suppresses false detections:

TτN,τN=max0m<Nzm.T\approx\tau_N,\qquad\tau_N=\max_{0\leqslant m<N}|z_m|.

This motivates a deterministic threshold based on the typical size of τN\tau_N; it is not an exact minimization formula for the realized denoising error. The random maximum τN\tau_N depends on NN. For fixed σ\sigma, its mean is asymptotic to σ2logN\sigma\sqrt{2\log N} as NN\to\infty. Its variance tends to zero with NN, so τN\tau_N concentrates increasingly near its mean. Figure 7.15 illustrates these trends numerically.

Figure 7.15. Empirical mean (top) and standard deviation (bottom) of the largest absolute Gaussian noise coefficient.

Asymptotic optimality.

Donoho and Johnstone [17] showed that the universal threshold T=σ2log(N)T = \sigma\sqrt{2 \log(N)} gives a risk bound for signals that admit accurate nonlinear approximations in {ψm}m\{\psi_m\}_m. The risk is within a logarithmic factor of an ideal coefficient-selection risk.

The oracle inequality is a standard Gaussian thresholding bound; see [17]. The rate follows by balancing CM2βCM^{-2\beta} and Mσ2M\sigma^2, with integer rounding and truncation at NN as in Theorem 7.1. The added σ2\sigma^2 term accounts for residual noise even at the zero signal.

The universal threshold T=σ2lnNT=\sigma\sqrt{2\ln N} is conservative: it suppresses nearly all pure-noise coefficients. The smaller thresholds illustrated in Figure 7.13 often give better SNR in these experiments.

7.3.4 Translation Invariant Thresholding Estimators

Translation invariance.

Let ff~=D(f)f\mapsto\tilde f=\mathcal{D}(f) be a denoising method, and fτ(x)=f(xτ)f_\tau(x) = f(x-\tau) be a translated signal or image for τRd\tau \in \mathbb{R}^d (d=1d=1 or d=2d=2). The denoiser is translation invariant on the shift lattice Δ\Delta if

τΔ,D(f)=D(fτ)τ\forall \,\tau \in \Delta, \quad \mathcal{D}(f) = \mathcal{D}(f_\tau)_{-\tau}

where Δ\Delta is a lattice of Rd\mathbb{R}^d. A denser shift lattice imposes equivariance at finer spatial resolution. This corresponds to the fact that D\mathcal{D} commutes with the translation operator.

Illustration. Unnumbered illustration: cycle spin principle

Translation invariance on a sufficiently fine set Δ\Delta prevents the denoiser from favoring particular feature locations. Without it, the same feature may be reconstructed differently depending on where it appears, producing visible artifacts.

For denoising by thresholding

D(f)=mST(f,ψm)ψm.\mathcal{D}(f) = \sum_m S_T( \langle f,\,\psi_m\rangle ) \psi_m.

a sufficient condition is invariance of the basis {ψm}m\{\psi_m\}_m under shifts in Δ\Delta, up to unit-modulus factors:

m, τΔ, m,λC,(ψm)τ=λψm\forall \,m',\ \forall \,\tau\in\Delta,\ \exists m, \: \exists \lambda\in \mathbb{C}, \quad \quad (\psi_{m'})_\tau = \lambda\psi_m

where λ=1|\lambda|=1.

On the periodic domain, the Fourier basis is invariant under every shift Δ=Rd\Delta=\mathbb{R}^d of [0,1]d[0,1]^d. The discrete Fourier basis is invariant under all integer shifts Δ={0,,N01}d\Delta=\{0,\ldots,N_0-1\}^d, where N=N0N=N_0 counts samples in one dimension and N=N0×N0N=N_0 \times N_0 counts pixels in two dimensions.

Unfortunately, an orthogonal wavelet basis

{ψm=ψj,n}j,n\{\psi_m = \psi_{j,n} \}_{j,n}

is generally not invariant under arbitrary shifts in either the continuous or discrete setting. For instance, in 1-D,

(ψj,n)τ{ψj,n}forτ=2j/2.(\psi_{j',n'})_{\tau} \notin \{ \psi_{j,n} \} \quad \text{for} \quad \tau=2^{j\prime}/2.

Cycle spinning.

For a finite group Δ\Delta of periodic shifts, average the shifted, denoised, and realigned outputs of D\mathcal{D} to obtain a translation-invariant estimator:

Dinv(f)=1ΔτΔD(fτ)τ.(7.11)\mathcal{D}_{\text{inv}}(f) = \frac{1}{|\Delta|} \sum_{\tau \in \Delta} \mathcal{D}( f_{\tau} )_{-\tau}. \tag{7.11}

One checks that

τΔ,Dinv(f)=Dinv(fτ)τ\forall \,\tau \in \Delta, \quad \mathcal{D}_{\text{inv}}(f) = \mathcal{D}_{\text{inv}}(f_\tau)_{-\tau}

To obtain translation invariance at pixel precision for data with NN samples, one should use a set of Δ=N|\Delta|=N translation vectors. For wavelets, this requires O(N2)O(N^2) operations.

Figure 7.16 applies cycle spinning to hard thresholding in an orthogonal wavelet basis, using the following shifts: Δ={0,1/N0,2/N0,3/N0}2\Delta= \{ 0, 1/N_0, 2/N_0, 3/N_0 \}^2 on an N0×N0N_0\times N_0 image, corresponding to shifts by {0,1,2,3}2\{ 0, 1, 2, 3 \}^2 pixels. This requires 16 forward and inverse wavelet-transform pairs. Averaging this subset of shifts does not in general guarantee exact pixel-shift equivariance. In this example, partial averaging reduces sensitivity to shifts, substantially improves the SNR, and suppresses oscillatory artifacts. These artifacts move as τ\tau changes, so averaging reduces them.

In Figure 7.17, translation-invariant hard thresholding slightly outperforms translation-invariant soft thresholding, reversing their ranking in the orthogonal-basis experiment.

Figure 7.16. Soft thresholding in an orthogonal wavelet basis (left) and translation-invariant hard thresholding (right).

Figure 7.17. SNR as a function of T/σT/\sigma for translation-invariant thresholding.

Translation invariant wavelet frame.

Cycle spinning also has a frame interpretation: replace the orthogonal basis B={ψm}\mathcal{B}= \{\psi_m\} by its translated copies,

Binv={(ψm)τ}m,τΔ.(7.12)\mathcal{B}_{\text{inv}} = \{ (\psi_m)_\tau \}_{m, \tau \in \Delta}. \tag{7.12}

Although Binv\mathcal{B}_{\text{inv}} is no longer an orthogonal basis, orthonormality of each translated copy gives the energy and reconstruction identities

 ⁣f ⁣2=1Δm,τΔf,(ψm)τ2andf=1Δm,τΔf,(ψm)τ(ψm)τ.|\!| f |\!|^2 = \frac{1}{|\Delta|} \sum_{m, \tau \in \Delta} |\langle f,\,(\psi_m)_\tau\rangle|^2 \quad \text{and} \quad f = \frac{1}{|\Delta|} \sum_{m, \tau \in \Delta} \langle f,\,(\psi_m)_\tau\rangle (\psi_m)_\tau.

Such redundant families are called tight frames.

One can then define a translation invariant thresholding denoiser

Dinv(f)=1Δm,τΔST(f,(ψm)τ)(ψm)τ.(7.13)\mathcal{D}_{\text{inv}}(f) = \frac{1}{|\Delta|} \sum_{m, \tau \in \Delta} S_T(\langle f,\,(\psi_m)_\tau\rangle) (\psi_m)_\tau. \tag{7.13}

This estimator equals the cycle spinning estimator defined in (7.11).

Counted with multiplicity, the translated frame has ΔB|\Delta| |\mathcal{B}| elements. For a basis of signals with NN samples and a lattice of Δ=N|\Delta|=N shifts, this gives up to N2N^2 vectors in Binv\mathcal{B}_{\text{inv}}. In a hierarchical construction such as a wavelet basis, however, different shifts can produce the same atom:

(ψm)τ=(ψm)τformmandττ,(\psi_m)_\tau = (\psi_{m'})_{\tau'} \quad \text{for} \quad m \neq m' \quad \text{and} \quad \tau\neq \tau',

The number of distinct vectors in Binv\mathcal{B}_{\text{inv}} can therefore be much smaller than N2N^2. For instance, for an orthogonal wavelet basis, one has

(ψj,n)k2j=ψj,n+k,(\psi_{j,n})_{k 2^j} = \psi_{j,n+k},

so many translated atoms coincide. For a signal of length NN, an undecimated transform has log2N\log_2N detail arrays of length NN, plus a coarse array. For an N0×N0N_0\times N_0 image (N=N02N=N_0^2), it has 3log2N03\log_2N_0 detail arrays of NN entries, plus a coarse array. Appropriate multiplicity weights must be retained when replacing the full translated family by distinct atoms.

The fast undecimated wavelet transform, often called the “à trous” transform, computes these coefficients in O(NlogN)O(N\log N) operations. Each detail array is indexed directly by every pixel location:

djω[n]=f,(ψj,0ω)n,n{0,,N01}2,ω{V,H,D},d_j^\omega[n]=\langle f,\,(\psi_{j,0}^\omega)_n\rangle,\qquad n\in\{0,\ldots,N_0-1\}^2,\quad\omega\in\{V,H,D\},

where the wavelets and shifts are discrete and appropriately normalized. Each array is a band-pass filtered image, as illustrated in Figure 7.18.

Figure 7.18. Translation invariant wavelet coefficients.

Figure 7.19 illustrates hard thresholding of these translated coefficients.

Figure 7.19. Left: translation invariant wavelet coefficients, for j=8,ω=Hj=-8, \omega=H, right: thresholded coefficients.

7.3.5 Other Shrinkage Rules

Other shrinkage rules offer different compromises between retaining large coefficients and suppressing noise. We describe two examples whose performance depends on the coefficient distribution of ff in the chosen basis.

Semi-soft thresholding.

Semi-soft thresholding interpolates between hard and soft thresholding through a parameter μ>1\mu>1:

STθ(x)=g11θ(x)wheregμ(x)={0ifx<Txifx>μTsign(x)μ(xT)μ1 otherwise.S_T^\theta(x) = g_{\frac{1}{1-\theta}}(x) \quad \text{where} \quad g_\mu(x) = \left\{ \begin{array}{l} 0 \quad \text{if} \quad |x|<T\\ x \quad \text{if} \quad |x|>\mu T\\ \mathop{\mathrm{sign}}(x)\frac{\mu(|x|-T)}{\mu-1} \text{ otherwise.} \end{array} \right.

For 0<θ<10<\theta<1, set μ=1/(1θ)\mu=1/(1-\theta). The limits θ0\theta\downarrow0 and θ1\theta\uparrow1 give hard and soft thresholding, respectively, away from the threshold boundary. Figure 7.20 shows an example of this nonlinearity.

Figure 7.20. Left: semi-soft thresholder, right: Stein thresholder.

Figure 7.21 shows an SNR improvement for a suitable choice of μ\mu, although the visual difference from hard and soft thresholding is small.

Figure 7.21. Left: SNR as a function of μ\mu and T/σT/\sigma. Right: SNR versus μ\mu, with T/σT/\sigma optimized separately for each μ\mu.

Stein thresholding.

Stein thresholding is defined using a quadratic attenuation of large coefficients

STStein(x)=max(1T2x2,0)x.S_T^{\text{Stein}}(x) = \max\left( 1-\frac{T^2}{|x|^2},0 \right)x.

The value at x=0x=0 is defined to be zero. This should be compared with the linear attenuation of soft thresholding

ST1(x)=max(1Tx,0)x.S_T^1(x) = \max\left( 1-\frac{T}{|x|},0 \right)x.

For large coefficients, Stein thresholding has the following shrinkage behavior:

STStein(x)x0 whereas ST1(x)xT,|S_T^{\text{Stein}}(x)-x| \rightarrow 0 \quad\text{ whereas }\quad |S_T^1(x)-x| \rightarrow T,

as x±x \rightarrow \pm \infty. Its deterministic shrinkage tends to zero, whereas soft thresholding retains a fixed shrinkage. This limiting property does not imply unbiased estimation at finite amplitudes.

Figure 7.22. SNR as a function of T/σT/\sigma for Stein thresholding.

Stein and hard thresholding give similar results in the translation-invariant natural-image experiments shown here.

7.3.6 Block Thresholding

The nonlinear thresholding methods above are diagonal estimators, since they attenuate each coefficient separately

f~=mATq(f,ψm)f,ψmψm\tilde f = \sum_m A_T^q(\langle f,\,\psi_m\rangle) \langle f,\,\psi_m\rangle \psi_m

where

ATq(x)={max(1T2/x2,0)forq=Steinmax(1T/x,0)forq=1 (soft)1x>Tforq=0 (hard)A_T^q(x) = \left\{ \begin{array}{l} \max(1-T^2/|x|^2,0) \quad \text{for} \quad q=\text{Stein}\\ \max(1-T/|x|,0) \quad \text{for} \quad q=1\text{ (soft)}\\ 1_{|x|>T} \quad \text{for} \quad q=0\text{ (hard)} \end{array} \right.

Define every attenuation factor to be zero at x=0x=0 when T>0T>0. Block thresholding shares an attenuation factor across a group of coefficients, exploiting their statistical dependence. This is useful for natural images, where edges create clusters of large wavelet coefficients. Grouping also helps suppress isolated noise coefficients in otherwise smooth regions.

Partition the coefficients into disjoint blocks; for example, in a 2-D wavelet transform,

{(j,n,ω)}j,n,ω=kBk,\{ (j,n,\omega) \}_{j,n,\omega} = \bigcup_k B_k,

where each BkB_k contains s×ss\times s neighboring coefficients at a fixed scale and orientation. The block size ss is a parameter of the method. Figure 7.23 shows an example of such a block.

The mean squared coefficient magnitude in a block is

Ek=1BkmBkf,ψm2.E_k=\frac{1}{|B_k|} \sum_{ m \in B_k } |\langle f,\,\psi_m\rangle|^2.

The block estimator

f~=mSTblock,q(f,ψm)ψm\tilde f = \sum_m S_T^{\text{block},q}(\langle f,\,\psi_m\rangle) \psi_m

applies the same attenuation to every coefficient in a block,

mBk,STblock,q(f,ψm)=ATq(Ek)f,ψm,\forall \,m \in B_k, \quad S_T^{\text{block},q} (\langle f,\,\psi_m\rangle) = A_T^q(\sqrt{E_k}) \langle f,\,\psi_m\rangle,

for q{0,1,stein}q \in \{0,1,\text{stein}\}. Figure 7.23 shows the attenuated blocks and the reconstructed image.

Figure 7.23. Left: wavelet coefficients, center: block thresholded coefficients, right: denoised image.

Figure 7.24, left, compares the rules for q{0,1,stein}q \in \{0,1,\text{stein}\}. Stein block thresholding gives the highest SNR in this comparison. Figure 7.24, right, compares block sizes for Stein thresholding. The choice s=4s=4 performs well in the displayed experiment.

Figure 7.24. SNR as a function of T/σT/\sigma (left) and comparison of different block sizes (right).

Figure 7.25 compares the reconstructions. Stein block thresholding in an orthogonal wavelet basis approaches the quality of translation-invariant hard thresholding here, at lower computational cost. The block thresholding strategy can also be applied to wavelet coefficients in a translation invariant tight frame, which gives the best result among the methods compared in this experiment.

The same block attenuation can be implemented directly after the wavelet transform.

Figure 7.25. Left: translation invariant wavelet hard thresholding, center: block orthogonal Stein thresholding, right: block translation invariant Stein thresholding.

More advanced denoisers use richer statistical models to improve on the methods presented here; see, for instance, [27].

7.4 Signal-Dependent Noise

In many imaging systems, the variance of the noise affecting f0,nf_{0,n} depends on the intensity f0,nf_{0,n} itself. We now study Poisson counts and multiplicative noise. Both can be expressed as additive residuals, but their residual distributions depend on the signal.

7.4.1 Poisson Noise

Many imaging devices measure intensity by counting photons. Examples include digital cameras, confocal microscopy, PET and SPECT tomography.

Poisson model.

For an unknown mean intensity f0,n0f_{0,n}\geqslant 0, a Poisson model describes the observed photon count:

fnP(λ)whereλ=f0,n[0,),f_n \sim \mathcal{P}(\lambda) \quad \text{where} \quad \lambda=f_{0,n}\in[0,\infty),

The Poisson distribution P(λ)\mathcal{P}(\lambda) has probability mass function

P(fn=k)=λkeλk!\mathbb{P}(f_n=k)=\frac{\lambda^k e^{-\lambda}}{k!}

and its parameter varies across pixels with the underlying intensity. Figure 7.26 shows several Poisson distributions.

Figure 7.26. Poisson distributions for various λ\lambda.

One has

E(fn)=λ=f0,nandVar(fn)=λ=f0,n\mathbb E(f_n)=\lambda=f_{0,n} \quad \text{and} \quad \text{Var}(f_n)=\lambda=f_{0,n}

Thus denoising again estimates a mean from one observation, but the variance now varies with intensity. The absolute noise level increases as more photons reach the sensor. For positive intensity, the relative standard deviation f0,n1/2f_{0,n}^{-1/2} instead decreases.

Figure 7.27 shows Poisson-corrupted versions of a clean image f0f_0 at different maximum mean intensities λmax\lambda_{\max}.

Figure 7.27. Poisson-corrupted flower images at increasing photon-count scales λmax\lambda_{\max}.

Variance stabilization.

Applying a thresholding estimator

D(f)=mSTq(f,ψm)ψm\mathcal{D}(f) = \sum_m S_T^q(\langle f,\,\psi_m\rangle) \psi_m

directly to ff can perform poorly because a single threshold TT cannot adapt to spatially varying noise. A variance-stabilizing transform φ:[0,+)R\varphi: [0,+\infty) \rightarrow \mathbb{R}, applied pixelwise, maps the counts to φ(f)\varphi(f). An additive Gaussian white-noise model can then be a useful approximation:

φ(f)φ(f0)+w(7.14)\varphi(f) \approx \varphi(f_0) + w \tag{7.14}

where wnN(0,σ2)w_n\sim\mathcal{N}(0,\sigma^2) are independent centered Gaussians with constant variance σ2\sigma^2.

The model (7.14) is approximate, and its accuracy depends on the intensity range of f0,nf_{0,n}. Two common variance-stabilizing transforms for Poisson noise are the Anscombe transform

φ(x)=2x+3/8\varphi(x) = 2\sqrt{x+3/8}

and the Freeman–Tukey transform

φ(x)=x+1+x.\varphi(x) = \sqrt{x+1}+\sqrt{x}.

Figure 7.28 compares the variance of φ(f)\varphi(f) after these transformations.

Figure 7.28. Exact Poisson variances of the Anscombe, Freeman–Tukey, and 2x2\sqrt{x} transforms as functions of the mean intensity.

A variance-stabilized denoiser is defined as

Dstab,q(f)=φ1(mSTq(φ(f),ψm)ψm)\mathcal{D}^{\text{stab},q}(f) = \varphi^{-1}( \sum_m S_T^q(\langle \varphi(f),\,\psi_m\rangle) \psi_m )

where φ1\varphi^{-1} is applied after projecting the denoised values onto its domain. The direct inverse generally introduces bias, especially at low counts; bias-corrected inverse transforms can improve the result.

At the moderate count levels in Figure 7.29, variance stabilization improves the denoising result.

Figure 7.29. Left: noisy image, center: denoising without variance stabilization, right: denoising after variance stabilization.

7.4.2 Multiplicative Noise

Multiplicative image formation.

A multiplicative noise model assumes that

fn=f0,nwnf_n = f_{0,n} w_n

where ww is a random multiplier, observed through one realization, with E(wn)=1\mathbb E(w_n)=1. Once again, the noise level depends on the pixel value

E(fn)=f0,nandVar(fn)=f0,n2σ2whereσ2=Var(wn).\mathbb E(f_n) = f_{0,n} \quad \text{and} \quad \text{Var}(f_n) = f_{0,n}^2 \sigma^2 \quad \text{where} \quad \sigma^2=\operatorname{Var}(w_n).

In SAR imaging, a common model forms ff by averaging KK independent observations, called looks:

1sK,fn(s)=f0,nwn(s)+rn(s)\forall \,1\leqslant s\leqslant K, \quad f^{(s)}_n = f_{0,n} w^{(s)}_n + r^{(s)}_n

where r(s)r^{(s)} is additive Gaussian white noise and the multiplier wn(s)w^{(s)}_n has an exponential distribution:

pwn(s)(x)=ex1x>0.p_{w^{(s)}_n}(x)=e^{-x}\mathbf1_{x>0}.

Averaging KK independent looks divides the additive-noise variance by KK. When the remaining additive component is negligible, the average is approximately

fn=1Ks=1Kfn(s)f0,nwnf_n = \frac{1}{K} \sum_{s=1}^K f^{(s)}_n \approx f_{0,n} w_n

where the multiplicative factor is distributed according to a Gamma distribution

wnGamma(shape=K,rate=K),pwn(x)=KKΓ(K)xK1eKx1x>0.w_n\sim\operatorname{Gamma}(\text{shape}=K,\text{rate}=K),\qquad p_{w_n}(x)=\frac{K^K}{\Gamma(K)}x^{K-1}e^{-Kx}\mathbf1_{x>0}.

Its mean is one and its variance is 1/K1/K, so increasing KK reduces the relative noise level.

Figure 7.30. Multiplicative Gamma noise for increasing numbers KK of averaged looks, with standard deviation σ=K1/2\sigma=K^{-1/2}.

Figure 7.30 illustrates how the noise changes with the number K=1/σ2K=1/\sigma^2 of averaged looks.

A simple variance stabilization transform is

φ(x)=log(x)c\varphi(x)=\log(x) - c

where

c=E(log(w))=ψ(K)log(K)whereψ(x)=Γ(x)/Γ(x)c = \text{E}(\log(w)) = \psi(K) - \log(K) \quad \text{where} \quad \psi(x) = \Gamma'(x)/\Gamma(x)

Here Γ\Gamma is the Gamma function and ψ\psi is its logarithmic derivative, the digamma function. The transformed observation satisfies

φ(f)n=logf0,n+zn,\varphi(f)_n=\log f_{0,n}+z_n,

for strictly positive intensities, where zn=log(wn)cz_n=\log(w_n)-c is centered additive noise with variance ψ(1)(K)\psi^{(1)}(K); ψ(1)\psi^{(1)} is the derivative of the digamma function. Thus the transformed target is logf0\log f_0, not φ(f0)\varphi(f_0). Exponentiating an estimate of logf0\log f_0 introduces a further statistical bias and may require correction.

Figure 7.31. Histogram of multiplicative noise before (left) and after (right) stabilization.

Figure 7.31 shows the effect of this variance stabilization on the distributions of ww and zz.

Figure 7.32 compares the two approaches at moderate noise levels σ\sigma, where variance stabilization improves the displayed result.

Figure 7.32. Left: noisy image, center: denoising after variance stabilization, right: denoising without variance stabilization.