Alejandra Estanislao

Frédéric A 2012 Meunier

F R Éd

Éric Meunier

A business dinner problem

Keywords: Howell designs, linear programming, meeting scheduling, optimization

We are given suppliers and customers, and a set of tables. Every evening of the forthcoming days, there will be a dinner. Each customer must eat with each supplier exactly once, but two suppliers may meet at most once at a table. The number of customers and the number of suppliers who can sit together at a table are bounded above by fixed parameters. What is the minimum number of evenings to be scheduled in order to reach this objective? This question was submitted by a firm to the Junior company of a french engineering school some years ago. Lower and upper bounds are given in this paper, as well as proven optimal solutions with closed-form expressions for some cases.

1. Introduction 1.1. Context. In 2009, the following problem was submitted to the "Junior company" of the Ecole des Ponts -one of the french engineering schools -by a firm. We are given a set S = {1, . . . , s} of suppliers, a set C = {1, . . . , c} of customers, and a room with t tables. Each evening of the forthcoming days, there will be a dinner. During a dinner, suppliers and customers sit at tables, in such a way that there are at most σ ≥ 1 suppliers and at most γ ≥ 1 customers sitting at the same table. Two suppliers can sit at most once at the same table. There is no similar restriction for two customers: two customers can sit as often as they want at the same table. Each customer and each supplier must sit at the same table exactly once, but not necessarily next to each other. Find a schedule (for each dinner, describe for each table the suppliers and the customers who sit at it) satisfying these constraints and minimizing the number of dinners. Note that there is always a feasible solution since whenever a supplier and a customer have not yet sat together at a table, we can add an additional dinner to allow the missing meeting.

An example of scheduling with t = 2, s = 5, c = 6, σ = 2, and γ = 3 is given in Table 1. The proposed solution requires six dinners. Theorems 2 and 3 below show that the optimal solution of Table 1 consists actually in three dinners.

We call this problem the Business Dinner Problem.

1.2. Related works. To authors knowledge, the Business Dinner Problem is new and has not yet been studied. However, there are some links with other problems, mainly from the combinatorial design theory.

In the Kirkman Schoolgirl Problem (see [START_REF] Abel | Resolvable and near resolvable designs[END_REF]), fifteen schoolgirls must be split into five groups of three girls each day of the week, so that no two girls are in the same group twice. This problem is known to have a solution. The condition on the girls resembles the condition on the suppliers with the "groups" playing the role of the tables. However, it is not clear how to build from a feasible solution of the Kirman Schoolgirl Problem a feasible solution to the Business Dinner Problem (which should then have t = 5 tables, s = 15 suppliers, at most σ = 3 suppliers per table, and c/γ ≤ 7), since there is no counterpart to the customers in the Kirkman Schoolgirl Problem.

The Social Golfer Problem is a generalization of the Kirkman Schoolgirl Problem for other values of these parameters: given s = σs ′ golfers and a time period of r days, we have to split each day the golfers into s ′ groups of σ golfers so that no two golfers are in the same group twice. Again, it is not clear how to build from a feasible solution of the Social Golfer Problem a feasible solution to the Business Dinner Problem (which should then have t = s ′ tables, s suppliers, at most σ suppliers per table, and c/γ ≤ r), again because there is no counterpart to the customers. The Social Golfer Problem belongs to the more general family of Tournament Scheduling Problems, see [START_REF] Dinitz | Scheduling a tournament[END_REF].

There is a combinatorial object strongly connected with our problem. A square array of size m × m is a Howell design of type H(m, 2n), with n ≥ 1, provided that (1) every cell is either empty or contains an unordered pair of elements (symbols) chosen from a set of size 2n, (2) every symbol occurs exactly once in each row and each column, (3) every unordered pair of symbols occurs at most once in the array.

A Howell design provides then a feasible schedule of the Business Dinner Problem for ⌈c/γ⌉ = m, s = 2n, σ = 2, and t ≥ n: the rows of the array are the dinners, the columns are the customer groups (of γ or less customers), and in each cell of the array, we find suppliers present for this dinner with this customer group at a table.

The following theorem was obtained after a series of papers from the early sixties until the eighties. Two papers [START_REF] Anderson | The Existence of Howell designs of Even Side[END_REF][START_REF] Stinson | The Existence of Howell designs of Odd Side[END_REF] conclude this series with a complete characterization of the values for which Howell designs exist. Theorem 1. A Howell design H(m, 2n) exists if and only if the following two conditions are satisfied:

(1) n ≤ m ≤ 2n -1 (2) (m, 2n) / ∈ {(2, 4), (3, 4), (5, 6), (5, 8)}
In Section 3.3, Howell designs will be used to derive upper bounds for our problem.

There is also a family of problems that seem closely related to ours, at least by the original formulation. It is the Oberwolfach Problem and its relatives. The Oberwolfach Problem [START_REF] Guy | Unsolved combinatorial problems[END_REF] first posed by Ringel in 1967 asks whether it is possible to seat an odd number n of mathematicians at m round tables of sizes (ℓ 1 , . . . , ℓ m ) with m i=1 ℓ i = n in (n -1)/2 dinners so that each mathematician sits next to everyone else exactly once. Equivalently, this problem consists in decomposing the complete graph K n into pairwise edge-disjoint copies of a given 2-regular graph. The conjecture is that except for some exceptional values of the ℓ i 's, such a decomposition always exists, see [START_REF] Bryant | Cycle decompositions[END_REF] or [START_REF] Traetta | A complete solution of the two-table Oberwolfach problems[END_REF] for the last results on this problem. A maybe more closely related problem is the Bipartite Analogue of the Oberwolfach Problem which consists in decomposing the bipartite complete graph K n,n into pairwise edge-disjoint copies of a given 2-regular graph. The complete answer was given by Piotrowski in 1991 [START_REF] Piotrowski | The solution of the bipartite analogue of the Oberwolfach problem[END_REF]. It models the case when there are two delegations, each mathematician must sit between mathematicians of the other delegation, and each mathematician sits next to every mathematician of the other delegation exactly once. Generalizations of this problem for complete n-partite graphs are also studied, see [START_REF] Liu | A generalization of the Oberwolfach problem and C t -factorizations of complete equipartite graphs[END_REF] and [START_REF] Liu | The equipartite Oberwolfach problem with uniform tables[END_REF]. Another variation of the Bipartite Analogue is given by the Oberwolfach Rectangular Table Negotation Problem for which the tables are rectangular, each delegation sits along one of the long sides of the tables, and each mathematician sits near to each mathematician of the other delegation exactly once, where "near" means the opposite position, the position to the right of the opposite one, or the position to the left of the opposite one. The Oberwolfach Rectangular Table Negotiation Problem has been studied in [START_REF] Chitra | Bipartite variation of the cheesecake factory problem: mH(k, 2l + 1)-factorization of K n,n[END_REF][START_REF] Froncek | Oberwolfach rectangular negotiation problem[END_REF][START_REF] Froncek | Rectangular table negotiation problem revisited[END_REF].

Despite the close original formulation, the Oberwolfach Problem and its variations do not seem to provide feasible solutions for the Business Dinner Problem. There is indeed a notion of neighbors at tables that is not present in the Business Dinner Problem. Moreover, and it holds also for the other problems cited above, the Business Dinner Problem is an optimization problem, for which dinner 1: table 1 1. A feasible schedule in six dinners for an instance with t = 2 tables, s = 5 suppliers, c = 6 customers, at most σ = 2 suppliers per table, and at most γ = 3 customers per table there are feasible solutions, whereas the problems above deal generally with the existence of some object. This difference is also one of the motivations of our work.

1.3. Main results. Note first that if c ≤ γ, the optimal solution is easy, see Section 3.1.

As it will become clear in the sequel, describing an optimal solution in the general case is a very difficult task since it contains as special cases open questions of the theory of combinatorial designs. However, we are able to provide the following non-trivial lower bounds and feasible solutions in the general case.

Theorem 2. Consider the Business Dinner Problem with t tables, s suppliers, c customers, at most σ suppliers, and at most γ customers simultaneously at a table. The following expressions are lower bounds when γ < c.

lb 1 = s σ , lb 2 = c γ , lb 3 = s tσ c γ , lb 4 =      √ s tγ   (c -γ) max γ c -γ , 1 + γ max γ c-γ , 1         , lb 5 = max j∈{2,...,σ} s t 2 j c γ - s -1 j(j -1)
. lb 5 can be made more explicit by a simple function study. The maximum of the expression over j is obtained for j = j * or j = j * + 1 with

j * =     1 1 - s-1 s-1+2⌈c/γ⌉     . If j * ∈ [2, σ], lb 5 is obtained for j = j * . If j * < 2, lb 5 is obtained for j = 2. If j * > σ, lb 5 is obtained for j = σ.
None of these lower bounds is striclty better than the others.

ub 1 = 2 σ 1 t min c γ , s max c γ , s 2
.
If ⌈s/σ⌉ ≤ ⌈c/γ⌉, the following expression is also an upper bound

ub 2 = 1 t s σ 1 -σ + σ max c γ , 2 s σ .
Moreover, there are explicit solutions matching these upper bounds.

None of the ub 1 and ub 2 is strictly better than the other. If one takes t = 3, s = 6, c = 3, σ = 2, and γ = 1, then ub 1 takes the value 3 and ub 2 takes the value 11. If one takes t = 3, s = 6, c = 9, σ = 2, and γ = 1 (only the number of customers changes), then ub 1 takes the value 18 and ub 2 takes the value 17.

ub 2 is also applicable when ⌈s/σ⌉ > ⌈c/γ⌉ by making groups of at most σ⌈c/γ⌉ suppliers each, see Section 4 for details.

1.4. Plan. Section 2 is devoted to the proof of Theorem 2. Optimal solutions for special caseswhose optimality is proven with the help of Theorem 2 -are described in Section 3. These optimal solutions can be used to build feasible solutions for other values of the parameters via slight changes (Section 4). These feasible solutions provide upper bounds for the Business Dinner Problem and prove Theorem 3. In the last section (Section 5), some open questions are stated.

Lower bounds

The purpose of this section is to prove Theorem 2. It will be done by proving three propositions (Propositions 1, 2, and 4), each of them providing some of the lower bounds.

√ s tγ (c -γ) max γ c-γ , 1 + γ max γ c-γ ,1
is a lower bound for the Business Dinner Problem.

Proof. Denote y k the number of dinners for which customer k = 1, . . . , c is present. Let z be the maximum number of suppliers sitting simultaneously at a table among all dinners and let x be the number of customers present at that table.

On the one hand, each customer is present for at least s/z dinners. Thus c k=1 y k ≥ cs/z. On the other hand, at least c -x customers are present for z dinners, in order to be able to meet each of the z suppliers having sat once together. Thus

y k ≥ (c -γ) max sγ c -γ , √ s + sγ max sγ c-γ , √ s .
Now, the conclusion follows from the fact that there are at most tγ customers present at each dinner.

It settles the case of lb 4 .

Remark. The lower bound lb 4 can be improved by taking into account the inequality z ≤ σ in the proof above. For sake of simplicity, we have not computed lb 4 with this additional constraint.

2.3.

Lower bounds through linear programming and duality. Another way to get lower bounds consists in introducing variables x i,j ∈ Z + which count for a given schedule the number of times supplier i sits at a table of exactly j suppliers (him included). We have the following relation σ j=1 γx i,j ≥ c, which comes from the fact that each customer sits with supplier i once. Another relation is σ j=1 (j -1)x i,j ≤ s -1, since two suppliers may sit at a common table at most once.

i∈S σ j=1 1 j x i,j is the number of tables needed, counted with multiplicity (each table is counted as many times it is used over the whole schedule). A lower bound is therefore given by the following linear program:

(1) (j -1)x j ≤ s -1

min 1 t i∈S σ j=1 1 j x i,j s.t. σ j=1 x i,j ≥ c γ i ∈ S σ j=1 (j -1)x i,j ≤ s -1 i ∈ S x i,j ∈ R + i ∈ S,
x j ∈ R + j ∈ {1, . . . , σ}.
The dual of program ( 2) is

(3) max c γ λ -(s -1)µ s.t. λ ≤ (j -1)µ + 1 j j ∈ {1, . . . , σ} λ, µ ∈ R + .
Let (λ * , µ * ) be an optimal solution of (3). We have

λ * = min j∈{1,...,σ} (j -1)µ * + 1 j
and thus an optimal value equal to (4) max µ≥0 min j∈{1,...,σ}

(j -1) c γ -(s -1) µ + 1 j c γ .
To evaluate this latter expression, we write

[0, +∞) = 0, 1 σ(σ -1) ∪ σ-1 k=2 1 (k + 1)k , 1 k(k -1) ∪ [1/2, +∞),
and we optimize for µ belonging to each of these intervals.

Remark that the map g : j → µj + 1 j is decreasing for j ≤ 1 √ µ and increasing otherwise.

Case µ ∈ [0, 1 σ(σ-1) ]: According to the remark concerning the map g, we have min j∈{1,...,σ}

(j -1) c γ -(s -1) µ + 1 j c γ = min j∈{σ-1,σ} (j -1) c γ -(s -1) µ + 1 j c γ .
Comparing the value obtained for j = σ -1 and j = σ leads to the maximum on this interval, depending on the sign of (σ -

1) c γ -(s -1), max 1 σ c γ , 2 σ c γ - s -1 (σ -1)σ . Case µ ∈ [ 1 (k+1)k , 1 k(k-1)
]: For such a µ, according to the remark on g, the j realizing the minimum is in {k -1, k, k + 1}. A straightforward computation shows that the minimum is actually reached on k.

• If ⌈c/γ⌉(k -1) ≤ s -1, then the maximum is reached for µ = 1 (k+1)k and we get a maximum equal to

2 k + 1 c γ - s -1 (k + 1)k . • If ⌈c/γ⌉(k -1) ≥ s -1, then the maximum is reached for µ = 1 k(k-1) and we get a maximum equal to 2 k c γ - s -1 k(k -1)
.

Case µ ∈ [1/2, +∞): Interverting min and max in Equation ( 4) increases the expression. Letting j = 1 once we have interverted leads therefore to an upper bound, which is equal to ⌈c/γ⌉ -(s -1)/2. This quantity is also a lower bound because it is what we get when we evaluate Equation ( 4) for µ = 1/2. Therefore, by strong duality, the optimal value of ( 3) is

(5) max 1 σ c γ , max j∈{2,...,σ} 2 j c γ - s -1 j(j -1)
.

To get the optimal j as stated just after Theorem 2, we compute the values x ≥ 1 for which

x → 2 x c γ -s-1
x(x-1) is an increasing map. A simple calculation leads to

x ∈   1; 1 1 - s-1 s-1+2⌈c/γ⌉   .
The integer j * maximizing the expression ( 5) is therefore one of the two integers around the right bound of this interval.

Proposition 3 and the preceding discussion lead to the following proposition.

Special cases with optimal solutions

3.1. Case c ≤ γ. In this case, the optimal solution is ⌈s/σ⌉. Indeed, all customers sit together at a table, and each evening, they have a dinner with exactly σ suppliers, except maybe the last evening, when they have a dinner with s -σ⌊s/σ⌋ suppliers. It gives ⌈s/σ⌉ dinners. Since it is also a lower bound (Proposition 1), it is an optimal solution.

3.2. Case σ = 1. We have the following proposition. Proof. Assume γ = 1. Consider the complete bipartite graph K s,c with on one side the suppliers and on the other side the customers. If the dinners are the colors, we want to find a proper edgecoloring of K s,c with each color being present at most t times. According to a theorem by De Werra [START_REF] Werra | On some combinatorial problems arising in scheduling[END_REF], the minimal number of colors in a proper edge-coloring of a bipartite graph G = (V, E) with each color being present at most t times is max(⌈|E|/t⌉, ∆(G)), where ∆(G) is the maximal degree of G. Therefore, the minimal number of colors in K s,c is max(⌈sc/t⌉, s, c).

The case γ > 1 is obtained as follows: split the customers in ⌈c/γ⌉ groups, each being of size ≤ γ; according to the preceding construction, we get a feasible solution with max(s, ⌈c/γ⌉, ⌈s/t⌈c/γ⌉⌉) dinners. This solution is optimal according to the lower bounds lb 1 , lb 2 , and lb 3 of Theorem 2.

3.3.

Case σ = 2, s > c/γ and t ≥ min(c/γ, s/2). Proposition 6. If σ = 2, s > c/γ, t ≥ min(c/γ, s/2) and (⌈c/γ⌉, s) = (2, 4), the optimal number of dinners is

max c γ , s 2 .
This case coincides more or less with the concept of Howell designs, presented in Section 1.2. With the help of Theorem 1, we are able to prove Proposition 6.

Proof of Proposition 6. Suppose first that (⌈c/γ⌉, s) / ∈ {(3, 4), [START_REF] Werra | On some combinatorial problems arising in scheduling[END_REF][START_REF] Dinitz | Scheduling a tournament[END_REF], [START_REF] Werra | On some combinatorial problems arising in scheduling[END_REF][START_REF] Froncek | Rectangular table negotiation problem revisited[END_REF]}. Because of the assumption of the theorem, we have also (⌈c/γ⌉, s) = [START_REF] Anderson | The Existence of Howell designs of Even Side[END_REF][START_REF] Chitra | Bipartite variation of the cheesecake factory problem: mH(k, 2l + 1)-factorization of K n,n[END_REF]. Therefore, we can apply Theorem 1.

Case ⌈c/γ⌉ ≥ s/2: If s is even, let 2n = s. With the interpretation of the Howell design H(⌈c/γ⌉, 2n) in terms of schedule, we are able to find a solution in ⌈c/γ⌉ dinners, which is obviously optimal as it is also the lower bound lb 2 . If s is odd, let 2n -1 = s, add a fictitious supplier and we get again an optimal solution in ⌈c/γ⌉ evenings with the same construction. Case s/2 > ⌈c/γ⌉: As in the case above, we define n such that s = 2n or s = 2n -1 according to the parity of s. With H(n, 2n) from which we keep only the ⌈c/γ⌉ first columns, we get a feasible schedule in n dinners. As n = ⌈s/σ⌉, which is the lower bound lb 1 , we get the optimality of this solution.

1,2 3,4 3 1 2,4 4 2 1,3 Table 2. An optimal schedule for t = 3 tables, s = 4 suppliers, ⌈c/γ⌉ = 3 groups of customers (the columns), at most σ = 2 suppliers per table, in 3 dinners (the rows) 3. An optimal schedule for t = 5 tables, s = 6 suppliers, ⌈c/γ⌉ = 5 groups of customers (the columns), at most σ = 2 suppliers per table, in 5 dinners (the rows)

For the three remaining cases (⌈c/γ⌉, s) ∈ {(3, 4), [START_REF] Werra | On some combinatorial problems arising in scheduling[END_REF][START_REF] Dinitz | Scheduling a tournament[END_REF], [START_REF] Werra | On some combinatorial problems arising in scheduling[END_REF][START_REF] Froncek | Rectangular table negotiation problem revisited[END_REF])}, we use the explicit solutions1 of Tables 234. The optimality is proven with the help of lower bound lb 2 .

For the case (⌈c/γ⌉, s) = (2, 4), we have a solution in three dinners, see in Table 5, and it is easy to see that there is no solution in two dinners. 4. An optimal schedule for t = 5 tables, s = 8 suppliers, ⌈c/γ⌉ = 5 groups of customers (the columns), at most σ = 2 suppliers per table, in 5 dinners (the rows) 1,2 3,4 3 1 4 2 Table 5. An optimal schedule for t = 2 tables, s = 4 suppliers, ⌈c/γ⌉ = 2 groups of customers (the columns), at most σ = 2 suppliers per table, in 3 dinners (the rows)

Remark. It becomes clear that a general exact solution for the present problem is out of reach: such a solution would describe under which conditions objects generalizing Howell designs with more than two numbers in each cell would exist -a difficult topic which is still under investigation. Proof. We first write the proof for the case s = 2t. We prove that there is a feasible solution matching this number of dinners. Let c ′ = ⌈c/γ⌉. We split the whole set of customers into c ′ groups, each of them with at most γ customers. Consider an optimal schedule with s suppliers and s -1 groups of customers and derive from it a feasible schedule in s -1 dinners (Proposition 6). At the end of these s -1 dinners, we have s -1 groups among the c ′ groups that have met all suppliers. For the remaining c ′ -s + 1 groups, we use a feasible solution in ⌈ s t (c ′ -s + 1)⌉ = 2c ′ -2s + 2 dinners, given by Proposition 5. The suppliers being alone in such a solution, we get a feasible solution for the whole collection of c ′ groups in 2c ′ -s + 1 dinners.

This number of dinners is optimal according to the lower bound lb 5 of Theorem 2 with j = 2.

Let us deal with the case s = 2t -1. Adding a fictitious supplier, we have s ′ = s + 1 suppliers and we get similarly as above a solution in s ′ -1 + ⌈ s t (c ′ -s ′ + 1)⌉ dinners. Note that the c ′ -s ′ + 1 groups of customers have s suppliers to meet and we get a s t term and not a s ′ t one. Replacing s ′ and s by their expressions in t, we get a solution in ⌈ c ′ s t + 3 -1 t -2t⌉ dinners. The lower bound lb 5 of Theorem 2 with j = 2 is in this case ⌈ c ′ s t -4t 2 -6t+2 2t ⌉ = ⌈ c ′ s t + 3 -1 t -2t⌉ and proves the optimality of this solution.

Explicit solutions.

Proof of Theorem 3. We get ub 1 as follows.

Let t 1 = t, t 2 = min c γ , s , σ 1 = σ and σ 2 = 2. We have r(t 2 , s, c, σ 2 , γ) ≤ max c γ , s 2 . Indeed, if s > c/γ, we use Proposition 6; and if s ≤ c/γ, we use Proposition 5 combined with the inequality r(t 2 , s, c, 2, γ) ≤ r(t 2 , s, c, 1, γ), which follows from Equation [START_REF] Froncek | Oberwolfach rectangular negotiation problem[END_REF]. Equations ( 6) and ( 7) are then used to conclude.

To get ub 2 , we first define a new business dinner problem with t ′ = ⌈s/σ⌉ tables, s ′ = t ′ σ suppliers, ⌈c/γ⌉ customers, at most σ suppliers per table and at most 1 customer per table. For this problem, a feasible solution consists in taking t ′ customers, and in putting each of them at a separate table. The first evening, each of these t ′ customers eats with σ distinct suppliers. The s ′ -σ following evenings, each of these t ′ customers eats with one of the s ′ -σ suppliers he has not yet eaten with. It is easy to schedule these dinners. For the ⌈c/γ⌉ -t ′ remaining customers, we build a solution with exactly one supplier per table in σ max(⌈c/γ⌉ -t ′ , t ′ ) dinners (the schedule follows from Proposition 5). We get therefore a feasible solution in 1 + s ′ -σ + σ max(⌈c/γ⌉ -t ′ , t ′ ) dinners: r(t ′ , s ′ , ⌈c/γ⌉, σ, 1) ≤ 1 -σ + σ max(⌈c/γ⌉, 2t ′ ). Combining this solution with the monotony of r in s, Equation ( 6) and Equation ( 8) (for γ 2 = γ 1 = γ), we get ub 2 . Actually, if s > c/γ, the upper bound ub 1 can be improved with the same proof (Proposition 6 can be used in a tighter way) by 2 σ

1 t min c γ , s 2 max c γ , s 2
.
The upper bound ub 2 leads to feasible solutions even if s/σ > c/γ. Indeed, we can make the Euclidean division of ⌈s/σ⌉ by ⌈c/γ⌉. Let us write ⌈s/σ⌉ = q⌈c/γ⌉ + ρ with 0 ≤ ρ < ⌈c/γ⌉.

Making q groups of at most σ⌈c/γ⌉ suppliers each and one group of at most σρ suppliers, and with the help of Equation ( 9), we get a solution in at most [START_REF] Liu | A generalization of the Oberwolfach problem and C t -factorizations of complete equipartite graphs[END_REF]

q 1 t c γ 1 -σ + 2σ c γ + ρ t 1 -σ + 2σ max c γ , 2ρ
dinners.

5. Some open questions 5.1. Improving the bounds. For many instances, the ratio (best upper bound) / (best lower bound) is low. It is however possible to make this ratio arbitrarily high as follows. Set s := x and σ := √ x and let x → +∞. The parameters c, γ, and t are considered as constant. The notation g = O(f ) means that g/f is asymptotically bounded above by a constant, whereas the notation g = Ω(f ) means that g/f is asymptotically bounded below by a constant. Then lb 2 is constant. The lower bound lb 5 goes to something negative: it can be checked that j * = Ω(x) and therefore the maximum is reached on σ when x is sufficiently high. The three others lower bounds are O( √ x).

We have ub 1 = 1 t c γ x 2 when x is sufficiently high. For the other upper bound, using Equation (10), we get ub 2 ∼

2 c γ -1 c γ 1 t c γ
x.

The ratio is therefore a Ω( √ x).

A question is whether it is possible to improve the lower and upper bounds in order to get a ratio bounded above by a constant.

Making groups.

The most intriguing open question is the following, as a positive answer seems intuitively correct, Is there always an optimal solution in which the customers are split into groups, the members of each group staying together for all dinners? Indeed, this property is satisfied in all optimal or good solutions proposed in the present paper. An alternative formulation is whether Equation ( 8) is actually an equality when γ 1 = γ 2 .

One table and at most one customer per table.

An open question which may be tractable is the case with only one table and at most one customer at each table. A partial answer is given Section 3.5 and we were not able to deal with the general case.

  c k=1 y k ≥ (c -x)z + xs/z. Therefore, we have a lower bound for c k=1 y k being min z∈R + ℓ(z) with ℓ(z) := max(cs/z, min 1≤x≤γ (c -x)z + xs/z). If z ≤ √ s, then cs/z ≥ min 1≤x≤γ (c -x)z + xs/z and ℓ(z) = cs/z. If z ≥ √ s, then cs/z ≤ min 1≤x≤γ (c -x)z + xs/z. In this latter case, (c -x)z + sx/z is minimum for x = γ and ℓ(z) = (c -γ)z + γs/z. The map g : u → (c -γ)u + γs/u attains its minimum for u = sγ c-γ . Therefore, according to the respective positions of √ c -γ and √ γ, the minimum of ℓ(z) is attained for z = √ s or z = sγ c-γ . Thus, c k=1

1 )

 1 is a lower bound for the Business Dinner Problem.It gives lb 3 and lb 5 .

Proposition 5 .

 5 If σ = 1, then the optimal number of dinners is

3. 4 .

 4 Case t = ⌈s/2⌉, σ = 2, and ⌈c/γ⌉ ≥ 3 2 s. Proposition 7. If t = ⌈s/2⌉, σ = 2, and ⌈c/γ⌉ ≥ 3 2 s, then the optimal number of dinners is 2 c γ -s + 1.

3. 5 .

 5 Case t = γ = 1, c ≤ p ≤ σ, s = p 2 with p prime. Proposition 8. If t = γ = 1, c ≤ p ≤ σ, s = p 2 withp prime, the optimal number of dinners is pc.

  The following table gives explicit values for parameters of the problem for which each of the lower bounds strictly dominates the other (indicated with a star * ). (t, s, c, σ, γ) lb 1 lb 2 lb 3 lb 4 lb 5 Consider the Business Dinner Problem with t tables, s suppliers, c customers, at most σ suppliers, and at most γ customers simultaneously at a table. The following expression is an upper bound,

	7 6 8 64 * 23 0 3 0 (5, 8, 8, 1, 2) 8 * 4 (6, 8, 8, 2, 1) 4 6 4 8 * (1, 8, 8, 1, 1) 8 (1, 11, 8, 6, 4) 2 2 4 4 7 * (1, 8, 11, 2, 1) 4 11 44 32 60

*

Theorem 3.

  2.1. Straightforward lower bounds. Take a customer. During a dinner, he sits at a table with at most σ suppliers. To meet all suppliers, he needs at least ⌈s/σ⌉ dinners. Take a supplier. During a dinner, he sits at a table with at most γ customers. To meet all customers, he needs at least ⌈c/γ⌉ dinners. This short discussion implies Proposition 1. ⌈s/σ⌉ and ⌈c/γ⌉ are lower bounds for the Business Dinner Problem. It settles the case of lb 1 and lb 2 .

	2.2. A counting argument.

Proposition 2. If c > γ, the quantity

computed with the help of the constraint programming toolbox of the IBM ILOG CPLEX Optimization Studio.

Proof. We define the following p × p matrices M (1) , . . . , M (c) where M (k) i,j = j + p(kj -j -k + i) mod p 2 for i, j ∈ {1, . . . , p} and for k ∈ {1, . . . , c}.

For a k ∈ {1, . . . , c}, let i, j, i ′ , j ′ be in {1, . . . , p}. If we have M (k) i,j = M (k) i ′ ,j ′ mod p 2 , then we get first that j = j ′ (by counting modulo p), then that i = i ′ . It means that the numbers appearing in a M (k) are all distinct modulo p 2 , and hence that all the numbers from 1 to 1 + p 2 modulo p 2 appear in such a matrix since there are p 2 entries.

We build now a feasible schedule in pc dinners as follows. For each k, the matrix M (k) encodes p dinners with customer k at the unique table: each row provides the suppliers present at a dinner. According to the remark above, each customer meets all suppliers. It remains to check that two suppliers eat at most once together. Assume that it is not the case. Because all numbers in a M (k) are distinct, we know that two suppliers eat at most once together, when one considers the dinners with a given customer. Therefore, if two suppliers eat at least twice together we have simultaneously

. . , p} with j 1 = j 2 and j ′ 1 = j ′ 2 , and distinct k and k ′ in {1, . . . , c}. We get first that j 1 = j ′ 1 and that j 2 = j ′ 2 (by counting modulo p). Then we get that p 2 divides p(i

The optimality of the solution is clear since it matches lb 4 of Theorem 2.

Feasible solutions

The main purpose of this section is to prove Theorem 3.

Domination results.

Let us denote r(t, s, c, σ, γ) the optimal solution of the problem. Obviously, it is an non-decreasing map in s and in c. It is also a non-increasing map in t, in σ, and in γ, but concerning these quantitites, we can say a little bit more.

(6) r(t 1 , s, c, σ, γ) ≤ t 2 t 1 r(t 2 , s, c, σ, γ) for any t 1 and t 2 .

Indeed, if t 1 ≥ t 2 , then any solution with t 2 tables is also a solution with t 1 tables (r is a non-increasing map). And if t 2 ≥ t 1 , we can split the set of tables into t 2 t 1 groups of t 1 tables, and use any solution of the problem with t 2 tables to build a solution with t 1 tables, each group corresponding to a distinct dinner.

With the same kind of reasoning, we get (7) r(t, s, c, σ 1 , γ) ≤ σ 2 σ 1 r(t, s, c, σ 2 , γ) for any σ 1 and σ 2 .

Making groups of at most γ 1 customers leads to

Finally, we have also the following relation.


Giovani Bernardes
email: giovani@fem.unicamp.br

Vitor Janito
email: janito@fem.unicamp.br

Vaqueiro Ferreira

FAST IMAGE SEGMENTATION BY WATERSHED TRANSFORM ON GRAPHICAL HARDWARE

Keywords: watershed transform, image segmentation, GPGPU

The watershed transform is widely used for image segmentation on computer vision applications. However, sequential watershed algorithms are not suitable for fast applications, once they are one demanding part of several tasks. This paper proposes two parallel algorithms for the watershed transform focused on fast image segmentation using off-the-shelf GPUs. In this sense, these algorithms aims for a speedup by mixing several techniques of the fastest procedures on both sequential and parallel fields. Both algorithms has four major steps, the parallel version processed on SIMD, and the hybrid version mixing parallel and sequential approaches. The experimental results obtained show that the hybrid version is faster, taking advantage of the most appropriate hardware for each task.

Introduction

The identification of objects on images needs in most cases a pre-processing step, with algorithms based on segmentation by discontinuity or the opposite, by similarity. Segmentation itself is not a trivial task, being one of the hardest ones in image processing. Some of its inherent problems are illumination variation through image sequences, dynamic change of background where the camera and/or target moves, as well as changes on the topology of the target or its partial or full occlusion, resulting on a higher complexity of the scene and therefore a more difficult problem.

There are several methods for instantaneous image segmentation on literature, such as background subtraction and its variations, which are very robust but restricted to static cameras, not applicable to a moving scene and camera, the aim of this work. Extraction by shape and colour also exist, however are more sensitive to the previously mentioned variations. An alternative is to join multiple techniques, aiming for gain in robustness. Nevertheless, this type of process carries a disadvantage on the time required for calculations, exceeding CPU capacity for instantaneous video processing. Given that need for a robust yet fast procedure, parallel implementations seem an obvious choice.

One significant part of some segmentation processes goes through the use of a watershed transform. With the use of special hardware, such as GPUs, it can be calculated faster, once these are highly specialised and optimised devices for graphic processing. This paper aims for the development of a watershed transform algorithm suited for GPU processing, developed with NVIDIA's CUDA platform, in four major steps. Two algorithms are proposed, a fully parallel SIMD algorithm and another hybrid approach, taking advantage of the best core for each necessary task. These proposals are compared with each other and with recently developed sequential watershed algorithms.

The paper is organised as follows: Sec. 2. revises the state of the art on the watershed transform algorithms both on sequential and parallel fields. Sec. 3. goes through the implementation and architecture of GPGPU processing with the CUDA libraries. Sec. 4. exposes both algorithms developed, explaining its operations. Sec. 5. presents the timing results obtained, comparing the algorithms. Lastly, Sec. 6. depicts conclusions obtained with this work.

Watershed Transform

Many definitions for the watershed transform exist in literature [START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF][START_REF] Meyer | Topographic distance and watershed lines[END_REF][START_REF] Lotufo | The ordered queue and the optimality of the watershed approaches[END_REF][START_REF] Falcão | The image foresting transform: theory, algorithms, and applications[END_REF][START_REF] Bieniek | A connected component approach to the watershed segmentation[END_REF][START_REF] Cousty | Watershed cuts: Minimum spanning forests and the drop of water principle[END_REF] that take different approaches on the problem, such as defining connected components via influence zones, shortest-path forests with a custom distance function and locally, by making paths of steepest descent.

Over the years, several algorithms of watershed have been proposed, according to different formal definitions and applying different strategies. On this paper, we only focus on those based on the local condition definition, which requires the less global operations, once it mimics the behaviour of a drop of water on a surface, easing a parallel implementation. Next, we discuss those algorithms on their sequential versions and the work on parallel watershed on the literature.

Sequential Watershed Algorithms

The recent fastest sequential watershed transform algorithms are the result of the evolution of the arrowing technique for watershed of [START_REF] Bieniek | An efficient watershed algorithm based on connected components[END_REF] and the union-find one of [START_REF] Meijster | A disjoint set algorithm for the watershed transform[END_REF]. Several algorithms based on this preliminary works have been proposed, using variations of the previous procedures, achieving considerable speedups without loss of precision [START_REF] Sun | A fast watershed algorithm based on chain code and its application in image segmentation[END_REF][START_REF] Lin | Comparison between immersion-based and toboggan-based watershed image segmentation[END_REF][START_REF] Osma-Ruiz | An improved watershed algorithm based on efficient computation of shortest paths[END_REF][START_REF] Cousty | Watershed cuts: Minimum spanning forests and the drop of water principle[END_REF]. These algorithms are all based on evaluating the neighbourhood, intuitively, to identify the direction of sliding of a drop of water on a surface until it reaches a minimum, and label the regions where the drops falls into the same minimum.

The work by [START_REF] Cousty | Watershed cuts: Minimum spanning forests and the drop of water principle[END_REF] introduced one of the fastest sequential watershed algorithms due to its linear complexity. However, its constraints and style of switching between breadth-first and depth-first propagation compose a hard problem for a parallel version. On the other side, its elegant design with the use of sets instead of queues for pixel storage and labelling suggests a possible path for parallelization. [START_REF] Osma-Ruiz | An improved watershed algorithm based on efficient computation of shortest paths[END_REF] proposed an improved algorithm on the sense of pixel visitation by optimising the preliminary works previously mentioned. Nevertheless, these improvements required a massive use of queues for synchronisation of pixel visitation. This feature, interesting for a sequential algorithm, in order to minimise memory access, demands several strategies of flow control on a parallel implementation, such as locks.

The algorithms of [START_REF] Sun | A fast watershed algorithm based on chain code and its application in image segmentation[END_REF], [START_REF] Lin | Comparison between immersion-based and toboggan-based watershed image segmentation[END_REF], [START_REF] Bieniek | An efficient watershed algorithm based on connected components[END_REF] and Meijster and [START_REF] Meijster | A disjoint set algorithm for the watershed transform[END_REF] are very similar in the sense of problem approach. Their difference is on which definition is applied, considering that Lin's and Meijster and Roerdink's procedure applies a label to distinguish pixels where the path of steepest descent is ambiguous between two or more minima. With the use of explicit loops over every pixel depending only on local information, these algorithms are good candidates for parallelization, even though not being the fastest sequential ones.

Parallel Watershed Algorithms

Given that the watershed transform is a very demanding task, early studies have been developed on parallel algorithms. Initially, the focus was on typical image processing systems, where the segmentation represented a time consuming operation [START_REF] Meijster | A Proposal for the Implementation of a Parallel Watershed Algorithm -CAIP[END_REF][START_REF] Bieniek | A parallel watershed algorithm[END_REF]. [START_REF] Roerdink | The watershed transform: definitions, algorithms and parallelization strategies[END_REF] extensively surveyed the literature on this problem. More recently, the evolution of sequential algorithms along with hardware minimised this problem. However, for fast applications (e.g. surveillance and navigation) the sequential algorithms are not fast enough, and the focus of works on parallel watershed algorithms have changed to this area [START_REF] Trieu | Real-time image segmentation based on a parallel and pipelined watershed algorithm[END_REF][START_REF] Galilée | Parallel asynchronous watershed algorithm-architecture[END_REF].

The initial work of [START_REF] Meijster | A Proposal for the Implementation of a Parallel Watershed Algorithm -CAIP[END_REF] is based on the work of [START_REF] Vincent | Watersheds in digital spaces: An efficient algorithm based on immersion simulations[END_REF], in the sense of definition and problem approach. The algorithm proposed relies on a graph transformation, performing the watershed on three steps: convert the image into a graph, where each vertex is a plateau; perform the watershed on the graph; convert the graph into the output image. The most important task, the watershed itself, is done by performing a breadth-first search from the minima, on an iterative flooding. [START_REF] Bieniek | A parallel watershed algorithm[END_REF] proposed another parallel algorithm with a modified definition, that is the local condition watershed transform. In fact, this proposal settles an architecture for a parallelization, as it approaches the problem on how it should divide the image, generate unique labels and merge regions, depending on a sequential algorithm executed on each region. The steps of the algorithm are: split the image on regions; for each region find the regional minima and generate labels; set temporary labels to pixels of the borders of regions; run a sequential watershed algorithm on each region; merge the regions processing the pixels with temporary labels. [START_REF] Galilée | Parallel asynchronous watershed algorithm-architecture[END_REF] introduces a new algorithm for parallel watershed transform, stating to be the first that does not require minima detection as a first step prior to definition of catchment basins. However, a first sequential step for attributing a distinct label for each pixel is necessary, which is in fact its address in raster scan. The algorithm itself is defined as a single procedure with state management and message passing, for status updating of the pixels. This way, pixels that cannot be processed with only local information, the plateaus, wait for neighbourhood data messages to arrive in order to decide which label is taken.

Following the line of work on fast applications, [START_REF] Trieu | Real-time image segmentation based on a parallel and pipelined watershed algorithm[END_REF] developed an algorithm for FPGA architectures based on the sequential algorithm of [START_REF] Sun | A fast watershed algorithm based on chain code and its application in image segmentation[END_REF]. The use of queues and stacks for synchronisation on this algorithm is substituted by a process of stabilisation of geodesic distance values and labelling, reading the memory always sequentially, on raster or anti-raster scan order. The plateau resolution is done by explicitly calculating the geodesic distances. Minima are labelled independently on a pixel basis, with merging of these sub-regions deciding for the minor label.

On the next section the GPU processing is discussed on its implications on parallel programming and on the algorithm proposed on this paper.

GPU Processing

The performance gain in the capacity of GPU (Graphics Process Unit) devices in the last years is no longer exclusive to graphics processing, as it becomes an excellent alternative for general purposes, where the CPU's known speed limits are broken with the insertion of this many-core programming paradigm. Also, the range of applications of parallel nature, the gain in speed compared to conventional computers, the simplicity and practicality in use and acquisition of this technology has drawn great attention from the scientific community.

As an example, the GeForce 8800, a card of the NVIDIA's G8 series of graphics cards. This graphics card has 128 units of calculation (called multiprocessors), distributed on 8 vector processors. It is an architecture similar to that found in clusters of CPUs, but confined to a single hardware device, and as such requires a style of programming called SIMD (Single Instruction Multiple Data). For this card, execution times of up to 100 times faster than the CPU time in classical programs as a multiplication of matrices have been obtained [START_REF] Cooperman | Gpu programming -syllabus[END_REF]. A study by NVIDIA presented a chart comparing the computational power of an Intel CPU, measured in peak GFlops, to the NVIDIA graphics cards, where the most modern GPU architecture delivers performance up to 6 times higher than the CPUs (NVIDIA, 2009a).

To explore the potential of the GPU, a different paradigm of programming should be used, called programming flow. Data are packaged in streams and the arithmetic calculations are kernels operating on them. Excerpts of programming that have enormous arithmetic rates can be shared in order to use the most of the GPU. [START_REF] Baggio | Gpu based image segmentation livewire algorithm implementation[END_REF] characterises the structure of algorithms as follows: (1) the parallel sections of the program are identified and implemented with a kernel, which is a share of the GPU to process arrays of data in parallel on different processors; (2) the organisation of these data should follow a hierarchy for the best arrangement of processing cores, as shown in Fig. 1.

A note to consider is that the data within the block must perform the same process, as a SIMD architecture. This simple and necessary routine for GPU programming does not always fit into some problems because they can not be arranged in parallel, thus these may not benefit of the acceleration of GPUs. On the other hand when working together with CPU and GPU, the gains are significant. On this line, NVIDIA developed an architecture called CUDA that enables the structuring involving sequential and parallel programming, where some sections are sequential and others parallel, depending on the problem. The CUDA architecture is a language binding to the C/C++ language for general purpose parallel implementation. CUDA consists of a runtime library extended from C. Its main abstraction is based on the hierarchy of thread groups, memory sharing and synchronisation. Key elements of CUDA are common C/C++ source code with different compiler forks for CPUs and GPUs; function libraries that simplify programming; and a hardware-abstraction mechanism that hides the details of the GPU architecture from programmers [START_REF] Halfhill | Parallel Processing with CUDA: Nvidia's high-performace computing platform uses massive multithreading[END_REF]. As a complex topic out of the scope of this paper, the reader is referred to the work of [START_REF] Nickolls | Scalable parallel programming with cuda[END_REF] for a detailed view on CUDA programming and modelling.

Parallel Watershed Algorithm

In this section we propose an algorithm for fully parallel SIMD implementation and a hybrid approach, based on both GPU and CPU. Firstly, the motivations and inspirations are presented. Next, the notation used is explained, and the algorithms depicted and explained. Lastly, implementation details are pointed out as well as performance considerations.

As presented on Sec. 2., there are several approaches for watershed algorithms. Even though the evolution of techniques achieved a great speedup in comparison with the first fast transforms, those are still not enough for applications such as instantaneous video analysis. Thus, the parallel approach seem obvious to achieve an even greater speedup. Along with the recent development on GPU parallel processing, presented on Sec. 3., with further optimisation for image processing, a new field for the watershed transform is seen, taking advantage of this massive many-core architecture.

This algorithm is inspired in both sequential and parallel previous algorithms presented on Sec. 2.. Among the sequential ones, the most influential is by [START_REF] Bieniek | An efficient watershed algorithm based on connected components[END_REF], which inspired on storing the pixel addresses for finding the steepest descent paths on a single step. The strategy of [START_REF] Galilée | Parallel asynchronous watershed algorithm-architecture[END_REF] of waiting for neighbourhood data to split non-minima plateaus is used along with the labelling of minima by neighbourhood evaluation, although in a different way, without explicit message passing.

Algorithm 1 presents our proposal for a parallel watershed transform. On the course of it, the statement for all denotes that every iteration can be processed in parallel, in a SIMD way, and there is a synchronisation step, where the next statement after the for all is only processed after every parallel process has terminated. The algorithm is divided in four major steps: find the lowest neighbour of each pixel (direct path of steepest descent); find the nearest border of internal pixels of plateaus, propagating uniformly from the borders; minima labelling by maximal neighbour address and pixel labelling by flooding from minima. The input image is called I, and the output labelled image is called lab, which is also used for storing addresses.

A similar algorithm has been proposed recently, though with modified strategies for labelling [START_REF] Körbes | A proposal for a parallel watershed transform algorithm for real-time segmentation[END_REF]. if ∃q ∈ N (p) : I(q) < I(p) and I(q) = min ∀q ′ ∈N (p) I(q ′ ) then if ∃q ∈ N (p) : lab(q) <= 0 and I(q) = I(p) then end for 37: end while For the parallel implementation of the algorithm, some parameters must be defined. The first one is the number of threads per block, in order to divide the processing and obtain the best performance. The image block size must be a multiple of the warp size, which is characterised as a minimum group of 64 threads, processed as SIMD by CUDA many-core architecture (NVIDIA, 2009b). Empirically, it is suggested the use of 256 threads as a good choice, balancing between memory latency, registers and threads.

Another parameter is the memory access. For this development, the texture memory is proposed, given its benefits compared to both global and constant memory. Some of these are (NVIDIA, 2009a): hardware-based linear interpolation and border management; potential higher bandwidth, once its cached. An observation is that the shared memory is used to store intermediary results, given that the texture memory is read-only.

Based on this approach, an image is taken as a grid divided in 16x16 pixels blocks, resulting in up to 256 threads. The image loaded on the CPU is copied to the texture memory of the GPU, where it is then processed via kernel access. The kernels were developed in two ways. The first is for step 1, which is based on texture memory access with block division as mentioned above, outputting its results to global memory. For the further steps, the other kernel demands a special approach, once pixel evaluation is highly guided by its neighbours. In effect, each block must include a border, containing neighbour pixels of the block, for correct processing. Fig. 2 shows the modelling used for each image block. To load data into blocks with edge, some parameters must be defined as the block size and grid, the window of data is processed and the radius of the edge in each axis. Considering coalescent data access, the block dimension is kept on 16x16, the grid obtained by the division between the size of the image processing window, whose value is 14x14. At that point, each block processes 196 threads, with other 60 inactive threads, were these data is processed by adjacent blocks. As the pixel depends on its nearest neighbors, the radius of the edge is set to 1. Using these parameters in hand with internal variables of the kernel, can obtain the index responsible for managing data in each block. As shown in the example below:

Definition of the index in the X axis to load the data with edge // Definition of the parameters . . .

4:

const int rangeStartx = BlockIdx.x * RAN GEW ;

5:

const int loadP osx = (rangeStartx -KERN ELRADIU S) + threadIdx.x; 6:

. . .

Once the data is loaded from the global memory to shared memory, the results are stored on output global memory, ensuring that border results do not overlap [START_REF] Podlozhnyuk | Image Convolution with CUDA[END_REF].

Along with these specifications, the algorithm is dependant on stabilisation steps, which are verified on the CPU. As the experimental results presented on Sec. 5. show, these steps contribute heavily for degrading the performance of Algorithm 1. Therefore, we propose a second algorithm, on a hybrid approach, were steps 1 and 2 are the same as Algorithm 1, processed on the GPU, and steps 3 and 4 are modified versions, processed on the CPU, achieving better performance. These steps follow general strategies of minima (connected component) labelling and path labelling found on algorithms such as [START_REF] Bieniek | A connected component approach to the watershed segmentation[END_REF], [START_REF] Osma-Ruiz | An improved watershed algorithm based on efficient computation of shortest paths[END_REF] and [START_REF] Lin | Comparison between immersion-based and toboggan-based watershed image segmentation[END_REF].

Algorithm 2: Hybrid watershed transform // First Step // Same as first step of Algorithm 1

1: P LAT EAU ← +∞ 2: for all p ∈ D do 3:
if ∃q ∈ N (p) : I(q) < I(p) and I(q) = min ∀q ′ ∈N (p) I(q ′ ) then if ∃q ∈ N (p) : lab(q) <= 0 and I(q) = I(p) then while lab(q) <= 0 do 39: q ← -lab(q) 40:

end while 41:

u ← p 42: while u = q do 43: v ← u 44: u ← -lab(u) 45: lab(v) ← lab(q) 46:
end while 47:

end if 48: end for

The procedures used for minima and path labelling on Algorithm 2 optimise performance given some conditions explained here. For most images, regional minima are composed by more than a few pixels, making the stabilisation step for minima labelling on Algorithm 1 take several turns, while on Algorithm 2 this analysis is done only once, and pixels receive its final labels as soon as visited. The same is valid for step 4, where long paths on Algorithm 1 take its length in number of turns to complete the labelling, while on Algorithm 2 pixels are visited only twice to receive its final labels. However, for step 2 a sequential approach would not improve the performance, as the border propagation is done similarly, though with a queue that restricts the set of pixels that are processed. Another consideration is that on every turn until stabilisation on Algorithm 1, each pixel is visited and processed, slowing its convergence. Along with these, CUDA is well suited for hybrid approaches, as mentioned on Sec. 3.1, and that improves the performance as seen on Sec. 5..

Experimental Results

For the experiments, was tested 4 different kinds of images on sizes ranging from 64x64 to 2048x2048, collecting 10 samples from each image to account for the overall average measured in each step. The data presented as follows is the average of the experiments, scaled to milliseconds (ms). The sequential algorithm implemented is a modified version of [START_REF] Lin | Comparison between immersion-based and toboggan-based watershed image segmentation[END_REF], which operates also on four steps very similar in purpose to those proposed on Algorithms 1 and 2, but without the watershed label, for matters of equivalence of definitions. Table 1 shows the performance for the sequential algorithm, processed on the CPU. These results were ob-tained on a computer with an AMD Phenom II X3 (2.6Ghz 7.5Mb Cache) with 4Gb RAM and a GeForce GTX295 with 1792Mb. Only one GPU core was used for the GPU processing.

Was applied watershed transform on an image 2D. An example is shown the popular image of Lena using the algorithm on the gradient and hmin (reconstructive filter the minimum) of the image. Fig. 4 1 shows that for the sequential algorithm, the first two steps are severe bottlenecks, greatly degrading the performance, specially on larger images. Moving to the fully parallel implementation on the GPU, developed according to Algorithm 1, Table 2 shows that the bottleneck on step 1 is completely mitigated, whereas for step 2 the performance depends on image size, though showing small improvements. However, for steps 3 and 4, the algorithm fails on achieving speedups, in fact, these steps contribute heavily for a poor overall performance. The observation that steps 1 and 2 of the parallel algorithm are more suited for GPU, and that steps 3 and 4 are more suited for the CPU, led to the hybrid algorithm, proposed on Algorithm 2. With the union of these steps, the resulting implementation achieved the time measurements of With the data collected on these three tables, a comparison may be done, checking the effective gain in time performance. This evaluation is seen on Table 4, where the algorithms are put aside and the relative gain is calculated for the average total time for each image size tested.

The analysis of the sequential algorithm. This is due to memory transfer bandwidth and the GPU clock, significantly slower than the CPU clock. This effect is reduced with the increase of image size, until the larger one tested, which falls into another problem. For this image, the second step is very time consuming, due to the stabilisation, reducing the gain. However, for average sizes of images -typically those produced by video cameras -the hybrid approach shows a gain of an average of 40%, meaning a reduction of time of almost half of the sequential algorithm. Lastly, we present a graph on Fig. 3, showing the increase of gain with the increase of image size, on average sizes.

Conclusion

In this paper we proposed two parallel watershed transform algorithms for implementation on many-core architectures, such as GPUs, and together with a CPU, taking advantage of the best hardware for each task. We reviewed the state of the art on both sequential and parallel algorithms and proposed a new one inspired on some techniques presented. Based on the results obtained on this fully parallel algorithm in comparison with a sequential version, a hybrid version was proposed, with the first two steps operating on the GPU and the last two on the CPU. Our algorithms are described along with the discussion of some of the implementation issues. With the hybrid algorithm, we achieved a significant speedup on images of average sizes (up to 1024x1024 pixels), being almost twice faster than the sequential algorithm. As the scope of this project lies on video analysis, with images of sizes closer to 512x512, the average time obtained of 18ms allows the segmentation to work on a rate of 30fps with extra time for other processing necessary, such as filtering.

Figure 1 :

 1 Figure 1: Structuring of data for implementation in parallel

Algorithm 1 :

 1 Parallel watershed transform // First Step 1: P LAT EAU ← +∞ 2: for all p ∈ D do 3:

  step 9: while lab is not stable do 10: lab ′ ← lab 11: for all p ∈ D : lab(p) = P LAT EAU do 12:

  all p ∈ D : lab(p) = P LAT EAU do 19: lab(p) = p + 1 20: end for 21: while lab is not stable do 22: for all p ∈ D : lab(p) > 0 do 23:for q ∈ N (p) do 24:if lab(q) > lab(p) then 25: lab(p) ← lab(q)

Figure 2 :

 2 Figure 2: Border behaviour to include neighbours outside of the block

  step // Same as second step of Algorithm 1 9: while lab is not stable do 10: lab ′ ← lab 11: for all p ∈ D : lab(p) = P LAT EAU do 12:

  ← 1 19: for p ∈ D do 20: if lab(p) = P LAT EAU then 21: lab(p) ← basins 22: basins ← basins + 1

Figure 3 :

 3 Figure 3: Graphic comparison of average time between algorithms

Figure 4 :

 4 Figure 4: Image of Lena (left), watershed computed on gradient and hmin of the image (right)

Table 1 :

 1 presents the results of watershed regions delimited by contours of the areas. Sequential algorithm processed on the CPU Table

	64x64 128x128 256x256 512x512 1024x1024 2048x2048
	Step 1 0,1821 0,7256	3,1650	11,9489	45,8002	171,0729
	Step 2 0,2751 1,1016	4,3633	17,8430	72,6984	306,1431
	Step 3 0,0386 0,1897	0,4629	1,6862	4,4622	17,0799
	Step 4 0,0554 0,1597	0,9337	3,5642	15,5848	70,0675
	Total 0,5511 2,1765	8,9249	35,0422 138,5456	564,3633

Table 2 :

 2 Parallel algorithm processed on the GPU

Table 3

 3

	64x64 128x128 256x256 512x512 1024x1024 2048x2048
	Step 1 0.8645 0.9912	1.5086	3.3537	10.0368	37.8606
	Step 2 0.2746 0.6246	2.2040	9.8523	56.3876	358.0210
	Step 3 0.0386 0.1897	0.4629	1.6862	4.4622	17.0799
	Step 4 0.0554 0.1597	0.9337	3.5642	15.5848	70.0675
	Total 1.2330 1.9652	5.1091	18.4564	86.4713	483.029

Table 3 :

 3 Hybrid algorithm processed on the GPU+CPU

  Table 4 must highlight two side-effects of GPU+CPU hybrid processing.The first one is for the smaller size, where this approach took more than twice the time than

		CPU	GPU	GPU + CPU Gain (%)
	64x64	0.5511	1.4820	1.2330	-123.75%
	128x128	2.1765	2.3909	1.9652	9.71%
	256x256	8.9249	6.4683	5.1091	42.75%
	512x512	35.0422	29.6566	18.4564	47.33%
	1024x1024 138.5456 113.7195	86.4713	37.59%
	2048x2048 564.3633 1564.2934	483.0290	14.41%

Table 4 :

 4 Comparison between algorithms