Scale Invariant Feature Extraction

Scale Invariant Region Detection

• Locations returned by the Harris and Hessian detectors are repeatable up to relatively small-scale changes.
• If an image scale differs too much between test images, extracted structures will be different.
• Scale invariant feature extraction requires detecting structures that can be reliably extracted under scale changes.

Automatic Scale Selection

• Given a keypoint in each image of an image pair, the goal is to determine whether surrounding image neighborhoods contain similar structure up to an unknown scale factor.
• Potential method includes sampling each image neighborhood at a range of scales and performing N × N pairwise comparisons to find the best match, but is too expensive for practical use.
• Instead, a signature function is evaluated on each sampled image neighborhood and its result is plotted as a function of the neighborhood scale.
• A signature function measures properties of the local image neighborhood at a certain radius.
• The signature function should take a similar qualitative shape if two keypoints are centered on corresponding image structures.
• The function shape will be squashed or expanded compared to the other based on the scaling factor between the two images.
• Corresponding neighborhood sizes are detected by searching for extrema of the signature function independently in both images.
• Given a keypoint location, a scale-dependent signature function is evaluated on the keypoint neighborhood, and the resulting value is plotted as a function of the scale.
• If two keypoints correspond to the same structure, their signature functions will take similar shapes.
• Corresponding 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 a detector for blob-like features that searches for scale space extrema of a scale-normalized Laplacian-of-Gaussian (LoG)
• The LoG filter mask corresponds to a circular center-surround structure.
• The structure uses 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 are detected by searching for scale-space extrema of the LoG.
• A repeatable keypoint location can be defined as the blob center for such blobs.
• The LoG can be applied to find the characteristic scale for a given image location.
• The LoG can be used to directly detect scale-invariant regions by searching for 3D (location + scale) extrema of the LoG.
• The scale-normalized Laplacian-of-Gaussian (LoG) is a popular choice for a scale selection filter.
• Its 2D filter mask has a circular center region with positive weights region, surrounded by another circular region with negative weights.
• The filter response is strongest for circular image structures whose radius corresponds to the filter scale.

Difference-of-Gaussian (DoG) Detector

• Lowe (2004) demonstrated that the scale-space Laplacian can be approximated by a difference-of-Gaussian (DoG).
• The DoG can be more efficiently obtained from the difference of two adjacent scales that are separated by a factor of k.
• When this factor is constant, the computation already includes the required scale normalization.
• Each scale octave can be divided into an equal number K of intervals.
• 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 searches for 3D scale space extrema of the DoG function.
• Obtained regions are very similar to those of the LoG detector.
• The DoG detector is often the preferred choice because it can be computed more efficiently.

Harris-Laplacian Detector

• The Harris-Laplacian operator (Mikolajczyk & Schmid 2001, 2004) increases discrimination compared to the Laplacian or DoG operators.
• Combines the Harris operator's specificity for corner-like structures with Lindeberg's scale selection mechanism (1998).
• It builds up two separate scale spaces for the Harris function and the Laplacian.
• Harris function is used to localize candidate points on each scale level.
• Points are selected 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.
• They are highly discriminative.
• The original Harris-Laplacian detector returns a much smaller number of points than the Laplacian or DoG detectors.
• Limited number of interest regions can be a disadvantage for many practical object recognition applications, such as robustness to partial occlusion.
• Due to this and other reasons, an updated version of the Harris-Laplacian detector has been proposed (Mikolajczyk & Schmid 2004).
• Instead of searching for simultaneous maxima, newer versions selects scale maxima of the Laplacian at locations for which the Harris function also attains a maximum at any scale.
• This idea can also be applied to the Hessian, leading to the Hessian-Laplace detector (Mikolajczyk et al. 2005).

Affine Covariant Region Detection

• Goal is to extend the region extraction procedure to affine covariant regions.
• Scale and rotation-invariant regions can be described by a circle, but an affine deformation transforms this circle to an ellipse.
• Local regions for which such an ellipse can be reliably and repeatedly extracted from local image properties must be found.

Harris and Hessian Affine Detectors

• Both the Harris-Laplace and Hessian-Laplace detectors can be extended to yield affine covariant regions.
• This is done 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 eigenvalues are computed to yield an elliptical shape (local affine deformation).
• Then 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.
• This process is repeated until the eigenvalues of the second-moment matrix are approximately equal.

Maximally Stable Extremal Regions (MSER)

• In contrast to other methods, that start from keypoints and progressively add invariance levels, MSER starts from a segmentation perspective.
• It applies a watershed segmentation algorithm.
• It extracts homogeneous intensity regions that are stable over a large range of thresholds (Maximally Stable Extremal Regions (MSER)).
• By construction, those regions are stable over a range of imaging conditions.
• MSER can still be reliably extracted under viewpoint changes.
• MSER is generated by a segmentation process and therefore is not restricted to elliptical shapes; it can have complicated contours.

Orientation Normalization

• Detected scale-invariant region's content needs to be normalized for rotation invariance.
• By finding the region's dominant orientation and rotating the region content according to this angle in order to bring the region into a canonical orientation.
• Lowe (2004) suggests the following procedure for the orientation normalization step:
• The region's scale is used to select the closest level of the Gaussian pyramid for each detected interest region.
• A gradient orientation histogram is built up with 36 bins covering the 360° range of orientations.
• Each pixel's corresponding 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.