【文章內(nèi)容簡介】 poses 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。 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 _ n. If 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 image into a new one which represents at each point p 2 hIi the d4distance to pixels having value zero. The transformation includes two steps. We apply functions f1 to the image I in standard scan order, producing I_(i。 j) = f1(i。 j。 I(i。 j)), and f2 in reverse standard scan order, producing T(i。 j) = f2(i。 j。 I_(i。 j)), as follows: f1(i。 j。 I(i。 j)) = 8: 0 if I(i。 j) = 0 minfI_(i ? 1。 j)+ 1。 I_(i。 j ? 1) + 1g if I(i。 j) = 1 and i 6= 1 or j 6= 1 5 m+ n otherwise f2(i。 j。 I_(i。 j)) = minfI_(i。 j)。 T(i+ 1。 j)+ 1。 T(i。 j + 1) + 1g The resulting image T is the distance transform image of I. Note that T is a set f[(i。 j)。 T(i。 j)] : 1 _ i _ n ^ 1 _ j _ mg, and let T_ _ T such that [(i。 j)。 T(i。 j)] 2 T_ i_ none of the four points in A4((i。 j)) has a value in T equal to T(i。 j)+1. For all remaining points (i。 j) let T_(i。 j) = 0. This image T_ is called distance skeleton. Now we apply functions g1 to the distance skeleton T_ in standard scan order, producing T__(i。 j) = g1(i。 j。 T_(i。 j)), and g2 to the result of g1 in reverse standard scan order, producing T___(i。 j) = g2(i。 j。 T__(i。 j)), as follows: g1(i。 j。 T_(i。 j)) = maxfT_(i。 j)。 T__(i ? 1。 j)? 1。 T__(i。 j ? 1) ? 1g g2(i。 j。 T__(i。 j)) = maxfT__(i。 j)。 T___(i + 1。 j)? 1。 T___(i。 j + 1) ? 1g The result T___ is equal to the distance transform image T. Both functions g1 and g2 de_ne an operator G, with G(T_) = g2(g1(T_)) = T___, and we have [15]: Theorem 1 G(T_) = T, and if T0 is any subset of image T (extended to an image by having value 0 in all remaining positions) such that G(T0) = T, then T0(i。 j) = T_(i。 j) at all positions of T_ with nonzero values. Informally, the theorem says that the distance transform image is reconstructible from the distance skeleton, and it is the smallest data set needed for such a reconstruction. The used distance d4 di_ers from the Euclidean metric. For instance, this d4distance skeleton is not invariant under rotation. For an approxi