Constraint Propagation

The assignment of meaning to one part of the scene limits the possible interpretations of other parts of the scene. This is called constraint satisfaction or constraint propagation It sounds complicated, but the basic idea is simple: the scene is interpreted by ruling out every interpretation except one. It is like a crime investigator eliminating every suspect except one, to find the guilty party.

Constraints "propagate" or spread because, once you have limited the possible interpretation of one part of the scene, that limits or constrains the possible interpretation of other parts of the scene. Eventually the process converges on a single set of interpretations of all the lines and vertexes in the scene. At that point, the scene is understood.


Upward and downward arrow vertices

What is "constraint propagation" and how is it illustrated in these examples?

For example, if an arrow vertex is interpreted as an upward pointing inner corner (like the first example in the figure) that means the two line segments forming the point of the arrow must both be edges of an object, and the point where they come together must be farther away from the viewer than the edges leading to it. Once the program "knows" those things, it can make other assumptions, and it goes on like that until the entire scene is interpreted.

Again: the goal is to interpret the entire scene by assigning a specific meaning to each line segment (this is the upper edge of a block, that's the edge of a shadow, etc.) as well as every corner and surface. To rule out all interpretations of a scene except one is to "satisfy all the constraints" and "understand" the scene. Like a detective working on a murder case, the computer looks for the one interpretation that makes sense out of all the evidence.

The MIT visual scene analysis program was one of the most successful examples of artificial intelligence research in the 20th Century. The project was largely successful by the mid-1980s. Starting with just a few basic assumptions, computers could accept the input from a video camera and locate the boundaries of objects in any scene. The fundamental problem of gestalt formation or object segregation was solved for visual perception.

Constraint satisfaction is a basic process found in all sorts of cognitive processes, but it can be an elusive idea to students encountering it for the first time. For this reason, we will take a look at two examples that show how the brain "assigns meaning" to line segments and vertexes in order to understand simple diagrams.

Example: The Necker Cube

Our first example involves a famous visual illusion, an ambiguous figure called the Necker Cube. It is one of the oldest visual illusions studied by psychologists, dating from the 1820s. The line drawing of a cube can be interpreted more than one way. Psychologists call this an ambiguous or bi-stable figure.


The Necker Cube

The Necker Cube appears to change its orientation in space as you stare at it. This happens because the stimulus can be interpreted in two ways that are equally good or "legal." Cognitive scientists interpret this as "competing high-level perceptual representations being activated in response to a given visual stimulus" (Suzuki and Peterson, 2000).

To use the language of constraint satisfaction, there are two interpretations of the cube that satisfy all the constraints of the sensory input, so the brain alternates between two equally acceptable interpretations.

What sort of "competition" takes place?

If you don't see the two different configurations, just stare at the cube for a while. It will change. If you do see the two different interpretations, experiment with holding the cube in one configuration, resisting the competition from the other interpretation. Suzuki and Peterson (2000) found substantial effects on this task from intention, which is what most people call willpower. However, eventually the neurons representing one option will fatigue, and the other option takes over (the cube flips).


Either A or B appears closer.

The Necker Cube has eight vertices. Of these eight, six are arrows around the edges, two are forks in the middle. The forks, A and B, determine the viewer's interpretation of the Necker Cube. If you interpret A as closer to you than B, then A is a "downward pointing outer corner." A marble placed on top of the cube (if the cube was solid) would roll toward you, hence it is a downward corner. If you interpret point A this way, then point B must be an upward pointing inner corner.

This is what is meant by constraint propagation. The interpretation of one element "spreads its influence" or propagates to adjacent elements. Now, when your neurons get tired of one interpretation, so (for example) they start interpreting point B as an upward-pointing outer corner, that forces your brain to re-interpret point A at the same moment. So the cube flips as a whole. The cube is treated as a gestalt, a whole thing, and the interpretation of each line and vertex must be consistent with the interpretation of the whole.

Example: Two T-vertexes aligned


Two T-vertices (circled) with stems (A and B) lined up. A and B are interpreted as the "same line."

What is a computer version of the gestalt "law of continuity"?

Here is another example of constraint propagation. This time it is based on a simple rule: when the stems of two T-vertexes are lined up, they represent a single edge passing behind an object. This is a computer version of the gestalt law of continuity (see Chapter 4), which says segments that line up on both sides of an object are interpreted as the same line.

In the illustration, two "T" vertexes are circled and the line segments next to them (the "stems" of the T) are labeled A and B. The computer is taught to assume, like a human, that if two T-stems line up, they are parts of the same edge. Therefore any identification of segment A will "propagate" to segment B. If A is identified as an upper, outer edge, B is, too. (They are identified as the same edge.)

How does the brain do visual scene analysis so quickly?

In discussing these examples we have adopted a step-by-step or serial processing approach, directing attention first to one segment, then another. By contrast, the visual system analyzes many different parts of the scene at once. Such parallel processing is much faster and more efficient than serial processing. The brain is massively parallel, which helps to explain its quickness in doing things like interpreting scenes. If you tilt your head back with your eyes closed, then open your eyes, your brain receives a new visual pattern, and it interprets all the lines, areas, and vertexes in about a quarter second. That is quite a feat!


Write to Dr. Dewey at psywww@gmail.com.

Don't see what you need? Psych Web has over 1,000 pages, so it may be elsewhere on the site. Do a site-specific Google search using the box below.

Custom Search

Copyright © 2007 Russ Dewey