all
ase
Ing
sth
ive
ire
ing
ıch
sen
ap-
to
ess
ose
act
(a) Arrow junction (b) Y junction
"V
SL?
4
*
As A ERN
(c) Multi junction (d) L junction (e) T junction
D Le
- n"
-. x
^ es
(f) Pseudo junction (g) Termination junction (h) Three-tangent junction (i) Curvature-L junction (j) Transition-S junction
Figure 2. Junction types in image structure graph based on catalogs in (Malik, 1987; Eggert, 1991). (a) Arrow junction has three arcs with
distinct tangents, one angle between a pair of arcs is greater than pi, (b) Y junction has three arcs with distinct tangents, all angles between
pairs of arcs are less than pi, (c) Multi junction has four or more arcs meeting at point, (d) L junction has two arcs with distinct tangent,
(e) T junction marks occlusion boundary, only two arcs have common tangent and curvature, (f) Pseudo junction is not a real junction, used
to include closed arc in graph, (g) Termination junction marks end of a visible contour (cusp), (h) Three-tangent junction has three arcs
with a common tangent, only two have common curvature, (i) Curvature-L junction has two arcs with a common tangent, but have distinct
curvatures, (j) Transition-S junction has continuous tangent and curvature across junction, curvature changes sign where two arcs meet.
lines of sight can be adjusted to produce the projected fea-
ture locations that best match the observed image features.
2.2 Defining a General View
The particular set of features used to describe a view has var-
ied between researchers. Early work used various 2-D feature
types such as image edges, vertices, silhouette moments, and
holes. The 3-D features taken from range imagery also in-
cluded edges and vertices, as well as face area, orientation
and location. Recently, the most common form of symbolic
representation for a 2-D view of a 3-D scene has become
the image structure graph. There is a long tradition of us-
ing the image structure graph in the analysis of polyhedral
scenes, and the concept has also been extended to handle
curved objects (Malik, 1987). The image structure graph is
a qualitative specification of the type and configuration of
the elements in the line drawing, omitting any quantitative
data such as the lengths of lines or the size of the angles
between lines.
The image structure graph is formed by abstracting the orig-
inal intensity image into an idealized line drawing, and then
labeling the lines and junctions formed by these lines. For
polyhedral objects, the line drawing is entirely determined by
the lines and the junctions formed where two or more meet.
To be clear about the terminology, a line in the line drawing
is a 2-D projection in the image plane of a 3-D edge on the
object surface. An edge is a locus of points where there is a
discontinuity in the surface normal (for example, where two
faces of a polyhedron meet).
For curved objects, the situation is more complicated. In
addition to edges that project to lines, curved objects also
have contour generators that project to occluding contours,
or simply contours, in the line drawing. A contour generator
(also called the rim or limb) is a locus of points on the object
surface where the line of sight is tangent to the surface (for
instance, the apparent side of a cylinder). For curved objects,
both lines and contours may appear in the image as either
straight or curved.
The lines/contours and junctions in a line drawing may be
assigned symbolic labels that indicate their 3-D interpreta-
tion. For example, a line in a polyhedral scene may be given
the symbolic label convez to indicate that the internal angle
between the two faces meeting at the corresponding edge on
the object is less than 180?, or concave for angles greater than
2.3 Object Domains
Over the years, the domain of objects for which an aspect
graph algorithm exists has steadily expanded. The view-
ing sphere, being simpler, has allowed more analyses to be
carried out both in theory and in practice. The more com-
plicated model of 3-D space has not limited theoretical de-
velopments as much as it has implementation. Polygons
and polyhedra are now well understood, and programs exist
which will construct their aspect graphs under either model.
Curved shapes, and more complex shapes such as those that
are articulated or deformable, require sophisticated construc-
tion techniques. Only a few such algorithms have been im-
plemented and those are restricted almost entirely to the
viewing sphere approach. These different domains will be
discussed later in the paper. An unlimited domain of objects
is available if one 1s willing to construct only an approximate
aspect graph, the topic of the next section.
180°. Similarly, junctions may be given labels to indicate the
quantity and type of contours intersecting at the point. A
fairly complete catalog of junction types, based on that of
Malik (Malik, 1987), is shown in Figure 2. For polyhedra,
only the first few junctions can exist, while all may occur
for a curved surface object. Even the labeling of the image
structure graph is not entirely consistent among researchers,
as some may choose to omit certain junction types from con-
sideration, or let such things as line labels be implicit rather
than explicit. Other possibly more robust image representa-
tions will be discussed in a later section.
Based on the image structure graph, viewpoint space can be
partitioned into regions of general viewpoints separated by
boundaries of accidental viewpoints. Under either model of
viewpoint space, a general viewpoint is one from which an
infinitesimal movement can be made in any direction and the
resulting image structure graph is isomorphic to the original.
An accidental viewpoint is one for which there is some di-
rection in which an infinitesimal movement will result in an
image structure graph that is not isomorphic to the original.
À visual event is said to occur on the passing from one re-
gion of general viewpoints through a boundary of accidental
viewpoints into another region of general viewpoints.
3. APPROXIMATE ASPECT GRAPHS
There are a variety of difficulties involved in developing an
algorithm to compute the aspect graph for a class of objects.
