SURF: Speeded Up Robust Features

From David's Wiki
\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)
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