Scale-Space for Discrete Signals
Tony Lindeb erg
Computer Vision and Associative Pattern Pro cessing Lab oratory (CVAP)
Royal Institute of Technology
S-100 44 Sto ckholm, Sweden
Abstract
We address the formulation of a scale-space theory for
discrete
signals. In one
dimension it is p ossible to characterize the smo othing transformations completely
and an exhaustive treatment is given, answering the following two main questions:
1. Which linear transformations remove structure in the sense that the number of
lo cal extrema (or zero-crossings) in the output signal do es not exceed the number
of lo cal extrema (or zero-crossings) in the original signal? 2. How should one create
a multi-resolution family of representations with the property that a signal at a
coarser level of scale never contains more structure than a signal at a ner level of
scale?
We prop ose that there is only one reasonable way to dene a scale-space for
1D discrete signals comprising a
continuous
scale parameter, namely by (discrete)
convolution with the family of kernels
T
(
n
;
t
)=
e
t
I
n
(
t
), where
I
n
are the mo died
Bessel functions of integer order. Similar arguments applied in the continuous case
uniquely
lead to the Gaussian kernel.
Some obvious discretizations of the continuous scale-space theory are discussed
in view of the results presented. We show that the kernel
T
(
n
;
t
) arises naturally
in the solution of a discretized version of the diusion equation. The commonly
adapted technique with a sampled Gaussian can lead to undesirable eects since
scale-space violations might o ccur in the corresp onding representation. The result
exemplies the fact that prop erties derived in the continuous case might b e violated
after discretization.
A two-dimensional theory, showing how the scale-space should be constructed
for images, is given based on the requirement that lo cal extrema must not be en-
hanced, when the scale parameter is increased continuously. In the separable case
the resulting scale-space representation can b e calculated by separated convolution
with the kernel
T
(
n
;
t
).
The presented discrete theory has computational advantages compared to a scale-
space implementation based on the sampled Gaussian, for instance concerning the
Laplacian of the Gaussian. The main reason is that the discrete nature of the
implementation has b een taken into account already in the theoretical formulation
of the scale-space representation.
1 Intro duction
It is well-known that ob jects in the world and details in an image exist only over a
limited range of resolution. A classical example is the concept of a branch of a tree which
1
