Solutions to exercises week 6

INF2310, spring 2017

Task 1

$w = \left[ \begin{array}{ccc} 1 & 2 & 1 \end{array} \right]$

and

$f = \left[ \begin{array}{ccccc} 1 & 3 & 4 & 3 & 4 \end{array} \right].$

a)

$f \stackrel{\text{full}}{\ast} w = \left[ \begin{array}{ccccccc} 1 & 5 & 11 & 14 & 14 & 11 & 4 \end{array} \right].$

b)

$f \stackrel{\text{valid}}{\ast} w = \left[ \begin{array}{ccc} 11 & 14 & 14 \end{array} \right].$

c)

$f \stackrel{\text{same}}{\ast} w = \left[ \begin{array}{ccccc} 5 & 11 & 14 & 14 & 11 \end{array} \right].$

Task 2

$w = \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right]$

and

$f = \left[ \begin{array}{cccc} 2 & 5 & 3 & 1 \\ 0 & 2 & 3 & 3 \\ 0 & 7 & 6 & 3 \\ 6 & 0 & 6 & 5 \end{array} \right].$

a)

$f \stackrel{\text{full}}{\ast} w = \left[ \begin{array}{cccccc} 2 & 7 & 10 & 9 & 4 & 1 \\ 2 & 9 & 15 & 17 & 10 & 4 \\ 2 & 16 & 28 & 33 & 19 & 7 \\ 6 & 15 & 30 & 35 & 26 & 11 \\ 6 & 13 & 25 & 27 & 20 & 8 \\ 6 & 6 & 12 & 11 & 11 & 5 \end{array} \right].$

b)

$f \stackrel{\text{valid}}{\ast} w = \left[ \begin{array}{cc} 28 & 33 \\ 30 & 35 \end{array} \right].$

c)

$f \stackrel{\text{same}}{\ast} w = \left[ \begin{array}{cccc} 9 & 15 & 17 & 10 \\ 16 & 28 & 33 & 19 \\ 15 & 30 & 35 & 26 \\ 13 & 25 & 27 & 20 \\ \end{array} \right].$

Task 3

Let $f$ be the input image and $w$ the mean value filter.

a)

Since the convolution operation is associative, $w \ast (w \ast f) = (w \ast w) \ast f$ . This means that the convolution with $w \ast w$ will produce the same result as two sequential convolutions with $$w$.

$w \ast w = \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] \ast \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] = \frac{1}{81} \left[ \begin{array}{ccccc} 1 & 2 & 3 & 2 & 1 \\ 2 & 4 & 6 & 4 & 2 \\ 3 & 6 & 9 & 6 & 3 \\ 2 & 4 & 6 & 4 & 2 \\ 1 & 2 & 3 & 2 & 1 \end{array} \right].$

b)

Yes, the convolution operator is associative and commutative, so the filter can be separated.

$\begin{aligned} w \ast w = \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] \ast \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] &= \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \\ &= \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \\ &= \frac{1}{9} \left[ \begin{array}{c} 1 \\ 2 \\ 3 \\ 2 \\ 1 \end{array} \right] \ast \frac{1}{9} \left[ \begin{array}{ccccc} 1 & 2 & 3 & 2 & 1 \end{array} \right]. \end{aligned}$

c)

A combination of separable filters is not generally separable. E.g. is the sum of the two filters

$w_1 = \left[ \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{array} \right]$

and

$w_2 = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{array} \right]$

not separable.

d)

The result of a convolution of two separable filters is allways separable.

Task 4

One advantage with symmetrical padding is that the padded image will have a smooth transition between the original boundary and the padded region. In addition will a neighbourhood at the boundary contain the same pixel values at both side of the boundary. With this, we have not introduced additional pixel values, or another local distribution of pixels.

One disadvantage with circular padding is that we can introduce sharp intensity edges in the transition between the original image and the padded region. This happens whenever the opposite boundaries have very different pixel intensities.

PS: Later in the course we will see that circular padding is implicit in the Fourier transform of the filtering. Since this is often not desirable, we will learn ways to mitigate this problem.

Task 5

Input image

$f = \left[ \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right].$

a)

$3\times 3$ median filter:

$g = \left[ \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right].$

This result is bad.

b)

$1\times 3$ median filter:

$g = \left[ \begin{array}{cccccccccc} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{array} \right].$

With a horizontal filter, horizontal edges are treated well, but vertical edges badly.

c)

$3\times 1$ median filter:

$g = \left[ \begin{array}{cccccccccc} 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array} \right].$

With a vertical filter, vertical edges are treated well, but horizontal edges badly.

d)

Since neither a $3\times 1$ median filtering of the result from b), nor a $1\times 3$ median filtering of the result from c), will produce the result from a), the $3\times 3$ median filter is not separable. In general, median filters are not separable, but we can still have fast implementation (see the lecture slides for week 6).

Task 6

a) Corner

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 1\\ \hline 0 & 0 & 1 & 1\\ \hline \end{array}$

b) Thin line

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 \\ \hline \end{array}$

b) Combination of corner and thin line

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 \\ \hline \end{array}$

We see that the result is equal to the input image (if we ignore the boundary). That is, the proposed filter preserves corners, edges, and combinations of those.

PS: The result and conclusion had been identical if we had tried it on sharper or mor flat corners, or if we had rotated the shapes.

INF2310 - Digital Image Processing

Solution proposal - week 6