Mehdi Baba-Ali
email: babaali@sic.univ-poitiers.fr

Guillaume Damiand
email: damiand@labri.fr

Xavier Skapin
email: xavier.skapin@univ-poitiers.fr

David Marcheix
email: marcheix@ensma.fr

Insertion and expansion operations for n-Dimensional Generalized Maps ⋆ ⋆⋆

. Our goal is to build a theoretical framework for defining and handling n-dimensional "top-down" irregular pyramids. To do so, we propose in this paper to study the definition of both insertion and expansion operations that allow to conceive these kinds of pyramids.

Introduction

Hierarchical representations form the bases of several applications in the field of discrete imagery. Our goal is the study of basic problems related to the definition of hierarchical structures. To achieve this goal, removal and contraction operations have been defined in [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF]. In this paper, we define two others basic operations: insertion and expansion, which allow to define "top-down" pyramids.

Many works deal with regular or irregular image pyramids for multi-level analysis and treatments. The first ones are [START_REF] Burt | Segmentation and estimation of image region properties through cooperative hierarchical computation[END_REF][START_REF] Jolion | The adaptive pyramid : a framework for 2d image analysis[END_REF][START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Moutanvert | Hierarchical image analysis using irregular tesselations[END_REF]. In irregular pyramids, each level represents a partition of the pixel set into cells, i.e. connected subsets of pixels. There are two ways to build an irregular pyramid: "botom-up" and "topdown" 4 . In the first case, the number of cells increases between two contiguous levels of a pyramid, while in the second case this number of cells decreases. To manipulate these models, it is neccessary to handle a (topological) representation and some basic operations, for instance dual graphs [START_REF] Kropatsch | Building irregular pyramids by dual-graph contraction[END_REF] and removal and contraction operations [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF]. Grasset-Simon and al [START_REF] Grasset-Simon | nD generalized map pyramids: Definition, representations and basic operations[END_REF] build a theoretical framework for defining and handling n-dimensional "bottom-up" irregular pyramids. To do so, they use the removal and contraction operations, defined in [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF], in order to get consistent definitions of data structures for any dimension. Our goal is the same as [START_REF] Grasset-Simon | nD generalized map pyramids: Definition, representations and basic operations[END_REF]: build a theoretical framework, but for defining and handling n-dimensional "top-down" irregular pyramids. Therefore, we study the definition of insertion and expansion of i-dimensional cells within n-dimensional objects, in order to define the relations between two consecutive levels of a "top-down" pyramid. We also study the definition of these operations in order to set the links between "bottom-up" and "top-down" irregular pyramids. Indeed, insertion and expansion operations (basic operations used for the definition of "top-down" irregular pyramids) are, respectively, the inverse of removal and contraction operations (Fig. 1).

We choose to study the definitions of insertion and expansion operations for n-dimensional generalized maps, since this model enables us to unambiguously represent the topology of quasi-manifolds, which is a well-defined class of subdivisions [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF]. Note that several models based on combinatorial maps [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF] have been proposed for handling two-dimensional [START_REF] Brun | Segmentation d'images couleur à base topologique[END_REF][START_REF] Fiorio | Approche interpixel en analyse d'images: une topologie et des algorithms de segmentation[END_REF] and three-dimensional segmented or multi-level images [START_REF] Bertrand | Topological encoding of 3d segmented images[END_REF][START_REF] Braquelaire | 3d split and merge with 3 maps[END_REF][START_REF] Braquelaire | A topological structuring for aggregates of 3d discrete objects[END_REF]. We prefer to use generalized maps instead of combinatorial maps, since their algebraic definition is homogeneous; therefore, we can provide simpler definitions of data structures and operations with generalized maps, which are also more efficiency for the conception of softwares (note that several kernels of geometric modeling softwares are based upon data structures derived from this notion). Last, we know how to deduce combinatorial maps from generalized maps, so the results presented in this article can be extended to combinatorial maps. Precise relations between generalized, combinatorial maps and other classical data structures are presented in [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF].

We recall in Section 2 the notion of generalized maps, removal and contraction operations. Then we define the insertion operation of one i-dimensional cell in Section 3, and expansion operation by duality (in Section 4). In Section 5, we show that it is possible to simultaneously insert and expand several cells of the same dimension. Last, we conclude and give some perspectives in Section 6.

Recalls

Generalized maps

An n-dimensional generalized map is a set of abstract elements, called darts, and applications defined on these darts: 1. B is a finite set of darts; 2. ∀i, 0 ≤ i ≤ n, α i is an involution 5 on B; 3. ∀i, j, 0 ≤ i < i + 2 ≤ j ≤ n, α i α j is an involution (condition of quasimanifolds).

Let G be an n-G-map, and S be the corresponding subdivison. A dart of G corresponds to an (n+1)-tuple of cells (c 0 , ..., c n ), where c i is an i-dimensional cell that belongs to the boundary of c i+1 [START_REF] Brisson | Representing geometric structures in d dimensions: topology and order[END_REF]. α i associates darts corresponding with (c 0 , . . . , c n ) and (c ′ 0 , . . . , c ′ n ), where c j = c ′ j for j = i, and c i = c ′ i (α i swaps the two i-cells that are incident to the same (i -1) and (i + 1)-cells). When two darts b 1 and b 2 are such that b

1 α i = b 2 (0 ≤ i ≤ n), b 1 is said i-sewn with b 2 . Moreover, if b 1 = b 2 then b 1 is said i-free.
In Fig. 2, Dart 1 corresponds to (s 1 , a 1 , f 1 ), dart 2 = 1α 0 corresponds to (s 2 , a 1 , f 1 ), 3 = 2α 1 corresponds to (s 2 , a 2 , f 1 ), and 20 = 3α 2 corresponds to (s 2 , a 2 , f 2 ). G-maps provide an implicit representation of cells: Definition 2. (i-cell) Let G be an n-G-map, b a dart and i ∈ N = {0, ., n}. The i-cell incident to b is the orbit 6 N -{i} (b) = α 0 , . . . , α i-1 , α i+1 , . . . , α n (b).

An i-cell is the set of all darts which can be reached starting from b, by using any combination of all involutions except α i . In Fig. 2, the 0-cell (vertex) incident to dart 2 is the orbit α 1 , α 2 (2) = {2, 3, 20, 21}, the 1-cell (edge) incident to dart 3 is α 0 , α 2 (3) = {3, 4, 19, 20}, and the 2-cell (face) incident to dart 9 is α 0 , α 1 (9) = {9, 10, 13, 14, 17, 18}. The set of i-cells is a partition of the darts of 5 An involution f on S is a one mapping from S onto S such that f = f -1 . 6 Let {Π0, ..., Πn} be a set of permutations on B. The orbit of an element b relatively to this set of permutations is Π0, ..., Πn (b) = {Φ (b) , Φ ∈ Π0, ..., Πn }, where Π0, . . . , Πn denotes the group of permutations generated by {Π0, . . . , Πn}. the G-map, for each i between 0 and n. Two cells are disjoined if their intersection is empty, i.e. when no dart is shared by the cells. More details about G-maps are provided in [START_REF] Lienhardt | N-dimensional generalized combinatorial maps and cellular quasimanifolds[END_REF].

Removal and contraction operations

In a general way for an n-dimensional space, the removal of an i-cell consists in removing this cell and in merging its two incidents (i + 1)-cells: so removal can be defined for 0 . . . (n -1)-cells.

Definition 3. (i-cell removal [8]) Let G = (B, α 0 , . . . , α n ) be an n-G-map, i ∈ {0, . . . , n -1} and C = N -{i} (b) be an i-cell, such that: ∀b ′ ∈ C, b ′ α i+1 α i+2 = b ′ α i+2 α i+1 7 . Let B S = Cα i -C, the set of darts i-sewn to C that do not belong to C (Fig. 3). The n-G-map resulting from the removal of C is G ′ = (B ′ , α ′ 0 , . . . , α ′ n ) defined by: -B ′ = B -C; -∀j ∈ {0, . . . , n} -{i} , α ′ j = α j |B ′ ; 8 -∀b ′ ∈ B ′ -B S , b ′ α ′ i = b ′ α i ; -∀b ′ ∈ B S , b ′ α ′ i = b ′ (α i α i+1 ) k α i (where k is the smallest integer such that b ′ (α i α i+1 ) k α i ∈ B S ).

The last expression redefines involution

α i for each dart b ∈ B S in G. Indeed, the image of b by α ′ i is dart b ′ ∈ B S such that b and b ′ both are ends of path (α i α i+1 )
k α i . In Fig. 3a, darts 1 and 4 are the extremities of path (α 0 α 1 ) α 0 which is represented by a curving line.

Note that G ′ can contain only one n-cell, and may even be empty if G contains only one i-cell. Note also that contraction operation can be defined directly by duality (see section 4 for explanations on duality in G-map). More details about removal and contraction operations are provided in [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF]. 7 This constraint corresponds to the fact that the local degree of i-cell C is 2 (a vertex locally incident to exactly two edges or an edge locally incident to two faces or a face locally incident to two volumes...). 8 α ′ j is equal to αj restricted to B ′ , i.e. ∀b ∈ B ′ , bα ′ j = bαj .

Insertion

The insertion of an i-cell C into an n-G-map G consists (conversely to removal operation) in adding this cell to G and splitting an (i + 1)-cell where C should be inserted: so insertion can be defined for 0 . . . (n -1)-cells. In this section, we present some useful cases of 0 and 1-insertions in 1-and 2-dimensional space before giving the general definition in nD.

Dimension 1: 0-insertion

In dimension 1, only the 0-insertion exists, which consists in adding a vertex and splitting an edge where that vertex should be inserted. Let G = (B, α 0 , α 1 ) be the initial 1-G-map, C = α 1 (b) be the vertex to insert (belonging to another G-map) and E and F be two subsets of darts such that: E ⊆ B and F ⊆ C. These subsets allow to explicit where and how cell C will be inserted in G-map G by using an additional involution9 γ (Fig. 4). The 1-G-map resulting from 0insertion, called

G ′ = (B ′ , α ′ 0 , α ′ 1 )
, is obtained only by redefining α 0 for the darts of E and F as follows: ∀b ∈ E ∪ F, bα ′ 0 = bγ, where

B ′ = B ∪ C (α ′ 0 is unchanged for the darts of B ′ -(E ∪ F ), α ′ 0 = α 0 and α ′ 1 is unchanged for the darts of B ′ , α ′ 1 = α 1 )
. Furthermore, 0-insertion can be applied only if the following preconditions are satisfied: (1) ∀b ∈ C, b is 0-free and (2) ∀b ∈ E, bα 0 = bγα 1 (α 0 α 1 ) k γ (where k is the smallest integer such that bγα 1 (α 0 α 1 ) k ∈ F ). These constraints ensure the validity of the operation and the fact that 0-insertion is the inverse operation of 0-removal, by avoiding the following cases:

1. b ∈ E is not 0-free and bγ is 1-free. In such a case, we have

C = F = {bγ}, b ′ = bα 0 ∈ B -E and b ′ = bγ. Thus, we have b ′ α ′ 0 = b ′ α 0 = b and b ′ α ′ 0 α ′ 0 = bα ′ 0 = bγ = b ′ . α ′ 0
is not well-defined since it is not an involution (Fig. 4b); 2. b ∈ E is not 0-free and it does not exist a path between darts b and bα 0 expressed by the following composition of involutions γα 1 (α 0 α 1 ) k γ. Indeed, for the same reason that the previous case, α ′ 0 is not well-defined and is not an involution; 3. it exists a path 10 between two darts b and b ′ of F such that b = b ′ and bγ is 0-free or bγα 0 = b ′ γ. In such a case, we do not obtain the same 1-G-map G after successively inserting then removing a 0-cell C; hence, the 0-insertion is not the inverse operation of 0-removal (Fig. 5).

In Fig. 4c, the 0-insertion of C 2 is obtained by redefining α 0 for the darts of E 2 = {1, 2} and F 2 = {5, 6} such that: 1α ′ 0 = 5 and 2α ′ 0 = 6. Note that α 1 is not modified by 0-insertion.

Dimension

2 0-insertion It consists in adding a 0-cell C = α 1 , α 2 (b) into an initial 2-G- map G = (B, α 0 , α 1 , α 2 )
. There are several ways to carry out this operation. Indeed, several possible combinations enable to link the darts of C with those of B (Figs. 6b and6c). Then, it is necessary to remove this ambiguity by defining an involution that enables to characterize these links in a single way. Let γ be this involution and E and F be two subsets of darts (γ, E and F are defined as above and respect the same properties). The 2-G-map resulting from 0-insertion, called

G ′ = (B ′ , α ′ 0 , α ′ 1 , α ′ 2 )
, is obtained by redefining α 0 for the darts of E and F as follows: ∀b ∈ E ∪ F, bα ′ 0 = bγ. In Fig. 6c, 0-insertion consists in setting 1α ′ 0 = 5, 2α ′ 0 = 8, 3α ′ 0 = 7 and 4α ′ 0 = 6. Note that this redefinition of α 0 is the same as for dimension 1 but concerns different darts, since it is a 0-cell within a 2D object (intuitively, in the general case, this operation consists in applying the 0-insertion defined for dimension 1 twice). 0-insertion can be applied only if the following preconditions are satisfied:

1. ∀b ∈ E ∪F such that bα 2 ∈ E ∪F then bα 2 γ = bγα 2 . This constraint enables to guarantee the quasi-manifold of the resulting 2-G-map:

∀b ∈ E ∪ F, α ′ 0 α ′ 2
is an involution, by using the following substitutions: 2. ∀b ∈ C, bα 1 α 2 = bα 2 α 1 : this constraint corresponds, in the general case, to the fact that the local degree of the vertex is equal to 2. If this constraint is not satisfied, we cannot remove C after inserting it. Indeed, ∀b ∈ C, bα 1 α 2 = bα 2 α 1 is also a precondition of the removal operation [START_REF] Damiand | Removal and contraction operations to define combinatorial pyramids: application to the design of a spatial modeler[END_REF]. Thus, in order to define insertion operation as inverse of removal operation, it is necessary to check this precondition; 3. ∀b ∈ E, bα 0 = bγα 1 (α 0 α 1 ) k γ (where k is the smallest integer such that bγα 1 (α 0 α 1 ) k ∈ F ): this constraint is the same as the one defined in the previous section.

∀b ∈ E ∪ F, bγ = bα ′ 0 and ∀b ∈ E ∪ F, bα 2 = bα ′ 2 . Then, we obtain ∀b ∈ E ∪ F, bα 2 γ = bγα 2 ⇔ bα ′ 2 α ′ 0 = bα ′ 0 α ′ 2 . Thus, α ′ 0 α ′ 2 is

1-insertion It consists in adding a 1-cell

C = α 0 , α 2 (b) into an initial 2- G-map G = (B, α 0 , α 1 , α 2 )
. Let E and F be two subsets of darts and γ an involution (E, F and γ are defined as in subsection 3.1). The 2-G-map G ′ , resulting from 1-insertion, is obtained by redefining α 1 for the darts of E and F as follows: ∀b ∈ E ∪ F, bα ′ 1 = bγ. Examples of this operation are represented in Figs. 7 and8. 1-insertion can be applied only if the following precondition is satisfied: ∀b ∈ E, bα 1 = bγα 2 (α 1 α 2 ) k γ (where k is the smallest integer such that: bγα

2 (α 1 α 2 ) k ∈ F ).
The first two preconditions, defined in the previous subsection, are always satisfied. Indeed, for the first case, G ′ is a quasi-manifold since only α 1 is redefined by 1-insertion operation, and α 0 α 2 is an involution in G; for the second case, the local degree of an edge in a 2-dimensional quasi-manifold is always equal to 2.

Dimension n

The general definition of i-cell insertion for an n-dimensional G-map is a direct extension of the previous cases. Let C be the i-cell to insert, E and F be two subsets of darts. i-insertion of C in G is carried out by sewing darts of F with those of E by an involution γ. Then i-insertion consists in redefining α i for the darts of E and F in the following way: bα ′ i = bγ. We obtain the general definition of the i-insertion operation: Definition 4. (i-cell insertion) Let G = (B, α 0 , α 1 , . . . , α n ) be an n-G-map, i ∈ {0, . . . , n -1}, C = α 0 , . . . , α i-1 , α i+1 , . . . , α n (b) be the i-cell to insert, E and F be two subsets of darts such that: E ⊆ B and F ⊆ C and γ be an involution defined on set E ∪ F such that: b ∈ E ⇔ bγ ∈ F . This operation can be applied only when:

-∀b ∈ F, b is i-free; -∀b ∈ C, bα i+1 α i+2 = bα i+2 α i+1 11 ; -∀b ∈ E ∪ F, ∀j 0 ≤ j ≤ n such that |i -j| ≥ 2 and bα j ∈ E ∪ F then bα j γ = bγα j ; -∀b ∈ E, bα i = bγα i+1 (α i α i+1 ) k γ (where k is the smallest integer such that bγα i+1 (α i α i+1 ) k ∈ F ).
The n-G-map resulting from the insertion of C is G ′ = (B ′ , α ′ 0 , . . . , α ′ n ) defined by:

-B ′ = B ∪ C; -∀j ∈ {0, . . . , n} -{i} , ∀b ∈ B ′ : bα ′ j = bα j ; -∀b ∈ B ′ -(E ∪ F ) : bα ′ i = bα i ; -∀b ∈ E ∪ F : bα ′ i = bγ.
The constraints of definition 4 enable to ensure that: the local degree of C is equal to 2, the resulting n-G-map is a quasi-manifold and insertion operation is the inverse of removal operation.

Note that, in the definition of G ′ , only α i is redefined for the darts of E ∪ F . Indeed, i-insertion involves the sewing of darts of F with those of E by α ′ i which is equal to γ. For everything else, the initial n-G-map remains unchanged. Now, we prove the validity of the operation by showing that the new structure

G ′ is a n-G-map. Theorem 1 G ′ is an n-G-map.
Proof. We differentiate three cases. First for j = i, involutions α j are not redefined but only restricted to the darts of the final G-map. Then, for j = i, we distinguish two cases, depending on if darts belong or not to E ∪ F :

1. for b 1 ∈ B -E: We show that b 2 = b 1 α i ∈ B -E. Assume that b 2 / ∈ B -E, then b 2 ∈ E. In this case, b 1 = b 2 α i ∈ E 12 so b 1 / ∈ B -E: contradiction. Moreover, b 1 α ′ i = b 1 α i ∈ B -E and b 1 α ′ i α ′ i = b 1 : α ′ i is
well-defined and is an involution (we use the same method for the darts of C -F ).

for b

1 ∈ E ∪ F , We show that b 2 = b 1 γ ∈ E ∪ F . That is true because γ is well-defined and is an involution on set E ∪ F . Moreover, b 1 α ′ i = b 1 γ ∈ E ∪ F and b 1 α ′ i α ′ i = b 1 γγ = b 1 : α ′ i is
well-defined and is an involution. We have now to prove that ∀j, 0

≤ j ≤ n, ∀k, j + 2 ≤ k ≤ n : α ′ j α ′ k is an involution. -for j = i et k = i: this is obvious since α ′ j = α j and α ′ k = α k . As G is a G-map, α j α k = α ′ j α ′ k is an involution. -for j = i: we show that ∀b 1 ∈ B ′ , we have b 1 α ′ i α ′ k = b 1 α ′ k α ′ i : 1. for b 1 ∈ B -E: b 1 α ′ i = b 1 α i and α ′ k = α k . Since G is a G-map, b 1 α i α k = b 1 α k α i ; since b 1 α k = b 1 α ′ k ∈ B -E (indeed, assume that b 2 = b 1 α k ∈ E. In this case, b 1 = b 2 α k ∈ E: contradiction), b 1 α k α i = b 1 α ′ k α i whence b 1 α k α i = b 1 α ′ k α ′ i ; thus b 1 α ′ i α ′ k = b 1 α ′ k α ′ i . 2. for b 1 ∈ C -F : similar to the previous case. 3. for b 1 ∈ E: b 1 α k ∈ E and b 1 α k γ = b 1 γα k (precondition of the insertion operation). So, b 1 α ′ i = b 1 γ, b 1 α k α ′ i = b 1 α ′ i α k . Moreover, ∀b ∈ B, bα j = bα ′ j ; thus, b 1 α ′ j α ′ i = b 1 α ′ i α ′ j (same
method for the darts of F ). -for k = i: similar to the previous case.

⊓ ⊔

Expansion

Informally, i-expansion consists in adding an i-cell "inside" an (i -1)-cell. Expansion is the dual of the insertion operation. The dual of a subdivision is a subdivision of the same space, for which an (n -i)-cell is associated with each initial i-cell, and incidence relations are kept the same. A nice property of G-maps is the fact that the dual G-map of G = (B, α 0 , . . . , α n ) is G ′ = (B, α n , . . . , α 0 ): we only need to reverse the involution order. We can thus easily deduce the definition of i-expansion from the general definition of i-insertion. We only have to replace '+' with '-' for indices of involutions for preconditions and operations, i.e. α i+1 α i+2 → α i-1 α i-2 and α i α i+1 → α i α i-1 (see two examples of expansion in Figs. 9 and 10). Definition 5. (i-expansion) Let G = (B, α 0 , α 1 , . . . , α n ) be an n-G-map, i ∈ {0, . . . , n -1}, C = N -{i} (b) be the i-cell to expand, E and F be two subsets of darts such that: E ⊆ B and F ⊆ C, γ be an involution defined on set E ∪ F such that: b ∈ E ⇔ bγ ∈ F . This operation can be applied only when: -

∀b ∈ F, b is i-free; -∀b ∈ C, bα i-1 α i-2 = bα i-2 α i-1 ; 13 -∀b ∈ E ∪ F, ∀j 0 ≤ j ≤ n such that |i -j| ≥ 2 and bα j ∈ E ∪ F then bα j γ = bγα j ; -∀b ∈ E et bα i = bγα i-1 (α i α i-1 ) k γ (where k is the smallest integer such that bγα i-1 (α i α i-1 ) k ∈ F ).
The n-G-map resulting from the expansion of this i-cell is G ′ = (B ′ , α ′ 0 , . . . , α ′ n ) defined by:

-B ′ = B ∪ C; -∀j ∈ {0, . . . , n} -{i} , ∀b ∈ B ′ : bα ′ j = bα j ; -∀b ∈ B ′ -(E ∪ F ) : bα ′ i = bα i ; -∀b ∈ E ∪ F : bα ′ i = bγ.
Theorem 2 G ′ is an n-G-map.

The proof for the expansion operation is equivalent by duality (exchange α (i+1) and α (i-1) ) to the proof of theorem 1.

⊓ ⊔

Generalisation

Previous definitions enable us to insert or to expand a single cell. For some applications, it could be more efficient to simultaneously apply several operations. In practice, let G be an n-G-map and G ′ another n-G-map 14 to insert (resp. to expand). The only difference with the definition of one insertion (resp. expansion) is that G ′ can contain several i-cells. Thus, the only modification in definition 4 (resp. definition 5) consists in replacing C, the i-cell to insert (resp. to expand) by G ′ , the set of i-cells. This allows us to apply simultaneously a set of operations and to obtain the same result as if we had successively applied the operations. For this generalisation, there is no additional precondition since i-cells are always disjoined in a n-G-map. We now show that it is possible to simultaneously perform insertions (resp. expansions) of several i-cells for a given i (0 ≤ i ≤ n).

Generalisation 1

We can easily prove that the previous definition of insertion (resp. expansion) stands for the insertion (resp. expansion) of a set of cells with the same dimension i.

In order to prove this claim, we can follow the same method described in the proof of theorem 1: just consider the sewing between the darts of G and the darts of different i-cells of G ′ .

In Fig. 11, the 2-G-map G ′ to insert contains four 1-cells: α 0 , α 2 (11), α 0 , α 2 (12), α 0 , α 2 (23) and α 0 , α 2 [START_REF] Moutanvert | Hierarchical image analysis using irregular tesselations[END_REF]. The first three edges are linked by α 1 , and the fourth edge is independent. Furthermore, the simultaneous insertion of these edges consists in sewing the darts of E = {1, 2, . . . , 10, 27, 28} and those of F = {11, 12, . . . , 20, 23, . . . , 26} (it is the same process as the one given in definition 4).

Conclusion and Perspectives

In this paper, we have defined insertion and expansion operations, which can be applied to one i-cell of any n-G-map, whatever their respective dimensions. Moreover, we have studied how to perform the same operations simultaneously. These definitions are homogeneous for any dimension. Since combinatorial maps can be easily deduced from orientable generalized maps, these operations can also be defined on combinatorial maps.

In order to conceive efficient algorithms, an interesting perspective is to perform different operations simultaneously: insertion and expansion of cells of different dimensions. We think that, in this case, we can apply the same preconditions as the ones used for insertion and expansion operations. Next, we will study "top-down" pyramids of n-dimensional generalized maps defined as stacks of n-G-map where each n-G-map is built from the previous level by inserting

Fig. 1 .

 1 Fig. 1. Links between the basic operations which allow to handle irregular pyramids.

Fig. 2 .

 2 Fig. 2. (a) A 2D subdivision. (b) The corresponding 2-G-map (involutions are explicitly given in the array). Darts are represented by numbered black segments.

Fig. 3 .

 3 Fig. 3. 0-removal in 1D. (a) Initial 1-G-map. (b) Result. Vertex C = α1 (2) = {2, 3} and Cα0 = {1, 4} = B S . 0-removal consists in setting 1α ′ 0 = 1 (α0α1) α0 = 4 ∈ B S and 4α ′ 0 = 4 (α0α1) α0 = 1 ∈ B S .

Fig. 4 .

 4 Fig. 4. 0-insertion in 1D. (a) Initial 1-G-map G corresponds to the orbit α0, α1 (1), 0-cell C1 = α1 (7) = {7}, E1 = {3}, F1 = {7}, involution γ is represented by dashed lines: γ sews darts 1, 2 and 3 with darts 5, 6 and 7, respectively. 0-cell C2 = α1 (5) = {5, 6}, E2 = {1, 2}, F2 = {5, 6}. (b) Invalid result after inserting C1 into G (α0 is no more an involution since 3α0 = 7 and 4α0 = 3). (c) Valid result after inserting C2 into G (the precondition bα0 = bγα1γ is satisfied for all darts of E2).

Fig. 5 .

 5 Fig. 5. Example where the precondition of the 0-insertion is not satisfied. (a) Darts of the vertex C to insert and to remove are numbered 3 and 4. Involution γ is marked with dashed line. E and F are two subsets of 0-free darts defined as: E = {1, 2} and F = {3, 4}. (b) Resulting 1-G-map G ′ after sewing the darts of F with those of E (0-insertion without precondition). (c) Resulting 1-G-map after removing C from G ′ : darts 1 and 2 are now sewed by α0, whereas they were 0-free before insertion.

Fig. 6 .

 6 Fig. 6. 0-insertion in 2D. (a) 0-cell C = α1, α2 (5) = {5, 6, 7, 8}, E = {1, 2, 3, 4}, F = C, initial 2-G-map G corresponds to the orbit α0, α1, α2 (1). Involution γ1 is represented by dashed lines and links darts 1, 2, 3 and 4 with 5, 6, 7 and 8, respectively. Involution γ2 (not shown on the figure) links darts 1, 2, 3 and 4 with 5, 8, 7 and 6, respectively. (b) Resulting 2-G-map after inserting C into G by using involution γ1. (c) Resulting 2-G-map after inserting C into G by using involution γ2.

Fig. 7 .

 7 Fig. 7. 1-insertion in 2D in the general case. (a) Darts of the edge to insert are numbered 1, 2, 3 and 4. Involution γ is represented by dashed line. (b) Result. The precondition of the 1-insertion is satisfied: 5α1 = 5γα2γ = 6 (here, k = 0).

Fig. 8 .

 8 Fig. 8. 1-insertion of a loop. (a) Initial 2-G-map with the loop to insert and involution γ. (b) Result. The precondition of the 1-insertion is satisfied: 13α1 = 13γα2 (α1α2) γ = 14.

Fig. 9 .

 9 Fig. 9. 1-expansion in 1D. (a) Darts of the edge to expand are numbered 2 and 3. Involution γ are marked with dashed line. (b) Result.

Fig. 10 .

 10 Fig. 10. 1-expansion in 2D. (a) Initial 2-Gmap with the edge to expand and involution γ. (b) Result.

Fig. 11 .

 11 Fig. 11. An example in 2D of simultaneous insertion of 1-cells. (a) 2-G-map before operation with the 1-cells to insert and involution γ (represented by dashed lines). (b) The resulting 2-G-map. The darts belonging to inserted 1-cells are numbered 11, 12, . . . , 26. For instance, 1α1 = 1γα2 (α1α2) 2 γ = 2 since three edges α0, α2 (11), α0, α2 (12) and α0, α2 (23) are inserted around the same vertex.

γ is defined on set E ∪ F as follows: b ∈ E ⇔ bγ ∈ F .

Note that this condition does not apply for i = n -1, so we can always insert any (n -1)-cell.

According to the previous preconditions, b2αi = b2γαi+1 (αiαi+1) k γ. Since b2γαi+1 (αiαi+1) k ∈ F then b2αi = b2γαi+1 (αiαi+1) k γ ∈ E.

Note that this condition does not apply for i = 1, so we can always expand any edge.

supported by the ANR program ANR-06-MDCA-015/VORTISS.

or expanding cells. This will be made for example within the Fogrimmi project whose goal is to define "top-down" pyramids to analyse biological medical images.


Alexandre Dupas
email: dupas@sic.univ-poitiers.fr

Guillaume Damiand
email: damiand@labri.fr

First Results for 3D Image Segmentation with Topological Map ⋆ ⋆⋆

Keywords: Topological model, 3D Image segmentation, Intervoxel boundaries, Combinatorial maps

This paper presents the first segmentation operation defined within the 3D topological map framework. Firstly we show how a traditional segmentation algorithm, found in the literature, can be transposed on a 3D image represented by a topological map. We show the consistency of the results despite of the modifications made to the segmentation algorithm and we study the complexity of the operation. Lastly, we present some experimental results made on 3D medical images. These results show the process duration of this method and validate the interest to use 3D topological map in the context of image processing.

Introduction

Segmentation of 3D images is a great challenge in many fields as for example in the analysis of medical images. The segmentation refers to the process of partitioning an image into regions which are homogeneous to a criterion. This kind of approach, called region-based segmentation, requires a representation of regions in the image.

There are many works that have studied the definition of such a structure to represent images. Topological data structures describe the image as a set of elements and their neighborhood relations. The most famous example is the Region Adjacency Graph (RAG) [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF] which represents each region by a vertex, and where neighboring regions are connected by an edge. But the RAG suffers from several drawbacks as it does not represent multiple adjacency or makes no difference between inclusion and adjacency relations. To solve these issues the RAG model has been extended, for instance in dual-graph structure to represent 2D images [START_REF] Kropatsch | Finding the structure of connected components using dual irregular pyramids[END_REF] or in topological maps [START_REF] Bertrand | Topological map: Minimal encoding of 3d segmented images[END_REF][START_REF] Braquelaire | Representation of segmented images with discrete geometric maps[END_REF][START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF][START_REF] Fiorio | A topologically consistent representation for image analysis: the frontiers topological graph[END_REF]. These last have already been used in segmentation of 2D images [START_REF] Braquelaire | Image segmentation with topological maps and interpixel representation[END_REF][START_REF] Haxhimusa | Hierarchical image partitioning using combinatorial maps[END_REF] and a previous work has defined two operations on 3D topological maps needed to achieve image segmentation [START_REF] Damiand | Split and merge algorithms defined on topological maps for 3d image segmentation[END_REF] but without using it in a segmentation process.

Our general objective is to develop segmentation operations which profit from all the information stored by topological maps. As a first step toward this goal, we show in this paper how topological maps may be used as a 3D image representation model in a traditional segmentation process. In our knowledge, this is the first time that 3D image segmentation is achieved by using combinatorial maps.

In the literature, we found a region-based segmentation method, proposed by P. F. Felzenszwalb and D. P. Huttenlocher in [START_REF] Felzenszwalb | Image segmentation using local variation[END_REF], which seems to provide interesting results. This method merges neighboring homogeneous regions in order to produce another homogeneous region. This approach of the segmentation is called bottom-up. As a variant of the split-and-merge methods, it consists in the merging of small regions into bigger ones. In the original work, the segmentation using a local criterion is defined on 2D graph representation of the image, but was extended to different models and in particular to a hierarchical combinatorial map representation of 2D image in [START_REF] Haxhimusa | Hierarchical image partitioning using combinatorial maps[END_REF].

In this paper we present how this segmentation technique can be transposed to the topological map framework. The implementation of the homogeneity criterion, its computation and the algorithm used are also provided. We show that the results obtained with this method are similar to those that could be obtained with the original approach. Moreover the processing time is suitable for 3D image segmentation as it allows to segment real medical images. At this time, using topological map does not improve original methods. The next step of this work is to mix this approach with topological criteria to improve the segmentation results and show the contribution of topological maps to the 3D image processing.

We first present in Sect. 2 topological maps, which are combinatorial maps verifying specific properties, used to represent 3D images. We also introduce a topological map manipulation operation used in this work : the region merging. Then, Sect. 3 details the criterion and presents the segmentation algorithm. We also explain why despite the differences between this method and the classical one, the results are similar. In Sect. 4 we present the complexity analysis of the segmentation operation and we give some experimental results on 3D medical images. Lastly, we conclude and give some perspectives in Sect. 5.

Recalls on 3D Topological Maps

A 3D topological map is an extension of a combinatorial map used to represent a 3D image partition. Let us recall the notions of combinatorial maps, 3D images, intervoxel elements and topological maps that are used in this work.

Combinatorial Map

A combinatorial map is a mathematical model describing the subdivision of a space, based on planar maps. A combinatorial map encodes all the cells of the subdivision and all the incidence and adjacency relations between the different cells, and so describe the topology of this space.

A combinatorial map can be obtained intuitively by successive decompositions as we can see in Fig. 1. To describe the 3D object shown in Fig. 1 A, we first decompose the volumes of this object (Fig. 1 B) then the faces of these volumes (Fig. 1 C) and finally the edges of these faces (Fig. 1 D). At each step, we keep the adjacency relations between the decomposed cells (drawn by black segments but only partially drawn for the last step). The obtained elements after the last decomposition are called darts and are the only basic elements used in the definition of the combinatorial maps. In order to obtain the map, we report each adjacency relation onto darts. We call β i the relation between two darts which describes an adjacency between two i-dimensional cells. Figure 1 E presents the combinatorial map corresponding to object shown in Fig. 1 A The different constraints of the 3-map definition (β 1 is a permutation, other β i are involutions and β 1 • β 3 is an involution) ensures the topological validity of described objects. For example, intuitively the last constraint says that two volumes can not be partially adjacent. If two volumes are adjacent for a face, they must be adjacent for all the edges of the face. See [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF] for more details on maps and comparison with other combinatorial models.

3D Images and Intervoxel Elements

Let us now recall some usual notions about images and intervoxels elements. A voxel is a point of discrete space Z Z 3 associated with a value which could be a color or a gray level. A three dimensional image is a finite set of voxels. In this work, combinatorial maps are used to represent voxel sets having the same labeled value and which are 6-connected. The label of a voxel is given by a labeled function l : Z Z 3 → L which gives for each voxel its label (a value in the finite set L). We speak about region for a maximal set of 6-connected voxel having the same label.

To avoid particular process for the image border voxels, we consider an infinite region R 0 that surrounds the image. If a region R j is completely surrounded by a region R i we say that R j is included in R i .

In the intervoxel framework [START_REF] Khalimsky | Boundaries in digital planes[END_REF], an image is considered as a subdivision of a 3-dimensional space in a set of cells: voxels are the 3-cells, surfels the 2-cells between two 3-cells, linels the 1-cells between two 2-cells and pointels the 0-cells between two 1-cells.

Topological Map

The topological map is a data structure used to represent the subdivision of an image into regions. It is composed of three parts:

a minimal combinatorial map representing the topology of the image; -an intervoxel matrix used to retrieve geometrical information associated to the combinatorial map. The intervoxel matrix is called the embedding of the combinatorial map; -an inclusion tree of regions. Figure 2 presents an example of topological map. The 3D image, divided into three regions plus the infinite region R 0 (Fig. 2 A), is represented by the topological map which is divided in three parts labeled B, C and D. The minimal combinatorial map extracted from this image is displayed in Fig. 2 B. The embedding of the map is represented in Fig. 2 C and the inclusion tree of regions in Fig. 2 D.

The combinatorial map allows the representation of all the incidence and adjacency relations between cells of the subdivision. In the topological map framework, we use the combinatorial map as a topological representation of the partition of an image in regions. Each face of the topological map is separating two adjacent regions and two adjacent faces do not separate the same two regions. With these rules, we ensure the minimality (in number of cells) of the topological map (see [START_REF] Damiand | Définition et étude d'un modèle topologique minimal de représentation d'images 2d et 3d[END_REF][START_REF] Damiand | Split and merge algorithms defined on topological maps for 3d image segmentation[END_REF] for more details on topological maps).

The intervoxel matrix is the embedding of the combinatorial map. Each cell of the map is associated with intervoxel elements representing geometrical information of the cell. A face in the combinatorial map is embedded by a set of surfels separating voxels of the two incident regions. The edges, which are the border of faces, are represented by a set of linels. The vertices, which are the border of edges, are embedded by pointels. Thus the intervoxel matrix allows to retrieve the geometry of the labeled image represented by the combinatorial map.

R 1 R 2 R 3 R
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1
R 1 R 2 R 3 R 0 A B C D
The inclusion tree of regions represents the inclusion relations. Each region in the topological map is associated to a node in the inclusion tree. The nodes are linked together by the inclusion relation defined in Sect. 2.2. To link this tree with the combinatorial map, each dart d of the map knows its belonging region (called region(d)). Each region R knows one of its dart called representative dart (called rep(R)).

The topological map can be modified by using an operation of regions merging [START_REF] Dupas | Comparison of local and global region merging in the topological map[END_REF]. This process, called global merge, allows to merge any number of sets of connected regions. In the resulting topological map, each set of connected regions is represented by only one region.

In order to handle such sets, we use a disjoint-set forest [START_REF] Cormen | Introduction to Algorithms[END_REF] of regions. We use the union-find trees to represent the disjoint-sets. The two possible operations on sets are the union of two sets, and find the corresponding set of a particular element. In [START_REF] Tarjan | Efficiency of a good but not linear set union algorithm[END_REF], R. Tarjan shows that union and find on disjoint-set represented by trees can be considered as constant time operations.

The principle of the algorithm of global merging is to remove all existing faces between regions of a same set: we remove the faces in the combinatorial map and their corresponding embedding. The next step is to simplify incident cells to respect the minimality of the topological map. This process is also performed both in the combinatorial map and in the embedding. The last step of the global merging process is to rebuild the inclusion tree by using the list of the remaining regions and the combinatorial map already built.

The complexity of this operation is O(|D|+|S|) where |D| is the total number of darts in the combinatorial map and |S| is the number of surfels of the removed faces in the embedding (see [START_REF] Dupas | Comparison of local and global region merging in the topological map[END_REF] for more details).

Operation of Segmentation

The segmentation is an image processing operation which leads to partition an image into multiple regions. The goal of segmentation is to simplify the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects in images.

The result of image segmentation is a set of regions that cover the entire image. All voxels in a region are similar with respect to some characteristics or computed properties, such as color or intensity. Adjacent regions are significantly different with respect to the same characteristics.

Let us present the characteristic used in this work to show the capacity of the topological map to be used in an image processing operation.

Criterion Used in the Segmentation Process

This method uses a local criterion proposed by P. F. Felzenszwalb and D. P. Huttenlocher in [START_REF] Felzenszwalb | Image segmentation using local variation[END_REF]. This segmentation criterion is based on intensity differences between neighboring pixels in 2D image. It is a region based segmentation using a characteristic onto regions and another characteristic between neighboring regions to produce a well-segmented (i.e. not over-segmented neither undersegmented) partition of the image.

We recall the principle of this segmentation. Each couple of adjacent regions is characterized by an external variation (Ext(R i , R j )). This value is the smallest intensity difference between neighboring voxels, one belonging to R i and the other one belonging to R j .

Each region is characterized by an internal variation (Int(R)): this value depends on voxels that are contained in the region. If a region contains voxels of the same intensity, its internal variation is 0. The authors in [START_REF] Felzenszwalb | Image segmentation using local variation[END_REF] prove that the new internal variation of two neighboring regions merged is equal to the external variation between the two regions. It allows the incremental computing of the internal variation of regions during the segmentation process.

We say that two regions are similar, and should be merged into one region, when the external variation between the regions is smaller than their minimum internal variation:

Ext(R i , R j ) ≤ M Int(R i , R j )
Where the minimum internal variation M Int is

M Int(R i , R j ) = min(Int(R i ) + τ (R i ), Int(R j ) + τ (R j ))
The threshold function τ controls the degree to which the external variation can actually be larger than the internal variations, and still have the regions be considered similar. We use, in this work, the same function as in the original work which depends on the size of the region, τ (R) = k/|R| where |R| is the size (in number of voxels) of the region R and k is a constant defined by the user depending on the considered image.

To use this process with the topological map, the notion of external variation is transposed on faces. We define the external difference of a face F to be the smallest intensity difference between neighboring voxels across the face F (i.e. one voxel is on a side of the face, and its neighboring voxel is on the other side).

This value is related to the external variation of regions by the following formula. Let be two regions R i and R j witch are adjacent by k faces F p , p ∈ [1..k]. The external variation Ext(R i , R j ) is equal to the minimum external variation of the faces F p with p ∈ [1..k]. This gives the following formula:

Ext(R i , R j ) = min(Ext(F p ), p ∈ [1..k])
For performance purposes, we store these values into the topological map. Each dart of the topological map knows both its belonging region and its belonging face. With the help of this structure, we store on each face its external variation and on each region its internal variation. These values are computed during the creation of the topological map and each operation applied to the map updates these values accordingly. So for each region and face of the topological map, we retrieve the corresponding variations in a constant time.

Algorithm

Algorithm 1 shows the segmentation process using a threshold function to produce the optimal6 segmentation of the 3D image represented by the given topological map.

This process is divided in two steps. First, we build a symbolic merging of the regions. This step corresponds to the choice of the regions to merge in the topological map. Then, we use the merging operation recalled in Sect. 2.3 to convert the symbolic merging into an effective one.

The first step uses a disjoint-set forest of regions to efficiently represent the symbolic merging of regions. Before the segmentation, each region belongs to its own set. To merge symbolically two regions, we merge the two disjoint-set representing these regions. We compute the new characteristics of the resulting region and we set them to the head of the disjoint-set (which represents the resulting region).

To initialize the process, we build a list of faces sorted by increasing external variation. The first face in the list has the lowest external variation. In fact, each face his represented by one of its darts. To build the list, we run through each dart of the topological map. If its incident face is not marked, we add the current dart to the list L and we mark the corresponding face. When all the darts have been processed, the list contains one dart for each face of the image. Then the list is sorted by increasing order of the external variation of the incident face, by using a classical sort algorithm.

For each dart, we first check if the two incident regions around the incident face are not already merged. This is performed by checking if the belonging region is possible for the two regions to merge when considering the other faces. There are two cases to consider.

If M Int(R 1 , R 2 ) does not change, the process of the other faces can not leads to the merging of the two regions since they have a greater external variation.

If M Int(R 1 , R 2 ) increases its value between the treatment of two faces F i and F j (i ≥ 1 and j > i) we have to show that this modification will not alter the result of the algorithm.

Let suppose

Int(R 1 ) + τ (R 1 ) < Int(R 2 ) + τ (R 2 ) and thus M Int(R 1 , R 2 ) = Int(R 1 )+τ (R 1
) (this supposition can be made without lost of generality, eventually by renaming the two regions). So M Int(R 1 , R 2 ) increases only if Int(R 1 ) + τ (R 1 ) increases. This is only possible if R 1 is merged with another neighboring region which will be called R 3 .

To merge R 1 and R 3 , we need a face F so that Ext(F ) ≤ M Int(R 1 , R 3 ). Since the list is sorted Ext(F 1 ) ≤ Ext(F ), and by definition of M Int, M Int(R 1 , R 3 ) ≤ Int(R 1 )+τ (R 1 ). Our starting hypothesis gives that Ext(F 1 ) > Int(R 1 )+τ (R 1 ). When combining these assertions, we have:

Ext(F ) ≥ Ext(F 1 ) > Int(R 1 ) + τ (R 1 ) ≥ M Int(R 1 , R 3 ). Thus Ext(F 1 ) > M Int(R 1 , R 3
), the region R 1 and R 3 will not be merged and Int(R 1 ) + τ (R 1 ) will not increase. This property shows that R 1 will never be merged during the algorithm. So M Int(R 1 , R 2 ) does not increase and each face

F p , p ∈ [2..k], Ext(F p ) > M Int(R 1 , R 2 )
. The region R 1 and R 2 will never merge.

⊓ ⊔ Thus Prop. 1 is verified. Algorithm 1 gives the same result as the one proposed in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF].

Results and Analysis

Let us talk about the complexity of the segmentation. Let be |F | the number of faces of the topological map and |D| the number of darts of the topological map. We know that |D| > |F | since there is at least one dart for each face of the map.

The initialization of the list of faces needs to run through all the darts. The marking operation as well as the checking of a mark are constant time operations. We perform |F | insertions in the list and then we sort it which leads to a complexity for this operation in O(|D| + |F | * log(|F |)). The union and find operations on disjoint-set are quasi-linear according to [START_REF] Tarjan | Efficiency of a good but not linear set union algorithm[END_REF] and thus we consider it linear for our usage.

Then each face is considered in a loop executed |F | times. The extraction of the list is a constant time operation as well as the retrieval of the belonging region of a dart and the β 3 operation. With the previous hypothesis on union-find trees, checking if the two regions are not merged is a constant time operation. The computation of the equation is also a constant time operation because we store the needed values on regions and faces. The access to these values is a constant time operation. The symbolic merging corresponds to the union operation on disjoint-sets and thus we consider it constant. So this part is performed in O(|F |).

The last step of this algorithm is the application of the global merging operation on the topological map. We use the complexity given in Sect. We have written an application which allows to segment an image in the 3D topological map framework. We have measured several values during the segmentation of three images (which are medical brain images). In order to decrease the memory needed by the representation of the image, we pre-segment the image during the extraction of its topological map. Table 1 shows the initial and final number of regions for each of the 3 images so as it gives an idea of the effectiveness of the segmentation process. We have also collected the processing time of the three steps of the segmentation. The fastest step is the symbolic merging since it only manipulates regions by using union-find trees and the sorted list of faces. The list initialization is a slow step as it depends on the topological map size. The slowest part is, as expected, the region merging operation since it heavily depends on the number of darts in the topological map. The total processing time is nevertheless suitable for a use of the algorithm in the image analysis framework.

We present a segmentation result obtained on Img1. Figure 3 shows one slice of the medical image on left side. The image on the right represents the labeled view of the slice after the segmentation process. This view allows to identify all the resulting regions of the image since they have different colors. We could observe that most of the brain is represented by only one region whereas the skull is composed of many regions. The segmentation needs to be tuned in order to produce more accurate results depending on the problem. For example, a low segmentation threshold leads to an over-segmentation which could be used in an image processing chain as the initial input.

Conclusion

In this paper, we have presented the implementation of an existing bottomup segmentation process in the 3D topological map. This work shows that the topological map is a suitable data structure to represent 3D images within the image processing framework.

We have detailed the homogeneity criterion used in the segmentation operation. It relies on intensity differences between neighboring voxels of the image. The aim of the segmentation process is to provide a set of homogeneous regions according to the criterion such as the merge of two regions produces another region which is not homogeneous.

The segmentation algorithm is divided in two main parts. Firstly we aim to produce a symbolic segmentation of the image, by handling its regions on a high level, and computing the criterion step by step during the merging process. Secondly, we use the existing operation of region merging in order to reflect the symbolic changes in the topological map.

We then proved that the modifications made to the initial segmentation algorithm do not modify its initial properties. We have analyzed the complexity of the whole segmentation process. We have made some experiments on the segmentation process. Obtained processing times prove that the most expensive part of the algorithm is the region merging one and show that 3D topological maps can be used in real image processing applications.

The following step is to improve the segmentation process by taking advantage of the topological and geometrical information stored by the 3D topological map. We intend to use these information in addition with the existing criterion to obtain results that not only depend on the homogeneous criterion but also take into account the shape of regions as well as the adjacency relations between regions. For example one topological criterion may disallow the creation of dou-ble torus region if no such object could exist in the image. This future work will show the advantage of using the topological map for 3D image segmentation.

Fig. 1 .

 1 Fig. 1. The successive decompositions of an object to obtain the corresponding 3-map. (A) A 3D object. (B) Disjointed volumes. (C) Disjointed faces. (D) Disjointed edges. (E) Corresponding combinatorial map.

Fig. 2 .

 2 Fig. 2. The different parts of the topological map used to represent an image. (A) 3D image. (B) Minimal combinatorial map. (C) Intervoxel matrix (embedding). (D) Inclusion tree of regions.

  2.3 which is O(|D| + |S|) where |S| is the number of surfels of deleted faces. This gives the complexity for the whole segmentation algorithm to O(|D| + |F | * log(|F |) + |S|). The operation depends on the number of darts of the whole topological map, the number of faces of the topological map and the number of surfels belonging to deleted faces.

Fig. 3 .

 3 Fig. 3. A slice of a 3D brain image (256 x 256 x 44 gray image) and the segmentation result produced by the algorithm on the same slice (k = 5000, p = 3).

  It depends on the number of darts |D|, the number of faces |F | and the number of surfels |S| of the topological map. The complexity is given by the relation O(|D| + |F | * log(|F |) + |S|).

  0

	00 00 00 00 11 11 11 11 00 00 00 00 11 11 11 11 0 0 0 1 1 1 00 00 00 00 11 11 11 11 000 000 000 000 000 000 000 000 000 000 000 000 000 111 111 111 111 00 00 00 00 00 11 11 11 11 11 111 111 111 111 111 111 111 111 111 00 00 00 11 11 11

Table 1 .

 1 Image information and processing time for the three steps of the segmentation algorithm (segmentation threshold k = 5000 and pre-segmentation p = 3).

	Image	Img1	Img2	Img3
	Size	256x256x44 256x256x111 256x256x124
	Initial Regions	147924	431486	310421
	Remaining Regions	10121	30179	22523
	List initialization	2.93s	8.72s	6.25s
	Symbolic merge	0.46s	1.30s	0.97s
	Global merge	5.50s	14.99s	11.69s
	Total	8.89s	25.10s	18.92s

A permutation on a set S is a one to one mapping from S onto S.

An involution f on a set S is a one to one mapping from S onto S such that f = f -1 .

β1 • β3 is the composition of both permutations: (β1 • β3)(x) = β1(β3(x)).

according to P. F. Felzenszwalb and D. P. Huttenlocher in[START_REF] Felzenszwalb | Image segmentation using local variation[END_REF].

Partially supported by the ANR program ANR-06-MDCA-008-05/FOGRIMMI.

Apply the global operation of region merging;

of the current dart d does not belong to the same disjoint-set as the belonging region of the dart β 3 (d) (i.e. the dart which belongs to the second region incident to the face). Then we compute the M Int value for the two incident regions and if this value is lesser or equal to the external variation of the current face, we symbolically merge the two regions. When all faces have been processed, the segmentation algorithm uses the merging operation to produce the topological map corresponding to the resulting regions.

The main difference between this algorithm and the graph-based process described in [START_REF] Felzenszwalb | Image segmentation using local variation[END_REF] is the usage of the external variation onto each face instead of the external variation between couple of regions. This modification is necessary since the topological map represents multi-adjacency while RAG only represents simple adjacency. We have to prove that both approaches are equivalent.

Property 1 ensures that two regions are merged if and only if they respect the original criterion equation. This property says that two regions R i and R j may be merged together if and only if they merge during the process of the first face which is incident to both regions in the increasing order of their external variation (this is due to the fact that the external variation of this first face is equal to the external variation between the two regions).

Property 1 (Validity).

If two regions R i and R j are not merged when the algorithm process the first separating face, then they will never merge during the algorithm.

Proof. We consider two regions R 1 and R 2 in the topological map that are multiadjacent. Let be F p , p ∈ [1..k], the different faces incident to both R 1 and R 2 . We suppose that Ext(F 1 ) ≤ Ext(F 2 ) ≤ . . . ≤ Ext(F k ). We know that the external variation of the two regions is equal to the external variation of the face F 1 .

Algorithm 1 processes the faces in increasing external variation order. The first face considered to merge R 1 and R 2 is thus F 1 .

Suppose Ext(F 1 ) > M Int(R 1 , R 2 ) then the two regions R 1 and R 2 are not merged according to the criterion. Given this hypothesis, we want to know if it


Jonas Vanardois

Pierre Trap

Francoise Roger

Fabrice Barou

Pierre Lanari

Didier Marquer

Jean-Louis Paquette

Jérémie Melleton

Kévin Fréville

Françoise Roger

New deformation, metamorphic and geochronological data on the Aiguilles-Rouges massif (Alpine External Crystallin massifs, France). A reappraisal of the Variscan tectono-metamorphic evolution in the Alpine Western External Crystallin massifs

published or not. The documents may come   L'archive ouverte pluridisciplinaire

The Aiguilles-Rouge Massif (ARM) is one of the Western External Crystallin Massifs (ECM) of the French Alps. Similarly to the other ECMs, the ARM exposes a Variscan basement made of migmatitic ortho-and paragneisses and micaschists that hold metric boudins of retrograded eclogites, amphibolites and serpentinites. Upward, low-grade and weakly metamorphosed Late-Carboniferous terrigenous sediments overly the Variscan basement. Deformation and metamorphism occurred between 330 and 300 Ma. The whole ARM is structured by a main N-S to NE-SW trending and vertical foliation formed in response to a regional dextral transpression. The tectonic significance of the ARM's high-pressure rocks in the Variscan belt realm as relics of a subduction zone, pieces of crustal root of an orogenic plateau or overpressure phenomenon along a high-strain zone is still highly debated. A question that also remains is how eclogite Pressure-Temperature-time-Deformation history (P-T-t-D path) relates to the metamorphic paths recorded in the surrounding migmatitic rocks. In this contribution we present new structural and microstructural (EBSD data) observations that give us a detailed vision of the partitioning of the crustal scale deformation during Late-Variscan time. Three main deformations, named D1, D2 and D3, have been recognized in the gneissic core of the ARM. D1 is relictual and corresponds to a flatlying S1 foliation that is only visible in the high grade metasedimentary rocks and preserved in low-D2 strain domains. D1 is associated with a partial melting metamorphic event M1. D2 is characterized by three main orientations of planar fabrics that are oriented in directions N160, N0 and N20. These planar fabrics are interpreted as S2-C2-C2' related to anastomosed system developed under a bulk dextral transpression. D2 shearing becomes more penetrative toward the NE, where it is associated to local partial melting. D3 corresponds to the development of a flatlying S3 cleavage together with the folding of vertical D2 foliations. The D3 is linked to a regional vertical shortening, associated to few liquid injections. These partial melting conditions occurring during D1, D2 and D3 deformations may unravel a continuum of these three deformations during a short period of time. Processing of new thermobarometric and LA-ICP-MS U-Pb geochronological data on eclogites, surrounding rocks and migmatites are currently in progress. The new obtained results will be presented in addition to the structural and metamorphic data in order to discuss the P-T-t-D path of the deeply buried metasedimentary rocks, migmatites and preserved eclogites.


Claire Silvani
email: silvani@lma.cnrs-mrs.fr

Stéphane Bonelli

Thierry Désoyer

Silvani Claire

Bonelli Stéphane

Desoyer Thierry

A discrete model for fracture of rigid solids based on a damaging interface

Keywords: Granular medium, rigid solids, interface, damage, fracture

We describe the progressive and delayed fracture of rigid solids by a discrete modelling. Each rigid solid is considered as an assembly of particles with initial cohesive bonds, the latter decreasing progressively during the loading. A damaging interface model is proposed to describe this progressive phenomenon. This model has been implemented in a numerical code based on a discrete element method. The illustrative example is related to the crushing of an assembly of rigid solids -i.e. a granular medium -due to an oedometric compression.

Résumé :

Nous décrivons la rupture progressive et différée de solides rigides par une approche discrète. Chaque solide rigide est représenté par une collection de particules, initialement liées par une cohésion qui peut progressivement diminuer au cours du chargement. Un modèle d'endommagement interfacial est proposé pour décrire cette décroissance progressive. Implémenté dans un code de calcul par éléments discrets, ce modèle permet de simuler la rupture de collections de solides rigides. L'exemple illustratif traite de la rupture et de l'attrition d'une collection de grains sous compression oedométrique.

Introduction

The general frame of this study is this of the progressive (finite cracking velocity) and delayed (with respect to the loading) fracture of rigid solids interacting by contact and friction. An illustrative example of such a structural problem is this of a rockfill dam, which can globally settle due to the local fracture of rock blocks in the time, see e. g. [START_REF] Deluzarche | Discrete numerical modelling of rockfill dams[END_REF], [START_REF] Oldecop | Fundamentals of rockfill time-dependent behaviour[END_REF] or Tran (2006).

C h o i c e i s h e r e m a d e t o g e t n u m e r i c a l l y a p p r o x i m a t e d s o l u t i o n s o f t h e c o n t a c t -f r i c t i o n p a r t o f t h e p r o b l e m b y u s i n g t h e d i s c r e t e e l e m e n t m e t h o d p r o p o s e d b y M . J e a n (1999) a n d J . J . M o r e a u ( 1988 ) . H o w e v e r , d u e t o t h e f a c t t h a t t h e r i g i d s o l i d s ( o r g r a i n s ) -w h i c h w i l l b e a l l a s s u m e d o f t h e s a m e c h a r a c t e r i s t i c s i z e D S -c a n b r e a k , e a c h o f t h e m i s c o n s i d e r e d a s a n a s s e m b l y o f r i g i d p a r t i c l e s -w h i c h w i l l b e a l s o a l l a s s u m e d o f t h e s a m e c h a r a c t e r i s t i c s i z e D p D S . T h e s e p a r t i c l e s a r e a s s u m e d t o b e i n i t i a l l y "g l u e d". F r o m a n u m e r i c a l p o i n t o f v i e w , a g r a i n , i . e . a n a s s e m b l y o f r i g i d p a r t i c l e s , m u s t t h u s b e s e e n a s a m e s h o f t h e r i g i d s o l i d , i n w h i c h a c r a c k c a n i n i t i a t e ( r e s p . p r o p a g a t e ) o n l y o n ( r e s p . t h r o u g h ) t h e c o n t a c t z o n e s b e t w e e n r i g i d g r a i n s . C o n s e q u e n t l y , f r o m a p h y s i c a l p o i n t o f v i e w , t h e s e c o n t a c t z o n e s h a v e t o b e c o n s i d e r e d a s r i g i d b u t b r e a k a b l e i n t e r f a c e s .

Strong cohesive forces are supposed to exist initially on the interfaces (see e. g. [START_REF] Delenne | Mechanical behaviour and failure of cohesive granular materials[END_REF]), giving to them their initial tensile strength. It is then assumed that, when a given interface I -characteristic area S (D p ) 2 in 3D and S D p in 2D -is submitted to a sufficiently strong tensile force, microcracks and/or microcavities, i.e. damage initiate, growth and, eventually, coalesce, that leads to the fracture of the interface (and so, to the irreversible vanishing of the cohesive forces).

Following this introduction, Section 2 is devoted to the presentation of the damaging interface model where, in agreement with the general frame of this study, the evolution of the damage is at the same times progressive and delayed. An illustrative examples is presented in Section 3, where the numerical results have been obtained using a numerical code in which the damaging interface model has been implemented. This example is related to the crushing of an assembly of two-dimensional rigid solids -i. e. a two-dimensional granular medium -due to an oedometric compression.

c r o c r a c k i n g a n d / o r m i c r o c a v i t a t i o n o f t h e c o n s t i t u t i v e m a t e r i a l o f I . It is assumed that 0 d 1 .
It is emphasized that, as soon as d = 1 , I is destroyed and the contact-friction interactions between the both grains have to be considered on the basis of the Signorini-Coulomb equations (see e.g. Moreau (1998)). These equations will not be detailed in the present paper.

The damaging interface model is actually based on previous work on continuum damage mechanics by Marigo (1981), where the necessary and sufficient condition for the intrinsic dissipation to be non negative is simply given by d 0 . We take to denote the stress tensor, taken here to be homogeneous in S . It is assumed that, due to the damage, the effective tough surface of I is not S but the undamaged part (1 d)S . The force vector acting on S is then F = S(1 d) N . We take F N = F N to denote the normal force (such that F N > 0 when I is submitted to a tensile force), F T = F F N N the tangential force, u N = u N the normal relative displacement and u T = u u N N the tangential relative velocity. A damage yield surface is introduced. Once more, it is clearly inspired by the works by Marigo (1981). However, for a sake of consistency between the present interfacial damage model and the Mohr-Coulomb Signorini one, which must merge in the latter one as soon as d = 1 , the damage yield surface is

g d (F T , F N ,d) = µ 1 F T + F N (1 d)F 0 .
where µ is the friction coefficient between grains when I is destroyed, and F 0 > 0 the undamaged yield. As for the fracture of I , which can occur suddenly when I is sufficiely damaged, it is controlled by a fracture yield surface, which reads:

3 g f (F T , F N ,d) = µ 1 F T + F N (1 d)F f .
where F f F 0 is the maximal tensile force I can undergo. It is emphasized that g d g f , whatever the reachable mechanical state is: damage takes place before fracture, apart from the limit case of a perfectly brittle interface ( F f = F 0 ), where damage and fracture are concomitant. We distinguish the history of the contacting bodies: the left status denotes the status before the current time, while the right status denotes the status before the current time.

The state laws are if the left status is cohesive (i.e. d < 1)

u N 0, F N (1 d)F f 0, F N (1 d)F f u N = 0 else u N 0, F N 0, F N u N = 0 .
The complementary laws include: -the evolution laws:

g f (F T , F N ,d) 0, 0, g f (F T , F N ,d) = 0 u T = F T F T , d = < g 0 (F T , F N ,d) > F 0
, where < . > denotes the MacCauley brackets, and is a characteristic time; -the status change rules:

the right status is the same as left status, except if the left status is cohesive (d < 1), and if the solution satisfies u 0 then the right status is set to "non-cohesive" (d = 1) . This description is inspired by the work of [START_REF] Jean | Non-smooth contact dynamics approach of cohesive materials[END_REF]. This is a non-smooth model: d may jump from its failure value given by g d (F T , F N ,d) = 0 to its maximum value. This rule does not allow the contacting bodies to be glued again, one the interface is destroyed. This damaging interface model has been implemented in a non-smooth contact dynamics code (LMGC90).

4

Each grain is an assembly of initially glued particles of a same diameter D p . From a numerical point of view, D p is the characteristic length of a mesh. As a consequence, F 0 and F f appear to be numerical parameters depending on D p : the smaller D p , the smaller F 0 and F f . We consider therefore as material parameters 0 = F 0 / (D p e) and u = F f / (D p e) (in the three-dimensionnal case, (D p ) 2 should be considered instead of (D p e) ). The dimensionless number r = F 0 / F f = 0 / u is a material parameter. A l l t h e s i m u l a t i o n s w e r e p e r f o r m e d w i t h µ = 1 .

T h e a x i a l s t r a i n i s d e f i n e d b y =|U | /L w h e r e U i s t h e g l o b a l d i s p l a c e m e n t i n d u c e d b y T ; t h e a x i a l s t r e s s i 4 shows that r influences the amplitude of the strain during the creep phase. The lower bound of the final amplitude corresponds to a perfectly brittle interface (r =1), while the upper bound corresponds to a damaging interface with no damage yield (r =0).

Fig. 5 shows the oedometric response of the sample during a constant stress rate. This sample behaves like most granular media: decreased compressibility along with increased load yields a convex stress/strain curve. However, this curve presents several breaks: they correspond mainly to the abrupt breakage of one or more grains. Stopping the loading and maintaining constant stress leads to a creep response, while maintaining constant strain leads to a stress relaxation.

Conclusions

Most of the structural failures are due to the pre-existence of various kinds of microdefects (microcracks and/or microvoids) in the materials, which propagate and eventually coalesce in a macro-crack. The modelling of these propagation and coalescence is an important issue. The discrete approach presented here is intended as a step toward this issue. The proposed damaging interface model is based on a reduced set of five parameters. The illustrative example clearly deals with dam engineering: rockfill material is characterized by delayed grain breakage under constant load. This is the main cause of the majority of post-constructive displacements observed in high rockfill dams, which can induce the failure of the impervious element or piping erosion.

2 A

 2 damaging interface modelling T h e ( t h e r m o ) d y n a m i c s y s t e m c o n s i d e r e d i n t h i s s e c t i o n i s a n i n t e r f a c e I b e t w e e n t w o g r a i n s . L i k e t h e g r a i n s , I i s a s s u m e d t o b e r i g i d : t h e a r e a o f t h e s u r f a c e S o c c u p i e d b y I i s t h e n c o n s t a n t , w h a t e v e r t h e f o r c e s a c t i n g o n a r e . F u r t h e r m o r e , t h e d i s p l a c e m e n t j u m p u t h r o u g h S i s a s s u m e d t o b e z e r o w h e n e v e r I i s n o t d e s t r o y e d ( i . e . w h e n e v e r S i s c l e a r l y d e f i n e d ) . A c t u a l l y , o n l y o n e evoluting s t a t e v a r i a b l e w i l l b e c o n s i d e r e d , d e n o t e d b y d ( s c a l a r ) a n d c h a r a c t e r i z i n g t h e d a m a g e b y m i

3

  Application to oedometric compression of a granular medium W e c o n s i d e r a n a s s e m b l y o f t w o -d i m e n s i o n n a l r i g i d s o l i d s ( g r a i n s ) -i . e . a t w o -d i m e n s i o n a l g r a n u l a r m e d i u m -s u b m i t t e d t o a c o m p r e s s i v e f o r c e | T | i n oed o m e t r i c c o n d i t i o n s ( i . e n o l a t e r a l d i s p l a c e m e n t s ) . I n t h e i n i t i a l s t a t e , s e e F i g . 1 , t h e s a m p l e ( i n i t i a l h e i g t h 45 cm, w i d t h L = 4 8 c m ) i s c o m p o s e d b y 7 5 g r a i n s ( d i a m e t e r s b e t w e e n 5 a n d 6 c m ) , e a c h o f t h e m b e i n g c o n s t i t u t e d b y 6 0 t o 7 0 p a r t i c l e s ( d i a m e t e r s D p b e t w e e n 5 a n d 6 m m ) . Th e n u m e r i c a l s i m u l a t i o n s i n v o l v e 4 9 8 0 p a r t i c l e s .

  s d e n o t e d b y =| T | /(eL) w h e r e e i s t h e ( u n i t ) t h i c k n e s s o f t h e s a m p l e . We take to denote t h e r a t i o b e t w e e n t h e current n u m b e r o f n o n -c o h e s i v e c o n t a c t s a n d t h e i n i t i a l n u m b e r o f c o h e s i v e c o n t a c t s . T h e l o a d i n g T i s first d e f i n e d by a Heaviside step , i n o r d e r t o h i g h l i g h t t h e c r e e p l i k e r e s p o n s e o f t h e g r a n u l a r m e d i u m . Figs. 2 and 3. show the influence of the characteristic time : this parameter simply delays the response (Fig. 2 left). The use of leads to an efficient dimensionless scaling in time (Fig. 2 right). Parameter slightly modifies the response quantitatively, as shown by the evolution of (Fig. 3 left). N o t i c e e v e n t u a l l y t h a t a n d e v o l v e s i n t h e s a m e w a y d u r i n g t h e c r e e p p h a s e : t h e k i n e t i c s i s m a i n l y g o v e r n e d b y t h e f r a c t u r e o f t h e i n t e r f a c e s (Fig. 3 right). For a given value of u , Fig.

FIG. 1 FIG. 2 -

 12 FIG. 1 -S a m p l e c o m p o s e d b y a n a s s e m b l y o f 7 5 n o n "g l u e d" g r a i n s ( i n i t i a l h e i g t h 45 cm, w i d t h 4 8 c m ) a n d s u b m i t t e d t o a n oed o m e t r i c l o a d i n g ; e a c h g r a i n s i s c o m p o s e d o f 6 5 p a r t i c l e s , i n i t i a l l y "g l u e d" .

Acknowledgement

This work was supported by the Région Provence Alpes Côte d'Azur. The authors wish to thank Frédéric Dubois for his valuable help with LMGC90.