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

Lecture 21 and 22 (Apr 29)

Calculus of variation

Functional: I(y): function $\rightarrow \mathbb{R}$.

Example: Brachistochrone Problem:
$$
I(y)=\int_a^b \sqrt{\frac{1+(y')^2}{2gy}} dx \, .
$$

Euler-Lagrange equation

first order optimality condition. Necessary but not sufficient.

Euler's solution: let $N=\frac{\partial f}{\partial y}$ and $P=\frac{\partial f}{\partial y'}$,
$$
N- \frac{d}{dx} P =0 \, .
$$

Gradient Descent

$$
\min_x f(x)
$$
where $f:\mathbb{R} \rightarrow \mathbb{R}$.

Direct approach: Solve $f'(x)=0$ for $x$.

Iterative approach:
$$
x_{n+1}=x_n-\epsilon f'(x_n)
$$
for some initial guess $x_0$ and some small $\epsilon>0$.

Time-dependent approach: artificial time $t$,
$$
\frac{x_{n+1}-x_n}{\epsilon} = -f'(x_n) \, .
$$
Taking $\epsilon \rightarrow 0$, we have
$$
\frac{d}{dt} x(t) = -f'(x(t)) \, ,
$$
with the initial condition $x(t=0)=x_0$. The steady state solution will correspond to a local minimum.

$$
\frac{d}{dt} f(x(t)) = \frac{df}{dx} \cdot \frac{dx}{dt} = f' \cdot (-f') = -(f')^2 \le 0 \, .
$$

Gradient Descent for Functional

$$
\min_y I(y)
$$
for a functional $I$. We introduce an artificial time variable and solve
$$
\frac{\partial y}{\partial t} = - \nabla_y I
$$
with the initial condition $y(x,0)=y_0(x)$. The steady state solution solves $\nabla_y I =0$.

Reading Materials

Lecture Notes: p.110-116

Lecture 20 (Apr 26)

Deconvolution

$g=h*f$, given both $g$ and $h$, want to determine $f$.

If only $g$ is given, we have a blind deconvolution problem.

$$
f=\mathcal{F}^{-1}\left[ \frac{\mathcal{F}(g)}{\mathcal{F}(h)} \right] \, .
$$

If there is noise, $g=h*f+n$, then
$$
f=\mathcal{F}^{-1}\left[ \frac{\mathcal{F}(g)}{\mathcal{F}(h)} \right]
- \mathcal{F}^{-1}\left[ \frac{\mathcal{F}(n)}{\mathcal{F}(h)} \right]
\, .
$$
Problems:
1. $n$ is an unknown;
2. $|\hat{h}_{p,q}| \sim 0$ will amplify the effect from the error term.

Optimization problem

Given $h$ (and so the matrix $H$) and $g$, want to determine $f$ such that
(1) $Hf=g$;
(2) $\min_f \|Hf-g\|_2^2$.

A circulant matrix $H$ can be diagonalized by Fourier transform, i.e. $H=WDW^{-1}$ where $W$ is the Fourier matrix. So $WDW^{-1} f =g$ and we also have $f=WD^{-1}W^{-1} g$, i.e. we determine $f$ by
1. compute the Fourier transform of $g$;
2. divide the Fourier coefficients by the Fourier coefficient of $h$;
3. compute the inverse Fourier transform.

Some matrix operations:
1) $\nabla_x (a^T x)=a$;
2) $\nabla_x (x^T A^T A x)=2 A^T A x$.

The minimizer to the minimization problem $\min_f \|Hf-g\|_2^2$ is given by
$$
f = (H^* H)^{-1} H^* g \, .
$$

Constrained optimization

$$
\min_x f(x)
$$
subject to $g(x)=0$.

Or, using a Lagrange multiplier to obtain an unconstrained optimization problem:
$$
\min_{x,\lambda} f(x)+\lambda g(x) \, .
$$

Constrained optimization formulation for deconvolution with noise:
$$
\min_f \|Q f\|_2^2
$$
subject to $\|Hf-g\|_2^2=\|n\|_2^2$, for some linear location-invariant operator $Q$, i.e. both $H$ and $Q$ can be diagonalized by the Fourier transform, $H=WDW^{-1}$ and $Q=WAW^{-1}$. The minimizer to the constrained problem can be solved by introducing a Lagrange multiplier. The solution is
$$
f=W\left(D^T D+\frac{1}{\lambda} A^T A \right)^{-1} D^T W^{-1} g \, .
$$

In the component form, we have
$$
f = \mathcal{F}^{-1} \left( \frac{d_i^*}{|d_i|^2 + \frac{1}{\lambda} |a_i|^2} \hat{g}_i \right) \, ,
$$
where $\hat{g}=\mathcal{F}(g)$.

Limitation

1) minimization w.r.t. $\lambda$: eye-norm, i.e. try various $\lambda$ and pick the best solution to human;
2) What is $Q$? For example, $Qf=\nabla^2 f$.

Reading materials

Lecture note: p.100-104

HW6

Problems:
#5.91, 94, 97, 100

Problems: [click here]
Due: May 9 (Thursday)
Submit: To the TA 

Project Final Report

Due: May 9 (Thursday) 1159pm

The requirement for the final report is no more than 
(1) eight (8) pages for individual project,
(2) ten (10) pages for group of 2 students,
(3) twelve (12) pages for group of 3 students.

Your project report should contain some background on the topic, the research methodology and your findings with enough supports. It will be graded based on, but not limited to, the following criteria (max 3% each)
1) accuracy;
2) execution;
3) presentation;
4) creativeness.

Any evidence of word-for-word copying from books or webpage will result in a lowered grade. You should research ideas for your group in the library and on the world-wide-web. Your paper should reference papers, books, etc. that you use in your work. 

Please email me a zip file of the final report and any code developed.

Lecture 19 (Apr 15)

Image Denoising

Ideal low pass filter:

$$

\hat{h}_{p,q}= \left\{

\begin{array}{cc}

1 & \mbox{ if $D(p,q)\le D_0$} \\

0 & \mbox{ otherwise.}

\end{array}

\right.

$$

Butterworth low pass filter

$$

\hat{h}_{p,q}=\frac{1}{1+[D(p,q)/D_0]^{2n}} \, .

$$

Gaussian low pass filter

$$

\hat{h}_{p,q}=e^{-D(p,q)^2}{2\sigma^2} \, .

$$

Image Edge Detection

Ideal high pass filter:

$$

\hat{h}_{p,q}= \left\{

\begin{array}{cc}

0 & \mbox{ if $D(p,q)\le D_0$} \\

1 & \mbox{ otherwise.}

\end{array}

\right.

$$

Butterworth high pass filter

$$

\hat{h}_{p,q}=1-\frac{1}{1+[D(p,q)/D_0]^{2n}}=\frac{1}{1+[D_0/D(p,q)]^{2n}} \, .

$$

Gaussian low pass filter

$$

\hat{h}_{p,q}=1-e^{-D(p,q)^2/(2\sigma^2)} \, .

$$

Deconvolution

$g=h*f$, given both $g$ and $h$, want to determine $f$.

If only $g$ is given, we have a blind deconvolution problem.

$$
f=\mathcal{F}^{-1}\left[ \frac{\mathcal{F}(g)}{\mathcal{F}(h)} \right] \, .
$$

Reading materials

MATLAB demo files for the ideal low pass filter: [Driver.m] [ideal_low.m]
Lecture notes: p.94-100

Lecture 18 (Apr 12)

Two dimensional generalizations

1) Fourier Transform
$$
f(x,y)=\int \int \hat{f}(u,v) e^{i2\pi(ux+vy)} du dv \\
\hat{f}(u,v)=\int \int f(x,y) e^{-i2\pi(ux+vy)} dx dy \, .
$$
2) Discrete Fourier Transform
$$
f_{m,n}= \frac{1}{MN} \sum_{p=0}^{M-1} \sum_{q=0}^{N-1} \hat{f}_{p,q} e^{i 2\pi \left( \frac{pm}{M}+\frac{qn}{N} \right)} \\
\hat{f}_{p,q}=\sum_{m=0}^{M-1} \sum_{n=0}^{N-1} f_{m,n} e^{-i 2\pi \left( \frac{pm}{M}+\frac{qn}{N} \right)} \, .
$$

Some properties

1) Periodicity:
$$
\hat{f}_{p,q}=\hat{f}_{p+k_1 M,q}=\hat{f}_{p,q+k_2 N}=\hat{f}_{p+k_1 M,q+k_2 N}
$$
for any integer $k_1$ and $k_2$.
2) Translation:
$$
\mathcal{F} \left[
f_{m,n} e^{i 2\pi \left( \frac{p^*m}{M}+\frac{q^*n}{N} \right)} \right] = \hat{f}_{p-p^*,q-q^*}
$$
3) From (2), take $p^*=M/2$ and $q^*=N/2$, we have
$$
\mathcal{F} \left[
f_{m,n} (-1)^{m+n} \right] = \hat{f}_{p-M/2,q-N/2} \, .
$$

Image Enhancement

Design $\hat{h}$ such that $\tilde{f}=\mathcal{F}^{-1}(\hat{h} \cdot \hat{g})$ achieves some properties.

Reading Materials:

Lecture Notes: p.94