A TOPOLOGICAL CHARACTERIZATION OF
Christian Ronse · 1986
A large number of skeletonization algorithms for binary images use the method of thinning: successive layers of pixels are deleted from the figure until it becomes one pixel thick. In this paper we analyze the topological properties of the set D of pixels to be deleted from a figure F in order to get a skeleton. We characterize them by the concept of strong k-deletability (k = 4 or 8). For individual pixels, strong k-deletability is equivalent to a more general property that we call k-deletability, which is a well-known connectivity requirement assumed--at least implicitly--in all existing thinning algorithms. We show then that a strongly k-deletable subset D of a figure F can be deleted by a succession of deletions of individual pixels Pl,..., Pt, where each Pl is k-deletable from F\{pjIj< i}. This justifies our definition of strong deletability and shows that any topologically valid skeleton can be obtained by some thinning process. One can find in the literature a large number of algorithms producing skeletons from arbitrary binary images. Most of them use the method of thinning: successive layers of pixels are deleted from the figure until it becomes one pixel thick. In general, the pixels are deleted according to certain criteria based on the configuration of white and black pixels in their 8-neighbourhood. We do not intend to list them; we can give as examples the algorithms of (2) and (8), which are sequential and parallel respectively. The features which must be retained in the skeletonization process are of a 'topological' or 'geometrical' nature (see also (1 )). The 'digital topology' considered here is based on the adjacency relations between pixels and has a different meaning from what one calls 'topology' or 'discrete topology' in mathematics (based on open and closed sets), although some concepts (connectedness, holes, Euler numbers, etc.) can be defined in both. In fact, the topological requirements of skeletonization can be stated in very rigorous terms, while the geometrical requirements are more vague and admit different~mathematical formulations. In this paper we study the topological aspects of the skeletonization process. Although one often claims that the topological requirements of thinning are well