Project 6: Automated Panorama Stitching on the n900

Due Date: 11:59pm on Wednesday, April 20th, 2011

Brief

• This handout: /course/cs129/asgn/proj6/handout/
• Stencil code: /course/cs129/asgn/proj6/stencil/
• New VM: /course/cs129/asgn/proj6/vm/
• Test Data: /course/cs195g/asgn/proj6/data/
• Handin: cs129_handin proj6
• Required files: README, code/, html/, html/index.html

Envoirnment Updates

You will again need to update your vm if you wish to test your code on the desktop. To do this run: sudo apt-get install libqt4-dev This update is unecessary if you only with to do testing on the phone.

Building and Testing Your Code

You may use the Features.pro file and QtCreator to build either the desktop or phone versions of the code. The code can also be built from the command line using:

• Desktop: qmake to create the desktop make file. make to build.
• Phone: mad qmake to create the desktop make file. mad make to build.

You can use the following command to test your code on the desktop: ./Features panorama img1 img2 destimage
You should can test your panorama stitcher on these two Yosemite images. If you would like a larger set to test on, try out this larger set of Yosemite images.

Requirements

You are required to implement the following:

• Accelerated feature matching and feature-space outlier rejection
• Robustly calculate a homography from matched features using RANSAC
• Warp images given a transformation matrix
• Composite the warped images into a mosaic

Recover Homographies

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. You should be able to test your code for recovering homographies independantly of your other code. It's important to make sure this part works since other parts build on top of it.

Warp Images

Once you have the homography, you will need to warp images. You should map the pixels in the warped image to pixels in the input image so that you don't end up with holes in your image. Here is a useful resource on image warping. Note the following when reading this resources:

• The authors are not necessarily doing a perspective transform
• The authors do not homogeonize their result coordinates, i.e. divide by homogeneous coordinate (x, y, w)/w = (x/w, y/w, 1)
• The authors have their width and height backwards throughout the entire paper: it should be [h,w] = size(A)

Composite Warped Images

You will need to composite two (or more) images to make a panorama. It is your choice on whether to incrementally warp one image to another or warp all the images to one image. It is also your choice on how to composite. You can simply do over, averaging, feathering, GraphCut seams, Poisson image blending or any other technique you feel like. You will not be penalized for doing simple composite techniques, but your results may not look as good.

Detect Features

Feature Detection and Description has been implemented for you! We have provided code for SURF (Speeded Up Robust Features). You are encouraged to look through and understand the code. You may also wish to experiment with other feature detectors and descriptors. We have provided space in the stencil code for the scheme we discussed in class using harris corners, non maximal supression, and MOPS descriptors.

Match Feature

Basic Feature Matching using the sum of squared differences metric to find the nearest neighbor has been implemented for you for testing purposes. It will work reasonably well, but a bit slowly. You are required to implement a faster approximate version using a provided kd-tree library. You are also required to use the ratio between the first and second nearest neighbors in this function; however, this should require little extra work because the kd-tree will be doing the heavy lifting.

Robustly Recover Homographies

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. You will need to remove these outliers as they will throw off your transformation matrix. A robust way to solve that is using the RANSAC algorithm.

Implementation Details

C++ stencil code is available in /course/cs129/asgn/proj6/stencil/. You're free to do this project in whatever language you want, but the TAs are only offering support in C++. The TAs have supplied several files to get you started. The only source file you should need to edit is Features.cpp in which you will need to complete the following functions:

• void ratioMatchFeatures(FeatureSet &f1, FeatureSet &f2, vector &matches, float &totalScore, Progressable *thread)
This function uses the ratio of the SSD distance of the two best matches and matches a feature in the first image with the closest feature in the second image. It can match multiple features in the first image to the same feature in the second image. Most of this function is implemented for you, but you need to call the FLANN library in order to find approximate nearest neighbors.


• void computeHomography(vector &f1, vector &f2, vector &matches, cv::Mat& h)
This function will take in two sets of features, and a list of matches, and return a homography computed using least squares (with the direct linear transformation approximation). Probably the best way to solve this is to use the singular value decomposition, in OpenCV as You may find cvSolve and / or cvSVD useful for solving the least squares problem. The memory for the output matrix h is allocated by this caller. Note that when calling this function, you will likely want to create a temporary sublist of four or more matches (i.e., you will never pass in the full list of matches, but will construct a subset of matches).


• cv::Mat ransacHomography(vector &f1, vector &f2, vector &matches, int numRounds, int inlierThreshold, Progressable *thread)
You will implement RANSAC as described in lecture. This function takes in two sets of features, a list of matches, and returns a 3 × 3 homography matrix, and runs RANSAC with "numRounds" rounds, with an inlier threshold of "inlierThreshold." This function will call computeHomography (which expects a preallocated 3 × 3 matrix of type CV_32F), as well as applyHomography.


• IplImage* constructPanorama(IplImage *img1, IplImage *img2, int featureType, int matchType, Progressable *thread)
This is the entry point for all panorama generation. The output image will be allocated by your code and in particular should be allocated from a call to compositeImages. This function will also depend on ransacHomography in order to compute a best homograph for the pair of images. You should use computeFeatures and matchFeatures when necessary.


• IplImage* compositeImages(IplImage *img1, IplImage *img2, cv::Mat h, Progressable *thread)
img1 and img2 are color images that you want to make into a panorama by applying the homography h, to img2. This function needs to determine the size of the output image and allocate the memory for it. You need to implement feathering and alpha blending in your own compositing routine.

If you're running into problems with your phone, check to see if the issue is addressed in the FAQ.

Allowed OpenCV Functions

You are allowed to use any of the basic math and input / output functionality provided by OpenCV or the c++ standard libraries. You are also allowed to use functions and classes related to the singular value decomposition and / or solving linear equations. You should not use any function that trivializes any portion of the project. Use your judgement. If you are unsure about whether or not you can use a function please email the staff.

Write up

Each group will produce a single hand in. Make sure you say who is in your group. Feel free to name your group, as well. Only one group member needs to run the handin script.

Describe your algorithm and any decisions you made to write your algorithm a particular way. Also discuss any extra credit you did. Feel free to add any other information you feel is relevant.

Because you are building a (hopefully) interactive system, it would be compelling to show videos of actual usage in different scenes.

Extra Credit

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

• (up to +5) Construct a panorama with more than two images.
• (up to +10) Instead of projecting your mosaic onto a plane, project it onto a sphere or cylinder.
• (up to +5) Creative use of image warping and compositing: add graffiti to a wall, project a movie onto a wall, etc..
• (up to +10) Panorama recognition: given a set of images that might form panoramas, automatically discover and stitch them together, in the spirit of Recognizing Panoramas which was developed into Autostitch software
• (up to +10) Automatically create globe panoramas
• (up to +5) Calibrate the n900 camera to remove radial distortion.

Graduate Credit

Groups contain mixtures of graduate and undergraduate students, so there are no distinct graduate requirements.

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:

• README - text file containing anything about the project that you want to tell the TAs
• code/ - directory containing all your code for this assignment
• html/ - directory containing all your html report for this assignment (including images)
• html/index.html - home page for your results

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

Rubric

• +25 pts: Matching feature points using acceleration and ratio-based outlier rejection
• +30 pts: Robustly recovering homographies using RANSAC
• +25 pts: Warping, rectifying and compositing images
• +20 pts: Write up with at least two panoramas from your own photos
• +20 pts: Extra credit (up to twenty points)
• -5*n pts: Lose 5 points for every time (after the first) you do not follow the instructions for the hand in format

Final Advice

• Start Early!
• Compare the results of your functions to the built in matlab functions maketform and imtransform.
• Have fun with this and be creative with your images

Credits

Project based on Noah Snavely's Computer Vision course at Cornell University. Handout written by Travis Webb and James Hays.

Good Luck!