Towards Diagram Processing: A Diagrammatic Information System

AAAI 1999

TL;DR

This paper proposes a novel approach to building AI agents capable of directly processing and reasoning with diagrammatic information, akin to how humans understand natural language. They introduce "Inter-Diagrammatic Reasoning" (IDR) and a query language called "Diagrammatic SQL" (DSQL) to enable systems to infer knowledge from diagrams and answer complex queries, demonstrating this with a US vegetation map example.

What Problem Does This Paper Address?

While significant research has focused on AI agents understanding natural language (text and speech), the ability to process and reason with visual information, specifically diagrams, has been comparatively neglected. This is a critical gap, as diagrams are a fundamental mode of human communication and information representation. The authors argue that for AI agents to truly function as partners in human discourse and activity, they must be fluent in processing diagrammatic information, just as they are expected to be with language. This paper aims to lay the groundwork for such agents by developing a system that can ingest, process, and extract knowledge from diagrams.

Methods

The core of the proposed system lies in two key innovations:

  • Inter-Diagrammatic Reasoning (IDR): This theory defines diagrams as tessellations (tilings) of a planar area. It leverages spatial and temporal coherence between diagrams to infer implicit information. IDR provides a set of unary and binary operators (like OR, AND, OVERLAY, PEEL) and functions to manipulate and combine diagrams. The system directly manipulates spatial representations of input bitmaps, avoiding premature translation into other formats.
  • Diagrammatic SQL (DSQL): To make querying diagrammatic information more intuitive, the authors extend SQL. DSQL allows users to query diagrams using a familiar syntax. Instead of returning relations, DSQL queries return sets of diagrams. These sets can be overlaid, counted, tested for emptiness, or used in set operations, mirroring the capabilities of IDR. The paper presents a subset of DSQL grammar and a compiler that translates DSQL queries into IDR operations.

Datasets

Not discussed in the paper. The paper uses example diagrams (US vegetation maps, state outlines) for demonstration rather than formal datasets.

Key Insights and Ideas

  • Diagrams as a First-Class Citizen: The paper strongly advocates for treating diagrammatic information with the same importance as natural language for AI agents.
  • Direct Spatial Manipulation: The approach of directly manipulating bitmap representations of diagrams, rather than immediately translating them, is presented as a flexible and efficient strategy.
  • DSQL as an Intuitive Interface: Extending SQL to query diagrams offers a powerful and familiar way for users to interact with diagrammatic information systems.
  • IDR as a Unifying Formalism: The IDR theory provides a robust framework for combining and reasoning with various diagrammatic representations, bridging the gap between visual input and inferential output.
  • Proof by Existence: The authors acknowledge that while their approach may not claim cognitive plausibility, the fact that humans naturally process diagrams serves as proof that such a system is achievable.

Key Results

The paper demonstrates a functional instantiation of a diagrammatic information system capable of answering a range of queries about US vegetation maps. The system successfully:

  • Accepts bitmap images of diagrams as input.
  • Parses diagrams based on semantic mappings (e.g., gray levels to vegetation types).
  • Uses IDR operators to perform operations like intersection and union on diagrammatic representations.
  • Answers queries such as "Which states have grassland?", "Which states do not have forest?", "How many states have desert?", and more complex relational queries.
  • The quality of responses is argued to equal or exceed human capabilities for the demonstrated range of queries.

Limitations and Future Work

The authors acknowledge several limitations and outline promising future directions:

  • Limited Query Range: Not all queries a human might expect are currently handled, specifically those involving neighborhood relations or precise area calculations.
  • Cartogram Specificity: The current system requires a priori diagrams (like state outlines) to match the size and orientation of the input diagrams.
  • Noise and Uncertainty: The system currently avoids dealing with real-world data complexities like textual annotations on diagrams.
  • Future Work:
    • Area and Neighborhood Queries: Integrating with theories like Furnas' BITPICT for area reasoning and mathematical morphology for neighborhood analysis.
  • Generalization: Extending DSQL to handle new diagram types and domains.
  • Full DSQL Grammar and Compiler: Developing a complete DSQL grammar and a robust compiler.
  • Relational Database Integration: Implementing a relational database backend for storage management and heterogeneous data querying.
  • Natural Language Interfaces: Exploring the integration of natural language interfaces for SQL with DSQL.
  • Real-world Data Handling: Addressing noise, uncertainty, and transformations for real-world diagrammatic data.

Summary updated

BibTeX
@inproceedings{1999towards,
  title = {{Towards Diagram Processing: A Diagrammatic Information System}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure