Scale-Space Properties of Quadratic Feature Detectors.
AbstractFeature detectors using a quadratic nonlinearity in the filtering stage are known to have some advantages over linear detectors; here, we consider their scale-space properties. In particular, we investigate whether, like linear detectors, quadratic feature detectors permit a scale selection scheme with the "causality property," which guarantees that features are never created as scale is coarsened. We concentrate on the design most common in practice, i.e., one dimensional detectors with two constituent filters, with scale selection implemented as convolution with a scaling function. We consider two special cases of interest: constituent filter pairs related by the Hilbert transform, and by the first spatial derivative. We show that, under reasonable assumptions, Hilbert-pair quadratic detectors cannot have the causality property. In the case of derivative-pair detectors, we describe a family of scaling functions related to fractional derivatives of the Gaussian that are necessary and sufficient for causality. In addition, we report experiments that show the effects of these properties in practice. Thus we show that at least one class of quadratic feature detectors has the same desirable scaling property as the more familiar detectors based on linear filtering.
Introduction
The process of detecting image features across a range of scales is important in
many machine vision applications, and dates at least from Rosenfeld [18] and
Marr [10]. In practical systems using multiscale techniques, features detected at
a coarse scale can determine the flow of processing at finer scales. It is thought to
be important in this context that features detected at a given resolution were not
created gratuitously at that scale, but rather are "grounded" in image detail at
a finer resolution. When a multiscale feature detection method never introduces
features as the scale is coarsened, it has the desirable property of causality. 1
A multiscale feature detection method comprises a way of detecting features,
and a way of selecting the scale of features detected. It is known that edge detectors
which operate by marking edges at zeros or extrema in the output of a linear
differential filter acting on the image have the causality property if scale is selected
by convolution of the image with a Gaussian [2,19], and these results have been
extended to scale selection by anisotropic diffusion [15]. More recently, quadratic
nonlinear filters for feature detection have been proposed as having advantages
over linear filters, particularly in their ability to detect and localize features with
complex structure [6,9,12-14]. However, the question whether these quadratic or
"energy" detectors permit a causal scale selection technique has remained open.
In this paper, we address this question for one-dimensional quadratic feature
detectors when scale is selected by convolution of the image with a scaling function.
We concentrate on detectors with two constituent filters, one even-symmetric and
one odd-symetric, this being the design most widely used in practice. We consider
two special cases of practical interest: quadratic detectors with constitutent filters
related by the Hilbert transform, and with constituent filters related by the first
spatial derivative. We show that, in the case of Hilbert-pair filters, there exists
no scaling function giving the causality property. In the case of derivative-pair
filters, we describe a family of scaling functions related to fractional derivatives of
the Gaussian that are necessary and sufficient for causality. Thus we show that
in the one dimensional case, at least one class of quadratic feature detectors has
the same desirable scaling property as the more familiar detectors based on linear
differential filtering.
The paper is organized as follows. Definitions, notation and assumptions are
1 The term in this context is due to Koenderink [8]. The property has various names in
the literature - "monotonicity' [2]', "well-behavedness' [5]', "nice scaling behavior' [19]', "the
evolution property' [7]'.
given in Section 2. Section 3 states the theorems about the scale-space properties
of Hilbert-pair and derivative-pair quadratic feature detectors; the proofs of the
theorems are in Appendix A. These results are supplemented with experimental
observations reported in Section 4. Section 5 discusses the results and directions
for future work.
2. Scale, causality, and feature detection
Let h(x) be a real-valued signal. We will assume x 2 R, giving direct application
to time signals, images with unidirectionally oriented edges, and images with
features that are one-dimensional on a scale comparable to the detector filter size.
Let oe ? 0 be a real-valued scale parameter, with increasing oe corresponding to
coarser scales. We are interested in finding the location of features in h at a scale
or, more to the point, in how this feature detection process behaves as oe is
varied.
A linear feature detector marks a feature in h(x) at position
local extremum in x of the linearly filtered signal
with Here f(x) is the impulse response of a linear shift invariant filter,
oe (x) is a scaling function of the form g(x=oe)=oe, and ' ' denotes convolution. Scale
selection is a matter of preprocessing the signal h by convolution with the scaling
function for some value of oe; since convolution is associative, it is equivalent to
view this as a matter of using a detector filter with impulse response f   g oe , which
depends on the scale parameter.
A quadratic (or "energy") feature detector marks a feature in the signal h at
position local maximum in x of the nonlinearly
filtered signal
[(f   g oe   h)(x)] 2 (2)
with Here F is the set of impulse responses of the constituent filters
of the detector. The process of scale selection is analogous to the case of the
linear detector (1), but the quadratic nonlinearity here gives the this detector
quite different properties.
It is known [2,19] that the Gaussian g oe (x) / exp(\Gammax 2 =2oe 2 )=oe uniquely gives
a scaling function with advantageous properties with respect to linear feature
detection. In particular, it gives a feature detector with the causality property;
no new features are introduced as oe increases. Our question is whether, like linear
detectors, there are quadratic feature detectors that have the causality property;
that is, whether there exist choices of constituent filters F and scaling function
g oe which guarantee that, for every h, new maxima are never introduced in E as
oe increases.
We will make these assumptions:
1. The constituent filter impulse responses f 2 F , the parameterized scaling
function g oe , and the signal h are functions R 7! R which are sufficiently well
behaved that E as defined in (2) is smooth and bounded.
2. The scaling function g oe (x) is of the form g(x=oe)=oe, for some even function
g(\Delta): the scaling function has no preferred direction or scale.
3. g(\Delta) is not such that g(x=oe)=oe / g(x) for all oe: scaling should do more than
multiply by a scalar.
4. g(x) has a differentiable Fourier transform G(u) (and so g(x=oe)=oe has Fourier
transform G(oeu)).
5. Each f 2 F has a Fourier transform F (u) nonzero for u in some open set of
R.
6. The signal h has a Fourier transform H(u).
These assumptions are in the spirit of those found in the study of scaling functions
for linear differential feature detectors, e.g. [2] and [19]; differences are minor and
technical.
We will concentrate on the case of quadratic feature detectors with a set of
two constituent filters even symmetric and f
symmetric in x. This case comprises all existing practice, and is sufficient to
account for much of the psychophysics of human edge perception, even for stimuli
that are not themselves even or odd symmetric [11].
2.1. Conditions for causality failure
Suppose there is a failure of the causality property for some quadratic feature
detector (2) at E(x 0 ; oe 0 ); that is, a local maximum of E(x; oe) is created with
increasing oe at critical point
of E with respect to x, and generically the set of critical points E x (x;
x
s
x
noncausal degenerate critical point
maxima
x
x
x
xx
xx

Figure

1:
The generic scale-space signature of a causality failure, i.e. a creation
of a new maximum, in E(x; oe). See text for discussion.
in a neighborhood of an upward opening parabola (a "noncausal"
fold catastrophe) as shown in Figure 1 [1,5,16]. E(x; oe) qualitatively changes
shape as a function of x in the neighborhood of the generic noncausal degenerate
critical point, as shown in Figure 2. For oe ! oe 0 , there is no maximum of E in
a neighborhood of x 0 ; at locally cubic in the neighborhood of x
with oe ? oe 0 , there is a local maximum of E near x 0 . Such a creation of a new
maximum of E with increasing oe implies that the feature detector does not have
the causality property.
It is straightforward to express the conditions accompanying such a generic
causality failure in terms of partial derivatives of E at the degenerate critical
point (see for example [19]): a noncausal fold catastrophe occurs in E(x; oe) at a
E(x,
E(x,
E(x,
Figure

2:
Behavior of E(x; oe) as a function of x near a noncausal degenerate
critical point small and positive.
point only if
Thus, showing the existence of a signal h that satisfies the conditions (3) for
as defined in (2) is sufficient to show that the correpsonding multiscale quadratic
feature detector does not have the causality property. Assuming that any signal
that produces a causality failure can be transformed into one that produces a
causality failure, the converse is also true, and the nonexistence of h to
satisfy (3) implies that the detector has the causality property. Alternatively,
following Hummell[7], one could try to prove causality by showing that for any h,
is the solution to a partial differential equation that satisfies a minimum
and a maximum principle. (This minimum-principle approach is, of course, not
useful in proving that a detector does not have the causality property.) Here, we
will take the first approach, and consider whether or not there exists a signal h to
satisfy the conditions (3) for particular quadratic detector designs.
2.2. Toward investigating the causality property
We will consider whether generic causality failures can occur in E(x; oe) at
since E is shift invariant with respect to the signal h, this is without loss
of generality. Here we develop a useful notation for the problem. Essentially,
we will seek an expression for the conditions (3) which reduces the question of
the causality property to the question of solving a constrained system of linear
equations.
(f   g oe
Partial derivatives of E in oe and x involved in the conditions (3) for x consist
of terms of this form, viz
oe
xoe
Recalling from assumption 2 that g oe (x) has the form g(x=oe)=oe, and writing F ,
G, and H for the Fourier transforms of f , g, and h respectively, we have from the
convolution and scaling theorems [4]
(f   g oe
e 2i-ux F (u)G(oeu)H(u) du
and therefore
where G (m) is the mth derivative of G. Note that G (m) (u) is real, and even or odd
in u depending as m is even or odd.
For further simplification of the notation, we represent the signal h(x) as the
sum of K sinusoidal components. It will be clear from the proofs that the results
we state in fact hold in the limit as K !1, so this discretization of the signal's
spectrum is without loss of generality. h(x) is real, and we can write, for some
complex coefficients h
where all the frequencies u k are positive (the DC term contributes nothing of
and '   ' denotes complex conjugation. Thus
We are interested in the case of quadratic feature detectors with a set of two
constituent filters even symmetric and f odd. The
Fourier transforms F e (u) and F o (u) of f e (x) and f o (x) are then even real and
odd imaginary, respectively. Writing h e
k for the even (real) part and h
k be the
imaginary (odd) part of each signal coeffient h k , so that h
we then have, for n even,
even
even
ki
and, for n odd,
ki
Now, we introduce the real column K-vectors f o;m , f e;m , h e , h with the k th
component of each specified as
f e;m
f o;m
Further, let U be the K \ThetaK diagonal matrix of positive frequencies diag(u
Then we have
even
even
In fact, to study the conditions for generic causality failure (3) we will need only
to consider partial derivatives with respect to oe of order 0 and 1. So, to simplify
the notation further, define
Now define the scalar identities
x =2-
oe
xoe =2-
x =2-
oe
xoe =2-
With this notation, we can state the issue as follows: An even-odd two-filter
quadratic feature detector has the (generic) causality property if and only if for
no diagonal positive frequency matrix U do there exist vectors h e , h o to solve the
systems 0
subject to the constraints
The question we are addressing in this paper is thus a question whether these
constrained systems have solutions. We discuss answers to this question in the
following sections.
3. Scale-space theorems
We are considering quadratic feature detectors with a set of two constituent filters
even symmetric and f in x. If one of
the constituent filters is the Hilbert transform of the other (perhaps multiplied by
a nonzero constant), we call it a Hilbert-pair detector. This is the most common
type of quadratic detector in practice; motivation for this design has come from
work in psychophysical modelling[11]as well as consideration of its computational
properties [12,17]. Because of the quadrature phase relationship between the
constituent filters, these are sometimes called "energy" feature detectors.
Suppose a one-dimensional function f(x) has Fourier transform F (u); then
the Hilbert transform of f has Fourier transform i sgn(u)F (u). This case gives a
particularly simple form for the systems (9) and (10), since when the constituent
filters f e and f are Hilbert transforms of each other we have (up to sign) f
We find that there always exist h e , h o to solve these constrained systems,
and so there exists a signal h(x) that leads the detector to a causality failure:
Theorem I. No Hilbert-pair quadratic feature detector has the causality property

The proof, in Appendix A, is constructive, in that for appropriate oe 0 , it gives
linear systems which can be solved to compute a signal h(x) which produces a
causality failure at scale In the case of Gaussian scaling and
differential constituent filters, this can be done at any scale oe. An example of
constructing a causality failure in such a quadratic detector is shown in Figure 3;
compare with Figure 2.
If one of the constituent filters in an even-odd quadratic detector is the first
derivative of the other (perhaps multiplied by a nonzero constant), we call it a
derivative-pair detector. Some properties of derivative-pair detectors have been
been discussed by Kube [9]. As with Hilbert-pair detectors, we obtain simplifications
in the form of the systems (9), (10), since if, for example, f
then f
Here however the result is more favorable, and we find that there exists a family
of scaling functions that give derivative-pair detectors the causality property. This
family includes the familiar Gaussian and its even derivatives, but is somewhat
more general. We define it as follows.
If a function g(x) has a Fourier transform G(u), then the t th derivative of g
(with respect to x) has Fourier transform (2-iu) t G(u). If t is not an integer, then
this is the Fourier transform of a fractional derivative of g. In general, a fractional
derivative of an even, real function will not be real or even. For example, if g oe is
a Gaussian
s
exp
for some nonzero r and positive s, then the t th derivative of g oe has Fourier trans-
2-r exp
\Gammas
which is not real and even as required for a real, even scaling function unless t is
an even integer. The related function
\Gammas
is, however, real and even for all real t. Expressed as a function of oeu
2-r exp
\Gammas
this is the Fourier transform of an admissible scaling function. Lacking a better
name, we will call such a scaling function a modified fractional derivative of the
Gaussian. This defines a family of scaling functions; it includes, for example, the
normal density function (when
and the second derivative of
the normal density function (when
We will find

Figure

3:
An example of a causality failure in Hilbert-pair quadratic detector. A
new maximum appears with increasing oe in E(x; oe) at
The constituent filters are a first-derivative operator and its Hilbert
transform; scaling is by convolution with a Gaussian. The signal h(x)
that produced this causality failure was constructed by solving the
system described in Section 3, with
2.
The dashed, dotted, and solid curves graph E(x; oe) as a function of x
for respectively. The new maximum can be observed in
the E(x; :16) curve to the left of

Figure

4:
Typical scaled impulse responses of the constituent filters f
for the Hilbert-pair quadratic feature detector discussed in the text.
Left, the first derivative of a Gaussian with standard deviation 8 pixels;
right, its Hilbert transform.
that scaling functions from this family are involved in the only known examples
of quadratic feature detectors with the causality property:
Theorem II. A derivative-pair quadratic feature detector has the causality
property if and only if its scaling function is an modified fractional derivative of
the Gaussian.
The proof is in Appendix A. Experiments showing the implications of these
theorems in feature detection on real images are discussed in the next section.
4. Results of experiments
Section 3 stated theorems to the effect that causality failures can occur in quadratic
feature detector schemes which use Hilbert-pair filters and Gaussian scaling, but
cannot generically occur if Gaussian scaling is used with derivative-pair filters.
However, these results leave open the questions whether causality failures occur
often in practice using Hilbert-pair detectors on real images, and whether non-generic
causality failures occur in practice with derivative-pair detectors. We have
attempted to address these questions with experiments we report here.
Six scenes were created by placing matte-surfaced right rectangular prisms and
cylinders randomly on a table; Figure 6 shows a typical arrangement of objects.
Each scene was imaged with camera geometry and illumination such that edges in
Typical scaled impulse responses of the constituent filters f
for the derivative-pair quadratic feature detector discussed in the text.
Left, the first derivative of a Gaussian with standard deviation 8 pixels;
right, its derivative.
the images were predominantly vertical, as shown in the other frame of Figure 6.
A typical row of 512 pixels was taken from each such image; this one-dimensional
signal was subjected to quadratic feature detection as defined in Section 2, using
Gaussian scaling with oe in the range 0.5 to 64 pixels. A region of each image from
which the row of pixels was taken and the graph of the pixel intensities in that
row are shown in Figures 7 - 12.
In one set of experiments, the quadratic detector had as constituent filters the
first-derivative operator and its Hilbert transform; in the other set of experiments,
the quadratic detector had as constituent filters the first-derivative operator and
its first derivative (i.e. the second derivative operator). Impulse responses of the
constituent filters at a scale of 8 pixels are shown in Figures 4 and 5 respectively. In
each experiment, local maxima were detected with no thresholding at scales in the
range 0.5 to 64 pixels, in 0.5 pixel steps. The resulting scale space representations
of the multiscale features found are also shown in Figures 7 - 11. Apparent
causality failures are indicated with arrows.
It is interesting that while the shapes of the constituent filter impulse responses
are quite similar, the performance of these two types of quadratic feature detector
are qualitatively quite different. For each image, the Hilbert-pair quadratic
detector exhibited causality failure. Some features which were introduced with
increasing scale were ephemeral, but others were quite robust and persisted over
a range of scales. The derivative-pair quadratic detector generated no observed
Top: Typical arrangement of objects used in creating the images used
in experiments. Bottom: Image of objects with viewing geometry
creating predominantly vertical edges. A row of pixels from such an
image is used as the one-dimensional signal h(x) for feature detection.
noncausal features. These experimental results are, of course, consistent with the
theoretical results stated in Section 3.
5. Discussion
The scale-space properties of quadratic feature detectors being of potential in-
terest, we have investigated whether any quadratic detectors have the causality
property. We considered one-dimensional derivative-pair and Hilbert-pair detec-
tors, and found that the former, but not the latter, can have the property. Fur-
ther, we showed that there is a family of scaling functions, related to fractional
derivatives of the Gaussian, which are necessary and sufficient for causality with
derivative-pair detectors. We proved theorems to this effect, and showed results
on real images that show that the theoretical results hold in practice.
Ronse[17]has studied Hilbert-pair detectors and concluded, on the basis of the
relation between maxima in E and phases of the Fourier components of the signal
h, that feature points are stable under convolution of the image with a zero-phase
scaling function such as the Gaussian. We emphasize that this is not true for
all features in every h; as we have shown, Hilbert-pair detectors cannot have
the causality property for any scaling function. However, it is true for feature
points relative to which the phases of all Fourier components of h are identical,
for example at which is even or odd symmetric in x. Though it
does not address the performance of Hilbert-pair detectors on more general kinds
of features, it is a remarkable property, and one that is not shared by linear or
derivative-pair quadratic detectors.
We have restricted our scope in various ways, and generalizations of these
results are possible. For example, we have concentrated on the case of one-dimensional
signals. A treatment of higher dimensions could be pursued with the
same kind of techniques; since with increasing spatial dimension there remains
only one scale parameter oe, generic nondegenerate critical points will always have
essentially a one-dimensional structure [1,16]. (The Hilbert transform and the
first derivative do not extend uniquely to higher dimensions, so a family of filters
parameterized by rotation would have to be considered.)
In addition, we have only considered the properties of quadratic detectors with
two constituent filters, one even and one odd symmetric, and only special cases
of these. The cases treated encompass all examples of quadratic detectors in the
literature, but others may be useful to investigate. Some extensions of the results
here are immediate; for example, any two-filter design which leads to independent
Figure

7:
From top to bottom: An image with one-dimensional edges; the graph
of image intensity for the top row of pixels in the image; feature scale-space
generated from that 1D signal with a Hilbert-pair quadratic
feature detector; feature scale-space generated from that 1D signal
with a derivative-pair quadratic feature detector. Gaussian scaling and
periodic convolution are used in each case. The Hilbert-pair detector
exhibits causality failures (indicated by arrows); the derivative-pair
filter does not. See text for discussion.18

Figure

8:
From top to bottom: An image with one-dimensional edges; the graph
of image intensity for the top row of pixels in the image; feature scale-space
generated from that 1D signal with a Hilbert-pair quadratic
feature detector; feature scale-space generated from that 1D signal
with a derivative-pair quadratic feature detector. Gaussian scaling and
periodic convolution are used in each case. The Hilbert-pair detector
exhibits causality failures (indicated by arrows); the derivative-pair
filter does not. See text for discussion.19

Figure

9:
From top to bottom: An image with one-dimensional edges; the graph
of image intensity for the top row of pixels in the image; feature scale-space
generated from that 1D signal with a Hilbert-pair quadratic
feature detector; feature scale-space generated from that 1D signal
with a derivative-pair quadratic feature detector. Gaussian scaling and
periodic convolution are used in each case. The Hilbert-pair detector
exhibits causality failures (indicated by arrows); the derivative-pair
filter does not. See text for discussion.20

Figure

10:
From top to bottom: An image with one-dimensional edges; the graph
of image intensity for the top row of pixels in the image; feature scale-space
generated from that 1D signal with a Hilbert-pair quadratic
feature detector; feature scale-space generated from that 1D signal
with a derivative-pair quadratic feature detector. Gaussian scaling and
periodic convolution are used in each case. The Hilbert-pair detector
exhibits causality failures (indicated by arrows); the derivative-pair
filter does not. See text for discussion.21

Figure

From top to bottom: An image with one-dimensional edges; the graph
of image intensity for the top row of pixels in the image; feature scale-space
generated from that 1D signal with a Hilbert-pair quadratic
feature detector; feature scale-space generated from that 1D signal
with a derivative-pair quadratic feature detector. Gaussian scaling and
periodic convolution are used in each case. The Hilbert-pair detector
exhibits causality failures (indicated by arrows); the derivative-pair
filter does not. See text for discussion.22
Figure

12:
From top to bottom: An image with one-dimensional edges; the graph
of image intensity for the top row of pixels in the image; feature scale-space
generated from that 1D signal with a Hilbert-pair quadratic
feature detector; feature scale-space generated from that 1D signal
with a derivative-pair quadratic feature detector. Gaussian scaling and
periodic convolution are used in each case. The Hilbert-pair detector
exhibits causality failures (indicated by arrows); the derivative-pair
filter does not. See text for discussion.23
rows in the systems (9) and (10) will permit a proof of noncausality along the
lines given for the Hilbert-pair case. Other generalizations may be difficult; the
question of the causality property for quadratic detectors is equivalent to deciding
whether a certain system of quadratic inequalities has a feasible solution, and in
its general form this appears to be a hard problem [3].
One can also raise the question of how important the causality property really
is in feature detector design. It may not be essential in practice to have all
features at every scale continuously traceable to features at scale 0. In our ex-
periments, some of the features introduced with increasing scale in Hilbert-pair
detectors were ephemeral, persisting only over a narrow range of scales. A multiscale
image processing system which computes image representations at only
discrete scales may not observe such short-lived events at all. These ephemeral
features often have low contrast, and are spatially unstable; postprocessing may
be able to eliminate many of them. Further, some persistent noncausal features
may have physical significance, even though they do not appear at some range of
finer scales. In general, scale-space properties may have to be balanced with other
properties of a feature detector, such as reliable detection of desired features in
the first place.
Nevertheless, the type of quadratic detector that has heretofore received most
of the attention in the literature, the Hilbert-pair detector, does not have the
causality property, and these results should direct increased interest toward the
derivative-pair type, which does.

Acknowledgements

This research was supported in part by NSF Research Initiation grant IRI 9211651,
by NSF grant IRI 9306155, and by ONR grant N00014-93-1-0990. The authors
are grateful to John Canny and Bill Helton for useful discussions.



--R

Theory
"Uniqueness of the Gaussian kernel for scale-space filtering,"
"Feasibility testing for systems of real quadratic equations,"
The Fourier Transform and Its Applications
"Singularity theory and phantom edges in scale space,"
"The design and use of steerable filters,"
"Reconstructions from zero crossings in scale space,"
"The structure of images,"
"Properties of energy edge detectors,"
"Theory of edge detection,"
"Feature detection in human vision: A phase-dependent energy model,"
"Feature detection from local energy,"
"Edge detection is a projection,"
"Detecting and localizing edges composed of steps, peaks and roofs,"
"Scale space and edge detection using anisotropic dif- fusion,"
Catastrophe Theory and its Applications
"On idempotence and related requirements in edge detection,"
"Edge and curve detection for visual scene anal- ysis,"
"Scaling theorems for zero crossings,"
--TR
feature detection;quadratic filters;edge detection;causality;nonlinear filtering;energy filters;scale space