COMPUTER VISION HOMEWORK 1 Solution

PROBLEM
TYPE
TOPIC
MAX. POINTS
1
Analytical
LSI Systems
10
2
Coding
2D-Convolution
5
3
Coding
Image Blurring and Denoising
15
4
Coding
Image Gradients
5
5
Analytical + Coding
Image Filtering
15
6
Analytical
Interview Question (Bonus)
10









Motivation

The long-term goal of our field is to teach robots how to see. The pedagogy of this class (and others at peer schools) is to take a bottom-up approach to the vision problem. To teach machines how to see, we must first learn how to represent images (lecture 2), clean images (lecture 3), and mine images for features of interest (edges are introduced in lecture 4 and will thereafter be a recurring theme). This is an evolution in turning the matrix of pixels (an unstructured form of “big data”) into something with structure that we can manipulate.

The problem set consists of:

    • analytical questions to solidify the concepts covered in the class, and

    • coding questions to provide a basic exposure to image processing using Python.

You will explore various applications of convolution such as image blurring, denoising, filtering and edge detection. These are fundamental concepts with applications in many computer vision and machine learning applications. You will also be given a computer vision job interview question based on the lecture.




1
Homework Layout

The homework consists of 6 problems in total, with subparts for each problem. There are 2 types of problems in this homework - analytical and coding. All the problems need to be answered in the Overleaf document. Make a copy of the Overleaf project, and fill in your answers for the questions in the solution boxes provided.

For the analytical questions you will be directly writing their answers in the space provided below the questions. For the coding problems you need to use the Jupyter notebook provided Jupyter notebook (see the Jupyter notebook for each sub-part which involves coding). After writing your code in the Jupyter notebook you need to copy paste the same code in the space provided below that question on Overleaf. For instance, for Question 2 you have to write a function ‘conv2D‘ in the Jupyter notebook (and also execute it) and then copy that function in the box provided for Question 2 here in Overleaf. In some questions you are also required to copy the saved images (from Jupyter) into the solution boxes in Overleaf. For instance, in Question 3.2 you will be visualizing the gaussian filter. So you will run the corresponding cells in Jupyter (which will save an image for you in PDF form) and then copy that image in Overleaf.

Submission

You will need to make two submissions: (1) Gradescope: You will submit the Overleaf PDF with all the answers on Gradescope. (2) CCLE: You will submit your Jupyter notebook (.ipynb file) with all the cells executed on CCLE.

Software Installation

You will need Jupyter to solve the homework. You may find these links helpful:

    • Jupyter (https://jupyter.org/install)

    • Anaconda (https://docs.anaconda.com/anaconda/install/)





















2
    • Image Processing

1.1    Periodic Signals (1.0 points)

Is the 2D complex exponential x(n1; n2) = exp(w1n1 + w2n2) periodic in space? Justify.











1.2    Working with LSI systems (3.0 points)

Consider an LSI system T [x] = y where x is a 3 dimensional vector, and y is a scalar quantity. We define 3 basis vectors for this 3 dimensional space: x1 = [1; 0; 0], x2 = [0; 1; 0] and x3 = [0; 0; 1].
    (i) Given T [x1] = a, T [x2] = b and T [x3] = c, find the value of T [x4] where x4 = [5; 4; 3]. Justify your approach briefly (in less than 3 lines).

    (ii) Assume that T [x3] is unknown. Would you still be able to solve part (i)?

(iii) T [x3] is still unknown. Instead you are given T [x5] = d where x5 = [1; 1; 1]. Is it possible to now find the value of T [x4], given the values of T [x1]; T [x2] (as given in part (i)) and T [x5]? If yes, find T [x4] as a function of a; b; d; otherwise, justify your answer.











1.3    Space invariance (2.0 points)

Evaluate whether these 2 linear systems are space invariant or not. (The answers should fit in the box.)
    (i) T1[x(n1)] = 2x(n1)
    (ii) T2[x(n1)] = x(2n1).
















3










Figure 1: (a) Graphical representation of x (b) Graphical representation of h

1.4    Convolutions (4.0 points)

Consider 2 discrete 1-D signals x(n) and h(n) defined as follows:

x(i) = i + 1
8i 2 f0; 1; 2; 3g

x(i) = 0
8i 62 0f; 1; 2; 3g
(1)
h(i) = i
1
8i 2 f0; 1; 2g

h(i) = 0
8i 62 0f; 1; 2g


    (i) Evaluate the discrete convolution h  x.

    (ii) Show how you can evaluate the non-zero part of h x as a product of 2 matrices H and X. Use the commented latex code in the solution box for typing out the matrices.


































4
    • 2D-Convolution (5.0 points)

In this question you will be performing 2D convolution in Python. Your function should be such that the convolved image will have the same size as the input image i.e. you need to perform zero padding on all the sides. (See the Jupyter notebook.)

This question is often asked in interviews for computer vision/machine learning jobs.

Make sure that your code is within the bounding box below.






















































5
    • Image Blurring and Denoising (15.0 points)

In this question you will be using your convolution function for image blurring and denoising. Blurring and denoising are often used by the filters in the social media applications like Instagram and Snapchat.

3.1    Gaussian Filter (3.0 points)

In this sub-part you will be writing a Python function which given a filter size and standard devia-tion, returns a 2D Gaussian filter. (See the Jupyter notebook.)

Make sure that your code is within the bounding box.











3.2    Visualizing the Gaussian filter (1.0 points)

(See the Jupyter notebook.) You should observe that increasing the standard deviation (s) increases the radius of the Gaussian inside the filter.

Copy the saved image from the Jupyter notebook here.











3.3    Image Blurring: Effect of increasing the filter size and s (1.0 points)

(See the Jupyter notebook.) You should observe that the blurring should increase with the kernel size and the standard deviation.

Copy the saved image from the Jupyter notebook here.














6
3.4    Blurring Justification (2.0 points)

Provide justification as to why the blurring effect increases with the kernel size and s?











3.5    Median Filtering (3.0 points)

In this question you will be writing a Python function which performs median filtering given an input image and the kernel size. (See the Jupyter notebook.)

Make sure that your code is within the bounding box.











3.6    Denoising (1.0 points)

(See the Jupyter notebook.)

Copy the saved image from the Jupyter notebook here.











3.7    Best Filter (2.0 points)

In the previous part which filtering scheme performed the best? And why?













7
3.8    Preserving Edges (2.0 points)

Which of the 3 filtering methods preserves edges better? And why? Does this align with the previous part?



























































8
    • Image Gradients (5.0 points)

In this question you will be visualizing the edges in an image by using gradient filters. Gradients filters, as the name suggests, are used for obtaining the gradients (of the pixel intensity values with respect to the spatial location) of an image, which are useful for edge detection.

4.1    Horizontal Gradient (1.0 points)

In this sub-part you will be designing a filter to compute the gradient along the horizontal direction. (See the Jupyter notebook.)

Make sure that your code is within the bounding box.











4.2    Vertical Gradient (1.0 points)

In this sub-part you will be designing a filter to compute the gradient along the vertical direction. (See the Jupyter notebook.)

Make sure that your code is within the bounding box.











4.3    Visualizing the gradients (1.0 points)

(See the Jupyter notebook.)

Copy the saved image from the Jupyter notebook here.















9
4.4    Gradient direction (1.0 points)

Using the results from the previous part how can you compute the gradient direction at each pixel in an image?











4.5    Separable filter (1.0 points)

Is the gradient filter separable? If so write it as a product of 1D filters.













































10
    • Beyond Gaussian Filtering (15.0 points)

5.1    Living life at the edge (3.0 points)

The goal is to understand the weakness of Gaussian denoising/filtering, and come up with a better solution. In the lecture and the coding part of this assignment, you would have observed that Gaussian filtering does not preserve edges. Provide a brief justification.

[Hint: Think about the frequency domain interpretation of a Gaussian filter and edges.]











5.2    How to preserve edges (2.0 points)

Can you think of 2 factors which should be taken into account while designing filter weights, such that edges in the image are preserved? More precisely, consider a filter applied around pixel p in the image. What 2 factors should determine the filter weight for a pixel at position q in the filter window?











5.3    Deriving a new filter (2.0 points)

For an image I, we can denote the output of Gaussian filter around pixel p as

GF[Ip] = å Gs  kp    qk Iq:
q2S

Ip denotes the intensity value at pixel location p, S is the set of pixels in the neighbourhood of pixel p. Gsp is a 2D-Gaussian distribution function, which depends on kp qk, i.e. the spatial distance between pixels p and q. Now based on your intuition in the previous question, how would you modify the Gaussian filter to preserve edges?

[Hint: Try writing the new filter as

 
BF[Ip] = å Gs  kp    qk f Ip; Iq  Iq:

q2S

What is the structure of the function f (Ip; Iq)? An example of structure is f (Ip; Iq) = h(Ip Iq) where h(x) is a monotonically increasing function in x?]

11









5.4    Complete Formula (3.0 points)

Check if a 1D-Gaussian function satisfies the required properties for f (:) in the previous part.

Based on this, write the complete formula for the new filter BF.











5.5    Filtering (3.0 points)

In this question you will be writing a Python function for this new filtering method (See the Jupyter notebook.)

Make sure that your code is within the bounding box.











5.6    Blurring while preserving edges (1.0 points)

Copy the saved image from the Jupyter notebook here.











5.7    Cartoon Images (1 points)

Natural images can be converted to their cartoonized versions using image processing techniques. A cartoonized image can generated from a real image by enhancing the edges, and flattening the

12
intensity variations in the original image. What operations can be used to create such images? [Hint: Try using the solutions to some of the problems covered in this homework.]


















Figure 2: (a) Cartoonized version (b) Natural Image













    • Interview Question (Bonus) (10 points)

Consider an 256 256 image which contains a square (9 9) in its center. The pixels inside the square have intensity 255, while the remaining pixels are 0. What happens if you run a 9 9 median filter infinitely many times on the image? Justify your answer.

Assume that there is appropriate zero padding while performing median filtering so that the size of the filtered image is the same as the original image.




















13