Multiple resolution representation and probabilistic matching of 2-d gray-scale shape.

One approach to pattern classification is to match a structural description of a pattern to models which describe the structural properties of pattern classes. The central problem in structural pattern matching is to determine the correspondence between the symbols which comprise a model and symbols which describe a pattern. The difficulty of determining this correspondence depends critically on the representation that is used to describe patterns. This correspondence presents a probabilistic representation for structural models of pattern classes. Both pattern descriptions and models for pattern classes are based on symbols which represent grayscale information at multiple resolutions. A pattern description is given by a tree of symbols with attribute values. Structural models are represented by a tree of symbols with probabilistic attributes. The position and scale (resolution) of the symbols, as well as other ``features,'' are represented by these attributes. An algorithm is presented for determining the correspondence between symbols in a description of a pattern and symbols in a model of a pattern class. This algorithm uses the connectivity between symbols at different scales to constrain the search for correspondence. An interactive training program for learning models of pattern classes is described, and some conclusions from the work are presented.