Crust and Skeleton

From VoroWiki

Jump to: navigation, search
Enlarge
Enlarge
Enlarge

A concept closely associated with the VD is the medial axis transform (MAT), or "skeleton". This is a subset of the VD, and is usually applied to polygons -- each point on the MAT is equidistant to at least two edges of the polygon. The resulting graph may be used to classify the polygon shape (Blum, 1966[1]) -- for example in character recognition. This will be discussed further when we talk about using the line segment VD to form polygons. However, each boundary of a complex object may be approximated by multiple points, and the MAT constructed by throwing away the unwanted edges, as before. Thus boundary points taken from an image may be used to generate the Euclidean VD and thus the MAT, giving a kind of shape description, as before. The work of Ogniewicz shows several examples. Okabe et al. (2000)[2] shows a variety of examples of generating complex objects from point sets on the boundary.

One problem, however, is that it is not always easy to colour the black boundary pixels so that edges may be distinguished. In this case all input points to the VD will have the same colour, and no MAT will be produced. (In the work of Gold (1998) just described, vertices were coloured by flood-filling the individual polygons.)

Contents

Computing the crust and the skeleton

A brilliant recent paper (Amenta et al., 1998) suggests how a solution may be achieved using “Voronoi Filtering”. First generate the VD of the “black” boundary points, and extract the “red” Voronoï vertices. Construct a DT of both the black and red points, and throw away all triangle edges connecting black points to red points. If the original boundary was sufficiently well sampled then the original boundary points will be correctly connected. (Sufficiently well sampled was shown to be a function of the distance from the boundary to the MAT. It is usually easily achievable except at sharp corners.) Of interest to us here is that the MAT is also extracted. A useful terrestrial example is the extraction of approximate watershed boundaries from a scanned hydrological network - the MAT gives the watershed between watercourses. Of greater Marine interest would be the extraction of spatial clusters (of boats, fish...) using the same method. The boundaries of diffuse clusters are rarely distinct, but the MAT separating the clusters is often well defined.

Enlarge
Enlarge
Enlarge
Simple test to determine if an edge is part of the crust or if its dual edge is part of the skeleton.
Enlarge
Simple test to determine if an edge is part of the crust or if its dual edge is part of the skeleton.
Skeleton in blue and crust in red.
Enlarge
Skeleton in blue and crust in red.
Skeleton in blue and crust in red.
Enlarge
Skeleton in blue and crust in red.

One-step crust and skeleton extraction algorithm

Application examples

References

  1. Blum H, (1967) A transformation for extracting new descriptors of shape. In: Whaten Dunn W (ed), Models for the Perception of Speech and Visual Form. MIT Press, 153-171.
  2. Okabe, A.; Boots, B.; Sugihara, K. & Chiu, S.N. (2000), Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley and Sons.
Personal tools