On Computing Structural Changes in Evolving Surfaces and their Appearance.
As a surface undergoes a one-parameter family of deformations, its shape and its appearance change smoothly except at certain critical parameter values where abrupt structural changes occur. This paper considers the case of surfaces defined as the zero set of smooth density functions undergoing a Gaussian diffusion process and addresses the problem of computing the critical parameter values corresponding to structural changes in the parabolic curves of a surface and in its aspect graph. An algorithm based on homotopy continuation and curve tracing is proposed in the case of polynomial density functions, whose zero set is an algebraic surface. It has been implemented and examples are presented.
Introduction
This article is concerned with the interplay of scale and shape in computer vision. Con-
cretely, imagine a smooth density function defined over some volume. The points where
the density exceeds a given threshold form a solid whose boundary is a level set of this
function. Smoothing the density changes its level sets and the solid shapes they bound.
What are the "important" changes that may occur? For example, can a solid break
into two pieces? Or for that matter, can two pieces merge into a single one? When?
Answering this question is relevant in medical imaging for example, where anatomical
surfaces are routinely identified in volumetric CT, MR, or ultrasound images as level
sets of smoothed density functions (Lorensen and Cline, 1987). Consider now a moving
object, say a train, and a static camera, say the old-fashioned large-format kind. As
the train speeds by, its silhouette on the ground glass of the camera will change, mostly
smoothly, but at times abruptly as well. For perfectly focussed cameras, a complete
catalogue of the corresponding discontinuities has been established by mathematicians
(Arnol'd, 1969; Platonova, 1981; Kergosien, 1981), leading to the introduction of aspect
graphs in computer vision by Koenderink and Van Doorn (1976, 1979). When the
camera is not perfectly focussed, the appearance of our (now blurry) train will still go
through occasional discontinuities, but these will be of a slightly different nature, and
they will depend on the amount of smoothing introduced by the camera optics. The
situation becomes even more complicated for digital cameras since the image plane in
this case is split into pixels that can only resolve points whose angular separation is
large enough. Characterizing and computing the scale, i.e., the amount of blur and/or
image resolution at which the discontinuities in appearance are themselves suddenly
changing is of course pertinent in line-drawing interpretation and more generally in
object recognition (Eggert et al., 1993; Shimshoni and Ponce, 1997).
As already hinted at, classifying the abrupt changes -called critical events or singularities
from now on- of the shape and/or appearance of a surface as it evolves
under certain types of deformations is the business of mathematicians, and it involves
2tools from differential geometry and singularity theory (Whitney, 1955; Thom,
1972; Arnol'd, 1984). This article is aimed at the simpler problem of actually computing
the singularities for a particular class of surfaces, namely the zero sets of polynomial
densities, or algebraic surfaces, evolving under one-parameter families of deformations,
mostly those associated with Gaussian smoothing of the polynomial density function.
For the sake of simplicity, we will further restrict our study of appearance changes to
surfaces of revolution defined by rotationally-symmetric density functions, and model
the dependency of appearance on scale using perfectly focussed pictures of blurred
objects (blurry images of perfectly sharp objects would of course provide a more
realistic model). In particular, the evolution process will not only depend on the shape
of the object, but on the actual density function used to define its surface, which
is only justified when this density function is physically significant, e.g., the X-ray
attenuation stored at each voxel of a CT image (Kergosien, 1991; Noble et al., 1997).
Despite these obvious limitations, we believe that the study undertaken in this paper
can bring some insight into the more general role of scale in vision, for example, give
an idea of the complexity of scale-dependent representations of shape and appearance,
and of their adequacy to the organization of objects into classes. We also believe that
some of the proposed techniques can be generalized without too much difficulty to more
general settings, for example the detection of singularities in medical images, or the
construction of scale-space aspect graphs for algebraic surfaces that are not rotationally
symmetric. Our presentation can be thought of as a preliminary experimental foray
into the role of scale in computational differential geometry (Koenderink, 1990). Specif-
ically, we address the problem of computing the critical values of a Gaussian diffusion
process corresponding to structural changes in (1) the parabolic curves of an algebraic
surface and (2) the aspect graph of algebraic surfaces of revolution. Section 2 gives a
brief survey of related work and presents an overview of our approach. We derive the
equations characterizing the singularities of evolving surfaces and their aspect graph
in Sections 3 and 4. These equations are solved using homotopy continuation (Morgan,
1987) and curve tracing (see Appendix A and (Kriegman and Ponce, 1991)), and a
number of experiments are presented in Sections 3.3 and 4.3. We conclude in Section 5
with a brief discussion of our results and perspectives on future research. Preliminary
versions of this work have appeared in (Pae and Ponce, 1999; Pae, 2000).
2. Background and Approach
2.1. Background
The idea of capturing the significant changes in the structure of a geometric pattern as
this pattern evolves under some family of deformations has a long history in computer
vision. For example, Marr (1982) advocated constructing the primal sketch representation
of an image by keeping track of the patterns that do not change as the image is
blurred at a variety of scales. The idea of recording the image changes under blurring
lead to the scale-space approach to image analysis, which was first proposed by Witkin
(1983) in the case of inflections of a one-dimensional signal, and has since been applied
to many domains, including the evolution of curvature patterns on curves (Asada and
Brady, 1986; Leyton, 1988; Mackworth and Mokhtarian, 1988) and surfaces (Ponce
and Brady, 1987; Monga et al., 1994), and more recently, the evolution of curves and
level sets under non-linear diffusion processes (Kimia et al., 1995; Sethian, 1996).
The aspect graph of Koenderink and Van Doorn (1976, 1979) provides another
example of an evolving geometric pattern characterized by its singularities. This time,
the objective is to enumerate the possible appearances of an object. The range of
viewpoints is partitioned into maximal regions where the (qualitative) appearance of
an object remains the same, separated by critical boundaries where the topology of
the silhouette changes according to some visual event. The maximal regions (labelled
by the object appearance at some sample point) are the nodes of the aspect graph,
and the visual events separating them are its arcs. Approaches to the construction of
the orthographic or perspective aspect graph of a polyhedral object include (Castore,
1984; Stewman and Bowyer, 1988; Plantinga and Dyer, 1990; Wang and Freeman,
1990; Gigus et al., 1991) and initial attempts at constructing scale-space aspect graphs
(Eggert et al., 1993; Shimshoni and Ponce, 1997) for this class of surfaces. Approximate
aspect graphs of polyhedral objects have also been successfully used in recognition
tasks (Chakravarty, 1982; Hebert and Kanade, 1985; Ikeuchi and Kanade, 1988).
For smooth surfaces, a complete catalogue of visual events is available from singularity
theory (Arnol'd, 1969; Platonova, 1981; Kergosien, 1981; Rieger, 1987), and it has
been used to compute the aspect graphs of surfaces of revolution (Eggert and Bowyer,
1989; Kriegman and Ponce, 1990), algebraic surfaces (Petitjean et al., 1992; Rieger,
1992), and empirical surfaces defined as level sets of volumetric density functions (Ker-
gosien, 1991; Noble et al., 1997) (see (Thirion and Gourdon, 1993) for related work).
In his book Solid Shape (1990), Koenderink addressed the problem of understanding
the structural changes of the latter type of surfaces as the density function undergoes a
diffusion process. He focussed on the evolution of certain surface attributes, namely, the
parabolic curves and their images via the Gauss map, which are significant for vision
applications: for example, the intersection of a parabolic curve with the occluding
contour of an object yields an inflection of the silhouette (Koenderink, 1984), and
the asymptotic directions along the parabolic curves give birth to the lip and beak-
to-beak events of the aspect graph (Kergosien, 1981). Koenderink proposed to define
morphological scripts that record the possible transformations of a surface and use
these as a language for describing dynamic shape. Bruce, Giblin and Tari (1996a)
have used singularity theory to expand Koenderink's work and establish a complete
catalogue of the singularities of the parabolic curves under one-parameter families of
deformations, and their work is the theoretical foundation for the approach presented
in Section 3. The same authors have also identified additional events involving the
ridges of a surface as well as multilocal singularities where a plane is bi- or tritangent
to the surface (Bruce et al., 1996b), but these will not be investigated in this paper.
2.2. Approach
The classical characterization of critical events in singularity theory is in terms of local
surface models defined by a height function is the parameter
controlling the surface evolution. In this article we are interested instead in global
surface models defined by some implicit equation F (x; Our approach to
the problem of computing the singularities of the evolution process relies on deriving
the equations that govern it and solving these equations for the corresponding critical
parameter values. Concretely, we will show in Sections 3 and 4 that the parabolic
curves of the surface formed by the zero set of a scale-dependent volumetric density
and its visual events can always be defined by a system of equations of the form
(1)
where P 1 to P n are non-linear combinations of F and its partial derivatives. For a
given value of t, these equations define a curve in IR n+1 . As will be shown in Sections
3 and 4, when t changes and the surface evolves, critical events can be characterized
by two additional equations, adding to a total of n equations in n unknowns
that admit, in general, a finite number of solutions.
To find these solutions, it is necessary to restrict our attention to classes of density
functions F for which (numerical or symbolic) algorithms guaranteed to find all zeros
of (1) exist. Specifically, we focus in this presentation on algebraic surfaces, defined as
the zero set of a volumetric polynomial density:
i+j+kd
a
Examples of algebraic surfaces include planes and quadric surfaces (i.e., ellipsoids,
hyperboloids and paraboloids) as well as the zero set of higher-degree polynomial
densities. Most importantly, as will be shown in the following sections, the equations
defining the singularities of evolving algebraic surfaces are polynomials in the unknowns
of interest. This is the key to computing the critical events associated with
surface evolution: as noted earlier, these events are characterized by systems of n
equations in n and they can be found using homotopy continuation
(Morgan, 1987), a global root finder that finds all the (real and complex) solutions of
square systems of polynomial equations. Between singularities, the structure of interest
(parabolic curves or aspect graph) does not change. An explicit representation for this
structure can be constructed using the curve tracing algorithm presented in (Kriegman
and Ponce, 1991). This algorithm is outlined in Appendix A for completeness.
3. Parabolic Curve Evolution
3.1. Problem Geometry
This section gives a brief overview of the differential geometry concepts needed to
understand the surface evolution process. The presentation is deliberately informal
and written with the hope that the reader's geometric intuition will compensate for
the lack of mathematical details. These can be found in classical texts (Hilbert and
Cohn-Vossen, 1952; Arnol'd, 1969; Platonova, 1981; Koenderink, 1990) and in the
paper by Bruce et al. (1996a) that has inspired the work presented here.
Consider a solid with a smooth boundary. Its surface can take three different forms
in the neighborhood of one of its points, depending on how it intersects its tangent
plane there (Figure 1): in the vicinity of an elliptic point, the surface is cup-shaped

Figure

it does not cross its tangent plane and looks like the surface of an egg or
the inside surface of its broken shell. We say that the point is convex in the former case
and concave in the latter one. At a hyperbolic point, the surface is saddle-shaped and
its tangent plane along two curves (Figure 1(b)). The tangents to these curves
are the asymptotic directions of the surface at the point. The elliptic and hyperbolic
points form patches on a surface, and they are separated by curves formed by parabolic
points where the intersection of the surface and its tangent plane has a cusp (there
are actually two types of parabolic points; we will come back to those in a minute).
The cusp direction is also an asymptotic direction in that case.
(a) (b) (c)

Figure

1. Local shape of a surface: (a) an elliptic point, (b) a hyperbolic point, and (c) a parabolic
point.
We define the Gaussian (or spherical) image of a smooth surface by mapping each
one of its points onto the place where the associated unit normal pierces the unit
sphere. It can be shown that the Gauss map is one-to-one in the neighborhood of
elliptic or hyperbolic points. The orientation of a small closed curve centered at an
elliptic point is preserved by the Gauss map, but the orientation of a curve centered
at a hyperbolic point is reversed (Figure 2).
Map
Gauss

Figure

2. Left: a surface in the shape of a kidney bean. It is formed of a convex area, a hyperbolic
region, and the parabolic curve separating them. Right: the corresponding Gaussian image. Darkly
shaded areas indicate hyperbolic areas, lightly shaded ones indicate elliptic ones.
The situation is a bit more complicated at a parabolic point: in this case, any small
neighborhood will contain points with parallel normals, indicating a double covering of
the sphere there (Figure 2): we say that the Gaussian image folds along the parabolic
curve.

Figure

3 shows an example, with a single covering of the sphere on one side of
the parabolic curve's image and a triple covering on the other side. The easiest way of
thinking about the creation of such a fold is to grab (in your mind) a bit of the rubber
skin of a deflated balloon, pinch it, and fold it over. As illustrated by the figure, this
process will in general introduce not only a fold of the spherical image, but two cusps
as well, whose preimages are aptly named cusps of Gauss. Cusps and inflections of the
spherical image of the parabolic curve always come in pairs. The inflections split the
fold of the Gauss map into convex and concave parts, and their preimages are called
gutterpoints (Figure 3).
Fold
Concave
Cusp of
Gauss
Gutterpoint Image
Fold
Image
Fold
Convex

Figure

3. Folds and cusps of the Gauss map. To clarify the structure of the fold, it is drawn in the left
and right sides of the figure as a surface folding in space. The changes in topology of the intersection
between a great circle and the Gaussian image of the surface as the circle crosses the fold are illustrated
in the far right of the figure.
As shown in (Bruce et al., 1996a), there are a few more possibilities in the case
of one-parameter families of deforming surfaces: indeed, three types of higher-order
contact may occur at isolated values of the parameter controlling the deformation.
The corresponding singularities are called A3, A4 and D4 transitions following Arnold's
conventions (Arnol'd, 1969), and they affect the structure of the parabolic curve as well
as its image under the Gauss map (Figure 4). There are four types of A3 transitions:
in the first case, a parabolic loop disappears from the surface, and an associated
loop with two cusps disappears on the Gauss sphere (this corresponds to a lip event
in catastrophe theory jargon (Thom, 1972; Arnol'd, 1984), see Figure 4(a)). In the
second case, two smooth parabolic branches join, then split again into two branches
with a different connectivity, while two cusping branches on the Gauss sphere merge
then split again into two smooth branches (this is a beak-to-beak event, see Figure
4(b)). Two additional singularities are obtained by reversing these transitions. At an
event, the parabolic curve remains smooth but its Gaussian image undergoes a
swallowtail transition, i.e., it acquires a higher-order singularity that breaks off into
two cusps and a crossing (Figure 4(c)). Again, the transition may be reversed. Finally,
there are four D4 transitions. In the first one (Figure 4(d)), two branches of a parabolic
curve meet then split again immediately; a similar phenomenon occurs on the Gauss
sphere, with a cusp of Gauss "jumping" from one branch to the other. In the second
transition (Figure 4(e)), a parabolic loop shrinks to a point then expands again into a
loop; on the Gauss sphere, a loop with three cusps shrinks to a point then reappears.
The transitions can as usual be reversed.
Gaussian Image
Parabolic Set
(a)
(b)
(c)
(d)

Figure

4. The singularities of evolving surfaces. The events are shown on both the surface (left) and
the Gauss sphere (right). The actual events are shown as black disks, and the (generic) cusps of Gauss
are shown as white disks. See text for more details.
3.2. Computational Approach
Bruce, Giblin and Tari (1996a) give explicit equations for all the singularities in the
case of a surface defined by a height function is the parameter
controlling the surface evolution. Here we are interested in surfaces defined by
the implicit equation F (x; can be thought of as a volumetric
density depending on t. Although it is possible to use the chain rule to rederive the
corresponding equations in this case, this is a complex process (Thirion and Gourdon,
1993) and we have chosen instead to first construct the equations characterizing the
parabolic curves and the cusps of Gauss, which turn out to have a very simple form,
then exploit the fact that the parabolic curve or its image under the Gauss map are
singular at critical events to characterize these events.
Let us start by considering a static surface defined by F (x; Using subscripts
to denote partial derivatives, the normal to this surface is given by the gradient
As shown in (Weatherburn, 1927), the parabolic curves are
defined by
ae F (x;
denotes the symmetric matrix@ F yy F zz \Gamma F 2
Note that denotes the Hessian matrix associated to F .
The cusps of Gauss are points where the asymptotic direction along the parabolic
curve is tangent to this curve (Koenderink, 1990). Let us show that the asymptotic
direction at a parabolic point is a = ArF . Asymptotic tangents can be defined as
vectors that (1) lie in the tangent plane and (2) are self-conjugated. The first condition
is obviously satisfied at a parabolic point since a \Delta
second condition is also obviously satisfied since a T Ha
the tangent to the parabolic curve is given by rP \Theta rF , it follows that the cusps of
Gauss are given by the equations 8 !
Note that rP has a simple form:
@
@x
since (@rF T In particular, this simplifies the expression
of C since the second term in (2) cancels in the dot product. Similar simplifications
occur during the computation of the non-generic singularities below.
We are now ready to characterize these singularities. Note that in the case of a
surface undergoing a family of deformations parameterized by some variable t, the
functions F , P and C also depend on t. Let us first consider A3 and D4 transitions.
Since they yield singular parabolic curves, they must satisfy
where rx denotes the gradient operator with respect to x, and the third equation simply
states that the normals to the original surface and the "parabolic surface" defined
by are parallel. This is a vector equation with three scalar components, but only
two of these components are linearly independent. It follows that the singularities of
the parabolic curves are characterized by four equations in four unknowns. The case of
singularities is a little more complicated since the parabolic curve is smooth there.
On the other hand, the curve defined in IR 4 by the cusps of Gauss is singular, and the
singularities can thus also be found by solving a system of four equations in four
unknowns, namely 8
3.3. Implementation and Results
We have constructed a MATHEMATICA implementation of the curve tracing algorithm
described in Appendix A and used the parallel implementation of homotopy
continuation described in (Stam, 1992) to solve all relevant polynomial equations.
This section demonstrates the computation of the singularities of two quartic surfaces
evolving under a Gaussian diffusion process. As shown in Appendix B, convolving a
polynomial density with a Gaussian kernel yields a new polynomial surface with the
same degree and coefficients that are polynomials in the scale oe of this kernel. The
calculation of these coefficients has been implemented in MATHEMATICA as well.

Figure

5 illustrates the effect of the diffusion process on the "squash" surface defined
in (Petitjean et al., 1992) by
The figure shows, from left to right, the original surface and its Gaussian image, the
first critical event (an A3 singularity where two components of the parabolic curve
merge into a single one), a snapshot of the surface after this event, and finally a
second A3 singularity where the parabolic curve vanishes. After that, the surface is
convex and no further singularity occurs except for the disappearance of the surface
itself.
Singularities
Type A3 A3 Vanish
oe 0.2487 0.3325 0.5498

Figure

5. Diffusion of the squash. Top: the evolving surface and its parabolic curves (as before, generic
cusps of Gauss are shown as white discs and singularities are shown as black discs). Middle: the
corresponding Gaussian image. Bottom: type and scale of the singularities. Here, as in the following
figure, the event corresponding to the disappearance of the surface is not shown.
Figure

6 shows the "dimple" surface defined in (Petitjean et al., 1992) by
as it evolves under a similar Gaussian diffusion process. There are four singularities in
this case, including the disappearance of the surface.
Dimple Singularities
Type D4 A3 A3 Vanish
oe 0.1486 0.1826 0.2532 0.3590

Figure

6. Evolution of the dimple surface (rows 1 and 2) and its Gaussian image (rows 3 and 4).
Our approach also handles other one-parameter families of deformations whose
dependence on the evolution parameter is polynomial: for example, Figure 7 shows the
singularities found when the dimple is linearly morphed into the squash as follows: if
respectively denote the squash and dimple equations,
the morphed surface is defined by (1 \Gamma t)S(x; There are five
critical events in this case, but, as in our other examples, no A4 singularity.
Singularities
Type D4 D4 A3 A3 A3

Figure

7. Morphing a dimple into a squash. The evolving surface is shown in columns 1 and 2, and
its Gaussian image is shown in columns 3 and 4.
4. Aspect Graph Evolution
4.1. Problem Geometry
We consider once again in this section a solid bounded by a smooth surface undergoing
some deformation process, but this time we study the evolution of its appearance as
both the deformation parameter and the viewpoint change. We assume orthographic
projection and model the range of viewpoints by a unit viewing sphere. As mentioned
in Section 2, the aspect graph of our object partitions this sphere into maximal regions
where the topological structure of its silhouette remains the same. This section
presents (informally once again) the geometric principles that determine the visual
events separating these regions and govern their evolution under the diffusion process.
Let us first consider the case of a static solid object. For a given camera position, the
contour of this object is defined by the set of curves where the image plane intersects
a viewing cylinder that grazes the object along a second set of curves, forming the
occluding contour. The occluding contour is in general smooth and it consists of fold
points, where the viewing ray is tangent to the surface, and a discrete set of cusp
points where the ray is tangent to the occluding contour as well. The image contour is
piecewise smooth, and its only singularities are a discrete set of cusps, formed by the
projection of cusp points, and T-junctions, formed by the transversal superposition
of pairs of fold points (Figure 8(b)). This is for transparent solids: for opaque ones,
contours terminate at cusps, and one of the two contour branches forming a T-junction
ends there.

Figure

8. The elements forming the contours of solids bounded by smooth surfaces. From left to right:
a smooth piece of image contour, a cusp, and a T-junction. Reprinted from (Petitjean et al., 1992,

Figure

3).
Critical changes in object appearance as a function of viewpoint are called visual
events. They bear the same colorful names, inherited from catastrophe theory (Thom,
1972; Arnol'd, 1984), as the singularities of evolving surfaces introduced in the previous
section, but have of course a different geometric meaning. Their occurence can be
understood in terms of the Gauss map. Let us first consider what happens to the
occluding contour as the great circle formed by its Gaussian image becomes tangent
to, then crosses the spherical image of the parabolic curve. As can be seen by examining
again

Figure

3, there are two cases: when the tangency occurs along a convex fold of
the Gauss map, we have a lip event: an isolated point appears on the spherical image
of the occluding contour before exploding into a small closed loop on the unit sphere

Figure

3, bottom right). In the image, there is no contour before the event, and an
isolated point appears out of nowhere at the singularity before exploding into a closed
loop consisting of a pair of contour branches meeting at two cusps (Figure 9). One of
the branches has two inflections and it is formed by the projection of both elliptic and
hyperbolic points, while the other one is formed by the projection of hyperbolic points
only. For opaque objects, one of the branches is always occluded by the object.

Figure

9. The lip event.
When the great circle associated with the occluding contour crosses the spherical
image of the parabolic curve along a concave part of the fold, a beak-to-beak event
occurs. Two separate loops merge then separate with a different connectivity (Figure
3, top right). In the picture, two distinct portions of the contour, each having a cusp
and an inflection, meet at a singularity (Figure 10). Before the event, each of the
branches is divided by the associated cusp into a purely hyperbolic portion and a
mixed elliptic-hyperbolic arc, one of which is always occluded. After the event, two
cusps and two inflections disappear as the contour splits into two smooth branches
with a different connectivity. One of these arcs is purely elliptic and the other one is
purely hyperbolic, one of the two always being occluded in the case of opaque objects.
The reverse transition is of course also possible, as for all other visual events.

Figure

10. The beak-to-beak event.
The lip and beak-to-beak events occur when the Gaussian image of the occluding
contour becomes tangent to the spherical image of a parabolic curve. It is easily shown
that this happens when the viewpoint is along the asymptotic tangent at a parabolic
point. A swallowtail event occurs when the viewing direction is along an asymptotic
tangent at a flecnodal point. As shown in Figure 11(a)-(b), the intersection of the
surface and its tangent plane at a flecnodal point consists of two curves, one of which
has an inflection at the point. Unlike ordinary asymptotic rays (Figure 11(c)), that are
blocked by the observed solid (this is what gives rise to contour terminations at cusps),
this one intersects the surface at a single point: it "sees through it" (Koenderink, 1990),
producing a sharp V on the image contour at the singularity. The contour is smooth
before the transition but it acquires two cusps and a T-junction after it (Figure 11,
bottom). All surface points involved in the event are hyperbolic. For opaque objects,
one branch of the contour ends at the T-junction and the other one ends at a cusp.
(a)
(b)
(c)

Figure

11. A swallowtail event. Top: (a) surface shape in the neighborhood of a flecnodal point, and
comparison of the intersection of the associated solid and its tangent plane (b) near such a point and
(c) an ordinary hyperbolic point. Bottom: the event itself.
Flecnodal points form curves on generic smooth surfaces. The visual events described
so far occur when the viewpoint crosses the surface ruled by asymptotic
tangents along these curves and their parabolic cousins. These events are said to
be local because each ruling grazes the surface at a single point. Multilocal events
occur when the viewpoint crosses the surface ruled by certain families of bitangent
and tritangent rays that graze the surface along multiple curves. Let us first discuss
tangent crossings. A limiting bitangent occurs when the tangent plane itself becomes
bitangent to the surface. The limiting bitangents sweep a ruled surface, called the
limiting bitangent developable. A tangent crossing occurs when the line of sight crosses
this surface (Figure 12, top), with two separate pieces of contour becoming tangent
to each other at the event before crossing transversally at two T-junctions (Figure 12,
bottom). For opaque objects, either a previously hidden part of the contour becomes
visible after the transition, or (as in the figure) another branch disappears due to
occlusion.
There are two more types of singular bitangents: the asymptotic bitangents, that
intersect the surface along an asymptotic direction at one of their endpoints, and the
A
A

Figure

12. A tangent crossing. The ordering of spatially distinct parts of the occluding contour changes
when the viewpoint crosses the limiting bitangent developable surface in B.
tritangents, that graze the surface in three distinct points. The corresponding visual
events occur when the line of sight crosses one of the associated developable surfaces,
and they also involve the appearance or disappearance of a pair of T-junctions: a cusp
crossing occurs when a smooth piece of the image contour crosses another part of the
contour at a cusp (or endpoint for an opaque object) of the latter (Figure 13(a)). Two
T-junctions are created (or destroyed) in the process, only one of which is visible for
opaque objects. A triple point is formed when three separate pieces of the contour
momentarily join at non-zero angles (Figure 13(b)). For transparent objects, three
T-junctions merge at the singularity before separating again. For opaque objects, a
portion of the contour disappears (or appears) after the transition, along with two
T-junctions, while a third T-junction appears (or disappears).
We have enumerated the visual events associated with static objects. When a surface
is allowed to deform, higher-order singularities will also occur. A catalogue of these
critical events can (in principle) be constructed using the tools of singularity theory.
As far as we know, however, this has not been done yet, and the associated image
singularities have not been analyzed either. Thus, we have not relied on an explicit
catalogue of scale-space critical events in the approach described in the next section:
instead, we have characterized numerically the singularities of the surfaces swept by
the parabolic and flecnodal curves and the bitangent and tritangent developables as
the parameter controlling surface evolution changes.
4.2. Computational Approach
In our implementation, we have decided for simplicity to focus on compact solids of
revolution bounded by algebraic surfaces with an equation of the form x
0, where R(z) is a polynomial of degree d. These surfaces are smooth by construction,
(a)
(b)

Figure

13. More multilocal events: (a) a cusp crossing; (b) a triple point. After (Petitjean et al., 1992)

Figure

6).
with a radius function
R(z) in the range of z values where R(z)  0. 1 As
shown earlier, convolving an algebraic surface with a Gaussian kernel yields another
algebraic surface. Furthermore, if the original surface is rotationally symmetric, so is
the smoothed surface. This simplifies the aspect graph construction since, for a fixed
scale, visual events occur along parallels (in the usual sense of constant-latitude circles)
of the viewing sphere in this case, and they can be characterized by a single number:
the tangent of the angle fi between the axis of symmetry of the solid of revolution
and the corresponding viewing direction. In the rest of this section, we will generalize
the visual event equations derived in (Kriegman and Ponce, 1990) for static solids of
revolution to the case where
R, and use polynomial curve tracing techniques
to trace these events in the oe; fi plane when the surface is allowed to evolve under a
Gaussian diffusion process governed by the scale parameter oe.
4.2.1. Local Events
As suggested by Section 4.1 and demonstrated by (Kriegman and Ponce, 1990; Petit-
jean et al., 1992), the computation of the local visual events of a (static) smooth
surface can be decomposed into two steps: (1) the identification of the parabolic
and flecnodal curves on the surface, and (2) the construction of the curves traced by
the corresponding asymptotic directions on the viewing sphere. The case of algebraic
surfaces of revolution is particularly simple, since the parabolic and flecnodal curves
are parallels (circular cross-sections perpendicular to the axis in this context), the
corresponding z values being the roots of univariate equations in z, and, as already
noted, the corresponding viewing directions (i.e., the asymptotic tangents along these
1 Using instead an arbitrary polynomial radius function r, as was done in (Kriegman and Ponce,
1990), would have forced us to either tackle the more complicated case of piecewise-smooth surfaces
when the range of z values is restricted to a compact interval where r(z) 6= 0, or to handle the
singularities occurring at points where but the tangent of the profile defining the solid of
revolution is not parallel to the cross-sections.
curves) also trace parallels on the viewing sphere. The equations for the parabolic
and flecnodal curves and the corresponding asymptotic directions were derived in
(Kriegman and Ponce, 1990). They can be expressed in terms of the radius function
r and its derivatives, and are also easily rewritten in terms of the function R used in
this presentation (Table I).

Table

I. Equations defining the local events for surfaces of revolution.
Both the original equations derived in (Kriegman and Ponce, 1990) and
the corresponding equations when
R(z) are given in the table.
(Kriegman and Ponce, 1990) New equation
Parabolic points r
Flecnodal points 3r 0 r 00
Viewing direction tan 2
The same equations hold for algebraic surfaces of revolution undergoing a Gaussian
diffusion process, but this time R also depends on the scale oe of the Gaussian kernel.
The curves formed in the oe; z plane by the pairs (oe; z) satisfying these equations can be
traced using the algorithm given in Appendix A, and the corresponding visual event
curves are then easily constructed in the oe; fi plane by substituting the corresponding
oe and z values in the viewing direction equation.
4.2.2. Multilocal Events
The construction of multilocal events is similar to the characterization of their local
counterparts, but it involves more unknowns. Indeed, the ruled surfaces associated with
multilocal events for solids of revolution touch their surfaces along a discrete set of
parallels determined by square systems of polynomial equations, and the directions of
the corresponding bitangents and tritangents trace parallels on the viewing sphere and
determine the structure of the aspect graph. The equations determining the limiting
bitangents, asymptotic bitangents and tritangents were derived in (Kriegman and
Ponce, 1990), and they are given in Table II, where they are also rewritten in terms
of the function R and its derivatives evaluated at the points z i where a bitangent
grazes the surface.
Note that the ruled surface defined by the limiting bitangents (resp. the asymptotic
bitangents) is defined by two equations in the z 1 and z 2 unknowns, i.e., the bitangency
condition given in the first row of Table II and the equation given in the second (resp.
third) row of this table. Likewise, the surface swept by the tritangents is defined by
three equations in the z 1 , z 2 and z 3 unknowns, namely the bitangency equation and the
two constraints given in the fourth row of the table. These equations can be simplified
by rewriting them in terms of the derivatives of R in z 1 . More precisely, any analytic
function F can be written as a convergent Taylor series
Table

II. Equations defining the multilocal events for surfaces of revolution. Both the original equations
derived in (Kriegman and Ponce, 1990) and the corresponding equations when
are given in the table. The bitangency condition is verified by all multilocal events. Note that the
used in Table II and the rest of this section to denote the value of a function
evaluated in z i , e.g., R 00= R 00 (z1 ).
(Kriegman and Ponce, 1990) New equation
Bitangents r 2
(R 0+R
Limiting
bitangents
Asymptotic
bitangents
R
Tritangents
(R 0+R
R
Viewing
direction tan 2
tan
In the case of a polynomial R of degree d, the series can be truncated since all the
derivatives of order greater than the degree of the polynomial are zero, and we have
d
Using these remarks it is a simple matter to simplify the equations defining the
multilocal visual events. The new equations are given in Table III, where A d\Gamma4 , B 2d\Gamma3 ,
C d\Gamma4 and D d\Gamma3 are respectively polynomials of degree
two variables. The coefficients are easily computed from Eq. (3) and Table II. Similar
calculations can also be done in the case where r is an arbitrary polynomial, see (Pae,
2000) for details.

Table

III. Simplified equations defining the multilocal events for surfaces of
revolution.
Simplified equation
Bitangents R 000+
Limiting
bitangents 2R1R
Asymptotic
bitangents R 000+
Tritangents
Viewing
direction tan 2 fi =2 R 00+
It should be noted that the new equations have a lower degree than the old ones. At
least as importantly, their form clarifies the geometric relationship between the surface
curves associated with local and multilocal events. By comparing Tables I and III we
see for example that the equation giving the viewing direction in the multilocal case
encompasses the corresponding equation for local events when z . Likewise, the
equations characterizing the limiting bitangents reduce to the equations characterizing
the parabolic and flecnodal points when z This occurs when a ruling of the
limiting bitangent developable reduces to a single point (a cusp of Gauss) where the
parabolic and flecnodal curves intersect tangentially (Koenderink, 1990).
Along the same lines, the equations defining the asymptotic bitangents both reduce,
in the limit z , to the equation of a flecnodal curve (this corresponds to the
intersection of the asymptotic bitangent developable and the flecnodal curve at a
biflecnode (Koenderink, 1990)). In this case the two equations given in Table III are
actually redundant and contain the flecnodal curve as an extraneous component. It
is easy to eliminate this redundancy (and lower the overall degree of the equations
determining cusp crossings) by replacing the second equation by
Finally, note that the equations defining the tritangents reduce to the equations
defining the asymptotic bitangents when z and to the equation defining the
flecnodal curve when z To remove these limit cases, we introduce
It is clear that both E d\Gamma4 (z are polynomials of degree d \Gamma 4,
and that
is a polynomial of degree
Thus tritangents can be characterized by the conditions
and the last equation determining the tritangents in Table III.
4.3. Implementation and Results
Armed with the equations derived in the previous section, we can now use the algorithm
described in Appendix A to trace the curves defined by these equations in IR k ,
with for the (oe; z) pairs associated with parabolic and flecnodal curves,
for the (oe; z associated with limiting and asymptotic bitangent rays, and
for the (oe; z associated with tritangents. We then construct
the corresponding scale-space visual event curves in the oe; fi plane by substituting
the corresponding values in the equations defining the singular viewing directions.
The regions delimited by these curves form a scale-space aspect graph, and sample
aspects for each one of them can also be constructed via curve tracing, as described in
(Kriegman and Ponce, 1990). The proposed approach has once again been implemented
using MATHEMATICA and homotopy continuation. We have conducted experiments
using two solids of revolution S 1 and S 2 . The first one is defined by
and the corresponding profile curve is shown in Figure 14.

Figure

14. The profile curve
R(z) associated with S1 .
The second solid of revolution, S 2 , is defined by
and the corresponding profile is shown in Figure 15.
Figure

15. The profile curve associated with S2 .

Figure

shows the scale-space aspect graph of S 1 plotted in the (oe; fi) plane, along
with a close-ups of a key area, and the corresponding aspects. The vertical lines drawn
in

Figure

are scale-space critical events, where the number of aspects changes.

Figure

17 shows the same plots for S 2 . These figures demonstrate that the number of
aspects generally decreases as the polynomial density is smoothed: indeed, although
the aspect graph of S 2 is initially quite complex with several almost indistinguishable
aspects near a triple point and the butterfly event associated with a biflecnode on the
surface (see (Koenderink, 1990) and Figure 17), it simplifies a great deal after this
event. It should be noted however that the number of aspects may locally increase for
a while as oe increases (e.g., after crossing the first vertical line in the close-up shown
in

Figure

16(top right)).
Swallowtail
Beak-to-Beak
Beak-to-Beak
Tangentcrossing
Separation
of
the
surface
Disappearance
of
parabolic
lines
Dissapearance
of
the
smaller
part
of
the
surface
A
F
G
Swallowtail
Beak-to-Beak Lip
Tangentcrossing

Figure

16. Top: the scale-space aspect graph of S1 and a close-up of the region marked by a rectangle;
Bottom: the aspects of S1 . The "aspect" (I) is a drawing of S1 in the area of the close-up shown in
the top-right part of the figure; close-ups of the actual aspects in this region are labeled (j) to (p).
A
Disappearance
of
parabolic
lines
Merging
of
a
of
swalltails
butterfly B
F
G
I
O
G
J3
O
(M) (N) (O) (P) (b)
(b') (b'') (O) (P) (Q) (R)

Figure

17. Top: the aspect graph of S2 , together with close-ups of the four regions marked by rectan-
gles. The visual events are indicated by numbers: 1=beak-to-beak, 2=lip, 3=swallowtail, 4=tangent
crossing, 5=cusp crossing and 6=triple point. Bottom: the aspects of S. The aspect (b) is at the
butterfly singularity shown above in the bottom-right rectangular region. The bottom two rows show
close-ups of the aspects near a triple point (GH) as well as two close-ups (b') and (b'') of the butterfly
and close-ups of the aspects near it.
5. Discussion
We have presented the first (to the best of our knowledge) implemented algorithm for
computing the critical events of evolving smooth surfaces and of their aspect graph.
Along the way, we have derived simple equations for the cusps of Gauss of implicit
surfaces (although those were without doubt known previously, it is difficult to find
such equations in the literature), and simpler, lower-degree equations for the multilocal
events of (static) solids of revolution than those given in (Kriegman and Ponce, 1990).
At this point, it is worth thinking about what the experiments conducted in this
paper have taught us: first, they suggest that algebraic surfaces evolve under parameterized
one-parameter families of deformations in a relatively simple and intuitive
manner. Thus there may be hope for using the sequence of critical events associated
with an evolving surface as a guide to constructing object taxonomies, individual
instances with similar sequences being grouped in the same class, 2 even if this involves
surface models and computational approaches completely different from those
presented in this article. Our (limited) experiments have shown, on the other hand,
that the scale-space aspect graph has a very complex structure at fine scales, with new
events sometimes occurring as scale increases, even though a great deal of simplification
appears to take place at coarse scales. In this context, the causality of the diffusion
process with respect to the various singularities should also be investigated (e.g., can
new parabolic curves appear as scale increases?), as has been done for zero-crossings
of the Laplacian of Gaussian-smoothed two-dimensional images (Yuille and Poggio,
1986).
It would be very interesting to generalize the results obtained in this paper to more
general settings and surface models, for example to surfaces defined as the zero sets of
empirical density functions (Kergosien, 1991; Noble et al., 1997), or, in the case of scale-space
aspect graphs, to algebraic surfaces that are not of revolution. This would require
efficient methods for monitoring the sign of the equations defining critical events at
each voxel of the empirical data in the first case, and, in the second case, trying to
simplify the multilocal visual event equations derived in (Petitjean et al., 1992), as
was done here for solids of revolution, to keep their degree and the computational
complexity of the corresponding scale-dependent algebraic calculations under control.
Along the same lines, it would be very interesting to assess the size of the various
scale-dependent structures discussed in this paper as a function of the degree of the
corresponding algebraic surfaces, using for example tools from enumerative geometry
and intersection theory (Petitjean, 1995). Surface evolution and aspect graph evolution
are obviously related, and their exact relationship should also be spelled out. Finally,
non-linear evolution processes independent of the underlying density (Kimia et al.,
1995; Sethian, 1996) are of course also of interest, as are better models of the imaging
process (i.e., blurring the image instead of the object), and they should be investigated.

Acknowledgments

. This work was partially supported by the National Science Foundation
under grant IRI-9634312 and by the Beckman Institute at the University of
Illinois at Urbana-Champaign.
These evolutionary sequences are clearly related to the idea of morphological scripts in
(Koenderink, 1990).

Appendix


A. Curve Tracing Algorithm
We recall in this section the curve tracing algorithm of (Kriegman and Ponce, 1991;
Petitjean et al., 1992). We consider an algebraic curve \Gamma, defined as in Eq. (1) by n
polynomial equations in n+1 unknowns (we assume that t is fixed here). The algorithm
traces \Gamma in four stages (Figure
1. Compute all extremal points (including singular points) of \Gamma in some direction,
say x . (These are marked E 1 and E 2 in the Figure 18.)
2. Compute all intersections of \Gamma with the hyperplanes orthogonal to the x 0 axis at
the extremal points. (In the figure, the hyperplanes are simply vertical lines, and the
only intersections in this case are E 1 and E 2 .)
3. For each interval of the x 0 axis delimited by these hyperplanes, intersect \Gamma and
the hyperplane passing through the mid-point of the interval to obtain one sample for
each real branch. (The samples are denoted S 1 to S 4 in the figure.)
4. March numerically from the sample points found in step 3 to the intersection
points found in step 2 by predicting new points through Taylor expansion and
correcting them through Newton iterations.

Figure

18. An example of curve tracing in IR 2 . This curve has two extremal points E1 ; E2 , and four
regular branches with sample points S1 to S4 . E2 is singular. (Reprinted from (Petitjean et al., 1992).)
requires the computation of the extrema of \Gamma in the x 0 direction. These
points are characterized by a system of n+1 polynomial equations in n+1 unknowns,
obtained by adding the equation jJ to (1), where J denotes the Jacobian matrix
n. They are found using the homotopy continuation method
(Morgan, 1987). Steps 2 and 3 require computing the intersections of a curve with a
hyperplane. Again, these points are the solutions of polynomial equations, and they
are found using homotopy continuation. The curve is actually traced (in the classical
sense of the term) in step 4, using a classical prediction/correction approach based on a
Taylor expansion of the P i 's. This involves inverting the matrix J which is guaranteed
to be non-singular on extrema-free intervals.
B. Gaussian Diffusion of Polynomial Densities
We give in this section explicit formulas for convolving a polynomial density with a
Gaussian kernel. We start with the univariate case, where G oe
oe
is
the Gaussian kernel with standard deviation oe, and P
i=0 a i x i is a polynomial
of degree d. The convolution is given by
G
oe\Omega
d
a i
where M j is the moment of order j of the Gaussian kernel, defined by
This moment is zero for odd values of j. For even values, it is easily shown that
proceeding by induction we finally obtain
Y
Now let us switch to the trivariate case of interest with
G oe (x;
The moments of this kernel are now given by
If one of the indices i, j or k is odd, M ijk is equal to zero. When all indices are even,
we use the separability of the Gaussian distribution to write
Y
r
Y
s
Y
This gives the following procedure for computing P oe
1. Expand P into an expression of the form
where C ijk (x; y; z) is polynomial in x, y, and z.
2. Calculate M ijk using the formula given above and let the result be d ijk oe i+j+k .
3. The desired convolution is
ijk
Obviously, In addition, it is easy to show that P oe is a polynomial in x,
y, z, and oe with the same degree as P . As an example, the polynomial P oe associated
with the density function (4x 2 that defines the surface
of the dimple in Section 3 is



--R


Catastrophe Theory.



of Comp.




IEEE Trans.


Geometry and the Imagination.

'La famille des projections orthogonales d'une surface et ses singularit'es'.



Solid Shape.




Curves and Surfaces.





Solving Polynomial Systems using Continuation for Engineering and Scientific Problems.



IEEE Conf.
'G'eom'etrie 'enum'erative et contacts de vari'et'es lin'eaires: application aux graphes d'aspects d'objets courbes'.






of Comp.
Level set methods: evolving interfaces in geometry


Master's thesis


Structural Stability and Morphogenesis.

Differential geometry.



--TR
The curvature primal sketch
Scaling theorems for zero crossings
On the classification of views of piecewise smooth objects
Marching cubes: A high resolution 3D surface construction algorithm
A process-grammar for shape
Solid shape
Computing exact aspect graphs of curved objects
Visibility, occlusion, and the aspect graph
A new curve tracing algorithm and some applications
Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects
Global bifurcation sets and stable projections of nonsingular algebraic surfaces
Computing exact aspect graphs of curved objects
Shapes, shocks, and deformations I
Parabolic curves of evolving surfaces
Ridges, crests and sub-parabolic lines of evolving surfaces
Finite-Resolution Aspect Graphs of Polyhedral Objects
On computing aspect graphs of smooth shapes from volumetric data
Generic Sign Systems in Medical Imaging
The Scale Space Aspect Graph
algebraic surfaces;differential geometry;aspect graphs;shape representation;scale space