Thinning methodologies−a comprehensive survey <s> VI. CONCLUSIONS <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> BIB001 </s> Thinning methodologies−a comprehensive survey <s> VI. CONCLUSIONS <s> A recently published parallel thinning approach [ 4 ] is evaluated. An improvement is suggested to enable preservation of certain diagonal lines which are not preserved by this algorithm. A unified notion of what is meant by an iteration (or subiteration) and parallel speed is presented, and with regard to its parallel speed this algorithm is argued to be comparable to other two-subiteration algorithms. The parallel speed of this algorithm is compared experimentally to the original algorithm that it improves [ 12 ] and it is shown that, unlike execution time on a specific machine, parallel speed is not improved. Finally, a more complete connectivity analysis is given illustrating sufficient additional conditions for applying fully in parallel the basic thinning operator used in both algorithms while maintaining all image connectivity properties. <s> BIB002
In the literature, there appears to be a general agreement about the requirements that should be met by a thinning algorithm. These include preservation of topological and geometric properties, isotropy, reconstructibility, and high processing speed. Whereas the nonpixel-based thinning methods of Section V are efficient in terms of the number of operations required, it would seem impossible for them to preserve more detailed features of patterns since they are usually based on locating certain critical points and connecting them. These procedures are useful in applications where the detection of such points would suffice, one possible example being feature extraction in OCR. In general, however, the emphasis should be placed on the development of parallel algorithms for processing speed, especially when parallel image processing structures become increasingly available. Reconstructibility, or the ability to regenerate the original pattern from the skeleton, is one objective measure of the accuracy with which a skeleton is representing the pattern. This criterion is generally satisfied by algorithms based on medial axis and other distance transforms by virtue of the fact that their skeletal pixels are also the centers of maximal blocks with known radii, but this is usually not the case with thinning algorithms. (Some exceptions are [86] , [88] , [138] and [77] to a certain extent, all of which use labeling schemes to retain the distances of skeletal pixels from the background). Complete isotropy or invariance under rotation seems almost impossible to achieve in iterative algorithms. In sequential algorithms, the result depends on the order in which pixels are examined, and in parallel algorithms that remove one or two types of border points in each subiteration, the resulting skeleton depends on the order of the subiterations. Examples of nonisotropic results from these algorithms are shown in BIB001 . At the same time, medial axis transforms are not invariant under rotation due to a lack of algorithms based on true Euclidean distance maps so that very different results can be obtained from right-angled corners with one side parallel to an axis and at 45' to it. The use of these transforms simply transfers the problem from the thinning algorithm to the distance function, and the result can be just as idiosyncratic [53] . Maintaining connectedness and topology in thinning appears to have been resolved through various means. In sequential algorithms, it is sufficient to examine 3 x 3 local neighborhoods from the viewpoint of crossing number, for example. Parallel algorithms resolve the problem by dividing each cycle into subiterations or by considering a larger neighborhood in one subiteration. Preservation of geometric properties, however, appears to be a more difficult problem. The main difficulty is that to achieve simplicity of algorithm and/or processing hardware, it is desirable to consider only small local neighborhoods, but these neighborhoods are incapable of providing global, structural information of the kind that is needed (for example) to distinguish between noise spurs and genuine end points. more broadly applicable [70] , BIB002 , or apply the condition only at the later stages of thinning [118] . However, every modification of this type involves a tradeoff when uniformly applied, and additional information is really needed to make finer distinctions between cases. For this reason, various criteria using distance transforms have been introduced ([ 1011, BIB001 , and  , for example). Some such means would be needed to propagate more global information to contour pixels, and it may allow for faster deletion of pixels in the initial stages. Ultimately, the particular geometric properties a skeleton should preserve may be problem or application dependent. Algorithms based on medial axis transforms that possess the reconstruction capability would be well suited to applications such as data compression for storage and facsimile transmission  . However, the skeletons obtained by these methods are very sensitive to contour noise since branches can originate to many convexities on the boundary, depending on the distance transform used. Of course, this property is what renders them capable of exactly recreating the original pattern, but they would not be useful for pattern recognition where patterns with a wide variety of insignificant local contour differences can belong to the same class. For this latter application, it is much more important for the pattern to be represented by a collection of arcs lying along the center lines of the main curves of the pattern, whereas small perturbations of the contour should be ignored. At the same time, it is recognized that the thinning of blob-like patterns may result in skeletons that cannot preserve the original shape. In this respect, two types of skeletons are actually obtained from the different methods of thinning and medial axis transforms, and the choice should depend on the application. In conclusion, it should be mentioned that comparison of the quality of skeletons remains a largely subjective, visual decision since the concepts of (connected) medial line, noisy branch, and excessive erosion have not been precisely defined. In addition, it is not objectively or quantitatively clear as to how a skeletal branch should accurately reflect the shapes of the two contours it represents. Comparisons are inevitably made when a new (or a modification of an existing) algorithm is proposed, but it is often based on the inconclusive evidence of one or two patterns. More general comparisons have been made from a digital geometry point of view [120] , and in [92] and [93] , comparisons have been made between skeletons obtained from thinning algorithms and reference skeletons prepared by human subjects. However, a more objective framework for the measurement of skeleton quality remains to be developed.