Scale Space

Image Processing and Computer Vision

Rein van den Boomgaard Leo Dorst

University of Amsterdam

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 1 / 23

 Outline

1 Introduction

2 Scale Space
Scale Space Definition
Causality in Scale-Space - Diffusion

3 Calculating a Scale-Space
Sampling Scale-Space
Scale-Space Pyramids

4 Derivatives in Scale-Space
Scale Normalized Derivatives
Edges in Scale-Space
Blobs in Scale-Space

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 2 / 23

 Scale-Space

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 3 / 23

 Scale-Space

We are looking for a family of image operators Ψs such that given the
‘image at zero scale’ f0 we can construct the family of images Ψs f0 such
that:
Ψs is a linear operator,
the operator Ψs is translation invariant,
it is rotational invariant,
the operator is separable by dimension, and
Ψs is invariant under changes of scale.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 4 / 23

 Scale-Space

Theorem (Gaussian Scale-Space)

The unique scale-space operator is the
Gaussian convolution:

f (x, s) = (f0 ∗ G s )(x)

where:
1 − kxk22
G s (x) = e 2s
2πs 2
We will often write f s to denote the image
f (·, s).

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 5 / 23

 Jan Koenderink
Prof. Jan Koenderink from Utrecht
University formulated scale-space
theory in the 1980’s.

The structure of images

JJ Koenderink - Biological
cybernetics, 1984 - Springer
Abstract. In practice the relevant
details of images exist only over a
restricted range of scale. Hence it is
important to study the dependence of
image structure on the level of
resolution. It seems clear enough that
visual perception treats images on
several levels of resolution ... Geciteerd
door 1693
Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 6 / 23
 Causality in Scale-Space

Luminance values (or gray values)

should not be created when
increasing the observation scale. I.e.
a value f (x, s) should be traceable to
a point in the infinitesimal
neighborhood of x at an
infinitesimally smaller scale s − ds.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 7 / 23

 Diffusion Equation

From the causality principle we can derive

that the scale-space function f (x, s) should
satisfy the partial differential equation:
∂f
= α 2 ∇2 f
∂s
with α an arbitrary function in x and s.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 8 / 23

 Diffusion Equation

From the causality principle we can derive

that the scale-space function f (x, s) should
satisfy the partial differential equation:
∂f
= α 2 ∇2 f
∂s
with α an arbitrary function in x and s.
Setting α2 = s leads to fs = s∇2 f with
solution:

f (x, s) = (f0 ∗ G s )(x)

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 8 / 23

 Diffusion Equation

From the causality principle we can derive

that the scale-space function f (x, s) should
satisfy the partial differential equation:
∂f
= α 2 ∇2 f
∂s
with α an arbitrary function in x and s.
2
Tt = ∇ T describes the Setting α2 = s leads to fs = s∇2 f with
temperature distribution as a solution:
function of time.
f (x, s) = (f0 ∗ G s )(x)

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 8 / 23

 Scale-Space

Definition:
f (x, s) = (f0 ∗ G s )(x)
Diffusion equation:
fs = s∇2 f
Derivatives: All derivatives satisfy the diffusion equation as well:

(∂... f )s = s∇2 (∂... f )

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 9 / 23

 Sampling Scale-Space

Space is sampled equidistantly:

x = i∆x, y = j∆y

for i = 0, . . . , nx − 1 and
j = 0, . . . , ny − 1.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 10 / 23

 Sampling Scale-Space

Space is sampled equidistantly:

x = i∆x, y = j∆y

for i = 0, . . . , nx − 1 and
j = 0, . . . , ny − 1.
Scale is sampled logaritmically:

s = α i s0 ,

for i = 0, . . . , ns − 1. (thus log s is

sampled equidistantly).

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 10 / 23

 Sampling Scale-Space

Space is sampled equidistantly:

x = i∆x, y = j∆y

for i = 0, . . . , nx − 1 and
j = 0, . . . , ny − 1.
Scale is sampled logaritmically:

s = α i s0 ,

for i = 0, . . . , ns − 1. (thus log s is

sampled equidistantly).

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 10 / 23

 Subsampling

512 × 512 256 × 256 128 × 128 64 × 64 32 × 32

f0 ∗ G s0 f0 ∗ G 2s0 f0 ∗ G 4s0 f0 ∗ G 80 f0 ∗ G 16s0

Top row: subsampling without smoothing

Bottom row: subsampling with Gaussian smoothing

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 11 / 23

 Subsampling

512 × 512 256 × 256 128 × 128 64 × 64 32 × 32

f0 ∗ G s0 f0 ∗ G 2s0 f0 ∗ G 4s0 f0 ∗ G 80 f0 ∗ G 16s0

Smoothing is essential before subsampling.

Top row: subsampling without smoothing

Bottom row: subsampling with Gaussian smoothing

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 11 / 23

 Subsampling

512 × 512 256 × 256 128 × 128 64 × 64 32 × 32

f0 ∗ G s0 f0 ∗ G 2s0 f0 ∗ G 4s0 f0 ∗ G 80 f0 ∗ G 16s0

Smoothing is essential before subsampling.
After smoothing you may subsample !

Top row: subsampling without smoothing

Bottom row: subsampling with Gaussian smoothing

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 11 / 23

 Burt Image Pyramid

Smoothing an image decreases the resolution (i.e.

we are unable to resolve the small details in the
image anymore).
Effectively we are removing the high frequencies in
the image.
With enough smooting applied we may subsample
the image to obtain an image with less pixels.
If we take a Gaussian pre-smooting with scale s
somewhere in the range from 0.7 to 1.5 we can
reduce the number of pixels with a factor 2 in both
grid directions.
Computationally this is very attractive . . .
but this way a lot of the interesting characteristics in
scale-space are missed due to the large sampling
intervals in scale.
Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 12 / 23
 Burt Image Pyramid
f s0 f 2s0 f 4s0

√ √
∗G s0 3
∗G 2s0 3

Subsample Subsample

f22s0 f24s0
√
∗G s0 3

Subsample

f44s0

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 13 / 23

 Scale-Space Pyramid

Replace one stage in the Burt pyramid:

√
G s0 3
f s0 f 2s0
Subsample

f22s0

with one octave in the scale-space pyramid:

√ √ √
∗G s0 α2 −1 ∗G s0 α α2 −1 2 ∗G s 0 α2 α2 −1 3s
f s0 f αs0 f α s0 fα 0 = f 2s0
Subsample

f22s0

where α = 2(1/K ) and K = 3.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 14 / 23
 Scale-Space Pyramids

Consider a scale-space sampled with s = αi s0 where α = 21/K .

At level i = K the smoothing scale is 2s0 .
The image at level K may thus be subsampled with a factor 2 in the
spatial domain.
In the second octave we need exactly the same Gaussian filters to
4 5 6
obtain f2α s0 , f2α s0 and f2α s0 = f 4so , i.e.
4s
√
α2 −1
f2α 0
= f22s0 ∗ G s0

etc.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 15 / 23

 Derivatives in Scale-Space

Scale-space: f s = f0 ∗ G s .
Scale-space of derivative g0 = ∂f0 (any
spatial derivative): g s = g0 ∗ G s .
Differentiating and smoothing are both
linear operators and so:

g s = ∂f s

for any scale.

i.e. first differentiating and then smoothing
is the same as first smoothing and then
differentiating.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 16 / 23

 Derivatives in scale-space

With larger scale the

0.4

0.3
response of the Gaussian
0.2
first order derivative
0.1
decreases.
0
0 10 20 30 40 50 60 70
Plotting sfxs shows that a
first order derivative
0.4

0.3
should be multiplied with
0.2
s to be constant over
0.1
scale.
0
0 10 20 30 40 50 60 70
When comparing local
structure (expressed in
Response of first order derivative Gaussian Gaussian Derivatives)
convolution to a step edge. On top fxs and across scales, it is
on the bottom sfxs . important to use scale
normalized derivatives.
Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 17 / 23
 Scale Normalized Derivatives

When comparing local structure (expressed in Gaussian derivatives) across

all scale levels it is important to use scale normalized derivatives.

Theorem (Scale Normalized Derivatives)

Let ∂ n denote any n-th order spatial derivative then the scale normalized
derivative is
s n∂n

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 18 / 23

 Edges in Scale-Space

On the left the original image.

The center of the circles is at x0 .
The middle image is the
Gaussian blur at scale 2.77, the
right image is at scale 21.35.
The bottom line in the graph is
0.4 the response fws (x0 ) as a
0.35

0.3 function of the scale s. The top

line is sfws (x0 ) plotted as a
0.25

0.2

0.15

0.1 function of s.
0.05

0
0 5 10 15 20 25 30 35 The two peaks in the top graph
correspond with the circles
drawn in the images.

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 19 / 23

 Blobs in Scale-Space

Consider a Gaussian shaped blob,

light on dark background:

f0 (x) = G b (x − x0 )

The scale normalized Laplacian

operator:

`(x, s) = s 2 (f0 ∗ ∇2 G s )(x)

has an extremum at s = b and

x = x0 .

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 20 / 23

 Blobs in Scale-Space

50

100

150

200

250

300

350

400

450

500
100 200 300 400 500 600 700 800

0.5

−0.5
0 10 20 30 40 50 60

0.5

−0.5
0 10 20 30 40 50 60

0.5

−0.5
0 10 20 30 40 50 60

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 21 / 23

 Blobs in Scale-Space

50

100

150

200

250

300

350

400

450

500
100 200 300 400 500 600 700 800

0.3

0.2

0.1

−0.1
0 1 2
10 10 10

0.3

0.2

0.1

−0.1
0 1 2
10 10 10

0.4

0.2

−0.2

−0.4
0 1 2
10 10 10

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 22 / 23

 Subpixel Accurate Blob Localization

Blob detection in scale space:

extrema of `(x, s) = s 2 (∇2 f s )(x)
write X = x y s T , then L(X) = `(x, s)

nescessary condition for extremum: ∇L = 0

Taylor series of L:

L(X0 + X) = L(X0 ) + XT (∇L)(X0 ) + 21 XT HL (X0 )X

∇L = 0 then gives as subpixel accurate estimate of the extremum:

X0 − HL−1 (X0 )(∇L)(X0 )

Rein van den Boomgaard, Leo Dorst (UvA) Scale Space 23 / 23