Editing Scale-invariant feature transform (section)

{{Short description|Feature detection algorithm in computer vision}}
{{FeatureDetectionCompVisNavbox}}

The '''scale-invariant feature transform''' ('''SIFT''') is a [[computer vision]] algorithm to detect, describe, and match local ''[[Feature (computer vision)|features]]'' in images, invented by [[David G. Lowe|David Lowe]] in 1999.<ref name="Lowe1999" /> Applications include [[Outline of object recognition|object recognition]], [[robotic mapping]] and navigation, [[image stitching]], [[3D modeling]], [[gesture recognition]], [[video tracking]], individual identification of wildlife and [[match moving]].

SIFT keypoints of objects are first extracted from a set of reference images<ref name=Lowe1999 /> and stored in a database. An object is recognized in a new image by individually comparing each feature from the new image to this database and finding candidate matching features based on [[Euclidean distance]] of their feature vectors. From the full set of matches, subsets of keypoints that agree on the object and its location, scale, and orientation in the new image are identified to filter out good matches. The determination of consistent clusters is performed rapidly by using an efficient [[hash table]] implementation of the generalised [[Hough transform]]. Each cluster of 3 or more features that agree on an object and its [[Pose (computer vision)|pose]] is then subject to further detailed model verification and subsequently outliers are discarded. Finally the probability that a particular set of features indicates the presence of an object is computed, given the accuracy of fit and number of probable false matches. Object matches that pass all these tests can be identified as correct with high confidence.<ref name="Lowe2004" />

Although the SIFT algorithm was previously protected by a patent, its patent expired in 2020.<ref name="patent" />