Romain Goffe
email: goffe@sic.univ-poitiers.fr

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

Luc Brun
email: luc.brun@greyc.ensicaen.fr

A causal extraction scheme in top-down pyramids for large images segmentation

Keywords: Irregular pyramid, Topological model, Tiled data structure, Combinatorial map

Applicative fields based on the analysis of large images must deal with two important problems. First, the size in memory of such images usually forbids a global image analysis hereby inducing numerous problems for the design of a global image partition. Second, due to the high resolution of such images, global features only appear at low resolutions and a single resolution analysis may loose important information. The tiled top-down pyramidal model has been designed to solve this two major challenges. This model provides a hierarchical encoding of the image at single or multiple resolutions using a top-down construction scheme. Moreover, the use of tiles bounds the amount of memory required by the model while allowing global image analysis. The main limitation of this model is the splitting step used to build one additional partition from the above level. Indeed, this step requires to temporary refine the split region up to the pixel level which entails high memory requirements and processing time. In this paper, we propose a new splitting step within the tiled top-down pyramidal framework which overcomes the previously mentioned limitations.

Introduction

High resolution image analysis usually entails memory issues that prevent them from being processed by common models. Moreover, in multi-resolution images, the amount of details at full resolution is likely to mask global features which only appear at lower resolutions. For instance, applicative fields such as whole slide microscopic imaging produce large multi-resolution images with resolutions up to 40 000×40 000: low resolutions let appear global features such as tissues delimitations while high resolutions allow to discern the different phases of mitosis within cells. As a result, analyzing such images implies a hierarchical representation with memory constraint.

The segmentation of an image defines an image partition into connected regions. Models for such partitions usually encode either geometrical or topological features of the partition. Operations involving both types of information are thus hard or costly to implement. For example, RAG-based data structures lack efficient access to regions' geometry. This drawback has entailed the design of topological maps [START_REF] Brun | Incremental modifications of segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF] for an efficient representation of both geometrical and topological information while allowing modifications of a partition through split and merge operations. Yet, they cannot apply to multi-resolution images since they do not encode a hierarchy of partitions.

Quadtrees and regular pyramids' frameworks provide a multi-resolution description of the image and a hierarchical segmentation scheme [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF] inducing a hierarchy of regions that may be defined onto such models. However, both models present several drawbacks: a given regular pyramid may fail to encode connected regions of any size and shape nor provide an efficient access to the neighborhood of a region. Moreover, both quadtrees and regular pyramids do not ensure that connected regions defined at a given level remain connected at the level below. The irregular pyramid framework has been introduced by [START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF] to overcome these limitations with different segmentation schemes such as [START_REF] Jolion | The adaptative pyramid: A framework for 2d image analysis[END_REF][START_REF] Kropatsch | Building irregular pyramids by dual graph contraction[END_REF]. Finally, in order to access both geometrical and topological information, [START_REF] Brun | Combinatorial pyramids[END_REF][START_REF] Grasset-Simon | n-d generalized map pyramids: Definition, representations and basic operations[END_REF] proposed a model of irregular pyramids composed of combinatorial maps. When applied to high resolution images, the bottom-up construction scheme of combinatorial pyramids raises at least two issues: memory usage and relevance of extracted information. Indeed, a bottom-up scheme starts from an explicit encoding of the whole initial partition: for large images this requires a large amount of memory especially if additional levels must also be computed. Moreover, in hierarchical data analysis, extracted information is usually more relevant if the construction scheme allows to use a region to influence the way its children (defined at a higher resolution) are processed. As a result, [START_REF] Goffe | Extraction of tiled top-down irregular pyramids from large images[END_REF] have introduced the tiled top-down framework for combinatorial pyramids.

A tiled top-down pyramid is a hierarchical model based on topological maps [START_REF] Brun | Incremental modifications of segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF] and thus, provides an efficient access to both geometrical and topological information. A top-down pyramidal model allows to reduce memory usage by encoding upper levels in the pyramid and refining only areas of interest. Moreover, the subdivision in tiles allows to bound the required amount of memory. Yet, its main drawback comes from its construction process [START_REF] Goffe | A top down construction scheme for irregular pyramids[END_REF]: in order to refine a region, a first step splits it into basic regions enclosing single pixels before the application of a merging step. This step may thus require a large amount of available memory to make temporary regions. Since the main operation in a top-down scheme consists in regions' splitting, we have explored alternative splitting techniques for combinatorial models. Different approaches have been proposed such as insertion operations [START_REF] Braquelaire | Representation of segmented images with discrete geometric maps[END_REF] or incremental extractions [DBF04, BDM03] but those methods are not designed for a causal hierarchical model [START_REF] Guigues | Scale-sets image analysis[END_REF]. This causal property is fundamental within the tiled top-down pyramidal framework since it ensures the existence of a hierarchy.

In this paper, we propose a new method for the construction of tiled top-down pyramids which avoids the temporary split of a region into basic regions enclosing a single pixel while preserving the causality of the pyramid. In Section 2, we present the different topological models used to define a tiled top-down pyramid. In Section 3, we detail our causal extraction for such pyramids. Finally, experiments and segmentation results are proposed in Section 4 in order to emphasize the advantage of our method.

Recalls

Combinatorial Maps

In two dimensions, a combinatorial map (noted 2-map) is a set of vertices, edges and faces that encodes the subdivision and incidence relationships of a topological space [START_REF] Lienhardt | Subdivisions of n-dimensional spaces and ndimensional generalized maps[END_REF]. A complete decomposition of an image results in a set of abstract basic elements called darts. We introduce two operators noted β i , i ∈ {1, 2} that apply on darts in order to represent adjacency relationships (Figure 1).

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

(2) β 1 is a permutation 1 on D;

(3) β 2 is an involution 2 on D.

Intuitively, we can consider a map as a planar graph where β i operators explicitly define the relationships between edges and where darts allow to differentiate the two extremities of an edge (a dart may be assimilated to a half-edge). In practice, the β 1 permutation allows to turn around a face: it links a dart of a face to the next one encountered while turning clockwise around it. The β 2 involution separates two adjacent faces: it links a dart to the other dart that belongs to the same edge but has an opposite orientation. For instance, in Figure 1(d),β 1 (3) = 4 and β 2 (4) = 5. As a result, a 2-map is a connected set of cells of 0, 1, and 2 dimensions. For i ∈ {0, 1, 2}, an i-cell respectively denotes a vertex, an edge and a face. The degree of an i-cell is its number of distinct incident (i + 1)-cells.

Topological Maps

Since combinatorial maps only describe topological relationships, an extension of the model which also encodes geometrical information has been introduced for a full 1 A permutation is a one to one mapping from S onto S. 2 An involution f is a one to one mapping from S onto S such that representation of a partition: the model of topological map [START_REF] Brun | Incremental modifications of segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF]. A topological map combines three distinct models: a 2-map that encodes topological relationships, a matrix of interpixel elements [Kov89, KKM90] that encodes the geometry of the partition elements, and a tree of regions for inclusion relationships. These three models are illustrated in Figure 2 and described below.

f = f -1 . (a) (b) (c) (d)

Minimal combinatorial map

As illustrated in Figure 2(b), a 2-map encodes topological relationships through β 1 and β 2 operators (Section 2.1). The combinatorial map is minimal in number of cells: there is not any vertex with a degree lower or equal to 2 and therefore, the removal of any element would change the topology. For implementation purposes, darts and regions are linked together: a dart knows the region it belongs to and a region knows a representative dart (arbitrary chosen on the external border of the region). Note that the infinite region may be omitted in some figures for visibility reasons.

Matrix of interpixel elements Pointels, linels and pixels [START_REF] Khalimsky | Boundaries in digital planes[END_REF] represent the geometry of a partition. Associating geometrical information to a topological element is an operation called embedding. Similarly to vertices, edges and faces, we respectively refer to pointels, linels and pixels as i-cells, i ∈ {0, 1, 2}. We respectively denote by pointel(d) and linel(d) the first pointel and linel of the embedding of a dart d. For example, in Figure 2(c), the embedding of the edge (1,2) is the sequence of linels (l 1 , l 2 , l 3 ); linel(1) = l 1 , pointel(2) = p 2 ; degree(p 1 ) = degree(p 2 ) = 3.

Tree of regions

The tree of regions describes inclusion relationships: a region is the father of the regions it contains. In Figure 2(d), r 1 contains r 2 , r 3 and r 4 , r 2 and r 3 are adjacent. The root of the tree encodes the background of the image and is called the infinite region (noted r ∞ ).

Tiled Top-down Framework for Combinatorial Pyramids

A hierarchical extension of the topological map model is proposed by [START_REF] Goffe | A top down construction scheme for irregular pyramids[END_REF]. Contrary to bottom-up methods, this framework uses a top-down approach which induces a segmentation process based on a rough partition refined at further levels: it results in a major memory reduction since regions may only be encoded at the top level of the pyramid. Moreover, it allows to take advantage of the focus of attention over interesting regions: the segmentation of a region can be adapted according to the features of its parent. Despite this memory reduction, [START_REF] Goffe | Extraction of tiled top-down irregular pyramids from large images[END_REF] proposes a subdivision of the levels into topological tiles in order to bound the amount of required memory. A topological tile is a topological map with an additional involution β 2 which applies on darts belonging to a border shared by two adjacent tiles [START_REF] Goffe | Extraction of tiled top-down irregular pyramids from large images[END_REF] to ensure their topological connection. The juxtaposition of topological tiles composes a tiled topological map. Such a map may contain fictive elements along the tiles' borders when, according to a given merging criterion, pixels on both sides of a tile's border belong to a same region. Linels encoding these fictive borders are marked by a flag indicating their fictive state. Tiled combinatorial maps (Definition 2) redefine the operators β 1 and β 2 [START_REF] Goffe | Extraction of tiled top-down irregular pyramids from large images[END_REF] to abstract those fictive elements (Figure 3(c)).

Definition 2 (Tiled combinatorial map). Let T be a set of connected topological tiles T = {t(i, j)} (i,j)∈{0,...,W }×{0,...,H} . Let D be the set of darts of T with a real embedding. A tiled combinatorial map M is a triplet M = (D, δ 1 , δ 2 ) where, ∀d ∈ D:

(1) δ 1 is a permutation on D such as:

δ 1 (d) = β 1 ((β 2 β 1 ) n (d)) with n = min{p ∈ N | linel(β 1 ((β 2 β 1 ) p (d)) is real} (2) δ 2 is an involution on D such as: δ 2 (d) = β 2 (d) if β 2 (d) exists β 2 (d) otherwise
A tiled top-down topological pyramid is a stack of finer and finer partitions denoted by P = {G k } k∈{0,...,n} where G k+1 is a tiled combinatorial map (Definition 2) deduced from G k by splitting operations. Within a pyramid, a tile is denoted by t(i, j, k) where (i, j, k) are the coordinates (i, j) of t at level G k . Besides, the pyramid may swap or load tiles between memory and disk and spread global modifications: if an operation modifies a tile's border, adjacent tiles that are either on disk or in memory should be updated. Note that a stack of successively refined partitions differs from the notion of resolution used within the regular pyramid framework: top-down pyramids can be constructed either from single or multi-resolution images.

Although, the pyramid mixes both regular and irregular notions, the top-down model remains an irregular pyramid since it handles fictive borders between the tiles. The resulting sequence of partitions is a causal structure [START_REF] Guigues | Scale-sets image analysis[END_REF] where hierarchical relationships are encoded through up/down relationships between tiles, darts and regions.

A first strategy to build the pyramid is to start from a single region and refine it according to segmentation criteria. The operation is performed in three steps. First, the last level is duplicated and up/down relationships are set. Second, a splitting criterion indicates the regions to refine. Those regions are split into a set of basic regions enclosing a single pixel. Third, the basic regions are merged according to a merging criterion. Since any couple of adjacent regions may be merged, this refinement step may encode any subdivision of the parent region. Yet, this solution presents a major drawback: the splitting step in one region per pixel is a bottom-up refinement that encodes every pixel of the split region. Such an operation implies useless calculus and important memory requirements.

A Causal Extraction Scheme for Tiled Top-down Pyramids

Our main objective consists in avoiding the bottom-up refinement step temporary creating one region per pixel. We propose with Algorithm 1 a hierarchical extension of the extraction scheme introduced by [START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF]. In order to adapt it to the tiled top-down pyramidal framework, we must fulfill two main constraints:

• the causal constraint entails that existing borders are preserved from one level to an other: any border defined in G k must exist in G k+1 and darts and regions of G k must be connected to their children in G k+1 .

• the top-down constraint (focus of attention): since we use a splitting criterion which determines whether a region should be refined in the next level, no border should be created within regions whose splitting criterion is false.

Those two constraints are illustrated in Figure 4. In Figure 4(a), the causality is ensured as each border defined in G k exists in G k+1 with up/down relationships set accordingly. For example, when the darts 3 and 4 are created, they must be linked with their respective parents 1 and 2. In Figure 4(b), the focus of attention for the top-down construction is respected as regions whose splitting criterion is set to false are not refined: no border is inserted in down(r 1 ) while r 2 is refined in G k+1 .

The global scheme of the extraction algorithm is the following. All the pixels of a tile t in G k+1 are traversed with a scanline traversal from top-left to bottom-right corner. For each pixel p, we create the region enclosing it (line 1 of Algorithm 1) which results in the insertion of two new borders between the p and its top and left neighbors. Then, we determine whether those borders should be kept or removed (line 2-3) by calling Algorithm 2. First, our two constraints must be respected: a border is kept if it corresponds to an existing border in G k (line 1 of Algorithm 2) and is removed if it corresponds to a forbidden refinement (line 2). Once those two conditions are verified, a merging criterion determines if the border is (line 3). Since a topological map aims at representing regions, the merging criterion has to define a partition: we may use a quantization of the tile up but conversely, a criterion based on a minimum gradient would lead to the creation of an inconsistent map with dangling edges. The last step finalizes the extraction by removing degree two vertices and computing the tree of regions (line 5 of Algorithm 1) as described in [START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF]. In the following, we implicitly use projections between levels: if p is a pixel of G k+1 , region(p) in G k refers to the region of the projection of pixel p in G k . In order to answer the first two conditions of Algorithm 2, two external structures related to up(t) called embedding structure and regions structure are required and detailed below.

Embedding structure This structure establishes the correspondence between darts and their embedding in a tile by mapping each linel to its dart. Thus, we can determine from the embedding of a dart d in G k+1 if there exists a dart d in G k whose embedding is down-projected onto the one of d. In this case, the border is kept and we establish up/down relationships between d = down(d ) and d = up(d) (line 4 of Algorithm 1).

Regions structure Similarly to an image of labels, this structure maps each tile's pixel to its region. It allows to know the splitting criterion of a pixel p in the above level. For instance in Figure 4(b), we can determine that region(p 7 ) in G k is r 1

Conclusion

In this paper, we have presented an alternative construction scheme for the extraction of tiled top-down pyramids that overcomes the main drawbacks of the previous method. First, our method requires less computational time and memory usage. Second, it still preserves the top-down hierarchical relationships of the model. Therefore, our method can favorably act as a replacement for the burst and merge refinement step during the construction of a tiled top-down pyramid. Finally, our causal extraction algorithm presents interesting perspectives for parallel computation that we plan to implement in our future work.

Figure 1 :

 1 Figure 1: Combinatorial maps: construction by successive decompositions. (a) Original image; (b) Decomposed faces; (c) Decomposed edges; (d) 2-Map: arrows represent darts, β 1 and β 2 operators are respectively represented by arcs and segments.

Figure 2 :

 2 Figure 2: Topological map: three complementary models for image representation. (a) Original image; (b) Combinatorial map for topological relationships. Dotted arrow denotes the dart of the infinite region; (c) Interpixel matrix for geometrical encoding: pointels and linels are represented by bold circles and segments; (d) Tree of regions.

Figure 3 :

 3 Figure 3: Representation of a top-down pyramid composed of two levels G k and G k+1 . (a) Original image: a tile t is decomposed in two tiles t 1 and t 2 (ratio = 2 × 2); (b) Interpixel matrix: fictive borders appear between t 1 and t 2 ; (c) Tiled combinatorial maps: δ 1 and δ 2 are represented by arcs and segments. Dotted arrows denote darts with a fictive embedding; (d) Relationships between darts.

Figure 4 :

 4 Figure 4: Extraction constraints for a tiled top-down pyramid. G k is a single tile t decomposed in G k+1 into 4 subtiles (ratio = 2 × 2). (a) Causal constraint: preserves existing borders; (b) Top-down constraint: the focus of attention only refines regions whose splitting criterion is true. Dotted arrows denote fictive borders.

Figure 5 :

 5 Figure 5: Causal extraction of a tiled top-down pyramid from a multi-resolution histological image. From left to right: low resolution of the original image, three different levels of the pyramid with increasing resolutions encoding a same small area.

The model is implemented in C++ and computations are carried out on an Intel E5300@2GHz with 2GB RAM.

Acknowledgements

This research is part of the FoGrImMi project, supported by the ANR foundation under grant ANR-06-MDCA-008-01/FOGRIMMI.

whose splitting criterion is false (r 1 must not be refined) so we do not keep the border between p 7 and p 5 .

Experiments

This section has two main objectives: show the advantage of our causal extraction algorithm compared to the initial burst-merge refinement and present first segmentation results obtained on histological images.

In Table 1, we provide runtime 3 and memory usage for our causal extraction algorithm (column 6-7) compared to a burst-merge refinement (column 4-5) with a fixed tile size of 512 × 512. We can notice that our extraction method globally improves the computational time from 15 to 40% with a reduction of memory usage around 10%. The computational time is mostly due to pixel traversal (to get colorimetric information for the regions) and segmentation criteria computation.

We illustrate the results of our extraction in Figure 5. This example shows the tiled map of the same small area of an histological image at different resolutions (4 000 × 3 036, 8 000 × 6 072, 32 000 × 24 291). The segmentation is based on an image quantization algorithm in two classes [KMN + 02].


Romain Goffe
email: goffe@sic.univ-poitiers.fr

Luc Brun
email: luc.brun@greyc.ensicaen.fr

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

Tiled top-down combinatorial pyramids for large images representation

Keywords: Irregular pyramid, Topological model, Tiled data structure, Combinatorial map

The uprising number of applications that involve very large images with resolutions greater than 30 000×30 000 raises major memory management issues. Firstly, the amount of data usually prevents such images from being processed globally and therefore, designing a global image partition raises several issues. Secondly, a multi-resolution approach is necessary since an analysis only based on the highest resolution may miss global features revealed at lower resolutions. This paper introduces the tiled top-down pyramidal framework which addresses these two main constraints. Our model provides a full representation of multi-resolution images with both geometrical and topological relationships. The advantage of a top-down construction scheme is twofold: the focus of attention only refines regions of interest which results in a reduction of the amount of required memory and in a refinement process that may take into account hierarchical features from previous segmentations. Moreover, the top-down model is combined with a decomposition in tiles to provide an accurate memory bounding while allowing global analysis of large images.

Introduction

Applicative fields involving high-resolution images raise two main issues for automatic or semi-automatic image analysis. First, images are produced with a very high resolution that usually prevents them from being processed by common models due to memory limitations. Second, the amount of details at full resolution is likely to mask global features which only appear at lower resolutions. For example, scanners for whole slide microscopic imaging produce multi-resolution images with resolutions up to 32 000 × 32 000: low resolutions let appear global features such as tissues delimitations while high resolutions allow to discern the different phases of mitosis within cells. As a result, analyzing such images implies a hierarchical representation with memory constraint.

The segmentation process is the first phase of image analysis: it defines a partition of the image according to a given criterion. Usually, data structures encoding those partitions focus either on geometrical or topological properties of partitions. Geometrical data structures such as arrays of labels provide an efficient encoding of both colorimetric and geometrical features of the partitions but do not provide an efficient access to topological features such as region adjacencies. On the other hand, topological data structures such as RAG represent those topological relationships but do not provide an efficient access to the geometrical properties of a partition. Moreover, such data structures do not allow to discriminate fine topological relationships: for instance, they may not indicate if a region is adjacent or included into another one. Topological maps [START_REF] Brun | Incremental modifications of segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for two-dimensional image representation: definition and optimal extraction algorithm[END_REF] are designed to efficiently access both geometrical and topological properties while allowing modifications of a partition through split and merge operations. Yet, they cannot apply to multi-resolution images since they do not encode a hierarchy of partitions.

Within the hierarchical framework, quadtrees and regular pyramids [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF] were the first structures used for segmentation. Both are based on psycho-visual properties but their approach is different: quadtrees use the top-down notion of focus of attention and performs a segmentation using a recursive splitting algorithm whereas regular pyramids adopt a bottom-up approach where each pixel of a level corresponds to a larger set of pixels at the level below. However, both models induce major drawbacks [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF]: they fail to neither encode connected regions of any size and shape at a given level nor provide an efficient access to the neighborhood of a region. Moreover, regular pyramids do not ensure that connected regions defined at a given level remain connected at the level below. Considering these limitations, [START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF] introduced the irregular pyramid framework which overcomes the drawbacks of its regular ancestors using a bottom-up construction scheme. Many segmentation algorithms have then been designed on this framework such as [START_REF] Jolion | The adaptative pyramid: A framework for 2d image analysis[END_REF][START_REF] Kropatsch | Building irregular pyramids by dual graph contraction[END_REF]. Finally, in order to access both geometrical and topological information, [START_REF] Brun | Combinatorial pyramids[END_REF][START_REF] Grasset-Simon | N-d generalized map pyramids: Definition, representations and basic operations[END_REF] proposed a model of irregular pyramids composed of combinatorial maps. However, a bottom-up analysis scheme raises at least two issues when applied to high resolution images: memory usage and relevance of extracted information. Indeed, encoding the whole initial partition of a large image is likely to require a large amount of memory especially if additional levels must be computed. Moreover, extracted information is usually more relevant if the construction scheme allows to use a region to influence the way its children (defined at a higher resolution) are processed. For example, within the histology application field, we may choose to refine differently the cells at full resolution depending on whether their parent region has been identified as stroma or as a cancerous area. The top-down construction scheme proposed by [START_REF] Goffe | A top down construction scheme for irregular pyramids[END_REF] overcomes these two constraints. Nevertheless, the issue of memory constraint is only partially solved since the number of regions defined at a given level is only bounded by the size of the image encoding this level in the pyramid.

The objective of this paper is the definition of a tiled structure for top-down irregular pyramids. We present in Section 2 the topological models used by our structure. In Section 3, we define the framework of tiled top-down pyramids. Finally, we present some experiments and segmentation results in Section 4 that highlight involved memory requirements and practical applications of the model.

Image Representation

Interpixel Boundaries

Within the segmentation framework, an image is decomposed into a set of regions where each region is a connected set of pixels. Representing the geometrical information of a partition consists in encoding the shape of its regions. We use a data structure relying on a matrix of interpixel elements ([Kov89, KKM90]) to encode the geometry of the partition elements. Thus, from a geometrical point of view, the partition is represented by an abstract cell complex (AC complex) composed of pointels (or points), linels (or cracks) and pixels, referred to as k-cell, k ∈ {0, 1, 2} (Figure 1(a)). We consider this representation as geometrical since each k-cell has an explicit geometrical embedding. AC complexes are locally finite Alexandroff spaces [START_REF] Alexandroff | Diskrete räume[END_REF]: every cell has a minimal finite neighborhood. Topological notions within an AC complex such as incidence or adjacency have been defined by [START_REF] Kovalevsky | Algorithms and data structures for computer topology[END_REF]:

• the border of a k-cell is a set of (l < k)-cells defined by a bounding relation;

• two k-cells are incident if one belongs to the border of the second;

• two k-cells are adjacent if they are both incident to a same (l < k)-cell;

• the degree of a k-cell is the number of adjacent (k + 1)-cells.

Let us introduce definitions of bounding elements that compose regions boundaries (Figure 1(c)):

• a bounding linel separates two pixels belonging to different regions;

• a bounding pointel is incident to at least two pixels belonging to different regions;

• a bounding path is an alternated sequence of bounding pointels and bounding linels;

Finally, regions boundaries are geometrically described as follow (Figure 1(d)):

• a segment is a maximal bounding path between two regions since it cannot be prolongated without modifying one of the two incident regions;

• a node results from the intersection of at least three segments: a segment connects two nodes.

Since a segment is a sorted sequence of bounding pointels and linels, two orientations are possible: each segment defines two oriented segments.

Combinatorial Maps

Adjacency and inclusion relationships between regions are usually referred to as the topological description of the image since those relationships are not tied to geometrical constraints. Contrary to the interpixel representation (Section 2.1), a two dimensional combinatorial map (2-map) only focuses on adjacency relationships between regions and, compared to a RAG structure, allows to represent multi-adjacencies.

A 2-map is based on two operators β 1 and β 2 that apply onto darts. A dart is an abstract basic element that corresponds to an oriented segment. It is associated to a single node, segment and region.

Definition 1 (2-dimensional combinatorial map). A two-dimensional combinatorial map M (or 2-map) is a triplet M = (D, β 1 , β 2 ) where:

1. D is a finite set of darts;

2. β 1 is a permutation1 on D;

3. β 2 is an involution2 on D.

Intuitively, we can consider a map as a planar graph where β i operators define relationships between edges. In practice, the β 1 permutation generates an orientation on the border of a face, more precisely, a clockwise cyclic order on the set of edges bounding a face. Each dart belongs to a single face and thus, to a single cycle of β 1 . The β 2 involution connects two darts belonging to a same edge, encoding an adjacency relationship. For instance, in Figure 2(b),β 1 (1) = 2, β 2 (2) = 5 and β 2 (5) = 2. For practical reasons, we also introduce the β 0 operator defined as

β 0 = β -1
1 . The notion of orbit is commonly used to traverse edges or faces: given φ a set of permutations φ = {f 1 , . . . , f k }, the orbit < φ > of a dart d represents the set of darts reachable from dart d by applying any combination of f i and f -1 i permutations.

Topological Maps

A topological map [BDM03, DBF04] combines three distinct models: a 2-map that encodes adjacency relationships, a matrix of interpixel elements [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF][START_REF] Khalimsky | Boundaries in digital planes[END_REF] that encodes the regions' boundaries and a tree of regions for inclusion relationships. These three models are illustrated in Figure 3 and described below.

Minimal combinatorial map

As illustrated in Figure 3(a), a 2-map encodes topological relationships through β 1 and β 2 operators. The combinatorial map is minimal in number of cells: there is not any vertex with a degree lower or equal to 2 and therefore, the removal of any element would result in regions merging and thus, would change the topology. For implementation purposes, darts and regions are linked together: a dart knows the region it belongs to and a region knows a representative dart.

Matrix of interpixel elements

All the cells of a 2-map are associated to their corresponding geometrical elements in the interpixel matrix. Associating geometrical information to a topological element is an operation called embedding. Given a dart d associated to a region r, a node n and a segment s:

• the orbit < β 1 > (d) corresponds to a face associated to region r. This relationship is encoded by a function region from D to the set regions labels such that region(d) = r;

• the orbit < β 1 •β 2 > (d) corresponds to a vertex associated to node n. Since each node correponds to a pointel, we encode this correspondence using a function pointel from D to the set of nodes labels such that pointel(d) = n;

• the orbit < β 2 > (d) corresponds to an edge associated to the unoriented segment s, each dart of < β 2 > encoding one orientation along s (for instance, For instance, in Figure 3(b), the embedding of dart 1 is the oriented segment represented by the sequence (p 1 , l 1 , l 2 , l 3 ); linel(1) = l 1 , pointel(1) = p 1 ; degree(p 1 ) = degree(p 2 ) = 3. Figure 3(d), summarizes associations between interpixel and topological representations.

Tree of regions

The tree of regions describes inclusion relationships: a region is the father of the regions it contains. In Figure 3(c), r 1 contains r 2 , r 3 and r 4 , r 2 and r 3 are adjacent. The root of the tree encodes the background of the image and is called the infinite region (noted r ∞ ).

Top-down Pyramids

In order to fit the hierarchical framework, the topological map model has been extended to top-down pyramids [START_REF] Goffe | Extraction of tiled top-down irregular pyramids from large images[END_REF] and we recall in this section the main notions and operations of the model. Each level of such a pyramid is deduced from the previous one by splitting operations. The resulting sequence of partitions defines thus a causal structure [START_REF] Guigues | Scale-sets image analysis[END_REF] which induces hierarchical relationships between levels: each level G k of a top-down pyramid is encoded by a topological map where each dart and each region is connected to its parent in G k-1 and one of its children in G k+1 . These links are called up/down relationships.

(a) (b) (c)
Contrary to bottom-up methods, based on an explicit encoding of the base of the pyramid, a top-down approach starts the segmentation process with a rough partition which is refined at further levels. This construction scheme results in a major memory reduction since many regions may be encoded only at the top level of the pyramid. Moreover, a top-down construction scheme allows to take advantage of the focus of attention over interesting regions: the segmentation of a region can be adapted according to the features of its parent.

During the construction of the pyramid, the refinement of a level is the main operation. In our model, it is performed in three steps. First, the level is duplicated and the up/down relationships are set (Figure 5(a)). Second, a splitting criterion selects the regions to refine in the next level. Those regions are decomposed into a set of basic regions, each region enclosing a single pixel (Figure 5(b)). Third, a merging process merges those basic regions according to a merging criterion. Since any couple of adjacent regions may be merged, this refinement step may encode any subdivision of the parent region (Figure 5(c)).

The different levels of a top-down pyramid encode a sequence of nested partitions, each level encoding additional details of the previous partition. This last notion is different from the notions of resolution used within the regular pyramid framework. For instance, a single image with a fixed resolution may be used within a topdown pyramid which will then encode different levels of details of a same image. An alternative solution consists in combining a top-down and a regular bottom-up pyramid. In this case, each level of a top-down pyramid encodes a partition of the initial image at a given resolution. The causality of the resulting hierarchy is induced by the construction scheme of a top-down pyramid. As a result, top-down pyramids can be constructed either from single or multi-resolution images.

3 Definition of a Tiled Top-down Pyramidal Model

Topological Tiles

The main drawback of the top-down pyramidal model is that the global amount of required memory is bounded below by the size of the larger partition processed within the pyramid: for each level, the whole topological map (which encodes the partition defined at this level) must be loaded. In the worst case, each region of the topological map encoding the base level partition may correspond to a single pixel hereby leading to an explicit encoding of the finest partition of the initial image.

Even if a top-down scheme usually supplies a major memory reduction compared to a bottom-up scheme, there is no accurate control over memory usage: a solution to this issue is to divide the topological map that represents a level into topological tiles.

Intuitively, a tile represents a regular and arbitrary subdivision of a level that can be recovered from the juxtaposition of all the tiles it has been split into. The interesting point in dividing the levels of the pyramid in tiles is that most of processings only require a few tiles at the same time: unused tiles can be stored apart by swapping them on disk so that a maximum of memory space is available for the tiles being processed. A simple solution to record a tile is to apply a unique label for each dart and region that identifies them in a file. Several strategies can be considered for the subdivision in tiles. A first approach would consist in defining a tile as a set of regions. However, such a solution looses the main advantage of memory bounding (a region may contain the whole image). A second approach is to keep a constant number of rectangular tiles per level. This strategy leads to single up/down relationships (one tile has exactly one parent and one child) but the size of a tile in G k depends on both the size of a tile in G 0 and the scale factor between the resolutions associated to G k and G 0 : in the case of a hierarchical image with important changes of resolution, the size of a tile on highresolution images is likely to exceed the available memory. A third approach uses a constant size of tiles: it offers an accurate control of the memory requirements since the amount of memory required by a tile is bounded by the size of the topological map encoding the finest partition on the tile. This last quantity is proportional to the size of the tile which is user-defined. We have thus preferred this solution for our model.

We define a topological tile as a rectangular area encoded by a local topological map composed of a combinatorial map, a geometrical matrix encoding interpixel elements and a tree of regions. Geometrically, two adjacent tiles have the same embedding along their shared border (Figure 6(b)). Topologically, each tile is a closed topological map (Figure 6(c)). We introduce a β 2 operator on the darts that belong to the border of a tile to ensure its connection with adjacent tiles (Figure 6(d)). The procedure ConnectTileBorders details the whole operation and is described below.

ConnectTileBorders

We call basic dart a dart d whose edge embedding is a single linel. Let s (resp. s ) be the set of darts that are adjacent to t (resp. t) and that belong to the infinite region of t (resp. t ). First, we split s and s into basic darts (line 1 of Algorithm 1). This splitting operation ensures that s and s share the same number of darts (Figure 7(a)). Second, we link t and t thanks to the β 2 operator (line 2) by traversing simultaneously the darts of s and s . This step is illustrated by Figure 7(b). Finally, since the previous steps may have created degree 2 vertices, we perform a simplification pass in order to maintain the minimal property of our model (line 3 and line 4). The idea is to process each vertex that belongs to the shared border (s, s ) of two adjacent tiles t and t , and to remove it according to the method in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF] 3 if its embedding is a pointel whose degree is equal to 2 in both t and t (Figure 7(c)). Indeed, the notion of minimality of the combinatorial map, presented in Section 2.3 may not be locally preserved along the tiles' borders: for example, in Figure 7(c), the tile t is not a minimal combinatorial map due to pointel p 1 whose degree is equal to 2.

Tiled Topological Maps

The connection of a set of tiles encodes a partition as a global structure called a tiled topological map. However, the geometrical subdivision entails two main consequences:

• the borders of the tiles should be considered as fictive if according to a given merging criterion, pixels on both sides of a tile's border belong to a same region (Figure 8(a));

• edges and regions may be split and shared by several tiles (Figure 8(b)).

Therefore, we detail below the DetectFictiveBorders procedure which allows to differentiate fictive borders from real ones. Moreover, we define the permutation δ 1 and the involution δ 2 in a tiled topological map in order to traverse edges and regions in the same way β 1 and β 2 allow to traverse a topological map.

DetectFictiveBorders

In order to specify whether or not an edge should be considered as fictive, we use a mark on the linels of the tiles borders. All the linels ation DetectFictiveBorders, all the linels of a segment associated to a fictive dart are marked as fictive and conversely, if all linels of a segment are fictive, the corresponding dart is fictive by definition. Therefore, the fictive property of a dart may be efficiently checked by testing the mark of one of its linels such as linel(d) (Section 2.3). Proposition 2 (δ 1 permutation). Let T be a set of connected topological tiles T = {t(i, j)} (i,j)∈{0,...,W }×{0,...,H} . Let D be the set of darts of T with a real embedding. δ 1 is a permutation on D such as:

(a) k = 0 (b) k = 1 (c) k = 2
∀d ∈ D; δ 1 (d) = β 1 ((β 2 • β 1 ) n (d)) with n = min{p ∈ N | linel(β 1 ((β 2 • β 1 ) p (d)) is real}
Proof. Since δ 1 applies from D onto D, the injection property implies that δ 1 is a permutation on D. Let us consider d and d such as

δ 1 (d) = δ 1 (d ). Then, (β 2 • β 1 ) n (d) = (β 2 • β 1 ) m (d). If n = m, then d = d since β 2 • β 1 is a permutation.
Otherwise, let us suppose that n > m. Then, (β 2 • β 1 ) n-m (d) = d which contradicts the definition of n. Thus, δ 1 is a permutation on D.

Note that using a 4-connected pixel grid, n cannot exceed 3. The three cases n = 0, n = 1, and n = 2 are illustrated in Figure 9.

The previous definitions of δ 1 and δ 2 operators allow to extend the definition of combinatorial maps to tiled combinatorial maps as follows:

Definition 2 (Tiled combinatorial map). Let T be a set of connected topological tiles T = {t(i, j)} (i,j)∈{0,...,W }×{0,...,H} . Let D be the set of darts of T with a real embedding. A tiled combinatorial map M is a triplet M = (D, δ 1 , δ 2 ) where:

(1) δ 1 is a permutation on D which follows proposition 2;

(2) δ 2 is an involution on D which follows proposition 1;

Tiled Top-down Pyramids

The pyramid defines a hierarchy by introducing up/down relationships between topological tiles, darts and regions. Except for the tiles of top and bottom levels of the pyramid that do not have respectively any parent and any child, each tile knows its single parent (tile up) and one of its child (tile down). Several tiles of a same level may have a same parent: since all the children of a given tile are adjacent, we can efficiently retrieve the children of a tile starting from the tile down and finding all its neighbors with the same tile up. We define a tiled top-down topological pyramid as a stack of tiled topological maps. The pyramid defines a three coordinates system of representation for a set of topological tiles denoted by t(i, j, k) where (i, j, k) indicates the coordinates (i, j) of the tile t at level k. Moreover, the pyramid may swap or load tiles between memory and disk and spread modifications to ensure the coherence of the model. For example, if a splitting operation modifies the border of a tile, the pyramid may update the adjacent tiles that are either on disk or in memory.

Definition 3 (Tiled top-down topological pyramid). A tiled top-down pyramid P composed of l + 1 tiled topological maps is defined by: P = {t(i, j, k)} k∈{0,...,l},(i,j)∈{0,...,W k }×{0,...,H k } where t(i, j, k) is a topological tile and ∀k, 0 ≤ k ≤ l:

(1) W k H k and (i, j) ∈ {0, . . . , W k } × {0, . . . , H k } encode respectively the number of tiles and the coordinates of one tile at level k. (2) t(i, j, k) is a topological tile encoding a partition of the geometrical tile (i, j) defined at level k; (3) t(i, j, k + 1), k < l is deduced from t(i, j, k) by performing splitting operations.

Note that, in addition to definition 5, a tiled top-down pyramid may alternatively be denoted by P = {G k } k∈{0,...,n} where G k+1 is a tiled combinatorial map (definition 2) deduced from G k by splitting operations. The hierarchy in a top-down pyramid is implicitly induced by up/down relationships. However, those relationships do not grant an immediate solution to retrieve edges and regions from one level to another. Indeed, the down relationship only provides a representative element of the connected set that represents a given object (edge or region) in a higher level. The issue consists in retrieving the correct neighbors of this representative and is detailed by two procedures EdgeChildrenRetrieval and RegionChildrenRetrieval respectively for edges and regions between two levels G k and G k+1 . Both procedures are illustrated by Figure 10.

EdgeChildrenRetrieval Algorithm 3 allows to retrieve an oriented segment defined at level G k in G k+1 . Due to the decomposition of the image partition into a set of tiles, such a segment is encoded in G k by a sequence of darts d i such as

d i = δ 1 (d i-1
). The algorithm retrieves the set of darts they have been split into in G k+1 . For each d i , we retrieve its children in G k+1 . For this purpose, down(d) is a first representative of d in G k+1 (line 1 of Algorithm 3). While traversing the set of darts incident to δ 1 (d), the dart up relationship indicates whether a dart corresponds to d i (line 2). In the example illustrated by Figure 10.a, edge e = (1, 2) may be retrieved considering the children of either dart 1 or dart 2. Let us consider dart 1. Darts 3 and 5 that correspond to 1 in G k+1 are respectively retrieved as down(1) and as the first dart d of the orbit < δ 1 • δ 2 > (δ 1 (3) = 4) verifying up(d) = 1. As a result, e = (1, 2) corresponds to the edges (3, δ 2 (3) = 7) and (5, δ 2 (5) = 8). RegionChildrenRetrieval Retrieving the children of a region r defined in G k can be decomposed in three main steps. First, down(r) provides a representative of r in G k+1 (line 1 of Algorithm 4). Second, neighboring regions are traversed using the orbit < 1 , δ 2 > (line 2). Third, the region up relationship indicates the regions that correspond to r (line 3). Finally, we call IncludedRegionsRetrieval (line 4) to add their included regions as long as their up is r (detailed below). In Figure 10.b, the children of r 1 in G k+1 are r 3 , r 4 and r 5 . The procedure retrieves r 3 as down(r 1 ), r 4 as a neighbor verifying up(r 4 ) = r 1 and r 5 as an included region of r 3 . Note that r 6 is ignored although it is an included region of r 5 since up(r 6 ) = r 2 = r 1 .

IncludedRegionsRetrieval This procedure, described in Algorithm 5, is called from Algorithm 4 on line 4. It uses the tree of regions in the topological map model to retrieve the children of a region R included in a region r such as up(r) = R (line 1 of Algorithm 5). Then, the procedure selects among them the regions whose up is R (line 2).

Construction Scheme

The construction scheme of a tiled pyramid is described below by the procedure TiledExtraction. It relies on the ConnectTileBorders operation described in Section 3.1. The operation is an incremental algorithm which only requires four tiles to be loaded into memory. For simplification purposes, given a tile t = t(i, j, k), lef t(t), top(t), right(t), bottom(t), up(t) respectively denote t(i-1, j, k), t(i, j -1, k), t(i + 1, j, k), t(i, j + 1, k) and t(i, j, k -1) as long as they are defined.

TiledExtraction

The global construction scheme of a tiled top-down pyramid starts by recording all the tiles of the initial map G 0 on disk (line 1 of Algorithm 6). The extraction scheme traverses tiles line by line from the top-left to the bottomright subdivision. In order to create a tile t (initially a copy of up(t)), three other tiles must be loaded into memory: up(t) since t is its refinement, lef t(t) and top(t)

Experiments and Application

This section has two main objectives: demonstrate the memory feasibility of the extraction of a combinatorial pyramid from large images and present first segmentation results obtained on histological images. We also provide runtime4 for the construction of tiled top-down pyramids from different images. 1, the extraction process is linear with the size of the image as we traverse all pixels to get colorimetric information for the regions. The maximum size of a tile is obtained when each pixel corresponds to a different region. In this case, the size of the combinatorial maps can be estimated as: 4 × sizeof (dart) × pixels + sizeof (region) × pixels. Our implementation results in sizeof (dart) = 60 bytes and sizeof (region) = 80 bytes. Experiments show similar values since the splitting method decomposes regions and produces one region per pixel before the merging step. Note that the required amount of available memory may be more important since the matrix of interpixel elements and the image5 must be loaded too. In Table 2, we provide runtime and memory usage for an extraction from different multi-resolution images. We can notice that the subdivision in tiles allows to bound memory requirements of the segmentation step.

Tiled top-down model

Discussion

In this paper, we have introduced the framework of tiled top-down pyramids as an extension of the model of topological map. Our model handles the hierarchical segmentation of large multi-resolution images. Indeed, it has been designed with the two following constraints: memory bounding and adaptive segmentation from global features present at low resolutions to finer details at high resolutions.

Our solution for memory bounding results in the decomposition of our model in a set of smaller structures, called topological tiles. Each resolution of the image is encoded by a set of connected tiles which form a tiled topological map. We have defined two new operators on those tiled levels to extend the operations defined for topological maps. These operators allow to abstract the artificial decomposition induced by the geometry of the tiles. Then, the pyramid defines a hierarchy between the topological tiles to encode the hierarchy induced by multi-resolution images. We also provide the main operations induced by this hierarchy.

In order to perform an adaptive segmentation of multi-resolution images, we have proposed a top-down construction scheme: each tile is deduced from its parent after splitting operations. The proposed algorithm is incremental and requires a maximum of four tiles in memory.

Finally, our experiments have confirmed that the memory bounding is sufficient to process large multi-resolution images such as histological images in whole slide imaging.

In our future work, we plan to improve the performance of the model with different splitting techniques and develop the segmentation aspect with new criteria specific to applications in histology.

Figure 1 :

 1 Figure 1: Interpixel boundaries. (a) Notations; (b) Original image; (c) Interpixel elements: bounding pointels and linels are filled; (d) Regions boundaries: segments and nodes.

Figure 2 :

 2 Figure 2: Combinatorial maps: a topological model for multi-adjacency relationships. (a) Original image; (b) 2-Map: arrows represent darts, β 1 and β 2 operators are respectively represented by arcs and segments; (c) Explicit β 1 and β 2 mappings.

Figure 3 :

 3 Figure 3: Topological map: three complementary models for partition encoding. (a) Combinatorial map for adjacency relationships. Dashed arrow denotes the dart of the infinite region; (b) Interpixel matrix for geometrical encoding: pointels and linels are represented by bold circles and segments; (c) Tree of regions for inclusion relationships; (d) Connection between the objects defined within the three models composing a topological map.

Figure 4 :

 4 Figure 4: Representation of a top-down pyramid composed of two levels G k and G k+1 . (a) Pyramid: β 1 and β 2 operators are represented by arcs and segments. Arrows between the levels show up/down relationships between darts and regions. Level G k is composed of a single region r 1 . The splitting operation on G k+1 allows to differentiate the two regions r 2 and r 3 ; (b) up/down relationships between darts; (c) up/down relationships between regions.

Figure 5 :

 5 Figure 5: Refinement of the regions that compose a level of a top-down pyramid. (a) Level duplication and up/down relationships between darts and regions; (b) Decomposition of selected regions into basic regions enclosing a single pixel; (c) Merge regions according to criterion result.

Figure 6 :

 6 Figure 6: Topological tile. (a) An image divided into 4 tiles; (b) Geometrical representation; (c) Topological representation. β 2 operator is represented by bold segments; (d) Detail of the connection between t(0, 0) and t(0, 1). Darts 2 and 3 belong to the infinite region. β 2 (1) = 2, β 2 (4) = 3, β 2 (1) = 4.

Figure 7 :

 7 Figure 7: Connection of borders between two tiles. (a) Splitting of the border into basic darts; (b) β 2 connection: d and d are two basic darts that belong to r ∞ and p = pointel(d) = pointel(β 2 (d )). Connecting t and t comes to link β 2 (d) with β 2 (d ) such as β 2 (β 2 (d)) = β 2 (d ); (c) Simplification step: degree(p 1 ) equals 2 in t but 3 in t whereas degree(p 2 ) equals 2 in both t and t : the vertex removal operation is only performed on pointel p 2 .

Figure 9 :

 9 Figure 9: The three different cases that define the δ 1 permutation. Each square belongs to a different tile. Dashed arrows denote the darts of the infinite region.

Figure 10 :

 10 Figure 10: Children retrieval operations for edges and regions in a tiled top-down pyramid. (a) Edge (1,2) corresponds to the edges (3,7) and (5,8); (b) Region r 1 corresponds to r 3 , r 4 and r 5 .

Figure 11 :

 11 Figure 11: Extraction of a tiled top-down pyramid from a multi-resolution histological image. (a) Partial representation of the original resolution; (b) Partitions.

Table 1 :

 1 Memory and time comparison between non-tiled and tiled top-down models for different scalings of image Lena with a basic segmentation criterion based on average gray values of the regions with user-defined thresholds of 30/20/10 for G 1 /G 2 /G 3 .

		top-down model	tiled top-down model
	img side extract	ram extract	ram	disc
	(pixels) runtime (MB) runtime (MB) (MB)
	512	4s	92	4s	92	3
	1 024	11s	366	8s	95	7
	2 048	40s 1 412	28s	92	19
	4 096	na	na	2mn	94	69
	8 192	na	na	7mn	95	272

  Table1emphasizes the advantage of using a tiled topdown model: while a plain top-down extraction cannot handle 4 levels of 4 096 × 4 096 due to memory limitations, the tiled approach can process any large image with an almost constant amount of memory. As shown by the fourth column of Table

Table 2 :

 2 Runtime and memory usage for the extraction of tiled top-down pyramids from the images Histology and Lena scaled at different resolutions. The pyramids are composed of three levels, each one encoding a different resolution.

	image	resolutions tile extract	ram	disc
		(pixels) side runtime (MB) (MB)
	Lena	128/256/512 128	1.9s	95	2
	Lena	512/1 024/2 048 128	20.6s	101	11
	Lena	2 048/4 096/8 192 128 5mn20s	126	157
	Lena 8 192/16 384/32 768 128 1h48mn	119 2 491
	Hist.	625/2 500/10 000 400	44mn	86	274

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

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

The vertex removal operation on a dart d ensures that β1(β0(d)) ← β1(d) and β1(β0(β2(β1(d)))) ← β2(d). Then, it deletes d and β1(β2(d)).

Return res;

The model is implemented in C++ and computations are carried out on an Intel E5300@2GHz with 2GB RAM.

We use the tiles of the bigtiff library available at http://www.aperio.com/bigtiff to load only the subdivisions that are necessary to the topological tiles being processed.

Acknowledgments

A preliminary version of this article was presented at the 13th International Workshop on Combinatorial Image Analysis [GDB09].

This research is part of the FoGrImMi project, supported by the ANR foundation under grant ANR-06-MDCA-008-01/FOGRIMMI.

encoding tiles' geometrical borders are marked as real during the construction of a tiled level (Algorithm 6). Then, the merging criterion is applied on all the couples of regions separated by a tile's border (line 2 of Algorithm 2): if both regions should be merged, we mark the embedding of their shared border as fictive (line 3 and line 4). Note that the merging criterion must implicitly define a partition to ensure that no dangling edges are produced. For example, a quantization is a suitable criterion whereas a criterion based on the difference of average gray levels of the regions compared to a defined threshold is not.

A dart d is said to have a real embedding if its associated oriented segment encodes a non fictive border, the dart is called fictive otherwise. Using the oper-

As a result, we introduce the δ 2 operator as follows:

Proposition 1 (δ 2 involution). Let T be a set of connected topological tiles T = {t(i, j)} (i,j)∈{0,...,W }×{0,...,H} . Let D be the set of darts of T with a real embedding. δ 2 is an involution on D such as:

δ 1 permutation The operator δ 1 allows to traverse an edge that may be shared by several tiles. For example, in Figure 8(b), starting from dart 1, iterations of δ 1 operator should lead to the successive traversal of the darts 4, 5, 6 and 7. The idea is the following: given a dart d, let us consider that δ 1 (d) = β 1 (d) as long as β 1 (d) does not have a fictive embedding. In this last case, δ 1 (d) belongs to an adjacent tile so we skip fictive darts with the operation β 2 • β 1 until δ 1 (d) has a real embedding. This procedure leads to the following proposition: