The authors present some historical research into early methods of skeletonization. The background to their work may be summarized as follows. Let I be the set of points (i, j) with i, j integral and let P be a finite subset of I. Then a set S is a skeleton for P if (1) S is thin, (2) S and P have the same connectivity, and (3) S reflects the shape of P. S is said to be thin if every point of S has a neighbor in the complement S¯ ; for connectivity see Rosenfeld and Kak [1]. Condition 3 is the most difficult to define; perhaps the most attractive definition is that of Pfaltz and Rosenfeld [2] for whom it is equivalent to 3’. However, a connected set P may be “represented” by a disconnected skeleton S which is somewhat disconcerting. Davis and Plummer [3] devised a more elaborate approach and proved that their method generates a skeleton S satisfying conditions 1, 2 and 3’.
Research on skeletonization is not over; for a given set P one may define very different sets S all of which satisfy criteria 1, 2 and 3’; thus, if P is a rectangle, the sets :9I are equally valid skeletons. Should one be preferred to the other and if so why?
Skeletons often have spurs, i.e., limbs of length one, which add little to an understanding of the shape of the figure. Should these spurs be removed while the skeleton is being produced--as suggested by Beun [4]--or should their removal wait till a later stage, as argued by Davies and Plummer?
Most important of all, the pattern on which skeletonization is to operate is often not just a binary pattern, but a grey-valued one; i.e., not just a set P but a set P together with a density function f defined on the set P. It is interesting to note that Hilditch [5] devised an algorithm to deal with this grey-weighted case, although most later authors deal only with the simpler binary version of the problem.
The authors’ contribution may be briefly summarized as follows. They define two algorithms for skeletonization, H, which they assert “truly reflects Hilditch’s approach” and S, which they assert “is the Stefanelli-Rosenfe- ld version of the . . . approach of Hilditch.” The authors exhibit two binary patterns for which H preserves and S fails to preserve the shape of the pattern.
The authors believe that in simplifying the Hilditch algorithm, Stefanelli and Rosenfeld [6] left out an important criterion with the result that the “simplified” procedure produces inferior skeletons. Your reviewer agrees with them, but to make this belief into a paper it is necessary to examine both sets of criteria and relate the different behavior of the algorithms to differences between the criteria. If the authors had done this they would have made a contribution to research in the history of skeletonization; however they go no further than the observation “thus algorithm H was able to prevent excessive erosion along slanting strokes of width 2, which algorithm S failed to do,” a statement which does not offer any explanation of the behavior.
They go on to show “that for a certain restrictive kind of data, alg H may be heuristically modified to achieve a marginal speed-up.” To put it another way, they can go 5 percent faster by abandoning one of the tests and with it the guarantee that the skeleton will have the correct properties.
Since H works correctly and S was superceded by the Davis and Plummer method the paper offers little that is new. The interested reader will find discussion of recent developments in Hilditch [7] and Davies and Plummer [3]; Rosenfeld and Kak ([1], p. 400) trace the history of the subject.