Next: Object Relative Position Up: Describing 2D Shape With Previous: Relative Size

### Object Position

The EPB representation contains no explicit information about overall object shape; it only has information about elements of the object boundary. This means that any description of the relative positions of objects must be in terms of their boundary elements rather than their axes, for example. This is not necessarily a disadvantage for purposes of analysing object interactions, since any interaction between the objects will take place on their boundaries. The position of an object in terms of its boundary elements can be defined relative to all other objects in the scene simply by stating what other objects have proximity relationships to each boundary element. This proximity information in the partial distance ordering constitutes an effective qualitative representation of two dimensional position.

Since boundary elements are used as the basic unit for describing the overall scene, rather than object axes, as in the ASSF representation, some technique is necessary for reducing the overall number of relationships described. This is because the total number of possible relationships between all boundary elements in the scene is the square of the number of elements in the scene, and becomes very large for even a moderately complex scene.

The method used to reduce the number of relationships is as follows: proximity is only measured between those boundary elements which would come into contact if the objects were to move toward each other. A simple transform can be carried out on visual scene data that filters out unlikely contacts, and also orders the remaining element proximities appropriately for inclusion in the partial distance ordering.

The proximity transform involves simultaneously ``expanding'' the boundaries of every object in the scene by constructing an enclosing outline around it. The boundaries are expanded in steps until elements on the expanded boundaries come into contact (this process is shown in Figure 4.1). The set of contacts that occur at a given expansion step are formed into an equidistance list, and these lists are ordered by the stages in the expansion at which they are formed. This information is integrated in the partial distance ordering with object internal proximities and segment lengths by simultaneously ``expanding'' along segments and inside objects, so that these distances can be formed into ordered equidistance lists together with proximities between boundary elements on different objects. This allows direct comparison of segment length with distances between objects.

The combination of boundary specified object relationships and parallel levels of detail on the object boundary means that at coarse levels of detail, solid objects can appear to interpenetrate. Consider two combs which are interlocked, as shown in figure 4.2. When viewed at a fine level of detail, the teeth of the combs are seen to be laced together. When viewed at a coarse level of detail, however, the combs have no teeth. The toothed edge of the comb may appear to be a wiggle, or even a straight boundary segment. This is a reasonable representation, since many operations can be performed on the comb as if the teeth were a straight edge (such as picking it up by the edges), however the apparent overlap of the combs now means that the proximity between the two coarsely represented edges should be negative, and this is inconsistent with the ``size'' ordering, which is a representation only of magnitude.

This apparent boundary overlap is a common situation when fastening devices are being considered. Fastened objects are usually interlocked in some way, and the interlocking mechanism is often small by comparison to the whole object, so that at some levels of detail the object boundary will simply be extended to include it. The use of a ``negative'' proximity here, although not strictly meaningful in a magnitude ordering (magnitudes are always positive), allows the amount of overlap of the coarse boundaries to be explicitly represented. To allow this, overlaps are included in the partial distance ordering like any other proximity information, but they are tagged as a special type. This means that the complete partial distance ordering may include four different types of distance: length, internal proximity, external proximity, and now overlap.

Next: Object Relative Position Up: Describing 2D Shape With Previous: Relative Size
Alan Blackwell
2000-11-17