Image Processing and Computer

Vision

Assignment T5

Jan Hendrik Dithmar

2031259

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

Assignment T5  Dithmar (2031259)

5.1 Derivative Filters

a. The equation system looks as follows:

f_{i−2} = f_{i} − 2hf′_{i} + 4\frac{h^{2}}{2} f′′_{i} − 8\frac{h^{3}}{6} f′′′_{i} + 16\frac{h^{4}}{24}f′′′′_{i} + O(h^{5})
= f_{i} − 2hf_{i} + 2h^{2}f′_{i} − \frac{4}{3}h^{3}f′′′_{i} + \frac{2}{3}h^{4}f′′′′_{i} + O(h^{5})
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} + O(h^{5})
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} + O(h^{5})
f_{i+2} = f_{i} + 2hf′_{i} + 4\frac{h^{2}}{2} f′′_{i} + 8\frac{h^{3}}{6} f′′′_{i} + 16\frac{h^{4}}{24}f′′′′_{i} + O(h^{5})
= f_{i} + 2hf_{i} + 2h^{2}f′_{i} + \frac{4}{3}h^{3}f′′′_{i} + \frac{2}{3}h^{4}f′′′′_{i} + O(h^{5})

⇒ 0 · f_{i} + 1 · f′_{i} + 0 · f′′_{i} = α_{−2}f_{i−2} + α_{−1}f_{i−1} + α_{0}f_{i} + α_{1}f_{i+1} + α_{2}f_{i+2} If you rewrite this, you get 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} + O(h^{5}))

+α_{−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} + O(h^{5}))

+α_{0} · 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} + O(h^{5}))

+α_{2} · (f_{i} + 2hf′_{i} + 2h^{2}f′′_{i} + \frac{4}{3}h^{3}f′′′_{i} + \frac{2}{3}h^{4}f′′′′_{i} + O(h^{5}))

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

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

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

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

This leads to the linear system of equations:

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

b. As in the script, I extend the Taylor expansion by one degree:

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} − \frac{4}{15}h^{5}f′′′′′_{i} + 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} − \frac{1}{120}h^{5}f′′′′′_{i} + 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} + \frac{1}{120}h^{5}f′′′′′_{i} + 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} + \frac{4}{15}h^{5}f′′′′′_{i} + O(h^{6})

Using the filter mask, one gets:

f′_{i} = \frac{1}{12h} [(1 − 8 + 8 − 1)f_{i} + (−2 + 8 + 8 − 2)hf′_{i}

+ (2 − 4 + 4 − 2)h^{2}f′′_{i}

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

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

+ (−\frac{4}{15} + \frac{1}{15} + \frac{1}{15} − \frac{4}{15}) h^{5}f′′′′′_{i}

+ O(h^{6})]

= \frac{1}{12h} [12hf′_{i} − \frac{2}{5}h^{5}f′′′′′_{i} + O(h^{6})]
f′_{i} = f′_{i} − \frac{1}{30}h^{4}f′′′′′_{i} + O(h^{5})

The order of consistency for this approximation is 4. c. If I want to approximate a derivative of order d with n points, it must

be that n > d.

IPCV  Page 2  WS 2007/2008

For a value j, where j ≠ d and j < n, all the coefficients in front of h^{j}f_{i}^{(j)} are 0 (this is also the case in part b.). What remains is h^{d}f_{i}^{(d)} and h^{n}f_{i}^{(n)} with their respective coefficients. The order of consistency is therefore n − d. If you compare this statement with my solution of part b., you see that it is true, since we have order of consistency n − d = 5 − 1 = 4.

5.2 Hough Transform

a. First of all, I have to state the five trigonometric curves which belong to the five points given.

1. (−1, 1): d = − cos ϕ + sin ϕ

2. (2, 0): d = 2 · cos ϕ

3. (3, 1): d = 3 · cos ϕ + sin ϕ

4. (1, 3): d = cos ϕ + 3 · cos ϕ

5. (0, 2): d = 2 · sin ϕ

Now I try to find the points which are on a line by using equality:

1. = 2.:

− cos ϕ + sin ϕ = 2 · cos ϕ
sin ϕ = 3 · cos ϕ

1. = 3.:

− cos ϕ + sin ϕ = 3 · cos ϕ + sin ϕ
4 · cos ϕ = 0

1. = 4.:

− cos ϕ + sin ϕ = cos ϕ + 3 · sin ϕ
− cos ϕ = sin ϕ

1. = 5.:

− cos ϕ + sin ϕ = 2 · sin ϕ
− cos ϕ = sin ϕ

It follows that the points (−1, 1), (1, 3) and (0, 2) belong to the same line. b. The equation for a circle looks like this:

|x − a|^{2} + |y − b|^{2} − r^{2} = 0

where (a, b) is the center and r the radius of the circle. For this exercise, we have r = 2 ⇒ r^{2} = 4. I will now look at the different points:

1. (−1, 1): |x + 1|^{2} + |y − 1|^{2} = 4

2. (2, 0): |x − 2|^{2} + |y − 0|^{2} = 4

3. (3, 1): |x − 3|^{2} + |y − 1|^{2} = 4

4. (1, 3): |x − 1|^{2} + |y − 3|^{2} = 4

5. (0, 2): |x − 0|^{2} + |y − 2|^{2} = 4 As one can easily see, the points 1, 3 and 4 belong to the same circle with radius 2 and the center point (1, 1).

5.3 Cooccurrence Matrices

Since d = (−1, −1)^{⊤}, we have to look at the upper left neighbor.

P[i,j]

\frac{1}{30}× 1 2 1 1 0 i
2 5 1 1 1
2 2 3 2 2
1 2 2 2 3
0 1 2 3

j