SURF: Speeded Up Robust Features

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