没有合适的资源？快使用搜索试试~ 我知道了~
ScaleSpace for Discrete Signals.pdf
3星 · 超过75%的资源 需积分: 17 38 下载量 150 浏览量
20151012
20:29:43
上传
评论
收藏 1.89MB PDF 举报
温馨提示
试读
21页
多尺度空间的经典英文原文，里面介绍了在离散信号情况下，什么样的滤波核能用于尺度变换。
资源推荐
资源详情
资源评论
234
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.
12.
NO.
3.
MARCH
1990
ScaleSpace for Discrete
Signals
TONY LINDEBERG
AbstractWe address the formulation of a scalespace theory for
discrete signals. In one dimension it is possible to characterize the
smoothing 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 local
extrema (or zerocrossings) in the output signal does not exceed the
number of local extrema (or zerocrossings) in the original signal?
2)
How should one create a multiresolution family of representations with
the property that a signal at a coarser level of scale never contains
more structure than a signal at a finer level of scale?
We propose that there is only one reasonable way to define 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'ln(t),
where
I.
are the modified Bessel functions of integer order.
Similar arguments applied in the continuous case
uniquely
lead to the
Gaussian kernel.
Some obvious discretizations of the continuous scalespace 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
diffusion equation.
The
commonly adapted technique with a sampled
Gaussian can lead to undesirable effects since scalespace violations
might occur in the corresponding representation. The result exempli
fies the fact that properties derived in the continuous case might be
violated after discretization.
A
twodimensional theory, showing how the scalespace should be
constructed for images, is given based on the requirement that local
extrema must not be enhanced, when the scale parameter is increased
continuously. In the separable case the resulting scalespace represen
tation can be calculated by separated convolution with the onedimen
sional kernel
T(n;
t).
The presented discrete theory has computational advantages com
pared to a scalespace implementation based on the sampled Gaussian,
for
instance concerning the Laplacian of the Gaussian. The main rea
son is that the discrete nature of the implementation has been taken
into account already in the theoretical formulation of the scalespace
representation.
Index TermsComputer vision, diffusion, Gaussian filtering, mul
tiresolution representation, scalespace discrete smoothing transfor
mations, signal processing.
I.
INTRODUCTION
T is wellknown that objects in the world and details in
I
an image exist only over a limited range of resolution.
A classical example is the concept of a branch of a tree
which makes sense only on the scale say from a few cen
timeters to at most a few meters. It is meaningless to dis
cuss the tree concept at the nanometer or the kilometer
level. At those levels
of
scale it is more relevant to talk
Manuscript received November
15,
1988; revised July 31, 1989. This
work was supported by the National Swedish Board
for
Technical Devel
opment.
The author is with the Computer Vision and Associative Pattern Pro
cessing Laboratory (CVAP), Royal Institute
of
Technology,
S100
44
Stockholm, Sweden.
IEEE
Log Number 8932046.
about the molecules, which form the leaves of the tree,
or the forest, in which the tree grows. If one aims at de
scribing the structure of an image, a multiresolution rep
resentation is of crucial importance. Then a mechanism,
which systematically removes finer details or highfre
quency information from an image, is required. This
smoothing must be available at any level of scale.
A method proposed by Witkin [23] and Koenderink and
van Doorn
[
111
is to embed the original image in a one
parameter family of derived images, the scalespace,
where the parameter
t
describes the current level of scale
resolution. Let us briefly develop the procedure as it is
formulated for onedimensional continuous signals: given
a signal f: R
+
R a function' L: R
x
R,
*
R is defined
by
L(x;
0)
=
f
(x)
and convolution with the Gaussian
kerne1g:R
x
R+\(O}
+
R
nm
if
t
>
0.
Equivalently the family can be regarded as de
fined by the diffusion equation
with initial condition L(x;
0)
=
f
(x).
This family pos
sesses some attractive properties.
As the scale parameter
t
is increased additional local
extrema or additional zero crossings cannot appear.
Causality in the sense that
L(x;
t2)
depends exclu
sively on L(x;
t,)
if
t2
>
tl
(t,,
t2
2
0).
The blurring is shift invariant and does not depend
upon the image values.
It has been shown by Babaud et
al.
[3]
that the Gaussian
function is the only kernel in a broad class of functions
which satisfies adequate scalespace conditions.
The scalespace theory has been developed and well
established for continuous signals and images. However,
it does not tell us at all about how the implementation
should be performed computationally for reallife, i.e.,
discrete signals and images. In principle, we feel that there
are two approaches possible.
Apply the results obtained from the continuous scale
space theory by discretizing the occurring equations. For
instance the convolution integral
(1)
can be approximated
by a sum using customary numerical methods. Or, the
diffusion equation (2) can be discretized in space with the
'R
+
denotes the set
of
real nonnegative numbers
01628828/90/03000234$01
.OO
0
1990 IEEE
LINDEBERG: SCALESPACE FOR DISCRETE SIGNALS
235
ordinary fivepoint Laplace operator forming a set of cou
pled ordinary differential equations, which can be further
discretized in scale. If the numerical methods are chosen
with care we will certainly get reasonable approximations
to the continuous numerical values. But we are not guar
anteed that the original scalespace conditions, however
formulated, will be preserved.
Define a genuinely discrete theory by postulating
suitable axioms.
The goal of this paper is to develop the second item and
to address the formulation of a scalespace theory for dis
crete images. We will start with a onedimensional signal
analysis. In this case it is possible to characterize exactly
which kernels can be regarded as smoothing kernels and
a complete and exhaustive treatment will be given. One
among many questions which are answered is the follow
ing: if one performs repeated averaging, does one then
get scalespace behavior? We will also present a family
of kernels, which are the discrete analog of the Gaussian
family of kernels. The set of arguments, which in the dis
crete case uniquely leads to this family of kernels do in
the continuous case uniquely lead
to
the Gaussian family
of kernels.
The structure of the twodimensional problem is more
complex, since it is difficult to formulate what should be
meant by preservation of structure in this case. However,
arguing that local extrema must not be enhanced when the
scale parameter is increased continuously, we will give
an answer to how the scalespace for twodimensional
discrete images should be calculated. In the separable case
it reduces to separated convolution with the presented one
dimensional discrete analog of the Gaussian kernel. The
representation obtained in this way has computational ad
vantages compared to the commonly adapted approach,
where the scalespace is based on different versions of the
sampled Gaussian kernel. One of many spinoff products
which come up naturally is a wellconditioned and
effi
cient method to calculate (a discrete analog of) the La
placian of the Gaussian. It is wellknown that the imple
mentation of the Laplacian of the Gaussian has lead to
computational problems
[8].
The theory developed in this paper also has the attrac
tive property that it is linked to the continuous theory
through a discretized version of the diffusion equation.
This means that continuous results may be transferred to
the discrete implementation provided that the discretiza
tion is done correctly. However, the important point of
the scalespace concept outlined here is that the properties
we want from a scalespace hold not only in the ideal the
ory but also in the discretization,2 since the discrete na
'In a practical implementation we are
of
course faced with rounding and
truncation errors due to finite precision.
But
the idea with this approach is
that we hope to improve our algorithms by including at least the discreti
zation effects already in the theory.
In
ordinary numerical analysis for sim
ulation of physical phenomena it is almost always possible to reduce these
effects by increasing the density
of
mesh points, in case the current grid is
not fine enough to give a prescribed accuracy in the result. However, in
computer vision we are often locked
to
some fixed maximal resolution,
beyond which additional image data are not available.
ture of the problem has been taken into account already
in the theoretical formulation of the scalespace represen
tation. Therefore, we believe that the suggested way to
implement the scalespace theory really describes the
proper way to do it.
The presentation is organized as follows. In Section I1
we define what we mean by a scalespace representation
and a onedimensional discrete scalespace kernel. Then
in a straightforward and constructive manner Section I11
illustrates some qualitative properties that must be pos
sessed by scalespace kernels. A complete characteriza
tion as well as an explicit expression for the generating
function of all discrete scalespace kernels are given in
Section IV. Section V develops the concept of a discrete
scalespace with a
continuous
scale parameter. The for
mulation is equivalent to the previous scalespace for
mulation, which in the continuous case leads to the
Gaussian kernel. The numerical implementation of this
scalespace is treated in Section VI. Section VI1 discusses
discrete scalespace properties of some obvious discreti
zations of the convolution integral and the diffusion equa
tion. Section VI11 describes some problems which occur
due to the more complicated topology in two dimensions.
In Section IX we develop the scalespace for twodimen
sional discrete images. Here we also compare the discrete
scalespace representation with the commonly used ap
proach, where the scalespace implementation is based on
various versions of the sampled Gaussian kernel. Finally,
Section X gives a brief summary of the main results.
The results presented should have implications for im
age analysis as well as other disciplines of digital signal
processing.
11.
SCALESPACE
AXIOMS
By a scalespace we mean a family of derived signals
meant to represent the original signal at various levels of
scale. Each member of the family should be associated
with a value of a scale parameter intended to somehow
describe the current level of scale. This scale parameter,
here denoted by
t,
may be either discrete
(
t
E
Z,
)
or con
tinuous
(t
E
R,
)
and we obtain two different types
of
dis
crete scalespacesdiscrete signals with a discrete scale
parameter and discrete signals with a continuous scale pa
rameter. However, in both cases we start from the follow
ing basic assumptions:
All representations should be generated by convolu
tion of the original image with a kernel (linear shiftin
variant smoothing).
An increasing value of the scale parameter
t
should
correspond to coarser levels of scale and signals with less
structure. Particularly,
t
=
0
should represent to the orig
inal signal.
All signals should be realvalued functions:
Z
+
R
defined on the same infinite grid; in other words no pyr
amid representations will be used.
The essential requirement is that a signal at a finer level
of scale should contain less structure than a signal at a
236
increasing
t
IEEE TRANSACTlONS ON PATTERN ANALYSlS AND MACHINE INTELLIGENCE,
VOL.
12,
NO.
3,
MARCH
1990
coarser
levels
of
scale
original
image
Fig.
1.
A
scalespace is an ordered set of derived signaldimages intended
to
represent the original signaliimage at various levels
of
scale.
coarser level of scale. If one regards the number of local
extrema as one measure of smoothness it is thus necessary
that the number of local extrema in space does not in
crease as we go from a finer to a coarser level of scale. It
can be shown that the family of functions generated by
convolution with the Gaussian kernel possesses this prop
erty in the continuous case. We state it as the basic axiom
for our onedimensional analysis and define the follow
ing.
Dejinition
1:
A onedimensional discrete kernel
K:
Z
+
R
is denoted a scalespace kernel if for all signals
fin
:
Z
,
R
the number of local extrema in the convolved
signalf,,,
=
K
*in
does not exceed the number of local
extrema in the original signal.
An important observation to note is that this definition
equivalently can be expressed in terms of zerocrossings
just by replacing the string “local extrema” with “zero
crossings.” The result follows from the facts that a local
extremum in a discrete function
f
is equivalent to a zero
crossing in its first difference
Af,
defined by
(
A
f
)
(x)
=
f
(x
+
1
)

f
(x),
and that the difference operator com
mutes with the convolution operator.
However, the stated definition has further conse
quences. It means that the number of local extrema (zero
crossings) in any nth order difference of the convolved
image cannot be larger than the number of local extrema
(zerocrossings) in the nth order difference of the original
image. Actually, the result can be generalized to arbitrary
linear operators.
Proposition
I:
Let K:
2
+
R
be a discrete scalespace
kernel and
6:
be a linear operator (from the space of real
valued discrete functions to itself), which commutes with
K. Then for any
f:
Z
+
R
(such that the involved quan
tities exist) the number of local extrema in
6:
(K
*:f
)
can
not exceed the number of local extrema in
6:
(
f
).
Proof:
Let
g
=
5:
(f).
As
K
is a scalespace kernel
the number of local extrema in K
*
g
cannot be larger than
the number of local extrema in
g.
Since
K
and
d:
commute
K*g
=
K*C(f)
=
C(K*f)andtheresultfollows.
0
This shows that not only the function, but also all its
“derivatives” will become smoother. Accordingly, con
volution with a discrete scalespace kernel can really be
regarded as a smoothing operation.
To realize that the number of local extrema or zero
crossings can increase even in a rather uncomplicated sit
uation consider the input signal
3
ifn
=O
I
0
otherwise
(3)
Jn(x)
=
2 ifn
=
+1
and convolve it with the kernels
(f,
f,
i),
(i, i),
and
(4,
i, i).
The results are shown in Fig. 2(b), (c), and (d),
respectively. As we see, both the number of local extrema
and the number of zerocrossings have increased for the
first kernel, but not for the two latter ones. Thus, an op
erator which naively can be apprehended as a smoothing
operator, might actually give a
less
smooth result. Fur
ther, it can really matter if one averages over three instead
of two points and how the averaging is performed.
In order to get familiar with the consequences of the
definition we will illustrate what this scalespace property
means. We start by pointing out a few general qualitative
requirements of a scalespace kernel that are necessarily
induced by the given axiom. We will also show that the
two latter kernels indeed are discrete scalespace kernels.
111.
SCALESPACE
KERNELS
A.
Positivity and Unimodality in the Spatial Domain
By considering the impulse response it is possible to
draw some qualitative conclusions about the properties of
a discrete scalespace kernel. Let
Then
fut(x)
=
(K
*
6)
(4
=
K(x).
(5
1
6(x)
has exactly one local maximum and no zerocross
ings. Therefore in order to be a scalespace kernel K must
not have more than one extremum and no zerocrossings.
Thus we can state the following.
Proposition
2:
All coefficients of a scalespace kernel
must have the same sign.
Proposition
3:
The coefficient sequence of a scale
space kernel
{
K(
n)
};=
pm
must be ~nimodal.~
Without loss of generality we can therefore restrict the
rest of the treatment to positive sequences where all K(
n)
2
0.
It seems reasonable to require4 that K
E
11,
i.e., that
E:=
pm
I
K(n)
I
is finite. Iffin is bounded and K
E
lI
then
the convolution is welldefined and the Fourier transform
of the filter coefficient sequence exists. It also allows
us
3A
real sequence is called unimodal if it is first ascending (descending)
and then descending (ascending).
4Some regularity requirement must be imposed on the input signal as
well. Throughout our following considerations we will stick to one general
convention.
If
nothing else is explicitly mentioned we assume that is
sufficiently regular such that the involved quantities exist and are well
defined.
LINDEBERG: SCALESPACE FOR DISCRETE SIGNALS
231
Fig.
2.
(a) Input signal.
(b)
Convolved with
(\,
\,
\).
(c)
Convolved with
(I,
i).
(d) Convolved with
(:,
I,
i).
to normalize the coefficients such that
K( n)
=
1.
Particularly, the filter coefficients
K( n)
must then tend to
zero as
n
goes to infinity.
B. Generalized Binomial Kernels
ficients:
Consider a twokernel with only two nonzero filter coef
p
ifn=O
r
0
otherwise.
K‘*’(n)
=
q
if
n
=
1
(6)
Assume that
p
I
0,
q
I
0,
andp
+
q
=
1.
It is easy to verify that the number of zerocrossings
(local extrema) in
fOut
=
K”’
*A,,
cannot exceed the num
ber of zero crossings (local extrema) in
J;,,.
This result
follows from the fact that convolution off,,, with
K‘*’
is
equivalent to the formation a weighted average
of
the
se
quence
{
J,,(x)}y=
m;
see Fig.
3.
The values of the out
put signal can be constructed geometrically and will fall
on straight lines connecting the values of the input signal.
The offset along the xaxis is determined by the ratio
q/(
p
+
q).
One realizes that no additional zerocrossings can
be introduced by this transformation. Thus, a kernel on
the form
(6)
is a discrete scalespace kernel.
Directly from the definition of a scalespace kernel it
follows that if two kernels
K,
and
Kb
are scalespace ker
nels then
K,
*
Kb
is also a scalespace kernel. Repeated
application of this result yields the following.
Proposition
4:
All kernels
K
on the form
*:=
I
Kj2’,
with
according to
(6),
are discrete scalespace kernels.
The filter coefficients generated in this way can be re
garded as a kind of generalized binomial coefficient. The
ordinary binomial coefficients are obtained, except for a
scalingfactor, as a special case if all
p1
and
qr
are equal.
Another formulation of Proposition
4
in terms of gener
ating functions is also possible.
Proposition
5:
All kernels with the generating function
pK(z)
=
Er=_,
K(n)z“
on the form
N
PK(Z)
=
Czk
n
(pr
+
qrz)
(7)
r=l
where
p,
>
0
and
qr
>
0
are discrete scalespace kernels.
Proof:
The generating function of a kernel on the
form
(6)
is
(pK!z)(x)
=
pr
+
qrz.
As convolution in the
spatial domain corresponds to multiplication of generat
XI
X
X+l
Fig.
3.
To
convolve
a
signal
J;.
with a twokernel K‘*’(n) is equivalent
to
form
a weighted average
of
the sequence
{
f;.
(x)
}:=
~ .
ing functions Proposition
4
gives
us
that
is the generating function of a scalespace kernel. A con
stant scalingfactor
C
or
a translation
qtransl
(z)
=
z
can
not affect the number of local extrema. Therefore these
factors can be multiplied onto
pK
(z)
without changing
k
the scalespace properties.
0
C.
No Real Negative Eigenvalues
of
the Convolution
Matrix
If the convolution transformation
f0,,
=
K
*
Jn
is rep
resented on matrix formf,,,
=
Cfi,,
a matrix with constant
values along the diagonals
=
K( i

j
)
appears. Such
a matrix is called a Toeplitz matrix.
Proposition
6:
Let
K;
Z
+
R
be a discrete kernel with
finite support and filter coefficients
c,
=
K( n).
If for some
dimension
N
the
N
X
N
convolution matrix
has a negative eigenvalue with a corresponding real ei
genvector then
K
cannot be a scalespace kernel.
Proof:
See Appendix A.l.
0
D.
Positivity in the Frequency Domain
The eigenvalues of a Toeplitz matrix are closely related
to the Fourier transform of the corresponding sequence of
coefficients
[7],
[6].
This property allows us to derive an
interesting Corollary from Proposition
6.
Proposition
7:
The Fourier transform
$,(e)
=
K( n) eino
of a symmetric discrete scalespace
kernel
K
with finite support is nonnegative.
Proof:
Let
XiN’
denote the smallest eigenvalue
of
the
convolution matrix of dimension
N
and let
m
denote the
238
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE.
VOL.
12,
NO.
3.
MARCH
1990
CI
CO
CI
.**
CN
CN
**’

minimum value5 the Fourier transform
$K
assumes on
[
a,
n]. As a consequence of a theorem by Grenander
[7,
Section 5.2, p. 651 about the asymptotic distribution
of eigenvalues of a finite Toeplitz matrix it follows that
lim
A!”
=
m
A\”
I
m.
(10)
N+m
If
m
is strictly negative then as limN+
A{”
=
m
it fol
lows that
A\”
will be negative for some sufficiently large
N.
According to Proposition 6 the kernel cannot be a scale
space kernel.
0
E.
Unimodality in the Frequency Domain
If a linear transformation is to be regarded as a smooth
ing transformation it turns out to be necessary that the low
frequency components are not suppressed more than the
high frequency components. This means that the Fourier
transform must not increase when the absolute value of
the frequency increases. The occurring unimodality prop
erty is easiest to establish for circular convolution. In this
case the convolution matrix becomes circulant,6 which
means that its eigenvalues and eigenvectors can be deter
mined analytically.
be the filter coefficients
of a symmetric discrete kernel with c,
=
0
if
I
n
1
>
N.
For all integers M
I
N
it
is required that the transfor
mation given by multiplication with the (2M
+
1
)
x
(2M
+
1
)
symmetric circulant matrix
(1
l), defined by
(
CiM)),,J
=
c,
J
(i,
j
=
0..
M
)
and circulant extension,
should be a scalespace transformation. Then, necessarily
the Fourier transform
$(e)
=
Enrn=
c,e’”*
must be un
imodal on
[
n,
TI.
Proposition
8:
Let
{
c,},”=
C‘M’
=
C
CN
CN
CN
CN
..
CN
5Due
to symmetry of the
kernel,
$K
(0)
assumes only real values.
The
minimum value
does
certainly exist since
$(e)
is a continuous function
and the interval
[
T,
T]
is compact.
61n
a circulant matrix each row is
a
circular shift of the previous row,
except
for
the first row which is a circular shift of the last row.
signal leading to a scalespace violation in the proof of
Proposition
8.
Then, the convolution effect on the “in
terior” periods will be identical to effect on one period by
circular convolution. If the signal consists of a sufficient
number of periods the boundary effects will be negligible
compared to the large number of scalespace violations
occurring in the inner parts. The formal details are some
what technical and can be found in [15, Section 2.61.
Proposition
9:
The Fourier transform
$K
(e)
=
E:=
K( n) ein@
of a symmetric discrete scalespace
kernel
K
with finite support is unimodal on the interval
[a, n] (with the maximum value at
0
=
0).
F. Kernels with Three Nonzero Elements
For a threekernel
K‘3’
with exactly three nonzero con
secutive elements
cPI
>
0,
co
>
0,
and cl
>
0
it is pos
sible to determine the eigenvalues of the convolution ma
trix and the roots of the characteristic equation
analytically. It is easy to verify that the eigenvalues
A,
of
the convolution matrix
are all real and equal to
and that the roots of generating function
pKi3)(z)
=
c]z
I
+
co
+
cIz are
CO
Jc~

~CIC]
2Cl
21.2
=
(14)
From
(13)
we deduce that if co
<
2
6
then for some
sufficiently large
N
at least one eigenvalue of
C‘N)
will be
negative. Thus, according to Proposition 6 the kernel can
not be a scalespace kernel. However, if
ci
I
4c,cI then
both the roots of
pK(3,
will be real and negative. This
means that the generating function can be written on the
form
(7)
and the kernel is a scalespace kernel. Conse
quently, we obtain a complete classification for all pos
sible values of c
co,
and cI. We conclude the follow
ing.
Proposition
10:
A threekernel with positive elements
C~,
co,
and cI is a scalespace kernel if and only if ci
2
~C~C,, i.e., if and only if it can be written as the con
volution of two twokernels with positive elements.
At this moment one could ask oneself if the result can
be generalized to hold for kernels with arbitrary numbers
剩余20页未读，继续阅读
资源评论
 davidlch20151012还不错。多尺度空间的经典英文原文，里面介绍了在离散信号情况下，什么样的滤波核能用于尺度变换
tostq
 粉丝: 1326
 资源: 20
上传资源 快速赚钱
 我的内容管理 展开
 我的资源 快来上传第一个资源
 我的收益 登录查看自己的收益
 我的积分 登录查看自己的积分
 我的C币 登录后查看C币余额
 我的收藏
 我的下载
 下载帮助
安全验证
文档复制为VIP权益，开通VIP直接复制
信息提交成功