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.
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
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.
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
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.
Everybody likes screenshots.
DemonstrationBut 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.
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
- 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:
|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)