Biological Knowledge Laboratory
College of Computer & Information Science WVH202
Northeastern University
360 Huntington Ave.
Boston, MA 02115
email: futrelle@ccs.neu.edu

							finite-state automaton
		x,y data graph
					gene diagram

A technical report which brings together all the pages in this demo set is available here for download as a single PDF file.

This set of web pages was prepared for the demonstration of the Diagram Understanding System (DUS) at the Fall AAAI Symposium on Formal Reasoning with Visual & Diagrammatic Representations (FRVDR98), Orlando, Florida, October 1998. This represents work done by R. P. Futrelle (http://www.ccs.neu.edu/home/futrelle/) and various graduate students over a number of years at Northeastern University, Boston. The overall goal of the Biological Knowledge Laboratory is to develop systems that can discover and exploit the content of scientific documents, e.g., using AI techniques for representing the conceptual structure of the documents. Biological research papers in particular contain numerous figures, so discovering figure content is important. The discussion here focuses on diagrams, by which we typically mean figures that are made up of vector elements: lines, polygons, text, etc., as opposed to photographs (pixmaps) -- see the three small samples above. Our major focus to date, and the content of this demo has been the parsing of diagrams. We explain how the system works by presenting a series of examples of its use to parse diagrams and to view the structure of the parses. We also discuss the nature of the grammars we use. All screen shots and example runs in this demonstration were produced on a Macintosh G3 Series PowerBook, 300MHz, using Macintosh Common Lisp, allocated 20MB of space.

February 2007: For recent work on diagrams in our lab, see the collection of downloadable papers here.

This work is relevant to formal reasoning about diagrams in at least the following ways:

• Parsing diagrams is reasoning about diagrams, in that it is a constructive proof that the parsed entity is an instance of a certain description of a class of objects.
  
  
• To do automated reasoning about a diagram, it is often useful to start with a structured description of the diagram, rather than a collection of primitive objects (lines, polygons, etc.). A parse produces such a description.
  
  
• Building a framework for writing grammars raises important issues about how to specify the geometrical relations that should hold within a diagram of a certain class.
  
  
• Designing a computational strategy for parsing a diagram forces us to think about how to discover and keep track of geometric relations within a diagram in an efficient way.
  
  
• Any approach to parsing helps to elucidate problems such as ambiguity in diagrams and their descriptions.

The proceedings of the FRVDR98 symposium are available as a technical report from AAAI. Anyone seriously interested in this area should obtain a copy of the report.

To explore my website for the demo, you may wish to start with the Introduction and proceed sequentially through the topics below, or go to one of them directly:

• Visualizing the Relations between Objects and Images
  
  
• Using the Lisp Inspector
  
  
• The Structure of Grammars for Diagram Parsing
  
  
  • Complete copy of a grammar for x,y data graphs
    
    
• How the Grammar Rules Drive the Parsing Process
  
  
• Parsing runs with timing
  
  
• Object Sharing in parsed structures
  
  
• Spatial indexing and geometrical computations
  
  
• Parsing finite-state automata diagrams and gene diagrams
  
  
  • Finite-state automata diagrams -- using sharing for context
    
    
    • Full finite-state automata grammar
      
      
  • Gene diagrams
    
    
    • Full gene diagram grammar
      
      

• Relation of this work to ideas/systems discussed in FRVDR98

		Return to R. P. Futrelle's home page

This site was developed on a Mac PowerBook using GoLive CyberStudio 3.1 for HTML and Screen Catcher 1.0 for images.