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

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

Lecture 17 (Apr 8)

Discrete Fourier Transform

$$

\hat{f}_n = \sum_{m=0}^{N-1} f_m e^{-2\pi i mn/N}

$$

Inverse Discrete Fourier Transform

$$
f_m = \frac{1}{N} \sum_{n=0}^{N-1} \hat{f}_n e^{2\pi i mn/N}
$$

Fourier Matrix: $F_N=[\omega^{mn}]$ where $\omega=e^{-2\pi i/N}$.

The inverse of the Fourier matrix: $F_N^{-1}=\frac{1}{N} \bar{F}_N$.

Fast Fourier Transform

Reading Materials

Lecture Notes: p.92-94

Lecture 16 (Apr 1)

Convolution Theorem

$\mathcal{F}(f*g)(s)= \hat{f}(s) \cdot \hat{g}(s)$.

Discrete Fourier Transform

$$
\hat{f}_n = \sum_{m=0}^{N-1} f_m e^{-2\pi i mn/N}
$$

Inverse Discrete Fourier Transform

$$
f_m = \frac{1}{N} \sum_{n=0}^{N-1} \hat{f}_n e^{2\pi i mn/N}
$$

Fourier Matrix: $F_N=[\omega^{mn}]$ where $\omega=e^{-2\pi i/N}$.

The inverse of the Fourier matrix: $F_N^{-1}=\frac{1}{N} \bar{F}_N$.

Reading Materials

Lecture Notes: p.90-92

Lecture 15 (Mar 25)

Delta function

$$
\mathcal{F}(1)=\delta(y)
$$

$$
\mathcal{F}(\delta)=1
$$

$$
\mathcal{F}(\cos 2\pi x) = \frac{1}{2} [ \delta(y-1)+\delta(y+1)]
$$

Some properties of Fourier Transform

1)
$$

\mathcal{F}(f(ax+b))=\frac{1}{a} e^{\frac{2\pi i by}{a}} \hat{f} \left( \frac{y}{a} \right)
$$
2)
$$

\mathcal{F}(f')=2\pi i y \mathcal{F}(f)
$$
3) Plancherel Identity
$$
\int |f(x)|^2 dx = \int |\hat{f}(y)|^2 dy
$$
4) $\hat{f}(0)=\int f(x) dx=$ are area under the function.

Convolution

$$
f*g(x)=\int_{-\infty}^{\infty} f(x-y) g(y) dy
$$

Properties:
1) Commutative
2) Linear

Convolution Theorem

$\mathcal{F}(f*g)(s)= \hat{f}(s) \cdot \hat{g}(s)$.

Reading Materials

Lecture Notes: p. 82-85, 88-90

Lecture 14 (Mar 22)

Expansions on other intervals

Given a periodic function $f(x)$ on an interval $[-L,L]$, we have
$$
f(x)= \frac{a_0}{2} + \sum_{n=1}^{\infty} \left[ a_n \cos \frac{n\pi x}{L}+ b_n \sin \frac{n\pi x}{L} \right]
$$
where
$$
a_n = \left<f(x),\cos \frac{n\pi x}{L} \right> \, \mbox{ and } \, b_n = \left<f(x),\sin \frac{n\pi x}{L} \right>
$$
and $<f,g>=\frac{1}{L} \int_{-L}^L f(x) g(x) dx$.

Fourier transform

$$
\mathcal{F}(f)(y)= \hat{f}(y) = \int_{-\infty}^{\infty} f(x) e^{-2\pi i xy} dx
$$
and
$$
\mathcal{F}^{-1}(\hat{f}(x)) = f(x) = \int_{-\infty}^{\infty} \hat{f}(y) e^{2\pi i xy} dy \, .
$$

Fourier spectrum

$|\hat{f}(y)|$.

Examples

$$

f(x)=\left\{

\begin{array}{c}

A \mbox{ for $-x_0<x<x_0$} \\

0 \mbox{ otherwise.}

\end{array}

\right.

$$

$$

f(x)=\left\{

\begin{array}{c}

e^{-ax} \mbox{ for $x>0$} \\

0 \mbox{ otherwise.}

\end{array}

\right.

$$

Some difficulties: what are $\mathcal{F}(1)$ and $\mathcal{F}(\cos 2\pi x)$?

Reading Materials

Lecture Notes p.80-82

Lecture 13 (Mar 18)

Fourier Series

Consider
$$
\mathcal{B}=\left\{ \frac{1}{\sqrt{2}} , \cos x, \cos 2x, \cdots, \sin x, \sin 2x , \cdots \right\} \, .
$$

With respect to the inner product
$$
<f,g> = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) g(x) dx \, ,
$$
$\mathcal{B}$ is orthonormal.

Fourier series:
$$
f(x)=\frac{a_0}{2} + \sum_{n=1}^{\infty} ( a_n \cos nx + b_n \sin nx ) \, ,
$$
where
$$
a_0=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) dx \, , \, a_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos nx dx \, , \, b_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin nx dx \, .
$$

Example: $f(x)=x$ on $x\in(-\pi,\pi)$ with periodic extension and is normalized. The partial sum of the Fourier series is given by
$$
s_N(x)= 2\sum_{n=1}^N \frac{(-1)^{n+1}\sin nx}{n} \, .
$$

Pointwise convergence

Given $x^*$, $\forall \epsilon>0, \exists N$ such that $n>N$ we have
$$
|s_n(x^*)-f(x^*)|<\epsilon \, .
$$

But, let $x_N=\frac{2N-1}{2N+1} \pi$, we have
$$
s_N(x_N)-f(x_N) > 0.5622 \, .
$$
This implies: $\forall N, \exists x_N$ such that
$$
|s_N(x_N)-f(x_N)| > 8.9\% \mbox{ of the jump.}
$$

Complex form of Fourier Series

$$
f(x)=\sum_{n=-\infty}^{\infty} c_n e^{inx}
$$
where
$c_n=<f(x),e^{inx}>=\frac{1}{2\pi} \int_{-\pi}^{\pi} f(x) e^{-inx} dx$ or $c_n=\frac{a_n-ib_n}{2}$ and $c_{-n}=\frac{a_n+ib_n}{2}$.

Def (Spectrum): $|c_n|$ vs. $n$.

Reading materials

Lecture Notes p.71-80

Lecture 12 (Mar 15)

Example on low rank matrix completion.

Why 1-norm minimization promotes sparsity?

Fourier Series

Consider
$$
\mathcal{B}=\left\{ \frac{1}{\sqrt{2}} , \cos x, \cos 2x, \cdots, \sin x, \sin 2x , \cdots \right\} \, .
$$

With respect to the inner product
$$
<f,g> = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) g(x) dx \, ,
$$
$\mathcal{B}$ is orthonormal.

Fourier series:
$$
f(x)=\frac{a_0}{2} + \sum_{n=1}^{\infty} ( a_n \cos nx + b_n \sin nx ) \, ,
$$
where
$$
a_0=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) dx \, , \, a_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos nx dx \, , \, b_n=\frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin nx dx \, .
$$

Example: $f(x)=x$ on $x\in(-\pi,\pi)$ with periodic extension and is normalized. The partial sum of the Fourier series is given by
$$
s_N(x)= 2\sum_{n=1}^N \frac{(-1)^{n+1}\sin nx}{n} \, .
$$

Reading materials

Lecture Notes: p.67-71

Lecture 10/11 (Mar 11)

Thm (Error in the low rank approximation): For any $\nu$ with $0\le \nu \le r=$rank$(A)$, let
$$
A_{\nu} = \sum_{j=1}^{\nu} \sigma_j \mathbf{u}_j \mathbf{v}_j^* \, .
$$
Then
\begin{eqnarray*}
\|A-A_{\nu}\|_2 &=& \mbox{inf}_{B\in \mathbb{R}^{M\times N}, \mbox{rank}(B)\le \nu} \|A-B\|_2 = \sigma_{\nu+1} \, , \\
\|A-A_{\nu}\|_F &=& \mbox{inf}_{B\in \mathbb{R}^{M\times N}, \mbox{rank}(B)\le \nu} \|A-B\|_F = \sqrt{\sigma_{\nu+1}+\cdots+\sigma_r^2} \, .
\end{eqnarray*}

Texture Image Inpainting using low rank matrix completion

Netflix problem: predict user rating for movies.

Reading materials

Lecture Notes: p.59-67

Lecture 9 (Mar 8)

Def ($N$ singular values of $A$): length of the $N$ principal semiaxes of $AS$, i.e. $\sigma_1, \sigma_2, \cdots, \sigma_N$ such that $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_N >0$.

Def ($N$ left singular vectors of $A$): $\{ u_1, u_2, \cdots, u_N \}$ orthonormal, principal semiaxes directions.

Def ($N$ right singular vectors of $A$): $\{ v_1, v_2, \cdots, v_N \}$, preimage of $\sigma_i u_i$. It turns out these vectors are orthonormal.

Reduced SVD:
$$
A=\hat{U} \hat{\Sigma} V^*
$$
where $\hat{U}\in\mathbb{R}^{M\times N}$, $\hat{\Sigma}\in\mathbb{R}^{N\times N}$ and $V\in\mathbb{R}^{N\times N}$.

Full SVD

$$
A=U \Sigma V^*
$$
where $U\in\mathbb{R}^{M\times M}$, $\Sigma\in\mathbb{R}^{M\times N}$ and $V\in\mathbb{R}^{N\times N}$.

Properties:
1. $v_i$: eigenvectors of $A^*A$.
2. $u_i$: eigenvectors of $AA^*$.
3. Nonzero singular values are the square roots of the nonzero eigenvalues of $A^*A$ or $AA^*$.

4. Rank$(A)=r=$ the number of nonzero singular values.
5. Range$(A)=$span$(u_1,u_2,\cdots,u_r)$.
6. Null$(A)=$span$(v_{r+1},v_{r+2},\cdots,v_N)$.
7. $A$ is the sum of $r$ rank-one matrices,
$$
A=\sum_{i=1}^r \sigma_i u_i v_i^* \, .
$$

Low rank approximation of $A$

For any $\nu$ such that $0\le \nu \le r$, define
$$
A_{\nu}=\sum_{i=1}^{\nu} \sigma_i u_i v_i^*
$$
is an rank-$\nu$ approximation of $A$.

Image Compression using SVD

Vector norm

A function $\| \cdot \|: \mathbb{R}^m \rightarrow \mathbb{R}$ such that
(1) $\|x\| \ge 0$, $\| x\|=0$ only if $x=0$;
(2) $\|x+y\| \ge \|x\| + \|y\|$;
(3) $\|\alpha x\| = |\alpha| \cdot \|x\|$.

Examples: $\|x\|_1$, $\|x\|_2$, $\|x\|_p$, $\|x\|_{\infty}$.

Matrix norm induced by vector norm

Def: $\|A\|$: the smallest $C\in \mathbb{R}$ such that
$$
\|A x\| \le C \|x\|
$$
for all $x\in \mathbb{R}^m$. Or,
$$
\|A\| = \mbox{sup}_{x\in \mathbb{R}^m, x\ne 0} \frac{ \|Ax\|}{\|x\|} = \mbox{sup}_{\|x\|=1, x \in \mathbb{R}^m} \|Ax\| \, .
$$

Reading materials

Lecture notes: p.56-60.

Lecture 8 (Mar 4)

Nonlinear Transforms

Denoising: Median filter.

Two different norms for the gradient in two dimensions:
$$
\|\nabla f\|_1 = \left| \frac{\partial f}{\partial x} \right| + \left| \frac{\partial f}{\partial y} \right| \\

\|\nabla f\|_2 = \left[ \left( \frac{\partial f}{\partial x} \right)^2 + \left(\frac{\partial f}{\partial y} \right)^2 \right]^{\frac{1}{2}}
$$

Eigenvalue Decomposition (EVD)

If $A$ is not square, there is no EVD.

Even if it's square, there is no guarantee that it has a complete set of e-vectors.

Singular Value Decomposition (SVD)

Geometrical observation: The image of the unit sphere under any $M\times N$ matrix is a hyperellipse.

Assume $A\in \mathbb{R}^{M\times N}$ is full rank, $M\ge N$.

Def ($N$ singular values of $A$): length of the $N$ principal semiaxes of $AS$, i.e. $\sigma_1, \sigma_2, \cdots, \sigma_N$ such that $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_N >0$.

Def ($N$ left singular vectors of $A$): $\{ u_1, u_2, \cdots, u_N \}$ orthonormal, principal semiaxes directions.

Def ($N$ right singular vectors of $A$): $\{ v_1, v_2, \cdots, v_N \}$, preimage of $\sigma_i u_i$. It turns out these vectors are orthonormal.

Reduced SVD:

$$

A=\hat{U} \hat{\Sigma} V^*

$$

where $\hat{U}\in\mathbb{R}^{M\times N}$, $\hat{\Sigma}\in\mathbb{R}^{N\times N}$ and $V\in\mathbb{R}^{N\times N}$.

Reading materials

Lecture Notes: pp.50-57

Lecture 7 (Feb 22)

Matrix representation of a linear transformation using the elementary basis of $\mathbb{R}^{M\times N}$. Compact representation of $w(s,t)$.

Box filter as an example. $TV(w * g)\le TV(g)$.

Edge detection
$$
g(x,y)=f(x,y)+c \Delta f(x,y) \, ,
$$
with $c<0$.

Reading materials

Lecture Notes: p.45-49.

Lecture 5+6 (Feb 18)

Normalized histogram

$h(r_i)=n_i$ represents the number of pixels in the image with intensity $r_i$. $p(r_i)=n_i/MN$ represents the percentage of pixels with the intensity $r_i$ such that $\sum_{i} p(i)=1$.

Histogram equalization

Given the normalized histogram $p_r(r_i)$, want to determine a transformation $s_i=T(r_i)$ for $i=0,1,\cdots,L-1$ such that $p_s(s_i)$ follows the uniform distribution
$$
\Rightarrow s=T(r)=(L-1) \int_0^r p_r(w) dw \, .
$$
In practice where image intensity is an integer, we have
$$
s_i=\mbox{round}\left[ (L-1) \sum_{j=0}^{i} p_r(r_i) \right] \, .
$$

Additive noise model

$g(x,y)=f(x,y)+n(x,y)$ where $f$ is the unknown clean image, $g(x,y)$ is the observed image and $n(x,y)$ is the noise. We assume $n(x,y)$ is a random variable which follows some distribution.

Gaussian noise, uniform noise, salt-and-pepper noise.

Filtering

Convolution
$$
g(x,y)= \sum_s \sum_t w(s,t) f(x-s,y-t) \, .
$$

Properties:
(i) Linear;
(ii) Convolution is commutative (ignoring the boundary effect).

For most image applications, we assume $w(s,t)$ is compact (only non-zero in a small neighborhood of $(x,y)$) and is symmetric.

Matrix representation of a linear transformation using the elementary basis of $\mathbb{R}^{M\times N}$. Compact representation of $w(s,t)$.

Reading Materials

Lecture notes: p.36-45

Slides: [click here]

Lecture 4 (Feb 15)

Relationship to image inpainting
Taking the mean, mode and median of the neighboring intensities:
$E_2(g) =  \sum_{i=1}^N \left| f_i-g \right|^2$, $E_0(g) =  \sum_{i=1}^N \left| f_i-g \right|^0$ and $E_1(g) =  \sum_{i=1}^N \left| f_i-g \right|^1$.

Intensity transformation [$s=T(r)$]: most are application/image dependent.

Reading Materials

Lecture notes: p.31-35

Slides: [click here]

Lecture 3 (Feb 11)

Image Interpolation

Properties of the piecewise linear interpolation:
1. Will not create new global extrema, i.e. $\max_{x\in[x_1,x_M]} p(x) = \max_i f_i$ and  $\min_{x\in[x_1,x_M]} p(x) = \min_i f_i$.
2. $TV(\mathbf{g})=TV(\mathbf{f})$ where $TV(\cdot)$ is the total variation of the signal.
3. It is a linear transformation from $\mathbb{R}^M$ to $\mathbb{R}^{2M-1}$.

Two dimensional (image) interpolation: bilinear interpolation.

Relationship to image inpainting
Taking the mean, mode and median of the neighboring intensities:
$E_2(g) =  \sum_{i=1}^N \left| f_i-g \right|^2$, $E_0(g) =  \sum_{i=1}^N \left| f_i-g \right|^0$ and $E_1(g) =  \sum_{i=1}^N \left| f_i-g \right|^1$.

Reading materials

Lecture notes: p.29-31

Lecture 2 (Feb 8)

Problems about the simple imaging model

Sampling: $\Omega \Rightarrow \Omega'=\{(x,y),x=1,2,\cdots,M, y=1,2,\cdots,N\}$.

Quantization: $[0,L-1] \Rightarrow \{0,1,2,\cdots,L-1\}$. MATLAB data type: uint8 and uint16.

Image interpolation

Given a signal $(x_i,f(x_i))$ for $i=1,2,\cdots,M$, we want to determine an approximation to $f(x^*)$ for $x^* \ne x_i$. Using
(i) High order polynomial interpolation: $p(x) \in P^{M-1}$ such that $p(x_i)=f(x_i) \Rightarrow$ one needs to invert a BIG matrix. This can be partially fixed by better basis for interpolation, such as Lagrange Interpolating Polynomials or Newton's Divided Difference.
(ii) Piecewise polynomial interpolation: determine $p_i(x) \in P^N$ for some $N \ll M-1$ such that the polynomial defined only piecewisely for $x \in [x_i,x_{i+1}]$ for $i=1,\cdots,M-1$. Then
$$
p(x) = \left\{
\begin{array}{cc}
p_1(x) & \mbox{ if $x\in[x_1,x_2]$} \\
p_2(x) & \mbox{ if $x\in[x_2,x_3]$} \\
\vdots & \\
p_{M-1}(x) & \mbox{ if $x\in[x_{M-1},x_M]$.}
\end{array}
\right.
$$
In particular, if $N=1$, the interpolation is called a piecewise linear interpolation.

Some properties of the piecewise linear interpolation

Properties of the piecewise linear interpolation:
1. Will not create new global extrema, i.e. $\max_{x\in[x_1,x_M]} p(x) = \max_i f_i$ and  $\min_{x\in[x_1,x_M]} p(x) = \min_i f_i$.
2. $TV(\mathbf{g})=TV(\mathbf{f})$ where $TV(\cdot)$ is the total variation of the signal.
3. It is a linear transformation from $\mathbb{R}^M$ to $\mathbb{R}^{2M-1}$.

Reading materials

Lecture notes: p.21-22,25-29
Presentation file: [click here]

Lecture 1 (Feb 1)

Overview

Introduction

A simple imaging model.
$$
f: \Omega \rightarrow [0,L]
$$
where $\Omega$ is a bounded domain in $\mathbb{R}^2$.

However, such a simple model has two limitations:
(1) Sampling;
(2) Quantization.

Reading materials

Lecture notes: p.20-21
Presentation file: [click here]