7.4: Scale-Invariant Feature Transforms

Scale-invariant feature transforms are a class of algorithms/signalprocessing techniques that allow to extract features that are easily detectable across different scales (or distances to an object), independent of their rotation, and to some extent robust to affine transformations, i.e., views of the same object from different perspectives, and illumination changes. An early algorithm in this class is the SIFT algorithm (Lowe 1999), which however has lost popularity due to closed-source and licensing cost, and has been replaced in the past with SURF (Speed-Up Robust Feature) (?) and ORB (?), which are freely available and have slightly different performance and varying use cases. As the math behind SURF is more involved, we focus on the intuition behind SIFT and encourage the reader to download and play with the various open-source implementations of other feature detectors that are available open source.

Figure \(\PageIndex{1}\): Lines in an image (left) transposed into Hough-space ρ (distance from origin) and θ (angle of normal with respect to origin). Bright spots in the Hough image (right) correspond to parameters that have received the most “votes” and clearly show the two lines at around 90° and 180° .

7.4.1. Overview

SIFT proceeds in multiple steps. Descriptions of the algorithm often include its application to object recognition, but these algorithms are independent of feature generation (see below).

• Differences of Gaussians (DoG) at different scales:
• Generate multiple scaled versions of the same image by re-sampling every 2nd, 4th and so on pixel.
• Filtering each scaled picture with various Gaussian filters of different variance.
• Calculating the difference between pairs of filtered images. This is equivalent to a DoG filter.
• Detecting local minima and maxima in the DoG images across different scales (Figure 7.4.2, left) and reject those with low contrast (Figure 7.4.2, right).

Figure \(\PageIndex{2}\): After scale space extrema are detected (left), the SIFT algorithm discards low contrast keypoints (center) and then filters out those located on edges (right). © Lukas Mach CC-BY 3.0

• Reject extrema that are along edges by looking at the second derivative around each extrema (Figure 7.5, right). Edges have a much larger principal curvature across them than along them.
• Assign a “magnitude” and “orientation” to each remaining extrema (keypoint). The magnitude is the squared difference between neighboring pixels and the orientation is the angle between magnitude along the y-axis vs. magnitude along the x-axis. These calculations are made for all pixels in a fixed neighborhood around the initial keypoint, e.g., in a 16x16 pixel neighborhood.
• Collect orientations of neighboring pixels in a histogram, e.g., 36 bins each covering 10 degrees. Maintain the orientation corresponding to the strongest peak and associate it with the keypoint.
• Repeat 4th step, but for four 4x4 pixel areas around the keypoint in the image scale that has the most extreme minima/maxima. Here, only 8 bins are used for the orientation histogram. As there are 16 histograms in a 16x16 pixel area, the feature descriptor has 128 dimensions.
• The feature descriptor vector is normalized, tresholded, and again normalized to make it more robust against illumination changes.
• Local gradient magnitude and orientation are grouped into bins and create a 128-dimensional feature descriptor.

The resulting 128 dimensional feature vectors are now scale-invariant (due to step 2), rotation-invariant (due to step 5), and robust to illumination changes (due to step 7).

7.4.2. Object Recognition using Scale-Invariant Features

Scale-invariant features of training images can be stored in a database and can be used to identify these objects in the future. This is done by finding all features in an image and comparing them with those in the database. This comparison is done by using the Euclidian distance as metric and searching a kd tree (with d=128). In order to make this approach robust, each object needs to be identified by at least 3 independent features. For this, each descriptor stores the location, scale and orientation of it relative to some common point on the object. This allows each detected feature to “vote” for the position of the object that it is most closely associated with in the database. This is done using a Hough-transform. For example, position (2 dimensions) and orientation (1 dimension) can be discretized into bins (30 degree width for orientation); bright spots in Hough-space then correspond to an object pose that has been identified by multiple features.