Intro to Image Understanding (CSC420)
Assignment 1
Posted: Jan 21, 2024 Submission Deadline : Jan 28, 11.59pm, 2024
Instructions for submission:
• Please write a document (pdf format) with your solutions.
• For the written part: Please write an explanation of how you computed your answer or
prove the problem step by step. You are highly recommended to use latex to compile math symbols. You may also write by hand and take photos. However, if the writing is not eligible, you may lose marks.
• For the coding part: Please include visualization results of each step. Please also attach your code in the document. E.g. for each relevant question, first show its image results, then attach the code at the end. If you only submit the code without the visualization figures, you will get at most half of the full mark.
• Please submit through MarkUs. You are expected to work on the assignment individ- ually. TA might perform plagiarism check.
Written Part (Max points: 6):
1. Assume we are doing convolution for an image with size H × W and a filter of size
(a) [0.5 point] What is the number of operations required for performing 2D convo- lution? 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 the 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), 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] In the general case, given a 3 × 3 filter, show under which condition it is separable.
3. [1 point] We know that convolution is commutative. Is cross correlation also commu- tative? Please provide a proof. You can do your analysis in 1D.
Programming Help, Add QQ: 749389476
4. [1 point] If I first convolve an image with a Gaussian filter with σ = 3, and then convolve the output with a Gaussian with σ = 5, this gives an equivalent result as if I just convolve the image with a Gaussian with what σ? Please include a mathematical justification for your answer.
Coding Part (Max points: 9): 1. Convolution Operation:
(a) [2 points] Write your own function for computing cross-correlation 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 performing cross-correlation of 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 performing cross-correlation. Please include a visualization of the result, when performing cross-correlation of the included waldo.png with the
filter 0.125 0.5 0.5 . Please show the original image and the image after
0 0.125 0.125 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 correlation function leveraging the fact that the filter is separable. If the above filter is separable, use this one. If not, choose an- other separable filter, and visualize the result when performing cross-correlation of waldo.png with the filter. Show the runtime comparisons between performing cross-correlation naively (not leveraging separability) and when leveraging sepa- rability.
(d) [1 point] Now you want to perform convolution instead of cross-correlation. Can you still take advantage of separability for cross-correlation? If so, please imple- ment it, and include a visualization of the result, when performing cross-correlation on waldo.png with the filter.
2. [1 point] Convolve the attached waldo.png with a (2D) Gaussian filter with σ = 2 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 and gradient direction 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 results in the assignment’s document.
Code Help, Add WeChat: cstutorcs
(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 hys- teresis thresholding. However, do perform non-maxima suppression. Please visualize your results on waldo.png.
Code Help