   Next: References Up: Computer Vision IT412 Previous: Lecture 8

# Interpreting line drawings

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. Discontinuities in surface normal, illumination, and surface reflectance all lead to viewpoint-independent edges, that is to edges whose three-dimensional spatial locations are independent of the viewpoint. By contrast, continuous surface-normal discontinuities, such as those that occur at the edge of a sphere, correspond to edges whose three-dimensional spatial location depends upon the viewpoint. Such edges are known as limbs or apparent contours.

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 . A concave edge is an edge along which the visible angle between the two faces forming the edge is less than . An occluding edge is a convex edge along which only one of the two faces adjoining the edge in space is visible in the line drawing. The label along an occluding edge is so directed that upon looking along the edge in that direction, the body of the object is on your right. Limbs are labeled with . Clearly, labeling is not unique, as is evidenced by optical illusions such as the Necker cube. Where labels change we have junctions, determined by discontinuous tangents or curvatures. There are six possible labels, giving the label set 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. 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  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:

• planar faces are represented by the equation of the planes which contain them (aix + biy + z + ci = 0), and 3D vertices are represented by a triple vj = (xj, yj, zj) such that (xj, yj) are the 2D coordinates of the corresponding junction;
• whenever, on account of a given labeling, a vertex vj can be said to lie on face fi (this is true, for example, if the edge to which vj belongs is labeled +'' or -'' and is on the boundary of fi), the following equation holds true:

aixj + biyj + zj + ci = 0,

where the unknowns are ai, bi, ci and zj;
• whenever a vertex vj can be said to be closer to the centre of projection than the face fi (this is true if, for example, part of face fi is occluded by face Fk along an occluding line l and vj is in the middle of l), the following inequality holds true:

aixj + biyj + zj + ci > 0.

• Now if all the equations, along with all the inequalities, above have solutions, the labeled line drawing correctly represents a polyhedral scene.
Since Linear Programming can be solved in polynomial time, the realizability question can be answered and a possible realization for a labeled line drawing can be exhibited in polynomial time. Thus, realizability can be efficiently checked only when a legal labeling is already available.   Next: References Up: Computer Vision IT412 Previous: Lecture 8
Robyn Owens
10/29/1997