K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Introduction <s> Everyone likes to speculate, and recently there has been a lot of talk about reading machines and hearing machines. We know it is possible to simulate speech. This raises lots of interesting questions such as: If the machines can speak, will they squawk when you ask them to divide by zero? And can two machines carry on an intelligent conversation, say in Gaelic? And, of course, there is the expression "electronic brain" and the question, Do machines think? These questions are more philosophical than technical and I am going to duck them. <s> BIB001 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Introduction <s> In almost all digital data processing machine applications, the input data made available to the machine are the result of some prior processing. This processing is done manually in many applications. Thus, such inputs as punched cards, magnetic tape, and punched paper tape often are the result of a manual processing operation in which a human being is required to inspect visually an array of printed characters and to describe these data in a form capable of being processed by machine. In recognition of the importance of automating such operations, many investigations have been undertaken to devise automatic character sensing equipment. Suppose, however, that we attempt to view such efforts in proper perspective. We find a more fundamental problem that has, heretofore, failed to receive the attention that it warrants. The problem is one of making directly available to a computer pictorial information which would ordinarily be visually processed by human beings before being fed to a data processing system. This pictorial information may range from such highly stylized forms as printed characters, diagrams, schematic drawings, emblems, and designs through less stylized forms in cartoons and handwritten characters to such highly amorphous forms as photographs of real objects, e.g., people, aerial views, and microscopic and telescopic images. <s> BIB002 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Introduction <s> A one-pass parallel thinning algorithm based on a number of criteria, including connectivity, unit-width convergence, medial axis approximation, noise immunity, and efficiency, is proposed. A pipeline processing model is assumed for the development. Precise analysis of the thinning process is presented to show its properties, and proofs of skeletal connectivity and convergence are provided. The proposed algorithm is further extended to the derived-grid to attain an isotropic medial axis representation. A set of measures based on the desired properties of thinning is used for quantitative evaluation of various algorithms. Image reconstruction from connected skeletons is also discussed. Evaluation shows that the procedures compare favorably to others. > <s> BIB003 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Introduction <s> A comprehensive survey of thinning methodologies is presented. A wide range of thinning algorithms, including iterative deletion of pixels and nonpixel-based methods, is covered. Skeletonization algorithms based on medial axis and other distance transforms are not considered. An overview of the iterative thinning process and the pixel-deletion criteria needed to preserve the connectivity of the image pattern is given first. Thinning algorithms are then considered in terms of these criteria and their modes of operation. Nonpixel-based methods that usually produce a center line of the pattern directly in one pass without examining all the individual pixels are discussed. The algorithms are considered in great detail and scope, and the relationships among them are explored. > <s> BIB004 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> Introduction <s> Thinning algorithms are an important sub-component in the construction of computer vision (especially for optical character recognition (OCR)) systems. Important criteria for the choice of a thinning algorithm include the sensitivity of the algorithms to input shape complexity and to the amount of noise. In previous work, we introduced a methodology to quantitatively analyse the performance of thinning algorithms. The methodology uses an ideal world model for thinning based on the concept of Blum ribbons. In this paper we extend upon this methodology to answer these and other experimental questions of interest. We contaminate the noise-free images using a noise model that simulates the degradation introduced by the process of xerographic copying and laser printing. We then design experiments that study how each of 16 popular thinning algorithms performs relative to the Blum ribbon gold standard and relative to itself as the amount of noise varies. We design statistical data analysis procedures for various performance comparisons. We present the results obtained from these comparisons and a discussion of their implications in this paper. > <s> BIB005
As a digital image processing technique, thinning has been around for many years. Thinning (also termed skeletonization) is an image pre-processing technique that is important in a number of applications like pattern recognition, data compression and data storage  . The history of thinning covers over fifty years. In the 1950s BIB001 found that an averaging operation over a square window with a high threshold resulted in a thinning of the input image. Then BIB002 mentioned that the "custer" operation was an early attempt to obtain a thinline representation of certain character patterns. However, still there is no ultimate solution suitable for each individual area of application BIB005 BIB003 BIB004  . This is due to the complicated nature of the processing as well as various evaluation measures that should be considered. There are more than one thousand algorithms that have been published on this topic. The thinning algorithms mentioned in this paper have been selected from among the best known published works. These selected works are given here for comparison to show and evaluate the efforts of other researchers and authors in working out and implementing a number of algorithms and approaches for a variety of applications. The first trials conducted in this field by the authors of this paper date back to 1999  . This was to aid recognition algorithms of cursive-character letters, which required thinning before classification. This work is an attempt to propose a new criterion and employ it to various applications. The presented method leads to a fast recognition algorithm of both typewritten and handwritten texts with the possibility of applying it to thin images of a variety of objects. The basic idea of thinning according to this approach lies in the generation of a skeleton with a one-pixel width. However, to serve more complicated cases, some modifications have been made to the whole criterion. The method suggested by the authors is universal and simple. It consists of several fast and easy-to-implement deleting phases. The obtained experimental results have also shown a successful application of the method in image pre-processing as well as image preparation for feature extraction and classification. The method proved its universality-not only does it work for printed words, but it has also shown a remarkable success rate on thinning handwritten scripts, signatures, numbers, characters of non-Latin-based alphabets (Arabic, Japanese) and even biometric images such as faces or fingerprints. The paper is organized as follows. Section 2 presents the state of the art in the following order: the proposed taxonomy of thinning algorithms, a description of general ideas of the most significant ones and a short comparison in terms of efficiency. Section 3 presents the thinning algorithm proposed by the authors in detail. Section 4 presents the results of the K3M algorithm and the comparison with other algorithms. Section 5 describes the concepts for the parallelization of intrinsically sequential thinning algorithms. Finally, Section 6 concludes the work and shows perspectives for future development.