Arrangements, Homomorphisms, and Discrete Relaxation

We show how homomorphisms between arrangements, which are labeled N-ary relations, are the natural solutions to some problems requiring the integration of low-level and high-level information. Examples are given for problems in point matching, graph isomorphism, image matching, scene labeling, and spectral temporal classification of remotely sensed agricultural data. We develop characterization and representation theorems for N-ary relation homomorphisms, and we develop an algorithm consisting of a discrete relaxation method combined with a depth-first search to find such homomorphisms.