Description
Written Part (Max points: 6):
1. Assume we are doing convolution for an image with size H × W and a filter with size
K × K:
(a) [0.5 point] What is the number of operations required for performing 2D convolution? E.g. how many add and multiplication operations in total? You do not
need to consider padding.
(b) [0.5 point] What is the number of operations required for performing convolution
with a separable filter? Assume this filter K × K is separable. You do not need
to consider padding.
2. Filter Separation:
(a) [1 point] Is a vertical derivative, ∂G(x,y)
∂y , of a Gaussian filter G a separable filter?
Analyze both the isotropic and anisotropic case.
(b) [1 point] Is a Laplacian of Gaussians (LoG) a separable filter?
(c) [1 point] Generally speaking, given a 3×3 filter, show that under which condition
it is separable.
3. [1 point] We know that convolution is commutative. Is cross correlation also commutative? Please provide a proof. You can do your analysis in 1D.
1
4. [1 point] If I first convolve an image with a Gaussian filter with σ = 1, and then
convolve the output with a Gaussian with σ = 2, this gives an equivalent result as if I
just convolve the image with a Gaussian with what σ?
Coding Part (Max points: 9):
1. Convolution Operation:
(a) [2 points] Write your own function for computing convolution of the 2D (grayscale)
image and a 2D filter. If the image is not grayscale, convert it to grayscale inside
your function (you can use built in functions for the conversion). The function
should accept a 2D image and a 2D filter (you can assume it’s a square matrix with
odd height and width), and return the resulting matrix obtained by convolving
the input image with the given filter. Make the output matrix be the same size
as the input image. Be careful to correctly deal with the border of the image –
the easiest way to do this is to “zero-pad” the image prior to convolution. Please
include a visualization of the result, when convolving the included waldo.png with
the filter
0 0.125 0
0.5 0.5 0.125
0 0.5 0
. Please show the original image and the image
after convolution.
(b) [0.5 point] Write a function to verify that the above filter is separable or not.
(c) [0.5 point] Write a faster convolution function leveraging the fact that the filter
is separable. If the above filter is separable, use this one. If not, choose another
separable filter, and visualize the result when convolving waldo.png with the filter.
Show the time comparison.
(d) [1 point] Assume the above filter is separable, but now you want to perform
cross correlation instead of convolution. Can you still take advantage or separability for correlation? If so, please implement it, and include a visualization of the result, when performing cross correlation on
waldo.png with the filter
0 0.125 0
0.5 0.5 0.125
0 0.5 0
.
2. [1 point] Convolve the attached waldo.png with a (2D) Gaussian filter with σ = 1 and
visualize the result (display the filter and the result of the convolution). You should
implement the Gaussian filter generation code with kernel size and σ as input. You can
use your implemented convolution code or built-in functions for convolution operation.
Include the visualized result in the assignment’s document.
3. Gradients Computation:
(a) [1 point] Compute magnitude of gradients for the attached images waldo.png
and template.png. Write your own function to do this. You can use the built-in
convolution function or your own implementation. Include the visualized result in
the assignment’s document.
2
(b) [1 point] Write a function that localizes the template (template.png) in the image
waldo.png based on the magnitude of gradients. Write your own function to do
this. Visualize the result and include it in the assignment’s document.
4. [2 points] Implement the Canny edge detector yourself. You do not need to do hysteresis thresholding. However, do perform non-maxima suppression. Please visualize
your results on waldo.png.
3
