K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Advantages and drawbacks of K3M. <s> Abstract Three new fast fully parallel 2-D thinning algorithms using reduction operators with 11-pixel supports are presented and evaluated. These are compared to earlier fully parallel thinning algorithms in tests on artificial and natural images; the new algorithms produce either superior parallel computation time (number of parallel iterations) or thinner medial curve results with comparable parallel computation time. Further, estimates of the best possible parallel computation time are developed which are applied to the specific test sets used. The parallel computation times of the new algorithms and one earlier algorithm are shown to approach closely or surpass these estimates and are in this sense near optimally fast. <s> BIB001 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Advantages and drawbacks of K3M. <s> Many algorithms for vectorization by thinning have been devised and applied to a great variety of pictures and drawings for data compression, pattern recognition and raster-to-vector conversion. But parallel thinning algorithms which generate one-pixel-wide skeletons can have difficulty preserving the connectivity of an image. In this paper, we propose a 2-subiteration parallel thinning algorithm with template matching (PTA2T) which preserves image connectivity, produces thinner results, maintains very fast speed and generates one-pixel-wide skeletons. <s> BIB002 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Advantages and drawbacks of K3M. <s> This paper presents a novel rule-based system for thinning. The unique feature that distinguishes our thinning system is that it thins symbols to their central lines. This means that the shape of the symbol is preserved. It also means that the method is rotation invariant. The system has 20 rules in its inference engine. These rules are applied simultaneously to each pixel in the image. Therefore, the system has the advantages of symmetrical thinning and speed. The results show that the system is very efficient in preserving the topology of symbols and letters written in any language. <s> BIB003
K3M has the following feasible advantages: BIB001 Zhang's BIB002 A-W BIB003 KMM K3M 1. The algorithm preserves right angles at the lines interconnections, which result in better correspondence between the original and the modified image. 2. It produces a one-pixel-wide skeleton. 3. The iterative phases are clearly aimed at deleting pixels in a specific neighbourhood, therefore a general idea of this thinning method is easily found. 4. The universality of the algorithm allows wide and diversified applications. Although the K3M algorithm has successfully proved its universal performance over many other algorithms, it is intrinsically iterative in nature, and hence it requires more computing power than other, non-iterative algorithms. Moreover, each iteration contains seven sequential phases. This increases the computational complexity and makes the parallelization attempts difficult. Despite the fact that these drawbacks do not affect the shape preservation, the authors are currently working on reducing the algorithm complexity and computational power requirements. The new results will be the matter of a future publication after proving their validity.