Technical details

Introduction

Hobby panorama photography is the process of photographing two or more images from the same viewpoint, which share a part of their view. That is, they overlap, usually around 20%. With modern computer software it is possible to "stitch" this images together so they appear as one large image. With additional viewing software the experience of "looking around" can be simulated. The most popular opensource software for panorama creation is hugin. Autopano-SIFT is a helper program for use with hugin, to create control point information.

The control point creation normally works through the manual work of the user, who tells the program exactly at which points the images share a common feature, much like ("the corner of the house is here in this picture, and there in that picture"). This process is called control point creation and takes a lot of time. With more images and multi-line panoramas (those that contain a second row of images) this is even more cumbersome, and one can spend a few hours just setting the control points.

SIFT Keypoints

The SIFT algorithm is a powerful algorithm to extract information from a real-world image. SIFT - Scale-Invariant Feature Transform - can, given the image, identify interesting points on the image ("features") and provide a signature for each such point. The signature can be saved to a file in a compact format. Later, this signatures can be compared against signatures from other images and questions such as "Is a similar object present in both images?" can be answered.

The SIFT algorithm provides the following key advantages over similar algorithms:

SIFT is an invention of David Lowe, and the mathematical details are described in the following papers:

Image matching

For every image autopano-sift generates a set of SIFT keypoints. All keypoints are merged into a large tree. The tree is an ordinary kd-tree with a rather high dimensionality (128 dimensions).

For every point a "nearest neighbour" is searched for. Nearest means that the keypoint descriptor differs only slightly from the point's descriptor. As normal kd-tree searching is impractical due to the high dimensionality, we use a special algorithm for high dimension search, called BBF - Best Bin First. However, this searching step is still the most time consumptive and forbids real-time application use of the SIFT algorithm.

The succesful matches are grouped into partitions, one for each possible image combination. Every partition has to contain at least three matches, else it is discarded. Afterwards the matches within the partition are checked for geometric consistency, using an algorithm called RANSAC - RANdom SAmple Consensus.

From the remaining matches, the control points are created.

Image match model

The RANSAC algorithm used for geometric checking requires a match "model" which can judge about the quality of a match. I have created a very simple yet practical and effective model for this. As the description of it uses some equations, I put it up in PDF format. I request comments and ideas for improvements, so please feel free to tell me your opinion on it.
matchmodel.pdf (130kb) - Matching model explanation

Automatic pre-aligning

With just the control point information the positions of the image has to be devised. Normally a program such as PTOptimizer is used to find a minimum-error configuration for the image positions. However, the optimizer uses heuristics which are prone to error in case a lot of information and completely unaligned images are used. As such, it is often necessary to provide a rough alignment of the images before the optimization can take place. Autopano-SIFT just tries to find such a pre-alignment automatically. It does this by exploiting known information about the images to order them on a horizon row. For this to work, the first images have to build a strict left-to-right or right-to-left order row on the horizon. The remaining images can be in arbitrary order.

The algorithm is as follows:

  1. The first two images are used to derive the direction (left-to-right or right-to-left) and to anchor the horizon line. The third image is selected as the current image, the previous image is the second one.
  2. The current image matches are compared with the previous image. If the current image is not on the horizon line, go to step 4.
  3. Set previous image to the current image and current image to the next input image. If there are no images left, go to step 6, else go to step 2.
  4. Estimate the current image position according to all other images already aligned.
  5. Set current image to the next available input image and go to step 5. If there are no input images left, go to step 6.
  6. Terminate.

After the algorithm finishes, all input images which are in a connected component with images on the horizon row are aligned.

Return to autopano-sift main page.