next up previous contents
Next: Object Position Up: Describing 2D Shape With Previous: Primitive Shape

Relative Size

The Extended Polygon Boundary representation expresses size in relative, rather than in absolute terms, the same as the ASSF representation. The ASSF system described the size of all features in a single shape relative to the length of that shape's axes. The disadvantage of this system was that it was not possible to directly compare the sizes of two features on different shapes. In fact, it was not always possible to compare the sizes of two features on the same shape, if they fell into the same range between distinguished points in the length quantity space.

This problem can be avoided by describing boundary element sizes relative to each other, rather than relative to a few reference values (whether axis lengths, or other values). If relative size is recorded on a global basis, rather than local to one shape, it is also possible to compare the size of elements on different objects. This ability is essential for reasoning about most types of object interaction.

Recording the relative sizes of all boundary elements in the scene results in a global size ordering. The use of a complete global ordering would provide a large amount of information, but removes some of the advantages of a qualitative representation, in that exact measurement information is needed to construct the ordering. In addition to this construction requirement, the ordering must be partially re-constructed when any movement occurs in the scene. The maintenance of a complete ordering would require that some numeric information be included for re-calculation of the ordering.

This problem can be overcome in part by using a partially ordered space instead of a complete ordering. A size value is given a context in the partially ordered space by three links: one to any other size that is known to be equal in magnitude, one to the smallest size in the space that is known to be larger than it, and one to the largest that is known to be smaller. The resulting partial distance ordering is a network of size relationships similar to the ``quantity lattice'' used by Simmons [Sim86] in investigating qualitative arithmetic.

The greatest advantage of the partial distance ordering is that exact information can be represented together with uncertain information. If all sizes in a scene are known precisely, a complete ordering can be created, while if no information at all is available, all sizes in the scene can be represented in parallel as equally uncertain. A normal application, of course, will involve a mixture of certain and uncertain information, that is represented as a network.

A typical situation where this is necessary is motion planning, where static measurements of the scene before any motion occurs are exactly known, but intermediate positions of the moving object during the proposed motion are only estimated. These estimated positions can be described as a limited range of possible values, while the exact information retains a strict ordering.

Techniques for reasoning with a partial ordering can make use of as much information as is available about any given measurement, thereby providing a natural graceful degradation of system performance when less precise data is available. The implementation described in the following chapter behaves in exactly this way, and it is able to continue reasoning either with imprecise input data, or after modifying its internal representation with inexact qualitative operations.

There are two types of distance information which must be available to a spatial reasoning system: sizes of things, and distances between things. In the EPB system, both types of information are recorded in the global partial distance ordering. The size of boundary segments is recorded explicitly as a length attribute of the segment, which points into the ordering. Distance between boundary elements, which is called ``proximity'', is recorded as part of a link between the elements. Proximity can be used to describe the distance between two elements on the same object, in which case it might also convey implicit information about the overall size of the object, or it can be used to describe the spatial relationships between two different objects.

The implementation of the partial distance ordering uses ``equidistance lists'' - sets of distances (which might be either segment lengths or proximities) of equal magnitude. The zero point in the ordering is the contact list which is the set of boundary elements that are in contact with another element. Contact is therefore treated the same as any other proximity - the distance simply has a magnitude of zero.


next up previous contents
Next: Object Position Up: Describing 2D Shape With Previous: Primitive Shape
Alan Blackwell
2000-11-17