【正文】 h that pi is an _neighbor of pi?1, for 1 _ i _ n, and all points on this sequence are either in M or all in the plement of M. A subset M _ C of an image carrier is called _connected i_ M is not empty and all points in M are pairwise _connected with respect to set M. An _ponent of a subset S of C is a maximal _connected subset of S. The study of connectivity in digital images has been introduced in [15]. It follows that any set hIi consists of a number of _ponents. In case of the grid cell model, a ponent is the union of closed squares (2D case) or closed cubes (3D case). The boundary of a 2cell is the union of its four edges and the boundary of a 3cell is the union of its six faces. For practical purposes it is easy to use neighborhood operations (called local operations) on a digital image I which de_ne a value at p 2 C in the transformed image based on pixel 4 values in I at p 2 C and its immediate neighbors in N_(p). 2 Noniterative Algorithms Noniterative algorithms deliver subsets of ponents in specied scan orders without testing connectivity preservation in a number of iterations. In this section we only use the grid point model. \Distance Skeleton Algorithms Blum [3] suggested a skeleton representation by a set of symmetric a closed subset of the Euclidean plane a point p is called symmetric i_ at least 2 points exist on the boundary with equal distances to p. For every symmetric point, the associated maximal disc is the largest disc in this set. The set of symmetric points, each labeled with the radius of the associated maximal disc, constitutes the skeleton of the set. This idea of presenting a ponent of a digital image as a \distance skeleton is based on the calculation of a speci_ed distance from each point in a connected subset M _ C to the plement of the subset. The local maxima of the subset represent a \distance skeleton. In [15] the d4distance is specied as follows. De_nition 1 The distance d4(p。 j are integers and n。 1。 1 Digital Image Processing 1 Introduction Many operators have been proposed for presenting a connected ponent n a digital image by a reduced amount of data or simplied shape. In general we have to state that the development, choice and modi_cation of such algorithms in practical applications are domain and task dependent, and there is no \best method. However, it is interesting to note that there are several equivalences between published methods and notions, and characterizing such equivalences or di_erences should be useful to categorize the broad diversity of published methods for skeletonization. Discussing equivalences is a main intention of this report. Categories of Methods One class of shape reduction operators is based on distance transforms. A distance skeleton is a subset of points of a given ponent such that every point of this subset represents the center of a maximal disc (labeled with the radius of this disc) contained in the given ponent. As an example in this _rst class of operators, this report discusses one method for calculating a distance skeleton using the d4 distance function which is appropriate to digitized pictures. A second class of operators produces median or center lines of the digital object in a noniterative way. Normally such operators locate critical points _rst, and calculate a speci_ed path through the object by connecting these points. The third class of operators is characterized by iterative thinning. Historically, Listing [10] used already in 1862 the term linear skeleton for the result of a continuous deformati