Plato's Cave: Combinatorial Explosion

Combinatorial Explosion in Computing the Gestalt Laws

Consider the Gestalt law of proximity. A conventional algorithm might compute this law with an algorithm something like...

At first sight this appears perfectly feasable. In practice however there are multiple problems. First of all, the objects must be identified and cataloged before this algorithm can work on them. But it is this similarity grouping which generates the low-level segmentation in the first place. In other words, the objects which must be grouped initially are the lowest level visual primitives, such as edges, lines, dots, etc. A natural image can contain thousands of such primitives, many of which may be illusory, such as attatched shadows, cast shadows, reflectance edges, textures, etc. so an algorithm which explicitly measures the distance between such features might have to generate a proximity table which is larger than the original image on which it is based.

Furthermore, the proximity relations are not defined by an absolute distance, but rather by relative groupings or clusterings, which may occur at a multitude of spatial scales, as shown below.

A full encoding of the rules of this algorithm would be even more complex, and would lead to yet more combinatorial problems. Furthermore, the Gestalt grouping laws do not act independently but appear to influence each other, so that the final pre-attentive percept is some analog combination of all of the Gestalt grouping laws acting in unison (note the influence of "good continuation", "symmetry (five-fold), and "closure" above). A full algorithmic coding of these rules in symbolic form would be practically impossible.

An analog Gestalt mechanism to compute the law of proximity in the above figure might be defined something like this: for every dot in the image, glue a marble at the corresponding location on a thin rubber sheet stretched over a rectangular frame. When all the marbles are glued in place, the gradient of the rubber sheet sagging under the weight of the marbles represents the strength and direction of the grouping force. While this mechanical analog has problems of its own, the principle behind this mechanism allows it to compute the grouping between any number of points with equal ease, and the analog nature of the system allows it to be coupled to other similar analog mechanisms to compute the other Gestalt grouping laws, so that the final grouping can be an analog combination of all of the analog laws acting simultaneously.

Return to argument

Return to Steve Lehar