Programming Assignment 2
This assignment is due on Tuesday, March 20, 2007.
In this assignment, you will implement two well-known computer vision algorithms: the Hough
transform and image segmentation using normalized cut by Shi and Malik. Both algorithms are
presented in details in the lecture slides. As before, you should turn in the MATLAB code (and others) in a zip file here.
Hough Transform
Hough transform is a classical computer vision algorithm that detects lines in the
data. In this part of the assignment, you will implement the Hough Transform and
a simple corner detector (see lecture slides).
The implementation of the Hough transform should contain a MATLAB routine that takes two inputs, 1) a
collection of 2D data points (in a 2-by-n matrix, where n is the number of points)
and 2) the desired number of lines. The routine should output the lines in cartesian representation
(A, B, C, in Ax+By=C). The routine for locating corners should take an (gray-scale) image as the sole input and output the locations of the detected corners.
The followings are three datasets that you have to test your implementation with. The first two are
collections of 2D point sets for testing Hough transform. The third is an image of a
chessboard pattern on a cube. In this image, there are (two sets of) three mutually-perpendicular bundles of parallel lines in 3D running across the cube. You should use your corner detector to detect the corner points and then use the Hough Transform routine to detect the lines. For each bundle of parallel lines, determine the vanishing point (if there is any) of these parallel lines, i.e., the intersection point of these lines. This last part can be tricky.
Data Sets
Data1 ( Data1 for MATLAB 6.5 or earlier)
Data2 ( Data2 for MATLAB 6.5 or earlier)
Cube
Normalized Cut
For the second part of the assignment, you will implement a simple image segmentation routine using
Shi and Malik's normalized cut. The algorithm is presented in class and details can be found in the
lecture slides and the paper.
Your routine should take as inputs 1) an image, 2) a parameter
sigma used in defining affinity measure. You are free to choose your own affinity measure but it has to be
in exponential form containing sigma, and 3) the number of segments. To make it easier, you can assume that the
third input is always in a power of 2. The implementation should output the segmentation result in the form
of a collection of images, one image for each segmented region (using black background). The implementation should be tested with the following four images.
Turn in the code as well as your best segmentation results for these images. You may need to try
with different values of sigma.
Note that you may have to use MATLAB's sparse matrix routines (help sparse). Recall that the affinity
matrix is a sparse matrix, which is usually too large to store as a regular matrix.
To compute the eigenvectors of a sparse matrix in MATLAB, use the MATLAB native routine 'eigs'.
Images
Tom and Jerry
Airplanes
Hurricane
Nicole
You can convert the color images into gray-scale images using rgb2gray, and
you can define the affinity measure directly using brightness intensity values.