Morphological skeleton representation and coding of binary images

Abstract-This paper presents the results of a study on the use of morphological set operations to represent and encode a discrete binary image by parts of its skeleton, a thinned version of the image contain-ing complete information about its shape and size. Using morphologi-cal erosions and openings, a finite image can be uniquely decomposed into a finite number of skeleton subsets and then the image can be ex-actly reconstructed by dilating the skeleton subsets. The morphological skeleton is shown to unify many previous approaches to skeletoniza-tion, and some of its theoretical properties are investigated. Fast al-gorithms that reduce the original qnadratic complexity to linear are developed for skeleton decomposition and reconstruction. Partial re-constructions of the image are quantified through the omission of sub-sets of skeleton points. The concepts of a globally and locally minimal skeleton are introduced and fast algorithms are developed for obtain-ing minimal skeletons. For images containing blobs and large areas, the skeleton subsets are much thinner than the original image. Therefore, encoding of the skeleton information results in loner information rates than optimum block-Huffman or optimum runlength-Huffman coding of the original image. The highest level of image compression was obtained by using Elias coding of the skeleton. I