Implementation description

In this project I implemented panorama stitching. This algorithm has two phases, automatically recovering homographies and stitching the panoramas. The first step can be performed by hand using a matlab function provided by the TA's in which four points defining the homography are specified on each image by hand. Once a homography is chosen, the second image is warped and overlayed with the first image.

In order to automaically detect the homography the following pipeline is employed

• A Harris interest point detector is run on both images to produce a high recall list of possible interest points.
• A smaller list of interest points is selected from the large set using adaptive non-maximal suppression. This intuitively says that given a suppression radius an interest point will suppress all other points within that radius which fall below some threshold (.9 in my implementation) of its importance value as assigned by the harris point detector. If we decide that we want to trim the list down to a maximum length (1000 in my implementation), we can reformulate the problem by creating an ordered list of points which would be included in order of increasing suppression radius, and then truncate the list to the desired length.
• With this list of interest points, I then extract a feature vector describing the interest point. In my implementation this is a 9x9 tile centered at the location of the interest point. Using a provided function for squared euclidian distance, I calculate a distance value for all pairs of points between the two images. This matrix is then thresholded and all distance which pass under the threshold are recorded as possible mappings. The threshold employed is on the ratio between the best match and second best match for an interest point in the first image. I used .5 as the threshold, so this means that good matches are those in which the first interest points nearest neighbor has at most half the distance as the second nearest neighbor are used as good matches.
• Finally, I used RANSAC to recover four pairs of points which define the homography. This involves randomly sampling 4 mappings from the set determined in the previous step. For each sample, a homography is calculated and then all points in the previous step's mapping list are transformed with this homography. If more than 14 points are transformed to a location within .5 pixels from their image in the mapping, the homography is accepted. 14 is used because the four points which were sampled will automatically be transformed with zero error, so it is required that at least 10 other points also be transformed correctly.

Images

The following images' homographies were all obtained automatically.