New performance evaluation of parallel thinning algorithms based on PRAM and MPRAM models

The objective of thinning is to reduce the amount of information in image p atterns to the minimum needed for recognition. Thinned image helps the extr action of important features such as end points. junction points, and conne ctions from image patterns. The ultimate goal of parallel algorithms is to minimize the execution time while producing high quality thinned image. Tho ugh much research has been performed for parallel thinning algorithms, ther e has been no systematical approach for comparing the execution speed of pa rallel thinning algorithms. Several rough comparisons have been done in ter ms of iteration numbers. But, such comparisons may lead to wrong guides sin ce the time required for iterations varies from one algorithm to the other algorithm. This paper proposes a formal method to analyze the performance o f parallel thinning algorithms based on PRAM (Parallel Random Access Machin e) model. Besides, the quality of skeletons, robustness to boundary noise s ensitivity, and execution speed are considered. Six parallel algorithms, wh ich shows relatively high performance, are selected, and analyzed based on the proposed analysis method. Experiments show that the proposed analysis m ethod is sufficiently accurate to evaluate the performance of parallel thin ning algorithms.