The scale-invariant feature transform (SIFT) is a computer vision algorithm for detecting, describing, and matching local features in images, invented by David Lowe in 1999. It enables robust object recognition under scaling, rotation, and illumination changes, with applications including object recognition, robotic mapping and navigation, image stitching, 3D modeling, gesture recognition, video tracking, individual identification of wildlife, and match moving.
SIFT extracts keypoints from reference images and stores them in a database. To recognize an object in a new image, each feature is compared against the database using Euclidean distance of feature vectors, and consistent clusters of matches are identified via an efficient hash table implementation of the generalized Hough transform. Clusters of three or more features are verified, and the probability of correct matches is computed. The algorithm was developed by Lowe over a decade of tinkering; its patent expired in 2020.
Overview
For any object in an image, important points can be extracted to provide a feature description. This description, taken from a training image, can locate the object in a new image containing other objects. Features must be detectable despite scaling, noise, and illumination changes, often lying on high-contrast regions like edges. Relative positions between features should remain consistent across images; for example, using only door corners works regardless of position, but points on the frame fail if the door moves. SIFT uses many features, reducing the impact of local variations on matching errors.
SIFT robustly identifies objects under clutter and partial occlusion because its descriptor is invariant to uniform scaling, orientation, and illumination changes, and partially invariant to affine distortion. The descriptor is based on image measurements in terms of receptive fields, with local scale invariant reference frames established by scale selection.
Types of features
SIFT features are local, based on appearance at interest points, and invariant to scale and rotation. They are robust to illumination changes, noise, and minor viewpoint changes. They are highly distinctive, easy to extract, and allow correct identification with low mismatch probability. Matching against large databases uses probabilistic algorithms like k-d trees with best-bin-first search due to high dimensionality. As few as three SIFT features can compute an object's location and pose, enabling close-to-real-time recognition on modern hardware.
Stages
Scale-invariant feature detection
Lowe's method transforms an image into a collection of feature vectors invariant to translation, scaling, and rotation, partially invariant to illumination, and robust to geometric distortion. These features resemble neurons in the primary visual cortex that encode basic forms for object detection in primate vision. Key locations are maxima and minima of the difference of Gaussians function in scale space, applied to smoothed and resampled images. Low-contrast candidates and edge responses are discarded, and dominant orientations are assigned. Descriptors robust to affine distortion are obtained by blurring and resampling local orientation planes around key locations.
Feature matching and indexing
Indexing stores SIFT keys and identifies matches from new images. Lowe used best-bin-first search, a modified k-d tree algorithm that finds nearest neighbors with high probability using limited computation, searching bins in order of distance from the query via a heap-based priority queue. For each keypoint, the nearest neighbor in the database is found by minimum Euclidean distance. Candidates are kept if the ratio of the distance to the closest different-class feature is sufficiently large, ensuring distinct object classes don't clutter matches. Consistent clusters are then verified.
Applications and Impact
SIFT has been widely adopted in computer vision, influencing fields like Artificial intelligence and Machine learning. Its robustness made it a standard for object recognition before deep learning approaches like Deep learning and Neural network methods became prevalent. The algorithm's expiration of patent protection in 2020 facilitated broader use in commercial and research applications.
SIFT's principles also inspired later feature descriptors and contributed to advances in Computer vision (not in provided list, so omitted) and robotics, particularly in Waymo and Tesla for navigation. Its ability to handle partial occlusion and clutter remains valuable in scenarios like wildlife identification and match moving in film production.
Legacy
Despite the rise of learned features from Deep learning models, SIFT remains a foundational technique, often used as a baseline in feature matching benchmarks. Its theoretical basis in scale-space theory continues to inform research in image analysis. The algorithm's development over ten years exemplifies iterative refinement in computer vision, and its expiry of patent protection has encouraged innovation in related areas.