Autopano-SIFT is a software solution that will make the creation of panorama images more fun

Panorama images are wide-angle images that amaze people: you often feel being inside the scene when watching a good panorama image. Creating such images is easy and everybody with a digital camera and a bit of patience can do it. Autopano-SIFT is there to make the creation of panorama images more fun.

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:

* Combined feature location and extraction algorithm.
* The keypoint locations are more precise and repeatable, because SIFT uses subpixel localization and multiple scale keypoint identification.
* The descriptors are highly distinctive. For example, I tested with up to 300,000 keypoints while matching a large 60 picture panorama and it did not have a single invalid match.
* The feature vectors can be efficiently correlated using probabilistic algorithms like Best-Bin-First kd-tree search.

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

* "Distinctive image features from scale-invariant keypoints" by David Lowe
Detailed description of the SIFT algorithm and how to efficiently implement it. Additionally there are empirical results to the parameters one should use.
* "Recognising panoramas" by Matthew Brown and David Lowe.
A more compact description how to use the SIFT feature detection algorithm as a base to build an efficient automatic panorama generation software on. Includes more advanced post-matching steps, such as Hough-transform filtering and also a pointer to the Best-Bin-First algorithm, an efficient probabilistic modification of the kd-tree algorithm (I also use BBF). See Matthew's panorama project page for some examples created with his original implementation.

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.

Example image

Almost everybody likes panorama images, and here is one of the pictures I created using my program,

The Juyong pass of the Great Wall of China

You can watch more images I made at www.behind-the-wall.org.

Details

Autopano-SIFT looks at your images and compares information about the images' content to order them correctly. Together with programs like hugin and enblend, you can create top-quality panorama images. The method autopano-sift uses to compare your images are described on another page describing technical details.

Screenshots

Everybody likes screenshots.

The new 2.0 Gtk# GUI

Automatic matches

Final blended images

Demonstration

But even better than screenshots, you can now watch an online demonstration that explains all the available options. The demonstration in flash format, and in html format.

Features
Autopano-SIFT takes many images and outputs PTO files which describe control point matches between the images.
It has the following features:

• SIFT - Scalable Invariant Feature Transform implementation to extract control points from images
• automatic pre-aligning of images
• sub-pixel coordinate precision for control point coordinates
• Linux, other Unix's and Windows supported
• GUIs:
  
  • Gtk# GUI
  • Windows native GUI
• Command line utilities
• 100% managed C# code, developed with Mono

The documentation is available in the tarball in form of manpages. Here you can find the latest documentation of the individual programs as PDF and in text format:

Program	Documentation
autopano-sift	Introduction: autopano-sift.pdf, autopano-sift.txt
autopano-complete.sh	Convenience script: autopano-complete.pdf, autopano-complete.txt
autopano-complete.old.sh	Convenience script (obsoleted version): autopano-complete.old.pdf, autopano-complete.old.txt
autopano	Match program: autopano.pdf, autopano.txt
autopanog	GUI: autopanog.pdf, autopanog.txt
generatekeys	SIFT key generation program: generatekeys.pdf, generatekeys.txt
showone	Key display program: showone.pdf, showone.txt
showtwo	Key match display program: showtwo.pdf, showtwo.

Notice: The SIFT algorithm is restricted by patents in the United States and hence this software is not completely free to use. For details see the LICENSE file included in the distribution, before you start to use this software. The University of British Columbia has applied for a patent on the SIFT algorithm in the United States. Commercial applications of this software may require a license from the University of British Columbia.

Please read and acknowledge the license (GPL) before running the software. A detailed changelog of autopano-sift is also available.

The latest version has been released on the 31th of October 2005. There is no updated 2.4 version for Windows yet.

• autopano-sift 2.4 MONO binaries and source (any Mono architecture),
  autopano-sift-2.4.tar.gz (640 kb)
  
  
  
  
  If you liked this article, subscribe to the feed by clicking the image below to keep informed about new contents of the blog: