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

- 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

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.