Differential Equations in Image Processing and Computer Vision

Assignment T1

Jan Hendrik Dithmar

2031259

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

Assignment T1  Dithmar (2031259)

1.1 Convolution, Derivatives and Diffusion Equation

a.

(f ∗ g′)(x) = ∫_{ℝ^{2}} f(y)(g(x − y))_{x}dy  (1)
(f ∗ g)′(x) = ∫_{ℝ^{2}}(f(y)g(x − y))_{x}dy
= ∫_{ℝ^{2}} [ \underbrace{(f(y))_{x}}_{=0} g(x − y) + f(y)(g(x − y))_{x}]dy
(f ∗ g)′(x) = ∫_{ℝ^{2}} f(y)(g(x − y))_{x}dy = (f ∗ g′)(x) (2)
(f ∗ g)′(x) =^{Comm.} (g ∗ f)′(x)
=^{(2)} (g ∗ f′)(x)
=^{Comm.} (f′ ∗ g)(x)
□

b.

u(x, t) =^{!} K\sqrt{2t}(x)
u_{t} = u_{xx} x ∈ ℝ, t > 0

We know from the lecture that

K_{σ}(x) = \frac{1}{σ\sqrt{2π}} · exp (−\frac{x^{2}}{2σ^{2}} )
⇒ K\sqrt{2t}(x) = \frac{1}{2\sqrt{πt}} · exp (−\frac{x^{2}}{4t} )

I calculate the derivatives u_{t} and u_{xx} and check whether they are equal.

u_{t} = \frac{−\frac{1}{2}π}{2(πt)^{3/2}} exp (−\frac{x^{2}}{4t} ) + \frac{1}{2\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) \frac{x^{2}}{4t^{2}}
= −\frac{π}{4(πt)^{3/2}} exp (−\frac{x^{2}}{4t} ) + \frac{x^{2}}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
= −\frac{π}{4\sqrt{πt}πt} exp (−\frac{x^{2}}{4t} ) + \frac{x^{2}}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
= −\frac{2t}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) + \frac{x^{2}}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
u_{t} = \frac{x^{2} − 2t}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )

u_{x} = \frac{1}{2\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) \frac{−2x}{4t} = −\frac{x}{4t\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
u_{xx} = −\frac{1}{4t\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) − \frac{x}{4t\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) (−\frac{x}{2t})
= −\frac{1}{4t\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) − \frac{x^{2}}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
= −\frac{2t}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} ) + \frac{x^{2}}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
u_{xx} = \frac{x^{2} − 2t}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )

One can easily see that u_{t} = u_{xx} which means that u(x, t) = K\sqrt{2t}(x) is a solution. □

c. In this case u(x, t) = (K\sqrt{2t} ∗ f)(x). One can easily show that u(x, t = 0) = f(x) by using the given assumption:

u(x, t = 0) = (K_{0} ∗ f)(x) =^{Ass.} f(x) ✓

Now, one only has to show that u_{t} = u_{xx}.

u_{t} = ((K\sqrt{2t} ∗ f)(x))_{t}
⇔^{(a)} u_{t} = ((K\sqrt{2t})_{t} ∗ f)(x)
u_{xx} = ((K\sqrt{2t} ∗ f)(x))_{xx}
⇔^{(a)} u_{xx} = ((K\sqrt{2t})_{xx} ∗ f)(x)

Since we know from part b., that

(K\sqrt{2t})_{t} = \frac{x^{2} − 2t}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
(K\sqrt{2t})_{x} = −\frac{x}{4t\sqrt{πt}} exp (−\frac{x^{2}}{4t} )
(K\sqrt{2t})_{xx} = \frac{x^{2} − 2t}{8t^{2}\sqrt{πt}} exp (−\frac{x^{2}}{4t} )

we see that (K\sqrt{2t})_{t} and (K\sqrt{2t})_{xx} are the same. Since (K\sqrt{2t})_{t} and (K\sqrt{2t})_{xx} are the same, the terms ((K\sqrt{2t})_{t} ∗ f)(x) = ((K\sqrt{2t} ∗ f)(x))_{t} and ((K\sqrt{2t})_{xx} ∗ f)(x) = ((K\sqrt{2t} ∗ f)(x))_{xx} are the same for any given bounded continuous funtion f. □

1.2 Numerical Differentiation

We want to approximate f′′ with f_{i−2}, f_{i−1}, f_{i}, f_{i+1}, f_{i+2}. Doing a Taylor expansion results in the following:

f_{i−2} = f_{i} − 2hf′_{i} + 2h^{2}f′′_{i} − \frac{4}{3}h^{3}f′′′_{i} + \frac{2}{3}h^{4}f_{i}^{(4)} − \frac{4}{15}h^{5}f_{i}^{(5)} + O(h^{6})
f_{i−1} = f_{i} − hf′_{i} + \frac{1}{2}h^{2}f′′_{i} − \frac{1}{6}h^{3}f′′′_{i} + \frac{1}{24}h^{4}f_{i}^{(4)} − \frac{1}{120}h^{5}f_{i}^{(5)} + O(h^{6})
f_{i} = f_{i}
f_{i+1} = f_{i} + hf′_{i} + \frac{1}{2}h^{2}f′′_{i} + \frac{1}{6}h^{3}f′′′_{i} + \frac{1}{24}h^{4}f_{i}^{(4)} + \frac{1}{120}h^{5}f_{i}^{(5)} + O(h^{6})
f_{i+2} = f_{i} + 2hf′_{i} + 2h^{2}f′′_{i} + \frac{4}{3}h^{3}f′′′_{i} + \frac{2}{3}h^{4}f_{i}^{(4)} + \frac{4}{15}h^{5}f_{i}^{(5)} + O(h^{6})

Comparing the coefficients:

0·f_{i}+0·f′_{i}+1·f′′_{i}+0·f′′′_{i}+0·f_{i}^{(4)} =^{!} α_{−2}f_{i−2}+α_{−1}f_{i−1}+α_{0}f_{i}+α_{1}f_{i+1}+α_{2}f_{i+2}

f′′_{i} = (α_{−2} + α_{−1} + α_{0} + α_{1} + α_{2})f_{i}

+(−2hα_{−2} − hα_{−1} + hα_{1} + 2hα_{2})f′_{i}

+ (2h^{2}α_{−2} + \frac{1}{2}h^{2}α_{−1} + \frac{1}{2}h^{2}α_{1} + 2h^{2}α_{2}) f′′_{i}

+ (−\frac{4}{3}h^{3}α_{−2} − \frac{1}{6}h^{3}α_{−1} + \frac{1}{6}h^{3}α_{1} + \frac{4}{3}h^{3}α_{2}) f′′′_{i}

+ (\frac{2}{3}h^{4}α_{−2} + \frac{1}{24}h^{4}α_{−1} + \frac{1}{24}h^{4}α_{1} + \frac{2}{3}h^{4}α_{2}) f_{i}^{(4)} + O(h^{5})

This gives the following system of equations:

( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ −2h & −h & 0 & h & 2h \\ 2h^{2} & \frac{1}{2}h^{2} & 0 & \frac{1}{2}h^{2} & 2h^{2} \\ −\frac{4}{3}h^{3} & −\frac{1}{6}h^{3} & 0 & \frac{1}{6}h^{3} & \frac{4}{3}h^{3} \\ \frac{2}{3}h^{4} & \frac{1}{24}h^{4} & 0 & \frac{1}{24}h^{4} & \frac{2}{3}h^{4} \end{matrix} ) ( \begin{matrix}α_{−2} \\ α_{−1} \\ α_{0} \\ α_{1} \\ α_{2} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix} )

( \begin{matrix}1 & 1 & 1 & 1 & 1 \\ −2 & −1 & 0 & 1 & 2 \\ 4 & 1 & 0 & 1 & 4 \\ −8 & −1 & 0 & 1 & 8 \\ 16 & 1 & 0 & 1 & 16 \end{matrix} ) ( \begin{matrix}α_{−2} \\ α_{−1} \\ α_{0} \\ α_{1} \\ α_{2} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 2/h^{2} \\ 0 \\ 0 \end{matrix} )

Solving the equation system: (checked with Maple, everything’s fine *gg*)

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ −2 & −1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^{2} \\ −8 & −1 & 0 & 1 & 8 & 0 \\ 16 & 1 & 0 & 1 & 16 & 0 \end{matrix} ) +2 · IV

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ −2 & −1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^{2} \\ −8 & −1 & 0 & 1 & 8 & 0 \\ 0 & −1 & 0 & 3 & 32 & 0 \end{matrix} ) −4 · II

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ −2 & −1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^{2} \\ 0 & 3 & 0 & −3 & 0 & 0 \\ 0 & −1 & 0 & 3 & 32 & 0 \end{matrix} ) +\frac{1}{3} · IV; (: 2)

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ −2 & −1 & 0 & 1 & 2 & 0 \\ 4 & 1 & 0 & 1 & 4 & 2/h^{2} \\ 0 & 3 & 0 & −3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 6 & 0 \end{matrix} ) +2 · II

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ −2 & −1 & 0 & 1 & 2 & 0 \\ 0 & −1 & 0 & 3 & 8 & 2/h^{2} \\ 0 & 3 & 0 & −3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0 \end{matrix} ) +\frac{1}{3} · IV; (: 2)

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ −2 & −1 & 0 & 1 & 2 & 0 \\ 0 & 0 & 0 & 1 & 4 & 1/h^{2} \\ 0 & 3 & 0 & −3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0 \end{matrix} ) +2 · I

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 3 & 4 & 0 \\ 0 & 0 & 0 & 1 & 4 & 1/h^{2} \\ 0 & 3 & 0 & −3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0 \end{matrix} ) −V

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 3 & 4 & 0 \\ 0 & 0 & 0 & 0 & −12 & −1/h^{2} \\ 0 & 3 & 0 & −3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 16 & 0 \end{matrix} ) \begin{matrix}⇒ α_{−2} = −\frac{1}{12h^{2}} \\ ⇒ α_{0} = −\frac{5}{2h^{2}} \\ ⇒ α_{2} = −\frac{1}{12h^{2}} \\ ⇒ α_{−1} = \frac{4}{3h^{2}} \\ ⇒ α_{1} = \frac{4}{3h^{2}} \end{matrix}

Finally we get:

α_{−2} = α_{2} = −\frac{1}{12h^{2}}
α_{−1} = α_{1} = \frac{4}{3h^{2}}
α_{0} = −\frac{5}{2h^{2}}

Let’s plug that into

f′′_{i} = \underbrace{(α_{−2} + α_{−1} + α_{0} + α_{1} + α_{2})}_{=0} f_{i}

+ \underbrace{(−2hα_{−2} − hα_{−1} + hα_{1} + 2hα_{2})}_{=0} f′_{i}

+ \underbrace{(2h^{2}α_{−2} + \frac{1}{2}h^{2}α_{−1} + \frac{1}{2}h^{2}α_{1} + 2h^{2}α_{2})}_{=1} f′′_{i}

+ \underbrace{(−\frac{4}{3}h^{3}α_{−2} − \frac{1}{6}h^{3}α_{−1} + \frac{1}{6}h^{3}α_{1} + \frac{4}{3}h^{3}α_{2})}_{=0} f′′′_{i}

+ \underbrace{(\frac{2}{3}h^{4}α_{−2} + \frac{1}{24}h^{4}α_{−1} + \frac{1}{24}h^{4}α_{1} + \frac{2}{3}h^{4}α_{2})}_{=0} f_{i}^{(4)}

+ \underbrace{(−\frac{4}{15}h^{5}α_{−2} − \frac{1}{120}h^{5}α_{−1} + \frac{1}{120}h^{5}α_{1} + \frac{4}{15}h^{5}α_{2})}_{=0} f_{i}^{(5)}

+ \underbrace{(\frac{4}{45}h^{6}α_{−2} + \frac{1}{720}h^{6}α_{−1} + \frac{1}{720}h^{6}α_{1} + \frac{4}{45}h^{6}α_{2})}_{=− \frac{1}{90} h^{4}} f_{i}^{(6)} + O(h^{7})

f′′_{i} = f′′_{i} − \frac{1}{90}h^{4}f_{i}^{(6)} + O(h^{7})

It follows that the order of consistency is 4.