A novel method of robust skeletonization based on the Voronoi diagram of boundary points, which is characterized by correct Euclidean metries and inherent preservation of connectivity, is presented. The regularization of the Voronoi medial axis (VMA) in the sense of H. Blum's (1967) prairie fire analogy is done by attributing to each component of the VMA a measure of prominence and stability. The resulting Voronoi skeletons appear largely invariant with respect to typical noise conditions in the image and geometric transformations. Hierarchical clustering of the skeleton branches, the so-called skeleton pyramid, leads to further simplification of the skeleton. Several applications demonstrate the suitability of the Voronoi skeleton to higher-order tasks such as object recognition.>

Discusses the amenability of the medial axis transform (MAT) or skeleton to processes at the intermediate level, which organize low-level primitives to entities on a semantically higher level (perceptual grouping). Several properties of the MAT assist the effective handling of proximity and adjacency relationships. The authors focus on the wealth of information contained in a specific implementation of the MAT on the raster grid, henceforth denoted as Voronoi skeleton.>

The system described is able to extract gripping information for a robot in most of the cases occurring in real life. For this step no individual object models were necessary. However, it was essential to use other general information on the objects like their symmetry properties. It was computationally advantageous to use contour information and not raster information. A method to deal with transparent and specularly reflecting objects is discussed.>

It is shown that the understanding of documents in general and of line drawings in particular can be seen as a first step towards the the understanding of arbitrary scenes by making effective use of methods from artificial intelligence. The starting point is a set of domain-independent linear image primitives which define a line graph. After the removal of artifacts the recognition of meaningful complex structures is accomplished in several steps with the aid of a growing amount of domain-specific knowledge. Further scene knowledge controls the deployment of the various operators to arrive at a consistent interpretation throughout the scene. The selection of the object-oriented programming paradigm proved to be very effective.>

Geometric objects such as polygons, line segments, and points may have manifold relations among each other, i.e., order, adjacency, connectivity, etc., and may be stored in a database. For the design of the spatial data structure and in order to preserve consistency when manipulating the data, we propose a graph grammar approach. All consistent states are described by a structure graph, and the manipulation rules are given by productions where intersection problems as well as topologic properties have to be solved. By appropriately modeling the behavior of geographic data, consistency is preserved at all times. This eliminates the tedious case of recovering a geographic database after an inconsistency has been detected.