Scale Invariant Region Detection

Scale Invariant Region Detection

• Harris and Hessian detectors are repeatable only up to small scale changes.
• Differences in image scale between test images yield different extracted structures.
• Scale-invariant feature extraction requires reliably detecting structures under scale changes.

Automatic Scale Selection

• For an image pair, it finds if surrounding image neighborhoods share the same structure despite an unknown scale factor.
• Achieved by sampling each image neighborhood at various scales and making N × N pairwise comparisons.
• This is too computationally expensive.
• Instead, a signature function is evaluated on each sampled image neighborhood, with plotted results.
• Signature functions are measures of local image neighborhood properties at a radius, it takes a similar qualitative shape when centered on related image structures.
• Scaling between two images results in one function shape being squashed or expanded over the other.
• Search for the extrema of the signature function in both images to detect corresponding neighborhood sizes.
• The goal is to evaluate a scale-dependent signature function at a keypoint neighborhood to plot its resulting value versus the scale. If the two key points match, their signature functions will have similar shapes.

Laplacian-of-Gaussian (LoG) Detector

• Builds on the previous idea, searching scale space extrema of a scale-normalized Laplacian-of-Gaussian (LoG).
• Proposed by Lindeberg in 1998.
• The LoG filter mask has a circular center-surround structure where the centre has positive weights and the ring has negative ones.
• It yields maximum responses when used to an image neighborhood with a similar (roughly circular) blob structure on a related scale.
• Scale-space extrema of the LoG detects circular blob structures.
• For such blobs, a repeatable keypoint location is the blob center.
• LoG finds the characteristic scale location and directly identifying scale-invariant regions via 3D extrema of LoG.

LoG as a Scale Selection Filter

• The scale-normalized Laplacian-of-Gaussian (LoG) is a popular choice for a scale selection filter.
• A 2D filter mask is shaped like a circular center with positive weights and a surrounding circular region with negative weights.
• The filter responds most to circular structures whose radius is equal to the filter scale.

Difference-of-Gaussian (DoG) Detector

• Lowe (2004) suggested that the scale-space Laplacian can be approximated by a Difference-of-Gaussian (DoG) D(x, σ), which more efficiently is obtained from the difference of two adjacent scales separated by a factor of k.
• Lowe (2004) shows that the computation already includes the scale normalization if the factor is constant.
• One can divide each scale octave into K intervals, where k = 2^(1/K) and ση = k^η σ₀.
• DoG provides a fine approximation for the Laplacian-of-Gaussian.
• Computation is efficient by subtracting adjacent scale levels of a Gaussian pyramid.
• The DoG region detector seeks 3D scale space extrema of the DoG function.
• The regions obtained are similar to those of the LoG detector.
• The DoG detector is preferred due to its efficient computation.

Examples of Detector Results

• Examples included a Hessian detector (top left)
• Harris detector (top right)
• Laplacian-of-Gaussian detector (bottom left)
• Difference-of-Gaussian detector (bottom right)

Harris-Laplacian Detector

• The Harris-Laplacian operator, as created by Mikolajczyk & Schmid (2001, 2004), increases discriminative power relative to Laplacian or DoG operators.
• It merges the Harris operator's specificity for corner-like structures with Lindeberg's (1998) scale selection mechanism.
• This Method first develops two independent scale spaces for the Harris function and the Laplacian.
• The Harris function localizes candidate points at each scale level.
• Selects those points for which the Laplacian has an extremum over scales.
• The result are points being robust to scale, image rotation, lighting, and camera noise.
• They also are discriminative, per comparative studies (Mikolajczyk & Schmid 2001, 2003).
• A drawback is that the Harris-Laplacian detector generates fewer points than Laplacian or DoG detectors do.
• A lower number of regions potentially reduces robustness to partial occlusion during practical object recognition.
• Updated versions use a less strict criterion.
• Mikolajczyk & Schmid refined the detector (2004).
• Rather than looking for simultaneous maxima, this selects scale maxima of the Laplacian at locations where the Harris function has a maximum at any scale.
• This concept applies to the Hessian, creating the Hessian-Laplace detector (Mikolajczyk et al. 2005).

Affine Covariant Region Detection

• Goal to extend the region extraction to affine covariant regions.
• Affine transformation turns an invariant circle to an ellipse.
• Local regions must allow reliable and repeatable ellipse extractions using local image data.

Harris and Hessian Affine Detectors

• Both Harris-Laplace and Hessian-Laplace detectors expand to affine covariant regions.
• Done with an iterative estimation scheme.
• The process begins with a circular region from the scale-invariant detector.
• In each iteration, the region's second-moment matrix is constructed.
• Calculates the eigenvalues of this matrix to get an elliptic form that yields local transformation.
• Image neighborhood is transformed so the ellipse becomes a circle to update location and scale in the transformed image.
• Repeated until the second-moment matrix's eigenvalues are equal.

Maximally Stable Extremal Regions (MSER)

• This approach starts from a segmentation perspective, contrasting with keypoint-centric methods.
• It uses a watershed segmentation on the image, extracting homogeneous intensity regions stable over a range of thresholds
• results in Maximally Stable Extremal Regions (MSER).
• By construct, these regions maintain stability within imaging conditions and withstand viewpoint changes.
• Regions are unrestricted to elliptical shapes and may have complex outlines due to their segmentation-based design.

Orientation Normalization

• Once a scale-invariant region is detected, normalize its content for rotation invariance.
• Normalization is done through finding the region's dominant orientation and rotating the content by this angle to achieve a canonical orientation.
• Lowe (2004) suggests the following steps for orientation normalization:
• For each detected interest region, the region's scale selects the Gaussian pyramid's closest level so all following calculations are performed to have scale invariance.
• Build a gradient orientation histogram with 36 bins in 360°.
• For a region's pixel, the associated gradient orientation enters the histogram, weighting by the pixel's gradient magnitude and a Gaussian window with a scale of 1.5σ, centered on the keypoint.
• The orientation histogram's highest peak is the dominant orientation, and a parabola fits to the histogram's three bins to interpolate peak location for better accuracy.