Qualitative Outline Theory

Antony Galton, Richard C. MeathrelIJCAI 1999

Abstract

This paper presents a formal qualitative language for describing 2D shapes through their outlines. By representing shapes as cyclically permutable strings of seven curvature primitives—including angles, curves, and cusps—governed by a regular grammar, the authors establish a framework for symbolic spatial reasoning. This approach allows for shape categorization and behavior prediction without the computational overhead of precise coordinate geometry.

Introduction

Spatial reasoning in Artificial Intelligence has traditionally focused on position or connectivity. When shape is addressed, the approach is typically quantitative, involving complex coordinate geometry. However, humans often reason about shapes qualitatively; we recognize that a "pointy" object may not fit in a "rounded" hole without needing exact measurements. Quantitative models are often computationally expensive and provide more detail than necessary for high-level reasoning. Qualitative Outline Theory (QOT) aims to fill this gap by creating a symbolic, linguistic approach to shape description and categorization.

Methodology

The authors propose representing a 2D outline as a cyclically permutable string (a ring) of symbols. This representation treats shape as a formal language, allowing researchers to use tools from computer science, such as regular expressions and automata, to analyze physical objects.

The Alphabet

The theory defines seven primitive qualitative curvature types that serve as the building blocks for any 2D outline:

  1. / : Straight line segment
  2. ⊃ : Convex curve segment
  3. ⊂ : Concave curve segment
  4. > : Outward pointing angle
  5. < : Inward pointing angle
  6. ⋗ : Outward pointing cusp
  7. ⋖ : Inward pointing cusp
Figure 1: Mapping the seven primitive curvature types to a sample 2D outline.

The Grammar and Simplification

To ensure these strings represent physically possible, closed 2D shapes, the authors developed a regular grammar consisting of 95 rules. This grammar enforces physical constraints, such as boundedness (requiring at least three convex points or a convex curve) and adjacency rules (e.g., two "point-like" elements cannot be adjacent; they must be separated by a "line-like" element).

Furthermore, the theory includes three simplification operators to handle different levels of detail, or "granularity":

  • Decusping (D): Converting cusps to angles, effectively viewing a shape from further away.
  • Smoothing (S): Replacing sharp angles with curves.
  • Merging (M): Absorbing straight lines into adjacent curves.
Figure 2: The application of Decusping (D), Smoothing (S), and Merging (M) operators to simplify a shape's qualitative description.

Key Insights

  • Sublanguages for Classification: By restricting the alphabet, the theory defines sublanguages that automatically categorize shapes. For instance, a string using only / and > represents a convex polygon, while a string using only ⊃ and ⊂ represents a smooth curvilinear outline.
  • Canonical Ordering: Since a closed loop has no natural start point, the authors utilize a lexicographical ordering system to ensure every unique shape has a single "canonical" string representation.
  • Granularity through Transformation: The simplification operators provide a systematic method for moving from high-detail representations to low-detail ones, reflecting how shape perception changes with distance.

Results and Limitations

As a theoretical proof-of-concept, the paper demonstrates that QOT can distinguish between shapes that previous qualitative theories struggled with, such as differentiating a triangle from a smooth curve. It also shows how the theory can be annotated with semi-quantitative data (like "short" or "long" segments) to increase descriptive power.

However, the current theory is strictly limited to 2D outlines and cannot distinguish between shapes with the same sequence of curves but different proportions (e.g., a square versus a rectangle). Extending the grammar to 3D and investigating how orientation or relative length constraints interact remain key areas for future work.

Summary updated

BibTeX
@inproceedings{galton1999qualitative,
  author = {Antony Galton and Richard C. Meathrel},
  title = {{Qualitative Outline Theory}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure