K3M: A universal algorithm for image skeletonization and a review of thinning techniques
---
paper_title: Experiments in processing pictorial information with a digital computer

paper_content:

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.
---
paper_title: Quantitative performance evaluation of thinning algorithms under noisy conditions

paper_content:

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. >
---
paper_title: One-pass parallel thinning: analysis, properties, and quantitative evaluation

paper_content:

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. >
---
paper_title: Programming pattern recognition

paper_content:

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.
---
paper_title: Thinning methodologies−a comprehensive survey

paper_content:

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. >
---
paper_title: Algorithms for Graphics and Image Processing

paper_content:

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.
---
paper_title: The use of hidden deletable pixel detection to obtain bias-reduced skeletons in parallel thinning

paper_content:

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.
---
paper_title: A systematic approach for designing 2-subcycle and pseudo 1-subcycle parallel thinning algorithms

paper_content:

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.
---
paper_title: Thinning methodologies−a comprehensive survey

paper_content:

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. >
---
paper_title: Fast fully parallel thinning algorithms

paper_content:

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.
---
paper_title: A rotation invariant rule-based thinning algorithm for character recognition

paper_content:

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.
---
paper_title: Thinning Algorithms for Gray-Scale Pictures

paper_content:

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.
---
paper_title: Algorithms for Graphics and Image Processing

paper_content:

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.
---
paper_title: Fast thinning algorithm for binary images

paper_content:

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.
---
paper_title: Colour image skeletonisation

paper_content:

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.
---
paper_title: Computing a family of skeletons of volumetric models for shape description

paper_content:

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.
---
paper_title: A thinning algorithm for discrete binary images

paper_content:

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.
---
paper_title: An improved parallel thinning algorithm

paper_content:

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.
---
paper_title: The use of hidden deletable pixel detection to obtain bias-reduced skeletons in parallel thinning

paper_content:

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.
---
paper_title: 3D discrete skeleton generation by wave propagation on PR-octree for finite element mesh sizing

paper_content:

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.
---
paper_title: Implementation and Advanced Results on the Non-Interrupted Skeletonization Algorithm

paper_content:

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].
---
paper_title: Pattern thinning by contour tracing

paper_content:

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.
---
paper_title: A thinning algorithm for Arabic characters using ART2 neural network

paper_content:

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.
---
paper_title: A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons

paper_content:

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.
---
paper_title: A distance map based skeletonization algorithm and its application in fiber recognition

paper_content:

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.
---
paper_title: An asynchronous thinning algorithm

paper_content:

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.
---
paper_title: A theory for multiresolution signal decomposition: the wavelet representation

paper_content:

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. >
---
paper_title: An improved rotation-invariant thinning algorithm

paper_content:

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.
---
paper_title: A systematic approach for designing 2-subcycle and pseudo 1-subcycle parallel thinning algorithms

paper_content:

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.
---
paper_title: Line thinning by line following

paper_content:

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.
---
paper_title: Document Examiner Feature Extraction: Thinned vs. Skeletonised Handwriting Images

paper_content:

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.
---
paper_title: Fast fully parallel thinning algorithms

paper_content:

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.
---
paper_title: Wavelet-Based Approach to Character Skeleton

paper_content:

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
---
paper_title: A thinning algorithm based on prominence detection

paper_content:

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.
---
paper_title: Parallel syntactic thinning by recoding of binary pictures

paper_content:

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.
---
paper_title: A contour characterization for multiply connected figures

paper_content:

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.
---
paper_title: A thinning algorithm for Arabic characters using ART2 neural network

paper_content:

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.
---
paper_title: A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons

paper_content:

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.
---
paper_title: A systematic approach for designing 2-subcycle and pseudo 1-subcycle parallel thinning algorithms

paper_content:

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.
---
paper_title: A 1-subcycle parallel thinning algorithm for producing perfect 8-curves and obtaining isotropic skeleton of an L-shape pattern

paper_content:

The authors review their pseudo-one-subcycle parallel thinning algorithm. They present two improved versions of this algorithm, and describe a two-stage structure to realize the one-subcycle parallel algorithm. The first stage is to produce a perfect 8-curve excluding T-junction thin line. The second is to obtain the isotropic skeleton of an L-shaped pattern. The two stage structure consists of a thinning table and a control unit. The thinning table is used to provide the attributions for an input 3*3 local pattern. The control unit is used to check the removal of the center pixel of this local pattern, and the inputs of the control unit also comprise the outputs of other neighboring thinning tables. This structure can exactly implement the proposed one-subcycle parallel algorithms. The two improved algorithms have been implemented. Experiments confirm that the improved algorithms can produce the desired effective thin line and also show that the structure realized is feasible and practicable. >
---
paper_title: A rotation invariant rule-based thinning algorithm for character recognition

paper_content:

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.
---
paper_title: A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons

paper_content:

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.
---
paper_title: Fast fully parallel thinning algorithms

paper_content:

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.
---

Title: K3M: A universal algorithm for image skeletonization and a review of thinning techniques
Section 1: Introduction
Description 1: Provide an overview of the importance of thinning in image processing, its history, and the motivation behind the proposed K3M algorithm.

Section 2: State of the art
Description 2: Present a historical review and taxonomy of thinning algorithms, along with descriptions of significant algorithms and their comparative efficiency.

Section 3: K3M: A modified KMM algorithm
Description 3: Detail the K3M algorithm, including its assumptions and definitions, the iterative nature of its phases, and the modifications made to improve upon the KMM algorithm.

Section 4: K3M results and comparison
Description 4: Showcase the thinning results of the K3M algorithm on various inputs such as isolated letters, handwritten words, and graphical symbols, and compare its performance with other known algorithms.

Section 5: Parallelizing sequential algorithms
Description 5: Discuss the challenges and strategies for parallelizing sequential thinning algorithms to utilize modern parallel processing techniques effectively.

Section 6: Conclusions and future work
Description 6: Summarize the findings of the paper, highlighting the advantages of the K3M algorithm, and outline future research directions to enhance the algorithm further.