Theory and application of the skeleton representation of continuous shapes

Shape representation is the means by which a planar region is specified in a computer. One particularly appealing choice of representation is the skeleton, which consists of the set of centers and radii of maximal disks contained in the shape. For most shapes, the skeleton is a graph that conveys the essential structure of the shape in a simplified manner. At the same time, it retains sufficient information to reconstruct the original shape.; In this thesis, we develop a new methodology for skeleton computation using a continuous-domain formulation. In order to accomplish this, we postulate the existence of underlying continuous shapes that have been sampled, and it is the underlying shapes for which we seek a representation. This is distinct from the traditional approach wherein the skeleton is transposed to the discrete domain and then applied to images. With this framework, we develop a new algorithm, based on the Voronoi diagram, that efficiently extracts a skeleton approximation from a finite boundary sampling. This continuous skeleton is substantially more useful for shape representation than its discrete-domain counterpart.; As an example of the usefulness of the new algorithm, we exploit the regular, predictable structure of the resulting skeleton to efficiently approximate and encode its constituent arcs. The result is a new compression algorithm for binary images, with the unique property that the reconstructed image degrades gracefully as compression is increased. As a second example of its broad applicability, we generalize the algorithm to three dimensions, and apply it to volume visualization and robotic path planning. The three-dimensional applications reveal the data structure as an excellent organizer of space, one which allows us to explore and map-out the reachable regions in a constricted space.; In summary, we have developed a new approach to skeleton computation. The approach is based on a fundamental relationship between the Voronoi diagram of a shape boundary and the skeleton of the shape. We are able to make practical use of this relationship by establishing continuity and convergence criteria, given finite approximations. The new approach holds considerable promise, as demonstrated by the applications and extensions explored herein.