Scale-Space Filtering

1. Introduction

Hardly any sophisticated signal understanding task can be performed using the raw numerical signal values directly; some description of the signal must first be obtained. An initial description ought to be as compact as possible, and its elements should correspond as closely as possible to meaningful objects or events in the signal-forming process. Frequently, local extrema in the signal and its derivatives­ and intervals bounded by extrema- are particularly ap­ propriate descriptive primitives: although local and closely , tied to the signal data, these events often have direct semantic interpretations, e.g. as edges in images. A description that characterizes a signal by its extrema and those of its first few derivatives is a qualitative description of exactly the kind we were taught to use in elementary calculus to "sketch" a function .

A great deal of effort has been expended to obtain this kind of primitive qualitative description (for overviews of this literature, see [1,2,3].) and the problem has proved extremely difficult. The problem of &cafe has emerged con­ sistently as a fundamental source of difficulty, because the events we perceive and find meaningful vary enormously in size and extent. The problem is not so much to eliminate fine-scale noise, as to separate events at different scales arising from distinct physical processes.[4] It is possible to introduce a parameter of uale by smoothing the signal with a mask of variable size, but with the introduction of scale-dependence comes ambiguity: every setting of the scale parameter. yields a different description; new extremal points may appear, and existing ones may move or disap­ pear. How can we decide which if any of this continuum of descriptions is "right"?

There is rarely a sound basis for setting the scale parameter. In fact, it has become apparent that for many tasks no one scale of description is categorically correct: the physical processes that generate signals such as images act at a variety of scales, none intrinsically more interest­ ing or important than another. Thus the ambiguity intro­ duced by scale is inherent and inescapable, so the goal of scale-dependent description cannot be to eliminate this am­ biguity, but rather to manage it effectively, and reduce it where possible.

This line of thinking has led to considerable interest in multi-scale descriptions [5,2,6,7]. However, merely com­ puting descriptions at multiple scales does not solve the problem; if anything, it exacerbates it by increasing the volume of data. Some means must be found to organize or simplify the description, by relating one scale to another. Some work has been done in this area aimed at obtaining "edge pyramids" (e.g. [8]), but no clear-cut criteria for con­ structing them have been put forward. Marr [4] suggested that zero-crossings that coincide over several scales are "physically significant," but this idea was neither justified nor tested.

How, then, can descriptions at different scales be related to each other in an organized, natural, and compact way? Our solution , which we call uale-&pace filtering, begins by continuously varying the scale parameter, sweeping out a surface that we call the &cale-&pace image. In this repre­ sentation , it is possible to track extrema as they move con­ tinuously with scale changes, and to identify the singular points at which new extrema appear. The scale-space image is then collapsed into a tree, providing a concise but com­ plete qualitative description of the signal over all scales of observation. 1

2. The Scale-Space Image

Descriptions that depend on scale can be computed in many ways. As a primitive scale-parameterization, the gaussian convolution is attractive for a number of its properties, amounting to "well-behavedness": the gaussian is symmetric and strictly decreasing about the mean, and therefore the weighting assigned to signal values decreases smoothly with distance. The gaussian convolution behaves well near the limits of the scale parameter, u, approach­ ing the un-smoothed signal for small u, and approaching the signal's mean for large u. The gaussian is also readily differentiated and integrated.

The gaussian is not the only convolution kernel that meets these criteria. However, a more specific motivation for our choice is a property of the gaussian convolution's zero-crossings (and those of its deriva~iv~s): as u decrease:-", additional zeroes may appear, but ex1stmg ones cannot m general disappear; moreover, of convolution kernels satisfy­ ing "well behavedness" criteria (roughly those enumerll:ted above,) the gaussian is the only one gu~ranteed to s~t1sfy this condition [12]. The usefulness of this property w1ll be explained in the following sections.

1 A complementary approach to the "natural" scale problem has been developed by Hoffman (9] .

The gaussian convolution of a signal f(x) depends both on x the signal's independent variable, and on u, the gaus­ sian''s standard deviation . The convolution is given by

where "*" denotes convolution with respect to x . This function defines a surface on the (x, u)-plane, where each profile of constant u is a gaussian-smoothed version of J(x), the amount of smoothing increasing with u. We will call the (x, u)-plane uale ~pace, and the function, F, defined in (1), the uale-~pace image of f. 2 Fig. 1 graphs a sequence of gaussian smoothings with increasing u . These are constant­ u profiles from the scale-space image.

At any value of u, the extrema in the nth derivative of the smoothed signal are given by the zero-crossings in the (n + 1)th derivative, computed using the relation

where the derivatives of the gaussian are readily obtained. Although the methods presented here apply to zeros in any derivative, we will restrict our attention to those in the second. These are extrema of slope, i.e. inflection points. In terms of the scale-space image, the inflections at all values of u are the points that satisfy

2 It is actually convenient to treat log a as the scale parameter, uniform expansion or contraction of the signal in the z­ direction will cause a translation of the scale-space image along the log a axis.

using subscript notation to indicate partial differentiation. 3

3. Coarse-to-fine Tracking

The contours of Fu = 0 mark the appearance and mo­ tion of inflection points in the smoothed signal, and provide the raw material for a qualitative description over al1 scales, in terms of inflection points. Next, we will apply two simplifying assumptions to these contours: (1) the identity assumption, that extrema observed at different scales, but lying on a common zero-contour in scale space, arise from a single underlying event, and (2) the localization assump­ tion, that the true location of an event giving rise to a zero-contour is the contour's x location as u -+ 0.

Referring to fig. 2, notice that the zero contours form arches, closed above, but open below. The restriction that zero-crossings may never disappear with with decreasing u (see section 2) means that the contours may never be closed below. Note that at the apexes of the arches, Fu:z = 0, so by eq. (2), these points do not belong to the contour. Each arch consists of a pair of contours, crossing zero with opposite sign.

The localization auumption is motivated by the obser­ vation that linear smoothing has two effects: qualitative simplification- the removal of fine-scale features--and spa­ tial distortion- dislocation , broadening and flattening of the features that survive. The latter undesirable effect may be overcome, by tracking coarse extrema to their fine-scale locations. Thus, a coarse scale may be used to identify ex­ trema, and a fine scale, to localize them. Each zero-contour therefore reduces to an (x, u) pair, specifying its fine-scale location on the x-axis, and the coarsest scale at which the contour appears.

A coarse-to-fine tracking description is compared to the corresponding linear smoothing in Fig. 3. 4

3 Note that the second condition in (2) excludes zero-crossings that are parallel to the z-axis, because these are not zero­ crossings in the convolved signal.

4. The Interval Tree

While coarse-to-fine tracking solves the problem of localizing large-scale events, it does not solve the multi-scale integration problem, because the description still depends on the choice of the continuous global scale parameter, u , just as simple linear filtering does. In this sec.tion, we reduce the scale-space image to a simple tree, concisely but completely describing the qualitative structure of the signal over all scales of observation.

This simplification rests on a basic property of the scale­ space image: as u is varied, extremal points in the smoothed signal appear and disappear at singular points (th~ tops. of the arches in fig. 2.) Passing through such a pomt with decreasing u, a pair of extrema of opposite sign appe~r in ' the smoothed signal. At these points, and only these pomts, the undistinguished interval (i.e. an interval bounded by ex­ tremal points but containing none) in which the singularity occurs splits into three subintervals. In general, each undis­ tinguished interval, observed in scale space, is bounded on each side by the zero contours that define it, bounded above by the singular point at which it merges into ~n enclos~ng interval, and bounded below by the singular pomt at which it divides into sub-intervals.

Conseque.ntly, to each interval, I, corresponds a node in a (generally ternary-branching) tree, whose parent node denotes the larger interval from which I emerged, and whose offspring represent the smaller intervals into which I subdivides. Each interval also defines a rectangle in scale­ space, denoting its location and extent on the signal (as defined by coarse-to-fine tracking) and its location and ex­ tent on the scale dimension. Collectively, these rectangles tesselate the (x, u)-plane. See fig. 4 for an illustration of the tree.

4Jn this and all illustrations , approximations were drawn by fitting parabolic arcs independently to the signal data o.n each interval marked by the description. This procedure IS crude, particularly because continuity is not enforced across inflections. Bear in mind that this procedure has been used only to display the qualitative description.

This interval tree may be viewed in two ways: as describ­ ing the signal simultaneously at all scales, or as generat­ ing a family of single-scale descriptions, each defined by a subset of nodes in the tree that cover the x-:lxis. On the second interpretation, one may move through the family of descriptions in orderly, local, discrete steps, either by choosing to subdivide an interval into its offspring, or to merge a triple of intervals into their parent. 5

We found that it is in general possible, by moving in­ teractively through the tree and observing the resulting "sketch" of the signal, to closely match observers' spon­ taneously perceived descriptions. Thus the interval tree, though tightly constrained , seems flexible enough ~ cap­ ture human perceptual intuitions. Somewhat surpnsmgly, we found that the tree, rather than being too constraining, is not constrained enough. That is, the perceptually salient descriptions can in general be duplicated within th~ t~ee's constraints but the tree also generates many descnptwns that plain); have no perceptual counterpart. This obser~a­ tion led us to develop a ~tability criterion for further prunmg or ordering the states of the tree, which is described in the next section.

5. Stability

Recall that to each interval in the tree corresponds a rectangle in scale space. The x boundaries locate the inter­ val on the signal. The u boundaries define the scale range over which the interval exists, its ~tability over scale changes. We have observed empirically a marked correspondence be­ tween the stability of an interval and its perceptual salience: those intervals that survive over a broad range of scales tend to leap out at the eye, while the most ephemeral are not perceived at all. To capture this relation, we have devised several versions of a stability criterion, one of which picks a "top-level" description by descending the tree until a local maximum in stability is found. Another iteratively removes nodes from the tree, splicing out nodes that are less stable than any of their parents and offspring. Both of these radically improve correspondence between the in­ terval tree's descriptions and perceptual features (see fig. 5.)

5For previous uses o( hierarchic signal descriptions see e.g. (10,11 ,2].

6. Summary

Scale-space filtering is a method that describes signals qualitatively, in terms of extrema in the signal or its deriva­ tives, in a manner that deals effectively with the prob­ lem of scale- precisely localizing large-scale events, and effectively managing the ambiguity of descriptions at mul­ tiple scales, without introducing arbitrary thresholds or free parameters. The one-dimensional signal is first ex­ panded into a two-dimensional uale-&pace image, by con­ volution with gaussians over a continuum of sizes. This con­ tinuous surface is then collapsed into a discrete structure, using the connectivity of extremal points tracked through scale-space, and the singular points at which new extrema appear. The resulting tree representation is a a concise but complete qualitative description of the signal over all scales of observation. The tree is further constrained using a maximum-stability criterion to favor events that persist over large changes in scale.

We are currently developing applications of scale-space filtering to several signal matching and interpretation prob­ lems, and investigating its ability to explain perceptual grouping phenomena. The method is also being extended to apply to two-dimensional images: the scale-space image of a 2-D signal occupies a volume, containing zero-crossing surfaces. 6