libsift - Scale-Invariant Feature Transform implementation

by Sebastian Nowozin (nowozin@cs.tu-berlin.de)

Introduction

This page is about a reusable computer program that can help in locating and using useful data about an image. Given the image, the program can 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.

This software is unusable on its own, and gives only a foundation upon which full programs can be build. One such program is my autopano-sift program, which can help in creating a single large image from many overlapping images.

Introduction for computer scientists

This library is a 100% C# implementation of the SIFT algorithm ("Scale-Invariant Feature Transform") and additional matching algorithms. The SIFT algorithm is an image feature location and extraction algorithm which 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.

Implementation

Requirements

a .NET runtime environment, I prefer Mono, using version 1.0 here
a fairly recent version of Gtk#, version ≥= 1.0 works for me
lots of RAM: The image transformations require a substantial amount of memory. 256Mb, or better yet, 512Mb make it fun.

Patent warning: 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.

Download

libsift 1.8, libsift-1.8.tar.gz (125kb)

Old versions

libsift 1.7, libsift-1.7.tar.gz (150kb)
libsift 1.6, libsift-1.6.tar.gz (150kb)
libsift 1.5, libsift-1.5.tar.gz (146kb)
libsift 1.4, libsift-1.4.tar.gz (147kb)
libsift 1.3, libsift-1.3.tar.gz (140kb)
libsift 1.2, libsift-1.2.tar.gz (125kb)
libsift 1.1, libsift-1.1.tar.gz (125kb)
libsift 1.0a, libsift-1.0a.tar.gz (115kb)
libsift 1.0, libsift-1.0.tar.gz (115kb)

License

Please read and acknowledge the license (GNU GPL) before running the software.

Donations

Developing libsift and the related autopano-sift software has required a considerable amount of time and effort. If you want to support further development, or if the library or program has been helpful to you, please consider making a small donation. Thanks!

Changes

Version	Changes
1.8-1.3	For the changelog, please see the autopano-sift page, thanks.
1.2	Fixes against the Gtk# library and Mono 1.0. Fix compatibility with the Microsoft .NET SDK compiler (csc).
1.1	Add a lot of support code to assist the autopano-sift package, such as RANSAC and a 2d image model. See the project page of autopano-sift for a detailed list of changes.
1.0a	Minor bugfix in MatchKeys functionality (null ref exception when no event handler had been registered.)
1.0	Initial release as separate library. The following changes are relative to autopano-sift-1.1. Add DoG peak threshhold. Add optional transparent gzip compression input/output to keypoint files. Change to use 0-255 byte descriptors instead of double. Improve default threshhold values. Improve matching code by replacing FPU intense code by integer code (150-200% as fast). Fix to use 3x3 Hessian instead of 2x2 to locate keypoints on subspace dimension. Fix to check for DoG peak value. Fix various smaller bugs.

Documentation and Usage

See the included README file. Except for inline comments there is no documentation yet. See the autopano-sift program and the included examples to understand the usage.

Feedback

I am curious about developer- and mathematicans feedback, so please mail me your thoughts to nowozin@cs.tu-berlin.de.

last update: Mon, 31 Oct 2005