Lectures 23 and 24 (May 6)

Constrained Optimization: Lagrange multiplier: $\min_u I(u)$ subject to $J(u)=0$ becomes $\min_{u,\lambda} I(u)+\lambda J(u)$.

A simple model for image denoising

Additive noise model: $f=u+n$, where $f$ is the observed image, $u$ is an unknown clean image and $n$ is the noise following $N(0,\sigma^2)$.

$$
\min \int |\nabla u|^2
$$
such that $\int n^2 = \int (f-u)^2 =\sigma^2$.

We introduce a Lagrange multiplier and minimize the following functional
$$
\min \int |\nabla u|^2 + \lambda (f-u)^2 \, .
$$

The Euler-Lagrange equation is given by
$$
-\Delta u + \lambda (f-u) = 0 \, .
$$

Solving it using Fourier transform, we have
$$
u= \mathcal{F}^{-1} \left( \frac{1}{1+\frac{4\pi^2}{\lambda} (p^2+q^2)} \hat{f}_{p,q} \right) \, .
$$
And this is the Butterworth low pass filter.

Rudin-Osher-Fatemi (ROF)

$$

\min \int |\nabla u| + \lambda (f-u)^2 \, .

$$

The Euler-Lagrange equation is given by

$$

-\nabla \cdot \left( \frac{\nabla u}{|\nabla u|} \right) + 2 \lambda (f-u) = 0 \, .

$$

Some properties of ROF:

1) Comparing with the diffusion equation

$$

\frac{\partial u}{\partial t} = \nabla \cdot \left( a(x) \nabla u \right) \, .

$$

For homogeneous region, $|\nabla u| \sim 0$ and so $a(x) \gg 1$, which gives fast diffusion.

Near edge, $|\nabla u| \gg 1$ and so $a(x) \sim 0$, which gives small diffusion.

2) Decide $\lambda$ in the original paper

$$

\lambda= \frac{1}{2\sigma^2} \int \frac{\nabla u \cdot \nabla f}{|\nabla u|} - |\nabla u| \, .

$$

3) Coarea formula

$$

\int \| \nabla 1_{\Omega} \|_2 = \mbox{ arclength of $\partial \Omega$} \, .

$$

Therefore, if $f=1_{\mathcal{B}_r}$, the minimizer to the ROF is

$$

u= c \, 1_{\mathcal{B}_r} = \max(0,1-\frac{1}{\lambda r}) \, 1_{\mathcal{B}_r} \, .

$$

This implies some part of the signal will always be regarded as noise.

p.127: the derivation on showing that the diffusion is along the tangential direction of the contours.

TV-L1 (BV-L1) Model

$$

E(u)= \int \| \nabla u \| + \lambda |f-u| \, .

$$

If $f=1_{\mathcal{B}_r(0,0)}$, then the minimizer to the TV-L1 model is

$u=f$ if $\lambda r>2$ and $u=0$ if $\lambda r<2$.

Reading Materials

MATLAB Demo: [click here]

PPT: [click here]

Lecture Notes: p.120-127