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):

- shadow lines correspond to an illumination discontinuity;
- an orientation discontinuity occurs when the surface normal is discontinuous;
- a depth discontinuity occurs at the edge of an object; and
- surface reflectance discontinuities can occur because of surface markings.

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. ALine 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.

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 calledFor example, let us label the line drawing shown in figure 9.

Junctions
Huffman checked for labelability by adopting a linguistic approach.
Four boolean predicates are introduced for
all segments *s*_{i}, where , such that if and only if *s*_{i} 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 *s*_{i} 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 *s*_{i}, *s*_{j}, *s*_{k} (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:

- planar faces are represented by the equation of the planes
which contain them (
*a*_{i}*x*+*b*_{i}*y*+*z*+*c*_{i}= 0), and 3D vertices are represented by a triple*v*_{j}= (*x*_{j},*y*_{j},*z*_{j}) such that (*x*_{j},*y*_{j}) are the 2D coordinates of the corresponding junction; - whenever, on account of a given labeling, a vertex
*v*_{j}can be said to lie on face*f*_{i}(this is true, for example, if the edge to which*v*_{j}belongs is labeled ``+'' or ``-'' and is on the boundary of*f*_{i}), the following equation holds true:*a*_{i}*x*_{j}+*b*_{i}*y*_{j}+*z*_{j}+*c*_{i}= 0,*a*_{i},*b*_{i},*c*_{i}and*z*_{j}; - whenever a vertex
*v*_{j}can be said to be closer to the centre of projection than the face*f*_{i}(this is true if, for example, part of face*f*_{i}is occluded by face*F*_{k}along an occluding line*l*and*v*_{j}is in the middle of*l*), the following inequality holds true:*a*_{i}*x*_{j}+*b*_{i}*y*_{j}+*z*_{j}+*c*_{i}> 0. - Now if all the equations, along with all the inequalities, above have solutions, the labeled line drawing correctly represents a polyhedral scene.