Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

Florence Zara
email: florence.zara@liris.cnrs.fr

Merge-and-simplify Operation for Compact Combinatorial Pyramid Definition

Keywords: Hierarchical image representation, combinatorial pyramids, 2D combinatorial map

Merge-and-simplify operation for compact combinatorial pyramid definition

Introduction

Image analysis consists to extract meaningful information from images. An efficient approach is inspired by the psychovisual properties of focus of attention. It analyzes the content of images at different scales/levels of details. This approach requires a relevant data structure to store the different levels of information. In this context, image pyramids are used for years in digital image processing [START_REF] Meer | Stochastic image pyramids[END_REF]; [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF]; [START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF]; [START_REF] Jolion | The adaptive pyramid: A framework for 2d image analysis[END_REF]).

The first pyramids were defined as sequences of images with decreasing resolutions. Each new level of a pyramid was computed using a same regular grouping pattern. These pyramids are called regular. But the segmentation process turned out more efficient using different adaptive grouping [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF]). The irregular pyramid was thus defined, where each level is a partition of the image pixels in regions. Such a pyramid requires a topological representation to describe the partitions, and basic operations to build the data structure. [START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF] proposed to code the sequence of partitions as a sequence of successive reduced graphs. Each vertex of a graph corresponds to a region, and an edge in the graph exists between two vertices when the two corresponding regions are adjacent in the image. In [START_REF] Kropatsch | Building irregular pyramids by dualgraph contraction[END_REF]; [START_REF] Kropatsch | Finding the structure of connected components using dual irregular pyramids[END_REF], dual graphs were defined: two graphs are stored, a graph and its dual.

Later on, specific data structures have been proposed to obtain a topological representation of the space. A 2D combinatorial map is a mathematical model of the representation of space subdivision. It is based on planar map [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF]; [START_REF] Tutte | A census of planar maps[END_REF]; [START_REF] Jacques | Constellations et graphes topologiques[END_REF]). Combinatorial maps have many advantages justifying their use: they are fully ordered; they enable the representation of multi-incidence relations; they allow us many topological operations; they allow us local modifications; they are independent of the geometry, i.e. they can represent curved objects as well as linear objects.

For these reasons, 2D combinatorial maps, or some variants, were used as basic data-structure in several image processing methods [START_REF] Braquelaire | Image segmentation with topological maps and inter-pixel representation[END_REF]; [START_REF] Fiorio | A topologically consistent representation for image analysis: the frontiers topological graph[END_REF]; [START_REF] Kthe | Xpmaps and topological segmentation -a unified approach to finite topologies in the plane[END_REF]; [START_REF] Dufourd | Design and formal proof of a new optimal image segmentation program with hypermaps[END_REF]. They were also used to define irregular pyramids for image processing, called combinatorial pyramids (Brun andKropatsch (2000, 2003b,a,c); [START_REF] Simon | Receptive fields for generalized map pyramids: The notion of generalized orbit[END_REF]Simon et al. ( , 2006)); Simon and Damiand (2006); [START_REF] Fourey | A first step toward combinatorial pyramids in n-D spaces[END_REF]). A combinatorial pyramid is a sequence of progressively reduced 2D combinatorial maps, plus some links between consecutive levels. To represent such a pyramid, an explicit representation stores each level as a distinct combinatorial map. The main advantage is to provide a direct access to each level of the pyramid. Its main drawback is to have an high complexity in memory space.

In this paper, our main contribution is the definition of a compact combinatorial pyramid that requires less memory space than previous explicit representations. Our solution is based on the definition of a new operation called merge-and-simplify, which is our second main contribution. This operation allows us to simultaneously merge some regions in a given combinatorial map, and simplify the region boundaries, which was not possible with original removal operations.

The outline of this paper is the following. Section 2 introduces all the basic notions used in this paper. In Section 3, we define our new operation and we show the links with the original operations. Then, this new operation is used in Section 4 to define our new compact combinatorial pyramid. The experiments presented in Section 5 show the interest of our solution: we both decrease the memory space and the computation time of the pyramid used for the image segmentation. In Section 6, we conclude and give some future work.

Preliminary notions

Some preliminary notions are introduced about combinatorial maps, operations on these maps, and combinatorial pyramids. In our mathematical notation, capital letters are used for sets, and lower case letters otherwise. For a mapping f from X to Y, the notation

f (E) = { f (e)|e ∈ E} is used, with E ⊆ X. f is a permutation if X = Y; f is an involution if X = Y and ∀e ∈ X, f ( f (e)) = e.

2-maps and their topological operations

The subdivision of a 2D topological space is a partition of the space into 3 subsets whose elements are cells of 0, 1 and 2 dimension (respectively called vertices, edges and faces). Border relations are defined between these cells, where the border of an i-cell is a set of (j<i)-cells. Two cells are incident when one belongs to the border of the second, and two i-cells are adjacent if they are both incident to the same (i-1)-cell. 2D combinatorial maps. A combinatorial map encodes a space subdivision and all the incidence relations between the different cells of the space. Consequently, it represents the topology of this space. It is based on a unique basic type of element, called dart, together with relations between these darts. A 2D combinatorial map (called 2-map) is a set of darts, which can be seen as half-edges, plus two mappings defined on these darts (cf. Def. 1) [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]; [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]). In this paper, 2-map is used without boundary. So, each edge is always described by 2 darts, and there is a specific unbounded face describing the external part of the object.

Definition 1 (2-map). A 2-dimensional combinatorial map is a triplet M = (D, β 1 , β 2 ) where: (1) D is a finite set of darts;

(2) β 1 is a permutation on D; (2) β 2 is an involution on D.

For a dart d, β 1 is the next dart after d in the same face than d.

β 0 = β -1
1 is the inverse relation: this is the dart before d in the same face. For a dart d, β 2 is the other dart of the same edge. Note that this definition of 2-map was extended to be able to represent objects with boundaries, and objects in higher dimension [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]).

A 2-map is equivalent to the half-edge data structure [START_REF] Weiler | Edge-based data structures for solid modelling in curved-surface environments[END_REF]; [START_REF] Mäntylä | An Introduction to Solid Modeling[END_REF]) or the DCEL data structure [START_REF] De Berg | Computational Geometry: Algorithms and Applications[END_REF]) -DCEL for Doubly Connected Edge List), where half-edges are equivalent to darts. Moreover, others equivalent solutions exist, for example the corner table data structure [START_REF] Rossignac | 3D compression made simple: Edgebreaker with zipandwrap on a corner-table[END_REF], where corners are equivalent to half-edges. The difference between these solutions are the naming of the elements (darts, half-edges, corners); the mappings represented (permutation around vertices or around faces); the way these mappings are stored (pointers or indices). We use the notation with darts and β (rather than α, σ and ϕ notations also used by many authors when dealing with planar maps) as it is the notation both used in the reference book about combinatorial maps [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]) and in the Combinatorial maps package [START_REF] Damiand | Combinatorial maps[END_REF]) in CGAL which is the main C++ library of computational geometry.

i-cells. Thanks to the darts and the β links, a 2-map describes the subdivision of a 2D object in cells. All the cells of the object are represented by some specific subset of darts. An edge is the set of two darts linked by β 2 ; a face is the set of all darts obtained by using β 1 , until going back to the original dart; a vertex is the set of all darts obtained by using β 1 • β 2 , until going back to the original dart. Two cells C 1 and C 2 are incident if C 1 ∩ C 2 ∅, or in other words, if the two cells share at least a common dart. Two i-cells C 3 and C 4 are adjacent if ∃C 5 , an (i -1)-cell, incident both to C 3 and C 4 .

Example. Fig. 1a gives an example of 2-map. It has 22 darts (drawn by oriented segments), 15 darts (numbered). Two darts linked by β 1 are drawn consecutively (for example β 1 (1) = 2), and two darts linked by β 2 are drawn in parallel, with reverse orientations, with a small gray segment over the two darts (for example β 2 (1) = 5). This 2-map has 9 vertices (for example vertex C 0 (2) = {2, 5, 15}, the set of all darts having this vertex as origin), 11 edges (for example edge C 1 (1) = {1, 5}) and 4 faces (for example face C 2 (1) = {1, 2, 3, 4}). C 0 (2) and C 1 (1) are incident because C 0 (2)∩C 1 (1) = {5} ∅. C 2 (1) and C 2 (5) = {5, 6, 7, 8} are adjacent because C 1 (1) is incident to both 2-cells. Dual of a 2-map. Given a 2-map M = (D, β 1 , β 2 ), its dual is the 2-map M = (D, β 1 • β 2 , β 2 ). Vertices of M are faces in M (and reciprocally); while edges stay unchanged in M and M.

Removal operations. We remind that cells are sets of darts in 2-maps. This is one interesting specificity of 2-maps. Thus, to define an operation that modifies a 2-map, only darts and β links have to be modified and the cells are automatically updated thanks to their definition. It is possible to simplify a 2-map by removing some of its edges or some of its vertices. When an i-cell C is removed, this merges the two (i + 1)-cells incident to C in one (i + 1)-cell. The edge removal operation is given in Def. 2.

Definition 2 (1-cell removal). Let M = (D, β 1 , β 2 ) be a 2-map and E be one of its edge1 . Let D N = β 0 (E) \ E. The 2-map resulting from the 1-removal of E in M is R 1 (M, E) = (D , β 1 , β 2 ), defined by:

• D = D \ E; • ∀d ∈ D , β 2 (d) = β 2 (d); • ∀d ∈ D \ D N , β 1 (d) = β 1 (d); • ∀d ∈ D N , β 1 (d) = (β 1 • β 2 ) k • β 1 (d), k is the smaller positive integer s.t. (β 1 • β 2 ) k • β 1 (d) E.
The main principle of this definition is to remove the 2 darts of the removed edge E, and to redefine the β 1 links of darts neighbors of E by β 0 . It is performed by jumping over E and turning around its extremity, until obtaining a non removed dart.

Vertex removal operation is based on a same principle. But contrary to edges, it is not possible to remove any vertex. Indeed, it must have at most two edges incident to the vertex, otherwise it is not possible to decide which edges to merge after the removal. Such a vertex is called removable.

For a removable vertex, the removal operation is given in Def. 3. In this definition, both β 1 and β 2 links of darts neighbors of the removed vertex have to be redefined.

Definition 3 (0-cell removal). Let M = (D, β 1 , β 2 ) be a 2-map and V be one of its removable vertex 2 . The 2-map resulting from the 0-removal of V in M is R 0 (M, V) = (D , β 1 , β 2 )
, defined by:

• D = D \ V; • ∀ j ∈ {1, 2}, ∀d ∈ D : -if d β -1 j (V) \ V, β j (d) = β j (d); -otherwise, β j (d) = β j • (β 1 ) k (d),
k is the smaller positive integer s.t.

β j • (β 1 ) k (d) V.
Fig. 1 illustrates these operations. Starting from the 2-map given in Fig. 1a, edge {1, 5} (red darts) and vertex {10, 13} (green darts) have been removed. The 2-map depicted in Fig. 1b was obtained, where β 1 of darts 4, 8, 9 and 12 were modified (blue darts), as well as β 2 of darts 9 and 12. These β 2 links must be updated because darts 10 and 13 were removed by the vertex removal operation, and these darts were linked respectively with darts 9 and 12 by β 2 links in the original map.

Removal operations are extended directly to set of cells: it is possible to remove simultaneously any set of removable vertices and edges, when the set of darts of these cells are disjointed. It is also possible to simplify a 2-map by using the contraction operation, which is the dual of the removal operation. We do not use this operation in this work (Brun andKropatsch (1999, 2003b); [START_REF] Damiand | Combinatorial maps[END_REF]Lienhardt (2003, 2014)).

Reducible vertices. If a vertex incident to only one edge (a loop, separating two faces) is removed, this also removes totally the edge and the 2 faces. To avoid such a removal, a property on the vertex to remove can be added: it must be 0-removable and incident to exactly two different edges. Such a vertex is called 0-reducible.

2 By definition of vertices in 2-maps, V is a set of darts.

Combinatorial pyramids

A combinatorial pyramid is a sequence of 2D combinatorial maps (M 0 , . . . , M l ) where the 2-map M i is called level i of the pyramid; level 0 is called the basis; level l the top; l is the height of the pyramid. Each map (except the basis) is a simplification of the 2-map in the previous level (Brun andKropatsch (2000, 2003a,c); Simon et al. (2006)). According to the application and the semantic associated with the 2-maps, it is possible to define each level M i in different ways, but the computation of a new level is usually done by using only one type of operation (removal or contraction of only one type of cells). Usually, the basis describes all pixels, then one level corresponds to the merging of some regions, and a second level corresponds to the simplification of the region boundaries.

For example in Brun and Kropatsch (2003a), the vertices of the basis of the pyramid correspond to the pixels of the image. Then, merging two adjacent regions is achieved by contracting the corresponding edge; and simplify the region boundaries is done by removing edges with some specific properties (double edges and empty-self loops).

Dual representation is used in Simon and Damiand (2006). Pixels of the image are represented by faces in the basis of the pyramid. Then, regions are merged by removing edges; and simplify the region boundaries is done by removing vertices.

When a new level is added in a pyramid, the 2-map has to be ever connected in order to have a correct definition of cells. Indeed, imagine a 2-map made of two squares, one inside the other. This 2-map has two connected components. The geometrical object represented is a square with an hole: that is, an object with three faces (the square, the hole and the unbounded face). But the 2-map has 4 faces, two for each square, which is not correct. Adding an edge between the two squares keep the 2-map connected and give us the correct number of faces.

When a set of edges E in a 2-map M is removed, the map stays connected if E is a forest3 in the dual 2-map M (Brun and Kropatsch (2003b)). For a combinatorial pyramid where each level is connected, it is possible to retrieve all the i-cells in a level i that are merged in a given i-cell in a level j > i (cf. Brun and Kropatsch (2003c); [START_REF] Simon | Receptive fields for generalized map pyramids: The notion of generalized orbit[END_REF]).

Encoding combinatorial pyramids. Several possibilities exist to encode more or less explicitly a combinatorial pyramid according to the expected space/time complexity (Simon et al. (2006)). In an explicit representation, each level of the pyramid is represented in a distinct 2-map; each dart stores 2 additional pointers to the corresponding darts in the previous and the next levels. In an implicit representation, only the basis of the pyramid is represented as a 2-map and additional information allows us to retrieve removed and contracted cells for each level.

Each representation has its own advantages and drawbacks. The implicit representation is the best one in term of space complexity. But it is the worst representation for time complexity since the traversal of any level needs to iterate through darts of the basis of the pyramid, jumping over all the darts removed/contracted. The explicit representation is the one which requires the most memory space since each level is represented plus the links between the level. But this is the best representation for operations since it provides a direct access to each level, and operations can be applied directly to each level without any dependencies with other levels.

In our work, an explicit representation is used, since our application needs fast access to each level of the pyramid. In this framework, our main contribution is the definition of a new operation, called merge-and-simplify, which allows us to decrease the height of a combinatorial pyramid by avoiding the need to use different levels for merging the regions and for simplifying the region boundaries.

2-maps versus graphs

Many image processing papers that consider hierarchical partitions use trees or graphs to describe the hierarchy (cf. for example [START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF]; [START_REF] Jolion | The adaptive pyramid: A framework for 2d image analysis[END_REF]; [START_REF] Kropatsch | Building irregular pyramids by dualgraph contraction[END_REF]; [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF]; [START_REF] Cousty | Hierarchical segmentations with graphs: Quasi-flat zones, minimum spanning trees, and saliency maps[END_REF]). But a graph is not able to describe multiple adjacencies; it does not keep the order of the edges around a vertex; it does not represent the faces but only vertices and edges; and it is not unique two different images could be represented by the same graph. Some solutions were proposed to solve some of these drawbacks, like dual-graphs [START_REF] Kropatsch | Finding the structure of connected components using dual irregular pyramids[END_REF]). But they are not topological representative of the images as it is possible to have two topological different images with the same dual graphs. Moreover, to maintain the correspondence between the 2 graphs, each operation performed has to be applied twice: once to the primal graph and another to the dual one.

Contrary to solutions based on graphs, a 2D combinatorial map is a mathematical model of the representation of space subdivision [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]): it allows us to fully define the topology of a planar partition by describing all the cells and all the incidence and adjacency relations between the cells, allowing multiple adjacencies relations. Moreover, several operations exist on 2-maps allowing to iterate through the elements of a 2-map, or to modify the subdivision. All of these reasons make 2-maps an efficient model to build, to represent and to update an image partition in regions, as shown by numerous work based on this model (for example [START_REF] Braquelaire | Image segmentation with topological maps and inter-pixel representation[END_REF]; [START_REF] Fiorio | A topologically consistent representation for image analysis: the frontiers topological graph[END_REF]; [START_REF] Kthe | Xpmaps and topological segmentation -a unified approach to finite topologies in the plane[END_REF]; [START_REF] Dufourd | Design and formal proof of a new optimal image segmentation program with hypermaps[END_REF]; Brun andKropatsch (2000, 2003b,a,c); [START_REF] Simon | Receptive fields for generalized map pyramids: The notion of generalized orbit[END_REF]Simon et al. ( , 2006)); Simon and Damiand (2006); [START_REF] Fourey | A first step toward combinatorial pyramids in n-D spaces[END_REF]).

The choice of one (hierarchical) data structure to describe partitions depends on the applications. If you only need to deal with regions and some criteria (like size, shape, color, etc.), a list of regions with attributes is enough. If one algorithm requires to access to regions adjacent to a given one, and needs to update these adjacency relations, a region adjacency graph will probably be a good choice. Whereas, if you need to describe the full topology of the partition, with several operations to update your model providing topological control on the modifications, 2-maps is probably the best suitable data-structure.

Our merge-and-simplify operation

In this section, a new operation on 2-maps called merge-andsimplify is defined.

Original operation

When faces are merged in a 2-map, for example during an image segmentation process based on region growing, edges separating faces to merge must be 1-removed. As seen in the previous section, the disconnection of the 2-map in several connected components can be avoided by imposing that the set of removed edges is a forest in the dual 2-map. This is a sufficient condition but not a required one. Indeed, when two regions to merge are adjacent along at least two consecutive edges, only one out of the two edges will be removed. Effectively, adding the two edges in the set of removed edges will create a cycle in the dual 2-map. Due to this condition, there are many edges inside faces resulting of the merging that must be removed since they do not describe any region boundary, as illustrated in Fig. 2b. This can be achieved by iteratively removing all the dangling edges (Simon and Damiand (2006)). At the end, the 2-map obtained in Fig. 2c contains no more dangling edges: each edge either belongs to the boundary of a face, or is a bridge necessary to keep the 2-map connected. But now this map contains too many vertices that must be removed. This is the last step of the simplification which consists to remove iteratively each 0-reducible vertex. The 2-map shown in Fig. 2d is obtained which can no more be simplified.

New operation: merge-and-simplify

Our idea is to define a new operation, called merged-andsimplify, which applies directly both the region merging and the two simplification steps (of dangling edges and of 0-reducible vertices). This new operation (given in Def. 4) takes as input a 2-map plus a set of edges. The dangling edges and the 0reducible vertices to remove are automatically computed by it. Definition 4 (Merge-and-simplify). Let M = (D, β 1 , β 2 ) be a 2-map and K 1 be a set of darts, union of edges 4 of M. Let us define:

• K 1 = K 1 ∪ E 0 . . . ∪ E e ,
where each E i is a dangling edge in R 1 (M, K 1 ∪ E 0 . . . ∪ E i-1 ); and there is no dangling edge in R 1 (M, K 1 ∪ E 0 . . . ∪ E e );

• K 0 = V 0 ∪ . . . ∪ V v , where each V i is a 0-reducible vertex in R 0 (R 1 (M, K 1 ), V 0 ∪ . . . ∪ V i-1 ); and there is no 0-reducible vertex in R 0 (R 1 (M, K 1 ), V 0 ∪ . . . ∪ V v ); • N 1 = β 0 (K 0 ∪ K 1 ) \ (K 0 ∪ K 1 ); • N 2 = β 2 (K 0 ) \ (K 0 ∪ K 1 ).
The 2-map resulting from the merge-and-simplify of M by K 1 is MS (M, K 1 ) = (D , β 1 , β 2 ), defined by:

• D = D \ (K 0 ∪ K 1 ); • ∀d ∈ D \ N 1 , β 1 (d) = β 1 (d); • ∀d ∈ N 1 , β 1 (d) = d = ( f k • . . . • f 0 • β 1 )(d),
where

f i = β 1 if ( f i-1 • . . . • f 0 • β 1 )(d) ∈ K 0 , or f i = β 1 • β 2 if ( f i-1 • . . . • f 0 • β 1 )(d) ∈ K 1 ,
and k being the smaller positive integer s.t. d ∈ D ;

• ∀d ∈ D \ N 2 , β 2 (d) = β 2 (d); • ∀d ∈ N 2 , β 2 (d) = β 2 • β 0 • β 1 (d).
The first part of the definition adds in K 1 all the dangling edges. Note that edge E i is dangling in R 1 (M, K 1 ∪E 0 . . .∪E i-1 ), i.e. in the 2-map obtained by removing all edges in K 1 plus all dangling edges E 0 , . . . , E i-1 . Such a definition is required because edge E i is possibly not dangling in the map obtained by removing all edges in K 1 , but can become dangling after the removal of some dangling edges.

In the second part, K 0 is defined as the set of all the 0reducible vertices. Similarly than for K 1 , vertex V i is added if it is 0-reducible in the 2-map where all the edges in K 1 are removed and all the previous 0-reducible vertices are removed.

N 1 is the set of non removed darts, neighbors by β 0 of one removed vertex or removed edge. These darts will have their β 1 4 By definition of edges in 2-maps, each edge is a set of darts.

modified by the operation. N 2 is the set of non removed darts neighbors of one remove vertex by β 2 , having their β 2 modified.

Then, similarly than the removal operation, the merge-andsimplify operation defines a new 2-map (D , β 1 , β 2 ) which redefines β 1 and/or β 2 for darts concerned by the operation. The difference is the paths followed for these redefinitions. Contrary to the original operation, a removed vertex can now be traversed starting from a neighbor dart of a removed edge. For this reason, there are 2 cases in the path traversal, depending if the last dart belongs to a 0-removed or a 1-removed cell. In each case, the definition of the original operation is used to follow correctly the path of removed darts: using either β 1 to jump over removed vertices, or β 1 • β 2 to turn over removed edges.

Comparison between original and new operations

Let us compare the new merge-and-simplify operation with the original one, which starts first to remove edges, then to remove vertices. In the example given in Fig. 3, we start from an initial 2-map (Fig. 3a) where an edge is marked to remove, by an external process (for example an image segmentation criterion). After the removal of this edge, the 2-map shown in Fig. 3b is obtained which contains one dangling edge and which is removed. The resulting 2-map (Fig. 3c) contains now two 0reducible vertices which are marked to remove. Fig. 3d shows the final result obtained after all the simplifications. To store these different steps into an explicit pyramid, 4 different levels are needed, 42 darts in total, and 11 β links are redefined. Let us reconsider the same example but using now the new merge-and-simplify operation. As shown in Fig. 4, the starting configuration is the same: an initial 2-map with only one edge marked to remove. But contrary to the previous simplification, dangling edge and 0-reducible vertices are directly marked to remove in the initial 2-map (Fig. 4a). After applying the mergeand-simplify operation,the simplified 2-map given in Fig. 4b is directly obtained in one step.

In this example, let us consider the path of darts traversed for the definition of β 1 (5). 5 ∈ N 1 (this is a neighbor dart of a removed edge). 5), the definition of β 1 (5) is reused (in order to avoid to redefine the path in Def. 4), go backward by β 0 to retrieve the last dart of the path in the same edge, then use β 2 . For dart 5, β 1 (5) = 9, β 0 (9) = 8 and β 2 (8) = 2: β 2 (5) = 2 is defined (and reciprocally).

f 0 = β 1 • β 2 because β 1 (5) ∈ K 1 ; f 1 = β 1 because 8 = β 1 • β 2 • β 1 ∈ K 1 , and k = 1 because 9 = β 1 • β 1 • β 2 • β 1 ∈ D . Thus β 1 (5) = 9 is defined. To define β 2 (
Thanks to this new operation, this simplification can be stored into an explicit pyramid which only has 2 different levels with 20 darts in total, and 8 β links (versus 4 levels, 42 darts and 11 β for the original version) are redefined.

Given a dart d ∈ N 1 , it is straightforward to prove that ∀i,

0 ≤ i < k, ( f i • . . . • f 0 • β 1 )(d) ∈ (K 0 ∪ K 1 ). Indeed, if we suppose ∃i, 0 ≤ i < k, d i = ( f i • . . . • f 0 • β 1 )(d) (K 0 ∪ K 1 ), then d i ∈ D = \(K 0 ∪K 1 )
, which contradicts k being the smaller positive integer s.t. d ∈ D . In other words, all darts traversed during the definition of β are removed by the operation, except the first and the last one.

Link with sequence of removal operations

Let M = (D, β 1 , β 2 ) be a 2-map and K 1 be a set of edges of M. We can prove that

M = MS (M, K 1 ) = (D , β 1 , β 2 ) is isomorphic to M = R 0 (R 1 (R 1 (M, K 1 ), E), V), with E = E 0 ∪ . . .∪ E e ,
where each E i is a dangling edge in R 1 (M, K 1 ∪ E 0 . . .∪ E i-1 ); and there is no dangling edge in R 1 (M, K 1 ∪ E 0 . . . ∪ E e ); and

V = V 0 ∪ . . . ∪ V v , where each V i is a 0-reducible vertex in R 0 (R 1 (M, K 1 ), V 0 ∪ . . . ∪ V i-1 ).
In other words, the same result is obtained by using the merge-and-simplify operation than using the sequence of 3 operations: (1) edge removal of edges in K 1 ; (2) edge removal of all dangling edges; (3) vertex removal of all 0-reducible vertices. This property ensures us the validity of our new operation. The principle of the proof of equivalence is the following. Starting from the definition of removal operations, which redefine β links, these definitions can be re-written by considering all the different cases of darts, depending if they belong to a vertex or an edge removed. At the end, the redefinition done when using the new operation is the same that the one obtained by applying successively the three simplifications.

Merge-and-simplify algorithm

Given a 2-map M and a set of darts K 1 (union of edges), the merge-and-simplify operation produces MS (M, K 1 ). Let see one algorihm to compute this 2-map from M and K 1 .

A first naive solution is to copy M into M , then to progressively simplify M in 3 steps: (1) remove all edges in K 1 ; (2) remove all dangling edges; (3) remove all 0-reducible vertices.

Hopefully, it is possible to build MS (M, K 1 ) directly in linear time in number of darts of M, without having to start to copy M requiring thus less memory allocation/de-allocation.

The principle of our method is (i) to mark all edges and all vertices to remove directly on M (thanks Algorithm 1); (ii) to build directly MS (M, K 1 ) by copying only non marked darts.

Algorithm 1: Merge-and-simplify: mark darts.

Input: A 2-map M; A set of darts K 1 , union of edges. Output: MS (M, K 1 ) 1 mark all darts in K 1 by m 1 ; 2 foreach dart d of M do Algorithm 1 starts by marking all given edges (line 1). Then, an iteration through each dart d is performed. A test is done to know if c 1 (d), the edge containing d, is dangling in the 2map obtained from M when removing all marked edges only by ignoring all darts marked by m 1 . When c 1 (d) is dangling, d is removed to the dart of an edge adjacent to c 1 (d) (line 5). Indeed, removing c 1 (d) can transform the adjacent edge into a dangling edge. Similarly for vertices, a test is performed to know if c 0 (d) is 0-reducible in the 2-map obtained from M when removing all marked edges and all marked vertices by ignoring all darts marked by m 0 or m 1 .

After the marking of removed darts, non marked darts can be copied, and Def. 4 can be used to link these darts together, by following the paths given in the definition.

Our compact combinatorial pyramids

The new merge-and-simplify operation enables a direct definition of compact combinatorial pyramid.

Definition 5 (Compact combinatorial pyramid). A 2dimensional compact combinatorial pyramid is a sequence of 2-maps (M 0 , . . . , M l ) where: ∀i, 1 ≤ i ≤ l, M i = MS (M i-1 , K i ), with K i a set of darts in M i-1 , being an union of edges forming a forest in M i-1 .

Let us compare a compact combinatorial pyramid P with a classical version P , which is defined by using only removal operations. In this case, each level M i in P (1 ≤ i ≤ l) corresponds to 3 levels in P : M j , M j+1 , M j+2 , with j = 3(i -1) + 1. M j = R 1 (M j-1 , K i ) is the level where given edges are removed.

M j+1 = R 1 (M j , E i0 ∪ . . . ∪ E il i ), where each E io is a dangling edge in R 1 (M j , E i0 ∪ . . . ∪ E i(o-1) ). M j+2 = R 0 (M j+1 , V i0 ∪ . . . ∪ V im i ), where each V io is a 0-reducible vertex in R 0 (M j+1 , V i0 ∪ . . . ∪ V i(o-1) ).
Three different levels are needed to (1) remove the given edges which are a forest in the dual 2-map; (2) remove all the dangling edges; (3) remove all the 0-reducible vertices. ( 2) and (3) can not be applied simultaneously by the classical removal operation because the set of concerned darts are not independent. ( 1) and ( 2) can be regrouped in a same level because they both use edge removal. In this case, only 2 levels is needed in P for each level in P (except for the base level).

With the first solution, the height of P is three times the height of P which is our compact version. With the second solution, the height of P is twice the height of P.

Reducing the height of the pyramid is interesting for two reasons: (1) it decreases the memory space required to represent the pyramid when using an explicit representation, since they are less darts to represent; (2) it decreases the time complexity of operations that traverses the pyramid, since this complexity is often based on the number of levels of the pyramid traversed.

It is important to remind that information described by the compact combinatorial pyramid is the same than the one described by the original version. Indeed, the meaningful levels are the ones without dangling edges, nor 0-reducible vertices, and these levels are the same in both pyramid versions.

Experiments

All experiments were run on an Intel R i7-4790 CPU, 4 cores @ 3.60GHz with 32 GB RAM. Both original and compact versions of the combinatorial pyramids have been implemented by using the CGAL implementation of combinatorial maps [START_REF] Damiand | Combinatorial maps[END_REF]). A combinatorial pyramid was built, starting from a 2-map that represents all image pixels as basis. In this level each region has one pixel. Then a new level was added by merging all pair of adjacent regions such that the difference between the two regions mean gray level is smaller than a given threshold τ. We started with τ = 5, and multiplied it by 2 for each new segmentation level. The process was ended when the top level of the pyramid has only 2 regions (one for the image pixels, the second one corresponding to the unbounded face). Fig. 6 presents 2 levels obtained for Img3. Fig. 7 shows the sum of number of darts of all levels, except the basis, for the pyramids computed from the 6 images. Each point represents one image: its x-coordinate is the number of darts of the original pyramid and its y-coordinate is the number of darts of the compact version. The fitting line has a slope of 0.34: the number of darts used by a compact pyramid can be approximated by 0.34 times the number of darts of the corresponding original pyramid. Moreover, Table 1 gives the number of darts used by the compact combinatorial pyramid in percentage of the number of darts of the classical one: in average, a compact combinatorial pyramid uses only 32.2% of darts of the corresponding classical pyramid, which is coherent with the slope of the fitting line obtained in Fig. 7. In these results, the number of darts of the basis were not summed up as it has a specific structure: this is a set of regular squares glued together (one square per pixel). Due to this specificity, it is inefficient to represent the basis using a classical data-structure for 2-maps (with darts and pointers): it is only implicitly represented. 2 gives the computation time (in seconds) to build the combinatorial pyramids for the 6 images for both versions. These computation were quite good, taking into account the big size of images. This table also gives the time used by the construction of the compact version in percentage of the time spent by the classical version. In average, the compact method uses 64.6% of the time of the classical construction method. shows these computation times using the same principle that the one used in Fig. 7 for the number of darts. Each point represents one image: its x-coordinate (resp. y-coordinate) is the computation time to construct the original (resp. compact) pyramid. The fitting line has a slope of 0.63: the computation time can be approximated to build a compact pyramid by 0.63 times the computation time to build the corresponding original pyramid. Our experiments show that using the compact version allows us to decrease the number of darts of about 64% and decrease also the computation time to build the pyramid of about 27%, without introducing any drawback. This shows the interest of using the compact version instead of the original one.

Conclusion

In this paper, a new operation on 2-maps is defined, mergeand-simplify, which allows us to merge some faces then to simplify the dangling edges and the 0-reducible vertices in a single operation. This operation is equivalent to apply successively three times the original removal operations. Our new operation can be used in order to define compact combinatorial pyramids which decrease the height of previous combinatorial pyramids. As illustrated in our experiments, this decreases the memory space used to store such a pyramid in an explicit representation, and it decreases also the computation time of the pyramid.

In our future work, we are going to define connecting walks, connecting dart sequences and receptive fields with our new framework: the three central notions when we want to retrieve information in a given level based on information on previous levels. We also would like to extend the merge-and-simplify operation in higher dimension.

Figure 1 :

 1 Figure 1: (a) A 2-map. (b) The 2-map obtained from (a) by the removal of edge {1, 5} and the removal of vertex {10, 13}.

  Figure 2: (a) An image. (b) Result obtained after the removal of some edges in the 2-map describing all the pixels of this image, these edges being a forest in the dual 2-map. (c) Result obtained after the removal of all dangling edges of (b). (d) Result obtained after the removal of all 0-reducible vertices.

Figure 3 :

 3 Figure 3: Illustration of the different steps to simplify a 2-map when using the original removal operation. (a) Initial configuration, one edge {12, 13} is marked to remove. (b) Result of the removal of edge {12, 13}. Now edge {6, 7} is dangling and thus marked to remove. (c) After the removal of edge {6, 7}, the two vertices {3, 8} and {4, 11} are 0-reducible. (d) Result of the removal of the two vertices {3, 8} and {4, 11}.

Figure 4 :

 4 Figure4: Same simplification than the example given in Fig.3, but using now the merge-and-simplify operation. (a) Initial configuration: edge {12, 13} ∈ K 1 , is the only input of the operation. Edge {6, 7} is dangling in M R 1 (K 1 ) and is thus added in K 1 . Vertices {3, 8} and {4, 11} are 0-reducible in M R 1 (K 1 ) and are thus added in K 0 . (d) Result of the merge-and-simplify operation, where edges in K 1 then vertices in K 0 are removed.

3

  while c 1 (d) is dangling, ignoring all darts marked by m 1 do 4 mark c 1 (d) by m 1 ; 5 d ← one non marked dart adjacent to c 1 (d); 6 foreach dart d of M do 7 if c 0 (d) is 0-reducible, ignoring all darts marked by m 0 or by m 1 then 8 mark c 0 (d) by m 0 ;

  Fig. 5 shows two images used for the experiments (images from Unsplash (https://unsplash. com/), taken resp. by C. Hu, D. Dobrila, J. Alexander, K. Toth, M. Asthoff and T. Naccarato). The sizes of images used are 1834 × 2000 (Img1), 2200 × 1313 (Img2), 3000 × 2000 (Img3), 3456×5184 (Img4), 5616×3744 (Img5) and 1280×853 (Img6).

Figure 5 :

 5 Figure 5: Two images used for the experimentations (Left) Img1. (Right) Img2.

Figure 6 :

 6 Figure 6: Two levels of the compact pyramid computed from Img3 (one random color per region). (Left) level 2. (Right) level 3 with less regions.

Figure 7 :

 7 Figure 7: Number of darts (without basis) of the different pyramids. A point represents one image: its x-coordinate (resp. y-coordinate) is the number of darts of the original (resp. compact) pyramid.

  Fig. 8

Figure 8 :

 8 Figure 8: Computation time to build the different pyramids. A point represents one image: its x-coordinate (resp. y-coordinate) is the computation time to construct the original (resp. compact) pyramid.

Table 1 :

 1 Number of darts of the compact combinatorial pyramid in percentage of the number of darts of the classical one.

	Img1	Img2	Img3	Img4	Img5	Img6	Average
	31.7% 22.0% 23.4% 33.6% 33.4% 35.1% 32.2%

Table

Table 2 :

 2 User time in seconds for constructing (a) the classical or (b) the compact combinatorial pyramid. (c) Time used by the construction of the compact version in percentage of the time spent by the classical version.

	Img1	Img2	Img3	Img4	Img5	Img6
	(a) 47.3s	29.9s	69.6s	303.8s 351.4s 14.1s
	(b) 30.4s	19.8s	45.9s	189.7s 226.6s 9.1s
	(c) 64.3% 66.2% 65.9% 62.4% 64.5% 64.6%

By definition of edges in

2-maps, E is a set of darts.

A forest is a set of trees, thus a set of edges without cycle, but not necessarily connected.