SURF

The Speeded Up Robust Features algorithm (BETVG08) draws on the SIFT algorithm and the theory of scale-space representations to propose an optimized version that uses approximated Hessians based on 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 with respect to rotation when the descriptor is extracted.

In SURF, keypoints are detected by computing local maxima 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)

the image formed by convolving the second-order derivatives of a Gaussian with variance $t=\sigma^2$ and the image at point $(x,y)$. For performance reasons, the Gaussian derivatives are quantized to integer values 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 the element of the matrix $\mathcal{H}$.

The bandwidth of these approximated 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 one, 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 attempts to compensate for the various rounding errors, and is normally set to the constant $w=0.912$. The determinant is finally normalized with respect to the size of the scale involved so that it can be compared across different scales.

The image is analyzed over several octaves (each octave has a scale factor twice that of the preceding octave). Each octave is divided into the same number of scale levels. The number of scales per octave is limited by the strictly quantized nature of the filter, and the approximated Gaussians are not as evenly spaced as in SIFT. In fact, 4 intervals per octave is the only possible number of subdivisions.

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

From the maxima thus detected, again using the integral image, the dominant orientation in the neighborhood of the point is extracted (a neighborhood with radius $6s$, sampled at intervals of $s$). In this case as well, Haar features with side length $4s$ are used and weighted with a Gaussian having distribution $\sigma=2s$.

Using the orientation information, a descriptor based on gradient directions is generated by sampling an area in a neighborhood of $20s$, divided 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.