Image Processing and Computer

Vision

Assignment T4

Jan Hendrik Dithmar

2031259

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

Assignment T4  Dithmar (2031259)

4.1 Continuous Nonquadratic Variational Methods

a. To state the Euler-Lagrange equations I have to compute the partial derivatives first, where I only look at the integrand

F (x, u, u_{x}) = (\frac{1}{2}(u − f)^{2} + α · λ^{2} · \sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}} ) dx

F_{u} = u − f
F_{u_{x}} = α · λ^{2} · \frac{1}{2} \frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · \frac{2}{λ^{2}} · u_{x}
= α · \frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · u_{x}

Now I can state the Euler-Lagrange equation:

0 = F_{u} − \frac{d}{dx}F_{u_{x}} = (u − f) − \frac{d}{dx} \frac{α}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · u_{x}
= (u − f) − α\frac{d}{dx} \frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · u_{x}
= u − f − α · (\frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · u_{xx} + \frac{d}{dx} · (\frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} ) · u_{x})
= u − f − α · (\frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · u_{xx} + u_{x} · (−\frac{1}{2}) · 2 · \frac{u_{x} · u_{xx}}{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}} )
= u − f − α · (\frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} · u_{xx} − u_{x}^{2} · u_{xx} · \frac{1}{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}} )

= u − f − α · u_{xx} · (\frac{1}{\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}}} − u_{x}^{2} · \frac{1}{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}} )

= u − f − α · u_{xx} · (\frac{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )}{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}} − u_{x}^{2} · \frac{1}{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}} )

= u − f − α · u_{xx} · (\frac{λ^{2} + u_{x}^{2} − u_{x}^{2}}{λ^{2} · (1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}} )
= u − f − α · u_{xx} · \frac{1}{(1 + \frac{u_{x}^{2}}{λ^{2}} )^{\frac{3}{2}}}

with boundary conditions

F_{u_{x}} = 0

in x = a and x = b.

b. λ is some kind of contrast parameter. The idea is that if |∇u| is greater than a certain ”threshold” λ, you have locations where you have edges. This means that you can use this fact for edge preserving.

c. First, one has to show that E(u) is strictly convex. From the lecture (Lecture 15, slide 7) we know that it is helpful to use the fact that g(s) = s^{2} is strictly convex. Furthermore, one has to show that

E(βu + (1 − β)v) < βE(u) + (1 − β)E(v)

which I will do first:

E(βu + (1 − β)v) = ∫_{a}^{b} (\frac{1}{2}((βu + (1 − β)v) − f)^{2}

+αλ^{2}\sqrt{1 + \frac{(βu_{x} + (1 − β)v_{x})^{2}}{λ^{2}}} ) dx

= \frac{1}{2} · ∫_{a}^{b}(βu + (1 − β)v − f)^{2}dx

+αλ^{2} ∫_{a}^{b} \sqrt{1 + \frac{(βu_{x} + (1 − β)v_{x})^{2}}{λ^{2}}} dx

= \frac{1}{2} ∫_{a}^{b}(β(u − f) + (1 − β)(v − f))^{2}dx

+αλ^{2} ∫_{a}^{b} \sqrt{1 + \frac{(βu_{x} + (1 − β)v_{x})^{2}}{λ^{2}}} dx

<^{(∗)} \frac{1}{2}β ∫_{a}^{b}(u − f)^{2}dx

+\frac{1}{2}(1 − β) ∫_{a}^{b}(v − f)^{2}dx

+αλ^{2} ∫_{a}^{b} \sqrt{1 + \frac{(βu_{x} + (1 − β)v_{x})^{2}}{λ^{2}}} dx

<^{(∗∗)} \frac{1}{2}β ∫_{a}^{b}(u − f)^{2}dx + \frac{1}{2}(1 − β) ∫_{a}^{b}(v − f)^{2}dx

+αλ^{2}β ∫_{a}^{b} \sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}} dx

+αλ^{2}(1 − β) ∫_{a}^{b} \sqrt{1 + \frac{v_{x}^{2}}{λ^{2}}} dx

= β ∫_{a}^{b} (\frac{1}{2}(u − f)^{2} + αλ^{2}\sqrt{1 + \frac{u_{x}^{2}}{λ^{2}}} ) dx

+(1 − β) ∫_{a}^{b} (\frac{1}{2}(v − f)^{2} + αλ^{2}\sqrt{1 + \frac{v_{x}^{2}}{λ^{2}}} ) dx

= β · E(u) + (1 − β) · E(v)

where • (∗): g(s) = s^{2} is strictly convex.

• (∗∗): g(y) = \sqrt{1 + y^{2}} is strictly convex.

Proof:

f(x) = \sqrt{1 + \frac{x^{2}}{λ^{2}}} = \sqrt{1 + (\frac{x}{λ})^{2}}
Substitution: y = \frac{x}{λ}
⇒ g(y) = \sqrt{1 + y^{2}}
g_{y} = \frac{y}{\sqrt{1 + y^{2}}}
g_{yy} = \frac{1}{(1 + y^{2})^{\frac{3}{2}}}

The second derivative is positive everywhere, so g(y) = \sqrt{1 + y^{2}} is strictly convex.

Result: This energy functional is strictly convex. From the lecture we know that the solution is unique and the single extremum of E(u) is then a minimum.

4.2 Discrete Variational Methods

a.

E_{f}(u) = \frac{1}{2} · ∑_{k=1}^{N}(u_{k} − f_{k})^{2} + α · λ^{2} · ∑_{k=1}^{N−1} \sqrt{1 + \frac{(u_{k+1} − u_{k})^{2}}{λ^{2} · h^{2}}}

where the signal is given by [u_{1}, …, u_{N}] and h is the step-size.

b. We know from the lecture (Lecture 15, slide 5) that the first partial derivatives w.r.t. u_{1}, ..., u_{N} must vanish:

0 = \frac{∂E_{f}}{∂u_{1}} = u_{1} − f_{1} + \frac{α}{h^{2}} · \frac{u_{2} − u_{1}}{\sqrt{1 + \frac{(u_{2}−u_{1})^{2}}{h^{2}·λ^{2}}}}

0 = \frac{∂E_{f}}{∂u_{i}} = u_{i} − f_{i} + \frac{α}{h^{2}} · (\frac{u_{i} − u_{i−1}}{\sqrt{1 + \frac{(u_{i}−u_{i−1})^{2}}{h^{2}·λ^{2}}}} − \frac{u_{i+1} − u_{i}}{\sqrt{1 + \frac{(u_{i+1}−u_{i})^{2}}{h^{2}·λ^{2}}}} )

, i = 2, ..., N − 1
0 = \frac{∂E_{f}}{∂u_{N}} = u_{N} − f_{N} + \frac{α}{h^{2}} · \frac{u_{N} − u_{N−1}}{\sqrt{1 + \frac{(u_{N} −u_{N−1})^{2}}{h^{2}·λ^{2}}}}

4.3 Wavelet Shrinkage

a.

f = (3, 4, 1, −2, 0, 4, −2, −4)^{⊤}

We have

c_{j,k} = \frac{1}{\sqrt{2}} · (c_{j−1,2k} + c_{j−1,2k+1})
d_{j,k} = \frac{1}{\sqrt{2}} · (c_{j−1,2k} − c_{j−1,2k+1})

and we start from c_{0,k} = f_{k} for k = 0, ..., N − 1 where N = 8. Since f has 8 components, we have the scale j = 1, 2, 3:

c_{1,0} = \frac{1}{\sqrt{2}} · (3 + 4) = \frac{1}{\sqrt{2}} · 7
c_{1,1} = \frac{1}{\sqrt{2}} · (1 + (−2)) = −\frac{1}{\sqrt{2}}
c_{1,2} = \frac{1}{\sqrt{2}} · (0 + 4) = 2\sqrt{2}
c_{1,3} = \frac{1}{\sqrt{2}} · (−2 + (−4)) = −3\sqrt{2}
c_{2,0} = \frac{1}{\sqrt{2}} · (\frac{1}{\sqrt{2}} · 7 + (−\frac{1}{\sqrt{2}})) = 3
c_{2,1} = \frac{1}{\sqrt{2}} · (2\sqrt{2} + (−3\sqrt{2})) = −1
c_{3,0} = \frac{1}{\sqrt{2}} · (3 + (−1)) = \sqrt{2}

d_{1,0} = \frac{1}{\sqrt{2}} · (3 − 4) = −\frac{1}{\sqrt{2}}
d_{1,1} = \frac{1}{\sqrt{2}} · (1 − (−2)) = 3 · \frac{1}{\sqrt{2}}
d_{1,2} = \frac{1}{\sqrt{2}} · (0 − 4) = −2\sqrt{2}
d_{1,3} = \frac{1}{\sqrt{2}} · (−2 − (−4)) = \sqrt{2}
d_{2,0} = \frac{1}{\sqrt{2}} · (\frac{1}{\sqrt{2}} · 7 − (−\frac{1}{\sqrt{2}})) = 4
d_{2,1} = \frac{1}{\sqrt{2}} · (2\sqrt{2} − (−3\sqrt{2})) = 5
d_{3,0} = \frac{1}{\sqrt{2}} · (3 − (−1)) = −\frac{1}{\sqrt{2}}

From that, I can state the transformed signal:

⇒ f̂ = (\sqrt{2}, −\frac{1}{\sqrt{2}}, 4, 5, −\frac{1}{\sqrt{2}}, 3 · \frac{1}{\sqrt{2}}, −2\sqrt{2}, \sqrt{2})^{⊤}

b. The transformed signal f̂ is approximately:

f̂ = (1.4, −0.7, 4, 5, −0.7, 2.1, 2.8, 1.4)^{⊤}

Since we want to remove three coefficients, the threshold parameter T has to be chosen s.t.

3 · \frac{1}{\sqrt{2}} ≤ T

Now I can state the signal after the hard wavelet shrinkage (without touching the scaling coefficient):

f̂′ = (\sqrt{2}, 0, 4, 5, 0, 0, −2\sqrt{2}, 0)^{⊤}

c. Computing the backtransform of the signal f̂′ looks like this: We have

c_{j,2k} = \frac{1}{\sqrt{2}}(c_{j+1,k} + d_{j+1,k})
c_{j,2k+1} = \frac{1}{\sqrt{2}}(c_{j+1,k} − d_{j+1,k})

and use the scale j = 2, 1, 0:

c_{2,0} = \frac{1}{\sqrt{2}} (\sqrt{2} + (−\frac{1}{\sqrt{2}})) = \frac{1}{2}
c_{2,1} = \frac{1}{\sqrt{2}} (\sqrt{2} − (−\frac{1}{\sqrt{2}})) = \frac{3}{2}

c_{1,0} = \frac{1}{\sqrt{2}}(3 + 4) = 7 · \frac{1}{\sqrt{2}}
c_{1,1} = \frac{1}{\sqrt{2}}(3 − 4) = −\frac{1}{\sqrt{2}}
c_{1,2} = \frac{1}{\sqrt{2}}(−1 + 5) = 2 · \sqrt{2}
c_{1,3} = \frac{1}{\sqrt{2}}(−1 − 5) = −3 · \sqrt{2}

c_{0,0} = \frac{1}{\sqrt{2}} (7 · \frac{1}{\sqrt{2}} + 0) = \frac{7}{2}
c_{0,1} = \frac{1}{\sqrt{2}} (7 · \frac{1}{\sqrt{2}} − 0) = \frac{7}{2}
c_{0,2} = \frac{1}{\sqrt{2}} (−\frac{1}{\sqrt{2}} + 0) = −\frac{1}{2}
c_{0,3} = \frac{1}{\sqrt{2}} (−\frac{1}{\sqrt{2}} − 0) = −\frac{1}{2}
c_{0,4} = \frac{1}{\sqrt{2}}(2 · \sqrt{2} + (−2 · \sqrt{2})) = 0
c_{0,5} = \frac{1}{\sqrt{2}}(2 · \sqrt{2} − (−2 · \sqrt{2})) = 4
c_{0,6} = \frac{1}{\sqrt{2}}(−3 · \sqrt{2} + 0) = −3
c_{0,7} = \frac{1}{\sqrt{2}}(−3 · \sqrt{2} − 0) = −3

Since f′_{k} = c_{0,k}, the signal is the following:

f′ = (\frac{7}{2}, \frac{7}{2}, −\frac{1}{2}, −\frac{1}{2}, 0, 4, −3, −3)^{⊤}