Scale Invariant Feature Extraction

Scale Invariant Region Detection

• Harris and Hessian detectors return locations repeatable up to relatively small-scale changes.
• If image scales differ, extracted structures differ.
• Scale invariant feature extraction requires detecting structures reliably extracted under scale changes.

Automatic Scale Selection

• Determines if neighborhoods in an image pair contain the same structure up to an unknown scale factor
• Achieved by sampling image neighborhood at a range of scales and performing N × N pairwise comparisons to find the best match, although it is too expensive for practical use
• Instead, a signature function is evaluated on each sampled image neighborhood, and the resulting value is plotted as a function of the neighborhood scale
• If two keypoints are centered on corresponding image structures, the signature function should take a similar qualitative shape
• The only difference is one function shape will be squashed or expanded due to the scaling factor between the two images.
• Corresponding neighborhood sizes are detected by independently searching for extrema of the signature function in both images.
• Automatic scale selection principle involves evaluating a scale-dependent signature function on the keypoint neighborhood and plotting the resulting value as a function of scale.
• If two keypoints correspond to the same structure, signature functions take similar shapes, and neighborhood sizes can be determined by searching for scale-space extrema of the signature function independently in both images.

Laplacian-of-Gaussian (LoG) Detector

• Lindeberg proposed that detector for blob-like features that searches scale space extrema of a scale-normalized Laplacian-of-Gaussian (LoG) (Lindeberg 1998)
• The LoG filter mask corresponds to a circular center-surround structure
• The filter mask has positive weights in the center region and negative weights in the surrounding ring structure
• It yields maximal responses if applied to an image neighborhood that contains a similar (roughly circular) blob structure at a corresponding scale
• Circular blob structures can be detected via scale-space extrema of the LoG
• A repeatable keypoint location can be defined as the blob center
• The LoG can find the characteristic scale for an image location and detect scale-invariant regions by searching for 3D extrema of the LoG.
• The scale-normalized Laplacian-of-Gaussian (LoG) is a popular choice for a scale selection filter
• The 2D filter mask takes the shape of a circular center region with positive weights, surrounded by another circular region with negative weights
• Filter response is strongest for circular image structures whose radius corresponds to the filter scale.

Difference-of-Gaussian (DoG) Detector

• The scale-space Laplacian can be approximated by a difference-of-Gaussian (DoG) D(x, σ) which can be more efficiently obtained from the difference of two adjacent scales separated by a factor of k (Lowe, 2004)
• When factor k is constant, then the computation includes the required scale normalization (Lowe, 2004)
• One can divide each scale octave into an equal number K of intervals such as k = 21/K and ση = κησο.
• The Difference-of-Gaussian (DoG) provides a good approximation for the Laplacian-of-Gaussian -It can be efficiently computed by subtracting adjacent scale levels of a Gaussian pyramid.
• The DoG region detector then searches for 3D scale space extrema of the DoG function
• The obtained regions are very similar to those of the LoG detector
• The DoG detector is often the preferred choice because it can be computed far more efficiently

Harris-Laplacian Detector

• The Harris-Laplacian operator (Mikolajczyk & Schmid 2001, 2004) aims to increase discriminative power compared to the Laplacian or DoG operators
• It combines the Harris operator's specificity for corner-like structures with the scale selection mechanism by Lindeberg (1998)
• Method builds up two separate scale spaces for the Harris function and the Laplacian
• It uses the Harris function to localize candidate points on each scale level and selects those points for which the Laplacian simultaneously attains an extremum over scales
• The resulting points are robust to changes in scale, image rotation, illumination, and camera noise
• Comparative studies show that they are highly discriminative (Mikolajczyk & Schmid 2001, 2003)
• The original Harris-Laplacian detector typically returns a much smaller number of points than the Laplacian or DoG detectors, which is a drawback
• A lower number of interest regions may be a disadvantage for many object recognition applications because it reduces robustness to partial occlusion.
• An updated version proposed (Mikolajczyk & Schmid 2004) selects scale maxima of the Laplacian at locations for which the Harris function also attains a maximum at any scale
• Instead of searching for simultaneous maxima
• The same idea can be applied to the Hessian, leading to the Hessian-Laplace detector (Mikolajczyk et al. 2005)

Affine Covariant Region Detection

• Aims to extend the region extraction procedure to affine covariant regions
• While a scale- and rotation-invariant region can be described by a circle, an affine deformation transforms this circle to an ellipse
• Aims to find local regions for which such an ellipse can be reliably and repeatedly extracted purely from local image properties

Harris and Hessian Affine Detectors

• Both the Harris-Laplace and Hessian-Laplace detectors can be extended to yield affine covariant regions through an iterative estimation scheme
• The procedure is initialized with a circular region returned by the original scale-invariant detector
• In each iteration, the region's second-moment matrix is built up, and the eigenvalues are computed which yields an elliptical shape (local affine deformation)
• The image neighborhood is transformed such that the ellipse is transformed to a circle, and the location and scale estimate is updated in the transformed image
• The procedure is repeated until the eigenvalues of the second-moment matrix are approximately equal

Maximally Stable Extremal Regions (MSER)

• In contrast to methods that add invariance levels from keypoints, MSER starts from a segmentation perspective
• Watershed segmentation algorithm is applied to the image, extracting homogeneous intensity regions stable over a large range of thresholds, thus resulting in Maximally Stable Extremal Regions (MSER)
• Regions are stable over a range of imaging conditions and can be reliably extracted under viewpoint changes by construction
• They are not restricted to elliptical shapes, but can have complicated contours since they are generated by a segmentation process

Orientation Normalization

• After a scale-invariant region has been detected, its content needs to be normalized for rotation invariance
• This is typically done by finding the region's dominant orientation and then rotating region content according to this angle to bring the region into a canonical orientation
• Lowe (2004) suggests using the region's scale to select the closest level of the Gaussian pyramid to perform all computations in a scale-invariant manner
• A gradient orientation histogram is built with 36 bins covering the 360° range of orientations
• For each pixel in the region, gradient orientation is entered into the histogram, weighted by the pixel's gradient magnitude and by a Gaussian window centered on the keypoint with a scale of 1.5σ
• The highest peak in the orientation histogram is taken as the dominant orientation
• A parabola is fitted to the 3 adjacent histogram values to interpolate the peak position for better accuracy