Why are SIFT descriptors scale invariant

Keypoint detection of the Scale-Invariant Feature Transform (SIFT) Prof ...

Computer vision

Keypoint detectionthe

Scale-InvariantfeatureTransform (SIFT)

Prof. Dr. Kai Uwe Barthel

International degree in media informatics

HTW Berlin


Portions of these slides are from Bahadir K. Gunturk

have been taken over and added,

translated and adapted.

2

© Kai Uwe Barthel


Aim:

Draft a local descriptor for

Description of typical object structures or

-properties.

Description of places very specific

visual properties / conditions in

a picture.

Use:

3

Object classification

Automatic mosaicing

Stereo matching

© Kai Uwe Barthel


Use of keypoints / point descriptors

If we take characteristic points in Bilthen

have found how can we do this

one anotherthe assign (match)?

4

© Kai Uwe Barthel

?


Use e.g. automatic stitching

5

http://www.cs.bath.ac.uk/brown/autostitch/autostitch.html

© Kai Uwe Barthel


introduction

Image areas are divided into local featurevectors

transformed compared to translations,

Rotations, Scales, and

Lighting changetheare invariant.

6

© Kai Uwe Barthel


introduction

SIFT in one sentence:

7

Gradient histogram

at

Harris corner points

© Kai Uwe Barthel


Harris Corner Detection I.

Identical object with different orientation and lighting

8

© Kai Uwe Barthel


Harris Corner Detection II

Corner response

9

© Kai Uwe Barthel


Harris Corner Detection III

Detected corner points

10

© Kai Uwe Barthel


Harris Corner Detection IV

Addiction the Corner point detection

of the Size scaling

11

© Kai Uwe Barthel


Harris Corner Detector Features

Rotational invariant: Rotation changethet the

Eigenvalues the Structure matrix not.

Invariant compared to lighting changestheungen

(additive and multiplicative).

R.

threshold

12

§ Since the derivatives are examined, invariant

towards additive changestheungen.

§ Multiplicative changesthethe corners are scaled

Response R, places the Maxima remain unchangedthet.

© Kai Uwe Barthel

R.


Harris Corner Detector Features

But:

Not invariant to image scaling!

13

All points will

classified as edges

© Kai Uwe Barthel

reduction

Corner!


Keypoint search - location and scaling

How should the appropriate scaling be selected?

15

© Kai Uwe Barthel


Scaling invariant detection

Analysis of regions (circles) around one

Point with different sizes

With corresponding sizes

Regions look similar

16

© Kai Uwe Barthel


Scaling invariant detection

Problem: How are the corresponding

Analysis regions independent of one anotherthe

to choose for each picture?

17

© Kai Uwe Barthel


Keypoint search - location and scaling

Scale selection principle (T. Lindeberg '94):

“In the absence of other evidence, assume that a scale level, at

which (possibly non-linear) combination of normalized

theivatives assumes a local maximum over scales, can be

treated as reflecting a characteristic length of a corresponding

structure in the data. "

18

possible solution:

è extreme values the Difference from bilthen,

those with Gaussian filters are more different

Radii were filtered

"Difference of Gaussians"

© Kai Uwe Barthel


f image1

Scaling invariant Keypoint detection

Solution:

Design of a function f for the region (circle),

which is scaling invariant.

I.e. the same “results” for corresponding

Regions of different scales

19

For a point in the picture, this can be thought of as a function of the

Think of the region size (the radius of the circle)

© Kai Uwe Barthel

Region size

scale = 1/2

f image2

Region size


f image1

Scaling invariant Keypoint detection

Common approach:

20

s 1

Use the maximum of this feature

The region size for which the maximum scored

is, should be invariant to the

Image scaling s.

© Kai Uwe Barthel

scale = 1/2

f image2

Region size Region size

s 2


Characteristic scaling

21

The relationship the Region size corresponds to

Scaling factor the both bilthe

© Kai Uwe Barthel

Region size

Region size


Scaling invariant Keypoint detection

f

Has a “good” function for scale detection

a "steep summit":

For typical bilthe reacts a "good"

Detector function on contrast

(on sharp local brightness changestheungen)

22

bad

Region size

© Kai Uwe Barthel

f

bad

Region size

f

Well

Region size


Scaling invariant Keypoint detection

Scale detection functions

= Filtering with suitable kernels

Kernel:

23

( (, , ) (, , ) )

2

L = Gxx x y + Gyy x y

σ σ σ

(Laplace function)

DoG = G (x, y, kσ) −G (

x, y,

σ)

(Difference of Gaussians)

With

© Kai Uwe Barthel

2 2

x + y


2

1 2

2πσ

σ

Gxy (,, σ) = e

f = kernel! picture

The L or DoG kernel is a

Matching filter, the punctiform

Finds structures (blobs).


Scaling invariant detectors

Finding local maxima in the local scale space:

Harris-Laplacian 1

§ local Harris Corner

Detector

§ Laplace filter in

Scale direction

Sift (DoG) 2

§ local Gaussian filtering

§ Difference in

Scale direction

scale

scale

1 K.Mikolajczyk, C.Schmid. “Indexing Based on ScaleInvariant Interest Points ”. ICCV 2001

24 © Kai Uwe Barthel

2 D.Lowe. “Distinctive Image features from Scale-Invariant Keypoints ”(2004)

y

y

← Harris →

← Gaussian →

space

x

space

x

← Laplacian →

← D →


SIFT

(ScaleInvariantfeatureTransform)


Scale-space extrema detection

Search for the place and

the "Characteristic scaling" for everyone

Keypoint.

29

© Kai Uwe Barthel


Difference-of-Gaussians

() I.

2

G k σ

*

σ D (σ) ≡ (G (


) −G (

σ) * I

G (k) * I

G (σ) * I

30

© Kai Uwe Barthel


Scale-Space extrema

Choose all extremes within their 3x3x3

Neighborhood:

31

© Kai Uwe Barthel

D.

D.

( 2

k σ)

(kσ

)

D (

σ)

X is chosen if its absolute value is greater than all 26 neighbors


Maxima in the place-scale space D

32

© Kai Uwe Barthel


Keypoint localization & filtering

Discard points with insufficient contrast:

§ DoG less than 0.03

(with a standardized range of [0.1])

Discard edges

33

§ Similar to the Harris Detector

© Kai Uwe Barthel


Without edges and little contrast

34

© Kai Uwe Barthel


Direction assignment

By assigning a prevailing orientation

can the Keypoint can be made rotationally invariant.

L is the image with the appropriate scale

Calculate strength and direction the Gradients:

35

© Kai Uwe Barthel

⎡⎡Lx (+ 1, y) −Lx (−1,

y)

⎤⎤

GradientVector = ⎢⎢

Lxy (, + 1) −Lxy (, −1)

⎥⎥

⎣⎣ ⎦⎦


Local, Scale- and direction assignment

36

© Kai Uwe Barthel


Direction assignment

37

© Kai Uwe Barthel


Direction assignment

38

© Kai Uwe Barthel


Direction assignment

39

© Kai Uwe Barthel


Direction assignment

All histogram peaks that have a value of

at least 80% of the maximum value of the

Own histogram are used for generating

of a keypoint with this direction.

This means that approx. 15% the Keypoints

can be assigned to multiple directions, however

this increases the "stability" significantly.

40

© Kai Uwe Barthel


SIFT Keypoints

(with location, strength and direction)

41

© Kai Uwe Barthel


SIFT Descriptor

Now has everthe Keypoint x, y, σ, m, θ

Place, scale, strength and direction

Now you need a descriptor the the

Describes region

42

§ This could be the pixel values the Environment of the

Be point, but ...

§ sensitive to lighting changestheungen

§ sensitive to small errors of x, y, θ

© Kai Uwe Barthel

Edelman et al. 1997


SIFT Descriptor

Use of a 16x16 gradient region, divided into 4x4

Subregions.

histogram the 4x4 region with 8 directions

Gaussian weighting around the center

4x4x8 = 128 more dimensional featurevector

43

© Kai Uwe Barthel


performance

Very "robust"

44

§ 80% reproducibility for:

§ 10% image noise

§ 45 ° viewing angle

§ 1000 -100000 keypoints in database

Best descriptor in the extensive

Investigation of

[Mikolajczyk & Schmid 2005]

© Kai Uwe Barthel


45

© Kai Uwe Barthel


46

© Kai Uwe Barthel


47

© Kai Uwe Barthel


Object detection in case of obscurations

48

© Kai Uwe Barthel