Qualitative Outline Theory

1 Introduction

The recent upsurge of interest in qualitative spatial rea­ soning in artificial intelligence has given rise to prolific work in the analysis of such spatial attributes as po­ sition, orientation, and connectivity, but comparatively little seems to have been done on the equally important attribute of shape. One reason for this is surely that shape is by far the most complex, and hardest_ to spec­ ify, of all spatial attributes; of the aforementwned at­ tributes, only connectivity comes anywhere near shape in the number of degrees of freedom it exhibits . The one area of artificial intelligence in which shape has been studied in some detail is Computer Vision. Here the ap­ proach tends to be rather more quantitative in nature than has been the norm in the knowledge representa­ tion community in which qualitative spatial reasoning has been developed. Outside artificial intelligence we must look to cognitive psychology for the most perti­ nent work on the subject of shape, some of which will be briefly discussed below.

· Richard Meathrel's research is supported by EPSRC award no. 97305965.

A theory of shape is important for AI on at least two counts. First, shape plays an important part in the recognition and description of objects. This is the aspect that has been focussed on in Computer Vision. Second, since the possible behaviour of an object , particul_arly in interaction with other objects, is strongly constramed by its shape, reasoning about the behaviour of ~bjects needs to be informed by a theory of shape. This rea­ soning may be concerned with something as simple as whether an object can fit into a container (size as well as shape is important here, of course), or whether one object can be concealed behind another, or it may be some much more complex chain of deductions concern­ ing the behaviour of a complexly interlocking mechanism such as a clock (cf. Faltings [1990]).

Existing approaches to shape may be loosely classi­ fied as either volume-based or outline-based. A complex solid object is composed of a number of smaller solid pieces put together in a particular way, as for example a coffeepot might consist of a body in the form of a trun­ cated cone, with a handle in the form of a half-torus and a spout in the form of a cylinder obliquely cut off at one end. This type of volume-based description is ex­ emplified by the work of Biederman [1987] and of Marr and Nishihara [1978)1. The alternative approach is to characterise the form of the outline of the object, for example by noting the variation in curvature across dif­ ferent positions. Examples of outline-based approaches to two-dimensional shape are those of Leyton l1988] and of Hoffman and Richards [1982], as well as the "multires­ olution" approach of Cinque and Lombardi [1995].

In this paper we propose an outline-based approach to the classification of shape which is in certain re­ spects more general than those just mentioned. Ley­ ton's work, for example, assumes that the shapes b~ing studied have smooth outlines with continuous denva­ tives. While any shape can be approximated by such outlines, it seems to us to be something of a limitation of a shape-classification system if the only way it provides to describe a triangle, for example, is as something ap­ proximated to by a certain class of smooth curves (those having just three curvature maxima). In our system, a triangle is given an exact representation 2 which distin­ guishes it from any smooth curve.

1 In two dimensions, "volume" becomes "area".

2 Existing outline-based approaches

In this section we briefly review a number of existing outline-based approaches to shape, in order to provide a basis for comparison with the system we propose. It should be emphasised that any such scheme can be evalu­ ated from three quite different standpoints. One of these concerns the techniques required for generating qualita­ tive representations of shape from some antecedent "ex­ act" representation, be it in the form of a digitised image or some continuous analogue of the shape itself. The sec­ ond ("internal") point of view presupposes the existence of qualitative representations within the scheme and con­ siders issues such as their expressive scope, manipulabil­ ity, and relationships to other such representations. The third point of view is concerned with the applicability of the scheme to new or pre-existing problems. We shall not attempt a full analysis of any of the schemes from all three points of view.

2.1 Hoffman and Richards

Hoffman and Richards [1982] view the identification of an object as a process carried out by the visual system, in which the description ascribed to the shape of an object is used as an initial index into a stored library of shapes. They see the primary problem of shape-description as that of correctly segmenting a shape into constituent parts. The key to such segmentation is provided by the following transversality regularity:

"When two arbitrarily shaped surfaces are made to interpenetrate they always [i.e., almost certainly] meet in a contour of concave discon­ tinuity of their tangent planes."

Extrapolating from this principle, they base their object recognition system on the idea of identifying negative curvature minima on the outline of an object as points at which to segment it into parts. One problem with this, which these authors do not appear to address, is that in many cases these curvature minima alone do not determine where the segmentation lines should be drawn in the interior of the figure . Given that we know the whereabouts of the part-defining boundary points, how do we complete the segmentation?

2.2 Leyton

Leyton [1988] presents a theory of shape which, like that of Hoffman and Richards, accords key importance to the curvature extrema around the outline of a shape. Leyton uses curvature extrema (both maxima and minima) not to segment an object into parts, but to infer the history of processes that have acted on a shape to produce it.

2 Namely,/>/>/>. See §3.1 for explanation.

The idea is that each type of curvature extremum is associated with a different kind of process in the defor­ mational history of a shape, as follows:

With each process type is associated a continuation rule and a bifurcation rule defining the possible de­ velopment of the process through time; by the table above a developmental sequence generated by these rules is translated into a corresponding sequence of outline types. By reasoning backwards one can use .the current shape of an object to infer the processes which have acted on it to produce that shape.

The scope of Leyton's theory is clearly limited to the shapes of objects which do acquire their shapes through a developmental sequence of the kind it is able to de­ scribe. This primarily limits it to "natural shapes such as tumors, clouds, and embryos" . It cannot apply, for ex­ ample, to most human artefacts, which are typically as­ sembled out of separate components rather than formed by a process of deformation. Another limitation is that the theory, as stated, can only apply to shapes whose outlines are smooth, continuously differentiable curves: no cusps, angles, or straight sections are allowed.

2.3 Cinque and Lombardi

The multiresolution approach of Cinque and Lombardi [1995] enables them to generate a sequence of strings characterising the same shape analysed at different lev­ els of resolution, an idea that also appears in a somewhat different context in the work of Witkin [1983] . The ex­ ample they give is the outline of a fish, which, at the highest resolution level, is divided into segments bearing the (cyclically-permutable) label-sequence YSCYCSCY­ CYCYCYCS, where 'C', 'S' and 'Y' stand for "concave", "straight", and "very convex" respectively {other possi­ ble labels being 'W' for "very concave" and 'X' for "con­ vex"). At the lowest level of resolution shown, the string becomes XSXCXCS. The labels are obtained by simu­ lating a heat-diffusion process on the shape, resulting in concave and convex boundary elements ending up at lower and higher "temperatures" respectively. It is es­ sentially a quantitative technique, although the symbol strings derived from it may be regarded as qualitative in nature.

3 Qualitative outline theory

We offer here a system for the qualitative description of two-dimensional outlines; the system has a number of interesting and cognitively salient subsystems.

It is a formal language for shape, with interesting sub­ languages. We give a regular grammar for the full lan­ guage, and illustrate how grammars for the sublanguages can be derived from it.

3.1 Qualitative curvature types

We build our shapes from the following seven qualitative curvature types:

• / Straight line segment
• => Convex curve segment
• C Concave curve segment
• > Outward pointing angle
• < Inward pointing angle
• >- Outward pointing cusp
• -( Inward pointing cusp

The shape illustrated in Figure 1 contains two straight­ line segments and one of each of the other curvature types, as indicated.

There are a number of ways of grouping the seven types, of which perhaps the most fundamental is the sep­ aration between line/ike elements (/,:>,C), which con­ tribute to the length of an outline, and point/ike elements (>, <, >- , -(), which do not. Another important group­ ing is outward(:>,>,>-) versus inward (C, < , -(),with/ belonging to neither category.

A possible eighth curvature type is a point of inflec­ tion, where a convex curve segment meets a concave one without an angle or cusp at their meeting point. It was not felt necessary to include this since it provides no information over and above that provided by the seven types listed above.

3.2 Figures

A figure is defined by a cyclically permutable string of curvature-type symbols subject to the following con­ straints:

• The string must contain either :> or at least three convex points (to ensure boundedness) .
• It must not contain two consecutive occurrences of the same curvature-type symbol.
• It must contain no two consecutive points .
• Any occurrence of either -( or >- must be adjacent (on at least one side) to an occurence of :> or C respectively.

By "cyclically permutable" we mean that the last symbol in the string must be regarded as being followed by the first, producing a ring rather than a string.

We believe that these constraints are sound and com­ plete in the sense that

1. Any "well-behaved" figure 3 has a ring description satisfying these constraints.
2. Any finite ring which satisfies the constraints defines a bounded figure (indeed a whole class of them) .

The outline pictured in Figure 1 can be described, running clockwise from the bottom, by the string =>< / >/>-C-o(; and equally by any cyclic permutation of this string (e.g., >-C-(:J< / > /) or of its reversal (e.g., :J-(C>- I> I<) .

3.3 Sublanguages

The following subsets of the set of qualitative curvature types generate important classes of outlines:

1. {:>, C, >, <, -(, >-} (Curvilinear outlines - i.e., no straight segments)
2. {:>, C, /} (Smooth outlines: no cusps or angles)
3. {=>,/,>}(Convex outlines)
4. {/, >,<}(Polygons: no curved segments)
5. {:>, /} (Convex smooth outlines)
6. {:>, >} (Convex curvilinear outlines)
7. {/, >} (Convex polygons)

Note that the class of convex smooth outlines is isomor­ phic to the class of convex curvilinear outlines: each el­ ement of the former can be converted into an element of the latter by replacing / by >, and vice versa. Sim­ ilar isomorphisms exist between other classes not listed above, e.g., "nephroids" (generated by{:>,-(}) and "as­ troids" (generated by { C, >-}).

3.4 Qualitative outline grammars

The constraints enumerated above can be captured by means of a formal grammar which generates all and only those rings which satisfy the constraints. More exactly, for each admissible ring, the grammar will generate at least one string which represents it. The grammar, which is regular and contains 95 rules with 35 non-terminal symbols, is given in the Appendix. In this grammar, "A" denotes the empty string.

Formal grammars for each of the sublanguages dis­ cussed above can be derived from the full grammar by selecting an appropriate subset of the rules. For exam­ ple, convex polygons, which contain only the curvature types / and >, are generated by the rules:

F> - ;c,

G; - > G>

H> - /I; I A

G> - /H;

H; - >H>

s - /F; F; - > F>

I; - > H>

3 This excludes fractals and other "pathological" outlines.

which can be simplified to

Similar grammars can be constructed for the other sub­ languages, with simplification possible in most cases.

The idea of a grammar for shape is not new, cf. Stiny [1980], Leyton [1988], but our grammars are not closely related to this earlier work.

3.5 Relations amongst the subclasses

Typically the smaller subclasses can be seen as homo­ morphic images of larger ones, under certain natural transformations involving a systematic loss of informa­ tion. This idea is related to the phenomenon of gran­ ularity which has received considerable attention in the knowledge representation community.

From a distance, a cusp looks very much like an angle. We can therefore apply a decusping operation to convert every instance of --< or >- to < or > respectively. If we started with the full set of outlines, the resulting outlines belong to the class defined by { :J, C , I, <, >} .

Other transformations are smoothing, by which angles are rounded off to convex curves, so that >, < are re­ placed by :J, C respectively (with subsequent collapse of any resulting sequences of the form :J:J or CC to :J, C respectively), and merging, by which a straight section of outline is merged with an adjacent curve (thus :J I and I :J become :J, and C I and I C become C, again with collapse of consecutive duplicates if necessary).

Under these transformations, an outline such as

becomes successively transformed to C>C> I>, then to C:JC:J I :J , and finally to C:JC:J, (see Figure 2) .

Figure 3 shows all the symmetrical subclasses, i.e., those for which each of the pairs {:J , C}, { <, >} and {--<, >-} is present or absent together. The arrows indi­ cate how the transformations of decusping, smoothing and merging operate on these subclasses. (Note that merging applied to { :J, C, I, >, <} does not give, as one might expect, { :J, C, >, <}; this is because a sequence such as > I > is unaffected by merging.)

3.6 Extracting the curvature sequence

To be useful, a representational formalism needs to be accompanied by a procedure for generating representa­ tions from the objects that they are representations of. In the case of qualitative outline theory, this means that we need to be able to extract the curvature sequence of an outline from the outline itself, or at any rate from a pictorial representation of it. The outline might be presented as a closed curve or colour-edge on a flat sur­ face, or it might be the boundary of a sheet of material; we need not at this stage specify its nature in more de­ tail. What we do assume is that we have a mechanism for tracing round the outline, keeping track of how the bearing (measured clockwise from an arbitrary fixed ref­ erence, e.g., "north") is changing. This enables us to give an algorithm for deriving the curvature sequence of an outline, using only local information obtained as the outline is traversed.

We begin anywhere we like on the outline and follow round clockwise.

• So long as the bearing varies continuously, we must have one of I, :J, C, according as the bearing is con­ stant, increasing, or decreasing.
• If there is a discontinuous change in the bearing, we have one of >, <, >-, --<. If the (clockwise) increase in bearing is less than 180°, we have >, if it is greater than 180°, we have <, and if it is exactly 180°, we have >- or -.<. To distinguish the last two cases, we have to keep track of where the section of outline just before the cusp is in relation to the section just after it. If the former is to the left as seen from the latter, we have --<, if to the right, >-.
• If on returning to the starting point the last curva­ ture type is the same as the first, omit it.

The above procedure can be followed with "clockwise" and "left" swapped with "anticlockwise" and "right", and the bearings measured in the anticlockwise sense.

3. 7 Canonical form of a sequence

In the above procedure we will obtain different results de­ pending on where we start and whether we trace the out­ line clockwise or anticlockwise. But any such result can be converted to any other for the same outline by means of an appropriate cyclic permutation together with, if necessary, reversal.

To facilitate recognition and indexing of qualitatively identical outlines, we select just one of its curvature-type sequences as canonical. To do this we first establish an (essentially arbitrary-but see below) canonical order­ ing of the curvature types, e.g., :::>, C, /, >, <, >-, ~. This determines a lexicographic ordering on curvature-type sequences. For a given outline we choose that curvature­ type sequence that comes earliest in this ordering. To convert an arbitrary curvature-type sequence into canon­ ical form we must find that permutation or reversed per­ mutation of it which is lexicographically earliest.

It should be noted that the grammar given in the ap­ pendix does not, in general, generate only the canon­ ical curvature-type sequence for a given outline. For example, as well as the canonical string :::>C:::>C>, the grammar also generates the non-canonical permutations :::>C>:::>C, :::>C:::>>C, and :::>>C:::>C, but none ofthe other six possibilities. The ordering of the curvature types is not entirely arbitrary: the ordering of the three linelike elements is tailored to the way the grammar is organ­ ised, in such a way as to guarantee that the canonical sequence is always generable.

3.8 Quantitative considerations

It is in the nature of a qualitative representation system that one representation can correspond to many differ­ ent objects. Objects which are indistinguishable within the system may nonetheless differ markedly with respect to features not accessible to the system. For a qualita­ tive representation such as ours, this will include all the quantitative features whose exact expression requires the use of real-number measurements. An example of this is shown in Figure 4, where five different exemplars are given of the qualitative outline type :::>~:::>~. It would not, perhaps, be true to say that the differences amongst these figures are purely quantitative-but they are quan­ titative inasmuch as they have to do with the relative lengths and curvatures of the linelike segments. An ob­ vious limitation of our system, as it stands, is its inability to discriminate between these different outlines.

Our qualitative representations could be extended in various ways to capture some of these distinctions. For example, each ~ symbol could be annotated with in­ dices such as U, D, L, R (for "upward pointing", "downward pointing", "left pointing" and "right pointing"). Under this scheme, the first two outlines in the figure are represented as :::>~n :::>~n, the others as :::>~L :::>~R, :::>~n :::>~u, and :::>~R:::>~u. These representations are still qualitative, and allow considerable lee-way, but they certainly come closer to capturing the essential elements of the visual appearance of the outlines.

Other aspects of the outlines might be captured by annotating the linelike elements ( :::> in these examples) by indices denoting their relative lengths. This could be done in a "semi-qualitative" way by adopting, say, a three-point scale of "short" (S), "medium" (M) and "long" (L )-with an inevitable attendant arbitrariness as to the demarcations between these categories. Sim­ ilarly, the angle types ( < and >) could be annotated with an indication of the size of the angle as well as the direction it is pointing in.

Clearly, our qualitative outline theory can be extended in many ways to include more precise information about the outlines it represents. It will be necessary to inves­ tigate how different such extensions interact with each other, e.g., fixing the orientations of the pointlike ele­ ments could impose constraints on the possible relative lengths of the linelike ones. The detailed working out of these constraints is likely to be problematic.

We advocate our theory as an appropriate baseline on which may be built more elaborate outline-based theories of shape to suit the particular needs of different areas of artificial intelligence and related disciplines.

4 Relation to other systems

Hoffman and Richards [1982] segment an outline at cur­ vature minima, using maxima and zeros to describe the shape of each segment. This results in four basic types of segment (loosely analogous to our curvature types, but restricted to smooth curves), which they call con­ tour codons 4 .

Leyton [1988] classifies outlines in terms of the pro­ cesses that might have given rise to them: each curva­ ture extremum is taken as indicative of an appropriate process that has led to the formation of that extremum by acting on some initially simpler outline: "each cur­ vature extremum implies a process whose trace is the unique symmetry axis associated with, and terminat­ ing at , that extremum" . Again there is a restriction to smooth curves.

Our system does not deal with extrema except in so far as the "point-like" curvature types ( <, >, ~~ >-) can be so regarded; curvature extrema in smooth curves are not singled out by our system. Given that both the above systems restrict themselves to smooth continuously dif­ ferentiable curves (the motivation for this being that it opens the way for a mathematical treatment using the tools of differential geometry), all the curves they con­ sider belong to our class {:::>, c}, but within this class they can make finer discriminations than we can-for example all convex curves in this class are described as ":J" in our system, but Leyton can recognise infinitely many varieties of this basic type according to how many protrusions and squashings they exhibit.

4 This approach has been extended by Rosin [1993] to in­ clude angles, cusps, and straight segments.

Cinque and Lombardi [1995] do not specify the cut-off point between "concave" and "very concave", or "con­ vex" and "very convex", and it would seem that there is inevitably something rather arbitrary about it. Even so, however the distinctions are defined, they afford dis­ criminations beyond the capabilities of our system.

In summary, the other systems considered here handle a restricted subset of the full range of outlines that our system handles, but on the other hand within this subset they are capable of making finer discriminations. There is a trade-off between scope and detail.

5 Concluding remarks

We have proposed a formal language for the qualitative representation of two-dimensional outlines. We have dis­ cussed both the scope and limitations of the language and have compared it with some other systems in the lit­ erature. We have indicated how the language may be ex­ tended, if desired, to enable finer shape-discriminations to be made. We have not addressed the problem of ex­ tending the theory to three dimensions, although this is an obvious next step to consider. This work forms part of an ongoing investigation of formalisms for the qualita­ tive representation of shape, on which we hope to report further at a later date.