SURF: Speeded Up Robust Features

• Springer Link to Paper (ECCV 2006) Paywall
• Paper
• Mirror

Authors

• Herbert Bay - ETH Zurich
• Tinne Tuytelaars - Katholieke Universiteit Leuven
• Luc Van Gool - ETH Zurich, Katholieke Universiteit Leuven

Feature Extraction

Fast-Hessian Detector

Our features will be regions in the image where the determinant of the Hessian are local maxima.

Figure 1 from the paper. Each region can be computed using a summed area table/integral image.

• The Hessian matrix:

\(\displaystyle \mathcal{H}(\mathbf{x}, \sigma) = \begin{bmatrix} L_{xx}(\mathbf{x}, \sigma) & L_{xy}(\mathbf{x}, \sigma)\\ L_{xy}(\mathbf{x}, \sigma) & L_{yy}(\mathbf{x}, \sigma) \end{bmatrix}\)

• Each entry is a convolution of a the Gaussian second order derivative with the image at \(\displaystyle \mathbf{x}\)
• These convolutions are approximated using box filters on an integral image (Fig 1).

  The approximations are denoted as \(\displaystyle D_{xx}, D_{yy}, D_{xy}\)

• The determinant of the hessian is then \(\displaystyle D_{xx}D_{yy} - (0.9*D_{xy})^2\)
  • 0.9 is a correction term for the approximation

    \(\displaystyle \frac{|L_{xy}(1.2)|_{F}}{|L_{xx}(1.2)|_{F}}\frac{|D_{xx}(9)|_{F}}{|D_{xy}(9)|_{F}} = 0.912\)

• Interest points are local extrema of the determinant and trace of the Hessian

Scale-space representation

• They can increase (e.g. double) the filter size for their approximation and to get representations at multiple scales.
• They apply a "non-maximum suppression in a \(\displaystyle 3 \times 3 \times 3\) neighborhood" to "localise interest points in the image and over scales"
  • Non-maximum suppression is a filtering technique to remove duplicates

    Basic idea: Let B be a set of regions. Let D be the filtered set we want to output.

    Pick the max confidence region from set B to D. Remove it from B.

    For each region in B, delete it if the IOU with selected is > threshold.

    See non-maximum suppression

SURF Descriptor

Orientation Assignment

Figure 2 from the paper

• Sample Haar-wavelet responses in x and y-direction at points around each feature
  • Using integral images, only 6 operations are need to compute in x or y direction (Fig. 2 middle)

    We have 6 distinct corners so we need 6 fma operations in total for each direction. (Actually 5 if one value is just multiplied by 1)

• Using a 360-degree (pivoting) sliding window with radius \(\displaystyle \frac{\pi}{3}\), calculate the sum of all horizontal and vertical responses yielding vector. Note the window moves in increments of \(\displaystyle \frac{\pi}{3}\)
• Pick the direction with the largest vector.

Descriptor Components

• Create square regions positioned at feature points and oriented using the calculated orientation (Fig. 2 right)
• ...

OpenCV

SURF is available in OpenCV

Resources

• Medium Introduction