Scale-Space Representation and SIFT

Harris is a keypoint detector that is not invariant to scale changes. To overcome this limitation, Lindeberg (Lin94,Lin14) introduced the concept of automatic scale selection, making it possible to detect keypoints at a given resolution level. The pyramid representation of a scene, a computationally efficient algorithm that had previously been widely used, is in fact a special case of this scale-space representation.

Let $G(x,y;t)$ be the two-dimensional Gaussian with variance $t > 0$, given by

$$G(x,y;t) = \frac{1}{2\pi t} e^{-\frac{x^{2}+y^{2}}{2t} }$$ (6.7)

(see Section 2.2).

The convolution $L(x,y;t)$ between the image $I(x,y)$ and the Gaussian $G(x,y;t)$

$$L(x,y;t) = G(x,y;t) \ast I(x,y)$$ (6.8)

generates the scale-space representation of the image. The variance $t=\sigma^2$ of the Gaussian kernel is called the scale parameter. The image representation at the degenerate scale $t=0$ is the original image itself.

It should be noted that applying a Gaussian filter to an image does not create new structures: all the information generated by the filter was already contained in the original image.

Figure 6.2: Scale-space representation of an image $512 \times 512$: from the original image $t=0$ to scales 1, 4, 16, 64, and 256.

The scale factor $t$ is a continuous quantity, but for computational reasons, discrete steps of this value are used, normally in exponential sequences, such as $t=2^i$ or $t=\frac{1}{2} e^{i}$.

Applying a derivative operator to a scale-space image, by the commutative property of convolution and differentiation, is equivalent to convolving the original image with the derivative of the Gaussian:

$$L_{x^{\alpha}}(\cdot ; t) = \partial_{x^{\alpha}}L(\cdot; t) = (\partial_{x^{\alpha}} g(\cdot; t) ) \ast f(\cdot)$$ (6.9)

where $\alpha$ denotes the multi-index notation for the derivative. In the same way, the definition of all edge or keypoint filters can be extended to any scale factor. Through Lindeberg's work, it became possible to extend the concept of Harris Corners to scale-invariant cases (the Harris-Laplace and Hessian-Laplace methods (MS02)).

Some interesting operators for finding keypoints are, for example, the gradient magnitude $\vert\nabla L\vert$, the Laplacian $\nabla^{2} L$, and the Hessian determinant $\det \mathcal{H}(L)$. All these operators are rotation invariant, meaning that the location of the minimum or maximum is independent of the rotation applied to the image.

Among these operators, one widely used for detecting keypoints is the scale-normalized Laplacian of Gaussian (LoG) (scale-normalized Laplacian operator):

$$\nabla_{n}^{2} L(x,y,t) = t(\frac{\partial^2}{\partial x^{2... ...( 1 - \frac{x^2 + y^2}{2t} \right) e^{-\dfrac{x^2 + y^2}{2t} }$$ (6.10)

Using the LoG operator, keypoints can be identified as local maxima or minima in the spatial and scale coordinates.

For example, a circle with radius $r$ has its maximum Laplacian response at scale factor $\sigma = r / \sqrt{2}$.

Figure 6.3: Comparison between the normalized LoG image (a) and DoG (b)

(a)	(b)

In the Scale-invariant feature transform (SIFT) algorithm, Lowe (Low04) approximates the Laplacian of Gaussian (LoG) with a Difference of Gaussians (DoG) to improve performance:

$$\begin{array}{rl} D(x,y;\sigma) & = (G(x,y;k\sigma ) - G(x,... ...ma) \\ & \approx (k-1) \sigma^2 LoG(x,y;\sigma) \end{array}$$ (6.11)

This procedure is more efficient because the Gaussian image at scale $k\sigma$ can be computed from the Gaussian image $\sigma$ by applying a filter $(k-1)\sigma$, which is smaller and therefore considerably faster overall than performing the convolution $k\sigma$ with the original image.

Whereas in LoG the keypoints were the local minima/maxima, both in space and scale, of the Laplacian image, in this case the keypoints are the minima and maxima in the difference image between the scale images $\sigma, k\sigma, \ldots, k^n\sigma$ through which the image is processed (Figure 6.4).

Figure 6.4: Detection of local minima and maxima: for each pixel and each scale, a neighborhood $3\times 3\times 3$ is compared.

With the introduction of the step $k$, the domain of the variable $\sigma$ is effectively divided into discrete logarithmic steps, grouped into octaves, and each octave is divided into $S$ sublevels. Thus, $\sigma$ assumes the discrete values

$$\sigma(o,s) = \sigma_0 2^{o + \frac{s}{S}} \leftrightarrow k=2^{\frac{1}{S}}$$ (6.12)

where $\sigma_0$ is the base scale factor.

The keypoints, found as maxima/minima in scale and space, both of which are discrete, are interpolated using a three-dimensional quadratic regression to determine the keypoint with subpixel and subscale accuracy.

Between one octave and the next, the image is downsampled by a factor of 2: in addition to the multiscale analysis within each octave, the image is processed again in the next octave by halving its horizontal and vertical dimensions, and this procedure is repeated several times.

The second stage of a keypoint detection and matching algorithm consists of extracting a descriptor for comparison, centered on the detected keypoint. In practice, to be scale invariant, the descriptor must be extracted at the same scale factor associated with the keypoint.

To be rotation invariant, however, the descriptor must be extracted from an image that has undergone some form of normalization with respect to the dominant direction determined in the neighborhood of the point being evaluated.

From this image, rotated to the keypoint's scale, it is possible to extract a descriptor that emphasizes edges in the neighborhood and is ultimately invariant to illumination.

Among the numerous variants, PCA-SIFT should be mentioned; it uses PCA to reduce the dimensionality of the problem to a descriptor containing only 36 elements. PCA is used in a prior training stage.