Exercise week 6

Task 1 - 1D convolution

Given two 1D filters

$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].$

Perform a convolution of $f$ by $h$ by hand using all the modes we discussed in the lecture

a)

full mode. (Hint: the result should have length 7).

b)

valid mode. (Hint: the result should have length 3).

c)

same mode with zero-padding. (Hint: the result should have length 5).

Task 2 - 2D convolution

As Task 1, but with 2D filters. Given two 2D filters

$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].$

Perform a convolution of $f$ by $h$ by hand using all the modes we discussed in the lecture

a)

full mode. (Hint: the result should have shape $6\times 6$ ).

b)

valid mode. (Hint: the result should have shape $2\times 2$ ).

c)

same mode with zero-padding. (Hint: the result should have shape $4\times 4$ ).

Task 3 - Mean value filtering

Suppose that we smooths an image by convolving it with a $3\times 3$ mean value filter. Then, convolve the result with the same $3\times 3$ convolution filter. That is, the original image has now been smoothed two times with a $3\times 3$ mean value filter.

a)

What kind of filter should we use to achieve the same result from only one convolution?

b)

Is this filter separable, and if yes, what filters can we separate it into?

c)

Is an arbitrary combination of separable filters also a separate filter?

d)

Is a convolution of arbitrary separable filters also separable?

Task 4 - Image boundary problem

Discuss pros and cons using symmetrical padding and circular padding.

Task 5 - Median filtering

Given the following binary $7\times 10$ image of the letters iQ

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

Filter this image with a median filter with different neighbourhoods. Use valid mode, that is, ignore the image boundary, this should give a $5\times 10$ shape on th result image. Use the following neighbourhoods

a)

Centered $3\times 3$ neighbourhood:

$\begin{array}{|c|c|c|} \hline \text{ } & \text{ } & \text{ } \\ \hline \text{ } & \text{ } & \text{ } \\ \hline \text{ } & \text{ } & \text{ } \\ \hline \end{array}$

b)

Centered $1\times 3$ neighbourhood:

$\begin{array}{|c|c|c|} \hline \text{ } & \text{ } & \text{ } \\ \hline \end{array}$

c)

Centered $3\times 1$ neighbourhood:

$\begin{array}{|c|} \hline \text{ } \\ \hline \text{ } \\ \hline \text{ } \\ \hline \end{array}$

d)

Use the results from a), b), c) to explain why the $3\times 3$ median filter from a) can not be separated into a $1\times 3$ median filter and a $3\times 1$ median filter.

Remember: A (possible non-linear) 2D filter is separable if the same filtering can be achieved by two sequential 1D-filtrations.

Task 6 - A smarter median-based filter?

Median filtering with quadratic neighbourhoods do not produce a desired result in corner pixels, and for pixels in thin lines.

Investigate if the following $5\times 5$ filter treat corners, thin lines, and combinations of them better. The filter is such that the result at $(x, y)$ is

$g[x, y] = \mathrm{median}\{\min\{\mathcal{A}_2(x, y)\}, \min\{\mathcal{A}_1(x, y)\}, f[x, y], \max\{\mathcal{A}_1(x, y)\}, \max\{\mathcal{A}_2(x, y)\}\}$

where

$f[x, y]$ is the pixel value at $(x, y)$ in the input image $f$ (green),
$\mathcal{A}_1(x, y)$ is the set of 8 neighbours with a distance 1 from $(x, y)$ (red),
$\mathcal{A}_2(x, y)$ is the set of 16 neighbours with a distance 2 from $(x, y)$ (blue).

png

You can try it out on the following test images (you can ignore the image boundary treatment).

a) Corner

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

a) Thin line

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

a) Combination of corner and thin line

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