Analysis of template matching thinning algorithms

摘要

Thinning, i.e. skeletonization and connectivity preservation, is an important operation being performed during low-level segmentation. Various template matching thinning algorithms have been proposed so far. No attempt has yet been made to conduct the average case analysis of these algorithms in order to measure their performance. In this paper a probabilistic model of average case analysis of template matching thinning algorithms is proposed. Using the proposed model of analysis a bound on the number of iterations required is computed and also the requirement of average time to complete the process of thinning of a uniformly distributed binary image in sequential as well as a parallel environment. Also a mathematical function is proposed to compute the number of cycles involved in the thinning process originated by a given algorithm.