Image Processing and Computer

Vision

Assignment T3

Jan Hendrik Dithmar

2031259

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

Assignment T3  Dithmar (2031259)

3.1 Interpolation

a. We have

β_{5}(k) = \{ \begin{matrix}\frac{1}{120} & k = ±2 \\ \frac{13}{60} & k = ±1 \\ \frac{11}{20} & k = 0 \\ 0 & for other integer values k \end{matrix}

Now I state the equation system:

( \begin{matrix}\frac{11}{20} & \frac{13}{60} & \frac{1}{120} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ & ... & ... & ... & ... & ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{120} & \frac{13}{60} & \frac{11}{20} \end{matrix} )·( c_{1} ; c_{2} ; c_{3} ; ⋮ ; c_{N−2} ; c_{N−1} ; c_{N} ) = ( f_{1} ; f_{2} ; f_{3} ; ⋮ ; f_{N−2} ; f_{N−1} ; f_{N} )

b.

( \begin{matrix}\frac{2}{3} & \frac{1}{6} & 0 \\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \\ 0 & \frac{1}{6} & \frac{2}{3} \end{matrix} ) · ( \begin{matrix}c_{1} \\ c_{2} \\ c_{3} \end{matrix} ) = ( \begin{matrix}f_{1} \\ f_{2} \\ f_{3} \end{matrix} )

( \begin{matrix}\frac{2}{3} & \frac{1}{6} & 0 \\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \\ 0 & \frac{1}{6} & \frac{2}{3} \end{matrix} ) · ( \begin{matrix}c_{1} \\ c_{2} \\ c_{3} \end{matrix} ) = ( \begin{matrix}4 \\ 28 \\ 24 \end{matrix} )

( \begin{matrix}\frac{2}{3} · c_{1} & + & \frac{1}{6} · c_{2} \\ \frac{1}{6} · c_{1} & + & \frac{2}{3} · c_{2} & + & \frac{1}{6} · c_{3} \\ & & \frac{1}{6} · c_{2} & + & \frac{2}{3} · c_{3} \end{matrix} ) = ( \begin{matrix}4 \\ 28 \\ 24 \end{matrix} )

This results in three equations with three unknowns:

\frac{1}{6} · c_{2}  = 4 − \frac{2}{3} · c_{1}

\frac{1}{6} · c_{1} + \frac{2}{3} · c_{2} + \frac{1}{6} · c_{3} = 28

\frac{2}{3} · c_{3} = 24 − \frac{1}{6} · c_{2} = 24 − (4 − \frac{2}{3} · c_{1})

= 20 + \frac{2}{3} · c_{1}

Let’s use the second equation to get c_{1}:

\frac{1}{6} · c_{1} + \frac{2}{3} · 6 · (4 − \frac{2}{3} · c_{1}) + \frac{1}{6} · \frac{3}{2} · (20 + \frac{2}{3} · c_{1}) = 28

\frac{1}{6} · c_{1} + 16 − \frac{8}{3} · c_{1} + 5 + \frac{1}{6} · c_{1} = 28

−\frac{7}{3} · c_{1} + 21 = 28
−\frac{7}{3} = 7
c_{1} = −3

Now, one can use the third equation to get c_{3}:

\frac{2}{3} · c_{3} = 20 + \frac{2}{3} · c_{1}

\frac{2}{3} · c_{3} = 20 + \frac{2}{3} · (−3)

\frac{2}{3} · c_{3} = 20 − 2

\frac{2}{3} · c_{3} = 18
c_{3} = 27

And now, let’s compute c_{2}:

\frac{1}{6} · c_{2} = 4 − \frac{2}{3} · c_{1}

\frac{1}{6} · c_{2} = 4 + 2
c_{2} = 6 · 6
c_{2} = 36

Having the coefficients, I compute the interpolation values for the points \frac{1}{2} and \frac{3}{2}:

f(x) = ∑_{k∈ℤ}c_{k} · φ(x − k)
= ∑_{k∈ℤ}c_{k} · β_{3}(x − k)

f (\frac{1}{2}) = c_{1} · β_{3} (−\frac{1}{2}) + c_{2} · β_{3} (−\frac{3}{2}) + c_{3} · β_{3} (−\frac{5}{2})
= −3 · \frac{23}{48} + 36 · \frac{1}{48} + 27 · 0
= −\frac{11}{16}

f (\frac{3}{2}) = c_{1} · β_{3} (\frac{1}{2}) + c_{2} · β_{3} (−\frac{1}{2}) + c_{3} · β_{3} (−\frac{3}{2})
= −3 · \frac{23}{48} + 36 · \frac{23}{48} + 27 · \frac{1}{48}
= \frac{131}{8}

3.2 Multiple Choice

a. false Since you can compute the discrete Wavelet coefficients in optimal complexity and the Wavelet transform is separable, you would get simply a factor more per dimension, i.e. 2 · N ∈ O(N) for 2-D instead of 1 · N ∈ O(N) for 1-D.

b. true Since all letters have the same probability it does not matter which letter is at which position in the tree built by the Huffman coding and because this does not matter, it is some kind of arbitrary assigning of codes to letters.

c. true We have (7)_{2} = 00000111 and (8)_{2} = 00001000. Since the first 4 bits do not change you have the possibility to store these bits efficiently with bitplane coding while you cannot do this with runlength coding.

d. false Since we already know that cubic B-splines can be efficiently solved using the Thomas algorithm, the coefficients for the cubic B-splines require less computational effort, namely O(n) instead of O(n^{3}), where quadratic B-splines require O(n^{2}) > O(n).

e. true If the histogram equalisation function is known, one can do the ”backcalculation” which results in the original histogram.

f. false Using a lowpass and highpass filter subsequently results in a bandpass filtered image and not in the original image.

3.3 Linear Filters

a. • x-direction: Gaussian, approximated by \frac{1}{12} 1 2 1 ⇒ lowpass filter

• y-direction: scaled box filter \frac{1}{12} 1 1 1 ⇒ lowpass filter

b. x-direction and y-direction: difference between identity and lowpass filter ⇒ highpass filter

\frac{1}{12} -1 -2 -1 2 4 2 -1 -2 -1 = 0 0 0 0 1 0 0 0 0 − \frac{1}{12} 1 2 1 -2 8 -2 1 2 1

c. x-direction and y-direction: difference between two lowpass filters ⇒ bandpass filter

\frac{1}{256} -1 -4 -6 -4 -1 -4 0 8 0 -4 -6 8 28 8 -6 -4 0 8 0 -4 -1 -4 -6 -4 1 = \frac{1}{256} ( \begin{matrix}0 & 0 & 0 & 0 & 0 \\ 0 & 16 & 32 & 16 & 0 \\ 0 & 32 & 64 & 32 & 0 \\ 0 & 16 & 32 & 16 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} − \begin{matrix}1 & 4 & 6 & 4 & 1 \\ 4 & 16 & 24 & 16 & 4 \\ 6 & 24 & 36 & 24 & 6 \\ 4 & 16 & 24 & 16 & 4 \\ 1 & 4 & 6 & 4 & 1 \end{matrix} )