Skip to main content

An analysis of hexagonal thinning algorithms and skeletal shape representation

R C Staunton, School of Engineering, University of Warwick, CV4 7AL, UK

Pattern Recognition, vol 29, no. 7, 1996, 1131-1146.

Abstract

The use of skeletons or stick figures for binary image shape analysis, object classification, and coding has been widely reported in the literature. Tools using the nomenclature of mathematical morphology for defining skeletons and analyzing algorithms based on the iterative deletion of pixels have recently been developed, and are extended here to examine the processing of binary images sampled on a hexagonal grid of points. The properties of a skeleton in a hexagonal grid are defined and thinning templates designed. It is shown that, even when simple templates are used, some parallel application can be achieved. The analysis leads to the development of a new algorithm in which pairs of templates are applied in parallel resulting in accurate and efficient processing. Finally, the new algorithm is compared experimentally to a similar parallel algorithm designed for a conventional rectangular sampling grid. The hexagonal skeleton exhibited more accurate corner representation, limbs that enable the area of a rectangular shape to be estimated from the skeleton, noise immunity without preprocessing, and a processing time of 55% of that required to process the rectangular scheme skeleton.

Key Words} - Mathematical morphology, skeleton, thinning, shape analysis, text recognition, document scanning, hexagonal sampling, stick figure.