Languages, Automata and Classes of Chain-Encoded Patterns
Abstract
By treating patterns as statements in a two-dimensional language, it is possible to apply linguistic theory to pattern analysis and recognition. This report presents an approach to a classification scheme for pattern languages that could provide information about types of programs and computation facilities capable of meeting particular pattern analysis and recognition requirements. Consideration is restricted to line patterns encoded in the chain code developed by Freeman. This encoding method represents a line pattern by a sequence of octal digits called a chain. Results can be extended to other forms of encoding when translators between codes can be built. The report compares languages formed by Boolean functions of languages and by the concatenation of strings of a number of languages with pattern languages. Pattern languages based on families of equations in two variables and formed from chains of straight lines, circles, and circular arcs are related to string language classes. Pattern properties, including closure, self-intersection, convexity, and periodicity, are examined. Pattern languages are also considered that are similar in various ways to an arbitrary given chain. Although the patterns considered in this report are relatively simple ones, it appears possible by means of language rules of a table-driven pattern analyzer to extend the approach to pattern classes containing more complex patterns.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1967
- Accession Number
- AD0668081
Entities
People
- Jerome Feder
Organizations
- New York University