Compositional pattern recognition
Daniel F. Potter · 1999
This thesis introduces a syntactic and probabilistic approach to pattern recognition based on the use Compositional Grammars and Compositional Distributions. Such grammars are related in spirit to the constraint-based grammar formalisms now popular in linguistics. Analytic definitions and some basic properties of several classes of compositional grammars and distributions are established. These grammars and distributions are used to describe (that is, define a prior on) the objects to be recognized. A bayesian MAP or equivalently MDL formulation for scene recognition/interpretation is defined. A chapter on recognition algorithms discusses some simple brute-force techniques for approximating solutions of this MAP/MDL problem. Another chapter presents an algorithm amenable to sampling certain compositional distributions. Experiments with recognition and synthesis of online handprint characters and words provide an example of the approach. A compositional grammar and distribution is first used to define a prior on objects up to scale, position, and orientation; thus, a compositional grammar and distribution is used to define a measure on object orbits under the action of the semidirect product group SE2∝R+ . Use of an application-specific conditional distribution on the remaining position, scale and orientation parameters extends the distribution to the actual objects to be recognized and sampled.