Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 46 ยท Features and Matching

Integral Images, SURF and SIFT Compared

Build an integral image, compute any box sum in four lookups, approximate the Hessian with box filters as SURF does, and compare SIFT, SURF and ORB side by side.

Feature detectors have to look at every pixel at many scales, so speed matters. The integral image (also called a summed-area table) is a small trick that makes one operation almost free: the sum of the pixels inside any rectangle, in a constant number of steps, whatever the size of the rectangle. It is the engine under the Viola-Jones face detector and under SURF (Speeded-Up Robust Features), the faster cousin of SIFT.

In this lesson you will build an integral image in NumPy, use it for box filters and local averages, see how SURF approximates the Hessian blob detector with boxes, and finish with a clear comparison of SIFT, SURF and ORB. Read Image Pyramids and Scale and Descriptors and Matching first if scale space and descriptors are new to you.

The integral image

Define I(x, y) as the sum of all pixels above and to the left of (x, y), including it. Each entry is built from its neighbours:

I(x, y) = pixel(x, y) + I(x - 1, y) + I(x, y - 1) - I(x - 1, y - 1)

That is two cumulative sums in NumPy: img.cumsum(axis=0).cumsum(axis=1). Now the sum of any rectangle needs only four values of I, the corners:

sum = I(bottom, right) - I(top - 1, right) - I(bottom, left - 1) + I(top - 1, left - 1)

You add the big rectangle from the origin, subtract the strip above and the strip on the left, and add back the corner you subtracted twice.

graph TD
    A["Table I: sum from the origin to each pixel"] --> B["Rectangle sum<br/>= D - B - C + A"]
    B --> C2["Four lookups,<br/>independent of rectangle size"]

Four reads give the sum of 9 pixels or of 90,000 pixels, at the same cost.

Python Box sums from four lookups

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The integral and direct sums agree for every rectangle. Building the table costs one pass over the image, and after that each box sum costs the same four reads. Compare that with summing the rectangle directly, which is proportional to its area.

Why this matters

  • A box filter (an average, or a difference of averages) of any size is cheap. Convolution with a Gaussian costs more as the kernel grows; a box filter does not.
  • Haar-like features (a light rectangle next to a dark one, used by the Viola-Jones face detector) are differences of box sums. A detector can test thousands of them per window in real time.
  • Adaptive thresholding (a pixel against the mean of its neighbourhood) uses the same table to get local means for all pixels in one pass. See Thresholding.
Python Speed: integral image versus direct summation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The absolute timings depend on the machine and on NumPy's vectorised summation, but the pattern is the point: the integral-image time does not grow with the box size.

From the Hessian to SURF

Recall the blob detectors from Image Pyramids and Scale: a blob is a place where the second derivatives are large. The matrix of second derivatives is the Hessian:

H = [[Lxx, Lxy], [Lxy, Lyy]]

where Lxx is the image convolved with the second derivative of a Gaussian in x, and so on. Its determinant, det(H) = Lxx * Lyy - Lxy^2, is large at blobs (strong curvature in both directions) and near zero along edges (strong curvature in one direction only).

SURF's idea is to replace the Gaussian second-derivative filters with box filters of a few rectangles each, with weights +1, -2, +1. With the integral image, every such filter costs a handful of lookups, whatever its size. The approximate determinant is:

det(H_approx) = Dxx * Dyy - (0.9 * Dxy)^2

where D are the box-filter responses and 0.9 is a weight that corrects for the approximation.

Two more savings follow:

  • Scale space by growing the filter, not shrinking the image. SIFT builds a pyramid of blurred, resized images. SURF keeps the image as it is and uses boxes of size 9, 15, 21, 27, ... Larger filters cost the same, so no resampling is needed.
  • A fast detector. Local maxima of the determinant across position and scale are the interest points. This is called the Fast Hessian detector.
Python A box-filter Hessian finds a blob

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The response peaks on the disc centre, and it is strongest for lobe size 7, the filter whose size best matches the blob: that is how a detector picks the scale. Small filters see only part of the disc and land a few pixels off. On the thin bar, a ridge with curvature in one direction only, the determinant is zero for every size, which is why the Hessian determinant rejects edges and lines. Real SURF adds proper non-maximum suppression over position and scale and interpolates the peak to sub-pixel accuracy.

The SURF descriptor

Once a point and its scale are known, SURF:

  1. Finds a dominant orientation from Haar wavelet responses (differences of box sums, again via the integral image) in a circular neighbourhood, and rotates the window to it. "Upright SURF" skips this step if the camera does not rotate.
  2. Divides the oriented square window into a 4 by 4 grid of sub-regions.
  3. In each sub-region it sums the Haar responses dx, dy, |dx| and |dy|, giving 4 numbers.
  4. Concatenates the 16 sub-regions into a 64-dimensional vector and normalises it to unit length, which makes it robust to contrast changes.

The sign of the Laplacian (is the blob bright on dark or dark on bright?) is stored as an extra bit, so matching can skip pairs of opposite type.

SIFT, SURF and ORB side by side

SIFT SURF ORB
Detector Difference of Gaussians extrema Box-filter Hessian (Fast Hessian) FAST corners + Harris ranking
Scale space Image pyramid, blur and resize Growing box filters on the original image Image pyramid
Orientation Histogram of gradient directions Haar wavelet responses Intensity centroid
Descriptor 128 floats (4x4 grid, 8 bins) 64 (or 128) floats 256 bits (BRIEF-like)
Matching distance Euclidean Euclidean Hamming
Speed Slowest of the three Several times faster than SIFT Fastest
Robustness Excellent Good, a little less than SIFT Good for moderate changes
Licence Patent expired in 2020, free to use Patented, in the non-free module of OpenCV Free

Which to use? ORB is the default for real-time and mobile work, SIFT when accuracy under large scale, rotation and viewpoint change matters and compute is available, and SURF mainly appears in older code and in the literature, where it showed that box filters plus integral images make robust features cheap. Modern pipelines increasingly use learned detectors and descriptors (SuperPoint, LoFTR, and similar), but the pipeline stays the same: detect, describe, match, verify with RANSAC.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many table lookups does the sum of any rectangle need with an integral image?

    The sum is D - B - C + A, the four corner values of the integral image, independent of the rectangle's size.
  2. 2. How does SURF build its scale space differently from SIFT?

    With an integral image, big box filters cost the same as small ones, so SURF keeps the image fixed and scales the filters.
  3. 3. What does the determinant of the Hessian respond to?

    A large determinant needs strong second derivatives in two directions; along an edge one of them is near zero.
  4. 4. What is the dimension of the standard SURF descriptor?

    4 by 4 sub-regions with 4 values each gives 64 numbers (128 in the extended version).
  5. 5. Which descriptor is matched with Hamming distance?

    ORB descriptors are binary strings, so the Hamming distance (count of differing bits) is the natural and fastest measure.

Summary

  • An integral image stores cumulative sums so that any rectangle sum needs only four lookups.
  • Box filters, Haar-like features, local means and adaptive thresholds all become cheap with it.
  • SURF approximates the Hessian determinant with box filters, scales the filter instead of the image, and detects blobs as maxima of the response over position and scale.
  • Its descriptor is a 64-number vector of Haar responses over a 4 by 4 grid, rotated to a dominant orientation.
  • SIFT is the most robust and slowest, SURF is faster, ORB is fastest and binary; choose by accuracy, speed and licence.

Next: Hough Transform.