Thinning methodologies−a comprehensive survey <s> V. NONITERATIVE THINNING METHODS <s> Conventional algorithms which have been proposed for the skeletonisation of digital patterns or pictures suffer from basic problems (for example, endpoint identification, connectivity) deriving from the rigid application of fixed rules. This letter introduces a heuristic approach to the problem which overcomes such difficulties and may be tailored to suit different types of data. <s> BIB001 </s> Thinning methodologies−a comprehensive survey <s> V. NONITERATIVE THINNING METHODS <s> Abstract A general-purpose edge extractor is presented. Although it is able to override gaps (up to 2 grid unit) it leads to good time performance. With a dual edge tracking technique, skeletons can be easily computed and gaps can be selectively overedden along skeletons. <s> BIB002 </s> Thinning methodologies−a comprehensive survey <s> V. NONITERATIVE THINNING METHODS <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> BIB003
In the preceding sections, we discussed algorithms that produce a skeleton by examination and deletion of contour pixels. In this section, the algorithms to be considered are nonpixel based; they produce a certain median or center line of the pattern directly in one pass without examining all the individual pixels. Since the algorithms that accomplish this by medial axis or distance transforms are discussed in a separate paper, we are mainly concerned here with methods that determine center lines by line following or from run length encoding. It has been argued that this is the way human beings would perform thinning and that it is possible to retain global features and maintain connectedness in the process The simplest category of these algorithms determines the midpoints of black intervals in scan lines and connects them to form a skeleton. These methods have the advantage of being computationally efficient, but they also have natural disadvantages and would create noisy branches when the strokes are nearly parallel to the scan line [87] . They are valid in certain specialized applications where the scanning direction can be approximately perpendicular to that of the stroke. For example, in [75] , the objects are rectangular with only small undulations along two parallel and much longer sides; therefore, a useful median line can be obtained by maintaining a constant scanning direction perpendicular to ~5 1 .  is in both the 2-and y-directions and the direction of smaller length (within certain constraints) would be selected. Some algorithms obtain approximations of skeletons by connecting strokes having certain orientations. For example, four pairs of window operations are used in four subcycles [76] to test for and determine the presence of vertical, horizontal, right, or left diagonal limbs in the pattern. At the same time, the operators also locate turning points and end points by a set of final point conditions, and these extracted points are connected to form a line segment approximation of the skeleton. In [lo81 and [110] , the boundary pixels are first labeled according to the above four local orientations. For each boundary pixel, a search is made for the same kind of label on the opposite side of the boundary (within a maximum stroke width) in the direction perpendicular to that given by the label. The midpoints of these pairs are then connected to form a skeleton. These methods are not appropriate for general applications since they are not robust, especially for patterns with highly variable stroke directions and thicknesses. In [19] , where a discrete version of the symmetric axis of an object is theoretically derived using them. Lines of elongated objects are followed by rectangular windows of variable size in BIB003 , where the window can shrink or grow in size according to the width of the line at the location of the window. The skeleton is the unit width line connecting the centers of successive windows. In [82], a combination of thinning and stroke tracking is used on Chinese characters. Contour pixels are first sequentially examined, and p is deleted if 01: N ( p ) has at least one interior pixel, 0 2 : N ( p ) has, at most, three contour pixels, and 0 3 : the contour pixels in N ( p ) U { p } are traced consecutively. When no more pixels can be deleted, the remaining pattern is traced using a 2 x 2 square, and the skeleton is the loci of these squares. The tracing is repeated if necessary. Apart from these contour tracking methods, skeletal pixels have also been determined by a heuristic approach BIB001 . The deletion of a pixel p is determined by the local pattern density Another set of algorithms determine the center line of P by tracking the two contours .of each curve simultaneously. In BIB002 , the edge trackers move under the constraint of maintaining minimum distance between them. In [105], elongated ribbon-like simply connected objects without protrusions are tracked by approximate trapezoids using two pointers to follow the two contours of P. The midpoint of the base of the next trapezoid is considered to be skeletal, where the next base is either the side opposite the present base or a diagonal, depending on whether the diagonals are almost equal in length. This algorithm is extended [lo61 to objects containing protrusions by generating skeletons of the protrusions and backbone separately and then joining them together. The above algorithm considers a simply connected pattern P to be a many-sided polygon, and this approach is also adopted in [72] to construct a median line. For every vertex v of P, its opposite line segment L is determined as the side of The number of directions (out of four) in which the pixel has a maximum value (according to the final addition matrix) is its comparative degree, and the matrix of these degrees is thinned according to the sequential procedure of [ 1371, together with the added condition of having a small degree. The addition matrix also contains information that allows for an approximate reconstruction of the pattern. Using a different approach, skeletons can also be obtained from Fourier descriptors, at least for patterns that are not closed or overlapping and that have constant width [90] . For such patterns, the contour is traced to obtain a closed curve from which Fourier descriptors can be extracted. Fourier descriptors of the skeleton can then be determined, and the skeleton can be constructed from a finite set of harmonics. However, it would appear that highly mathematical methods can be used to obtain skeletons of only rather idealized patterns. 