discrete structure

Elm20o

BertrandPaper.pdf

Home >Computer Science homework help >discrete structure

E L S E V I E R Pattern Recognition Letters 16 (1995) 979-986

Pattern Recognition Letters

A parallel thinning algorithm for medial surfaces Gilles Bertrand

LABO IAAL ESIEE, Citg Descartes, BP 99, 93162 Noisy-le-Grand Cedex, France

Received 6 December 1994; revised 22 February 1995

Abstract

A new 3D parallel thinning algorithm for medial surfaces is proposed. It works in cubic grids with the 6-connectivity. This algorithm is based on a precise definition of end points which are points belonging to surfaces or curves. We give a necessary and sufficient Boolean condition for characterizing points which are simple, non-ends and which are border points of a certain type (N, S, E, W, U, D). The algorithm consists precisely in removing all points satisfying the condition: it has a little computational cost and it is based on a clear thinning criterion.

Keywords: Thinning algorithms; Skeleton; Three-dimensions; Cubic grids; Discrete topology

1. I n t r o d u c t i o n

Thinning an image consists in deleting simple points which are not end points. The simple point condition ensures that the topology o f the image is unchanged and the non-end point condition allows to preserve some useful informations relative to the shape o f the objects. An example o f a commonly used notion o f end point is to consider all extremities o f curves, i.e. all points having a single neighbor (see Tamura, 1978). For designing a parallel thinning algorithm, it is also necessary to have another condition since the simulta- neous removal o f all simple points which are not end points may lead to some changes o f the topology o f the image. In the 2D case the most classical way for solving this problem is to use a directional stategy for deleting points in parallel (see Rosenfeld and Kak, 1982): border points are classified in four types N, S, E, W; a N-border point is a point having a neighbor in the north direction which belongs to the complemen- tary o f the object. A basic directional thinning scheme

consists in deleting, at each iteration, all border points o f a given type which are simple and non-en~ds.

Some parallel algorithms using a directional strat- egy have been proposed for thinning 3D objects into curves or surfaces. Most o f them use some ad hoc con- ditions for characterizing end points (e.g. Tsao and Fu, 1981; Gong and Bertrand, 1990; Mukherjee et al., 1990). In fact, characterizing 3D end points is not ob- vious: perhaps the only attempt to have such a char- acterization is the one given in (Morgenthaler, 1981 ).

In this paper, we present a 3D parallel thinning al- gorithm for medial surfaces. It works in cubic grids with the 6-connectivity. This algorithm is based on a precise definition o f end points which are points be- longing to surfaces or curves elements. This notion o f end point improves the one given in (Morgenthaler, 1981), since it is clearer and more natural. Further- more we give a necessary and sufficient Boolean con- dition for characterizing simple non-end points of a given type. It leads to a low computational cost paral- lel thinning algorithm.

980 G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986

./I ./ / / ; / " j

V ? . / / ' ./ /

/ - 7 - / - Fig. 1. The neighborhood of x; the 6-neighbors (full circles), the 1 8 - n e i g h b o r s ( full squares), the 26-neighbors (empty circles).

2 . B a s i c n o t i o n s

A point x E Z 3 is defined b y (X 1 ,X2, X3) with xi E Z. We consider the two distances:

i=3

D l ( x , y ) = ~ - ~ i Y i - - xi I and i=1

Do~(x, y ) = m a x [ Y i - xil. i=1,2,3

The associated n e i g h b o r h o o d s are

B i ( x ) = {y I D ~ ( x , y ) <<. i} and

Bi~(x) = { y l D , ( x , y ) <~ i}.

We c o m m o n l y use the f o l l o w i n g n e i g h b o r h o o d s : the 6 - n e i g h b o r h o o d N 6 ( x ) = B~ ( x ) ,

- the 1 8 - n e i g h b o r h o o d N , s ( x ) = B ~ ( x ) fq B ~ ( x ) and,

- the 2 6 - n e i g h b o r h o o d N26 ( x ) = B ~ ( x ) . We define

Ug(x) = U6(x) \ {x}, N~8(x) = NIS(X) \ {x},

N~6(X) = N 2 6 ( x ) \ {x}.

Two points x and y are said to be n-adjacent ( n = 6, 1 8 , 2 6 ) i f y E N ~ ( x ) . We call the points o f N ~ ( x ) , N~'s(X) \ N ~ ( x ) , and N~6(x) \ U~'8(x) the 6-, 18-, and 2 6 - n e i g h b o r s o f x, respectively (see Fig. 1).

To each 6 - n e i g h b o r o f x a direction d is associated (i.e. d = U, D, N, S, E or W ) as depicted in Fig. 2. A d - b o r d e r p o i n t o f X C Z 3 is a point x such that x E X and the 6 - n e i g h b o r o f x in the d-direction b e l o n g s to X.

Let X C Z 3. We d e n o t e X~ = Nn* ( x ) A X and X--ff = N ~ ( x ) N X for n = 6, 1 8 , 2 6 .

~/ N W E

Fig. 2. The 6 directions.

A n n-path is a sequence o f points x0 . . . . . x~, with xi n-adjacent to x i - t for i = 1 . . . . . k. I f x0 = Xk, the path is closed.

A n object X C Z 3 is said to be n-connected if for any two points o f X, there is an n-path in X between these two points. The equivalence classes relative to this relation are the n-connected c o m p o n e n t s o f X. As in 2D, i f we use an n-connectivity f o r X, w e have to use another W-connectivity for X. In this paper, we consider that ( n , ~ ) = ( 2 6 , 6 ) o r ( 6 , 2 6 ) .

The set o f all connected c o m p o n e n t s o f X adjacent to x is denoted C x ( x ) . N o t e that C x ( X ) is a set o f subsets o f X and not a set o f points.

I f X is finite, the infinite c o m p o n e n t o f X is the b a c k g r o u n d ; the other ones are the cavities.

In 3D the notion o f hole is not simple to define. For example, a h o l l o w ball has one cavity and no hole, a solid torus has no cavity and o n e hole, a h o l l o w torus has o n e cavity and two holes. The presence o f an n- hole in X is detected whenever there is a closed n-path in X that c a n n o t be deformed, in X, to a single point. We give here a definition o f deformation derived f r o m ( K o n g , 1989) and (Bertrand, 1 9 9 2 ) :

Let y and yl be two closed n-paths. We say that y/ is an elementary deformation o f y if yt and y are the same except in a little portion P o f Z3: if n = 26, P is a 2 × 2 x 2 unit cube, i f n = 6, P is a 2 x 2 unit square.

We say that y~ is a deformation o f y if there is a sequence o f closed paths Y0 . . . . . Yk such that Y0 = Y, Yk = yt and "Yi is an elementary deformation o f ')/i-l.

The relation o f deformation induces some equiva- lence classes which c o r r e s p o n d to the intuitive notion o f holes. T h e use o f a unit square and a unit cube for the 6- and the 26-connectivity, respectively, is neces- sary for the c o r r e s p o n d e n c e between the holes o f X and o f X.

A point x E X is said to be n-simple if its removal does not c h a n g e the t o p o l o g y o f the image, i.e., there is a o n e - t o - o n e c o r r e s p o n d e n c e between the c o m p o n e n t s , the holes o f X and X and the c o m p o n e n t s , the holes

G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986 981

/ /

y../" , . / ' _/1 / . / ,/ j , / . / y /

/ / , L~ / / / / / A I / / /

/ / / /

A6 A18 A26

/ / q / /

/ / V V

A18 A26

Fig. 3. All the configurations involved in the characterization of simple points: black and white points represent respectively |he object and its complementary.

o f X \ {x} and X U {x}; the n- and the Z-connectivity are used for X and X, respectively.

Let us consider the five configurations depicted in Fig. 3:

3. Simple points characterizations

Definition 3. We define the following five sets rela- tive to x:

In (Bertrand and Malandain, 1992), two topologi- cal numbers are introduced ( # S stands for the cardi- nality o f S) :

Definition 1. The topological numbers relative to X C Z 3 and x E Z 3 are the two numbers:

T6(x,X)=#CX(X~8) and T 2 6 ( x , X ) = # C x ( x ~ 6 ) .

I f we consider the (n, ~)-connectivity, T, (x, X) and T~(x, X) are used for describing the topological char- acteristics o f x. These two numbers allow to charac- terize 6- and 26-simple points (see Bertrand and Ma- landain, 1994) :

Proposition 2 . x is n-simple if and only if Tn( x, X ) = 1 and T,v(x, X) = 1.

A6 = {y E X such that y is a 6-neighbor o f x and N~ ( y ) n X~8 = 0}.

Als = {y E X such that y is a 18-neighbor o f x and Ng ( y ) n X---~ = 13}.

A26 = { y G X s u c h that y is a 26-neighbor o f x and N~6(y) n X~8 = 13}.

A18 = {y E X such that y is a 18-neighbor o f x and N~6(y) n X~s = 13}.

A26 = { y E X s u c h t h a t y is a 26-neighbor o f x and N ~ 6 ( y ) N i l 8 = 13}.

In (Bertrand, 1994, 1995), it is shown that these configurations are sufficient to compute the two topo- logical numbers and to have a Boolean characteriza- tion o f 6-simple points ( a 26-simple point character-

982 G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986

/ J

/ 7 / j/- J

/ j ,

J J

/ , / ,

7 7

j /

,/ . /

./ p

(b) Fig. 4. Examples.

(c)

ization may be obtained by inverting the role of X and X) :

Proposition 4 . x i s a 6-simple point iff (#X~ = 1) o r (#X~6 = 1) or (#A26 = 0,#X~8 = 1) or (#A6 = 0,#A26 = 0,#AI8 = 0,#X~ - #AI8 + #A26 = 1).

As far as we know, this is the only available Boolean characterization o f 3D simple points. This characteri- zation will help us to find a Boolean characterization o f points which are removed when using a directional strategy, i.e., simple non-end points o f a given type. Before that we have to propose a definition o f end points.

0D 1D 2 D Fig. 5. kD-elements.

arcs, surfaces, and thick objects. Nevertheless, accord- ing to that definition, the central point in Fig. 4 ( c ) is not an end. In order to include such cases and to have a more natural definition o f end points we propose the notion of k-dimensional cell (see Figs. 5 and 6).

4. The end point characterization and the algorithm

In this section, we will use the 6-connectivity for X and the 26-connectivity for X.

A thinning algorithm for medial surfaces iteratively delete simple border points provided curves and sur- faces are preserved. For that last purpose it is neces- sary to have an end points characterization which must detect points belonging to curves or surfaces. Perhaps the only available characterization corresponding to such an approach is the one proposed in (Morgen- thaler, 1981 ): an octant Q o f N26 (X) (i.e., a 2 x 2 x 2 cube) is thin if x and every point o f X n Q directly adjacent to x are adjacent (in the X sense) to a point o f X n Q. We say that x is an end if x or one o f its immediate neighbors is in no non-thin octants. Exam- ples o f 6-ends are given in Figs. 4 ( a ) and 4 ( b ) : these points are ends since they occur at the jonctions o f

Definition 5. A 3D-element is a 2 x 2 x 2 cube; a 2D- element is a 2 x 2 square; a 1D-element is a couple o f adjacent points; a 0D-element is a point.

Let X C Z 3. A 3D-cell is a 3D-element included in X. A kD-cell is a kD-element included in X which is not included in a (k + 1)D-cell, for k = 2, 1,0.

We see that the central points in the three configu- rations o f Fig. 4 are characterized by the fact that they belong to 2D or 1D cells.

We give now a basic topological property o f points which have not such a characteristic (see also (Hall, 1992) and (Ma, 1994) who propose sufficient condi- tions for removing points in parallel without altering the topology o f the image).

Proposition 6. A d-border point which does not be- long to any 2D- or 1D- or OD-cell is a simple point. Furthermore the removal o f any set o f such points does not change the topology o f the image.

G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986 983

(a)

~-------~ l---

( b )

Fig. 6. An object X represented by voxels ( a ) and by cells ( b ) : X is composed o f 23 voxels (i.e. 23 points) and it contains four 3D-cells, one 2D-cell and one ID-cell.

Y ' / / z / ' y u d ~

z ' / / "

/ A

X I / /

• / t h e D - w i n d o w

Fig. 7. The neighborhood o f a U-border point.

Proof. ( See Fig. 7.) Let us consider a point x which is a U-border point which does not belong to any 2D- or 1D- or 0D-cells. This point must belong to at least one 3D-cell. It follows that its D-neighbor d necessarily belongs to X. Let y be a 6-neighbor o f x in the N, S, E or W directions. Suppose y E X. The 1D-element {x, y} must be included in a 3D-cell so that the point z which is the D-neighbor o f y necessarily belongs to X. It follows that d and y are connected inside X~8. So we can see that T 6 ( x , X ) = 1.

Furthermore, if y E X, the points d and z are not U- border points so we can see that T 6 ( x , X ) will remain as it is if any set o f U-border points is removed.

Let us consider now the connected components o f X~6. Since the U-neighbor u o f x belongs to X, the only possibility to have more than one connected com- ponent in X~6 is to have a point p in the D-window o f x belonging to X (the D-window is the 3 × 3 hor-

_A _7 /

• j

/ ' . 7 e"

Fig. 8. A counterexample.

izontal square containing d ) and not connected to u. The point p could be in a position such as z or z~: in both cases the points y, y~, yH must belong to X. This is impossible, since, in this case, the 2D-element {x, y, yt, ytt} would not belong to a 3D-celL Hence T 2 6 ( x , X ) = 1.

Furthermore let us consider any U - b o r d e r point t belonging to the D-window o f x. Let u ~ b e the U- neighbor o f t: uu~t defines a 26-path. Hence we can see that T26(x,X) will remain as it is if any set o f U-border points is removed. []

A U-border point which does not belong to kD cells, for k = 0, 1,2, is a simple point. Nevertheless there are some points which do not belong to kD ~ells, for k = 0, 1,2, and which are not simple: such a case is depicted Fig. 8. We see that these cases correspond to a bottle neck o f the object: the contour o f the object (i.e. a surface) folds upon itself leading to "singular elements". We now present a characterization o f such elements.

Definition 7. A 0D- or 1D-element is a singular ele- ment if it is included in X and it is contained in only two 3D-cells which are not sharing a 2D-element.

We now propose the definition o f end points. We include points belonging to singular elemenls in the definition since such elements may be viewed as de- generated 1D- or 2D-cells.

Definition 8. A d-border point is an end point if it belongs to a kD-cell, for k = 0, 1,2, or if it belongs to a singular element.

The following property gives a Boolean character- ization o f end points which uses the configurations presented in the preceding section.

984 G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986

/ / /~ / /

j j / - / -

/ J / • / /

J 7 / / , / - / - T > ', '/ 7 v

C, C2 C3

C4 C5 Fig. 9. The configurations of U-border points which do not belong to kD-cells, k = 0, I, 2.

P r o p o s i t i o n 9. A d-border point is not an end point i f and only i f

[#A26 = 0] A [#A26 ~(0] A [#X~ ~< #A26 + 2 ] . ( 1 )

P r o o f . L e t us c o n s i d e r a U - b o r d e r p o i n t x w h i c h d o e s not b e l o n g to a kD-cell, f o r k = 0, 1,2. It m u s t b e l o n g to a 3D-cell and it m a y b e seen that it m a y b e l o n g to 1, 2, 3 o r 4 3D-cells. B y c o n s i d e r i n g each case, w e can see that x c o r r e s p o n d s to o n e o f the 5 configurations d e p i c t e d in Fig. 9. I n the configuration Ca the p o i n t x b e l o n g s to a s i n g u l a r element, so x is not an end p o i n t i f and o n l y i f it c o r r e s p o n d s to the configurations C l , C2, C3, C5. B y c o n s i d e r i n g each configuration, w e n o t e that a U - b o r d e r p o i n t is in the configuration Ci i f and o n l y i f - f o r i = 1: ( # X 6 ~ 6 ) , # A 2 6 = 4 and ( # A 2 6 = 0 ) .

f o r i = 2 : ( # X 6 ~< 5 ) , # A 2 6 = 3 and # A 2 6 = 0. f o r i = 3 : # X 6 ~-~ 4 , # A 2 6 = 2 and ( # A 2 6 = 0 ) . f o r i = 5 : # X 6 ~ 3 , # A 2 6 = 1 and ( # A 2 6 = 0 ) .

T h e c o n d i t i o n s w h i c h are in p a r e n t h e s e s could b e o m i t t e d . W e h a v e i n c l u d e d t h e m in order to s h o w that these f o u r cases m a y b e c o n d e n s e d into the condition (1). []

W e note that, d u e to P r o p o s i t i o n 3, a p o i n t is s i m p l e and not an end p o i n t i f and o n l y i f it satisfies the c o n d i t i o n ( 1 ). This allows us to p r e s e n t the p r o p o s e d thinning algorithm. It consists in using the classical directional stategy f o r thinning ( s e e R o s e n f e l d and Kak, 1982) and m a y b e stated as follows.

Delete all d-border points which are simple and not end points, i.e., all d-border points satisfying the con- dition ( 1 ). Do it successively f o r d = U, B, N, S, E, W . Repeat until there is no change.

S o m e results given b y this a l g o r i t h m are p r e s e n t e d in Fig. 10.

I n the 2 D case s o m e thinning a l g o r i t h m s using o n l y t w o subiterations have been p r o p o s e d . In o u r case w e can see that it is not p o s s i b l e to use less than 6 subit- erations. This p o i n t m a y b e verified on the c o u n t e r e x - a m p l e given in Fig. 11 ( a ) : if, f o r e x a m p l e , the U - b o r d e r p o i n t s and the N - b o r d e r p o i n t s are c o n s i d e r e d in parallel f o r deletion, w e see that the t w o p o i n t s x and y will b e suppressed; the o t h e r p o i n t s will r e m a i n ( t h e y are end p o i n t s ) , so that a h o l e will b e created in the object. W e c o u l d try to use a m o r e restrictive c o n - dition than the condition ( 1 ) in o r d e r to avoid these

G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986 985

Fig. 10. Two examples of thinned objects.

.7 / .

(a) (b) Fig. I I. Two counterexamples.

cases and to have a thinning algorithm requiring less sub-iterations. The drawback o f such an approach is that we would not eliminate all simple points which are not end points.

5. Discussion and conclusion

We have proposed a 3D parallel thinning algorithm which works with the 6-connectivity. It corresponds exactly to the extension, for the 3D case, o f the basic 2D directional thinning scheme presented in: the in- troduction. It follows also the approach o f (Morgen- thaler, 1981) where a precise definition o f end points is given. We have tried to improve this definition. Fur- thermore, we have proposed a necessary and sufficient Boolean condition for points which are to b e deleted (in (Morgenthaler, 1981) no implementation is con- sidered).

Is it possible to have such a thinning scheme using the 26-connectivity? Let us consider the pattern P de-

986 G. Bertrand~Pattern Recognition Letters 16 (1995) 979-986

picted in Fig. 11 ( b ) : since it consists in four mutually 26-adjacent points not belonging to a plane, P may be considered as a 3D pattern. Hence, the 4 points are not 26-ends; furthermore they are also 26-simple and U-border points. Thus, we see that the basic di- rectional thinning scheme cannot be used with the 26- connectivity, otherwise patterns like P would be com- pletely deleted and the topology o f an image could be modified. Some authors introduce some extra condi- tions for insuring the topological soundness o f some algorithms based upon a directional thinning scheme (e.g. Tsao and Fu, 1982; Gong and Bertrand, 1990): U-border points which are simple and not end points must satisfy other conditions in order to be deleted. The drawback is that these algorithms are not com- plete: they do not remove all points which could be removed. Complete thinning algorithms for the 26- connectivity are proposed in (Bertrand and Aktouf, 1994) where a thinning scheme based upon subfields is considered.

References

Bertrand, G. (1992). Characterizations of three-dimensional holes. Internal report, ESIEE.

Bertrand, G. (1994). On the computation of topological numbers. Proc. 4th Conf. on Discrete Geometry f o r Comp. Imagery, 137- 146.

Bertrand, G. (1995). A Boolean characterization of three- dimensional simple points. Pattern Recognition Lett., submitted.

Bertrand, G. and Z. Aktouf (1994). A 3D thinning algorithm using subfields. Proc. SPIE Conf. on Vision Geometry III, Vol. 2356, 113-124.

Bertrand, G. and G. Malandain (1992). A new topological classification of points in 3D images. Proc. European Conf. on Computer Vision, 710-714.

Bertrand, G. and G. Malandain (1994). A new characterization of three-dimensional simple points. Pattern Recognition Lett. 15, 169-175.

Gong, W.X. and G. Bertrand (1990). A simple parallel 3D thinning algorithm. Proc. lOth lnternat. Conf. on Pattern Recognition, 188-190.

Hall, R.W. (1992). Connectivity preserving parallel operators in 2D and 3D images. Proc. SPIE Conf. on Vision Geometry 1, Vol. 1832, 172-183.

Kong, T.Y. (1989). A digital fundamental group. Computer Graphics 13, 159-166.

Kong, T.Y. and A. Rosenfeld (1989). Digital topology: introduction and survey. Computer Vision, Graphics, and Image Processing 48, 357-393.

Ma, C.M. (1994). Sufficient conditions for 3D 6-subiteration parallel thinning algorithms to preserve connectivity. Proc. SPIE Conf. on Vision Geometry 111, Vol. 2356, 46-52.

Morgenthaler D.G. (1981). Three dimensional simple points: serial erosion, parallel thinning, and skeletonization. TR-1005, Computer Science Center, Univ. of Maryland, College Park, MD.

Mukherjee, J., P.P Das and B.N. Chatterji (1990). On connectivity issues of ESPTA. Pattern Recognition Lett. 11,643-648.

Rosenfeld, A. and A. Kak (1982). Digital Picture Processing. Academic Press, New York.

Tamura, H. (1978). A comparison of line thinning algorithms from digital geometry viewpoint. Proc. 4th lnternat. Conf. on Pattern Recognition, 715-719.

Tsao, Y.E and K.S. Fu (1982). A 3D parallel skeletonwise thinning algorithm. Proc. IEEE Pattern Recognition Image Processing Conf., 678-683.