Analysis of thinning algorithms using mathematical morphology

Abstract

A precise definition of digital skeletons and a mathematical framework for the analysis of a class of thinning algorithms, based on morphological set transformation, are presented. A particular thinning algorithm (algorithm A) is used as an example in the analysis. Precise definitions and analyses associated with the thinning process are presented, including the proof of convergence, the condition for one-pixel-thick skeletons, and the connectedness of skeletons. In addition, a necessary and sufficient condition for the thinning process in general is derived, and an algorithm (algorithm B) based on this condition is developed. Experimental results are used to compare the two thinning algorithms, and issues involving noise immunity and skeletal bias are addressed. Although both algorithm A and algorithm B generate connected and one-pixel-thick skeletons, algorithm B generates skeletons which follow their medial axes closely. Both produce noisy skeletons if the original objects contain noisy boundaries. This problem has been dealt with by using trimming templates at each pass in parallel with the thinning operation; however, skeletal legs are no longer preserved.