Scale Invariant Region Detection

• Visual Recognition Lecture 2 by Dr. Shaheera Rashwan

Scale Invariant Region Detection

• Harris and Hessian detectors return locations that are only repeatable up to relatively small-scale changes.
• If the image scale differs too much between test images, the extracted structures will also differ.
• Detecting structures reliably extracted under scale changes is necessary for scale-invariant feature extraction.

Automatic Scale Selection

• Determine whether surrounding image neighborhoods contain the same structure, up to an unknown scale factor, given a keypoint in each image of an image pair.
• Sampling each image neighborhood at a range of scales and performing N×N pairwise comparisons finds the best match, though this is too expensive for practical use.
• Evaluate a signature function on each sampled image neighborhood and plot the result value as a function of the neighborhood scale.
• A signature function measures properties of the local image neighborhood at a certain radius.
• If two keypoints are centered on corresponding image structures, the signature function should take a similar qualitative shape.
• Scaling factors between two images result in one function shape being squashed or expanded compared to the other.
• Corresponding neighborhood sizes can be detected by searching for extrema of the signature function independently in both images.
• If the 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.

The 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) (Lindeberg 1998).
• The LoG filter mask corresponds to a circular center-surround structure.
• The center region has positive weights, and the surrounding ring structure has negative weights.
• It yields maximal responses when applied to an image neighborhood containing a similar (roughly circular) blob structure at a corresponding scale.
• Circular blob structures can be detected by searching for scale-space extrema of the LoG.
• For such blobs, a repeatable keypoint location can be defined as the blob center.
• The LoG can find the characteristic scale for a given image location.
• The LoG can detect scale-invariant regions directly by searching for 3D (location + scale) extrema of the LoG.
• The Laplacian-of-Gaussian (LoG) is a popular choice for a scale selection filter.
• A 2D filter mask takes the shape of a circular center region with positive weights, surrounded by another circular region with negative weights.
• The filter response is strongest for circular image structures whose radius corresponds to the filter scale.

The Difference-of-Gaussian (DoG) Detector

• The scale-space Laplacian can be approximated by a difference-of-Gaussian (DoG) D(xg), which can be more efficiently obtained from the difference of two adjacent scales that are separated by a factor of k, as shown by Lowe (2004).
• When the factor is constant, the computation already includes the required scale normalization, according to Lowe (2004).
• Each scale octave can be divided into an equal number K of intervals, such as k = 2^(1/K) and ση = k^ησο.
• 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 since it can be computed far more efficiently.

Harris-Laplacian Detector

• The Harris-Laplacian operator (Mikolajczyk & Schmid 2001, 2004) was proposed to increase the discriminative power compared to the Laplacian or DoG operators described so far.
• Problem with LoG and DoG: They detect too many blob-like features.
• Solution: Combine Harris detector (corner detection) with LoG (scale selection).
• It combines the Harris operator's specificity for corner-like structures with the scale selection mechanism by Lindeberg (1998).
• The method first builds up two separate scale spaces for the Harris function and the Laplacian.
• It then 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.
• They are also highly discriminative, according to several comparative studies (Mikolajczyk & Schmid 2001, 2003).
• The original Harris-Laplacian detector typically returns a much smaller number of points than the Laplacian or DoG detectors.
• For many practical object recognition applications, the lower number of interest regions may be a disadvantage, reducing robustness to partial occlusion.
• For this reason, an updated version of the Harris-Laplacian detector has been proposed based on a less strict criterion (Mikolajczyk & Schmid 2004).
• Instead of searching for simultaneous maxima, it selects scale maxima of the Laplacian at locations for which the Harris function also attains a maximum at any scale.
• As in the case of the Harris-Laplace, the same idea can also be applied to the Hessian, leading to the Hessian-Laplace detector (Mikolajczyk et al. 2005).

Affine Covariant Region Detection

• The aim is to extend the region extraction procedure to affine covariant regions.
• A scale- and rotation-invariant region can be described by a circle, but an affine deformation transforms this circle to an ellipse.
• 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.
• This is done by the following 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 of this matrix are computed.
  • This yields an elliptical shape that represents a local affine deformation.
  • The image neighborhood is transformed such that this ellipse is transformed to a circle.
  • The location and scale estimate are 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 the above methods, which start from keypoints and progressively add invariance levels, this approach starts from a segmentation perspective.
• It applies a watershed segmentation algorithm to the image.
• It extracts homogeneous intensity regions which are stable over a large range of thresholds, thus ending up with Maximally Stable Extremal Regions (MSER).
• Regions are stable over a range of imaging conditions.
• They can be reliably extracted under viewpoint changes.
• Since they are generated by a segmentation process, they are not restricted to elliptical shapes and can have complicated contours.

Orientation Normalization

• After a scale-invariant region has been detected, its content needs to be normalized for rotation invariance.
• By finding the region's dominant orientation and then rotating the region content according to this angle, the region is brought into a canonical orientation.

Lowe (2004) Orientation Normalization Step

• For the orientation normalization step, Lowe (2004) suggests the following procedure:
  • For each detected interest region, the region's scale is used to select the closest level of the Gaussian pyramid, so that all following computations are performed in a scale-invariant manner.
  • A gradient orientation histogram with 36 bins covering the 360° range of orientations is built up.
  • For each pixel in the region, the corresponding gradient orientation is entered into the histogram.
  • It is weighted by the pixel's gradient magnitude.
  • It is also weighted 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.