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

Instructions

1. Load the image pair and matching points file into MATLAB (see sample code in the data file).
   
   
2. Find a least-squares 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:
   
   
   
3. 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.
   
   
4. Find a least-squares 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.
   
   
5. 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.
   
   
6. 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.
   
   
7. 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 rank-2 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 pre-computed matches, extract and match your own features. You can use this corner detector code. For feature matching, try to extract fixed-size 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

• 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.