Use of Partitioning Techniques in a Syntactical Approach to the Recognition and Regeneration of Images

In this research v/e present a syntactic approach to pattern recognition. Learning is done by inference of probabilistic finite state grammars for the strings formed by scanning the images. Recognition is done through the use of a maximum likelihood acceptor. The recognition rate is found unacceptably low ( 12^). Partitioning techniques are introduced to preprocess the images before learning. The best partitioning technique is based on a generalized mutual information measurement which minimizes the inter dependence of the different blocks in the partitioned images. An algorithm for sequential partitioning of the image based on the generalized mutual information measurement is shown to be optimal and of significant practical implication. This algorithm allows sequential partitioning which is as 'good* as an exhaustive search. The average recognition results (1/3 training set and 2/3 nontraining set} is found to be 72.51^» The concept of entropy is extended to constant length languages and hence used to compare between various grammars inferred in different partitioning experiments. The grammars inferred for recognition are used to regenerate images. Two new assesment measurements for quantitatively evaluating the quality of the regenerated images are introduced. The first measurement is an information measurement, while the second uses concepts of clustering namely scatter matrices to assess the quality of the regenerated images. These quantitative measurements are shown to agree with the visual quality of the regenerated images.