ABSTRACT

Waltz's (1975) work introduced the inherently global constraint afforded by shadows cast from a single distant source and showed that the multiple ambiguities possible without shadows were often resolved to a unique interpretation with shadows. More importantly, the process by which the unique interpretation was discovered naturally lends itself to parallel processing of a particular sort. If each vertex has an associated processor, and each processor changes its state according to the state of those directly connected to it, a stable configuration will be reached with the final states giving locally consistent labelings. Rosenfeld, Hummel and Zucker (1976) noted the connection between this scheme and relaxation processes in numerical analysis.