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.
So with n curves we have 6n possibilities for assigning labels to the curves. A labeling of a line drawing is a function from L into the set of possibilities. However, it is clear that humans don't consider all possibilities when assigning an interpretation to a line drawing.
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 , and independently by Clowes , 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.
For example, let us label the line drawing shown in figure 9.
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  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  applied a similar approach to the labeling of piecewise smooth curved line objects. Parodi  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  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.