Thinning methodologies−a comprehensive survey <s> I. INTRODUCTION N THE EARLY years of computer technology, it was <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> Thinning methodologies−a comprehensive survey <s> I. INTRODUCTION N THE EARLY years of computer technology, it was <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> Thinning methodologies−a comprehensive survey <s> I. INTRODUCTION N THE EARLY years of computer technology, it was <s> Abstract Most characters represent a blend of aspects which are essential to the embodiment of a given letter with aspects which embellish or adorn the essential aspects. In attempting to separate these two classes of aspects, it was found convenient to introduce a formal structure which is intermediate between the physical character and the abstract letter description. This formal structure was termed a skeleton. The letter-skeletal and skeletal-character links are presented followed by an example wherein one begins with an abstract letter description, proceeds to formulate a skeleton, and finally generates a character. The relations and applications of this work to the fields of character recognition and character generation, particularly where multiple fonts are involved, are also discussed. <s> BIB003 </s> Thinning methodologies−a comprehensive survey <s> I. INTRODUCTION N THE EARLY years of computer technology, it was <s> Abstract A set of “logical pixel logic” based procedures is described and illustrated for detecting the near-minimal number of pixels on a perfectly 8- or 6-connected binary thin line which have to be retained to adequately approximate the original pixel string with a connected sequence of straight-line segments. The found critical points or pixels on the line are for practical purposes the same as those chosen by a person, were he asked to perform the same task. The method is fast and in practically all cases the approximating connected sequence of straight-line segments does not deviate by more than one pixel distance from the original pixel string. Experiments on Chinese characters have given very good results. The method could also be used as a preprocessing step to conventional iterative methods based on minimizing a distance criterion between the approximating straight-line segments and the pixels on the original binary line. It will be very useful in any field in which computational speed is one of the major concerns, such as industrial vision systems. <s> BIB004 </s> Thinning methodologies−a comprehensive survey <s> I. INTRODUCTION N THE EARLY years of computer technology, it was <s> Abstract This paper presents an algorithm for thinning digital binary patterns (skeletonization). The algorithm consists of two phases. The first phase thins the input pattern to unit thickness by alternately smoothing of the pattern and stripping of the contour points. The second phase adjusts the resulting skeleton from phase one so that a medial skeleton can be obtained. The performance of this algorithm is first compared experimentally with recent results of two other research groups and then with nine other skeletonization algorithms proposed by other researchers. Results show that the alternate smoothing and stripping algorithm produces skeletons which are smooth and with least distortion and well-formed than the others. <s> BIB005 </s> Thinning methodologies−a comprehensive survey <s> I. INTRODUCTION N THE EARLY years of computer technology, it was <s> This paper presents a new algorithm to compute skeletons of noisy images of objects which can be described as ``amorphous blobs.'' Such a requirement arose from our research to obtain a better understanding of the role of the pseudopod in leukocyte locomotion. It involves the modeling and detection of pseudopods which are by their nature nonrigid bodies appearing on the cell's surface membrane. By computing skeletons at different resolutions, a filtered version can be produced without violating the constraints imposed by the semantic knowledge of pseudopod morphology. The filtered version incorporates all the significant ``events'' that occur at the different resolutions. The resolution at which the shape is examined is related to the degree of smoothing, in that the lower the resolution gets, the higher the degree of smoothing. Skeleton branches that persist over several scales arise from convexities that are locally as well as globally significant. Their stability is related to their perceptual significance. Our approach is to combine an initial region centered description (skeleton) with a boundary analysis executed at different resolutions. Having computed the skeleton at different scales, we then use those computed at the lower resolutions as a measure of how global the underlying convexity is. Clearly the skeletons computed at higher resolutions represent the exact location and orientation of the underlying convexities. <s> BIB006
I realized that machine recognition of patterns was a possibility, and together with this arose the need for reducing the amount of information to be processed to the minimum necessary for the recognition of such patterns. It seems that the earliest experiments in data compression were conducted on character patterns in the 1950's. In BIB001 , it was found that an averaging operation over a square window with a high threshold resulted in a thinning of the input image, and in BIB002 , the "custer" operation was an early attempt to obtain a thinline representation of certain character patterns. The thinned characters were used for recognition in [107] ,  , and  . This practice has been widely used since then (for example, [18] , (1171, [67] , [121] , and [69] ), and integrated circuits have been designed for this purpose [96] . During these years, many algorithms for data compression by thinning have been devised and applied to a great variety of patterns for different purposes. In the biomedical field, this technique was found to be useful in the early 1960's, when a "shrink" algorithm was applied to count and size the constituent parts of white blood cells in order to identify abnormal cells  , [94] . Since that time, applications in Manuscript received August 6, 1990; revised June 21, 1991. S. -W. Lee is with the Department of Computer Science, Chungbuk National University, Cheongju, Chungbuk, Korea. IEEE Log Number 9201772. this area have included analyses of white blood cells BIB006 and chromosomes [51] ,  , automatic X-ray image analysis [95] , and analysis of coronary arteries [81] . In other sectors, thinned images have found applications in the processing of bubble-chamber negatives [73] , the visual system of an automaton  , fingerprint classification [74] , quantitative metallography [68] , measurements of soil cracking patterns [83] , and automatic visual analyses of industrial parts [75] and printed circuit boards [133] . This wide range of applications shows the usefulness of reducing patterns to thin-line representations, which can be attributed to the need to process a reduced amount of data as well as to the fact that shape analysis can be more easily made on line-like patterns. The thin-line representation of certain elongated patterns, for example, characters, would be closer to the human conception of these patterns; therefore, they permit a simpler structural analysis and more intuitive design of recognition algorithms. For example, a partially abstract, graph-like skeleton has been considered to be a link between the abstract description of a letter and its physical representation as a character BIB003 . In addition, the reduction of an image to its essentials can eliminate some contour distortions while retaining significant topological and geometric properties. In more practical terms, thin-line representations of elongated patterns would be more amenable to extraction of critical features such as end points, junction points, and connections among the components (e.g., see BIB004 ), whereas vectorization algorithms often used in pattern recognition tasks also require one-pixel-wide lines as input. Naturally, for a thinning algorithm to be really effective, it should ideally compress data, retain significant features of the pattern, and eliminate local noise without introducing distortions of its own. To accomplish all that using the simplest and fastest algorithm is the challenge involved. Perhaps as a result of its central role in the preprocessing of data images or perhaps because of its intrinsic appeal, the design of thinning or skeletonization algorithms has been a very active research area. About 300 articles have been published on various aspects of this subject since its inception; therefore, it is felt that a comprehensive survey of this area is due. There have been other comparisons and survey articles in the field ([120] , [53] , [30] , [lll] ), and some authors have included comparisons with other results in their publications (for example, [122] , [77] , BIB005 , and [24] ). The aim here is to collect most (if not all) of the articles in this field published in English, to classify and discuss them according to the methodologies employed, and to include areas not usually covered in the other surveys-morphologica1 skeletonization, 3-D skeletonization, and grey-scale thinning. All of these will 0162-8828/92$03.00 0 1992 IEEE I IEEE TRANSACTIONS ON PATERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 14, NO. 9, SEPTEMBER 1992 be discussed under a consistent set of terminologies (where variations will be mentioned) in the hope that such a unified treatment would be helpful. This article is organized as follows. Section I1 contains an overview of the thinning process and pixel deleting criteria. In Sections I11 and IV, sequential and parallel thinning algorithms, respectively, will be discussed, whereas the noniterative nonpixel-based methods will be considered in Section V. This article will conclude with some observations and remarks in Section VI. In a separate follow-up article, we will consider medial axis and other distance transforms, extensions of thinning algorithms to 3-D and grey-scale images, and we will include a brief discussion of morphological skeletonization.