Scale Invariant Region Detection

• Visual Recognition Lecture 2 by Dr. Shaheera Rashwan

Scale Invariant Region Detection

• Harris and Hessian detectors' locations are repeatable up to relatively small-scale changes.
• Extracted structures from test images will also be different if images differ too much in scale.
• Detecting structures reliably extracted under scale changes is necessary for scale-invariant feature extraction.

Automatic Scale Selection

• Determine whether image neighborhoods contain the same structure up to an unknown scale factor, given a keypoint in each image of an image pair.
• Achieve this by sampling each image neighborhood at a range of scales and performing N × N pairwise comparisons to find the best match, which is too expensive for practical purposes.
• Signature function is instead evaluated on each sampled image neighborhood, and the result value is plotted as a function of the neighborhood scale.
• The signature function measures properties of the local image neighborhood at a certain radius, it takes a similar qualitative shape if the two keypoints are centered on corresponding image structures
• One function shape will be squashed or expanded compared to the other as a result of the scaling factor between the two images.
• Corresponding neighborhood sizes can be detected by searching for extrema of the signature function independently in both images.
• Evaluate a scale-dependent signature function on the keypoint neighborhood and plot the resulting value as a function of the scale.
• If the two keypoints correspond to the same structure, the 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) (Lindeberg 1998).
• The LoG filter mask corresponds to a circular center-surround structure with positive weights in the center region and negative weights in the surrounding ring structure.
• LoG yields maximal responses when applied to an image neighborhood that contains 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.
• Note that for such blobs, a repeatable keypoint location can also be defined as the blob center.
• The LoG can find the characteristic scale for an image location and 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 takes the shape of a circular center region with positive weights, surrounded by another circular region with negative weights.
• The filter response is therefore strongest for circular image structures whose radius corresponds to the filter scale.

Difference-of-Gaussian (DoG) Detector

• As shown by Lowe (2004), 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 that are separated by a factor of k.
• Lowe (2004) showed that when this factor is constant, the computation already includes the required scale normalization.
• 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.
• 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.
• The obtained regions are very similar to those of the LoG detector
• In practice, the DoG detector is often the preferred choice since it can be computed far more efficiently.
• The lecture gives examples of image filtering using Hessian, Harris, Laplacian-of-Gaussian and Difference-of-Gaussian detectors.

Harris-Laplacian Detector

• The Harris-Laplacian operator (Mikolajczyk & Schmid 2001, 2004) was proposed for increased discriminative power compared to the Laplacian or DoG operators described so far.
• The Harris operator's specificity for corner-like structures is combined with the scale selection mechanism by Lindeberg (1998).
• The method first builds up two separate scale spaces for the Harris function and the Laplacian.
• The Harris function is then used to localize candidate points on each scale level, and the points for which the Laplacian simultaneously attains an extremum over scales are selected.
• The resulting points are robust to changes in scale, image rotation, illumination, and camera noise.
• They are highly discriminative, as several comparative studies show (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.
• The lower number of interest regions may be a disadvantage and reduces robustness to partial occlusion for many practical object recognition applications.
• 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.
• While a scale- and rotation-invariant region can be described by a circle, an affine deformation transforms this circle to an ellipse.
• The aim is 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

• 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, which yields an elliptical shape (local affine deformation).
  • Transform the image neighborhood such that this ellipse is transformed to a circle and update the location and scale estimate in the transformed image.
  • This 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.
• Applies a watershed segmentation algorithm to the image and extracts homogeneous intensity regions that are stable over a large range of thresholds, resulting in Maximally Stable Extremal Regions (MSER).
• By construction, regions are stable over a range of imaging conditions and can still be reliably extracted under viewpoint changes.
• 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 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:
  • 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 is built up with 36 bins covering the 360° range of orientations.
  • For each pixel in the region, the 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, and a parabola is fitted to the 3 adjacent histogram values to interpolate the peak position for better accuracy.