Scale Invariant Region Detection

• Visual Recognition Lecture 2 was given by Dr. Shaheera Rashwan

Scale Invariant Region Detection

• Locations from Harris and Hessian detectors are repeatable only up to small-scale changes
• Extracted structures differ if image scale differs too much between test images
• Scale invariant feature extraction necessitates detecting structures 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 the same structure up to an unknown scale factor
• Sampling each image neighborhood at a range of scales and performing N × N pairwise comparisons to find the best match is too expensive to be practical
• Instead, we evaluate a signature function on each sampled image neighborhood
• Plot the result value as a function of neighborhood scale
• The signature function should take a similar qualitative shape if two keypoints are centered on corresponding image structures because it measures local image neighborhood properties at a certain radius
• The only difference will be that one function shape will be squashed or expanded compared to the other as a result of the scaling factor
• Corresponding neighborhood sizes are detected by searching for extrema of the signature function independently in both images
• The principle involves evaluating a scale-dependent signature function on the keypoint neighborhood and plotting the resulting value as a function of the scale
• Signature functions will take similar shapes for keypoints corresponding to the same structure, and 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 the LoG detector (1998) for blob-like features that searches for scale space extrema of a scale-normalized function
• 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
• 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 and to directly detect scale-invariant regions by searching for 3D (location + scale) extrema of the LoG
• The scale-normalized LoG is a popular choice for a scale selection filter
• Its 2D filter mask is 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

Difference-of-Gaussian (DoG) Detector

• According to Lowe(2004), the scale-space Laplacian can be approximated by a difference-of-Gaussian (DoG) D(x, σ), which can be obtained more efficiently by subtracting two adjacent scales separated by a factor of k
• Lowe (2004) shows that computation already includes the required scale normalization when this factor is constant
• Each scale octave can be divided into an equal number K of intervals
• The 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
• It is often the preferred choice as it can be computed far more efficiently

Harris-Laplacian Detector

• The Harris-Laplacian operator (Mikolajczyk & Schmid 2001, 2004) was proposed for increased 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)
• The method initially 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
• Comparative studies show that it is highly discriminative (Mikolajczyk & Schmid 2001, 2003)
• Original Harris-Laplacian detector returns a much smaller number of points than the Laplacian or DoG detectors
• As a result, for many practical object recognition applications, the lower number of interest regions may reduce robustness to partial occlusion
• An updated version 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
• This idea can also 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
• 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, we build up the region's second-moment matrix and compute the eigenvalues of this matrix to yield an elliptical shape (local affine deformation)
  • The image neighborhood is transformed such that this ellipse is transformed to a circle and we update the location and scale estimate in the transformed image.
  • The procedure is repeated until the eigenvalues of the second-moment matrix are approximately equal

Maximally Stable Extremal Regions (MSER)

• Begins from a segmentation perspective by progressively adding invariance levels from keypoints
• It 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)
• The regions are stable over a range of imaging conditions and can still be reliably extracted under viewpoint changes
• Generated by a segmentation process not restricted to elliptical shapes, but with complicated contours

Orientation Normalization

• After a scale-invariant region has been detected, its content needs to be normalized for rotation invariance
• It 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.
• We then build up a gradient orientation histogram 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 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