Qualitative Outline Theory

Antony Galton and Richard Meathrel

In Thomas Dean (ed.), Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99) , Stockholm, Sweden, 31 July-6 August 1999, pages 1061-66.
ISBN 1-55860-613-0

Abstract

Shape is the most complex, and hardest to specify, of all spatial attributes. A theory of shape is important for AI both for recognition and description of objects and for reasoning about the possible behaviours of objects. In keeping with the spirit of knowledge representation in AI, a useful theory of shape should have a qualitative basis, while not excluding the possibility of incorporating quantitative information. Theories of shape may be loosely classified as either volume-based or outline-based. The theory presented in this paper is of the latter type, and initially confined to two-dimensional outlines. Outlines are represented by means of strings over an alphabet of seven qualitative curvature types, and a regular grammar is given which generates the strings corresponding to possible outlines. Subsets of the curvature-type alphabet are used to characterise cognitively salient subclasses of outlines, with corresponding regular subgrammars. Operations of decusping, smoothing, and merging are used to simplify outlines for representation at coarser granularity. An algorithm is given for deriving the curvature sequence of an outline, using only local information obtained as the outline is traversed. Finally, indications are given as to how more detailed (including quantitative) information might be incorporated into the theory.

Full paper (Compressed postscript file, 50K, 6 pages)