Elements of Computer Vision
Line Labeling
In the 1970's, David Huffman and Maxwell Clowes (among others) began to teach a computer to recognize polyhedral images as 3-d scenes. As A. Dewdney explains in his book The New Turing Omnibus, a polyhedral scene is "an assembly of solids each of which is bounded by plane faces. The faces of these solids meet along straight-line segments having a characteristic geometry and showing only a finite number of relationships where two or more of them meet." The work of Huffman and Clowes to make a computer understand such a scene and determine what individual shapes it is composed of was later expanded on by David Waltz. The following image is an example of a polyhedral scene:

There are a defined number of junctions which can occur between the lines of a polyhedral scene. Dewdney describes five such junctions:

and Lawrence Stevens, in his book Artificial Intelligence: The Search for the Perfect Machine, adds::

Each segment of those junctions can be characterized as well:

A segment marked 'concave' is an edge to a hidden face of an object in the image. A segment marked 'convex' is an edge to a visible face of an object. A segment marked 'obscuring' means that it hides an edge to a face. Finally, an edge marked 'crack' indicates an edge that is common to two objects. The segments of each junction cannot be labeled arbitrarily any one of these four ways, however, because the laws of physics only allow certain combinations. For example, an arrow can only occur when the head segments are both obscuring and the stem is convex or when the head segments are both concave and the stem is convex. Other combinations could lead to scenes like:

which is not possible in nature.

To re-cap, in an image such as:

a computer would begin by seeing something entirely 2-D. A computer can use the knowledge of which combinations of different junctions are possible to map out all the junctions of this polyhedral scene, thereby determining what objects it contains. The final image would be something like:

This process is a first step for computers toward fully understanding 3-dimensional space.

Back to the Table of Contents.