Diagrams are a critical part of virtually all scientific and technical documents. Analyzing diagrams will be important for building comprehensive document retrieval systems. This paper focuses on the extraction and classification of diagrams from PDF documents. We study diagrams available in vector (not raster) format in online research papers. PDF files are parsed and their vector graphics components installed in a spatial index. Subdiagrams are found by analyzing white space gaps. A set of statistics is generated for each diagram, e.g., the number of horizontal lines and vertical lines. The statistics form a feature vector description of the diagram. The vectors are used in a kernel-based machine learning system (Support Vector Machine). Separating a set of bar graphs from non-bar-graphs gathered from 20,000 biology research papers gave a classification accuracy of 91.7%. The approach is directly applicable to diagrams vectorized from images.

This paper describes substantial advances in the analysis (parsing) of diagrams using constraint grammars. The addition of set types to the grammar and spatial indexing of the data make it possible to efficiently parse real diagrams of substantial complexity. The system is probably the first to demonstrate efficient diagram parsing using grammars that easily be retargeted to other domains. The work assumes that the diagrams are available as a flat collection of graphics primitives: lines, polygons, circles, Bezier curves and text. This is appropriate for future electronic documents or for vectorized diagrams converted from scanned images. The classes of diagrams that we have analyzed include x,y data graphs and genetic diagrams drawn from the biological literature, as well as finite state automata diagrams (states and arcs). As an example, parsing a four-part data graph composed of 133 primitives required 35 sec using Macintosh Common Lisp on a Macintosh Quadra 700.

A semantic analysis approach is described in which diagrams are represented as collections of geometric objects. The fundamental organizing principle for these objects is the generalized equivalence relation. Examples include near, parallel, and aligned. These relations can be computed efficiently using GOSSAMER, a pyramidal data structure that allows spatially associative access to objects. Animate vision, in which the image is scanned either continuously or discontinuously, is used to mimic the efficient strategy used by humans to view diagrams. The system is implemented in Common Lisp and is being applied to data graphs and gene diagrams in the biological literature.>

Coding a large and diversified graphics application system is a difficult task. We suggest an approach to this problem in which programs are built up using Objects (e.g., Classes, Modules) newly generated or drawn from a library. Each Object has an Aid which supports an interactive dialogue with the programmer resulting in the insertion of the appropriate references to the Object into the developing code. An Aid can display graphical Objects and accept sketching and picture editing. An Association capability allows the programmer to generate code corresponding to the displayed graphical material. The Association can be literal, with numerical values being inserted, or symbolic, with variable arguments inserted. A Programming System that is so structured implements an Intrinsically Graphical Language because the code can be “written” using both textual and graphical dialogues.

The extraction of information from movie film and videotape has always been a very tedious process. Yet the usefulness of these media in biomedical research, behavioral science, industrial testing, etc., is apparent. We are developing a system, GALATEA, for the rapid extraction of data from film or video using interactive graphics. The key aspects of GALATEA are: The user indicates what features are of interest using an x, y digitizing pen. These pen positions are the only data the system sees, so that full digital image encoding is avoided. The user can trace the features while the fim runs (frame-by-frame analysis is not necessary). The user has constant feedback in the form of an animated, computer-generatedmovie (Kinegram), overlaid on the original film image and running synchronously with it. It is this kinetic feedback of the data entered that makes the system efficient. Structured programming, real-time programming techniques, data structures for time-dependent pictures and dynamical graphics tools are covered. A detailed discussion is given of Slippage or soft degradation in real-time systems under fluctuating load conditions.