A Hierarchy of Boundary-based Shape Descriptors

1 Introduction

In the development of conceptual tools for spatial representation and reasoning, the category of shape has proved to be one of the most problematic areas. Some important earlier work, representative of the boundary-based approach to shape, is exemplified by the contour codons of Hoffman and Richards [1982] and the extremum primitives of Leyton [1988]. These two approaches, although differing in motivation and detail, both used the idea of characterising the shape of an outline by means of a string of tokens, recording salient curvaturebased features encountered during a traversal of the outline. A more recent approach, using yet another set of primitives, is that of [Galton andMeathrel, 1999]. In [Meathrel and Galton, 2000], we attempted to define the boundary-based approach to shape in a more general and systematic way. By considering variations in curvature as a starting point, we derived two sets of atomic tokens for describing curves, and presented token ordering graphs for verifying the syntax of atomic curve descriptions.

The present paper extends the work described in [Meathrel and Galton, 2000] in three significant respects: (i) by systematically investigating the structure of sets of atomic curvaturebased tokens, resulting in an unbounded hierarchy of atomic tokens, (ii) by incorporating kink points (angles and cusps) into the framework of tokens, and (iii) by providing a pair of compatibility matrices, and an algorithm, for generating transition tables for any level in the hierarchy, from which level-specific token ordering graphs can be constructed.

2 Deriving the hierarchy of atomic tokens

At each point on a curve, the tangent to the curve at the point is either defined or undefined. The rate of change of the tangent bearing CQ with distance along a curve gives us curvature (the first derivative of tangent bearing with respect to arclength). We can also consider the rate of change of curvature (CR BC ), which is the second derivative of tangent bearing. For each curve we can think of there being an infinite number of associated plots. Our hierarchy of descriptors is based on a discretisation of CQ and its derivatives. For tangent bearing we are interested in whether CQ is defined (BW) or undefined (CD), so we use the quantity space CUBWBN CDCV. Points where the tangent bearing is undefined correspond to angles and cusps, and may be referred to as kink points. For all of the derivatives of tangent bearing (i.e., CRBN CR BC BN CR BCBC BN BM BM BM), we use the quantity space CUB7BN BCBN A0 BN CDCV, since a derivative may be positive, zero, negative, or undefined.

2.1 Curve states

Associated with each point  on a curve is a sequence of qualitative values, representing CQ, CR, CR BC , etc. The complete curve state at  corresponds to an infinite sequence of values. We write BS CZ DC to denote the CZth component of the curve state DC. Not all component sequences give rise to valid curve states. If a component has a value other than CD, then the value of the next component is unconstrained. If, however, a component does have the value CD, then all subsequent components must also be CD. More formally, a curve state DC must satisfy the following constraint:

A partial curve state at  is any initial D2-tuple of the complete curve state. So if DC BP CWBWBNB7CX, for example, then BS BD DC BP BW, BS BE DC BP B7, and DC is a partial curve state that is assigned to points on a curve where the tangent bearing is defined and the curvature is positive.

We refer to a partial curve state with D2 components as a level-D2 state. Given the complete set of states for some level CZ, it is straightforward to generate the set of states for level CZB7BD. Each state DC, at level CZ, generates a set of level-CZB7BD states, CB, as follows (where DD BP BS CZ DC):

There are two partial curve states with one component: CWBWCX and CWCDCX. From these two states we can generate the five states of level 2 and then, from those, the fourteen states of level 3:

For each point on a curve we can assign a partial curve state of CZ components, so we could theoretically represent a curve by providing a mapping between curve points and partial curve states. However, such a mapping would be infinite and therefore of no practical use. Because our state components take qualitative values, however, certain states may persist over intervals of curve and, therefore, support mappings that are finite. A curve state may have an interval and/or a point interpretation. A state that has an interval interpretation may persist over an interval of curve, and a state that has a point interpretation may hold at a single curve point, without holding on any interval adjoining that point. An atomic token identifies a particular interpretation of a partial curve state.

2.2 Interval and point interpretation

For each set of level-CZ curve states, we obtain a corresponding set of level-CZ atomic tokens by considering the allowable interpretations of each state. A state may support an interval interpretation, a point interpretation, or both. An atomic token (or "atom") is a particular interpretation of a particular state, and is identified by a signature consisting of a sequence of qualitative component values. A signature that is underlined indicates an interval interpretation; a non-underlined signature indicates a point interpretation. The atom D+, for example, is identified with the interval interpretation of the state CWBWBNB7CX, and the atom D+-0 is identified with the point interpretation of the state CWBWBN B7BN A0 BN BCCX.

A curve state may hold at a single point iff one of its components is either zero or undefined. This is because if all components are defined, then all of them are continuous, and hence the values 'B7' and 'A0' can only hold over intervals. A curve state may persist over an interval iff none of its components are undefined and, whenever a component has the value zero, the next component also has the value zero. The following predicates, therefore, can be used to determine the interpretations that are supported by a curve state:

2.3 Atomic hierarchy

For each set of partial curve states (each level) we can use the predicates D4D3CXD2D8-CXD2D8CTD6D4 and CXD2D8CTD6DACPD0-CXD2D8CTD6D4 to obtain the corresponding set of atoms. The partial curve states and atoms for level 3 are as follows:

The first four levels of the hierarchy of atomic tokens are shown in Figure 1. Each atom in the hierarchy (except the atoms D and U at level 1) is a child of a single parent atom at the previous level, i.e., each atom at level CZ is derivable from one, and only one, atom at level CZA0BD. We call parent atoms that have more than one child expansive, and those with only one child non-expansive. An interval atom is expansive iff its last component is either 'B7' or 'A0', otherwise it is nonexpansive. A point atom is expansive iff its last component is not 'CD', otherwise it is non-expansive. At level 1, then, there is just one non-expansive atom, U, which propagates through the hierarchy as UU, UUU, and so on. The other level-1 atom, D, expands into five atoms at level 2; two of which are nonexpansive: D0 and DU.

Any atom is either an interval (I) or a point (P), and either expansive (E) or non-expansive (N), giving us four kinds of atoms: IE, IN, PE, and PN. Each IE atom yields five children: two IE atoms, one IN atom, one PE atom, and one PN atom. Each PE atom yields four children: three PE atoms and one PN atom. The non-expansive atoms, IN and PN, yield a single IN atom and a single PN atom, respectively.

The recursive equations for calculating the numbers of each kind of atom at level CZ, and the actual figures for levels 1 to 6, are as follows:

2.4 Atom labelling

Annotating curves with signatures and describing curves with strings of signatures is not ideal. Therefore, for notational convenience, we assign each atom at level two or above a suitable descriptive label, according to the following convention 1 : the label begins with '', 'CI', '', or 'CD', depending on whether the curvature component is positive, zero, negative, or undefined. The remaining components (CR BC BN CR BCBC BN BM BM BM) are denoted by a superscripted string, whose elements are values from the set CUB7BN BCBN A0 BN CDCV. The label is underlined if the atom it is symbolising is an interval. To distinguish between the two distinct kinds of atoms where the curvature component is CD, we use the label 'CD CQ ' for atoms where the tangent bearing component is also CD, and 'CD CR ' for atoms where the tangent bearing is BW. Using the new notation, the first three sets of atomic tokens are written as follows:

1 At level 1, D is given the label 'BW' and U is given the label 'CD CQ ', where 'CQ' signifies that the tangent bearing component is undefined.

Level 1 BM BWBNCD CQ

Level 2 BM BN CIBN CIBNBN CD CR BN CD CQ

Level 3 BM  B7

BN  BC BN  BC BN  A0 BN  CD BN CI B7 BN CI BC BN CI BC BN CI A0 BN CI CD BN  B7 BN  BC BN  BC BN  A0 BN  CD BN CD CR BN CD CQ

2.5 Kink points

At each level in the hierarchy there exists a single kink-point atom labelled CD CQ , each component of which takes the value CD. Such atoms represent points on a curve where the tangent bearing (and therefore all of its derivatives) are undefined, and correspond perceptually to angles and cusps. Clearly, we would like to be able to distinguish between different kinds of kink points, otherwise we are losing important curve information. In particular, the two most relevant aspects of a kink point we would like to preserve are its orientation (whether it is inward-pointing or outward-pointing) and its type, i.e., whether it is an angle or a cusp. In order to distinguish between the different kinds of kink points, we introduce the following kink tokens into our representation: CD BO and CD BQ (for inward and outward pointing angles, respectively), and CD AU and CD AV (for inward and outward pointing cusps, respectively). These tokens have the same status as CD CQ , in that they can be thought of as appearing at every level in the hierarchy. Note, however, that kink tokens are not atomic, since the process by which the atomic tokens are derived does not produce them. Instead, we need to introduce them explicitly.

3 Atomic description

A curve is described by a string of atomic tokens taken from a particular level in the hierarchy. By prefixing descriptions with a symbol indicating curve type, both open and closed curves can be represented. We use ' CN ' for open curves and ' AD ' for closed ones. Our convention for relating changes in tangent bearing to curvature is that a clockwise change in tangent bearing indicates positive curvature, while an anticlockwise change indicates negative curvature. Thus positive curvature is associated with convex curve segments and negative curvature with concave segments. A curve can be traversed in one of two directions. For a closed curve, the direction is that which preserves the intended figure/ground relationship. For open curves, consistent description dictates that one of the two directions is chosen as the "default" one.

Shown in Figure 2 are two curves that have been annotated with level-3 atoms. Note that  BC refers to a convex circular arc (constant positive curvature over an interval), whereas  BC refers to a positive curvature extremum; and analogously with  BC and  BC . Given a closed curve there will be, in general, a number of different token strings that describe it. However, we can easily transform one string into another by cyclically shifting it by a certain amount. In this sense, all of the strings may be considered equivalent. Any one of sixteen level-3 strings may be used to describe the closed curve in Figure 2, two of which are obtained by either starting at the CD BO or starting at the uppermost CI BC :

The importance of specifying a particular direction for open curves is illustrated by the open curve in Figure 2, where a reversal of direction yields the description CN CI BC CD BO  A0 . Note, however, that under a system where "mirror-reflected" curves are considered equivalent, the direction chosen for traversal is unimportant.

3.1 Levels of description

A curve has a description at every atomic level. The most coarse-grained description is at level 1, where only the atoms BW and CD CQ are available. By moving down the hierarchy (and incorporating more qualitative components) we get finergrained descriptions that reflect the increase in discriminatory power that extra components provide.

Given the description of a curve at some level CZ, we can derive all of the coarser-grained descriptions for the curve, i.e., from the description at level 1 through to the description at level CZA0BD. If CG denotes the description of a curve BV, at level CZ BQ BD, then the following straightforward three-step procedure yields the description of BV at level CZA0BD:

1. Replace each atom of CG with its parent.
2. Iteratively replace substrings of the formDCDC (where DC is a single atom) with DC, until there are no more substrings of the formDCDC.
3. If BV is a closed curve, and the string resulting from the previous step is of length greater than two, and begins and ends with atoms of the same type, then remove the last atom in the string.

By applying the procedure to the ellipse shown in Figure 3, we get the level-2 description AD , by re-applying the procedure with AD  as input, we get the most coarse-grained description for an ellipse: AD BW.

Although we can derive all coarser-grained descriptions for a curve given its description at level CZ BQ BD, it is not possible, in general, to derive any of its finer-grained descriptions. The occasion when it is possible to derive a finer-grained description is when the description given consists entirely of atoms that are non-expansive, in which case all finer-grained descriptions are accessible. Consider the description of a square at level 2: AD CICD BQ CICD BQ CICD BQ CICD BQ . Because both CI and CD BQ are non-expansive, we can get the "finer-grained" description at level 3 by replacing each atom in the string with its single child atom. The level-5 description, for example, is AD CI BCBCBC CD BQ CI BCBCBC CD BQ CI BCBCBC CD BQ CI BCBCBC CD BQ . Another example would be a shape that has the level-3 description CN  BC (i.e., a convex circular arc segment). For most shapes it would appear that there exists some minimal value of CZ such that its description at level CZ contains only non-expansive atoms. For the square, CZ BP BE; descriptions at levels CZ BQ BE are unnecessary, leading to no increase in "qualitative precision". For a circle, we need to go to level 3 to achieve this. In this sense, a circle might be regarded as a more complex shape than a square.

4 Token ordering graphs

A curve is described by stringing together those atoms that correspond to the "atomic" qualitative boundary features of the curve. Clearly, some features can occur together and some cannot. A token ordering graph (TOG), of the kind introduced in [Meathrel and Galton, 2000], encodes the constraints that determine the basic string syntax for a set of atoms. In this section, we show how the transition tables that underlie such graphs can be systematically constructed for each level of the atomic hierarchy.

Given a set of atoms, a TOG is a way of pictorially representing the two complementary transition tables that specify which atoms may follow which other atoms in a string. The interval-interval ("I-I") table tells us which interval atoms can follow which other interval atoms. The interval-pointinterval ("I-P-I") table tells us which point atoms can occur in between each pair of interval atoms. It is the construction of these tables, then, that we are primarily interested in. The I-I and I-P-I tables for level 2 are given later, in Figure 4.

4.1 Compatibility matrices

We make use of two compatibility matrices when constructing I-I and I-P-I tables. First, consider the construction of an I-I table for a given level in the hierarchy. Each cell B4row DCBN column DDB5 in an I-I table contains a tick iff the interval atom DD can directly follow the interval atom DC. Given interval atoms DC and DD, at level D2, we can determine whether ot not DD can directly follow DC by making use of the matrix given in Table 1. The matrix tells us whether or not the CZth qualitative components of the atoms DC and DD are compatible.

The CZth component of DD is compatible with the CZth component of DC, and CRD3D1D4CPD8CXCQD0CTB4CZBN DDBN DCB5 holds, iff the condition in the corresponding cell is satisfied. If BS CZ DC and BS CZ DD are of opposing signs then they are definitely incompatible (signified by a BR in the appropriate cell), because a derivative cannot change from positive to negative (or vice versa) without taking the value BC or CD in between. If an interval over which BS CZ has the value BC is followed immediately by an interval over which BS CZ is positive, then in the latter interval it must initially be increasing, i.e., BS CZB7BD must be positive. This explains the entry for cell B4BS CZ DC BP BCBN BS CZ DD BP B7B5. Analogous explanations hold for the other non-trivial entries in the table. Given interval atoms DC and DD at level D2, then, DD can directly follow DC iff CRCPD2-CUD3D0D0D3DBB4DDBN DCB5 holds:

In other words, DD and DC must be distinct interval atoms (to ensure an underlying state change), and the components of DD must be compatible with the components of DC. Note that, whenever a condition in the matrix refers to an "unavailable" component of an atom AB, i.e., when CZB7BD BQ D2, the condition is satisfied because the value of BS D2B7BD AB is unconstrained (since it is not specified). As an example, consider the level-3 interval atoms  B7 and  BC , and whether  BC can directly follow  B7 . We start by comparing the second component of each atom, since all interval atoms have the same value (BW) for their first component. Because both BS BE  B7 and BS BE  BC take the value 'B7', the compatibility condition is BQ, and therefore satisfied. The condition of compatibility for the final component pair evaluates to BS BG  B7 BP A0, since BS BF  B7 BP B7 and BS BF  BC BP BC. The condition is satisfied because  B7 has no fourth component ( B7 is a generalisation of a set of child atoms that includes the level-4 atom  B7A0 ).

Next, consider the construction of an I-P-I table for a given level in the hierarchy. Each cell B4row DCBN column DDB5 in an I-P-I table contains a list of point atoms that can occur in between interval atoms DC and DD. For I-P-I tables, we make use of the compatibility matrix given in Table 2, which differs from the matrix for I-I tables in that the notion of compatibility concerns three components rather than just two. Given a point atom D4 and interval atoms DC and DD, at level D2, the component BS CZ D4 is compatible with the components BS CZ DC and BS CZ DD, and CRD3D1D4CPD8CXCQD0CTB4CZBN D4BN DCBN DDB5 holds, iff the condition in the corresponding cell is satisfied. A point atom D4, then, can occur in between two interval atoms DC and DD (after DC and before DD) iff CRCPD2-D3CRCRD9D6-CQCTD8DBCTCTD2B4D4BN DCBN DDB5 holds:

CRCPD2-D3CRCRD9D6-CQCTD8DBCTCTD2B4D4BN DCBN DDB5 B0 B4BLCPBN CQ AK D2B5B4 BS CP D4 BIBP BS CP DC CM BS CQ D4 BIBP BS CQ DD B5 CM B4BKCZB5B4 BD BO CZ AK D2 AX CRD3D1D4CPD8CXCQD0CTB4CZBN D4BN DCBN DDB5 B5

In other words, the underlying curve state of D4 must be distinct from the underlying curve states of DC and DD, and the qualitative components of D4 must be compatible with those of DC and DD. As before, conditions that refer to "unavailable" components are automatically satisfied. To illustrate we shall use the table to determine which point atoms can come between DC BP  A0 and DD BP  BC . We have BS BE DC BP BS BE DD BP B7 and BS BF DC BP A0 BN BS BF DD BP BC. We want to know the possible values for BS BD D4, BS BE D4 and BS BF D4. Since the definition of CRCPD2-D3CRCRD9D6-CQCTD8DBCTCTD2 imposes no constraints on the first level components, BS BD D4 can be either BW or CD. For CZ BP BE, the top-left cell of the matrix states that BS BE D4 may be any of B7, CD, and BC, but BC is ruled out because it requires that BS BF DC BP A0 and BS BF DD BP B7, which contradicts BS BF DD BP BC. Moving on to CZ BP BF, we consult the middle cell in the bottom row of the matrix. We see that BS BF D4 may be either CD or BC, the additional constraints on the latter value being irrelevant in the present case, as CZB7BD BQ BF. Remembering that if any component is CD, all subsequent components must be CD too, we derive the following candidate component sequences for D4:

corresponding to the level-3 atoms CD CQ ,  CD ,  BC , and CD CR . The first condition of CRCPD2-D3CRCRD9D6-CQCTD8DBCTCTD2 rules out  BC , as its underlying curve state is not distinct from that of DD. Thus we conclude that only the point atoms CD CQ ,  CD , and CD CR can occur in between the interval atoms  A0 and  BC .

4.2 Transition tables

The set of atoms at level CZ is the union of a set of interval atoms,
CZ , and a set of point atoms,  CZ , e.g., at level 2 we have
BE BP CUBN CIBNCV and  BE BP CUCIBN CD CR BN CD CQ CV. The transition tables at level CZ, I-I CZ and I-P-I CZ , each contain CY
CZ CY BE cells, one for each ordered pair of interval atoms. We refer to a cell B4row DCBN column DDB5 in the I-I CZ and I-P-I CZ tables by writing I-I CZ B4DCBN DDB5 and I-P-I CZ B4DCBN DDB5, respectively. The following algorithm populates the I-I and I-P-I tables for any level CZ BQ BD in the hierarchy 2 :

2 At level 1, I-I BD B4BWBNBWB5 is empty and I-P-I BD B4BWBNBWB5 contains CD CQ .

for each CWDCBN DDCX BE 
 CZ A2 
 CZ do if CRCPD2-CUD3D0D0D3DBB4DDBN DCB5 then I-I CZ B4DCBN DDB5 AW D4 ; for each D4 BE  CZ do if CRCPD2-D3CRCRD9D6-CQCTD8DBCTCTD2B4D4BN DCBN DDB5 then add D4 to I-P-I CZ B4DCBN DDB5;

Owing to space constraints, only the I-I and I-P-I transition tables for level 2 are given here (see Figure 4). As described in DC2.5, we can substitute the single kink-point atom CD CQ with a set of kink tokens: CUCD BO BN CD BQ BNCD AU BN CD AV CV. In order to do this, we need to replace each CD CQ in cell B4DCBN DD) of the I-P-I table with the correct subset of kink tokens, as follows: (i) replace CD CQ with CD BO and CD BQ , and (ii) add CD AU if BS BE DC BP B7 or BS BE DD BP B7, and add CD AV if BS BE DC BP A0 or BS BE DD BP A0, i.e., inward-pointing cusps must be flanked by an interval of positive curvature and outward-pointing cusps by an interval of negative curvature (cf. [Galton and Meathrel, 1999, DC3.2]).

4.3 Graph correspondence

A TOG consists of nodes representing atomic tokens and edges representing token ordering constraints. The nodes for interval atoms are shown as rectangles and those for point atoms as circles. Any path through a TOG, which starts and finishes at a node representing an interval atom, yields a syntactically valid string of tokens that is instantiable as an open curve and that may or may not be instantiable as a closed curve. A TOG that encodes the ordering constraints for the atoms of level 2 (incorporating the set of kink tokens) is shown in Figure 5. We have seen that we can construct I-I and I-P-I tables for any level of the atomic hierarchy. From the tables for a particular level, a corresponding TOG can be constructed that visually encodes the constraints given by the table contents. We do not here provide an algorithm for constructing TOGs from I-I and I-P-I tables; details relevant to such an algorithm may be found in [Meathrel and Galton, 2000, DC5]. The TOG in Figure 5, then, corresponds to the I-I and I-P-I tables given in Figure 4 (with CD CQ replaced with the kink tokens, as described at the end of DC4.2). The TOGs in Figures 2 and 4 of [Meathrel and Galton, 2000] correspond, respectively, to the I-I and I-P-I tables of levels 2 and 3 of the atomic hierarchy 3 .

3 With CD CQ not replaced by the more-specific kink tokens.

5 Conclusion

We have generalised the work described in [Meathrel and Galton, 2000], by deriving an unbounded hierarchy of atomic tokens and incorporating distinct kink tokens for inward and outward pointing angles and cusps. Both open and closed curves have qualitative descriptions, consisting of strings of atoms, at every level of the hierarchy, with the most coarsegrained description at level 1. Higher-numbered levels, where more qualitative components are included, possess greater discriminatory power and allow for finer-grained descriptions. We showed how, for each level of the hierarchy, I-I and I-P-I transition tables, encoding the ordering constraints for the set of atoms at that level, can be constructed by a simple algorithm that makes use of a pair of compatibility matrices. From a pair of I-I and I-P-I tables, a corresponding TOG can be constructed that visually encodes their constraints.

In [Meathrel and Galton, 2000], we showed how sequences of atomic tokens (with "contexts") can be used to model boundary-based schemes such as those of Leyton [1988] and Hoffman and Richards [1982]. We believe the theory presented here provides an adequate basis for constructing any boundary-based scheme of qualitative shape descriptors.