Linguistic Specification and Analysis of Classes of Line Patterns

摘要

Pictorial patterns can be considered as statements in a two-dimensional language. In the report, a variety of languages composed of sets of encoded geometric curves are classified in the Chomsky language hierarchy. The relationships between classes of languages and classes of automata then permit bounds on the time and memory required to recognize the patterns to be determined. The phrase-structure grammar scheme for string languages is extended by permitting symbols to have an arbitrary number of 'attaching points,' and classes of the extended languages are defined. An algorithm for parsing a 'context-free' language of this type according to a formal language description is incorporated into a table-driven pattern analyzer. This device is an extension of the idea of a table-driven compiler and is able to perform a broad range of pattern analysis tasks on widely differing classes of line patterns. The class of patterns and method for structurally breaking down the patterns can be changed simply by changing the entries in the program syntax tables. The table-driven pattern analyzer is applied to the recognition of events in bubble chamber photographs. (Author)