【文章內(nèi)容簡介】 eds by contour following. Examples of parallel algorithms in this third class are reduction operators which transform contour points into background points. Di_erences between these parallel algorithms are typically de_ned by tests implemented to ensure connectedness in a local neighborhood. The notion of a simple point is of basic importance for thinning and it will be shown in this report that di_erent de_nitions of simple points are actually equivalent. Several publications characterize properties of a set D of points (to be turned from object points to background points) to ensure that connectivity of object and background remain unchanged. The report discusses some of these properties in order to justify parallel thinning algorithms. Basics The used notation follows [17]. A digital image I is a function de_ned on a discrete set C , which is called the carrier of the image. The elements of C are grid points or grid cells, and the elements (p。 I(p)) of an image are pixels (2D case) or voxels (3D case). The range of a (scalar) image is f0。 :::Gmaxg with Gmax _ 1. The range of a binary image is f0。 1g. We only use binary images I in this report. Let hIi be the set of all pixel locations with value 1, . hIi = I?1(1). The image carrier is de_ned on an orthogonal grid in 2D or 3D space. There are two options: using the grid cell model a 2D pixel location p is a closed square (2cell) in the Euclidean plane and a 3D pixel location is a closed cube (3cell) in the Euclidean space, where edges are of length 1 and parallel to the coordinate axes, and centers have integer coordinates. As a second option, using the grid point model a 2D or 3D pixel location is a grid point. Two pixel locations p and q in the grid cell model are called 0adjacent i_ p 6= q and they share at least one vertex (which is a 0cell). Note that this speci_es 8adjacency in 2D or 26adjacency in 3D if the grid point model is used. Two pixel locations p and q in the grid cell model are called 1 adjacent i_ p 6= q and they share at least one edge (which is a 1cell). Note that this speci_es 4adjacency in 2D or 18adjacency in 3D if the grid point model is used. Finally, two 3D pixel locations p and q in the grid cell model are called 2adjacent i_ p 6= q and they share at least one face (which is a 2cell). Note that this speci_es 6adjacency if the grid point model is used. Any of these adjacency relations A_, _ 2 f0。 1。 2。 4。 6。 18。 26g, is irreexive and symmetric on an image carrier C. The _neighborhood N_(p) of a pixel location p includes p and its _adjacent pixel locations. Coordinates of 2D grid points are denoted by (i。 j), with 1 _ i _ n and 1 _ j _ m。 i。 j are integers and n。m are the numbers of rows and columns of C. In 3Dwe use integer coordinates (i。 j。 k). Based on neighborhood relations we de_ne connectedness as usual: two points p。 q 2 C are _connected with respect to M _ C and neighborhood relation N_ i_ there is a sequence of points p = p0。 p1。 p2。 :::。 pn = q such 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 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 o n 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。 q) from point p to point q, p 6= q, is the smallest positive integer n such that there exists a sequence of distinct grid points p = p0,p1。 p2。 :::。 pn = q with pi is a 4neighbor of pi?1, 1 _ i _ p = q the distance between them is de_ned to be zero. The distance d4(p。 q) has all properties of a metric. Given a binary digital image. We transform this