A line drawing is a representation of the features in an image. Humans are remarkably adept at interpreting line drawings, that is, at deducing three dimensional geometrical structure from a very sparse collection of lines. Our inferences are not always infallible, although most often when we do fail to interpret a line drawing correctly we usually arrive at an ambiguous interpretation rather than an incorrect one.
The understanding of line drawings brings together ideas from computer vision and artificial intelligence, and has become a classical field of study in both areas. The problem is usually divided into two steps, namely labeling and realization. Labeling is meant to provide a qualitative description of the scene, by classifying the segments of a line drawing as the projection of concave, convex or contour edges. Realization involves the physical legitimacy of the interpreted scene, and tries to recover the underlying 3D structure.
The features that appear in a line drawing may result from a number of different scene events (see figure 1):
In this lecture we will assume that the line drawing contains no surface reflectance discontinuities and no illumination discontinuities. Thus, we will only deal with depth and orientation, concentrating on the geometric aspects of the image.
What we would like to do is interpret the surfaces making up the objects in the scene. Clearly, we can't expect to determine functions that describe these surfaces when we only have the boundary information. The best we can hope for is line labeling followed by quantitative shape inference. Line labeling has been solved in general, whereas quantitative shape inference has only been solved for polyhedra.
Figure 2 illustrates the six possible labels we can attach to edges. A convex edge is an edge along which the visible angle between the two faces forming the edge is greater than
Line labels capture the qualitative nature of a line drawing in the
sense that bulges in the surface neither change the labeling not the
line drawing. We will describe a scheme for labeling line drawings
first described by Huffman [3], and independently by
Clowes [1], in 1971. Huffman restricted his attention to
the case where all faces are planar, that is, a ``polyhedral world'',
so now there are only four possible labels . He also assumed that all vertices are trihedral, that is, they
are formed by exactly three faces, and that there are no object
alignments, which would result in a ``crack'' edge.
Huffman first noted the need for a general viewpoint assumption, that is, he assumed that the line drawing was viewed from a general viewpoint, so that a small perturbation of the viewpoint would not affect the line drawing. Figure 4 illustrates a general and non-general viewpoint image of a cube.
We also note that not all possible line labels lead to legal labelings, that is, to representations of objects that are constructible in the real world. Figure 5 illustrates some legal and illegal labelings. Huffman began by constructing all the possible trihedral vertices that could be viewed from all possible viewpoints, thus finding all physically possible junctions. He did this by constructing a cube that was divided in each of the three orthogonal directions. Imagine that any one octant is filled with solid material, and it is then viewed from the other 7 octants. When two octants are filled, we either have a rectangular slab of material which is qualitatively like a single octant cube, or a solid made up from diagonally opposite octants, which is an illegal polyhedron under the Huffman assumptions (the vertices are not all trihedral).Similar arguments apply when either 4 or 6 octants are filled, so the only interesting cases are filling 1, 3, 5, and 7 octants with solid material, leading to four basic ways in which three planar surfaces can form a vertex of a polyhedron. These are illustrated in figure 6.
Within each unoccupied subspace, the appearance of the vertex in the line drawing remains the same with respect to the number, the labels, and the configuration of the lines forming that vertex. There are three possible line configurations forming the junction, and they are called Y, L and arrow junctions. The fourth possible junction type is called a T junction, and occurs at depth discontinuities, indicating an occluding boundary. A T junction corresponds to a global scene phenomenon, whereas all the other junction types represent local scene events. An example of the junctions that can be seen from various octants for the case where one octant is filled is given in figure 7. The complete junction catalogue for polyhedral scenes is given in figure 8. Note that simple combinatorics would suggest a much larger junction dictionary; we ought to be able to label in 43 = 64 distinct ways. But as we saw before, many of these combinations are not physically realizable. A line drawing is said to be labelable if a label can be assigned to every segment such that every junction is labeled according to the junction catalogue.For example, let us label the line drawing shown in figure 9.
Junctions A and C are arrow junctions, and thus have three possible labelings each. Junctions B and D are L junctions, and thus have six possible labelings each. However, we cannot arbitrarily assign labels within these groups because of global consistency constraints. So we begin by making an arbitrary assignment for A and see how this affects the possible assignments for B, C and D. We will see that there are only three possible interpretations of this line drawing: a tetrahedron on a table, a tetrahedron floating in space, and a tetrahedron stuck on a wall. Thus we ended up with 3 out of 45 = 1024 possibilities.
Huffman checked for labelability by adopting a linguistic approach.
Four boolean predicates are introduced for
all segments si, where
, such that
if and only if si is labeled ``+'', and likewise for
.For
and
, we suppose that
an arbitrary direction has been assigned a priori to all segments (this
is automatically true if segments are stored as pairs of vertices). Then we
pose
if and only
if si is labeled with an arrow that is concordant (discordant) to the
intrinsic direction of the segment.
The four predicates must obey the following equation, which assures that exactly one of the predicates is true for all segments:
Each legal labeling of a junction corresponds to a set of values for the predicates associated with the segments of the junction. This set of values can be described by a boolean equation. For example, the following equation must hold for the predicates of the incident segments si, sj, sk (arranged in an anti-clockwise direction) of a Y junction (it is assumed that the intrinsic direction of the segments is the outward direction):
Now we have an equation for each segment, and an equation for each
junction. Putting all these equations together we get a boolean
proposition that can easily be put in conjunctive normal form, and
is satisfiable if and only if the line drawing is labelable. The labeling
problem has therefore been reduced to a satisfiability problem for a
boolean expression. Note, thus, that labeling of trihedral scenes,
like the satisfiability problem, is -complete. This linguistic
approach to labeling is a very inefficient way of solving the problem.
In 1971 Waltz [8] exhibited a filtering algorithm
with very good average running time (roughly linear in the
number of segments). The algorithm achieves local consistency
in the following way: given a junction, rule out all legal
labelings of the junction for which there is no labeling of the
neighbour junctions which is compatible with it. Repeat this procedure
until no further progress can be made. To label a line drawing,
first achieve this local consistency and then achieve global consistency
by tree searching with backtracking. Malik [4] applied
a similar approach to the labeling of piecewise smooth curved line
objects. Parodi [6] has recently studied the complexity
of labeling origami scenes, that is scenes constructed by assembling
planar panels of negligible thickness, and has shown that this
problem is also -complete.
Using schemes such as those above, Escher type objects can be shown to be physically impossible. Hence, all physical objects (in the trihedral world) should be labelable. However, labelability is not a sufficient condition for physical realizability. We can see this with the example illustrated in figure 10. We can visualize this object as a truncated pyramid, where the edges 1, 2 and 3 do not meet at a single point. Such an object is not physically constructible with planes because if it were, then edge 1 would meet face B at some point P. Now P, being a point on edge 1, lies on A and C. Since P meets B, P therefore lies on A and B, implying that P lies on line 2. Likewise, P lies on C and B, implying that P lies on line 3. But we assumed that the edges 1, 2 and 3 did not meet at a single point, so we have a contradiction.
The realizability problem for a labeled line drawing was solved by Sugihara [7] in 1982. He reduced the problem to an instance of Linear Programming. Roughly speaking, the reduction goes as follows:
aixj + biyj + zj + ci = 0,
where the unknowns are ai, bi, ci and zj;aixj + biyj + zj + ci > 0.