Skip to content
Search

Scale-invariant feature transform

lastmod 2022-07-12created 2019-12-066 edits

The scale-invariant feature transform (SIFT) is a feature detection algorithm in computer vision to detect and describe local features in images. It was patented in Canada by the University of British Columbia and published by David Lowe in 1999. Applications include object recognition, robotic mapping and navigation, image stitching, 3D modeling, gesture recognition, video tracking, individual identification of wildlife and match moving.

About

With the Harris Corner Detector, keypoints may or may not be detected depending on changes in scale. SIFT is an algorithm that can detect keypoints even when the scale changes.

  1. Detect Scale-Space Extrema: Build a Scale-Space and find every Key Candidate that can be found.
  2. Accurate Key Point: The Key Candidates passed from the previous step include Edges, Corners, Blobs, etc.; this step picks the highly important Edges, Corners, blobs, etc. among them.
    • Remove Low Contrast
    • Edge Thresholding
  3. Assign Orientation: Take a 16x16 patch centered on the Key and determine the Gradient Magnitude / Orientation. Then a Histogram is drawn; rather than using the Magnitude in each direction as-is, it is multiplied by a Gaussian weighted Function before being used in the Histogram. In other words, the Histogram is drawn with slightly larger weights near the center of the Key.
    • The direction of the Peak in the Histogram is taken as the Key Orientation; if there is another Peak at 80% or more of the Key orientation, it also becomes a Key Orientation.
  4. Key Point Descriptor: The Key Orientation was found in the previous step. This is where rotation invariance comes in. The found Key Orientation is rotated back to 0 degrees to build the Descriptor. That is, if the Key Orientation is 60 degrees, it is rotated back by 60 degrees so that the Key Orientation is set as the 0-degree reference. In this state, the 16x16 pixels are merged into 4x4 Cells, an 8-direction Histogram is drawn, and a 4x4x8 Descriptor is built. (Mainly 128Demension is used)
  5. Key Matching: Matching between the input image and the Descriptors. Compute the Euclidean distance between each Key and Descriptor to find the Key with the smallest (closest) value. At this point, the closest Key and the second-closest Key are compared, and if the difference is small, they are not used for Key matching.

See also

Favorite site

References

  1. Bskyvision_-_Scale_Invariant_Feature_Transform.pdf ↩

author Zer0 sitemap