CS 558: Homework Assignment 1

CS 558: Homework Assignment 1
Homeworks will be done individually: each student must hand in their own answers. It is
acceptable for students to collaborate in understanding the material but not in solving the problems.
Use of the Internet is allowed, but should not include searching for previous solutions or answers
to the specific questions of the assignment.
No late submissions will be allowed without consent from the instructor.
Electronic submission on Canvas is mandatory.
Submit a zip file containing: 1) a pdf file with the source code (excluding libraries), the resulting
images and a brief explanation of the implementation, 2) the code, 3) the output images.
Problem 1: Pre-processing. Download the image provided. You must implement two methods
for detecting lines (Problems 2 and 3). Before extracting the lines, you need to detect potential
points on them. Apply a Gaussian filter first and use the Sobel filters as derivative operators.
Threshold the determinant of the Hessian and then apply non-maximum suppression in 3 × 3
neighborhoods. Ignore pixels for which any of the filters falls even partially out of the image
boundaries.
Problem 2: RANSAC. Apply RANSAC on the points detected above to find four lines with strong
support. Since it is intractable to guarantee that you found the four lines with the most support, use
your best judgement to determine that the outputs are correct. One possible implementation is to
run RANSAC until it finds a line with a sufficient number of inliers. Make sure that the same
inliers are not used again. Plot the line segments in the image by connecting the two extreme inliers
of each line. Also plot the inliers as 3 × 3 squares.
Problem 3: Hough Transform. Apply a Hough transform to detect the four lines with the
strongest support using the polar parameterization of the line (not the point coordinates). Plot the
results as above. 
Note that the last two problems are independent.
Requirements and notes.
• You can use any programming language.
• You are allowed to use image reading and writing functions, matrix operation tools such as
computing eigenvalues, as well as plotting functions, but you are not allowed to use filtering, edge
detection or other image processing functions.
• Screenshots of the input with the lines and squares superimposed are acceptable.
• If you cannot implement the Hessian detector, using the local maxima of the gradient magnitude
will allow you to continue, but will not receive maximum credit. (Non-maximum suppression
should be in all directions here, as with the Hessian detector.)
• In Problem 1, the main parameter to be adjusted is the threshold on the determinant of the Hessian.
The standard deviation of the Gaussian filter is not that important.
• In Problem 2, the main parameters are the required number of inliers and the distance threshold
that determines which points are inliers given a line equation.
• In Problem 3, the main parameters are the dimensions of the bins of the accumulator