Differential Equations in Image Processing and Computer Vision

Assignment T6

Jan Hendrik Dithmar

2031259

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

1  2  3  4  ∑

Assignment T6  Dithmar (2031259)

6.1 Discretisation of Hyberbolic PDEs

a. • forward differences:

\frac{u_{i}^{k+1} − u_{i}^{k}}{τ} = a · \frac{u_{i+1}^{k} − u_{i}^{k}}{h}
⇔ u_{i}^{k+1} = aτ · \frac{u_{i+1}^{k} − u_{i}^{k}}{h} + u_{i}^{k}

• backward differences:

\frac{u_{i}^{k+1} − u_{i}^{k}}{τ} = a · \frac{u_{i}^{k} − u_{i−1}^{k}}{h}
⇔ u_{i}^{k+1} = aτ · \frac{u_{i}^{k} − u_{i−1}^{k}}{h} + u_{i}^{k}

• central differences:

\frac{u_{i}^{k+1} − u_{i}^{k}}{τ} = a · \frac{u_{i+1}^{k} − 2u_{i}^{k} + u_{i−1}^{k}}{2h}
⇔ u_{i}^{k+1} = aτ · \frac{u_{i+1}^{k} − 2u_{i}^{k} + u_{i−1}^{k}}{2h} + u_{i}^{k}

b. The results from above should now be represented as a convex combination.

• forward differences:

u_{i}^{k+1} = \frac{aτ}{h} u_{i+1}^{k} + (1 − \frac{aτ}{h} ) u_{i}^{k}

To fullfill one criterion of the convex combination \frac{aτ}{h} > 0 and since τ, h > 0 it must hold that a > 0. For the other part of the convex combination you see that

1 − \frac{aτ}{h} > 0
⇔ \frac{aτ}{h} < 1
⇔ a < \frac{h}{τ}

If 0 < a < \frac{h}{τ}, the max-min-stability holds.

• backward differences:

u_{i}^{k+1} = (1 + \frac{aτ}{h} ) u_{i}^{k} − \frac{aτ}{h} u_{i−1}^{k}

In this case, on the one hand side it must be fullfilled that −\frac{aτ}{h} > 0 ⇔ \frac{aτ}{h} < 0. On the other hand it must hold the following:

1 + \frac{aτ}{h} > 0
\frac{aτ}{h} > −1
a > −\frac{h}{τ}

If −\frac{h}{τ} < a < 0, the max-min-stability holds.

• central differences:

u_{i}^{k+1} = (1 − 2\frac{aτ}{h} ) u_{i}^{k} + \frac{aτ}{h} (u_{i+1}^{k} + u_{i−1}^{k})

In this case, \frac{aτ}{h} > 0 ⇔ a > 0. Furthermore

1 − 2\frac{aτ}{h} > 0
2\frac{aτ}{h} < 1
a < \frac{h}{2τ}

If 0 < a < \frac{h}{2τ}, the max-min-stability holds.

6.2 Slope Transform

We know that

S[f](u) := stat_{x}(f(x) − ux)

Since stat_{x}g(x) := g(x)|g′(x) = 0 we can plug this in:

S[f_{p}](u) = stat_{x}(f_{p}(x) − ux)
= {f_{p}(x) − ux | f′_{p}(x) − u = 0}
= {cx^{p} − ux | pcx^{p−1} − u = 0}
= \{x (cx^{p−1} − u) | x^{p−1} = \frac{u}{pc}\}
= \{x (\frac{u}{p} − u) | x = sgn(u) |\frac{u}{pc}|^{\frac{1}{p−1}} \}
= \{sgn(u) |\frac{u}{pc}|^{\frac{1}{p−1}} (\frac{u}{p} − u)\}
S[f_{p}](u) = \{sgn(u) |\frac{u}{pc}|^{\frac{1}{p−1}} \frac{u}{p}(1 − p)\}

For the case that p = 2 we get the following:

S[f_{2}](u) = {cx^{2} − ux | 2cx − u = 0}
= \{x(cx − u) | x = \frac{u}{2c}\}
= \{\frac{u}{2c} (\frac{u}{2} − u)\}
= \{−\frac{u^{2}}{4c}\}

In this case the slope transform remains a quadratic function. This shows the fact that parabolas remain parabolas (to be more precise ”paraboloids”) under the slope transform (Lecture 21, slide 13).

6.3 Curvature-Based Morphology

We know from Lecture 22, slide 3 that

∂_{t}u = Δu
= ∂_{xx}u + ∂_{yy}u (by the definition of Δ)
= ∂_{ηη}u + ∂_{ξξ}u (η ∥ ∇u, ξ ⊥ ∇u)
DIC  Page 3  SS 2008

We want with MCM a smoothing along isophotes, so ∂_{ηη}u vanishes, since this term smoothes across the edge. So it remains to show that

∂_{ξξ}u = \frac{u_{y}^{2}u_{xx} − 2u_{x}u_{y}u_{xy} + u_{x}^{2}u_{yy}}{u_{x}^{2} + u_{y}^{2}}  (1)
= Δu − \frac{1}{|∇u|^{2}} ∇u^{⊤}Hess(u)∇u (2)
= |∇u|div (\frac{∇u}{|∇u|})  (3)

Let’s show that (1) = (2):

Δu − \frac{1}{|∇u|^{2}} ∇u^{⊤}Hess(u)∇u

= u_{xx} + u_{yy} − \frac{1}{u_{x}^{2} + u_{y}^{2}} ∇u^{⊤}Hess(u)∇u
= u_{xx} + u_{yy} − \frac{1}{u_{x}^{2} + u_{y}^{2}} (u_{x}, u_{y}) ( \begin{matrix}u_{xx} & u_{xy} \\ u_{yx} & u_{yy} \end{matrix} ) ( \begin{matrix}u_{x} \\ u_{y} \end{matrix} )
= \frac{(u_{x}^{2} + u_{y}^{2})(u_{xx} + u_{yy})}{u_{x}^{2} + u_{y}^{2}} − \frac{1}{u_{x}^{2} + u_{y}^{2}} (u_{x}, u_{y}) ( \begin{matrix}u_{xx}u_{x} + u_{xy}u_{y} \\ u_{yx}u_{x} + u_{yy}u_{y} \end{matrix} )
= \frac{(u_{x}^{2} + u_{y}^{2})(u_{xx} + u_{yy})}{u_{x}^{2} + u_{y}^{2}} − \frac{1}{u_{x}^{2} + u_{y}^{2}} (u_{xx}u_{x}^{2} + u_{xy}u_{y}u_{x} + u_{yx}u_{x}u_{y} + u_{yy}u_{y}^{2})
= \frac{u_{x}^{2}u_{xx} + u_{x}^{2}u_{yy} + u_{y}^{2}u_{xx} + u_{y}^{2}u_{yy} − u_{xx}u_{x}^{2} − 2u_{x}u_{y}u_{xy} − u_{yy}u_{y}^{2}}{u_{x}^{2} + u_{y}^{2}}
= \frac{u_{y}^{2}u_{xx} − 2u_{x}u_{y}u_{xy} + u_{x}^{2}u_{yy}}{u_{x}^{2} + u_{y}^{2}}

Let’s show that (1) = (3):

|∇u|div (\frac{∇u}{|∇u|})

= \sqrt{u_{x}^{2} + u_{y}^{2}} (∂_{x} \frac{u_{x}}{\sqrt{u_{x}^{2} + u_{y}^{2}}} + ∂_{y} \frac{u_{y}}{\sqrt{u_{x}^{2} + u_{y}^{2}}} )
= \sqrt{u_{x}^{2} + u_{y}^{2}} (\frac{u_{xx}\sqrt{u_{x}^{2} + u_{y}^{2}} − u_{x} \frac{1}{2\sqrt{u_{x}^{2}+u_{y}^{2}}} (2u_{x}u_{xx} + 2u_{y}u_{yx})}{u_{x}^{2} + u_{y}^{2}}

+ \frac{u_{yy}\sqrt{u_{x}^{2} + u_{y}^{2}} − u_{y} \frac{1}{2\sqrt{u_{x}^{2}+u_{y}^{2}}} (2u_{x}u_{yx} + 2u_{y}u_{yy})}{u_{x}^{2} + u_{y}^{2}} )

= \frac{u_{xx}(u_{x}^{2} + u_{y}^{2}) − u_{x}(u_{x}u_{xx} + u_{y}u_{yx})}{u_{x}^{2} + u_{y}^{2}} + \frac{u_{yy}(u_{x}^{2} + u_{y}^{2}) − u_{y}(u_{x}u_{yx} + u_{y}u_{yy})}{u_{x}^{2} + u_{y}^{2}}
= \frac{u_{xx}u_{x}^{2} + u_{xx}u_{y}^{2} − u_{x}^{2}u_{xx} − u_{x}u_{y}u_{xy} + u_{yy}u_{x}^{2} + u_{yy}u_{y}^{2} − u_{x}u_{y}u_{xy} − u_{y}^{2}u_{yy}}{u_{x}^{2} + u_{y}^{2}}
= \frac{u_{y}^{2}u_{xx} − 2u_{x}u_{y}u_{xy} + u_{x}^{2}u_{yy}}{u_{x}^{2} + u_{y}^{2}}

6.4 Multiple Choice

a. NO b. NO c. NO d. NO