ch Automatic Panorama Generation

Introduction

The objective of this panorama generation algorithm is to automatically stitch together different images of the same scene with overlapping elements. This is done by identifying corresponding points and then calculating the homographies for stitching the images together. It is assumed that the input images are actually overlapping photographs of the same scene, so that a panorama is actually possible. The part of this algorithm on matching points between images is based on (Brown, et al). Recovering the homography is based on RANSAC from (Fischler and Bolles) and the projective mapping descriptions in (Heckbert).


Automated Panorama Stitching Algorithm

The following steps describe stitching together 2 images. To stitch together N > 2 images, these steps need to be repeated to grow the panorama image iteratively, one additional image at a time.

  1. Find initial interest points
  2. A harris corner detector is performed on a single scale to identify the inital set of interest points from each image. This initial set of interest points needs to be pared down in the following steps, because it may contain many false matches.

  3. Apply adaptive non-maximum suppression

    Adaptive non-maximum suppression is used to rank the interest points identified in step 1. This is done by identifying for each point, the distance to the nearest interest point whose harris corner strength is 90% as large. The interest points are then ranked by minimum radius (from greatest to least) and up to the highest ranking 500 interest points are selected.

  4. Extract feature vectors from interest points

    Next, an 8x8 pixel feature vector is extracted from each interest point. This feature vector is created by sampling 64 pixels spaced 5 pixels apart in the local neighborhood of the interest point. To reduce antialiasing effects from this subsampling, an image pyramid is used. The resulting features are scale invariant but not rotation invariant.

  5. Find corresponding points with Lowe's ratio test

    Ater feature vectors from both images have been acquired, the features can be compared to find corresponding points. This comparison is done by computing the distances between all the features from one image to all the features in the other image, and then applying Lowe's ratio test. This ratio test involves dividing the first nearest neighbor distance with the second nearest neighbor distance for each feature. Only corresponding points where the ratio is under a parameterized threshold are kept.

  6. Approximate homography using RANSAC

    The best 4 pairs of corresponding points must now be found in order to compute the projective transformation from one image to the other. This projective mapping is solved using a linear system of equations as shown below, where the 4 pairs of corresponding points are mapping from (u,v) to (x,y):

    RANSAC or "Random Sample Consensus" is used to find the best corresponding points to compute this homography. For each RANSAC iteration, 4 randomly selected pairs of corresponding points are selected to compute this projective mapping. This homography is then applied to all corresponding points to measure its accuracy by counting the number of inliers. An inlier is defined as a point (u,v) where the projective mapping yields an error of at most half a pixel off the actual (x,y). After 10,000 RANSAC iterations, the homography that yields the most inliers is selected.

  7. Warp and composite images

    Next, the homography is used to warp the two images. Finally, the two images are then composited by simply averaging the overlapping regions.


Results from Original Images

The following results show the source images and the resulting panorama.

Source Images

Panorama

Source Images

Panorama


Results from Default Images

The following results show panoramas for the default images.