PDL(ID:7300/pdl008)Picture Description LanguagePicture Description Language Likely to be different to that of Wyvill 1974 References: in Information and Control 14(1) 1969 view details Conclusions We have described a syntax-directed picture analysis system based on the use of a formal picture description scheme. The system accepts a description of a class of pictures in terms of a grammar generating sentences in the PDL picture language; the grammar is explicitly used to direct the analysis or parse, and to control the calls on pattern classification routines for the primitive picture components. In addition to providing a general framework in which a large class of pictures may be described and hopefully analyzed, our approach automatically incorporates a form of contextual pattern recognition that, in many instances, should assist and simplify the classification of primitive patterns. The potential benefits of our methods were demonstrated by the application of an implemented system to the analysis of a small sample of spark chamber film; these benefits include ease of implementation and modification, with little sacrifice in machine efficiency. This research points to a number of interesting problems and extensions for future work. PDL has some obvious limitations; prominent among these is the inability to conveniently express more complex relations such as "inside of" or "overlapping," and the restriction to only two points of concatenation for a primitive. Can the language be generalized to handle the above without destroying its essential simplicity? PDL is a description language; it would also be useful to have a language in which picture processing systems may be implemented. As a first step, it would appear useful to embed PDL in a conventional algorithmic language. We have not carefully investigated the means or the advantages of adding an imposed semantics to each syntax rule; the idea is to allow arbitrary computations to be made over the picture structure as the parse proceeds. This paper has dealt primarily with the analysis problem. However, in many applications, there is a need for both analysis and generation, for example, in computer-aided design; what is analyzed must be generated and vice versa. It would be desirable if the same description formalism could be used for both problems. A start has been made in using PDL for generation purposes in George and Miller [8] and Shaw [21]. In problems of the type we are considering, most of the analysis time is devoted to accessing data for primitive recognition. The data structures used at the primitive level are therefore critical and worthy of deeper study. Graphics data structures employing list processing techniques are widely used [9] but are too inefficient for the large quantities of data in many practical picture processing applications. When dealing with digitized pictures, only the most obvious structures have been used. Some investigation of more efficient parsing methods would be beneficial. For example, one could use some form of look-ahead in our top-down analyzer to eliminate false goals; Anderson [2] has used the model of simple precedence grammars to obtain a more efficient analyzer for two-dimensional mathematical expressions. Finally, experiments with implemented systems in other application areas are warranted, including flowchart generation and analysis, analysis of text and mathematics, and analysis and generation of line drawings such as electric circuits; as well as looking at high energy particle physics photographs in more detail. Extract: Introduction Introduction Much research and development effort has been devoted to the design and construction of hardware and computer programs for automatic picture processing. In addition to the interesting theoretical problems generated by this activity, there is a practical demand for these systems in such diverse areas as biomedicine, high energy particle physics, library automation, military reconnaissance, robot development, space exploration, computer-aided design, and commercial data proeessing. Several working systems exist, notably in high energy particle physics [1]; however, these are usually one-of-a-kind, represent tremendous investments, especially in programming; and, in terms of their recognition capability and efficiency, often do not perform as well as originally anticipated or desired. What is needed are some general methods that simplify the construction of automatic picture processing systems and, at the same time, improve their accuracy and efficiency. A particularly promising approach is the linguistic one, originally advocated by Eden [4, 5], Narasimhan [17, 18], and Kirsch [11]. (See Miller and Shaw [14] for a survey of the use of linguistic methods in picture processing. ) The method is basec on the use of picture description schemes that include a mechanism for grouping components into higher level structures; a multidimensional extension of th( techniques of language syntax analysis is then employed to analyze the pictures Experimental systems of this type have been implemented by Narasimhan [18]. Anderson [2], and Evans [6], as well as by this author. This paper discusses the methods employed to analyze or parse pictures which may be described in our particular picture language. The applicable class of pictures is first defined; we call these graph-representable since they may be conveniently represented as a directed graph. The picture description scheme and its formal properties are described elsewhere [19, 20]. Here, it is presented in sufficient detail for an understanding of the remainder of the material. The bulk of the paper is concerned with our picture parsing algorithm--a top-down goal-directed syntax analyzer that has a direct analogy to a corresponding string syntax analyzer; we discuss the rationale behind our choice of analyzer, its advantages and limitations, the interesting differences between string and picture parsing, and the role of pattern recognition routines. Some experiences with an implemented system are then related. The concluding section summarizes the main features of our approach and suggests some problems for future research. The work can be distinguished from that of other researchers in the following ways: 1. It is based on a formal picture description scheme which allows the manipulation of descriptions. 2. The same description language can be used for both analysis and generation purposes. 3. It is beneficial to do the primitive pattern classification within our system rather than external to it as is done in [2] and [6]; the syntax-directed nature of the method results in a form of contextual pattern recognition that simplifies the classification task in many instances. 4. While we feel that our methods can be applied to a wide variety of pictures, and, in principle, are universally applicable, there are nevertheless many types of pictures for which our approach does not seem practical. Systems that allow the description of a picture as a set of subpictures and an arbitrary set of relations satisfied by them [6, 16] are more general but, in our estimation, are not likely to be practical. Extract: ACKNOWLEDGMENTS ACKNOWLEDGMENTS. The author is deeply indebted to his thesis advisor, Professor William F. Miller, for many valuable discussions on this work, for his constant enthusiasm and encouragement, and for providing a stimulating atmosphere that made it not only possible, but a pleasure to do research. The critical reading of this paper by D. Gries and C. Zahn is gratefully acknowledged. in [ACM] JACM 17(3) July 1970 view details An implementation of the model is used as an example of its applicability and is implemented by defining its components utilizing a simple precedence translator writing system. The languages defined using this implementation can function interactively or as a slave system and are device independent. A two-dimensional mathematical expression display system is used to illustrate this implementation. Extract: GEM langauges GEMS is an implementation of the model presented in Section 2; it was implemented in PL/I on an IBM 360/91. GEMS is implemented as three language preprocessors which translate the descriptions into PL/I programs which can then be compiled. The three language pre-processors are the control language (Lc), the definition language (Ld) and the graphical language (Lg); these pre-processors are implemented using SIMPLE (George 1971a) I and a procedure library for accessing the data structure. in Nake, F. and Rosenfeld, A. "Graphic Languages" Amsterdam: North-Holland Publishing Company 1972. view details in Watanabe, S. (ed.) "Frontiers of Pattern Recognition" Academic Press 1972 view details Research into the interpretation of graphics has been motivated primarily from two sources. The first is simply the desire to realise in man-machine communication the kind of descriptive power supported by the use of graphics in man-man communication. The second springs from working with a data base of information which is most conveniently recorded in graphical form (e.g. maps, engineering drawings, etc.). The quality associated with this kind of interpretation is captured by the idea of the 'machine perception of graphics'. The acceptance of this idea places computer graphics and with it, graphic languages, in a cognate position with respect to picture interpretation and scene analysis, although there are, of course, important differences. The body of the paper is concerned with reviewing the status of graphical languages given that the task for which they have to be suited is one of interpretation. Extract: PDL grammar and operations Shaw (196S) presents his PDL (Picture Description Language), which is a language designed for expressing structural descriptions of PLctures. Using it, one can describe a class of pictures in terms of a set of primitives and a restricted set of relationships. The acceptor for PDL analyses a picture by a parsing process which uses a set of PDL statements to assign a 'parse tree'. This work is motivated almost entirely by the' linguistic approach', the author placing PDL within the formal framework of 'The Linguistio Model' as discussed above. A primitive in PDL is any curve (or picture part) having two distinguished points, a 'head' and a 'tail'. A description of a picture is built up by concatenating these directed primitives in any of the four possible ways which can be specified by given binry operators. When two parts are concatenated a new be specified by given binry operators. mlen two parts are concatenated a new part is formed having its own head and tail which are located in accordance with the heads and tails of the components and the particular concatenation operator. Thus the new part can enter into further concatenation relationships. in Nake, F. and Rosenfeld, A. "Graphic Languages" Amsterdam: North-Holland Publishing Company 1972. view details Extract: Shaw and PDL Shaw [13], [14] discussed a particular realization of this formalism. To allow descriptions of classes of pictures, he provided a picture description language (PDL). Each picture describable in PDL has two designated connection points -- the head and the tail. A sentence in PDL gives a structural description of a picture by naming all of its primitives and their tail/head connectivity. in IEEE Transactions on Software Engineering (TSE) 3(2) 1977 view details |