Case Study: Interpreting Visual Scenes - Thinking as Computation - page 126

Figure 6.8. The four vertex types

Arrow Fork L-vertex T-vertex

as labeled > , since in going from H to A the surface is to the right. (The + and - labels
will be the same for either direction of the edge.)

6.3.1 Constraints on vertices and edges

What kind of background knowledge is expected in order to interpret edges in an
image like this? The answer has to do with the vertices , where the edges meet. Only
four types of vertices are expected in such an image, as shown in figure 6.8. (All but
the T-vertex appear in figure 6.7: E, A, and G are L-vertices; C, K, and I are forks; the
rest are arrows.) Furthermore, in any polyhedral image, only some combinations of
edge types can meet at a vertex.
Consider, for example, the L-vertex of figure 6.8. Suppose that both edges meeting
at the vertex were labeled + . Then because of the surfaces below each edge, there
would need to be an extra edge where they meet, making the vertex into an arrow.
The conclusion: two edges labeled + cannot meet at an L-vertex.
The full range of possibilities for the edges at each type of vertex are shown in
figure 6.9. These facts can be encoded in Prolog in a straightforward way, as is done
in figure 6.10. In all cases, the edges are understood as leaving the vertex. The reverse
predicate is used to relate the label of an edge to the label of the same edge in the
reverse direction.
With this background knowledge, the visual interpretation of a polyhedral image
can proceed. Given is a list of vertices, their types, and the edges that leave each
vertex. The job is to assign labels to each edge; this is approached as a constraint
satisfaction problem:
The variables are the edges in the image.

Each variable takes a value from one of the four labels: > , < , + , and - .

The constraints are that each vertex in the image must connect edges with labels
that are in accordance with the rules shown in figure 6.9.