K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> State of the art <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> BIB001 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> State of the art <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> BIB002 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> State of the art <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> BIB003 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> State of the art <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> BIB004 </s> K3M: A universal algorithm for image skeletonization and a review of thinning techniques <s> State of the art <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> BIB005
The survey presented in this section introduces a historical review covering over 40 years of works on thinning algorithms, together with their basic principles and the state of the art. This survey is mainly based on algorithms mostly known to the authors, available either as papers in international conference proceedings, periodical and journal transactions or book chapters. The central role in the survey was played by BIB001 , BIB003 ,  and, finally,  . This is in addition to lots of individual works showing different methods and algorithms of thinning. Generally, each of the presented algorithms has its own advantages and disadvantages, and each has its applications where it performs better than others. Therefore, it is often difficult to directly compare the results. 2.1. Taxonomy. All thinning algorithms can be classified as either iterative or non-iterative. In iterative methods, thinning algorithms produce a skeleton by examining and deleting contour pixels through an iterative process in either sequential or parallel way. Parallel algorithms may also be further classified according to their performance, i.e., in 4-, 2-, or 1-subcycle manners. The latter (1-subcycle parallel algorithms) have always received more considerable attention in the research area of parallel thinning as they have reduced the computation time in a number of iterations, and that is why they are sometimes called one-pass or fully parallel algorithms BIB002 BIB005 BIB004 . In sequential thinning algorithms, contour points are examined for deletion in a predetermined order, and this K3M: A universal algorithm for image skeletonization and a review of thinning techniques 319 can be accomplished by either raster scanning or following the image by contour pixels. In parallel thinning algorithms, pixels are examined for deletion on the basis of results obtained only from the previous iteration. That is why parallel thinning algorithms are suitable for implementation in parallel processors. Non-iterative (non-pixel based) thinning algorithms produce a certain median or centre line of the pattern to be thinned directly in one pass, without examining all the individual pixels. The methods used in the works presented in this section may also be categorized as one of the following methodologies (Fig. 1). 