Parsing of Graph-Representable Pictures
Shaw, Alan C.
This paper describes a syntax-directed picture analysis system based on a formal picture description scheme. The system accepts a description of a set of pictures in terms of a grammar generating strings in a picture description language; the grammar is explicitly used to direct the analysis or parse, and to control the calls on pattern classification routines for primitive picture components. Pictures are represented by directed graphs with labelled edges, where the edges denote elementary picture components and the graph connectivity mirrors the picture component connectivity; blank and don't care "patterns" allow the description of simple relations between visible patterns. The bulk of the paper is concerned with the picture parsing algorithm which is an n-dimensional analog of a classical top-down string parser, and an application of an implemented system to the analysis of spark chamber film. The potential benefits of this approach, as demonstrated by the application, include ease of implementation and modification of picture processing systems, and simplification of the pattern recognition problem by automatically taking advantage of contextual information. Key Phrases: picture processing, picture parsing, picture description, picture analysis, pattern recognition, top-down analyzer, graph representable pictures, syntax directed analysis, picture language, picture grammar, graphics language.
computer science; technical report
Previously Published As