## Description

1

ECS 189G: Intro to Computer Vision

Problem Set 2

Instructions

1. Answer sheets must be submitted on SmartSite. Hard copies will not be accepted.

2. Please submit your answer sheet containing the written answers in a file named:

FirstName_LastName_PS2.pdf. Please put your name on the answer sheet.

3. Please submit your code and input /output images in a zip file named: FirstName_LastName_PS2.zip.

Please do not create subdirectories within the main directory.

4. You may collaborate with other students. However, you need to write and implement your own

solutions. Please list the names of students you discussed the assignment with.

5. For the implementation questions, make sure your code is documented, is bug-free, and works out

of the box. Please be sure to submit all main and helper functions. Be sure to not include absolute

paths. Points will be deducted if your code does not run out of the box.

6. If plots are required, you must include them in your answer sheet (pdf) and your code must display

them when run. Points will be deducted for not following this protocol.

1 Short answer problems [20 points]

1. Suppose we form a texture description using textons built from a filter bank of multiple anisotropic derivative

of Gaussian filters at two scales and six orientations (as displayed below in Figure 1). Is the resulting

representation sensitive to orientation, or is it invariant to orientation? Explain why.

Figure 1: Filter bank

2. Consider Figure 2 below. Each small dot denotes an edge point extracted from an image. Say we are going

to use k-means to cluster these points’ positions into k=2 groups. That is, we will run k-means where the

feature inputs are the (x,y) coordinates of all the small dots. What is a likely clustering assignment that would

result? Briefly explain your answer.

2

Figure 2: Edge points

3. When using the Hough Transform, we often discretize the parameter space to collect votes in an

accumulator array. Alternatively, suppose we maintain a continuous vote space. Which grouping algorithm

(among k-means, mean-shift, or graph-cuts) would be appropriate to recover the model parameter

hypothesesfrom the continuous vote space? Briefly describe and explain.

4. Suppose we have run the connected components algorithm on a binary image, and now have access to the

multiple foreground ‘blobs’ within it. Write pseudocode showing how to group the blobs according to the

similarity of their area (# of pixels) and aspect ratio (width/height), into some specified number of groups.

Define clearly any variables you introduce.

2 Programming [80 points]

1. Color quantizationwith k-means [40points]

For this problem you will write code to quantize a color space by applying k-means clustering to the pixels

in a given input image, and experiment with two different color spaces—RGB and HSV. Write Matlab

functions as defined below. Save each function in a file called <function-name.m and submit all of them.

(a) [5 points] Given an RGB image, quantize the 3-dimensional RGB space, and map each pixel in the

input image to its nearest k-means center. That is, replace the RGB value at each pixel with its nearest

cluster’s average RGB value. Use the following form:

Function [outputImg, meanColors] = quantizeRGB(origImg, k)

where origImg and outputImg are MxNx3 matrices of type uint8, k specifies the number of

colors to quantize to, and meanColors is a k x 3array of the k centers. Matlab tip: if the variable

origImg is a 3d matrix containing a color image with numpixels pixels, X =

reshape(origImg, numpixels, 3); will yield a matrix with the RGB features as its rows.

3

(b) [5 points] Given an RGB image, convert to HSV, and quantize the 1-dimensional Hue space. Map each

pixel in the input image to its nearest quantized Hue value, while keeping its Saturation and Value

channels the same as the input. Convert the quantized output back to RGB color space. Use the

followingform:

Function [outputImg, meanHues] = quantizeHSV(origImg, k)

where origImg and outputImg are MxNx3 matrices of type uint8, k specifies the number of

clusters, and meanHues is a k x 1vector of the hue centers.

(c) [5 points] Write a function to compute the SSD error (sum of squared distances error) between the

original RGB pixel values and the quantized values, with the following form:

function [error] = computeQuantizationError(origImg,quantizedImg)

where origImg and quantizedImg are both RGB images, and erroris a scalar giving the total

SSD error across all pixels in the image.

(d) [5 points] Given an image, compute and display two histograms of its hue values. Let the first

histogram use k equally-spaced bins (uniformly dividing up the hue values), and let the second

histogram use bins defined by the k cluster center memberships (i.e., all pixels belonging to hue cluster

i go to the i-th bin, for i=1,…k). Use the following form:

function [histEqual, histClustered] = getHueHists(im, k)

where im is an MxNx3matrix representing an RGB image, and histEqual and histClustered

are the two output histograms.

(e) [5 points] Write a script colorQuantizeMain.m that calls all the above functions appropriately

using the provided image fish.jpg, and displays the results. Calculate the SSD error for the image

quantized in both RGB and HSV space. Write down the SSD errors in your answer sheet. Illustrate the

quantization with a lower (k=5) and higher (k=25) value of k. Be sure to convert an HSV image back

to RGB before displaying with imshow. Label all plots clearly with titles.

(f) [15 points] In your write-up, explain all the results. How do the two forms of histogram differ? How

and why do results vary depending on the color space? The value of k? Across different runs of kmeans (with the same value of k)?

Matlab useful functions: kmeans, rgb2hsv, hsv2rgb, imshow, im2double, reshape,

subplot, title, hist.

2. Circle detection with the Hough Transform [40 points]

Implement a Hough Transformcircle detector that takes an input image and a fixed radius, and returns the

4

centers of any detected circles of about that size. Include a function with the following form:

Function [centers] = detectCircles(im, radius, useGradient)

where im is the input image, radius specifies the size of circle we are looking for, and useGradient

is a flag that allows the user to optionally exploit the gradient direction measured at the edge points. The

output centers is an N x 2 matrix in which each row lists the (x,y) position of a detected circle’s center.

Save this function in a file called detectCircles.m and submit it.

Then experiment with the basic framework, and in your write-up analyze the following:

(a) [10 points] Explain your implementation in concise steps (English, not code).

(b) [10 points] Demonstrate the function applied to the provided images jupiter.jpg and egg.jpg (and an

image of your choosing if you like). Display the accumulator arrays obtained by setting

useGradient to 0 and 1. In each case, display the images with detected circle(s), labeling the

figure with the radius. You can use impixelinfo to estimate the radius of interest manually.

(c) [10 points] For one of the images, display and briefly comment on the appearance of the Hough space

accumulator array.

(d) [5 points] Experiment with ways to determine how many circles are present by post-processing the

accumulator array.

(e) [5 points] For one of the images, demonstrate the impact of the vote space quantization (bin size).

Matlab useful functions: atan2, hold on, plot, fspecial, conv2, im2double, sin,

cos, axis equal, edge, impixelinfo.

Matlab tip: Note that the row number (“y” value) for an image position is flipped from Cartesian coordinates,

increasing as we move down.

3 [OPTIONAL] Extra credit [up to 10 points]

Extend your Hough circle detector implementation to detect circles of any radius. Demonstrate the method applied

to the test images.