Parsing of Graph-Representable Pictures

TLDR

Pictures are represented as directed graphs whose labeled edges encode elementary components and connectivity, with blank and don't‑care patterns describing simple relations between visible patterns. The paper presents a syntax‑directed picture analysis system built on a formal picture description scheme, focusing on an n‑dimensional top‑down parsing algorithm and its application to spark chamber film analysis. The system employs a grammar that generates picture description language strings to direct parsing and control calls to pattern‑classification routines for primitive picture components. The approach simplifies pattern recognition by leveraging contextual information and facilitates easy implementation and modification of picture processing systems, as shown in the spark chamber film application.

Abstract

A syntax-directed picture analysis system based on a formal picture description scheme is described. 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 labeled 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.