Description
1 Theory (15 marks)
You can submit your response as a PDF document, which can be typed out in LaTeX/Word, or
handwritten and scanned. If handwritten, please ensure legibility of answers.
1. Linear Filters (2+2+2+1+3=10 marks): In class, we introduced 2D discrete space convolution.
Consider an input image I[i, j] and a filter F[i, j]. The 2D convolution F ∗ I is defined as
(F ∗ I)[i, j] = X
k,l
I[i − k, j − l]F[k, l] (1)
(a) Convolve the following I and F (using pen and paper). Assume we use zero-padding where
necessary.
I =
2 0 1
1 −1 2
F =
1 −1
1 −1
(2)
Please DO NOT write programs. It will also be helpful for answering question (d).
(b) Note that the F given in Equation 2 is separable, that is, it can be written as a product of two
filters: F = F1F2. Find F1 and F2. Then, compute (F1 ∗ I) and F2 ∗ (F1 ∗ I), i.e., first perform
1D convolution on each column, followed by another 1D convolution on each row. (Please DO
NOT write programs. Do it by hand.)
1
(c) Prove that for any separable filter F = F1F2
F ∗ I = F2 ∗ (F1 ∗ I)
Hint: Expand Equation 1 directly.
(d) Carefully count the exact number of multiplications (multiplications only, including those multiplications due to zero-padding) involved in part (a) and part (b). which one of these requires
fewer operations? You may find the computation steps you wrote down for (a) and (b) helpful
here.
(e) Consider a more general case: I is an M1 × N1 image , and F is an M2 × N2 separable filter.
i. How many multiplications do you need to do a direct 2D convolution?
ii. How many multiplications do you need to do 1D convolution on rows and columns?
Hint: For (i) and (ii), we are asking for two functions of M1, N1, M2 and N2 here, no
approximations.
iii. Use Big-O notation to argue which one is more efficient in general: direct 2D convolution
or two successive 1D convolutions?
2. Canny Edge Detector (2.5+2.5=5 marks): Suppose the Canny edge detector successfully detects an edge. The detected edge (shown as the red horizontal line in Figure 2a) is then rotated by
θ, where the relationship between a point on the original edge (x, y) and a point on the rotated edge
(x
0
, y0
) is defined as
x
0 = xcosθ ; y
0 = ysinθ
(a) Will the rotated edge be detected using the same Canny edge detector? Provide either a
mathematical proof or a counter example. Hint: The detection of an edge by the Canny edge
detector depends only on the magnitude of its derivative. The derivative at point (x,y) is
determined by its components along the x and y directions. Think about how these magnitudes
have changed because of the rotation.
Figure 1: Canny Edge Detector
(b) After running the Canny edge detector on an image, you notice that long edges are broken into
short segments separated by gaps. In addition, some spurious edges appear. For each of the
two thresholds (low and high) used in hysteresis thresholding, state how you would adjust the
threshold (up and down) to address both problems. Assume that a setting exists for the two
thresholds that produce the desired result.
2
2 Programming (35 marks)
• Please see the attached zip file which contains 6 programming question in DL4V Assignment 1.ipynb
notebook. Do fill out the code where-ever it is asked for and turn-in the completed jupyter notebook.
• Marks breakdown is as follows:
– Question 1: 10 marks
– Question 2: 5 marks
– Question 3: 2.5 marks
– Question 4: 2.5 marks
– Question 5: 10 marks
– Question 6: 5 marks
• Note: you are required to work with images provided in the zip file. Specifically, car road.jpg and
car.jpg for Question 1 and clown.png for rest of the questions.
3
