Computer Vision Representations

Generalized cylinders

Generalized cylinders use the idea that many biological and manufactured objects are naturally described as a ``swept volume'' of a two dimensional set moving along some 3-space curve.

A generalized cylinder is thus defined by

• a sweeping area,
• an axis, and
• a sweeping rule.

Some simple examples of objects that are easily modelled by generalized cylinders are given by a cylinder itself, a cone, and a torus. For a cylinder, the sweeping area is a disc in the x-y plane, the sweeping axis is the z axis, and the sweeping rule is constant. For a cone, the sweeping area is a disc in the x-y plane, the sweeping axis is the z axis, and the sweeping rule is linear, say 1-z. For a torus, the sweeping area is a disc in the y-z plane, the sweeping axis is a circle in the x-y plane, and the sweeping rule is constant. Problems that occur with the generalized cylinder representation are that the rules can be complicated, and the representations are not generally unique. Nevertheless, generalized cylinders can be very useful and do allow easy calculation of a number of mathematical properties of the objects involved, for example, volume or surface normals, etc. Rod Brooks used generalized cylinders in his vision system ACRONYM - A Cone Representation of Objects Not Yet Modelled (1981).

Aspect graphs

Consider the possible line drawings of a given three dimensional object. Although there is an infinite number of line drawings, there is only a finite class of labellings.

For example, for a cylinder, there are three characteristic views, or aspects. These are illustrated in figure 4.

 

Figure: The characteristic views of a cylinder.

These characteristic views divide 3-space into a finite class of volumes, each volume representing a different aspect of the object. This defines an aspect graph, the nodes of which are the volumes in space and the arcs correspond to whether volumes are neighbours or not. The aspect graph of a cylinder is given in figure 5.

 

Figure: The aspect graph of a cylinder.

Moving from one aspect to another is called an event. This corresponds to moving along an arc in the aspect graph. However, the method of aspect graphs is unwieldy for complicated objects. For example, it has been estimated that there are approximately 10⁴ different aspects for Michaelangelo's ``David''.

Skeleton representations

If a region is made of thin components, it can be described for many purposes by a ``stick figure'' skeleton. Skeletons may be derived by thinning algorithms that preserve the connectivity of regions.

The skeleton is defined in terms of the distance of a point x to a set A, where

$$d(x,A) = \inf_{z \in A} d(x,z).$$

The function d can be any metric, for example, the Euclidean metric. Now let B be the set of boundary points of an object. For each point p in the object, find its closest neighbours on the boundary. If more than one boundary point is at the minimum distance to p, then p is on the skeleton of the object. Thus, the original region may be recovered by the union of discs centred on the skeleton points.

The problems with the skeleton representation arise from its sensitivity to noise. Very small changes in a region can result in very large changes to the skeleton of the object.