COMP 776 Spring 2009
Assignment 3: Fitting of geometric transformations, 3D triangulation
Due date: March 17 5PM (after Spring Break)
The goal of the assignment is to use linear least squares methods
and RANSAC to fit affine transformations, homographies, and fundamental
matrices to pairs of images. The second goal is to use the matching points
and camera matrices to perform triangulation to recover the corresponding
scene points in 3D.
Test Data
Download fullsize images, matching points,
camera matrices, and sample code.
Instructions
 Load the image pair and matching points file into MATLAB (see sample code
in the data file).
 Find a leastsquares affine transformation that maps all the points
in the first image onto corresponding points in the second image. Visualize
the fit by displaying the second image with its own points and the reprojected
points from the first image. Corresponding points should be connected by line
segments (the sample code contains all the elements you need for doing this).
Put the mean squared residual in the caption to the figure. Here is a sample
of what the output figure should look like:
 Now implement RANSAC to find the biggest set of matches consistent
with an affine transformation. Display the results for the inlier matches in
the same way as above. Put the number of inliers and the residual in the caption.
 Find a leastsquares planar homography that maps all the points from the
first image onto the corresponding points in the second image. Display the
results in the same way as in 2.
 Similarly to 3, use RANSAC to find the biggest set of matches consistent
with a planar homography. Display the results in the same way as in 3.
 Now fit a fundamental matrix and use the sample code provided to visualize
the results. The residual in this case should be the mean squared distance
between points in the second image and the corresponding epipolar lines.
 Load the camera matrices for the two images (they are stored as 3x4 matrices
and can be loaded with the load command, i.e., P1 = load('house1_camera.txt');
Find the centers of the two cameras. Use linear least squares
to triangulate the position of each matching pair of points given the two cameras.
Display the two camera centers and scene matches in 3D. Also compute the residuals
between the observed 2D points and the projected 3D points in the two images.
Details
 For details of the fitting methods, you should review the lectures on
alignment and epipolar geometry.
 In MATLAB, the solution to a linear least squares system AX=B is given by
X = A\B;
 Homography fitting calls for homogeneous least squares. The solution
to the homogeneous least squares system AX=0 is obtained from the SVD of A
by the singular vector corresponding to the smallest singular value:
[U,S,V]=svd(A); X = V(:,end);
 For homography and fundamental matrix fitting, don't forget to normalize
the data as described in the lecture on epipolar geometry. To see the difference
made by data normalization, you should run the estimation process for
unnormalized and normalized data and compare the output and the
residuals produced by both. Don't forget that the residual should always
be computed in the original pixel coordinates.
 Don't forget to enforce the rank2 constraint for the fundamental matrix F.
This can be done by taking the SVD of F, setting the smallest
singular value to zero, and recomputing F.
 For RANSAC, a very simple implementation is sufficient. Use 3 and 4 matches,
respectively, to initialize affine transformations and homographies. You should
output a single transformation that gets the most outliers in the course of all
the iterations. For the various RANSAC parameters (number of iterations, inlier
threshold), play around with a few ``reasonable'' values and pick the ones
that work best. Refer to this lecture for details on RANSAC.
For randomly sampling matches, you can use the randperm function.
 Recall that the camera centers are
given by the null spaces of the matrices. They can be found by taking the SVD of the
camera matrix and taking the last column of V.
 The linear least squares method for triangulation is described in
this lecture. To simplify the implementation,
it is not necessary to use data normalization for this part of the assignment
(in my implementation, normalization made very little difference for this part).
 Plotting in 3D can be done using the plot3 command. Use the
axis equal option to avoid automatic nonuniform scaling of the 3D space.
For bonus points

Use RANSAC to find several dominant subsets of inliers for homography in the
house sequence. The simplest way to do this is to find the largest consistent subset
using one run of RANSAC, then remove it from the set of matches, and run RANSAC again
to get the next biggest set, etc.

Instead of using precomputed matches, extract and match your own features.
You can use this corner detector code. For feature matching, try to extract
fixedsize patches around each corner location and compare them using SSD
or normalized correlation. Experiment with David Lowe's feature space outlier
rejection heuristic (comparing distance of nearest neighbor to that of
second nearest neighbor) and different thresholds for accepting putative
matches. Note that if you don't use the "ground truth" matches, you will
now have to run RANSAC to fit the fundamental matrix.
What to hand in
Hand in your code and a brief report with the following results (one for
each test image pair):
 Global affine transformation  output image and residual.
 Affine transformation computed with RANSAC  output image, number of inliers, and residual.
 Global homography  output image, residual. Show results for normalized and unnormalized data.
 Homography computed with RANSAC  output image, number of inliers, residual.
 Fundamental matrix  output image of points and corresponding epipolar lines, residual.
Show results for normalized and unnormalized data.
 Triangulation  screenshot of 3D plot with camera centers and triangulated scene points.
Residual values between original 2D points and reprojected scene points. 2D residual plots for this part
are optional.
As for the previous assignment, email me your homework file if it's not bigger than 2MB,
otherwise put it on the web and send me the URL. Your submission must be sent by 5PM
on March 17.
