SURF

The Speeded-Up Robust Features algorithm (BETVG08) draws on SIFT and scale-space theory to provide an optimized version that uses approximations of the Hessian computed with the integral image, both to detect keypoints and to extract their descriptors.

SURF is invariant to translation, scale, and rotation, but a simplified variant, called “U-SURF”, is invariant only to translation and scale changes: in this case, the region around the detected point is not normalized for rotation when the descriptor is extracted.

In SURF, keypoints are detected by finding local minima of the determinant of the Hessian image, defined as:

$$\mathcal{H}(x,y; t)=\begin{bmatrix} \frac{\partial}{\parti... ...in{bmatrix}D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$$ (6.13)

an image formed by convolving the image at point $(x,y)$ with the second derivatives of a Gaussian with variance $t=\sigma^2$. For performance reasons, the Gaussian derivatives are quantized to integers and approximated by rectangular regions (box filters); that is, some rectangular regions around the point are assigned positive weights, others negative weights, and their sum forms an element of the matrix $\mathcal{H}$.

The width of these approximate filters can be estimated as

$$\sigma = \frac{1.2}{9} l$$ (6.14)

where $l$ is the filter size. The filter $9 \times 9$, the smallest possible, for example, approximates the derivatives of a Gaussian with variance $\sigma=1.2$.

The determinant image is computed as

$$\det(\mathcal{H}) = D_{xx} D_{yy} - \left(w D_{xy} \right)^{2}$$ (6.15)

where $w$ is a factor that accounts for quantization and compensates for rounding errors, and is usually set to the constant $w=0.912$. The determinant is then normalized with respect to the size of the scale involved, so that it can be compared across different scales.

The image is analyzed over multiple octaves, each with a scale factor twice that of the previous octave. Each octave is divided into the same number of scale levels. The number of scales per octave is limited by the filter's strictly quantized nature, and the approximate Gaussians are not as evenly spaced as in SIFT. In practice, four intervals per octave are the only possible subdivision.

Within each octave, as the scale $s$ and position vary, Non-Maxima Suppression $3\times 3\times 3$ is performed on the determinant image of $\mathcal{H}$. The local minima and maxima, interpolated using a three-dimensional quadratic fit as in SIFT, are the SURF keypoints. The scale is set equal to the variance of the associated filter $s=\sigma$.

For the maxima thus found, the dominant orientation in the neighborhood of the point is extracted using the integral image (neighborhood of radius $6s$, sampled at intervals of $s$). Here too, Haar features with side length $4s$ are used and weighted with a Gaussian distribution $\sigma=2s$.

The orientation information is used to generate a descriptor based on gradient directions by sampling the region around $20s$, dividing it into $4 \times 4$ regions, and weighting the points with a Gaussian $\sigma=3.3s$. Within each region, $d_x$, $d_y$, $\vert d_x\vert$, and $\vert d_y\vert$ are computed. Both the orientation and the gradient histogram are extracted at the feature detection scale.