Differential Equations in Image Processing and Computer Vision

Assignment T4

Jan Hendrik Dithmar

2031259

Group 2: Thu, 12-14 (Markus Mainberger)

1  2  3  4  ∑

Assignment T4  Dithmar (2031259)

4.1 Continuous Variational Regularisation

We have

E_{f}(u) = ∫_{Ω} (Ψ_{1} ((u − f)^{2}) + αΨ_{2} (|∇u|^{2})) dx

with

Ψ_{1}(s^{2}) = \sqrt{s^{2} + ε^{2}}
Ψ_{2}(s^{2}) = λ^{2} log (1 + s^{2}/λ^{2})

and α, ε, λ > 0. It follows:

E_{f}(u) = ∫_{Ω} (\sqrt{(u − f)^{2} + ε^{2}} + αλ^{2} log (1 + |∇u|^{2}/λ^{2})) dx

We have

E_{f}(u) = ∫_{Ω} F (x_{1}, x_{2}, u, u_{x_{1}}, u_{x_{2}})dx

which has to satisfy the Euler-Lagrange equation

F_{u} − ∂_{x_{1}}F_{u_{x_{1}}} − ∂_{x_{2}}F_{u_{x_{2}}} = 0

with the boundary condition

n^{⊤} ( \begin{matrix}F_{u_{x_{1}}} \\ F_{u_{x_{2}}} \end{matrix} ) = 0.

F = \sqrt{(u − f)^{2} + ε^{2}} + αλ^{2} log (1 + |∇u|^{2}/λ^{2})
F_{u} = \frac{1}{2} · ((u − f)^{2} + ε^{2})^{− \frac{1}{2}} · 2(u − f)
= \frac{u − f}{\sqrt{(u − f)^{2} + ε^{2}}}
F_{u_{x_{1}}} = αλ^{2} \frac{1}{1 + |∇u|^{2}/λ^{2}} 2u_{x_{1}}/λ^{2}
= 2α\frac{u_{x_{1}}}{1 + |∇u|^{2}/λ^{2}}
F_{u_{x_{2}}} = αλ^{2} \frac{1}{1 + |∇u|^{2}/λ^{2}} 2u_{x_{2}}/λ^{2}
= 2α\frac{u_{x_{2}}}{1 + |∇u|^{2}/λ^{2}}

Just plugging in the results into the Euler-Lagrange equation yields

\frac{u − f}{\sqrt{(u − f)^{2} + ε^{2}}} − ∂_{x_{1}}2α\frac{u_{x_{1}}}{1 + |∇u|^{2}/λ^{2}} − ∂_{x_{2}}2α\frac{u_{x_{2}}}{1 + |∇u|^{2}/λ^{2}} = 0
\frac{u − f}{\sqrt{(u − f)^{2} + ε^{2}}} − 2α∂_{x_{1}} \frac{u_{x_{1}}}{1 + |∇u|^{2}/λ^{2}} − 2α∂_{x_{2}} \frac{u_{x_{2}}}{1 + |∇u|^{2}/λ^{2}} = 0
\frac{u − f}{\sqrt{(u − f)^{2} + ε^{2}}} − 2α div (\frac{∇u}{1 + |∇u|^{2}/λ^{2}} ) = 0

with the boundary condition

n^{⊤} ( \begin{matrix}F_{u_{x_{1}}} \\ F_{u_{x_{2}}} \end{matrix} ) = 0.

This knowledge allows to formulate the gradient descent:

∂_{t}u = −γ∇_{u}E
= −γ · (\frac{u − f}{\sqrt{(u − f)^{2} + ε^{2}}} − 2α div (\frac{∇u}{1 + |∇u|^{2}/λ^{2}} ))

4.2 Rotation Invariance of Energy Functionals

In both cases it should hold the following:

Ψ(u_{x}, u_{y}) = Ψ(u_{ξ}, u_{η})

a. Ψ(u_{x}, u_{y}) = |u_{x}| + |u_{y}|. It follows that Ψ(u_{ξ}, u_{η}) = |u_{ξ}| + |u_{η}|. From the hint we can get the following for u_{ξ} and u_{η}:

u_{ξ} = u_{x} · cos ϑ + u_{y} · sin ϑ
u_{η} = −u_{x} · sin ϑ + u_{y} · cos ϑ

⇒ Ψ(u_{ξ}, u_{η}) = |u_{x} · cos ϑ + u_{y} · sin ϑ| + | − u_{x} · sin ϑ + u_{y} · cos ϑ|

Let’s have a look at the case that ϑ = \frac{π}{4}. Then we get

Ψ(u_{ξ}, u_{η}) = \frac{\sqrt{2}}{2}(|u_{x} + u_{y}| + |u_{y} − u_{x}|) ≠ |u_{x}| + |u_{y}| = Ψ(u_{x}, u_{y})

Thus Ψ(u_{x}, u_{y}) = |u_{x}| + |u_{y}| is not rotaionally invariant. b. Ψ(u_{x}, u_{y}) = u_{x}^{2} + u_{y}^{2}.

It follows Ψ(u_{ξ}, u_{η}) = u_{ξ}^{2} + u_{η}^{2}. Using again the hint, we get for u_{ξ} and u_{η} the same as above.

⇒ Ψ(u_{ξ}, u_{η}) = (u_{x} · cos ϑ + u_{y} · sin ϑ)^{2} + (u_{y} · cos ϑ − u_{x} sin ϑ)^{2}
= u_{x}^{2} cos^{2} ϑ + 2u_{x}u_{y} cos ϑ sin ϑ + u_{y}^{2} sin^{2} ϑ
+u_{y}^{2} cos^{2} ϑ − 2u_{x}u_{y} cos ϑ sin ϑ + u_{x}^{2} sin^{2} ϑ
= u_{x}^{2}(\underbrace{cos^{2} ϑ + sin^{2} ϑ}_{=1}) + u_{y}^{2}(\underbrace{cos^{2} ϑ + sin^{2} ϑ}_{=1})
= u_{x}^{2} + u_{y}^{2} = Ψ(u_{x}, u_{y})

Thus Ψ(u_{x}, u_{y}) = u_{x}^{2} + u_{y}^{2} is rotationally invariant.

4.3 Discrete Energy Minimisation

E_{f}(u_{1}, ..., u_{N}) = ∑_{k=1}^{N}(u_{k} −f_{k})^{2} +α ∑_{k=1}^{N−1}(u_{k+1} −u_{k})^{2} +β ∑_{k=2}^{N−1}(u_{k+1} −2u_{k} +u_{k−1})^{2}

a. Setting \frac{∂E}{∂u_{i}} = 0 for i = 1, ..., N gives

0 = 2(u_{1} − f_{1}) − 2α(u_{2} − u_{1}) + 2β(u_{3} − 2u_{2} + u_{1})
= u_{1} − f_{1} − α(u_{2} − u_{1}) + β(u_{3} − 2u_{2} + u_{1})
0 = 2(u_{2} − f_{2}) − 2α(u_{3} − u_{2}) + 2α(u_{2} − u_{1}) + 2β(u_{4} − 2u_{3} + u_{2})

−4β(u_{3} − 2u_{2} + u_{1})

= u_{2} − f_{2} − α(u_{3} − u_{2}) + α(u_{2} − u_{1}) + β(u_{4} − 2u_{3} + u_{2})

−2β(u_{3} − 2u_{2} + u_{1})

0 = 2(u_{i} − f_{i}) − 2α(u_{i+1} − u_{i}) + 2α(u_{i} − u_{i−1})

+2β(u_{i+2} − 2u_{i+1} + u_{i}) − 4β(u_{i+1} − 2u_{i} + u_{i−1}) +2β(u_{i} − 2u_{i−1} + u_{i−2}) (i = 3, ..., N − 2)

= (u_{i} − f_{i}) − α(u_{i+1} − u_{i}) + α(u_{i} − u_{i−1})

+β(u_{i+2} − 2u_{i+1} + u_{i}) − 2β(u_{i+1} − 2u_{i} + u_{i−1}) +β(u_{i} − 2u_{i−1} + u_{i−2}) (i = 3, ..., N − 2)

0 = 2(u_{N−1} − f_{N−1}) − 2α(u_{N} − u_{N−1}) + 2α(u_{N−1} − u_{N−2})
−4β(u_{N} − 2u_{N−1} + u_{N−2}) + 2β(u_{N−1} − 2u_{N−2} + u_{N−3})
= u_{N−1} − f_{N−1} − α(u_{N} − u_{N−1}) + α(u_{N−1} − u_{N−2})
−2β(u_{N} − 2u_{N−1} + u_{N−2}) + β(u_{N−1} − 2u_{N−2} + u_{N−3})
0 = 2(u_{N} − f_{N}) + 2α(u_{N} − u_{N−1}) − 2β(u_{N} − 2u_{N−1} + u_{N−2})
= u_{N} − f_{N} + α(u_{N} − u_{N−1}) − β(u_{N} − 2u_{N−1} + u_{N−2})

b. I would say that the terms where a β stands in front of are the discretisations of the fourth order derivatives. If you combine these terms to one term you get a structure where u_{i+2}, u_{i+1}, u_{i}, u_{i−1}, u_{i−2} are involved, so this is not a second order but a fourth order derivative.

4.4 Half-Quadratic Regularisation

E_{f}(u) = ∫_{Ω} ((u − f)^{2} + α2λ^{2} (1 − exp (−\frac{|∇u|^{2}}{2λ^{2}} ))) dx

I can rewrite this into

E_{f}(u) = ∫_{Ω} ((u − f)^{2} + αΨ (|∇u|^{2})) dx

with

Ψ(|∇u|^{2}) = 2λ^{2} (1 − exp (−\frac{|∇u|^{2}}{2λ^{2}} ))

F = (u − f)^{2} + αΨ (|∇u|^{2})
F_{u} = 2(u − f)
F_{u_{x_{1}}} = 2αλ^{2} (− exp (−\frac{|∇u|^{2}}{2λ^{2}} )) · (−2u_{x_{1}}/2λ^{2})
= 2αu_{x_{1}} exp (−\frac{|∇u|^{2}}{2λ^{2}} )
F_{u_{x_{2}}} = 2αλ^{2} (− exp (−\frac{|∇u|^{2}}{2λ^{2}} )) · (−2u_{x_{2}}/2λ^{2})
= 2αu_{x_{2}} exp (−\frac{|∇u|^{2}}{2λ^{2}} )

Its Euler-Lagrange equation is given by (divided by 2)

0 = (u − f) − α · div (\underbrace{exp (−\frac{|∇u|^{2}}{2λ^{2}} )}_{Ψ′(|∇u|^{2})} ∇u)

Let’s formulate the energy functional for the Half-Quadratic case:

E_{HQ}(u, v) := ∫_{Ω} ((u − f)^{2} + α(v · |∇u|^{2} + η(v))) dx

E_{HQ}(u, v) has the two Euler-Lagrange equations:

0 = (u − f) − α div(v∇u)
0 = |∇u|^{2} + η′(v)

We know that

v := Ψ′(|∇u|^{2}) = exp (−\frac{|∇u|^{2}}{2λ^{2}} )

To obtain |∇u|^{2}, let’s solve v for |∇u|^{2}:

v = exp (−\frac{|∇u|^{2}}{2λ^{2}} )
log(v) = −\frac{|∇u|^{2}}{2λ^{2}}
|∇u|^{2} = − log(v) · 2λ^{2}
= −2λ^{2} · log(v)

Then we can rewrite the Euler-Lagrange equations

0 = (u − f) − α div(v∇u)
0 = |∇u|^{2} \underbrace{−2λ^{2} log(v)}_{=η′(v)}

We know that η′(v) = −2λ^{2} log(v) and thus

η(v) = −2λ^{2}v(log(v) − 1)

This gives

E_{HQ}(u, v) := ∫_{Ω} ((u − f)^{2} + α(v|∇u|^{2} − 2λ^{2}v(log(v) − 1))) dx