EE366-Homework 6 Solved

Problem 1 (a) Linear image filters are implemented through 2D convolutions. The convolution oper-          ation was defined in class as:

O[u, v] = X I[u − i, v − j] K[i, j], ∀(u, v) ∈ I,

(i,j)∈W

where K ∈Rw×w is the convolution kernel. The center of the window and kernel is considered to be coordinate (0, 0) and i, j ∈ [−h, h].

Work out (using pen and paper) the 2D convolution for the input image and kernel shown in Figure 1. The output image should be of the same size as the input image. You can choose to find output at the boundary by assuming any of the stated techniques in the slides (zero padding, loop around, etc.)

The convolution formula stated above can also be viewed as a graphical procedure, whose steps are outlined below:

1.    Flip the kernel in both the horizontal and vertical directions about the center pixel.

2.    Align the now flipped kernel over the input image, such that center pixel of the kernel is aligned with pixel location for which you want to compute output value.

                                                

 

3.    Multiply the kernel values with overlapping input values respectively.

4.    Sum up all the obtained products to find the output value.

(b) The kernel of a Gaussian filter is:

G[i, j] =  e− i22+σ2j2 ,

where σ2 is the variance. As we know the Gaussian function has an infinite support, so we are considering a finite version of the kernel here obtained by truncation, e.g. if we want a 3×3 sized Gaussian kernel, then i, j ∈{−1, 0, 1}. Using the definition from the previous part, an image can be filtered using a Gaussian kernel as:

O = I ∗ G.

An interesting property of the Gaussian kernel is that 2D convolution of an image with the Gaussian kernel can be written as two 1D sequential convolutions, i.e.

O[x, y] = I[x, y] ∗ G[x, y] = I[x, y] ∗ G[y] ∗ GT [x],

where G[y] is a vertical 1D Gaussian kernel and GT (x) is a horizontal 1D Gaussian

kernel  . Prove this property, using the definition of 2D con-

volution and 1D convolution.

Note that the order of convolution does not matter because its commutative, i.e. image could be convolved with the horizontal vector first and then with the vertical vector.

 2 2D kernels that allow decomposition into 1D kernels are called separable, and kernel matrix in such cases can be written as K = vhT , where v is a column vector and hT is a row vector.

Work out using pen and paper the convolution of the input image from Figure 1 with kernel corresponding to

G  .

(c)     Write a MATLAB function convolve(image,kx,ky) that accepts an input image and two 1D kernels as arguments, and generates a filtered image as an output, assuming that 1D kernels form a separable 2D kernel. You cannot use any MATLAB functions that trivialize this task, e.g. conv2/conv. You may use any method to find the convolution output at the boundary pixels. The MATLAB functions imread,imshow or functions iread,idisp from Corke’s library may be of help here.

(d)    Choose a grayscale image and apply a Gaussian filter of size 5×5 to it. Comment on the output using at max three sentences. Recall that Gaussian kernel is separable, and so you can use an 5 × 1 Gaussian kernel using the expression G  y2 where y ∈{−2, −1, 0, 1, 2}. Choose σ = 0.83

(e)     Sharpen the same image using the Gaussian kernel.

(f)      An image I(x, y) is a 2D function I : R2 → R. The derivatives of this function can be computed and approximated as:

Ix 

Iy  (x, y + 1) − I(x, y − 1)] .

Find the kernels (i)kx ∈R1×3 (ii) ky ∈R3×1, such that Ix = I ∗ kx and Iy = I ∗ ky .

(g)     Write a MATLAB function that accepts an image as an argument and computes

 q

Ix, Iy , and  Ix2 + Iy2 for this image. The last magnitude is returned as the output image.

                                                

 

(h)    Use an original gray-scale image and Gaussian filtered image as inputs to the function in the previous part, and comment on the output for the original image and differences between the two outputs.

Problem 2

 
In this problem, you’re going to establish an image segmentation pipeline based exactly on the methods discussed in the class. Your goal in this problem is to have the computer find the answers to the following questions about the included image objects.png:

1.   How many objects are in the image?

2.   Provide a descriptor for the location of each object in the image.

3.   Which object has the largest area?

4.   Can question 1 be answered for ducks.png? You can threshold experimentally.

5.   If you knew apriori that the image contained geometrical shapes, then can you think of some strategy for determining the shape? (You don’t have to write code)

You are to provide your own MATLAB code for the entire pipeline. You cannot use MATLAB functions that trivialize these tasks. Examples of disallowed MATLAB functions include bwconncomp,bwlabel,bwpropfilt,imbinarize,regionprops,visboundaries. Your submission should include code for the following steps:

(a)     A threshold˙image MATLAB function that thresholds an image. It should accept an input image and a threshold value as an argument, and return a binary image of same size as output. You don’t have to implement automatic thresholding, and can determine threshold experimentally. The MATLAB functions rgb2gray, imtool, and imhist may be of help here.

(b)     A label˙image MATLAB function that accepts the binary image from the previous step as argument and returns a labeled image. Each blob in the image should be assigned a different label, based on 4-connectivity. The MATLAB function label2rgb can help you visualize your labels.

(c)     A calculate˙centroids MATLAB function that accepts labeled image from the previous step as an argument and returns a matrix with locations of all centroids in (x, y) format.

(d)     Necessary additions to the previous code to answer the questions outlined above.