Theory

For a positive integer M, an M-semisegmentation of a set V of spels is a function a that maps each c e V into an (M + 1)-dimensional vector ac = (a£, ajc, ..., a'M), such that

1. a0c e [0, 1] (i.e., it is nonnegative but not greater than 1),

2. for each m the value of am is either 0 or a£, and

3. for at least one m in the range 1 < m < M, am = a£.

We say that a is an M-segmentation if, for every spel c, a0 is positive.

If there are multiple objects to be segmented, it is reasonable that each should have its own fuzzy spel affinity. For images this idea is discussed in [27], here it is generalized by the following concepts. An M -fuzzy graph is a pair (V, where V is a nonempty finite set and ^ = ,..., ) with tym (for 1 < m < M) being a fuzzy spel affinity. A seeded M-fuzzy graph is a triple (V, V), where (V, is an M-fuzzy graph and V = (V1,..., VM), where Vm c V, for 1 < m < M .A seeded M-fuzzy graph is connectable if

1. the set V is (min1<m<M tym)-connected (we define (min1<m<M ty^ (c, d) = min1<m<M fm (c, d)) and

For an M-semisegmentation a of V and for 1 < m < M, the chain (c(0),..., c(K)) is said to be a am-chain if a!^ > 0, for 0 < k < K. Furthermore, for W c V and c e V, we use ^a,m,w (c) to denote the maximal tym-strength of a a m-chain from a spel in W to c. (This is 0 if there is no such chain.)

Theorem 1.1. If (V, V) is a seeded M-fuzzy graph, then

(i) there exists an M-semisegmentation a of V with the following property: for every c e V, if for 1 < n < M

I maxdeV(min(ixanyn(d), ^n(d, c))) otherwise, then for 1 < m < M

m I 0 otherwise,

(ii) this M-semisegmentation is unique, and

(iii) it is an M-segmentation, provided that (V, V) is connectable.

Before discussing the validity of Theorem 1.1, we discuss in less mathematical terms what it says. The property stated in Theorem 1.1 is a reasonable one, as can be seen in Fig. 12.2. Let c be an arbitrary spel and suppose that ad is known for all other spels d. Then, for 1 < n < M (M = 3 in Fig. 12.2), the scn of Eq. (12.4) is the maximal ^-strength of a chain (d(0\..., d(L), c) from a (seed) spel in Vn to c such that a^ > 0 (i.e., d® belongs to the nth object), for 0 < l < L. (sn is defined to be 0 if there is no such chain.) Intuitively, the mth object can

Figure 12.2: Illustration of the desirability of the M -segmentation whose existence (and uniqueness) is guaranteed by Theorem 1.1.

"claim" that c belongs to it if, and only if, scm is maximal and is greater than 0. This is indeed how things get sorted out in Eq. (12.5): —m has a positive value only for such objects. Furthermore, this is a localized property in the following sense: for a fixed spel c we can work out the values of the scn using Eq. (12.4) and what we request is that, at that spel c, Eq. (12.5) be satisfied. What Theorem 1.1 says that there is one, and only one, M-semisegmentation that satisfies this property simultaneously everywhere, and that this M-semisegmentation is in fact an M-segmentation, provided that the seeded M-fuzzy graph is connectable.

Now we illustrate the Theorem 1.1 for the seeded two-fuzzy graph (V, V) definedby V = {(-1), (0), (1)} and ^ = 1, ^ 2), where ^ xand ^ 2 are the reflexive and symmetric fuzzy spel affinity functions (i.e., ^m(c, c) = 1 and ^m(c, d) = ^m(d, c) for 1 < m < 2 and c, d e V) defined by the additional conditions ^((-1), (0)) = 0.5, ^((0), (1)) = 0.25, ^((-1), (1)) = 0, ?2((-1), (0)) = 0.5, ^2((0), (1)) = 0.5, ?2((-1), (1)) = 0, and V = ({(0)}, {(-1)}). The two-segmentation — of V that satisfies Theorem 1.1 is given by = (1, 0, 1), a(0) = (1,1, 0), and —(1) = (0.25, 0.25, 0). To test this suppose, for example, that we have been informed that a-1) = (1, 0, 1) and —0 = (1, 1, 0) and we wish to use the Theorem 1.1 to determine —^ We find that s(1) = 0.25 (obtained by the choice d = (0)) and s® = 0 (if we choose in Eq. (12.4) d to be (-1), then ^ 2((-1), (1)) = 0,ifwe choose it to be (0), then 2,(-i)(0) = 0 since there is no —2-chain containing (0), because — 20) = 0). Hence Eq. (12.5) tells us that indeed —(1) = (0.25, 0.25, 0). Note that there is a chain ((-1), (0), (1)> of ^-strength 0.5 from the seed spel (-1) of Object 2 to (1), while the maximal ^ 1-strength of any chain from the seed spel (0) of Object 1 to (1) is only 0.25; nevertheless, (1) is assigned to Object 1 by Theorem 1.1, since the fact that (0) is a seed spel of Object 1 prevents it (for the given ^) from being also in Object 2, and so the chain ((-1), (0), (1)> is "blocked" from being a —2-chain.

An intuitive picture of the inductive definition of the M-semisegmentation of Theorem 1.1 is given by the following description of a military exercise. There are M armies (one corresponding to each object) competing for the control of N castles that are connected by one-way roads between them. Initially all armies have full strength (defined to be 1) and they occupy their respective castles (seed spels). All armies try to increase their respective territories, but the moving from a castle to another one reduces the strength of the soldiers to the minimum of their strength at the previous castle and the affinity (for that army or object) of the road connecting the castles. The affinities of the roads for the various armies are fixed for the duration of the exercise.

All through the exercise each castle will also have have a strength assigned to it, which is a real value in the range [0, 1]. The strength of a castle may increase as the exercise proceeds. Also, at any time, each castle may be occupied by one or more of the armies.

The objective of the exercise is to see how the final configuration of occupied castles depends on the initial castle assignment to the various armies. Since we are describing an algorithm here, the individual armies have to follow fixed rules of engagement, which are the following.

The exercise starts by distributing the soldiers of the armies into some of the castles and assigning to those castles that have soldiers in them (and to the soldiers themselves) the strength 1 and to all other castles the strength 0. We say that this distribution of armies and strengths describes the situation at the start of Iteration 1. At any given time, a castle will be occupied by the soldiers of the armies that were not weaker than any other soldiers who reached that castle by that time.

The exercise proceeds in discrete iterative steps and the total number of iterations (NI) is determined by the number of distinct affinity values for all armies and roads. These values are put into a strictly decreasing order and the strength of the iteration i (IS(i)) is defined as the ith number of this sequence. The following gets done during Iteration i. Those soldiers (and only those soldiers) that occupy a castle of strength IS(i) will try to increase the territory occupied by their army. They will send units from their castle toward all the other castles. When these units arrive at another castle, their strength will be defined as the minimum of IS(i) and the affinity for their army of the road from the originally occupied castle to the new one. If the strength of the new castle is greater than the strength of any of the armies arriving at it, the strength and occupancy of the castle will not change. If no arriving army has greater strength than the strength of the new castle, then the strength of the new castle does not change, but it will get occupied also by those arriving armies whose strength matches that of the castle (but not by any of the others). If some of the arriving armies have greater strength than the strength of the castle, then the castle will be taken over by those (and only those) arriving armies that have the greatest strength, and the strength of the castle is set to the strength of the new occupiers. This describes what happens in one iterative step except for one detail: if an army gets to occupy a new castle because its strength is IS(i) (this can only happen if the affinity for this army of the road to this castle is at least IS(i)), then that army is allowed to send out units from this new castle as well. (This cannot lead to an infinite loop, since there are only finitely many castles and so it can only happen finitely many times that an army gets to occupy a new castle because its strength is IS(i).)

The exercise stops at the end of Iteration NI. The output of the exercise provides, for each castle, the strength of the castle and the armies that occupy it at the end of the exercise.

Proof of Theorem 1.1(i). In this existence proof (first published in [28]) we provide an inductive definition that resembles both the description above and the actual algorithm that is described later on. However, this inductive definition is not strictly identical to the algorithm since it was designed to make our proof simple, while the algorithm was designed to be efficient. (In fact, the picturesque description above is nearer to the algorithm than to the inductive definition that follows.)

Let R = {1} U [fm(c, d) > 0 11 < m < M, c, d e V}. R is a finite set of real numbers from (0, 1], and so its elements can be put into a strictly decreasing order 1 = V > 2r > ••• > |R|r > 0. We define inductively a sequence of M-semisegmentations 1a, 2a,..., |R|a and a sequence lU, 2U,..., 1RU of subsets of V as follows.

1 if there is a chain of ^m-strength 1 from a seed in Vm to c, 0 otherwise.

(Here, and later, the definition of ia£ implicitly follows from the fact that ia is an M-semisegmentation.) For 1 < i < |R|, we define iU = {c | V0c > V}. (12.7)

For 1 < i < |R|, c e V, and 1 < m < M, we define

(i-1) am, if c e (i-1) U, ir if there is a chain (c(0),..., c(K)) of ^m-strength ir such that c(0) e (i-1)U, (i-1)am(0) > 0, (12.8)

c(K) = c and, for 1 < k < K, c(k) / (i-1)U, 0 otherwise.

It is obvious from these definitions that V is an M-semisegmentation, for 1 <

We now demonstrate the definitions on the seeded two-fuzzy graph (V, V) discussed above. In this case R = {1, 0.5, 0.25}. It immediately follows from Eq. (12.6) that 1a(-1) = (1, 0, 1), 1a(0) = (1, 1, 0), and 1a(1) = (0, 0, 0). It turns out that 2a = 1a. This is because 1U = {(-1), (0)}, and there are no chains starting at either of these spels which satisfy, for i = 2, all the conditions listed in the second line of Eq. (12.8). On the other hand, the chain ((0), (1)} canbeused to generate 3 a, which is in fact the 2-segmentation specified by the condition of Theorem 1.1. This is not an accident, we are now going to prove that in general the |R|a defined by Eq. (12.6)-(12.8) satisfies the property stated in Theorem 1.1(i).

It clearly follows from the definitions (12.6) and (12.8) that, for c e V and 1 < m < M, 1 R|< e R U {0}. Furthermore, it is also not difficult to see, for 1 < i < |R|, that if c e iU, then Vm = |R|am, and that iU = {c ||R|a0c > V} . (12.9)

These imply the following two properties of the M-semisegmentation |R|a.

(A) For c e V and 1 < m < M, |R|am = 1 if, and only if, there is a chain of ^„-strength 1 from a seed in Vm to c.

(B) For c e V ,1 < m < M,and2 < i < |R|,| R|am = ir if, and only if, there is a chain(c(0), •••, c(K)) of ^-strengthir such that c(0) e (i-1)U, |R|a,m(0) > 0, c(K) = c and, for 1 < k < K, c(k) / (i-1)U.

Let c, d e V. We say that (c, d) is consistent if, for 1 < m < M, |R|am = |R|a,c implies that one of the following is true:

0 0

Post a comment