Lecture 2 Problems – Solutions

Problem 1

Recall that $f \otimes w$ means cross-correlating image $f$ with filter $w$. Compute the following cross-correlation using same output size and zero padding. $$\begin{bmatrix} 0 & 1 & 0\\ 0 & 1 & 0\\ 0 & 1 & 0 \end{bmatrix} \otimes \begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1 \end{bmatrix}$$ #### Solution

$$\begin{bmatrix} 3 & 6 & 3\\ 4 & 8 & 4\\ 3 & 6 & 3 \end{bmatrix}$$

Problem 2

Perform the same convolution as above, but use repeat padding.

Solution

$$\begin{bmatrix} 4 & 8 & 4\\ 4 & 8 & 4\\ 4 & 8 & 4 \end{bmatrix}$$

Problem 3

Perform the same convolution as above, but use valid output size.

Solution

$[8]$

Valid output size gives values only where the kernel fully overlaps the image. In this case, that’s just one pixel.

Problem 4

Describe in words the result of applying the following filter using cross-correlation. If you aren’t sure, try applying it to the image above to gain intuition.

$$\begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{bmatrix}$$

Solution

This actually shifts things one pixel to the left. Try it out on an example to see this. If we were using convolution, it would shift right.

Problem 5

Compute the following convolution, assuming repeat padding and same output size. $$\begin{bmatrix} 0 & 0 & 1\\ 0 & 0 & 1\\ 0 & 1 & 1 \end{bmatrix} * \begin{bmatrix} 0 & 0 & 0\\ 1 & 0 & -1\\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} \ & \ & \ \\ \ & \ & \ \\ \hspace{1em} & \hspace{1em} & \hspace{1em} \end{bmatrix}$$

Solution

$$\begin{bmatrix} 0 & 0 & 1\\ 0 & 0 & 1\\ 0 & 1 & 1 \end{bmatrix} * \begin{bmatrix} 0 & 0 & 0\\ 1 & 0 & -1\\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}$$

Problem 6

Will the answer to #5 change if you use the following non-square filter instead? $$\begin{bmatrix} 1 & 0 & -1\\ \end{bmatrix}$$

Solution

No.

Problem 7

Design a 5x5 convolution filter that shifts an image up by one pixel then applies a width-3 box blur. Would the filter differ if you blurred before shifting?

Solution

$$\begin{bmatrix} 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ \end{bmatrix} / 9$$

A box blur would be a 3x3 box of 1/9, and shifting up would be a 1 in the position one up from the center; convolving these should get you the same box, but shifted up. I’d approach this by writing one filter to accomplish each operation, then convolving them together to get a single filter that does both.

Problem 8

Does blurring then sharpening an image yield the original, unfiltered image?

Solution

No. The stuff lost when blurring is truly gone and cannot be recovered by sharpening. We’ll see more on this next class!

Problem 9

Compute a 3x3 filter by convolving the following $1 \times 3$ filter with its transpose using full output size and zero padding: $$\begin{bmatrix} 1 & 2 & 1\\ \end{bmatrix}$$

Solution

$$\begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1 \end{bmatrix}$$

Problem 10

Suppose you have an image $F$ and you want to apply a $3 \times 3$ filter $H$ that can be written as $H = G * G^T$, where $G$ is $1 \times 3$. Which of the following will be more efficient?

* $F * (G * G^T)$ 
* $(F * G) * G^T$

Solution

The second option is faster.

11

For each of the following, decide whether it’s possible to design a convolution filter that performs the given operation.

1. Max filter: the output pixel is the maximum value among the pixels in the input window

2. Threshold: the output pixel is

   * 1.0 if the input pixel is > 0.5

   * 0.0 otherwise

3. $y$ partial derivative: the output is a finite-differences approximation of the input image's vertical derivative $\frac{\partial}{\partial y}  f(x, y)$.

Solution

No

No

Yes