Big picture

In this assignment you will apply what we learned in class to fit a line using RANSAC.

The second part of this assignment will help you understand the mapping between two images of the same planar object under different projective cameras. This mapping (a homography) is not generally valid, but it is valid if the objects are planar (as in this homework), or the camera is rotated around its optical center.

Grad students will further see how using this constraint is very helpful to prune bad matches of localized feature points like SIFT. Grad students will learn how to use the RANSAC method to find the homography. This will further illustrate that RANSAC is a very powerful method for fitting models with a modest number of parameters.

You can do this assignment in either Matlab or C/C++.

Information for those working in C/C++ who want to use my libraries.

Assignment specification

1. RANSAC. This file contains 300 points, of which at least 1/4 can be assumed to lie on a pretty good line. Write a program that reads in these points, makes a scatter plot of them, finds a line using RANSAC, and plots that line on top of the scatter plot. Hand in your code to produce this plot. In addition, put the plot into a PDF, and report the line found, the error of the line based on what you found as the inliers (+).

   You should use the perpendicular distance from the inlier points to the proposed line as your error measure. Don't forget to refit the line after establishing the inliers using homogeneous least squares.

   Note: In class we mentioned two methods for determining inliers versus outliers (threshold, and best N%). You can use either here, but since I am telling you a lower bound on inliers, you may find using the best N% to be a bit easier. If you want to try using a threshold, and/or both methods, you could consult the scatter plot help you choose a threshold.

   Tip: See http://en.wikipedia.org/wiki/RANSAC for more on RANSAC, including the standard formula that allows you to choose the number of iterations sensibly.

2. Homography. Implement both methods discussed in class for computing the homography between two planar images based on 4 point matches. For the first method you will need to set up the matrix along similar lines to what we did with camera calibration (HW 3). For DLT, follow the notes. The equations for both methods are solved using homogeneous least squares.

   Test both methods on the data used in Assignment Six. For each pair of images (slide and video frame), collect 8 point matches using manual mouse clicking. Do not spend too much time getting perfect matches. In fact, if the points are completely free of error then it may be harder to understand what is happening.

   Now take a subset of 4 points from those 8 as input to a test program that computes the homography. Use the computed homography to map all 8 source points (from the slide) to the video frame. In the video frame images, display the 8 clicked points, and the 8 mapped locations differently (e.g. different color). Ideally they should be relatively close, and in particular, the 4 points used to establish the homography should be on top of each other. Hand in three pairs of images for each method showing the marked points in both, and the mapped points in the video frame (+).

3. Required for grad students only (modest extra credit for ugrads).

   Homography and RANSAC. Now use RANSAC to improve the keypoint matching to search for a set of N keypoints that all agree about the homography. From your previous work on Assignment Six, you probably have some idea about what a good number for N is. Does RANSAC help? If you already were sufficiently conservative with N that most matches are good, cconsider if you can get away with a bigger N when you use RANSAC. (A bigger N is better if you can retrieve some good matches you would have done without otherwise which then leads to a more accurate homography).

   Provide revised figures with keypoint matches as you did for Assignment Six for the method you deemed best and worse, or, if that is not clear, choose two of them (+).

   Comment on any difference in the two methods for solving for the homography. (Note: In general the DLT method is regarded to be more stable, but I have no idea if this will be the case here).

   Tip: Ensure that the 4 matches in each group are different. If you naively randomly sample, then you might draw the same match twice. This will lead to a degenerate equation that might produce an error when you try to solve it. (This may happen on occasion anyway, so if you are able to trap that error and ignore it, your code will be more robust).

To hand in the above, use the turnin program available on lectura (turnin key is cs477_hw8).  Hand in any code, and a PDF reporting on what you did with images embedded.