K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Elongated black objects in black-and-white pictures can be ``thinned'' to arcs and curves, without changing their connectedness, by (repeatedly) deleting black border points whose deletion does not locally disconnect the black points in their neighborhoods. This technique generalizes to gray-scale pictures if we use a weighted definition of connectedness: two points are ``connected'' if there is a path joining them on which no point is lighter than either of them. We can then ``thin'' dark objects by changing each point's gray level to the minimum of its neighbors' gray levels, provided this does not disconnect any pair of points in its neighborhood. Examples illustrating the performance of this technique are given. <s> BIB001 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> The paper discusses thinning algorithms and introduces a characterization of skeletal pixels in terms of how many arcs of the boundary pass through a pixel. A new algorithm is proposed which proceeds by peeling off successive contours of the set to be thinned while identifying pixels where disjoint parts of the boundary have been mapped. The union of these pixels (plus a few others with similar properties) forms the skeleton. The algorithm can be implemented in such a way as to have time complexity which is a linear function of the area. <s> BIB002 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract The possibility of applying thinning algorithms to digital figures not already nearly thin is discussed in the framework of using contour tracing to inspect the pixels currently candidates for removal. The proposed algorithm takes advantage of this approach both to reduce the computation time needed to obtain the skeleton and to perform contour analysis in order to find the contour regions to be represented by the skeleton branches. Since different contour descriptions can be found, various skeleton structures can alternatively be generated depending on the requirements of the problem domain. The skeleton found may also be regarded as a discrete version of that obtained by using the medial axis transformation. <s> BIB003 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract Binary pictures are taken into account and an algorithm which transforms a digital figure into a set of 8-simple digital arcs and curves, by employing local sequential operations, il illustrated. The adopted procedure considers the removal of suitable contour elements of the given figure and it is repeated on every current set of 1-elements as long as the final thinned figure is obtained. The notion of local elongation is employed to find, at every step of the process, those contour regions which can be regarded as significant protrusions. Then such regions are detected before applying the removal operations, contributing hence to the isotropic behavior of the proposed thinning transformation. Further refinements of the algorithm are also discussed. <s> BIB004 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> 1: Introduction.- 1.1 Graphics, Image Processing, and Pattern Recognition.- 1.2 Forms of Pictorial Data.- 1.2.1 Class 1: Full Gray Scale and Color Pictures.- 1.2.2 Class 2: Bilevel or "Few Color" pictures.- 1.2.3 Class 3: Continuous Curves and Lines.- 1.2.4 Class 4: Points or Polygons.- 1.3 Pictorial Input.- 1.4 Display Devices.- 1.5 Vector Graphics.- 1.6 Raster Graphics.- 1.7 Common Primitive Graphic Instructions.- 1.8 Comparison of Vector and Raster Graphics.- 1.9 Pictorial Editor.- 1.10 Pictorial Transformations.- 1.11 Algorithm Notation.- 1.12 A Few Words on Complexity.- 1.13 Bibliographical Notes.- 1.14 Relevant Literature.- 1.15 Problems.- 2: Digitization of Gray Scale Images.- 2.1 Introduction.- 2.2 A Review of Fourier and other Transforms.- 2.3 Sampling.- 2.3.1 One-dimensional Sampling.- 2.3.2 Two-dimensional Sampling.- 2.4 Aliasing.- 2.5 Quantization.- 2.6 Bibliographical Notes.- 2.7 Relevant Literature.- 2.8 Problems.- Appendix 2.A: Fast Fourier Transform.- 3: Processing of Gray Scale Images.- 3.1 Introduction.- 3.2 Histogram and Histogram Equalization.- 3.3 Co-occurrence Matrices.- 3.4 Linear Image Filtering.- 3.5 Nonlinear Image Filtering.- 3.5.1 Directional Filters.- 3.5.2 Two-part Filters.- 3.5.3 Functional Approximation Filters.- 3.6 Bibliographical Notes.- 3.7 Relevant Literature.- 3.8 Problems.- 4: Segmentation.- 4.1 Introduction.- 4.2 Thresholding.- 4.3 Edge Detection.- 4.4 Segmentation by Region Growing.- 4.4.1 Segmentation by Average Brightness Level.- 4.4.2 Other Uniformity Criteria.- 4.5 Bibliographical Notes.- 4.6 Relevant Literature.- 4.7 Problems.- 5: Projections.- 5.1 Introduction.- 5.2 Introduction to Reconstruction Techniques.- 5.3 A Class of Reconstruction Algorithms.- 5.4 Projections for Shape Analysis.- 5.5 Bibliographical Notes.- 5.6 Relevant Literature.- 5.7 Problems.- Appendix 5.A: An Elementary Reconstruction Program.- 6: Data Structures.- 6.1 Introduction.- 6.2 Graph Traversal Algorithms.- 6.3 Paging.- 6.4 Pyramids or Quad Trees.- 6.4.1 Creating a Quad Tree.- 6.4.2 Reconstructing an Image from a Quad Tree.- 6.4.3 Image Compaction with a Quad Tree.- 6.5 Binary Image Trees.- 6.6 Split-and-Merge Algorithms.- 6.7 Line Encodings and the Line Adjacency Graph.- 6.8 Region Encodings and the Region Adjacency Graph.- 6.9 Iconic Representations.- 6.10 Data Structures for Displays.- 6.11 Bibliographical Notes.- 6.12 Relevant Literature.- 6.13 Problems.- Appendix 6.A: Introduction to Graphs.- 7: Bilevel Pictures.- 7.1 Introduction.- 7.2 Sampling and Topology.- 7.3 Elements of Discrete Geometry.- 7.4 A Sampling Theorem for Class 2 Pictures.- 7.5 Contour Tracing.- 7.5.1 Tracing of a Single Contour.- 7.5.2 Traversal of All the Contours of a Region.- 7.6 Curves and Lines on a Discrete Grid.- 7.6.1 When a Set of Pixels is not a Curve.- 7.6.2 When a Set of Pixels is a Curve.- 7.7 Multiple Pixels.- 7.8 An Introduction to Shape Analysis.- 7.9 Bibliographical Notes.- 7.10 Relevant Literature.- 7.11 Problems.- 8: Contour Filling.- 8.1 Introduction.- 8.2 Edge Filling.- 8.3 Contour Filling by Parity Check.- 8.3.1 Proof of Correctness of Algorithm 8.3.- 8.3.2 Implementation of a Parity Check Algorithm.- 8.4 Contour Filling by Connectivity.- 8.4.1 Recursive Connectivity Filling.- 8.4.2 Nonrecursive Connectivity Filling.- 8.4.3 Procedures used for Connectivity Filling.- 8.4.4 Description of the Main Algorithm.- 8.5 Comparisons and Combinations.- 8.6 Bibliographical Notes.- 8.7 Relevant Literature.- 8.8 Problems.- 9: Thinning Algorithms.- 9.1 Introduction.- 9.2 Classical Thinning Algorithms.- 9.3 Asynchronous Thinning Algorithms.- 9.4 Implementation of an Asynchronous Thinning Algorithm.- 9.5 A Quick Thinning Algorithm.- 9.6 Structural Shape Analysis.- 9.7 Transformation of Bilevel Images into Line Drawings.- 9.8 Bibliographical Notes.- 9.9 Relevant Literature.- 9.10 Problems.- 10: Curve Fitting and Curve Displaying.- 10.1 Introduction.- 10.2 Polynomial Interpolation.- 10.3 Bezier Polynomials.- 10.4 Computation of Bezier Polynomials.- 10.5 Some Properties of Bezier Polynomials.- 10.6 Circular Arcs.- 10.7 Display of Lines and Curves.- 10.7.1 Display of Curves through Differential Equations.- 10.7.2 Effect of Round-off Errors in Displays.- 10.8 A Point Editor.- 10.8.1 A Data Structure for a Point Editor.- 10.8.2 Input and Output for a Point Editor.- 10.9 Bibliographical Notes.- 10.10 Relevant Literature.- 10.11 Problems.- 11: Curve Fitting with Splines.- 11.1 Introduction.- 11.2 Fundamental Definitions.- 11.3 B-Splines.- 11.4 Computation with B-Splines.- 11.5 Interpolating B-Splines.- 11.6 B-Splines in Graphics.- 11.7 Shape Description and B-splines.- 11.8 Bibliographical Notes.- 11.9 Relevant Literature.- 11.10 Problems.- 12: Approximation of Curves.- 12.1 Introduction.- 12.2 Integral Square Error Approximation.- 12.3 Approximation Using B-Splines.- 12.4 Approximation by Splines with Variable Breakpoints.- 12.5 Polygonal Approximations.- 12.5.1 A Suboptimal Line Fitting Algorithm.- 12.5.2 A Simple Polygon Fitting Algorithm.- 12.5.3 Properties of Algorithm 12.2.- 12.6 Applications of Curve Approximation in Graphics.- 12.6.1 Handling of Groups of Points by a Point Editor.- 12.6.2 Finding Some Simple Approximating Curves.- 12.7 Bibliographical Notes.- 12.8 Relevant Literature.- 12.9 Problems.- 13: Surface Fitting and Surface Displaying.- 13.1 Introduction.- 13.2 Some Simple Properties of Surfaces.- 13.3 Singular Points of a Surface.- 13.4 Linear and Bilinear Interpolating Surface Patches.- 13.5 Lofted Surfaces.- 13.6 Coons Surfaces.- 13.7 Guided Surfaces.- 13.7.1 Bezier Surfaces.- 13.7.2 B-Spline Surfaces.- 13.8 The Choice of a Surface Partition.- 13.9 Display of Surfaces and Shading.- 13.10 Bibliographical Notes.- 13.11 Relevant Literature.- 13.12 Problems.- 14: The Mathematics of Two-Dimensional Graphics.- 14.1 Introduction.- 14.2 Two-Dimensional Transformations.- 14.3 Homogeneous Coordinates.- 14.3.1 Equation of a Line Defined by Two Points.- 14.3.2 Coordinates of a Point Defined as the Intersection of Two Lines.- 14.3.3 Duality.- 14.4 Line Segment Problems.- 14.4.1 Position of a Point with respect to a Line.- 14.4.2 Intersection of Line Segments.- 14.4.3 Position of a Point with respect to a Polygon.- 14.4.4 Segment Shadow.- 14.5 Bibliographical Notes.- 14.6 Relevant Literature.- 14.7 Problems.- 15: Polygon Clipping.- 15.1 Introduction.- 15.2 Clipping a Line Segment by a Convex Polygon.- 15.3 Clipping a Line Segment by a Regular Rectangle.- 15.4 Clipping an Arbitrary Polygon by a Line.- 15.5 Intersection of Two Polygons.- 15.6 Efficient Polygon Intersection.- 15.7 Bibliographical Notes.- 15.8 Relevant Literature.- 15.9 Problems.- 16: The Mathematics of Three-Dimensional Graphics.- 16.1 Introduction.- 16.2 Homogeneous Coordinates.- 16.2.1 Position of a Point with respect to a Plane.- 16.2.2 Intersection of Triangles.- 16.3 Three-Dimensional Transformations.- 16.3.1 Mathematical Preliminaries.- 16.3.2 Rotation around an Axis through the Origin.- 16.4 Orthogonal Projections.- 16.5 Perspective Projections.- 16.6 Bibliographical Notes.- 16.7 Relevant Literature.- 16.8 Problems.- 17: Creating Three-Dimensional Graphic Displays.- 17.1 Introduction.- 17.2 The Hidden Line and Hidden Surface Problems.- 17.2.1 Surface Shadow.- 17.2.2 Approaches to the Visibility Problem.- 17.2.3 Single Convex Object Visibility.- 17.3 A Quad Tree Visibility Algorithm.- 17.4 A Raster Line Scan Visibility Algorithm.- 17.5 Coherence.- 17.6 Nonlinear Object Descriptions.- 17.7 Making a Natural Looking Display.- 17.8 Bibliographical Notes.- 17.9 Relevant Literature.- 17.10 Problems.- Author Index.- Algorithm Index. <s> BIB005 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract A problem common to many areas of pictorial information processing is the transformation of a bilevel (two-color) image into a line drawing. The first step in such a process is discussed: transformation of the bilevel image into another bilevel image that is “thin.” An algorithm is proposed that can be implemented in either parallel or sequential fashion, and therefore is suitable for a mixed operation where a group of processors operate in parallel with each one examining sequentially the pixels of a part of the image assigned to it. It is possible to process images in pieces and thin correctly parts that are intersected by the dividing lines. Therefore, the method can be used on large images, such as maps and engineering drawings. The algorithm may also be run with certain options that label the thinned image so that exact reconstruction of the original is possible. <s> BIB006 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract In recoding with three bits the pixels of objects in binary images according to some measure of distance to the background, parallel thinning is achieved using syntactic rules. The codes in a 3 × 2 window are searched for interrelations which determine the new code of the central pixel. The local structure of the codes is determined through a binary cascade of tables. To each structure corresponds a rewriting rule. The new code is the output of the cascade. A two-scan postprocessing is needed to obtain a skeleton with linear structure. <s> BIB007 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract A fast thinning algorithm is proposed which achieves its increase in speed by applying any existing thinning algorithm to a greatly reduced amount of image information. The procedure compacts the image, applies an optimal thresholding routine, thins the result, and then expands the skeleton to its original scale. Results of testing the algorithm on a number of images are shown. <s> BIB008 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract The characterization of a digital figure in terms of the multiple pixels, i.e., the pixels placed where the contour selfinteracts, can provide useful shape cues. These pixels can satisfactorily be detected if a suitable definition of contour simplicity is available. Such a definition is given in this paper, for the case of multiply connected figures. The multiple pixels are those where the contour fails to be simple, and they can be identified by using 3 × 3 local operations. <s> BIB009 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract A line following algorithm is presented as a means to perform line thinning on elongated figures. The method is faster than conventional thinning algorithms and not as sensitive to noise. It can be useful for other applications also. <s> BIB010 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Abstract This paper describes a systematic approach for designing parallel thinning algorithms, in which three new functions, named local connecting, extended local connecting and erosive direction number, are introduced. With these functions as well as two properties of shape invariance of local edges and local straight lines, all the possible cases of 2-subcycle parallel thinning algorithm are constructed and all the corresponding removing conditions are generated and assigned automatically. In addition, the pseudo 1-subcycle parallel thinning algorithm is also presented. Finally, the effects and efficiency of the above proposed algorithms are analyzed and compared with those of some presently well-known algorithms. Experimental results confirm this new approach, and an efficient and effective algorithm has been built for practical applications. <s> BIB011 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Multiresolution representations are effective for analyzing the information content of images. The properties of the operator which approximates a signal at a given resolution were studied. It is shown that the difference of information between the approximation of a signal at the resolutions 2/sup j+1/ and 2/sup j/ (where j is an integer) can be extracted by decomposing this signal on a wavelet orthonormal basis of L/sup 2/(R/sup n/), the vector space of measurable, square-integrable n-dimensional functions. In L/sup 2/(R), a wavelet orthonormal basis is a family of functions which is built by dilating and translating a unique function psi (x). This decomposition defines an orthogonal multiresolution representation called a wavelet representation. It is computed with a pyramidal algorithm based on convolutions with quadrature mirror filters. Wavelet representation lies between the spatial and Fourier domains. For images, the wavelet representation differentiates several spatial orientations. The application of this representation to data compression in image coding, texture discrimination and fractal analysis is discussed. > <s> BIB012 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <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> BIB013 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Bias skeletons yielded by thinning patterns which usually degrade the preservation of significant geometric features of patterns are addressed in this paper. Based on the considerable performance of our pseudo 1-subcycle parallel thinning algorithm, we continuously adopt it to develop an intermediate vector analysis about the removed pixels in each normal iteration to obtain bias-reduced skeletons. The hidden deletable pixel which is a major factor to yield bias skeletons is newly defined and can be detected by the presented algorithms of vector analysis. <s> BIB014 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <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> BIB015 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> The authors propose a thinning algorithm based on clustering the image data. They employ the ART2 network which is a self-organizing neural network for the clustering of Arabic characters. The skeleton is generated by plotting the cluster centers and connecting adjacent clusters by straight lines. This algorithm produces skeletons which are superior to the outputs of the conventional algorithms. It achieves a higher data-reduction efficiency and much simpler skeletons with less noise spurs. Moreover, to make the algorithm appropriate for real-time applications, an optimization technique is developed to reduce the time complexity of the algorithm. The developed algorithm is not limited to Arabic characters, and it can also be used to skeletonize characters of other languages. <s> BIB016 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> In this paper a new morphological technique suitable for colour image skeleton extraction is presented. Vector morphological operations are defined by means of a new ordering of vectors of the HSV colour space, which is a combination of conditional and partial sub-ordering. Then, these are used to extract skeletons of colour images in terms of erosions and openings. The proposed method was tested with a variety of images and such experimental results are provided. Its applications include image compression and recognition problems. <s> BIB017 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> This paper is a continuation to the work in [1], in which a new algorithm for skeletonization is introduced. The algorithm given there and implemented for script and text is applied here on images like pictures, medical organs and signatures. This is very important for a lot of applications in pattern recognition, like, for example, data compression, transmission or saving. Some interesting results have been obtained and presented in this article. Comparing our results with others we can conclude that if it comes to thinning of scripts, words or sentences our method is as good as some of the latest approaches, when considering cursive script. However, when it comes to pictures, signatures or other more complicated images, our algorithm showed better and more precise results [6]. <s> BIB018 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <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> BIB019 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> This paper proposes a new algorithm to generate a disconnected, three-dimensional (3D) skeleton and an application of such a skeleton to generate a finite element (FE) mesh sizing function of a solid. The mesh sizing function controls the element size and the gradient, and it is crucial in generating a desired FE mesh. Here, a geometry-based mesh sizing function is generated using a skeleton. A discrete skeleton is generated by propagating a wave from the boundary towards the interior on an octree lattice of an input solid model. As the wave propagates, the distance from the boundary and direction of the wave front are calculated at the lattice-nodes (vertices) of the new front. An approximate Euclidean distance metric is used to calculate the distance traveled by the wave. Skeleton points are generated at the region where the opposing fronts meet. The distance at these skeleton points is used to measure both proximity between geometric entities and feature size, and is utilized to generate the mesh size at the lattice-nodes. The proposed octree-based skeleton is more accurate and efficient than traditional voxel-based skeleton and proves to be great tool for mesh sizing function generation. <s> BIB020 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Ahmed and Ward [Sept. 1995] have recently presented an elegant, rule-based rotation-invariant thinning algorithm to produce a single-pixel wide skeleton from a binary image. We show examples where this algorithm fails on two-pixel wide lines and propose a modified method which corrects this shortcoming based on graph connectivity. <s> BIB021 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> This paper describes two approaches to approximation of handwriting strokes for use in writer identification. One approach is based on a thinning method and produces raster skeleton whereas the other approximates handwriting strokes by cubic splines and produces a vector skeleton. The vector skeletonisation method is designed to preserve the individual features that can distinguish one writer from another. Extraction of structural character-level features of handwriting is performed using both skeletonisation methods and the results are compared. Use of the vector skeletonisation method resulted in lower error rate during the feature extraction stage. It also enabled to extract more structural features and improved the accuracy of writer identification from 78% to 98% in the experiment with 100 samples of grapheme "th" collected from 20 writers. <s> BIB022 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Skeletons are important shape descriptors in object representation and recognition. Typically, skeletons of volumetric models are computed via an iterative thinning process. However, traditional thinning methods often generate skeletons with complex structures that are unsuitable for shape description, and appropriate pruning methods are lacking. In this paper, we present a new method for computing skeletons on volumes by alternating thinning and a novel skeleton pruning routine. Our method creates a family of skeletons parameterized by two user-specified numbers that determine respectively the size of curve and surface features on the skeleton. As demonstrated on both real-world models and medical images, our method generates skeletons with simple and meaningful structures that are particularly suitable for describing cylindrical and plate-like shapes. <s> BIB023 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> Character skeleton plays a significant role in character recognition. The strokes of a character may consist of two regions, i.e., singular and regular regions. The intersections and junctions of the strokes belong to singular region, while the straight and smooth parts of the strokes are categorized to regular region. Therefore, a skeletonization method requires two different processes to treat the skeletons in theses two different regions. All traditional skeletonization algorithms are based on the symmetry analysis technique. The major problems of these methods are as follows. 1) The computation of the primary skeleton in the regular region is indirect, so that its implementation is sophisticated and costly. 2) The extracted skeleton cannot be exactly located on the central line of the stroke. 3) The captured skeleton in the singular region may be distorted by artifacts and branches. To overcome these problems, a novel scheme of extracting the skeleton of character based on wavelet transform is presented in this paper. This scheme consists of two main steps, namely: a) extraction of primary skeleton in the regular region and b) amendment processing of the primary skeletons and connection of them in the singular region. A direct technique is used in the first step, where a new wavelet-based symmetry analysis is developed for finding the central line of the stroke directly. A novel method called smooth interpolation is designed in the second step, where a smooth operation is applied to the primary skeleton, and, thereafter, the interpolation compensation technique is proposed to link the primary skeleton, so that the skeleton in the singular region can be produced. Experiments are conducted and positive results are achieved, which show that the proposed skeletonization scheme is applicable to not only binary image but also gray-level image, and the skeleton is robust against noise and affine transform <s> BIB024 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> The conversion of two-dimensional objects into a skeletal representation is a fundamental calculation in image processing and pattern recognition, because topological structures of objects can be preserved in the skeleton. For the purpose of shaped fiber recognition, the number of shaped fiberpsilas branches is necessary to be calculated. In this paper, a skeletonization algorithm is proposed, in which the fiberpsilas topology information is well preserved. The algorithm also shows good noise tolerance. At the end of this paper, the experimental results of shaped fiber recognition based on proposed algorithm are given. <s> BIB025 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> General ideas and examples. <s> This paper describes an improved thinning algorithmfor binary images. We improve thinning algorithm fromthe fundamental properties such as connectivity, one-pixelwidth, robust to noise and speed. In addition, inorder to overcome information loss, we integrated thecontour and skeleton of pattern and proposed thethreshold way. Some fundamental requirements ofthinning and the shape of pattern are preserved very well.Algorithm is very robust to noise and eliminate somespurious branch. Above all, it can overcome the loss ofinformation in pattern. Experimental results show theperformance of the proposed algorithm. <s> BIB026
In this section a detailed description of most of the basic algorithms of thinning is presented in order to show how others attack the problem of skeletonization. Some of them are explained in detail in  .  proposed a parallel algorithm that formed a basis for many thinning algorithms. Image pixels are examined for deletion in an iterative process (not divided into subcycles). Contour pixels with at least two black neighbours, and where all its neighbours are 4-connected (sticking together with its edge), are marked for deletion. This may result in excessive erosion, it does not reduce diagonal lines to a unit pixel width and the skeleton is not located centrally (due to the asymmetric nature of its conditions).  presented skeletonization as transformation for the aim of shape description. He called this transformation MAT-Medial Axis Transformation. Figure 2 shows examples of obtaining skeletons from some objects by this method. Fig. 2 . Illustration of the result of thinning shapes by Blum's algorithm.   worked out a sequential approach, in which he defined the 'crossing number'-the number of times one crosses over from a white point to a black point when the eight neighbours of a tested pixel are traversed in sequence. The image is scanned from left to right and from top to bottom, and pixels are marked for deletion under additional conditions to prevent erosion, maintain connectivity and preserve two-pixel wide lines. This method was also used with gray-scale images.  showed many new aspects and solved serious problems commonly met in thinning algorithms. He was the first to evaluate the necessary and sufficient conditions for preserving topology while deleting border points in parallel process. Thereby, he solved the problem of erosion in the thinning of diagonal lines. In his algorithms, he considered a 3×3 local neighbourhood. He proved that 'a border pixel is removed only if its neighbourhood has only one black component (i.e., the Hilditch crossing number is 1) and has at least two black neighbours. ' Arcelli's parallel behaviour algorithm  uses two 3 × 3 thinning windows together with their 90 • rotations as masks for pixel deletion. It removes pixels from eight borders in the following order: north-west, west, and so forth. However, it does not remove all deletable pixels. BIB001 introduced the algorithm for thinning gray-scale pictures. It is based on a generalized concept of pixel connectivity: two pixels are "connected" if there is a path joining them with no pixel lighter than either of them. Using this idea, the thinned version on an image can be obtained by changing each pixel gray level to the minimum of its neighbor's gray levels. BIB002 BIB005 BIB006 introduced the definition of "multiple pixels" for the first time-points that are traversed more than once during contour tracing, points with no neighbours in the interior and points on two-pixel-wide lines. If only the "multiple pixels" from every tracing are retained, the result may not be a connected skeleton. Therefore, "multiple pixels" are called skeletal, as well as eight neighbours of skeletal pixels from a previous iteration. This does not result in a one-pixelwide skeleton. Contour pixels are traced sequentially. Then, BIB005 proposed a combination of parallel and sequential operations-a pattern could be divided into fields, which are processed independently by parallel processors, each operating sequentially on its own segment. Arcelli's algorithm BIB003 is of a sequential type. It uses contour tracing to find the pixels for deletion. This approach allows reducing the computational time needed to obtain the skeleton. Contour analysis is performed to find regions to be represented by the skeleton branches. The method of BIB004 is also a sequential algorithm-successive iterations consider the removal of contour elements. Regions that can be regarded as significant protrusions are detected before applying the removal operations. In BIB009 , the authors used the Pavlidis concept of 'multiple pixels' (pixels are placed where the contour self-interacts). The paper gives a necessary definition to satisfactorily detect such pixels. Then Arcelli and di Baja (1989) developed a sequential algorithm that used a 4-distance transform to find a set of skeletal pixels (two-pixel wide, at most) within one raster scan of the image. Then, another inspection of the picture removes the unnecessary pixels. The algorithm of BIB007 covers onesubcycle parallel thinning using syntactic rules and a cascade of tables to determine a new pixel code, on the basis of the distance to the background. Two-scan postprocessing is applied to obtain the final skeleton. BIB008 proposed a fast thinning algorithm where the image is compressed to a reduced gray-scale representation. This is then thresholded (with connectivity constraints) to a binary image to which an existing thinning algorithm BIB004 was applied. The resulting skeleton is then expanded to its original scale.  wrote a paper presenting a onesubcycle thinning algorithm and its parallel implementation. They called it a 'one-pass algorithm'. They paid attention to the idea of bias skeletons, the basic approach used later by Chen BIB011 BIB014 in his modified algorithm. Bias skeletons appear in the junction of lines that form angles less than 90 • (Fig. 3(a) ). They mentioned two reasons behind generating bias skeletons. One is that the restoring templates are of an even size and hence the pixel removal process is not symmetrical, unless we are dealing with systematic design, as restoring templates are only used in maintaining the connectivity of the final skeleton. The other factor is due to the side effect of the thinning templates, that is, they remove pixels from convex corners faster than from concave corners. A sample of thinning results using this algorithm is given in Fig. 3(a) . BIB010 presented a noniterative, non-pixel based algorithm, which produces a skeleton in one pass, by line-following. The line is followed by a window of variable size, the skeleton is the line connecting centres of successive windows. The method is less sensitive to noise than conventional thinning algorithms. The algorithm of  is another example of parallel thinning. The contour pixels are examined for deletion in an iterative process. The decision is based on a 3 × 3 neighbourhood. Each iteration is divided into two subcycles-one deleting the north and east pixels and the other for south and west. This algorithm does not give a one-pixel-wide skeleton. Although it shows very good results in thinning and provides a rather good skeleton, the algorithm and its 1-subcycle modified version BIB013 do not preserve all significant geometric features of the image (see Fig. 3(b) ). Chen and Hsu worked out an interesting algorithm modifying it through a series of papers (1989b; 1989a; 1990; 1988) . BIB014 reached a 1-subcycle parallel thinning algorithm producing a one-pixel-wide skeleton that preserves significant geometric features of patterns ( Fig. 3(c) ). He developed a method embedded in a parallel algorithm BIB011 to produce biasreduced skeletons using, as a major factor, what he defined the HDP-Hidden Deletable Pixel detected by algorithms of vector analysis. The HDP is detected and removed, so that the bias skeleton can be reduced. Despite the satisfactory results of thinning, Chen's algorithm did not show any significant application to object-images, handwritten words or at least machine-written alphabets of a cursive character. The results of thinning curved parts of machinewritten English letters, for example, are not as good as those of straight lines. This is demonstrated by the thinning results of this algorithm in Fig. 3 (c). (a) (b) (c) Fig. 3 . Thinning by CWSI  ) (a), AFP3 BIB013 ) (b), CYS BIB014 (c).  introduced the force-based approach with a new idea for thinning strategy based on a definition of a 'skeletal pixel' as being as far from the object outline as possible while maintaining basic connectivity properties. Accordingly, the basic idea is that a skeleton is a global property of a binary object, and that the boundary should be used to locate the skeleton pixels. The criterion is summarized as follows: the background pixels which are adjacent to the boundary act as if they exerted a force; the skeletal pixels lie in areas having the ridges of this force field and are located by searching where directions of the force vectors change significantly. Figure 4 shows how to compute the force at a pixel location and the vector sum of forces. BIB015 This algorithm actually represents a modification to Guo and Hall's approach. In an iterative process the deletion decision is based on eleven 3×3 thinning templates. There are two subcycles-the second uses templates rotated by 180 degrees. The algorithm preserves the connectivity of patterns and produces one-pixel-wide skeletons (Fig. 5 ). In the paper, Zhang claimed this algorithm was faster than Guo and Hall's. The Altuwaijri algorithm-ART2 NN BIB016 ) is a data-image-clustering based thinning algorithm that employs neural networks and adaptive resonance theory for image clustering. The image is an Arabic character BIB016 . Altuwaijri claims the algorithm produces skeletons which are superior to the outputs of the conventional algorithms. He compared it ( Fig. 6 ) with Zhang's algorithm given in BIB015 . ART2 showed higher data-reduction efficiency and much simpler skeletons with less noise spurs and reduced time complexity. The main advantage of this method, however, is its ability to remove the redundant loops appearing in the final thinned shape in many thinning algorithms. This problem may not seem particularly important for the preservation of essential geometric features in most alphabetical scripts. However, in Arabic and many other cursive character alphabets such a problem is serious as the resulting letter may resemble another letter, rather than the correct one. Figure 7 shows how the redundant loop may change the letter Seen into the letter Ssad. BIB017 proposed a method for obtaining a skeleton from a color image using morphological operations on vectors defined in the HSV color space. In the presented method the extraction of a skeleton is preceded by the ordering of vectors based on their individual components (hue, saturation and value). KMM   BIB018 ) is the authors' original contribution based on an original approach described in  and modified in a series of works  BIB018 . The algorithms acronym comes from the initials of the authors: Khalid, Marek and Mariusz. Basically, the algorithm is a sequential iterative one. It produces a one-pixel-wide continuous skeleton from an image. The details of the thinning algorithm are given in . The main goal of the algorithm was 1. to obtain a continuous line of symmetry (the name given by Blum to the skeleton  ), and alphabet letters, signatures, pictures and medical images in their two-dimensional views. The ideal skeleton was not the aim of the criterion. In fact, there is no algorithm that yields an ideal skeleton in any case. The most important thing is usually the retaining of pixels that preserve the significant geometric features of the given pattern in all kinds of images. Figure 8 shows KMM thinning results when applied to the same figures given in  and shown earlier in Fig. 2 . Notice that the two circles differ from each other by one pixel-length in their diameters. The circle of a diameter with an even number of pixels is thinned to a dot, while that of a diameter with an odd number of pixels is thinned to an angular shape. Note also that a rectangle is thinned to a line and seems to be more appropriate than Blum's skeleton  . KMM was under continuous modification. Its latest version for universal use will be given in Section 3 as K3M-Khalid, Marek, Mariusz, Marcin. The algorithm presented by BIB019 is an example of parallel thinning with the decision of deletion made upon an algorithm based on quantity and position of neighbours of each pixel. With 20 a rules, a pixel is classified into one of four classes, and then a decision is made. Two-pixel-wide lines are treated separately. BIB026 proposed another parallel thinning algorithm. Pixel elimination rules are based on 3 × 3 windows considering all kinds of relations (256) formed by 8-neighbours of the object pixel. All the rules are applied simultaneously to each pixel. In order to keep the connectivity of even pixel-width lines, additional checks are applied before deleting the pixels. These additional checks involve using rules based on 4 × 4, 3 × 4 and 4 × 3 windows. In order to reduce the loss of information when thinning shapes like in Fig. 9(a) , the authors introduce a parameter R, where A(s) is the area of s pixels, s 1 is the image skeleton, s 2 is the image contour. Based on its value, the algorithm returns either a thinned image (Fig. 9(b) ) or its contour (Fig. 9(c) ). If R is less than the threshold, the image contour is retained. The threshold value used by the authors was 0.4.  created a method that interprets the image as a 2D thermal conductor that consists of pixels, where pixel intensity represents the temperature. Pixels with a higher intensity value have higher temperature, while the background pixels have the lowest temperature. The thinning task is considered as an inverse process of heat conduction. The thinning process follows the inverse of the temperature flow, from cooler (background pixels) to warmer areas (object pixels with higher intensity), as in The first step of the algorithm is the calculation of the Heat-Flow Direction Map (HFDM), which gives the directions and magnitude of the time-inversed heat flow for each point of the image. Then for each pixel of the image the intensity is subtracted and added to the pixel selected based on information provided by the HFDM. The latter step is iterated until a completely thinned image is obtained. The disadvantages of the proposed method lie in the K3M: A universal algorithm for image skeletonization and a review of thinning techniques 323 fact that it does not guarantee a one-pixel width skeleton and that the computation of the right number of iterations to preserve the shape topology is a difficult task. BIB020 proposed an algorithm to generate a disconnected, three-dimensional (3D) skeleton. A discrete skeleton is generated by propagating a wave from the boundary towards the interior on an octree lattice of an input solid model. As the wave propagates, the distance from the boundary and the direction of the wave front are calculated at the lattice-nodes (vertices) of the new front. An example of their results is shown in Fig. 11 . Rockett's algorithm BIB021 aimed at improving the rule based algorithm presented by BIB019 . They observed the number of cases where the A-W algorithm failed to produce a centre line of a single pixel width. To eliminate such cases they adopted a two-stage thinning procedure which used the A-W rules to thin down to a skeleton which includes 2-pixel wide lines. As a second stage, they examined the 2-pixel wide lines in the skeleton produced by the first processing stage to see which pixels can be deleted without compromising the connectivity of the skeleton. In order to determine if the deletion of a pixel in a 2-pixel wide line disrupts connectivity, they built an adjacency matrix from an undirected graph of the local pixel connectivity over its eight neighbours (Fig. 12) . To retain connectivity, before deleting the pixel the algorithm checks if every row (or column) of the adjacency matrix contains at least one non-zero entry. An example of Rockett's results is presented in Fig. 13 . BIB022 constructed the skeleton in three steps directly from the greyscale image and represent it as a set of curves which in turn are represented as cubic B-splines. The method was designed to extract the skeleton which is very close to human perception of the original pen tip trajectory (Fig. 14) . BIB023 proposed a method for computing skeletons of volumetric models by alternating thinning and a novel skeleton pruning routine. The presented me- thod creates a family of skeletons parameterized by two user-specified numbers that determine respectively the size of the curve and surface features on the skeleton. BIB024 extracted the skeleton of a character on the basis of the wavelet transform BIB012 . The skeletonization algorithm starts with the extraction of a primary skeleton in a regular region followed by amendment processing of the primary skeletons and connecting them in the singular region (Fig. 15) . BIB025 proposed a three-stage skeletonization algorithm for shaped fiber recognition. In the first stage, the Euclidean distance transform is applied to the fiber image. In the second stage, the local maximal disc centres are determined as the true skeleton points, regar-(a) (b) Fig. 15 . Examples of images (a) and their thinned versions (b) using the algorithm described in BIB024 . dless of their connectivity. In the last step, a full skeleton is generated by linking isolated skeleton points, and pruning spurs arising from edge noise (Fig. 16 ). (a) (b) Fig. 16 . Examples of star and trilobal shaped fibres (a) and their skeletons (b) obtained using the method presented in BIB025 . Table 1 concludes the presentation of selected works by giving a summary of their most important features.