Automatically Transforming Symbolic Shape Descriptions for Use in Sketch Recognition

Tracy Hammond, Randall DavisAAAI 2004

Introduction

Building sketch recognition systems from scratch for every new domain—such as UML diagrams, mechanical engineering schematics, or flowcharts—represents a significant engineering bottleneck. Sketch recognition is inherently difficult due to the "messiness" of human drawing, characterized by varying stroke orders, speeds, and styles. Traditionally, developers had to manually code the logic for every specific shape in a new domain. This paper introduces LADDER, a symbolic language designed to overcome this by allowing developers to describe shapes once, while a translator automatically generates the necessary recognizers, editors, and display modules for a domain-independent sketch system.

The LADDER Framework

The authors propose a framework that functions much like a "compiler-compiler" for sketches. Just as tools like Yacc or Lex allow developers to define a grammar for a programming language and automatically generate a parser, LADDER allows for the definition of a geometric "grammar" for hand-drawn symbols.

Figure 1: The LADDER framework architecture, showing the translation from domain descriptions to functional recognition and display modules.

The framework consists of three primary components:

  1. LADDER Language: A high-level symbolic language where users describe shapes based on their geometry and relationships (e.g., defining an arrow as a shaft and two head lines meeting at an acute angle).
  2. The Translator: This component parses LADDER descriptions and transforms them into three functional pieces: Shape Recognizers (converted into rules for the Jess forward-chaining logic engine), Editing Recognizers (logic for detecting gestures like "hold and drag"), and Shape Exhibitors (Java classes that define how recognized shapes are "cleaned up" for display).
  3. Domain-Independent System: A core engine that handles low-level primitive recognition (lines, arcs, ellipses) and provides the infrastructure for the generated components to execute.

Methodology and Key Insights

Unlike earlier systems that relied on statistical features like drawing speed or bounding box dimensions, LADDER focuses on how shapes look (geometry). This ensures a symbol is recognized regardless of the number of strokes or the speed at which it was drawn. The system employs a bottom-up recognition strategy: it first identifies simple primitives and then uses the Jess rule engine to "build up" to complex shapes. If a collection of primitives satisfies the geometric constraints defined in LADDER, the rule engine identifies the complex shape.

Evaluation Across Diverse Domains

To evaluate the system, the authors wrote LADDER descriptions for several distinct domains. Because this is a symbolic AI approach rather than a deep learning one, evaluation focused on the system's ability to successfully generate working recognizers for a wide variety of symbols without manual coding.

Figure 3: Examples of shapes from five different domains for which the system successfully generated recognition logic.

The system successfully generated recognizers for over 50 different shapes across five domains, including:

  • UML Class Diagrams
  • Flowcharts
  • Finite State Machines
  • Mechanical Engineering Diagrams
  • Course of Action Diagrams (complex military symbols)

Results and Future Work

The research demonstrated that a single, domain-independent engine can be customized for wildly different tasks simply by swapping a text-based description file. Beyond recognition, the system successfully implemented automated "cleaning," replacing messy hand-drawn strokes with idealized geometric versions in real-time.

However, the authors noted several areas for improvement. The system currently relies on "hard" geometric constraints; incorporating "soft" constraints (probabilistic matches) would increase robustness. Additionally, while LADDER is more efficient than manual coding, it still requires human effort to write descriptions. Future work aims to implement "learning by example," where the system generates LADDER code automatically from a user's drawings, and the development of GUI debugging tools to help refine shape constraints.

Summary updated

BibTeX
@inproceedings{hammond2004automatically,
  author = {Tracy Hammond and Randall Davis},
  title = {{Automatically Transforming Symbolic Shape Descriptions for Use in Sketch Recognition}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2004},
}
Figure