SURF算法（Speeded Up Robust Features）

1 SURF: Speeded Up Robust Features

In this section, the SURF detector-descriptor scheme is discussed in detail. First the

algorithm is analysed from a theoretical standpoint to provide a detailed overview of how

and why it works. Next the design and development choices for the implementation of

the library are discussed and justified. During the implementation of the library, it was

found that some of the finer details of the algorithm had been omitted or overlooked,

so Section 1.5 serves to make clear the concepts which are not explicitly defined in the

SURF paper [1].

1.1 Integral Images

be defined by the formula:

I

P

(x, y) =

i≤x

X

i=0

j≤y

j=0

region is reduced four operations. If we consider a rectangle bounded by vertices A, B,

when large areas are required. SURF makes good use of this property to perform fast

1.2.1 The Hessian

The SURF detector is based on the determinant of the Hessian matrix. In order to

motivate the use of the Hessian, we consider a continuous function of two variables such

that the value of the function at (x, y) is given by f(x, y). The Hessian matrix, H, is the

matrix of partial derivates of the function f.

H(f(x, y)) =

"

∂

f

∂x

∂

f

∂x∂y

det(H) =

∂

2

f

∂x

2

∂

2

f

∂y

2



2

function by the second order derivative test. Since the determinant is the product of

ties I(x, y). Next we require a method to calculate the second order partial derivatives of

the image. As described in Section ?? we can calculate derivatives by convolution with

an appropriate kernel. In the case of SURF the second order scale normalised Gaussian is

the chosen filter as it allows for analysis over scales as well as space (scale-space theory is

discussed further later in this section). We can construct kernels for the Gaussian deriva-

tives in x, y and combined xy direction such that we calculate the four entries of the

Hessian matrix. Use of the Gaussian allows us to vary the amount of smoothing during

the convolution stage so that the determinant is calculated at different scales. Further-

more, since the Gaussian is an isotropic (i.e. circularly symmetric) function, convolution

with the kernel allows for rotation invariance. We can now calculate the Hessian matrix,

xy

xx

(x, σ) refers to the convolution of the second order Gaussian derivative

∂

g(σ)

with the image at point x = (x, y) and similarly for L

known as Laplacian of Gaussians.

Figure 2 illustrates the similarity between the discretised and cropped kernels and their

box filter counterparts. Considerable performance increase is found when these filters

are used in conjunction with the integral image described in Section 1.1. To qauntify

the difference we can consider the number of array accesses and operations required in

the convolution. For a 9 × 9 filter we would require 81 array accesses and operations for

the original real valued filter and only 8 for the box filter representation. As the filter is

increased in size, the computation cost increases significantly for the original Laplacian

while the cost for the box filters is independent of size.

Figure 2: Laplacian of Gaussian Approximation. Top Row: The discretised and cropped second

remaining areas not weighted at all. Simple weighting allows for rapid calculation of areas

the original and approximated kernels. Bay [1] proposes the following formula as an

accurate approximation for the Hessian determinant using the approximated Gaussians:

approx

D

yy

2

representation’s negligible loss in accuracy is far outweighed by the considerable increase

in efficiency and speed. The determinant here is referred to as the blob response at

location x = (x, y, σ). The search for local maxima of this function over both space and

scale yields the interest points for an image. The exact method for extracting interest

with Gaussian kernel and repeatedly sub-sampled (reduced in size). This method is used

to great effect in SIFT [9] but since each layer relies on the previous, and images need

to be resized it is not computationally efficient. As the processing time of the kernels

used in SURF is size invariant, the scale-space can be created by applying kernels of

increasing size to the original image. This allows for multiple layers of the scale-space

pyramid to be processed simultaneously and negates the need to subsample the image

hence providing performance increase. Figure 3 illustrates the difference between the

traditional scale-space structure and the SURF counterpart.

Figure 3: Filter Pyramid. The traditional approach to constructing a scale-space (left).

The image size is varied and the Guassian filter is repeatedly applied to smooth subse-

space is obtained from the output of the 9 × 9 filters shown in 2. These filters correspond

to a real valued Gaussian with σ = 1.2. Subsequent layers are obtained by upscaling

approx

Base Filter Scale

Base Filter Size

= Current Filter Size ·

1.2

When constructing larger filters, there are a number of factors which must be take into

consideration. The increase in size is restricted by the length of the positive and negative

lobes of the underlying second order Gaussian derivatives. In the approximated filters

the lobe size is set at one third the side length of the filter and refers to the shorter side