Scale-Space Properties of the Multiscale Morphological Dilation-Erosion.
AbstractA multiscale morphological dilation-erosion smoothing operation and its associated scale-space expansion for multidimensional signals are proposed. Properties of this smoothing operation are developed and, in particular a scale-space monotonic property for signal extrema is demonstrated. Scale-space fingerprints from this approach have advantages over Gaussian scale-space fingerprints in that they are defined for negative values of the scale parameter; have monotonic properties in two and higher dimensions, do not cause features to be shifted by the smoothing, and allow efficient computation. The application of reduced multiscale dilation-erosion fingerprints to the surface matching of terrain is demonstrated.
Introduction
There has been an increasing trend to use multiple scales in parallel in image analysis
and computer vision since the pioneering work of Marr and colleagues who appreciated
that the multiscale analysis of images offers many benefits [1], [2], [3], [4].
A major difficulty with any multiscale approach is: how do we relate information obtained
at one scale to that obtained at another? Do we not just have a stack of different
signal descriptions?
One solution to this problem lies in embedding this stack of descriptions in a mathematical
space known as "scale-space" [5]. Then the signal features form continuous paths
in this scale-space and can be tracked from scale-to-scale. Suppose we have a signal,
R and a smoothing kernel g(x; oe) : R n \Theta R! R. The signal smoothed at scale
oe is then given by F : R n \Theta R! R:
where   denotes convolution. F is a function on the (n 1)-dimensional space called
"scale-space"and is known as the "scale-space image" of the signal [5].
The ideas behind scale-space first appeared in a report on expert systems by Stansfield
[6] who was looking at ways to extract features from graphs of commodity prices. The
May 11, 1995
scale-space concept was named, formalised, and brought to image analysis by Witkin [5],
[7]. Both these authors used Gaussian functions as the smoothing kernel:
(2)
The idea is elegant: if scale is considered as a continuous variable rather than a parameter,
then a signal feature at one scale is identified with that at another scale if they lie on the
same feature path in the resulting "scale-space". This technique provides a means for
". managing the ambiguity of scale in an organized and natural way" [5].
A central idea in Witkin's work is that important signal features would persist through
to relatively coarse scales even though their location may be distorted by the filtering
process. However by "coarse-to-fine tracking" they could be tracked back down a path
in scale-space to zero scale to be located exactly on the original signal. In this way the
benefit of large smoothing to detect the major features could be combined with precise
localisation. In a way these linkages across scale are used to overcome the "uncertainty
principle" which states that spatial localisation and frequency domain localisation are
conflicting requirements [8].
A defining feature of scale-space theory, in contrast to other multiscale approaches, is
the property that a signal feature, once present at some scale, must persist all the way
through scale-space to zero-scale (otherwise the feature would be spurious: being caused
by the filter and not the original signal). This is often called a monotone property since
the number of features must necessarily be a monotone decreasing function of scale. If
#[f(x)] denotes the number of features in an signal, then we require,
A continuity property is also implied since the feature paths should be continuous to enable
tracking in scale.
It should be noted at this point that the term "scale- space" is not used consistently
throughout the literature. As various authors have sought to extend and generalise
Witkin's results to higher dimensions and to non-linear smoothing operators, they have
been forced to emphasize certain aspects of the theory and de-emphasize others. The
emphasis in the present paper is clearly on the monotone property for signal features, we
May 11, 1995
use signal extrema not zero-crossings as the signal feature of importance, we no-longer use
a linear smoothing operator, and we do not restrict the scale parameter to non-negative
values. As with others before us, we also feel justified in using the term "scale-space" for
our theory.
Koenderink, emphasised the differential structure of scale-space, that is, what are the
laws governing the shape of the surface surrounding an arbitrary point F
space? Koenderink [9] showed that Gaussian filtering is the Green's function [10] of the
differential equation known as the "Heat equation". That is, the scale-space image:
Z
with g(x; oe) given by (2) is a solution of:
@oe
With this approach, the original signal is the initial condition
into scale-space under control of equation (5).
The solutions to equation (5) obey a "maximum principle" [11] which states that: if
F is a solution to equation (5) on the open and bounded region with F of class C 2 and
continuous on the closure of the region. Then F assumes its maximum at some point on
the boundary of the region or for
It has been shown that the maximum principle implies a evolution property for zero-crossings
of the solution of the heat equation [12]: Let C be a connected component of
the set of zero-crossings in the domain:
property ensures that a new zero-crossing component cannot begin at non-zero scale, and
that all zero-crossing components can be traced to features on the original signal.
This evolution property, called "causality" in [9], under certain conditions leads uniquely
to the scaled Laplacian-of-Gaussian filter [13]. Important later work generalizing the heat
equation has shown that space variant anisotropic operators can also satisfy causality
while not degrading image edges with increasing scale [14]. The maximum principle and
its evolution or causality properties are indeed one way to extend Witkin's 1-D results to
images and higher dimensions. However, part of the elegance of the 1-D result is lost since,
"a closed zero-crossing contour can split into two as the scale increases, just as the trunk of
a tree may split into two branches" [15]. This may be a problem as two separate contours
at a coarse scale may in fact be caused by the same signal feature (see, for example, the
diagrams in [16]). The monotone property is therefore not valid, which is a disadvantage
with the linear scale-space formulations using zero-crossings in 2-D and higher dimensions.
Morphological operations[17], [18] can remove structure from a signal, and therefore
others have found them suitable as scale-space smoothers. Chen & Yan [19] have used a
scaled disk for the morphological opening of objects in binary images to create a scale-space
theorem for zero-crossings of object boundary curvature. These results have since
been extended to general compact and convex structuring elements [20]. Unfortunately,
these results only apply to zero-crossings of boundary curvature of objects in binary im-
ages, although they can also be applied to 1-D functions, through the use of umbras [21].
However, the extension to higher dimensions seems problematic [22].
Recent work has also considered the construction of a scale-space through scaled morphological
operations [23]. Van den Boomgaard's approach proceeds by considering the
non-linear differential equation which governs the propagation of points on a signal into
scale-space under morphological operations with a scaled convex structuring function.
However, this work mainly examined the differential structure of the scale-space itself and
did not explicitly emphasize a monotonic property. All the points on a signal propagate
into scale-space and Van den Boomgaard did not explicitly consider special signal points
(features) except for singular points which do not obey a monotonic property.
Alvarez and Morel have recently presented an excellent theoretical unification and ax-
iomization of many multiscale image analysis theories including most of those mentioned
above [24]. Once again this approach emphasizes the partial differential equations governing
the propagation of the image into scale-space. Here the causality principle is essentially
the maximum principle already discussed. The importance of image features and
the monotonic property is not stressed in this multiscale theory.
A discussion of scale-dependent morphology would not be complete without a brief discussion
of granulometries. Granulometries as introduced in [25] are set valued mappings
that satisfy axioms choosing to exactly generalize the physical meaning of a size distribution
6or "sieving" [17]. This means, the mappings must be anti-extensive, increasing, and
idempotent, which implies (under some general restrictions) that they are given by scaled
morphological openings. Granulometries enable the distribution of particle sizes in an image
to be found, and have been extended to gray-scale images [26], and to give a shape-size
descriptor [27]. In summary, granulometries do use scale dependent morphology, but do
not distinguish image features throughout scale-space, and the emphasis of the approach
is quite distinct from scale-space theory.
The way we have chosen to extend Witkin's work is to return to first principles. If the
aim is to examine the "deep structure" of images then we should seek to relate signal
features across differing scales of image blurring. To be a scale-space theory, we require a
monotonic property that ensures that increasing scale removes features from the image.
In Witkin's original work, extrema of the signal and its first derivative are seen as
fundamental signal features [7]. However, as discussed in [16], there is no convolution
kernel with the property that it does not introduce new extrema with increasing scale
in 2-D, so our monotonic property does not hold for linear filters and signal extrema.
We have found that scaled morphology, in particular dilation and erosion, can give a
monotonic property for signal extrema, and indeed that this result holds for signals on
arbitrary dimensional space. We have also found a way to combine the dilation and erosion
to give meaning to negative values of the scale parameter, thereby creating a full-plane
scale-space.
The multiscale dilation-erosion is introduced in Section III and its scale-space properties
are discussed in Section IV. An application to surface matching is briefly described in
Section V, followed by a summary and conclusion in which we indicate some advantages
of this approach over Gaussian scale-space. The proofs of the various mathematical results
are placed in the Appendix. Parts of this work can be found in earlier conference papers
[28], [29] and more fully in [22].
II. Multiscale Morphology
We use the notation of [18] to introduce morphology on functions. Denoting the func-
R, the two fundamental operations of grayscale
morphology are:
The dilation of the function f(x) by the structuring
function g(x) is denoted by (f \Phi g)(x), and is defined by
(f \Phi
The erosion of the function f(x) by the structuring
function g(x) is denoted by (f \Psi g)(x), and is defined by
x is the translate of D, D
D is the reflection of D, -
refer to the supremum (least upper bound) and infimum
(greatest lower bound), of f [30]. In the discrete case where the function is a finite set of
points, maxfg and minfg are used.
In general, the result of dilation or erosion depends on the position of the "origin" of
the structuring function. However, since we wish to avoid level-shifting effects, we will
require:
sup
and to avoid horizontal translation effects, we require,
We assume that all structuring functions discussed in this paper satisfy equations (6) and
(7).
A. Scale Dependent Morphology
We propose to make the above morphological operations scale dependent by the use of
the scaled structuring function,
where oe is a scale parameter and G Gg. This form of functional scaling
is compatible with the idea of a scaled (hemi)sphere in Euclidean morphology, with radius
May 11, 1995
as the scale parameter, which we can write as:
with G joejg.
Returning to equation (8), if G is bounded, say, G ' fx : kxk ! Rg for some R with k:k
the Euclidean norm, then g oe is defined on G oe so the support region of
the structuring function scales correctly, in particular:
However, further conditions need to be imposed on the structuring function to ensure
reasonable scaling behaviour. Consider the threshold set of the structuring function
G oe To incorporate the idea of scaling we wish to
ensure that for all t ! 0:
for all R ? 0:
In terms of the functions involved this is equivalent to,
Expanding equation (15) we have,
G: (17)
Divide by joe 2 j and let
G: (18)
This relation indicates that a chord from the origin to any point on the structuring function
should lie on or below the structuring function (see figure 1). This, together with the
non-positivity condition (6), means that the structuring function should be monotonic
decreasing along any radial direction from the origin.
Place figure 1 near here
Fig. 1.
In almost all practical cases we will use the smaller class of continuous convex 1 structuring
functions. Typical scaled structuring functions include:
"flat" structuring functions g oe scaled disks where
spheres g oe
circular poweroids g oe the circular paraboloids
2.
Examples of various 2-D structuring functions are shown in figure 2.
Place figure 2 near here
Fig. 2.
B. Multiscale Dilation-Erosion Scale-Space
With a scaled structuring function of the previous section we propose to join dilation and
erosion at zero scale to form a single multiscale operation which unifies the morphological
operations as follows:
Definition 3 (Multiscale Dilation-Erosion): The multiscale dilation-erosion
of the signal f(x) by the scaled structuring function g oe (x) is denoted 2 by f ~ g oe ,
1 By convention, in mathematical morphology, a "convex" function has any chord entirely on or below the
function. Note, this would be called a "concave" function in analysis.
2 the symbol "~" has previously been used by [17] to refer to the "Hit or Miss Transform" which does not appear
in this paper.
and is defined by
(f \Phi g oe )(x) if oe ? 0;
(f \Psi g oe )(x) if oe ! 0.That is, for positive scales we perform a dilation, for negative scales an erosion. With this
method scale may be negative; it is joej which corresponds to the intuitive notion of scale.
Unlike linear operators, dilation and erosion are "non-self-dual" [31], positive and negative
scales in scale-space contain differing aspects of the information in a signal. As we shall
see, positive scales pertain to local maxima in the signal, whereas negative scales pertain
to local minima. Other authors (eg. [32]) have considered scaled dilations and erosions
separately, and it is well known from mathematical morphology that if f is sufficiently
smooth, then both lim oe!0 (f \Phi g oe but we explicitly
combine these operations into a single operation. We specifically wish to consider the
scale-space fingerprint for positive and negative scales as a whole since the information
content of a signal is expanded into this entire region. This approach will also be partially
supported by the continuity properties developed in section III.B.
Having proposed a suitable operator, we now define the associated scale-space image
defined by (cf. equation (1)):
where the (n 1)-dimensional space given by D \Theta R is known as the "multiscale dilation-
erosion scale-space".
Since we are using the operations of mathematical morphology to smooth a signal, the
well known geometric visualizations of dilation and erosion are intuitively helpful: For
the moment, take the scaled structuring function to be a ball with the radius as a scale
parameter: a positive radius corresponds to rolling the ball along the top of the "surface"
of the signal, and a negative radius to rolling the ball along the underneath. The smoothed
signal can be visualised as the surface traced out by the centre of the ball when it is traced
over the top (dilation) or underneath (erosion) of the "surface" of the signal. We illustrate
this operation for a 1-D signal in figure 3.
Place figure 3 near here
Fig. 3.
Intuitively, this new surface is smoother (in the sense of having smoother and less hills)
than the original signal, and furthermore the larger the radius the smoother the "filtered"
surface becomes. In the limits: as the radius approaches zero the original image is re-
covered; and as the radius approaches infinity the output becomes flat. It should be
apparent that if the ball touches the top of a hill (local maxima) then a hill will appear
on the output at exactly that point. If however the radius is such that the ball is prevented
from touching that hill by nearby hills, then no hill will appear at that point on the
output, and more importantly that hill cannot reappear for any increased value of radius,
r. In more precise terms: we propose that the number of local maxima is a monotone
decreasing function of r. This suggests a scale-space monotonic principle which is treated
more rigorously in the next section.
III. Properties of Multiscale Dilation-Erosion
The properties of the smoothing will be introduced formally in the form of propositions
building to a theorem which is the central result of the paper. In outlining the results of
this chapter we will often make use of the duality between dilation and erosion
indicates the reflection of g,
Therefore many results on f ~ g oe for oe ? 0, which corresponds to dilation, can be immediately
applied to oe ! 0, corresponding to erosion. In practice most structuring functions
are symmetrical about the origin so that - and in this case the erosion of a signal by
a structuring function may be obtained by negating the signal performing a dilation with
that same structuring function and negating the result.
A. Properties of the Filter Support
The sup and inf operations in the multiscale dilation-erosion need not be taken over
the full domain G but only within a smaller region S ae G. This region, can be called the
"support region" of the smoother. In general, if we can reduce the area (volume) of the
support region we decrease the time for computation of the smoothing operation.
Assume that the signal is non-negative and bounded, that is, there exists some M - 0
such that 0 -
Proposition 1: If we let S
oe (t) - \Gammaf (x)g then ,
(f \Phi g oe
and,
(f \Psi g oe
:Using the inequality 0 - f(x) - M for all x 2 D a more general support S g can be found
that is independent of position x. Putting the extreme values for f(x) into the formulae
for S p and S n we obtain:
It is mathematically convenient to represent the support regions as closed sets, so from
now we let S p ; S n or S g denote the closure of the respective regions if necessary. Using
the support region S p ; S n or S g enables the computation of the multiscale dilation-erosion
to be made more efficient. These support regions depend on scale, in particular from
equations (10) and (14) we see that they approach a single point at the origin as oe ! 0,
importantly,
B. Continuity and Order Properties of the Scale-Space Image
The multiscale dilation-erosion (definition 3) consists of three parts corresponding to
positive, zero, or negative values of the scale parameter. Since the structuring function
May 11, 1995
is non-negative at the origin [see eq. (7)], the dilation is extensive and the erosion anti-
extensive, that is (f \Phi g) - f and (f \Psi g) - f . Thus we have the result,
However, the justification for the joining of the multiscale dilation and erosion would be
considerably strengthened if we can show the stronger result that both operations approach
f(x) as the scale parameter approaches zero from above and below. In other words it is
natural to consider the behaviour of the scale-space image F (x; oe) across the "seam" at
in scale-space. This can be done on the grounds of continuity and we have the
following proposition.
Proposition 2: If the bounded signal f(x) is continuous at some x 2 D, then
the scale-space image F (x; oe) is continuous with respect to oe at
That is, at points x where f(x) is continuous, F
A careful study of the proof of proposition 2 reveals that a slightly stronger result holds,
in fact continuity of the signal is not necessary for the one-sided limits to converge to the
signal. At points
, and at points x = x l where f(x l ) is "lower semi-continuous" (l.s.c.)
F
We recall that a function f is said to be "upper semi-continuous" at c if the non-deleted
limit Lim x!c sup Further f is "lower semi-continuous" at c iff \Gammaf (c) is
u.s.c. Upper semi-continuous functions are often used to model "pictures" [17] since their
threshold sets, are closed sets.
If the structuring function is sufficiently smooth this property transfers to the scale-space
image and we have the following proposition:
Proposition 3: If the structuring function g(t) is a continuous function on R n
then the scale-space image is continuous for all x 2 D; oe 6=
The following point-wise order properties of the scale-space image follow directly from the
extensivity, and increasing properties of the morphological dilation and erosion [18].
Proposition 4: The scale-space image F (x; oe )(x) possesses the
following properties:
ff(t)g for all x 2 D;
ff(t)g for all x 2 D;
for all oe Signal Extrema in Scale-Space
Propositions 2 to 4 show that the scale-space image has good continuity and order
properties but we have yet to show the essential scale-space monotonic property. The
major result of this paper is a theorem which shows in a precise way how f ~ g oe becomes
smoother with increasing joej. Further we show that the monotonic property holds for local
extrema of the signal so this is the signal "feature" appropriate to the multiscale dilation-
erosion scale space. Prior to presenting this theorem some necessary partial results are
obtained.
The first result relates the position and amplitude of a local maximum (or minimum) in
the filtered signal to that in the original signal.
Proposition 5:
Let the structuring function have a single maximum at the origin, that is, g(x) is
a local maximum implies
(a) If oe ? 0 and (f ~ g oe )(x max ) is a local maximum, then, f(x max ) is a local
maximum of f(x) and (f ~ g oe )(x
(b) If oe ! 0 and (f ~g oe )(x min ) is a local minimum, then, f(x min ) is a local minimum
of f(x) and (f ~ g oe )(x min
We are now able to relate a signal feature at non-zero scale to the original signal (zero
scale). However to obtain a monotonic result we need the next proposition.
Proposition
Let the structuring function have a single local maximum at the origin, that is,
g(x) is a local maximum implies
(a) If oe 0 ? oe ? 0 and (f ~ g oe 0
local maximum, then, (f ~ g oe )(x max ) is
a local maximum and, (f ~ g oe )(x
(b) If oe local minimum, then, (f ~ g oe )(x min ) is
a local minimum and, (f ~ g oe )(x min
These propositions provide very important scale-space results because they enable coarse-
to-fine tracking in the scale-space image. If a signal feature (extrema) appears at some
scale oe 0 it also appears at zero scale and all scales in between. Stated as a monotonic
property, we can state that the number of features may not decrease as scale approaches
zero. This property is now encapsulated in a theorem.
Theorem 1 (Scale-Space Monotonic
a bounded function, scaled structuring function satisfying
the conditions of proposition 6, and the point sets, E is a local
maximum g, and, E min is a local minimum g, denote the local extrema
of f . Then, for any oe 1
and,
Proof:
Suppose the theorem is false and E max (f~g oe 4
then there exists some x max 2 D such that F local maximum but
is not, which contradicts proposition 6(a). The case for E min is proved
similarly using proposition 6(b). 2
This theorem is actually stronger than required since it governs the positions of the extrema
as well as their number. To obtain a monotone property of the form of equation (3), we
need some R such that
For the practical case where E ae Z n we simply choose card[E], the number of
points in E. We have the following corollary to the theorem:
Corollary 1 For R, such that
for any oe 1
Proof: The proof follows from the direct substitution of (25) in Theorem 1. 2
Therefore, Corollary 1 is a monotone property of the form of equation (3).
We have shown that the number of features may not increase with increasing scale
but we have not shown that they decrease! Indeed with some (artificial) signals the
number of extrema is constant across all scales. For example, if
are independent
of oe. If a signal, however, contains information at different scales this will generally be
reflected as a decrease in the number of features with increasing joej. If the signal has a
single unique global maximum (minimum), then for sufficiently large positive (negative)
scale, there remains only a single feature in the scale-space image.
Theorem 1 provides one of the "scale-space axioms" of Lindeberg [34]
"The essential requirement is that a signal at a coarser level of scale should contain less
structure than a signal at a finer 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 increase as we go from a finer to a coarser level of scale."
The other axioms are also satisfied with appropriate modifications:
ffl All signals should be defined on the same domain; in other words no pyramid representations
will be used.
ffl An increasing value of the scale parameter oe should correspond to coarser levels of scale
and signals with less structure. Particularly, should represent to the original
signal. Note: this axiom is satisfied for (oe - 0), for (oe - decreasing value of oe
corresponds to signals with less structure.
ffl All representations should be generated by convolutions of the original image with a
kernel (linear shift-invariant smoothing). Note: the morphological convolution is shift-
invariant, however it is increasing [35] instead of being linear.
These axioms being satisfied, we are justified in claiming the construction of a "scale-
space".
D. Fingerprints
The "scale-space fingerprints" are plots, versus scale, of the point sets of the positions
of the signal features, we define:
Definition 4 (Multiscale Dilation-Erosion Scale-Space Fingerprint): The
multiscale dilation-erosion scale-space fingerprint is a plot, versus scale, of the
scale-dependent point-set:
oe ):Such a plot for a uniform random noise signal is shown in figure 4.
Place figure 4 near here
Fig. 4.
The full fingerprint requires intensive computation as the signal must be smoothed at
multiple scales. For some applications it may be sufficient to use a subset of the fingerprint,
the "reduced fingerprint" which is defined as:
(Reduced Multiscale Dilation-Erosion Scale-Space Finger-
print): The reduced multiscale dilation-erosion scale-space fingerprint is defined
as:
0.In figure 5 we plot the reduced fingerprint for a uniform random noise signal .
Place figure 5 near here
Fig. 5.
We note from figure 5 that the reduced fingerprint consists of vertical lines only. This
follows directly from Theorem 1 which shows that the multiscale dilation (erosion) preserves
the location of signal maxima (minima). With regard to the computation of this
reduced fingerprint, we note that having determined the spatial position of these lines from
May 11, 1995
the extrema of the original signal, we need only to determine the scale at which each line
ends. Thus, for an n dimensional signal the reduced fingerprint can be represented as a
set of (n 1)-tuples. The reduced fingerprint can be computed without signal smoothing
and an efficient algorithm has been presented elsewhere [36]. For a signal of N points,
finding the local extrema has a complexity of O(N ), and for k extrema, finding the reduced
fingerprint is O(k).
The applications of this approach and its fingerprints are no doubt many, and mainly
unexplored. However as an example we briefly describe in the next section the use of the
reduced multiscale dilation-erosion fingerprint in the matching of surfaces [29].
IV. Surface Matching Using Multiscale Dilation-Erosion Fingerprints
From the previous section we see that for 2-D signals the reduced fingerprint can be
compactly represented as a set of triples, that is FP
We do not expect the reduced fingerprints to uniquely define a signal, however they
define equivalence classes, and if a set of surfaces are sufficiently non-regular and dense
in local extrema the reduced fingerprints may be useful in representing the surfaces for
efficient matching.
As an example we wish to match mountain features in a 512 \Theta 512 pixel digital elevation
map (DEM) where the pixel spacing is 30m. We wish the procedure to recover, location,
rotation, and magnification parameters from reference regions in a database.
To obtain the database regions, eight circular regions of radius 40 pixels, each surrounding
a major feature (the origin), were selected from the DEM. These regions are shown in
figure 6.
Place figure 6 near here
Fig. 6.
To add noise and distortion to the problem, and to provide a test of the algorithm, the
selected regions were re-sampled at 15m spacing, rotated \Gamma30 ffi about the origin, magnified
by 1.25 in both height and spatial extent, re-sampled to a 30m grid and smoothed by a
Gaussian filter of unit scale. These resulting database regions are shown in figure 7.
Place figure 7 near here
Fig. 7.
A. Method
The matching procedure proceeds by hypothesise and verify steps. The structuring
function used is a scaled sphere.
1. For each model in the database we select the dominant feature (the pixel of maximum
height). Using the dominant feature as the origin we obtain the reduced fingerprint of
the model in polar co-ordinates. This takes the form of a list of (r; '; oe) values. Under
magnification, translation, and rotation, the ratio r=oe remains constant and therefore
can be used to match features. Polar coordinates are used to facilitate the matching
of features in rotated models. This list is sorted by scale and stored in the database.
2. The reduced morphological scale-space fingerprint of the test scene is then found using
Cartesian co-ordinates.
3. To form hypotheses, features in the scene with large assigned scales are found and
placed in a list. These features may correspond to model origins. Any such feature
with a nearby feature matching the r=oe ratio of a model feature generates a hypothesis
for the next stage. Other features in the list are discarded. Each hypothesis is in the
model: m; at position: (x; y); at angle: OE; at magnification: M .
4. Each hypothesis is then verified or rejected according to whether, under that hypo-
thesis, a sufficient proportion of the features in the model match features in the scene
and thus are consistent with the hypothesis. Experimentally, an acceptance value of
25% was found to give reliable matching while allowing for missing features due to
noise or occlusion. For efficiency, the matching process is done in order of coarse-to-
fine scales. Since we hypothesise using large scale features and verify using finer scales,
this approach corresponds to the coarse-to-fine tracking of scale-space [7].
B. Experimental Results
The DEM scene consists of 1133 extrema. With the parameters used, the hypothesis
generation step generates 45 hypotheses. The recognition procedure quickly and correctly
May 11, 1995
identifies all the regions and estimates the position, angle, and magnification parameters.
The exact and recovered region parameters are shown in table I.


I
Mountain recognition: region parameters and recovered region parameters from the
recognition process
scene parameters
model position angle magnitude
6 192, 304
recovered parameters
model position angle magnitude
6 193.0, 303.7 30.4 0.798
8 307.9, 99.3 30.2 0.802
Indicative run times for the various parts of the procedure on a Silicon Graphics Personal
Iris 4D/35 computer are: Obtain fingerprint of each model 0.5s; Obtain fingerprint of scene
121s; Generate hypotheses 0.7s; Verify hypotheses 0.3s.
V. Discussion and Conclusion
A scaled morphological dilation-erosion operation has been introduced for the scale-space
smoothing of signals which can be represented as bounded real functions on R n . The
multiscale dilation-erosion is translation-invariant, non-linear (increasing) and dependent
on a real scale parameter. The smoothed signals taken as a whole can be considered as a
function on R n+1 , the so-called "scale-space". This scale-space image exists for negative as
well as positive scale and thus is "more expanded" than the Gaussian scale-space image
which only exists for non-negative scale. The scale-space image has good continuity and
order properties. The position and height of extrema in the signal are preserved with
increasing scale (maxima for scale ? 0 and minima for scale ! 0), until they vanish. A
monotonic property for these signal features has been demonstrated. Fingerprint diagrams
from this scale-space may be used to represent signals and are of use in signal matching.
To summarise, the multiscale dilation-erosion scale-space fingerprint differs from the
Gaussian scale-space fingerprint in that it:
ffl possesses monotonic properties in 2 and higher dimensions;
ffl represents local extrema instead of zero-crossings;
ffl exists for negative as well as positive scale.
The reduced fingerprint multiscale dilation-erosion scale-space fingerprint which consists
of local signal maximums only for positive scale and local signal minimums for negative
scale. This reduced fingerprint:
ffl consists of vertical lines only (since the position of signal features in not altered by the
ffl is equivalent to a set of (n 1)-tuples, where n is the dimension of the signal;
ffl can be efficiently computed without signal smoothing.
The results of surface matching in a DEM scene using the reduced fingerprint have been
presented.
It is important to note the limitations and restrictions on the proposed theory. In essence
we return to the early days of scale-space theory by placing emphasis on the importance
of signal features, and the tracking of these features through scale.
Modern scale-space theory seems to concentrate on powerful mathematical results describing
2the axiomatic bases and the differential structure and invariants of the various
scale-spaces [37], [24], while important theoretically, causality in the form of the maximum
principle on PDE's, has taken precedence over a monotonic principle for signal features.
We have emphasised such a monotonic principle in this paper.
The utility of this approach has yet to be demonstrated, in particular work is needed on
the computation, stability, inversion and application of the full fingerprint. The selection of
structuring function is another area mostly unexplored although dimensionality arguments
[38] would suggest spheres for range images, and elliptic poweroids for intensity images
[39]. In 1-D, the non-creation of maxima (minima) implies the non-creation of minima
(maxima) due to the interleaving of maxima and minima, in higher dimensions this does
not necessarily hold. We have as yet no results on these other possible monotonic properties
in higher dimensions.
Since we do not use an averaging filter for signal smoothing the question of the sensitivity
of this method to signal noise naturally arises. As the dilation and erosion depend on the
extreme values of the (additively weighted signal) in the neighbourhood of a point, impulse
noise in particular will upset the method. Additionally, almost any high-frequency noise
will introduce many new local extrema into the signal causing many spurious features in
the analysis. For independent and identically distributed noise on a featureless image, the
probability that a given pixel has a higher or lower value than all its 8 neighbours due to
the noise is approximately 2 \Theta 0:5 up to N 2extrema may be introduced into an
N \Theta N image.
There are at least two ways to consider the question of noise: one approach is to say
that if noise is present in the signal it should be filtered out before the signal is analysed.
Depending on the nature of the noise various methods may be appropriate, from linear
filters, to more modern and powerful techniques such as the "data sieve" [40], or for a
morphological flavour, the clos-opening or open-closing [41], [42]. In the DEM surface
matching described previously, pre-processing of the noisy database regions with a Gaussian
filter per region, which was considered appropriate for
this application.
A second view considers noise as "small-scale" features. Due to the low-pass nature
May 11, 1995
of the linear scale-space approaches, high frequency noise is constrained by the signal
smoother to the lower reaches of scale-space where it can be ignored if necessary. With our
proposed approach, this is not true, scale does not simply relate to inverse frequency, small-scale
features may crowd the region near zero in scale-space, but these do not necessarily
correspond to noise in the usual sense. A high amplitude impulse will be seen as a large
scale feature especially if it is on a relatively flat region on the signal.
In the final analysis it must be the application which determines if the definition of
"scale" embodied in the proposed method is useful or otherwise.

Acknowledgements

The work reported in this paper was undertaken with the financial assistance of a QUT
Postgraduate Research Award. The comments of V. Chandran, and A. Zoubir on earlier
drafts are appreciated as are the valuable comments of the referees.



--R


"Theory of edge detection"
"A computational theory of human stereo vision"
"Bandpass channels, zero-crossings, and early visual information pro- cessing"
"Scale-space filtering"
"Conclusions from the commodity expert project"
"Scale space filtering: a new approach to multi- scale description"
"The uncertainty principle in image processing"
"The structure of images"
Theory and Problems of Partial Differential Equations
Maximum Principles in Differential Equations
"Reconstructions from zero crossings in scale space"
"Uniqueness of the gaussian kernel for scale-space filtering"
"Scale-space and edge detection using anisotropic diffusion"
"Scaling theorems for zero crossings"
"A multiresolution hierarchical approach to image segmentation based on intensity extrema"
Image Analysis and Mathematical Morphology
"Image analysis using mathematical morphology"
"A multiscaling approach based on morphological filtering"
"Shape analysis using morphological scale space"
"Grayscale morphology"
Morphological Scale-Space With Application to Three-Dimensional Object Recognition
"The morphological structure of images: The differential equations of morphological scale-space"
"Formalization and computational aspects of image analysis"
Random Sets and Integral Geometry
"Euclidean gray-scale granulometries: Representation and umbra inducement"
"Pattern spectrum and multiscale shape representation"
"Morphological scale-space"
"Morphological scale-space fingerprints and their use in object recognition in range images"
Introduction to Real Analysis
Image Analysis and Mathematical Morphology.

The Elements of Real Analysis
"Scale-space for discrete signals"
"The algebraic basis of mathematical morphology: I. dilations and erosions"
"Morphological scale-space fingerprints and their use in 3-D object recognition"
"Scale space: Its natural operators and differential invariants"
"Dimensionality in image analysis"
"On dimensionality in multiscale morphological scale-space with elliptic poweroid structuring functions"
"Properties of a series of nested median filters, namely the data sieve"
"Morphological filters - part I: Their set-theoretic analysis and relations to linear shift-invariant filters"
"Morphological filters - part II: Their relations to median, order statistic, and stack filters"
--TR

--CTR
Christoph Lrig , Thomas Ertl, Hierarchical volume analysis and visualization based on morphological operators, Proceedings of the conference on Visualization '98, p.335-341, October 18-23, 1998, Research Triangle Park, North Carolina, United States
Anant Madabhushi , Jayaram K. Udupa , Andre Souza, Generalized scale: theory, algorithms, and application to image inhomogeneity correction, Computer Vision and Image Understanding, v.101 n.2, p.100-121, February 2006
C. L. Luengo Hendriks , G. M. P. van Kempen , L. J. van Vliet, Improving the accuracy of isotropic granulometries, Pattern Recognition Letters, v.28 n.7, p.865-872, May, 2007
Bogdan Raducanu , Manuel Graa , F. Xabier Albizuri, Morphological Scale Spaces and Associative Morphological Memories: Results on Robustness and Practical Applications, Journal of Mathematical Imaging and Vision, v.19 n.2, p.113-131, September
A. Meijster , M. H. F. Wilkinson, A Comparison of Algorithms for Connected Set Openings and Closings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.484-494, April 2002
Alessandro Duci , Anthony Yezzi , Stefano Soatto , Kelvin Rocha, Harmonic Embeddings for Linear Shape Analysis, Journal of Mathematical Imaging and Vision, v.25 n.3, p.341-352, October   2006
A. Engbers , R. Van Den Boomgaard , A. W. M. Smeulders, Decomposition of Separable Concave Structuring Functions, Journal of Mathematical Imaging and Vision, v.15 n.3, p.181-195, November 2001
M. Ceccarelli , A. Petrosino, A parallel fuzzy scale-space approach to the unsupervised texture separation, Pattern Recognition Letters, v.23 n.5, p.557-567, March 2002
B. Raducanu , P. Sussner , M. Graa, Steps towards one-shot vision-based self-localization, Biologically inspired robot behavior engineering, Physica-Verlag GmbH, Heidelberg, Germany,
Anthony J. Yezzi , Stefano Soatto, Deformotion: Deforming Motion, Shape Average and the Joint Registration and Approximation of Structures in Images, International Journal of Computer Vision, v.53 n.2, p.153-167, July
Andrew Senior , Rein-Lien Hsu , Mohamed Abdel Mottaleb , Anil K. Jain, Face Detection in Color Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.696-706, May 2002
Bernhard Burgeth , Joachim Weickert, An Explanation for the Logarithmic Connection between Linear and Morphological System Theory, International Journal of Computer Vision, v.64 n.2-3, p.157-169, September 2005
Joachim Weickert , Seiji Ishikawa , Atsushi Imiya, Linear Scale-Space has First been Proposed in Japan, Journal of Mathematical Imaging and Vision, v.10 n.3, p.237-252, May 1999
Ulisses Braga-Neto , John Goutsias, Object-Based Image Analysis Using Multiscale Connectivity, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.892-907, June 2005
scale-space fingerprints;scale-space filtering;monotonic property;multiscale morphology;signal analysis