## Ra0d min Ra0c fmc d and R Ra0d1212

We now show that, for all c, d e V, (c, d) is consistent.

To do this, we assume that there is a (c, d) and an m such that |R|am = |R|ac and yet none of Eqs. (12.10)-(12.12) holds and show that this leads to a contradiction. A consequence of our assumption is that c = d and at least one of the following must be the case:

1 Biad = min (|RV0c, fm(c, d)) and ^a^ = IRIad■ (12.14)

We may assume that IRIaC > 0 and that ^m(c, d) > 0, for otherwise one of Eqs. (12.11) or (12.12) clearly holds. Hence 1 RIa^ = 1 RIa£ = ir, for some 1 < i < |R|. From Eqs. (12.13) and (12.14) it follows that IRIad < ir. It then follows from Eq. (12.9) that if i > 2, then neither c nor d is in (i-1)U.

If i = 1, then by A there is a chain of ^„-strength 1 from a seed in Vm to c. If i > 2, then by B there is a chain (c(0),..., c(K)) of ^„-strength V such that c(0) e (i-1)U, IRIa,m0 > 0, c(K) = c, and, for 1 < k < K, c(k) / (i-1)U. In both cases, either d is already in the chain or we can extend the chain without losing its just stated property to d, and so A or B implies that IBIamo = ir. It follows that if f-m(c, d) > ir Eq. (12.12) holds, a contradiction. So assume that ^m(c, d) = jr for some j > i. Since Eq. (12.13) or (12.14) holds, we get that d / (j-Y)U. But c e (j-Y)U, and so, applying B to the chain {c, d), we get that IRIam = jr. This implies that Eq. (12.12) holds. This final contradiction completes our proof that, for all c, d e V, (c, d) is consistent.

Next we show that, for all c e V and 1 < m < M,

To simplify the notation, we use in this proof s to abbreviate IRIam. Recall that XiR a,m,Vm(c) denotes the maximal fm-strength of an 1 R 1 am-chain from a seed in Vm to c. Note that we can assume that s e R, for the alternative is that s = 0 in which case there can be no 1 Rlam-chain that includes c and so the right-hand side of Eq. (12.15) is also 0 by definition. Our proof will be in two stages: first we show that there is an IRIam-chain from a seed in Vm to c of f m-strength s and then we show that there is no 1 Rlam-chain from a seed in Vm to c of fm-strength greater than s.

To show the existence of an1 Rlam-chain from a seed in Vm to c of f m-strength s, we use an inductive argument. If s = V = 1, then the desired result is assured by A. Now let i > 1 and s = ir. Assume that, for 1 < j < i, whenever a spel d is such that 1 Rlam = jr, then there is an IRIam-chain from a seed in Vm to d of fm-strength jr.

By B there is a chain (c(0),..., c(K)) of ^„-strength s such that c® e U, 1 > 0, c(K) = c, and, for 1 < k < K, c(k / (i—1)U. We are now going to show that (c(0),..., c(K)) is an |R|am-chain by showing that, for 1 < k < K, 1 R|amf} = s. Otherwise, consider the smallest k > 1 that violates this equation. Then we have that |R|atm* 1) > s and ^amf*1 < s (recall that c® / ^^U and so 1 ^a^ < s). This combined with the fact that fm(c(k—1), c®) > s violates the consistency of (c(k—1), c®). Since c® e (i—1)U and |R|am(0:> > 0, |^omf0 = jr for some 1 < j < i and, by the induction hypothesis, there is an |R|am-chain from a seed in Vm to c® of ^„-strength jr > s. Appending (c(0),..., c(K^ to this chain we obtain |R|am-chain from a seed in Vm to c of ^„-strength s. (Just appending may not result in a chain, since a chain is defined as a sequence of distinct spels. However, this is easily remedied by removing, for a repeated spel in the sequence, all the spels between the repetitions and one of the repetitions.)

Now we show that there is no |R|am-chain from a seed in Vm to c of ^m-strength greater than s. This is clearly so if s = 1. Suppose now that s < 1 and that (c(0),..., c(K)) is an |R|am-chain from a seed in Vm of ^„-strength t > s. We now show that, for 0 < k < K, |^a^ > t. From this it follows that c(K) cannot be c and we are done. Since c® is a seed in Vm, '^amf0 = 1 > t. For k > 0, induction that makes use of the consistency of (c(k—1), c®) leads to the desired result.

Toshowthat a = |R|a satisfies the property stated in Theorem 1.1(i), we first make two preliminary observations:

(A) For any c e V and 1 < m < M, if an > 0, then scn = an = ofi. (The first equality follows from Eqs. (12.14) and (12.15), and the second from the definition of M-semisegmentation.)

(B) For any c e V and 1 <n< M, if a® = 0 and a^ > 0, then scn < a0c. (Assume the contrary. It cannot be that scn is defined by the first line of Eq. (12.4), for then c e Vn and by A we would have that a£ = 1. Hence scn is defined by the second line of Eq. (12.4) using some d such that min a,n,Vn(d), c)) = scn > a^ > 0. Hence, by Eq. (12.15) and > a0c > 0 and so a0d = and > a0c. Interchanging c and d in the definition of consistency, we see that Eq. (12.10) cannot hold since ad > 0 and = 0, (12.11) cannot hold since a^ < ad, and (12.12) cannot hold since = 0 and a0 > 0. This contradiction with the consistency of (d, c) proves B.)

To complete the proof, let c e V. We first assume that a0 = 0. Let 1 < n < M. By the definition of M-semisegmentation, an = 0. It follows from A that c g Vn and so scn is defined by the second line of Eq. (12.4). If scn were greater than 0, then there would have to be a d e V and a chain of positive tyn-strength from Vn to d, such that c) > 0. But then, that chain to d either contains c or could be extended to a chain of positive tyn-strength from Vn to c; either case would imply by Eq. (12.15) that an > 0. Hence scn = 0, and since this is true for 1 < n < M, Eq. (12.5) holds for 1 < m < M.

We now assume that a0c > 0. By the definition of an M-semisegmentation, for 1 < m < M, either an = a0 (and there is at least one such n) or an = 0. In the first case we have, by A, that scn = an = a0, and in the second case we have, by B, that scn < a0. From this it again follows that Eq. (12.5) holds for 1 < m < M. □

Next we show that such M-semisegmentation is unique. The following proof was first published in [29].

Proof of Theorem 1.1(H). Suppose that there are two different M-semisegmentations a and t of V having the stated property. We choose a spel c, such that ac = tc, but for all d e V such that max(a^, T0d) > max(a0c, t£), ad = t d. Without loss of generality, we assume that a0 > t0 , from which it follows that, for some m e{1,...,M}, am > Tm (> 0) and so, by Eq. (12.5), am = scm and c e Vm. This implies that there exists a am-chain (d(0),..., d(L)) in V of tym-strength not less than am(> 0) such that d(0) e Vm and tym(d(L), c) > am. Next we show that (d(0),..., d(L)) is a tm-chain.

We need to show that for 0 < l < L, t m > 0. This is true for 0, since d(0) e Vm. Now assume that it is true for l — 1 (1 < l < L). Since (d(0),..., d(l-1)) is a tm-chain in V of tym-strength at least ac(> 0) from an element of Vm, we have that pT,m,V„(d(l—1->) > am. Since we also know that tym(d(l—1), d®) > am, we get that m > am (where t is defined for t as s is defined for a in Eq. (12.4)). The only way Tmm(l) could be 0, if there were an n e{1,..., M} such that max^d®, t^®) > Tf = Tdf) = tdf) > m > am = a0 = max(a0, t0). By the choice of c, this would imply that ad® = tdff), which cannot be since a_m(l) = 0.

From the facts that (d(0),..., d(L)j is a tm-chain of tym-strength not less than am and that tym(d(L), c) > am, it follows that T0 > tm > am = a0 > T0, implying that all the inequalities are in fact equalities. But then am = tm = tm, contradicting am > Tm and thereby validating uniqueness. □

Finally we show that provided that (V, V) is connectable, any M-semisegmentation having the stated property is in fact an M-segmentation. The following proof was also first published in [29].

Proof of Theorem 1.1(iii). We observe that it is a consequence of Eq. (12.5) that, for any spel c, o^ = max1<m<M scm. Since we assume that the seeded M-fuzzy graph (V, V) is connectable, there exists a chain (c(0),..., c(K)) of positive (min1£m<M ^m)-strength from a seed spel to an arbitrary spel c. We now show inductively that, for 0 < k < K, o^ > 0. This is clearly so for k = 0. Suppose now that it is so for k — 1. Choose an m (1 < m < M) such that o^" 1} = o^' 1} = s^k 1). Then there is a o m-chain of positive ^m-strength from a spel in Vm to c(k—1). Since fm(c(k—1\ c®) > 0, o0cCk} > s^ > 0. □

### 12.3.2 Algorithm

In this subsection, we present an algorithm that produces the M-semisegmentations whose existence and uniqueness are guaranteed by Theorem 1.1. In designing the algorithm we aimed at making it efficient: as is illustrated in the next subsection, our implementation of it allowed us to find 3-segmentations of images with over 10,000 spels in approximately a tenth of a second.

As the algorithm proceeds, it maintains (and repeatedly changes) an M-semisegmentation o. The claim is that at the time when the algorithm terminates, o satisfies the property of Theorem 1.1(i).

The algorithm makes use of a priority queue H of spels c, with associated keys o£ [26]. Such a priority queue has the property that the key of the spel at its head is maximal (its value is denoted by Maximum-Key(H), which is defined to be 0 if H is empty). As the algorithm proceeds, each spel is inserted into H exactly once (using the operation H H U{c}) and is eventually removed from H using the operation Remove-Max(H), which removes the spel c from the head of the priority queue. At the time when a spel c is removed from H, the vector oc has its final value. Spels are removed from H in a nonincreasing order of the final value of oq. We use the variable l to store the current value of Maximum-Key(H). Algorithm 1 shows a detailed specification using the conventions adopted in [26].

The process is initialized (Steps 1-10) by first setting om to 0, for each spel c and0 < m < M .Then, for every seed spel c e Vm, c is put into Um and H and

Algorithm 1 Multiobject fuzzy segmentation.

14. do remove a spel d from Um

15. C c e V | am < min(l, ^m(d, c)) and a0C < min(l, fm(d, c))}

17. do remove a spel c from C

26. Remove-Max(H)

27. l Maximum-Key(H)

both a£ and am are set to 1. Following this, l is also set to 1. At the end of the initialization, the following conditions are satisfied.

(i) a is an M-semisegmentation of V.

(ii) A spel c is in H if, and only if, 0 < a^ < l.

The initialization is followed by the main loop of the algorithm. At the beginning of each execution of this loop, conditions (i) to (iv) above are satisfied. The main loop is repeatedly performed for decreasing values of l until l becomes 0, at which time the algorithm terminates (Step 11). There are two parts to the main loop, each of which has a very different function.

The first part of the main loop (Steps 12-24) is the essential part of the algorithm. It is in here where we update our best guess so far of the final values of the am. A current value is replaced by a larger one if it is found that there is a am-chain from a seed spel in Vm to c of ^m-strength greater than the old value (the previously maximal ^m-strength of the known a m-chains of this kind) and it is replaced by 0 if it is found that (for an n = m) there is a an-chain from a seed spel in Vn to c of ^-strength greater than the old value of am.

The purpose of the second part of the main loop (Steps 25-29) is to restore the satisfaction of conditions (iii) and (iv) above for a new (smaller) value of l.

To help with the understanding of why this algorithm performs as desired, we comment that just prior to entering its main loop (Steps 11-29), there are four kinds of spels. There are those spels d that have previously been put into and have subsequently been removed from H; for these spels not only does the vector ad has its final value, but also we have already put into H (and possibly even have already removed from H) every spel c such that ^m(d, c) > 0, for at least one m. (For spels of this first kind, a,d > l.) Secondly, there are the spels d that are in at least one of the Um; for these spels the vector a d has its final value, but we may not have yet put into H every spel c such that ^m(d, c) > 0 for at least one m. (For spels of this second kind, atf = am = l.) This will get done in the next execution of Steps 13-21, while Steps 22-24 will insure that the ac get updated appropriately. Consequently, the spels c which are in H but not in any of the Um are those for which there is, for some 1 < m < M, a a m-chain (for the current a) from a seed spel in Vm to c; for the rest of the spels (those which have not as yet been put into H) there is no m for which there is a am-chain (for the current a) from a seed spel in Vm to c. (For spels c of these third and fourth kinds, 0 < —0c < l and —0 = 0, respectively.)

One tricky aspect of the algorithm is that a spel of the third kind may become a spel of the second kind and a spel of the fourth kind may become a spel of the third (or even of the second) kind during the execution of the main loop. That the description of the four kinds of spels remains as given in the previous paragraph is insured by Steps 19 and 21. (Step 21 also insures that condition (ii) stated above remains satisfied. To see this, observe that Step 15 guarantees that if c is put into C, then 0 < min(l, ^m(d, c)) and consequently the t defined in Step 18 and used in Step 24 is also positive. That condition (i) stated above remains satisfied is obvious from Steps 20-24.)

We complete this subsection with a brief discussion of our implementation of Algorithm 1. As suggested in [26], we use a heap to implement the priority queue H. This provides us with efficient implementations of the operations of insertion into (H H U c) and removal from (Remove-Max(H)) the priority queue, as well as of Step 29. In applications it is typically the case that, for every spel d, there is a fixed number of spels c such that £M= 1 ^m(d, c) > 0 and a list of all such c is inexpensive to produce. In such a case the cost of executing Step 15 becomes proportional to a constant (four, six, or twelve in the examples shown below and in Section 12.4) independent of the size of V. Using L to denote this constant, the computational complexity of the Algorithm 1 is the following: since each spel can belong to multiple objects there can be at most M| V | executions of the loop 13-24, while the loop 16-24 can be executed at most L times. Steps 19 and 24 have O (log | V |) operations while Steps 22-23 have O (M) operations, so the loop 16-24 has O (M log | V |) operations. Since this loop can be executed at most ML\V | times, the time complexity of Algorithm 1 is O (M2L | V | log | V |).

0 0