face morph

Project 6: Automated Panorama Stitching

Due Date: 11:59pm on Monday, November 26th, 2012

Brief

Requirements

The general pipeline for this project involes the following steps:

  1. Define correspondences between the 2 images.
  2. Recover the homography using RANSAC
  3. Warp one image using the recovered homography
  4. Composite the images
A simple version of step 3 and 4 is already implemented for you. You will focus on step 1 and 2.

Details

Define correspondences between the 2 images

You will try to automaticaly find corresponding points in two images. Your code for this should go in define_correspondence.m. This part of the process is based on Brown, et al. It is strongly recommended that you read this paper.

  1. Harris Interest Point Detector (section 2) - is already done for you (see harris.m)
  2. Implement adaptive non-maximal suppression (section 3) - loop through all initial interest points, and for each interest point compare the corner strength to all other interest points. Keep track of the minimum distance to a larger magnitude interest point (not necessarily larger, perhaps within 0.9 as large, see paper). After you've computed this minimum radius for each point, sort the list of interest points by descending radius and take the top N.
  3. Implement feature descriptor extraction (section 4) - Ignore rotation invariance, sub-pixel accuracy, and the wavelet transform. Remember to normalize each of your feature vectors: subtract the mean and divide by the standard deviation. Regardless of the size of the patch sampled from the image, the descriptor should end up as an 8x8 patch.
  4. Implement feature matching (section 5) - Look at pairs of features and compute the distance between them. This is why we give you dist2. After distances between all pairs of points hvae been computed, you might have 500 interest points, and could consider each point mapped to its first nearest neighbor as a correspondence. But most of these correspondences are spurious. Use Lowe's "ratio test" and keep only correspondences where the ratio between the first and second nearest neighbor distance is below some threshold.

Recover the homography using RANSAC

You will be recovering a projective transformation H. H is a 3x3 matrix with 8 degrees of freedom. It is possible to solve H by pairs of corresponding points since q=Hp. You will need to solve a system of at least 8 linear equations to solve for the 8 unknowns of H. These 8 linear equations are based on the 4 pairs of corresponding points. Here is a useful resource on projective mappings. Your code for this should go in calculate_transform.m.

With the automatic feature extraction, you will have a overdetermined system of equations for H. Unfortunately, some of the points may be false positives: points that matched under the threshold but are not actually matches. Even with an overdetermined system of equations, outliers from false positives will make a least-squares solution difficult to use (especially because with a d^2 penalty the outliers will be weighted more). A robust way to solve this problem is using the RANSAC algorithm, which examines random subsamples of matches in the hope that some subset will not be confused by outliers. Because you need to solve for 8 values, you will need four 2D points to create the transformation matrix. The TAs suggest 1000 iterations and an error tolerance of 0.5. This equates to iterating 1000 times to find a transform based on 4 points and counting the number of inliers -- transformed points that have at most an error of 0.5 (half a pixel) to their actual correspondence points. Return the homography which had the most inliers. You may need to invert this homography for the later image warping functions. Implement this in ransac.m.

Write up

For this project, just like all other projects, you must do a project report in HTML. In the report you will describe your algorithm and any decisions you made to write your algorithm a particular way. Then you will show and discuss the results of your algorithm. Also discuss any extra credit you did. Feel free to add any other information you feel is relevant.

globe panorama

Extra Credit

You are free to do whatever extra credit you can think of, but here are a few examples.

Graduate Credit

You are required to do at least 10 points of extra credit.

Handing in

This is very important as you will lose points if you do not follow instructions. Every time after the first that you do not follow instructions, you will lose 5 points. The folder you hand in must contain the following:

Then run: cs129_handin proj6
If it is not in your path, you can run it directly: /course/cs129/bin/cs129_handin proj6

Rubric

Final Advice

Credits

Project derived from Alexei A. Efros' Computational Photography course, with permission.

Good Luck!