Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> Abstract : The aims and scope of the project are summarized. The primary tasks are the construction of a 1,000-image optical preprocessor having its input derived from a television camera, and the development of techniques and equipment for applying the MINOS II learning machine to the processing of graphical data. A detailed analysis is presented of the problems associated with the design of the 1,000-image preprocessor. A structure using a storage tube, an array of plastic lenses, and cadmium sulphoselenide photoconductive cells is proposed. The most severe constraints are cost and the marginal level of illumination. The automatic training procedure, which is a significant technical development of MINOS II is analyzed in detail; both logical and electrical circuits are given. (Author) <s> BIB001 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <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> BIB002 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> A thinning algorithm, of the banana-peel type, is presented. In each iteration pixels are attacked from all directions (there are no sub-iterations), and the deletion criteria depend on the 24 nearest neighbours.© (1983) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only. <s> BIB003 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> This paper describes an algorithm to efficiently realize repeated Cellular Logic operations. These Cellular Logic operations include erosions and dilations as well as skeletonization (topology-preserving shrinking) and propagation procedures. In the proposed method only those image pixels which might change in an iteration are processed, based on the changed pixels in the previous iteration. Processing times for solid objects (maximum diameter 40 to 200 pixels, 256 x 256 image) on a 10 Mhz Motorola 68000 system range from 250 ms to 400 ms per iteration. A simpler suboptimal method is also described which is 2 to 3 times slower. <s> BIB004 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> Abstract This paper presents an algorithm for thinning digital binary patterns (skeletonization). The algorithm consists of two phases. The first phase thins the input pattern to unit thickness by alternately smoothing of the pattern and stripping of the contour points. The second phase adjusts the resulting skeleton from phase one so that a medial skeleton can be obtained. The performance of this algorithm is first compared experimentally with recent results of two other research groups and then with nine other skeletonization algorithms proposed by other researchers. Results show that the alternate smoothing and stripping algorithm produces skeletons which are smooth and with least distortion and well-formed than the others. <s> BIB005 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> A simple sequential thinning algorithm for peeling off pixels along contours is described. An adaptive algorithm obtained by incorporating shape adaptivity into this sequential process is also given. The distortions in the skeleton at the right-angle and acute-angle corners are minimized in the adaptive algorithm. The asymmetry of the skeleton, which is a characteristic of sequential algorithm, and is due to the presence of T-corners in some of the even-thickness pattern is eliminated. The performance (in terms of time requirements and shape preservation) is compared with that of a modern thinning algorithm. <s> BIB006 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> Abstract Digital topology deals with the topological properties of digital images: or, more generally, of discrete arrays in two or more dimensions. It provides the theoretical foundations for important image processing operations such as connected component labeling and counting, border following, contour filling, and thinning—and their generalizations to three- (or higher-) dimensional “images.” This paper reviews the fundamental concepts of digital topology and surveys the major theoretical results in the field. A bibliography of almost 140 references is included. <s> BIB007 </s> Thinning methodologies−a comprehensive survey <s> OVERVIEW OF THINNING <s> A modification is proposed to the Safe Point Thinning Algorithm (SPTA) to speed it up. The modified algorithm was implemented on a single processor. It was then implemented on the Homogeneous Multiprocessor Proper under two techniques: data decomposition and function decomposition. Experimental results show that with our modification and multiprocessor implementations, the SPTA was considerably speeded up. <s> BIB008
The term "skeleton" has been used in general to denote a representation of a pattern by a collection of thin (or nearly thin) arcs and curves. Other nomenclatures have also been used in different contexts. For example, the term "medial axis" is also used to denote the locus of centers of maximal blocks that are also equivalent to the local maxima of chessboard distance [loll. Some authors also refer to a "thinned image" as a linedrawing representation of a pattern that is usually elongated. In recent years, it appears that "thinning" and "skeletonization" have become almost synonymous in the literature, and the term "skeleton" is used to refer to the result, regardless of the shape of the original pattern or the method employed. In this paper, we will observe the general usage of the term "skeleton"; however, we will refer to methods involving determination of centers of maximal blocks as "medial axis transformations," whereas the reduction of generally elongated patterns to a line-like representation will be considered as "thinning." This seems to be a reasonable way to distinguish between different methodologies while recognizing that the results can be quite similar in appearance. In this section, we consider some general aspects of iterative thinning algorithms or, more precisely, the algorithms that delete successive layers of pixels on the boundary of the pattern until only a skeleton remains. The deletion or retention of a (black) pixel p would depend on the configuration of pixels in a local neighborhood containing p. According to the way they examine pixels, these algorithms can be classified as sequential or parallel. In a sequential algorithm, the pixels are examined for deletion in a fixed sequence in each iteration, and the deletion of p in the nth iteration depends on all the operations that have been performed so far, i.e., on the result of the (n-1)th iteration as well as on the pixels already processed in the nth iteration. On the other hand, in a parallel algorithm, the deletion of pixels in the nth iteration would depend only on the result that remains after the (n-1)th; therefore, all pixels can be examined independently in a parallel manner in each iteration. In the following discussion (as in the literature), the terms iteration and cycle are used interchangeably, as are the terms subiteration and subcycle. The term pass has been used to denote either iteration or subiteration, but it will be used to mean subiteration here. The following notations will be adopted in the discussion below. It is understood that a pixel p examined for deletion is a black pixel, and the pixels in its 3 x 3 window are labeled as shown in Fig. 1 there exists an 8-(or 4-) path from z to y consisting of points in Q. In this case, Q is said to be an 8-(or 4-) component of P. The order of connectivity of P is the number of components of its complement P , and if this order is 1, we say that P is simply connected; otherwise, P is multiply connected. A pixel p is 8-(or 4-) deletable if its removal does not change the 8-(or 4-) connectivity of P. The pixels considered for deletion are contour pixels. It has been suggested BIB001 that the satisfying duality of P and P having different types of connectivity would eliminate the paradoxes of P and P, being both connected or both disconnected [98] . Since it is desirable for a skeleton to have unit width, the choice would be to adopt 8-connectivity for P and 4-connectivity for P. This is assumed in the rest of the paper unless otherwise stated, and the reader is referred to the original publications for the (usually) analogous formulations using the other metrics. One consequence of this choice is that connectivity can be preserved by deleting only those pixels of P that are 4-adjacent to P. Therefore, contour pixels are usually defined as those having at least one white 4-neighbor ([lo41 and [18] are exceptions). We will assume the common definition of contour pixels, unless otherwise stated, and note that contour points have also been called edge points [77] and border points BIB007 . Noncontour black pixels are said to be interior points. We will also consider p to be an end point and retained if b(p) = 1; this will be referred to as the end point (or end pixel) condition. This condition is applied differently by some authors: p may be retained when there are two or three consecutive black pixels on one side of N ( p ) [77] , the condition may be applied only after the first two iterations  , or it may be omitted entirely in order to avoid spurious branches [18] . Most of the differences between algorithms occur in the tests implemented to ensure connectedness. This property has been defined in terms of crossing number, connectivity number, and pixel simplicity. There are two definitions of the crossing number of a pixel. Rutovitz [lo31 first proposed this useful measure of connectivity as the number of transitions from a white point to a black point and vice versa when the points of N ( p ) are traversed in (for example) counterclockwise order. Therefore, this crossing number can be defined as i = l where 2 9 = xl, and it is equal to twice the number of black 4-components in N ( p ) . Deletion of p would not affect 4-connectivity if X,(p) = 2 since the black pixels in N ( p ) are 4-connected in these cases. However, since disjoint 4-components can be 8-connected, skeletons obtained using this crossing number can contain 8-deletable pixels, and these skeletons are sometimes said to be imperfectly 8-connected [24] or are more than one pixel wide. In order not to belabor this point, we will assume that this will be understood in later sections and that skeletons obtained this way would usually need postprocessing to replace 4-connectedness with 8-connectedness. For this purpose, various algorithms can be applied, for example, those in [loo] or [SI. Hilditch [52] defined the crossing number X H ( P ) as the number of times one crosses over from a white point to a black point when the points in N ( p ) are traversed in order, cutting the corner between 8-adjacent black 4-neighbors. Therefore An alternative approach to preserving topology during thinning is that the genus of P (and P ) should remain invariant [124] , where the genus of P is defined as the number of connected components of P minus the number of holes of P. For any pixel p , its effect on the genus G can be determined completely from the configuration of N ( p ) . If deletion of p does not change G, p is said to be "simple." Since there are 256 configurations of N ( p ) , these combinations can be examined, and the ones where p is simple can be stored in a look-up table. It can be readily verified that the concept of "simple" based on genus is equivalent to that based on connectivity. Pixels with connectivity number N!(p) greater than one also belong to the category of multiple pixels [85] . These pixels are considered to occur where a pattern "folds" onto itself, and they include end points of branches, strokes that are two pixels in width, and pixels that should be assigned to the skeleton on the basis of the connectivity criteria. Consequently, these pixels are retained in the thinning process. This notion will be considered in more detail when the algorithms that utilize them are discussed. TABLE I GENERAL CLASSIFICATION SCHEME by other researchers using various techniques. Cellular logic operations based on 3 x 3 neighborhoods are used in BIB004 ; since a change in the value of p may induce a change only in the pixels of N ( p ) in the next iteration, only these pixels need to be processed. In [go] , it was found that a sequential thinning method based on raster scan and 3 x 3 operations can be implemented using a pipeline structure to reduce the memory and processing time required. In [91] , connected horizontal runs of black pixels are coded in interval tables (the use of pointers in these tables implies that only a change of pointers would be required when a shift operation is used on local neighborhoods). The image that remains after one iteration is found by inspection of the overlapping intervals in the preceding, current, and next lines of the image. Alternatively, contour pixels can be queued, with the change of a contour pixel causing all its 4- of pixels can be deleted in one iteration; therefore, fewer iterations would be required to obtain skeletons of thick patterns. However, this increase in speed is achieved at the expense of "coarser" results (noisy skeletons); in the thinning of elongated patterns, the use of a larger k can be detrimental to processing speed. The same thinning algorithm has also been implemented in parallel in this work by using four subiterations and examining one type of border pixels (north, south, east, or west) in each subiteration. In another early algorithm [134] , every black pixel p is examined and labeled according to the rule Contour following algorithms can visit every border pixel of picture, if all the borders of the picture and holes are followed [ 1341. Therefore, such methods, which have been utilized previously without proof, have been shown to be valid in this sense. Border following algorithms are also given in these papers. These algorithms have an advantage over raster scans because they require the examination of only the contour pixels instead of all the pixels in P and P in every iteration. Some algorithms that use contour tracing are seen in [lo] , [85] , BIB005 , [126] , [130] , and BIB006 , and the contours are traced using the Freeman chain codes in [64] . is examined, it is usually deleted or retained according to the configuration of N ( p ) . To prevent sequentially eliminating an entire branch in one iteration, a sequential algorithm usually marks (or flags) the pixels to be of 3. p is a contour pixel, i.e., p has at least one white 4-A seminal algorithm in sequential thinning is that of Hilditch  , which utilized the crossing number X,(p). The pattern is scanned from left to right and from top to bottom, and pixels are marked for deletion under four additional conditions that here for completeness: following properties unless otherwise stated: neighbor. Then, two raster Scans in opposite directions are performed to remove pixels labeled 2 and 3, respectively, provided these pixels are not end points and have connectivity number 1 (where 4-or 8-connectivity can be used). Although the algorithm is simple and yields connected skeletons, vertical strokes that are an even number of pixels wide and open at one end can be completely eliminated. In [18] , the different criteria of [lo41 are used for contour or edge points. For example, p is a west edge point if there is at most one black pixel in the first column of N ( p ) and at least 3 black pixels in the rest of N ( p ) . In this case, an extra HI: At least One black neighbor of P must be Unn~rked. H2: X H (~) = 1 at the beginning of the iteration. H3: If53 is marked, setting 2 3 = 0 does not change X H ( P ) . H4: Same as H3, with 2 5 replacing 2 3 . Condition H1 was designed to prevent excessive erosion of small "circular" subsets, H2 to maintain connectivity, and H3-H4 to preserve two-pixel wide lines. The author also extended the method to thinning of grey-scale chromosome images. This algorithm has also been implemented for binary images The SPTA [77] is a sequential algorithm that uses two raster scans per cycle, where the first is left to right, and the second is top to bottom. In each scan, p is marked for retention (p is a safe point) if one of the following is true: N1: N ( p ) satisfies one of the windows in Fig condition had to be imposed to prevent an interior pixel from being marked as an edge point. Edge points are marked in one raster scan after which the marked points are compared against six 3 x 3 windows (those shown in Fig. 2 and their 90" rotations) and deleted if they are not break points, i.e., their removal does not create breaks in the pattern. It was found that elimination of the end-point condition resulted in less spurious tails. The procedure is repeated until no pixels are deleted or for a preset maximum of three iterations, after which a single "clean-up" scan is applied to remove all black pixels that are not end points, break points, or interior points. The results obtained from this procedure were not very different from those of thinning carried through to the end, probably because this algorithm was designed and tested on (almost thin) character patterns. The preceding algorithm assumes a smoothing preprocessing phase; this is extended in BIB005 , where smoothing is performed before each iteration. In each iteration, contour pixels satisfying the usual stated conditions are marked and then examined for deletion as in [18] but with the endpoint condition. When no more pixels can be deleted, a final adjustment phase is introduced in which a skeletal pixel would be moved to one of its 4-neighbors if the latter pixel has a greater 8-distance from the background. In the process, connectivity of the skeleton is maintained while skeletal points are moved closer to the medial line of the original pattern. The classical thinning algorithms mentioned in [87] also use the windows shown in Fig. 2 together with their 90" rotations to determine skeletal pixels. (For the sake of brevity, we use 90" rotations to also include 180" and 270" rotations when different windows are generated). Since these windows, in effect, only represent connectivity preservation criteria, their sequential application to a pattern could result in excessive erosion or serious shortening of branches. To overcome this difficulty, a mixture of parallel and sequential operations is proposed. Only one type of contour point is processed in each subiteration, skeletal pixels are marked for retention through all subsequent iterations, and a pixel q to be deleted is marked so that it is considered to be a black pixel when its neighboring pixels are checked in the current iteration. These conditions are designed to preserve connectivity and prevent disappearance of two-pixel wide lines, and they also retain end points without requiring a specific condition. A variation of this algorithm is based on the compilation of an extensive list of thinning rules and consideration of 5 x 5 neighborhoods BIB003 . These larger neighborhoods are also used in [69] , where the pattern is raster scanned, and deletion of the center pixel is based on comparison with 20 25-b templates stored on a chip. These conditions are equivalent to a west contour point p being safe if the boolean expression 5 1 ( 2 2 + 5 3 + 57 + z 8 ) ( 5 3 + 5 4 ) ( 2 7 + 5 6 ) = 0. In the first scan, west contour points are marked, then east contour points that are not west safe points, and so on. Condition N2 is intended to prevent excessive erosion of diagonal strokes two pixels wide, but it can lead to noisy branches [65] . In BIB008 , a modification was proposed to SPTA to eliminate (in most cases) the last pass when no pixels would be deleted, and the modified algorithm was implemented on a multiprocessor using the methods of a) function and b) data decomposition. In a), each processor executes one scan, and each completed row is moved to the processor performing the next scan, whereas in b) each processor scans a portion of the image with overlapping boundaries. The Rutovitz crossing number X R (~) is used to determine pixel deletion in  ,  , and BIB002 . In these algorithms, a slightly different definition of contour pixel is used; here, a contour pixel is a black pixel having at least one white 8-neighbor. This condition together with the use of X,(p) require an additional condition ( F = 5 1 % 3 2 5 5 7 = 0) to ensure that holes would not be created when contour points are deleted. Complete conditions for deletability of p while maintaining connectivity are given in  ; briefly, these useful conditions are as follows: 