Project 6 Writeup

Jarrell Travis Webb (jtwebb)
April 19th 2010

Alogrithm

This algorithm is somewhat more complicated than the others so we will break it down into separate parts. The overall plan is to take multiple overlapping images and stich them together into panoramas. The steps are as follows: 1) Find harris corners. 2) Perform a special brand of adaptive non-maximal supression on the corners to get evenly distributed interesting features. 3) Match interesting features across overlapping images. 4) Sift the features to find and remove false matches. 5) Find the transformation between the overlapping images. 6) Warp the images into place and composite them to create the panorama.
For testing purposes it is a good idea to have a manual system by which to choose features. A minimum of four points are required to recover a projective transformation because a projective transformation has eight free parameters. Projective transformations are sufficient to describe the warps between images taken from a single focal point. Once the user selects points we can exactly recover the transformation or homography between them and then use that to warp the coordinates of the coordinates of one image to exactly align with the other. We warp backwards to avoid holes in the warped image. Holes will occur when the warp defines coordinates for pixels that weren't in the original image. Warping backwards dodges this difficulty. Compositing is done trivially and looks nice enough because the matches are so strong.
Once we know we can make panoramas with help from users the remaining task is to automate the process. I don't know much about harris corners because they were implemented for us. What I do know is that they are interesting features of an image. Once we know where corners are we grab a window around the corner and normalize it so that we can try to find that same corner + window in the other images. To find corners in multiple images we look for the first two nearest neighbors in euclidean distance between the normalized windows (thought of as vectors). We take the ratio of the first two nearest neighbors and if that is less than a threshold we assume the corners match. We look for the ratio of the first two because we are searching not for corners that match well, but for corners that uniquely match well. However we still have too many erroneous matches so we use RANSAC to try to find a best fit. RANSAC selects data features randomly and assumes those corners are right. It then searches for features that corroborate that opinion. RANSAC runs for many iterations and keeps the solution with the lowest error. Now that we have the transformation we do exactly what we did when we had user help.

Panorama 1

Panorama 2

Panorama 3

Panorama 4