Gray skeletons and segmentation of shapes

Noise presents a major difficulty in implementing various methods of shape analysis currently in use. A way to deal with this problem is to presmooth shapes. However, this is problematic on several counts. It makes extensions to 3D shapes difficult. The shape may lack sufficiently many pixels in its narrow regions for computing high-order smoothing operators. How constructs such as shape skeletons are affected by smoothing is not at all clear. The objective of this paper is to demonstrate a new approach to shape analysis which does not require presmoothing of the shape. The basic tool is the “gray skeleton” which is the shape skeleton whose points are associated with significance numbers. A pruning method is developed for extracting a “noise-free” skeleton from the gray skeleton. The problem of segmenting shapes is addressed by formulating a segmetation functional in terms of gray skeletons. Fast algorithms for computing and pruning gray skeletons, and for finding an approximate minimum of the segmentation functional make the approach practical to implement.