Image Processing and Computer

Vision

Assignment T2

Jan Hendrik Dithmar

2031259

Group T1: Tue, 14-16 (Sebastian Zimmer)

Assignment T2  Dithmar (2031259)

This is a sample text to see, whether deactivating oplocks helps... blubb... blubb again

2.1 Image Pyramids

We have the following signal

f = (−20, −2, 11, −4, −12, −20, 6, 24, 12)^{⊤}

Let’s do the Gaussian pyramid first:

v^{3} = f
v^{2} = R_{3}^{2}v^{3}

= ( \begin{matrix}\frac{2}{3} & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{3} & \frac{2}{3} \end{matrix} ) ( \begin{matrix}−20 \\ −2 \\ 11 \\ −4 \\ −12 \\ −20 \\ 6 \\ 24 \\ 12 \end{matrix} )

= (−14, 4, −12, 4, 16)^{⊤}
v^{1} = R_{2}^{1}v^{2}

= ( \begin{matrix}\frac{2}{3} & \frac{1}{3} & 0 & 0 & 0 \\ 0\frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 \\ 0 & 0 & 0 & \frac{1}{3} & \frac{2}{3} \end{matrix} ) ( \begin{matrix}−14 \\ 4 \\ −12 \\ 4 \\ 16 \end{matrix} )

= (−8, −4, 12)^{⊤}
v^{0} = R_{1}^{0}v^{1}
= ( \frac{1}{3} \frac{1}{3} \frac{1}{3} ) ( \begin{matrix}−8 \\ −4 \\ 12 \end{matrix} )
= 0

The Gaussian pyramid of the signal f is {v^{3}, v^{2}, v^{1}, v^{0}}.

Now I compute the Laplacian pyramid:

w^{0} = v^{0} = 0
w^{1} = v^{1} − P_{0}^{1}v^{0}
= ( \begin{matrix}−8 \\ −4 \\ 12 \end{matrix} ) − ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) · 0

= ( \begin{matrix}−8 \\ −4 \\ 12 \end{matrix} )

w^{2} = v^{2} − P_{1}^{2}v^{1}

= ( \begin{matrix}−14 \\ 4 \\ −12 \\ 4 \\ 16 \end{matrix} ) − ( \begin{matrix}1 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 1 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 \end{matrix} ) · ( \begin{matrix}−8 \\ −4 \\ 12 \end{matrix} )

= ( \begin{matrix}−14 \\ 4 \\ −12 \\ 4 \\ 16 \end{matrix} ) − ( \begin{matrix}−8 \\ −6 \\ −4 \\ 4 \\ 12 \end{matrix} )

= ( \begin{matrix}−6 \\ 10 \\ −8 \\ 0 \\ 4 \end{matrix} )

w^{3} = v^{3} − P_{2}^{3}v^{2}

= ( \begin{matrix}−20 \\ −2 \\ 1 \\ −4 \\ −12 \\ −20 \\ 6 \\ 24 \\ 12 \end{matrix} ) − ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 1 \end{matrix} ) · ( \begin{matrix}−14 \\ 4 \\ −12 \\ 4 \\ 16 \end{matrix} )

= ( \begin{matrix}−20 \\ −2 \\ 1 \\ −4 \\ −12 \\ −20 \\ 6 \\ 24 \\ 12 \end{matrix} ) − ( \begin{matrix}−14 \\ −5 \\ 4 \\ −4 \\ −12 \\ −4 \\ 4 \\ 10 \\ 16 \end{matrix} )

= (−6, 3, 7, 0, 0, −16, 2, 14, −4)^{⊤}

The Laplacian pyramid of the signal f is {w^{3}, w^{2}, w^{1}, w^{0}}. Now I reconstruct the initial signal from the Laplacian pyramid:

v^{0} = w^{0} = 0
v^{1} = w^{1} + P_{0}^{1}v^{0}
= ( \begin{matrix}−8 \\ −4 \\ 12 \end{matrix} )

v^{2} = w^{2} + P_{1}^{2}v^{1}

= ( \begin{matrix}−6 \\ 10 \\ −8 \\ 0 \\ 4 \end{matrix} ) + ( \begin{matrix}1 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 1 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 \end{matrix} ) · ( \begin{matrix}−8 \\ −4 \\ 12 \end{matrix} )

= ( \begin{matrix}−6 \\ 10 \\ −8 \\ 0 \\ 4 \end{matrix} ) + ( \begin{matrix}−8 \\ −6 \\ −4 \\ 4 \\ 12 \end{matrix} )

= (−14, 4, −12, 4, 16)^{⊤}
v^{3} = w^{3} + P_{2}^{3}v^{2}

= ( \begin{matrix}−6 \\ 3 \\ 7 \\ 0 \\ 0 \\ −16 \\ 2 \\ 14 \\ −4 \end{matrix} ) + ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 1 \end{matrix} ) · ( \begin{matrix}−14 \\ 4 \\ −12 \\ 4 \\ 16 \end{matrix} )

= ( \begin{matrix}−6 \\ 3 \\ 7 \\ 0 \\ 0 \\ −16 \\ 2 \\ 14 \\ −4 \end{matrix} ) + ( \begin{matrix}−14 \\ −5 \\ 4 \\ −4 \\ −12 \\ −4 \\ 4 \\ 10 \\ 16 \end{matrix} )

= (−20, −2, 11, −4, −12, −20, 6, 24, 12)^{⊤} = f

2.2 Discrete Fourier Transform

First of all, I want to rename the signal f_{1} to f and f_{2} to g for the sake of readability when it comes to (double-)indicies later on. So we have:

f = (6, 8, 2, 4)^{⊤} and g = (4, 6, 8, 2)^{⊤}

a.

f̂_{0} = \frac{1}{2} · ∑_{m=0}^{3} f_{m} · exp (−\frac{i2π0m}{4})
= \frac{1}{2} · (f_{0} + f_{1} + f_{2} + f_{3})
= \frac{1}{2} · (6 + 8 + 2 + 4)
= 10
f̂_{1} = \frac{1}{2} · ∑_{m=0}^{3} f_{m} · exp (−\frac{i2π1m}{4})
= \frac{1}{2} · (f_{0} · e^{0} + f_{1} · e^{−iπ/2} + f_{2} · e^{−iπ} + f_{3} · e^{−i3π/2})
= \frac{1}{2} · (6 · 1 + 8 · (−i) + 2 · (−1) + 4 · i) = \frac{4 − 4i}{2}
= 2 − 2i
f̂_{2} = \frac{1}{2} · ∑_{m=0}^{3} f_{m} · exp (−\frac{i2π2m}{4})
= \frac{1}{2} · (f_{0} · e^{0} + f_{1} · e^{−iπ} + f_{2} · e^{−i2π} + f_{3} · e^{−i3π})
= \frac{1}{2} · (6 · 1 + 8 · (−1) + 2 · 1 + 4 · (−1))
= −2
f̂_{3} = \frac{1}{2} · ∑_{m=0}^{3} f_{m} · exp (−\frac{i2π3m}{4})
= \frac{1}{2} · (f_{0} · e^{0} + f_{1} · e^{−i3π/2} + f_{2} · e^{−i3π} + f_{3} · e^{−i9π/2})
= \frac{1}{2} · (6 · 1 + 8 · i + 2 · (−1) + 4 · (−i)) = \frac{4 + 4i}{2}
= 2 + 2i

ĝ_{0} = \frac{1}{2} · ∑_{m=0}^{3} g_{m} · exp (−\frac{i2π0m}{4})
= \frac{1}{2} · (g_{0} + g_{1} + g_{2} + g_{3}) = \frac{1}{2} · (4 + 6 + 8 + 2)
= 10
ĝ_{1} = \frac{1}{2} · ∑_{m=0}^{3} g_{m} · exp (−\frac{i2π1m}{4})
= \frac{1}{2} · (g_{0} · e^{0} + g_{1} · e^{−iπ/2} + g_{2} · e^{−iπ} + g_{3} · e^{−i3π/2})
= \frac{1}{2} · (4 · 1 + 6 · (−i) + 8 · (−1) + 2 · i) = \frac{−4 − 4i}{2}
= −2 − 2i
ĝ_{2} = \frac{1}{2} · ∑_{m=0}^{3} g_{m} · exp (−\frac{i2π2m}{4})
= \frac{1}{2} · (g_{0} · e^{0} + g_{1} · e^{−iπ} + g_{2} · e^{−i2π} + g_{3} · e^{−i3π})
= \frac{1}{2} · (4 · 1 + 6 · (−1) + 8 · 1 + 2 · (−1))
= 2
ĝ_{3} = \frac{1}{2} · ∑_{m=0}^{3} g_{m} · exp (−\frac{i2π3m}{4})
= \frac{1}{2} · (g_{0} · e^{0} + g_{1} · e^{−i3π/2} + g_{2} · e^{−i3π} + g_{3} · e^{−i9π/2})
= \frac{1}{2} · (4 · 1 + 6 · i + 8 · (−1) + 2 · (−i)) = \frac{−4 + 4i}{2}
= −2 + 2i

Now I compute the spectra of the signals:

|f̂_{0}| = \sqrt{10^{2}} = 10
|f̂_{1}| = \sqrt{2^{2} + (−2 · i)^{2}} = \sqrt{4 + 4i^{2}} = \sqrt{4 − 4} = 0
|f̂_{2}| = \sqrt{(−2)^{2}} = 2
|f̂_{3}| = \sqrt{2^{2} + (2 · i)^{2}} = \sqrt{4 + 4i^{2}} = \sqrt{4 − 4} = 0
\left|{ \atop ĝ_{0}}\right| = \sqrt{10^{2}} = 10
\left|{ \atop ĝ_{1}}\right| = \sqrt{(−2)^{2} + (−2 · i)^{2}} = \sqrt{4 + 4i^{2}} = \sqrt{4 − 4} = 0
\left|{ \atop ĝ_{2}}\right| = \sqrt{2^{2}} = 2
\left|{ \atop ĝ_{3}}\right| = \sqrt{(−2)^{2} + (2 · i)^{2}} = \sqrt{4 + 4i^{2}} = \sqrt{4 − 4} = 0

The Fourier spectra of f and g are identical while the coefficients of f and g are different.

b. The highest frequency is 10 which I set to 0, so I obtain:

f̂_{0} = 0
f̂_{1} = 2 − 2i
f̂_{2} = −2
f̂_{3} = 2 + 2i

The backtransform looks like this:

f_{0} = \frac{1}{2} · ∑_{p=0}^{3} f̂_{p} · exp (\frac{i2πp0}{4})

= \frac{1}{2} · (0 + (2 − 2i) − 2 + (2 + 2i))
= \frac{1}{2} · 2
= 1

f_{1} = \frac{1}{2} · ∑_{p=0}^{3} f̂_{p} · exp (\frac{i2πp1}{4})

= \frac{1}{2} · (0 + (2 − 2i) · e^{iπ/2} − 2 · e^{iπ} + (2 + 2i) · e^{i3π/2})
= \frac{1}{2} · ((2 − 2i) · (−i) − 2 · (−1) + (2 + 2i) · i)
= \frac{1}{2} · (−2i + 2i^{2} + 2 + 2i + 2i^{2})
= \frac{1}{2} · (−2)
= −1
f_{2} = \frac{1}{2} · ∑_{p=0}^{3} f̂_{p} · exp (\frac{i2πp2}{4})

= \frac{1}{2} · (0 + (2 − 2i) · e^{iπ} − 2 · e^{i2π} + (2 + 2i) · e^{i3π})
= \frac{1}{2} · ((2 − 2i) · (−1) − 2 + (2 + 2i) · (−1))
= \frac{1}{2} · (−2 + 2i − 2 − 2 − 2i)
= \frac{1}{2} · (−6)
= −3
f_{3} = \frac{1}{2} · ∑_{p=0}^{3} f̂_{p} · exp (\frac{i2πp3}{4})

= \frac{1}{2} · (0 + (2 − 2i) · e^{i3π/2} − 2 · e^{i3π} + (2 + 2i) · e^{i9π/2})
= \frac{1}{2} · ((2 − 2i) · i + 2 + (2 + 2i) · (−i))
= \frac{1}{2} · (2i − 2i^{2} + 2 − 2i − 2i^{2})
= \frac{1}{2} · 6
= 3

The resulting signal is f = (1, −1, −3, 3)^{⊤}. This signal is symmetric which results in a better signal with respect to smoothness.

2.3 Discrete Fourier Transform

To show that

v_{p} = \frac{1}{\sqrt{M}} (exp (\frac{2πip0}{M}) , exp (\frac{2πip1}{M}) , …, exp (\frac{2πip(M − 1)}{M}))^{⊤}

form an orthonormal basis one has to show the following:

1. We have M different vectors (already known)

2. v_{i} ∈ ℂ^{M} ∀i ∈ {0, ..., M − 1} (already known)

3. Vectors are orthogonal and have norm 1 which meands that they are orthonormal.

The last point has to be shown. For this proof I want to state the following:

⟨v_{p}, v_{q}⟩ = \{ \begin{matrix}1 & (p = q) \\ 0 & (else) \end{matrix} ∀p, q ∈ \{0, ..., M − 1\}

To use this fact, a case distinction is necessary:

• Let p ∈ {0, ..., M − 1}, p = q. Let’s plug in the definition:

⟨v_{p}, v_{q}⟩ = ∑_{m=0}^{M−1} \frac{1}{\sqrt{M}} · exp (\frac{i2πpm}{M}) · \overline{\frac{1}{\sqrt{M}} · exp (\frac{i2πqm}{M})}
= ∑_{m=0}^{M−1} \frac{1}{\sqrt{M}} · exp (\frac{i2πpm}{M}) · \frac{1}{\sqrt{M}} · exp (−\frac{i2πqm}{M})
= \frac{1}{M} · ∑_{m=0}^{M−1} · exp (\frac{i2πm}{M} · (p − q))
=^{(p=q)} \frac{1}{M} · ∑_{m=0}^{M−1} \underbrace{exp(0)}_{=1}
= \frac{M}{M}
= 1

• Let p ∈ {0, ..., M − 1}, p ≠ q. Let’s plug in the definition again:

⟨v_{p}, v_{q}⟩ = ∑_{m=0}^{M−1} \frac{1}{\sqrt{M}} · exp (\frac{i2πpm}{M}) · \overline{\frac{1}{\sqrt{M}} · exp (\frac{i2πqm}{M})}

= ∑_{m=0}^{M−1} \frac{1}{\sqrt{M}} · exp (\frac{i2πpm}{M}) · \frac{1}{\sqrt{M}} · exp (−\frac{i2πqm}{M})

= \frac{1}{M} · ∑_{m=0}^{M−1} · exp (\frac{i2πm}{M} · (p − q))

= \frac{1}{M} · ∑_{m=0}^{M−1} exp (\frac{i2π}{M} · (p − q))^{m}

=^{(∗)} \frac{1}{M} · \frac{1 − exp (\frac{i2π}{M} · (p − q))^{M}}{1 − exp (\frac{i2π}{M} · (p − q))}
= \frac{1}{M} · \frac{1 − exp (\frac{i2πM}{M} · (p − q))}{1 − exp (\frac{i2π}{M} · (p − q))}
= \frac{1}{M} · \frac{1 − exp(i2π(p − q))}{1 − exp (\frac{i2π}{M} · (p − q))}
= \frac{1}{M} · \frac{1 − exp(i2π)^{(p−q)}}{1 − exp (\frac{i2π}{M} · (p − q))}
=^{(∗∗)} \frac{1}{M} · \frac{1 − 1^{(p−q)}}{1 − exp (\frac{i2π}{M} · (p − q))}
= 0

where (∗) is the formula for the geometric series

∑_{k=0}^{n} r^{k} = \frac{1 − r^{n+1}}{1 − r} (r ≠ 1)

and (∗∗) is the fact that 1 = e^{i2π} ∀n ∈ ℤ. I want to prove the latter in just a few lines:

1 = 1^{n}
= (e^{i2π})^{n}
= e^{i2πn}

Since (p − q) ∈ ℤ, the upper equations hold for our case.