Differential Equations in Image Processing and Computer Vision

Assignment T3

Jan Hendrik Dithmar

2031259

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

Assignment T3  Dithmar (2031259)

3.1 Discretisation of Anisotropic Nonlinear Diffusion

a. • using forward differences for ∂_{y} and ∂_{x}:

∂_{x} ≈ \frac{u_{i+1} − u_{i}}{2h_{1}}
∂_{y} ≈ \frac{1}{2h_{2}} (b_{i,j+1} \frac{u_{i+1,j+1} − u_{i,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i+1,j} − u_{i,j}}{2h_{1}} )

• using backward differences for ∂_{y} and ∂_{x}:

∂_{x} ≈ \frac{u_{i} − u_{i−1}}{2h_{1}}
∂_{y} ≈ \frac{1}{2h_{2}} (b_{i,j} \frac{u_{i,j} − u_{i−1,j}}{2h_{1}} − b_{i,j−1} \frac{u_{i,j−1} − u_{i−1,j−1}}{2h_{1}} )

• averaging both results:

\frac{1}{2} [\frac{1}{2h_{2}} (b_{i,j+1} \frac{u_{i+1,j+1} − u_{i,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i+1,j} − u_{i,j}}{2h_{1}} )

+\frac{1}{2h_{2}} (b_{i,j} \frac{u_{i,j} − u_{i−1,j}}{2h_{1}} − b_{i,j−1} \frac{u_{i,j−1} − u_{i−1,j−1}}{2h_{1}} )]

= \frac{1}{4h_{2}} (b_{i,j+1} \frac{u_{i+1,j+1} − u_{i,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i+1,j} − 2u_{i,j} + u_{i−1,j}}{2h_{1}}

−b_{i,j−1} \frac{u_{i,j−1} − u_{i−1,j−1}}{2h_{1}} )

b. • using forward differences for ∂_{y} and backward differences for ∂_{x}:

∂_{x} ≈ \frac{u_{i} − u_{i−1}}{2h_{1}}
∂_{y} ≈ \frac{1}{2h_{2}} (b_{i,j+1} \frac{u_{i,j+1} − u_{i−1,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i,j} − u_{i−1,j}}{2h_{1}} )

• using backward differences for ∂_{y} and forward differences for ∂_{x}:

∂_{x} ≈ \frac{u_{i+1} − u_{i}}{2h_{1}}
∂_{y} ≈ \frac{1}{2h_{2}} (b_{i,j} \frac{u_{i+1,j} − u_{i,j}}{2h_{1}} − b_{i,j−1} \frac{u_{i+1,j−1} − u_{i,j−1}}{2h_{1}} )

• averaging both results:

\frac{1}{2} [\frac{1}{2h_{2}} (b_{i,j+1} \frac{u_{i,j+1} − u_{i−1,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i,j} − u_{i−1,j}}{2h_{1}} )

+\frac{1}{2h_{2}} (b_{i,j} \frac{u_{i+1,j} − u_{i,j}}{2h_{1}} − b_{i,j−1} \frac{u_{i+1,j−1} − u_{i,j−1}}{2h_{1}} )]

= \frac{1}{4h_{2}} (b_{i,j+1} \frac{u_{i,j+1} − u_{i−1,j+1}}{2h_{1}} + b_{i,j} \frac{u_{i+1,j} − 2u_{i,j} + u_{i−1,j}}{2h_{1}}

−b_{i,j−1} \frac{u_{i+1,j−1} − u_{i,j−1}}{2h_{1}} )

c. approximating the term ∂_{x}(b∂_{y}u) + ∂_{y}(b∂_{x}u) in the following way:

• using forward differences for ∂_{y} and ∂_{x}:

∂_{x}(b∂_{y}u) + ∂_{y}(b∂_{x}u)

≈ \frac{1}{2h_{1}} (b_{i+1,j} \frac{u_{i+1,j+1} − u_{i+1,j}}{2h_{2}} − b_{i,j} \frac{u_{i,j+1} − u_{i,j}}{2h_{2}} )

+\frac{1}{2h_{2}} (b_{i,j+1} \frac{u_{i+1,j+1} − u_{i,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i+1,j} − u_{i,j}}{2h_{1}} ) =: C_{a}

• using backward differences for ∂_{y} and ∂_{x}:

∂_{x}(b∂_{y}u) + ∂_{y}(b∂_{x}u)

≈ \frac{1}{2h_{1}} (b_{i,j} \frac{u_{i,j} − u_{i,j−1}}{2h_{2}} − b_{i−1,j} \frac{u_{i−1,j} − u_{i−1,j−1}}{2h_{2}} )

+\frac{1}{2h_{2}} (b_{i,j} \frac{u_{i,j} − u_{i−1,j}}{2h_{1}} − b_{i,j−1} \frac{u_{i,j−1} − u_{i−1,j−1}}{2h_{1}} ) =: C_{b}

• averaging both results:

\frac{1}{2}(C_{a} + C_{b})

• using forward differences for ∂_{y} and backward differences for ∂_{x}:

∂_{x}(b∂_{y}u) + ∂_{y}(b∂_{x}u)

≈ \frac{1}{2h_{1}} (b_{i,j} \frac{u_{i,j+1} − u_{i,j}}{2h_{2}} − b_{i−1,j} \frac{u_{i−1,j+1} − u_{i−1,j}}{2h_{2}} )

+\frac{1}{2h_{2}} (b_{i,j+1} \frac{u_{i,j+1} − u_{i−1,j+1}}{2h_{1}} − b_{i,j} \frac{u_{i,j} − u_{i−1,j}}{2h_{1}} ) =: C_{c}

• using backward differences for ∂_{y} and forward differences for ∂_{x}:

∂_{x}(b∂_{y}u) + ∂(b∂_{x}u)

≈ \frac{1}{2h_{1}} (b_{i+1,j} \frac{u_{i+1,j} − u_{i+1,j−1}}{2h_{2}} − b_{i,j} \frac{u_{i,j} − u_{i,j−1}}{2h_{2}} )

+\frac{1}{2h_{2}} (b_{i,j} \frac{u_{i+1,j} − u_{i,j}}{2h_{1}} − b_{i,j−1} \frac{u_{i+1,j−1} − u_{i,j−1}}{2h_{1}} ) =: C_{d}

• averaging both results:

\frac{1}{2}(C_{c} + C_{d})

3.2 Discretisation of Anisotropic Nonlinear Diffusion

If I can find a condition number that is greater than the ”magic number” presented in Lecture 8, slide 11, I have a situation where the ”nonnegativity” criterion is violated. This is the case if the ratio between the eigenvalues is greater than 5.8284, especially for the following diffusion tensor:

( \begin{matrix}1 & 5 \\ 5 & 8 \end{matrix} )

where the eigenvalues are

\frac{9}{2} ± \frac{1}{2}\sqrt{149}.

This can also happen if we have a diagonally dominant diffusion tensor. An example would be the following tensor:

( \begin{matrix}30 & 5 \\ 5 & 30 \end{matrix} )

where the eigenvalues are here 25 and 35.

3.3 Stopping Time Selection: Decorrelation Criterion

We have to smooth the signal

(3, 5, 3, 5, −5, −3, −5, −3)

with

(0.25, 0.5, 0.25).

The convention for the following calculations is that f denotes the ”old” signal and g denotes the ”new” signal.

1. iteration: (3.5, 4, 4, 2, −2, −4, −4, −3.5)

f̄ = \frac{1}{8}(3 + 5 + 3 + 5 − 5 − 3 − 5 − 3) = 0
ḡ = \frac{1}{8}(3.5 + 4 + 4 + 2 − 2 − 4 − 4 − 3.5) = 0
var(f) = \frac{1}{8} · 136 = 17
var(g) = \frac{1}{8} · 96.5 = 12.0625
cov(f, g) = \frac{1}{8} · 105 = 13.125
corr(f, g) = \frac{13.125}{\sqrt{17} · \sqrt{12.0625}} ≈ 0.9165501

2. iteration: (3.625, 3.875, 3.5, 1.5, −1.5, −3.5, −3.875, −3.625)

f̄ now equals ḡ of the previous iteration.

f̄ = 0
ḡ = 0
var(f) = 12.0625
var(g) = \frac{1}{8} · 85.3125 = 10.6640625
cov(f, g) = \frac{1}{8} · 90.375 = 11.296875
corr(f, g) = \frac{11.296875}{\sqrt{12.0625} · \sqrt{10.6640625}} ≈ 0.9960435

Since this value is already larger than the correlation coefficient from the first iteration we can stop the process here.

3.4 Convex Functionals and Forward Diffusion

According to Lecture 4, slide 6, we have to ensure that

Φ′(u_{x}) = (Ψ′(u_{x}^{2})u_{x})′ > 0

to get forward diffusion.

(Ψ′(u_{x}^{2})u_{x})′ = Ψ′′(u_{x}^{2}) · 2u_{x} · u_{x} + Ψ′(u_{x}^{2})
= 2Ψ′′(u_{x}^{2})u_{x}^{2} + Ψ′(u_{x}^{2})

Let’s see whether we have forward diffusion or not:

\underbrace{2 \underbrace{Ψ′′(u_{x}^{2})}_{≥0} u_{x}^{2}}_{≥0} + \underbrace{Ψ′(u_{x}^{2})}_{>0} > 0

We know from the problem text that Ψ′′(u_{x}^{2}) ≥ 0. This means that the whole term 2Ψ′′(u_{x}^{2})u_{x}^{2} ≥ 0. From Lecture 10, slide 4, we know the assumption that Ψ′(u_{x}^{2}) > 0.