Julien Bouchez

Olivier Beyssac

Valier Galy

Jérôme Gaillardet

Christian France- Lanord

Laurence Maurice

Patricia Moreira-Turcq

Oxidation of petrogenic organic carbon in the Amazon floodplain as a source of atmospheric CO 2

The two long-term sources of atmospheric carbon are CO 2 degassing from metamorphic and volcanic activity, and oxidation of organic carbon (OC) contained in sedimentary rocks, or petrogenic organic carbon (OC petro ). The latter flux is still poorly constrained. In this study, we report Particulate Organic Carbon (POC) content and 14 C-activity measurements in Amazon River sediments, which allow for estimates of the OC petro content of these sediments. A large

INTRODUCTION

CO 2 degassed from Earth's interior is partly scavenged by chemical reactions occurring during weathering of silicate rocks and subsequent carbonate precipitation in the ocean [START_REF] Garrels | Controls of atmospheric O 2 and CO 2past, present and future[END_REF]. It is also consumed by photosynthesis followed by burial of organic matter in marine sediments [START_REF] Hayes | The carbon cycle and associated redox processes through time[END_REF]. These two mechanisms have respectively built up the two major carbon reservoirs of Earth's surface: limestones (50 x 10 6 GtC), and 14 C-free organic matter disseminated in sedimentary rocks, or petrogenic OC (OC petro , 12.5 x 10 6 GtC; [START_REF] Berner | Atmospheric carbon dioxide levels over Phanerozoic time[END_REF]. The oxidation of petrogenic OC is a source of CO 2 to the atmosphere (Berner, 2004). However, quantifying the modern rates of OC petro oxidation remains a challenge for understanding and modeling the geological carbon and oxygen cycles. Although a few studies based on soil profiles have attempted to determine rates of OC petro oxidation (e.g., [START_REF] Keller | Soil respiration and georespiration distinguished by transport analyses of vadose CO 2 , 13 CO 2 and 14 CO 2[END_REF][START_REF] Keller | Soil respiration and georespiration distinguished by transport analyses of vadose CO 2 , 13 CO 2 and 14 CO 2[END_REF][START_REF] Petsch | A field study of chemical weathering of ancient sedimentary organic matter[END_REF], budgets of fossil organic carbon oxidation at river catchment scale have not received much attention (e.g., Galy et al., 2008b ;[START_REF] Hilton | Tropicalcyclone-driven erosion of the terrestrial biosphere from mountains[END_REF].

The dissolved and particulate load transported by rivers derive from chemical weathering of rocks and physical erosion of soils and rocks. This includes organic material, which consists in a mixture of recent biospheric carbon (OC recent ), and OC petro [START_REF] Blair | From bedrock to burial: the evolution of particulate organic carbon across coupled watershed-continental margin systems[END_REF][START_REF] Komada | Oceanic export of relict carbon by small mountainous rivers[END_REF][START_REF] Leithold | Geomorphic controls on the age of particulate organic carbon from small mountainous and upland rivers[END_REF]. The oxidation of OC transported in rivers is thought to mostly affect OC recent and to have no effect on the geological budget of atmospheric CO 2 . In their study on the Amazon river, [START_REF] Hedges | Carbon-14 in the Amazon River System: Science[END_REF] showed that the organic material transported by the Amazon river mostly consists in OC recent derived from the highly productive lowland ecosystems.

During fluvial transport, the oxidation of this dissolved and particulate organic matter results in the escape of ca. 500 MtC/yr to the atmosphere (Richey et al., 2002). Most of this oxidation derives from OC recent [START_REF] Mayorga | Young organic matter as a source of carbon dioxide outgassing from Amazonian rivers[END_REF] and has therefore no impact on the long-term regulation of atmospheric CO 2 . However, a significant fraction of particulate organic matter can be of petrogenic origin. Distinguishing between OC petro and OC recent in rivers is thus of prime importance because only the oxidation of OC petro represents an input of C to the active reservoirs at Earth's surface.

In this study, we report POC (Particulate Organic Carbon) and 14 C activity measurements in river sediments collected throughout the Amazon River system. Sediments were collected along river depth-profiles in order to capture the whole range of granulometric spectrum of erosion products. Concentrations of OC petro were measured in these sediments, and coupled with structural characterization of OC petro by Raman microspectroscopy. This allows us to estimate the first order of carbon input to the atmosphere by OC petro oxidation during transfer of sediments in the floodplains of the Amazon Basin, and gives a lower bound on the estimate of CO 2 release to the atmosphere by the oxidation of OC petro in the Amazon Basin.

SETTING, SAMPLING AND ANALYTICAL METHODS

The Amazon is the world largest river in terms of drainage area and water discharge to the ocean [START_REF] Meybeck | River discharges to the oceans: an assessment of suspended solids, major ions and nutrients[END_REF]. Isotopic studies (Allègre et al., 1996) have clearly shown that most of the Amazon River sediments are derived from the Andes. There, Amazon tributaries drain extensive outcrops of easily erodible sedimentary and meta-sedimentary rocks, such as black shales in the Bolivian Andes.

We sampled the two main tributaries of the Amazon, the Solimões and the Madeira rivers, at their mouth, as well as the Amazon mainstream at Obidos, in June 2005 and March 2006 (Fig. 1). The Beni River, which supplies most of the sediments to the Madeira River, has been sampled at the outlet of the Andes, near Rurrenabaque, where it enters the Madeira floodplain, in February 2001. At each location, river water was sampled at various river depths along vertical profiles, from channel surface to bottom, and filtered at 0.22 µm porosity; bed sediments were also dredged. Within the channel of large rivers, granulometric sorting induces important variations of chemical composition of river sediments from the surface to the bottom (Galy et al., 2008a). The sampling technique used here allows us to characterize the whole range of erosion products in terms of grain size distribution and mineralogy.

POC content was determined using a modified Eurovector EuroEA3028-HT elemental analyzer coupled to a GV Instruments IsoPrime continuous-flow isotope mass spectrometer at the CRPG, Vandoeuvre-lès-Nancy, France [START_REF] Galy | Determination of Total Organic Carbon content and 13 C in carbonate-rich detrital sediments: Geostandards and Geoanalytical Research[END_REF]. 14 C activity was determined by Accelerator Mass Spectrometry at LMC14 National Facility, Saclay, France, after off-line organic matter combustion and CO 2 cryogenic purification. Samples were decarbonated before combustion [START_REF] Galy | Determination of Total Organic Carbon content and 13 C in carbonate-rich detrital sediments: Geostandards and Geoanalytical Research[END_REF]. 14 C values are given after correction for 13 C fractionation (normalization to a  13 C of 25‰), and expressed as pMC (percentage of Modern Carbon) comparatively to 95% of the 14 C activity of the oxalic acid standard OXI. Petrogenic carbon was characterized by Raman microspectroscopy using a Renishaw InVia Raman micro-spectrometer at the Laboratoire de Géologie, Ecole Normale Supérieure, Paris, France (Bernard et al., 2008).

Raman spectra were obtained directly on raw sediments, and on thin sections for bedrocks.

RESULTS: 14 C AGE OF OC recent AND OC petro CONTENT

In depth-profile sediments, 14 C content shows a wide range of variation, between 37.5 and 86.2% pMC (Tab. 1). A first-order positive relation between pMC and POC is observed, the coarser bed sediments being the most depleted in both OC and 14 C.

In river sediments, OC can be interpreted as a binary mixture of OC petro and OC recent with distinct 14 C content (e.g., [START_REF] Blair | From bedrock to burial: the evolution of particulate organic carbon across coupled watershed-continental margin systems[END_REF]. Following the approach of Galy et al. (2008b) we plot our results in a diagram of POC * pMC (or Modern C) as a function of POC (Fig. 2). Depthprofiles from different sampling locations define linear trends, at 95% confidence level, regardless the sampling period. These correlation indicate that samples from a given depthprofile have rather constant absolute OC petro concentration and 14 C activity of the OC recent component (see appendix for details). The values of OC petro content in the samples and 14 C-age of the OC recent pool can be both determined from the slope and intercept of each line (Tab. 1).

Similar observations were made on the Ganga-Brahmaputra system (Galy et al., 2008b).

The highest OC petro content, 0.26% (±0.11%, 2 sigma uncertainty), is obtained for the Beni at Rurrenabaque. There, OC petro makes up to 50% of the POC, and likely originates from the large outcrops of black shales drained by this river. Lowland sampling locations (Solimões, Madeira and Amazon) all display lower OC petro content, between 0.02% and 0.06%, (or even lower, regarding the uncertainties reported in Tab. 1). Thus, there is a large apparent decrease in OC petro concentration between the entry and the outlet of the Madeira floodplain.

Since the Beni contributes to ca. 40% of the Madeira sedimentary budget [START_REF] Guyot | Dissolved solids and suspended sediment yields in the Rio Madeira basin, from the Bolivian Andes to the Amazon[END_REF], potential addition of supposedly OC petro -free sedimentary material by other tributaries of the Madeira River could only lead to an OC petro content decrease by a factor of slightly more than two. Hence, the apparent 10-fold decrease in OC petro content could mainly be due either to a preferential burial of OC petro -rich material in the floodplain, or to a loss by oxidation.

Burial of sedimentary material occurs in the Amazon basin between the Andean source of sediments and the Amazon mouth, in particular between Rurrenabaque and the mouth of the Madeira [START_REF] Guyot | Dissolved solids and suspended sediment yields in the Rio Madeira basin, from the Bolivian Andes to the Amazon[END_REF]. If sediment storage is the cause of the observed decrease of OC petro concentration reported here, it would imply the preferential sedimentation of an OC petro enriched component. As stated above, sampling along depth-profiles allows to take into account the whole range of riverine particulate matter in size distribution and mineralogy. Our results (Fig. 2) show that absolute OC petro content is the same along all depth-profiles, despite expected variations in particle size distribution with depth [START_REF] Curtis | Non-uniform vertical distribution of fine sediment in the Amazon River[END_REF]. Selective burial of a given size fraction should therefore not affect OC petro concentration of suspended sediments. This observation strongly suggests that the decrease of OC petro concentration along the course of the Madeira is due to OC petro oxidation.

ESTIMATE OF THE MAGNITUDE OF THE CO 2 SOURCE

Given the important amount of sediments transported in the Madeira floodplain [START_REF] Guyot | Dissolved solids and suspended sediment yields in the Rio Madeira basin, from the Bolivian Andes to the Amazon[END_REF], the oxidation flux resulting from the large decrease in OC petro content during the transfer of sediments in the floodplain should be significant. A first-order oxidation flux of OC petro can be estimated using previous works on sedimentary budgets in the Madeira River Basin. Among the 212 Mt/yr of sediments delivered by the Beni River to the plain, ca. one half is buried in the foreland basin [START_REF] Guyot | Dissolved solids and suspended sediment yields in the Rio Madeira basin, from the Bolivian Andes to the Amazon[END_REF]. The amount of Beni sediments actually transiting through the plain is thus on the order of 100 Mt/yr. Hence, given the OC petro concentration reported in this study, 100 Mt/yr of sediments represent a OC petro flux of 0.26 MtC/yr supplied to the plain and not buried. At the outlet, 100 Mt/yr of sediments represent a Publisher: GSA Journal: GEOL: Geology Article ID: G30608

Page 7 of 15 OC petro flux of 0.02 MtC/yr that exits the plain. The difference of ca. 0.25 MtC/yr is thus the oxidation flux of OC petro in the Madeira floodplain. This is a first order estimate but also a lower bound of the OC petro oxidation flux of the Madeira basin as we assumed that no OC petro is delivered to the Madeira floodplain by its two other main tributaries. In addition, this estimate does not take into account the oxidation of OC petro upstream Rurrenabaque and in Andean soils which we are not able to address here. Moreover, we assume that no oxidation affects the sediments buried in the foreland basin. The flux of 0.25 MtC/y is thus a minimum bound of the OC petro -derived CO 2 outgassing flux . This number is in the same order of magnitude as the net CO 2 sequestration flux in this basin associated to silicate weathering (0.8 MtC/yr; [START_REF] Gaillardet | Chemical and physical denudation in the Amazon River Basin[END_REF].

OC petro STRUCTURAL CHARACTERIZATION

OC petro is derived from organic carbon initially trapped in sediments and has been structurally and chemically transformed during diagenesis and metamorphism. Structural characterization of OC petro by Raman microspectroscopy has been performed both in riverine sediments and bedrock samples. Because volcanic rocks of the high cordillera may not contain any significant amount of solid OC, the main sources of OC petro are most likely the sediments, mainly black shales, drained by the Rio Beni. Three samples representative of the main bedrock lithologies from the Tipuani, Mapiri and Coroico basin have been investigated (Fig. 1). They contain two main OC petro fractions (Fig. 3): one is rather disordered, exhibiting Raman spectra typical of greenschist facies [START_REF] Beyssac | Raman spectra of carbonaceous material in metasediments: a new geothermometer[END_REF], in agreement with the thermal history of these rocks. The second is highly graphitic and supposedly represents a detrital pool. Both fractions are found in all riverine sediments either as isolated particles or as inclusions or aggregates within minerals (mostly quartz, phyllosilicates or plagioclases, Fig. 3). As shown in Fig. 3, the graphitic phases become dominant in samples of downstream sediment (Rio Beni and then Rio Madeira), while the disordered fraction progressively disappears. Graphite thus appears to be the most stable phase with respect to the oxidation process.

DISCUSSION AND CONCLUSION

This study thus shows that the oxidation of OC petro during fluvial transport is a significant flux for the long-term atmospheric CO 2 budget. Fluvial oxidation of OC petro may counteract the consumption flux of CO 2 by silicate weathering, which is conventionally thought to be the only significant process, with organic carbon sequestration, to control atmospheric CO 2 at geological timescales (Berner, 2004;Wallmann, 2001). The degradation of physically mobilized ancient organic matter in large fluvial systems is most probably dependent on a number of factors such as residence time of particles in floodplains [START_REF] Blair | The persistence of memory: the fate of ancient sedimentary organic carbon in a modern sedimentary system[END_REF], or on climatic conditions. This important oxidation flux found here is probably favored by the warm and oxidative conditions that prevail in the soils of Amazonian floodplains. Whether this oxidation of OC petro occurs via biotic (Petsch et al., 2001) or abiotic [START_REF] Chang | Coal weathering and the geochemical carbon cycle[END_REF] pathways, is beyond the scope of the paper but would need further investigations. Galy et al. (2008b) showed that 30%-50% of the OC petro present in the Himalayan source rocks were preserved and are still present in the marine sediments of the Bengal Fan. Our estimate of the OC petro preservation in the Madeira floodplain, 15%, is an upper bound of the extent of OC petro preservation in the Madeira basin, as it does not take into account the oxidation taking place in Andean soils, downstream the sampling locations, or even in the ocean, before or after deposition. The Amazon basin is hence a better incinerator of OC petro than the Himalayan system. This is likely due to differences in the sources of OC petro . Low-grade metamorphic rocks with disordered OC are common in the Andes, while high-grade metamorphic rocks generating highly graphitic OC are widespread in the Himalaya [START_REF] Beyssac | Thermal metamorphism in the Lesser Himalaya of Nepal determined from Raman spectroscopy of carbonaceous material[END_REF]. Disordered OC is more prone to oxidation than graphite because of its chemistry (aromatic skeleton with radicalization) and structure, as micro-and nano-porosity enhance oxidation rates.

Over geological timescale, geodynamic (metamorphic grade, erosion intensity…) settings probably control the extent of preservation of OC petro during the erosion-transport-sedimentation cycle. Over shorter timescale (tens to hundreds kyrs), and for a given geodynamic context, climate is likely to control the oxidation or preservation of OC petro , through erosion, temperature, and probably the nature of microbial communities (and their metabolic activity) present in the floodplain.

We speculate that, in response to an atmospheric CO 2 rise, increased global temperature would probably enhance oxidation of petrogenic OC in large river floodplains and associated CO 2 outgassing. This mechanism possibly constitutes a new positive feedback in the long-term carbon cycle.

ACKNOWLEDGMENTS

This study was funded by CNRS-INSU program Reliefs de la Terre, and realized in the frame of the HyBAm project (cooperation agreement with CNPq n° 492685/2004-5). We sincerely ackowledge the following Brazilian Institutions and Universities: ANA, UnB, UFF, CPRM. We thank C. Guilmette for technical assistance in the stable isotopes laboratory and R. Hilton for improving the quality of the text. This is IPGP contribution N°2564.

APPENDIX: OC petro AND 14 C AGE OF OC recent CALCULATION

We use a method described in Galy et al., 2008b. Briefly, we describe the OC pool as a binary mixture of OC petro , derived from the rocks, and OC recent derived from the biosphere (vegetation, soils and autotrophic production in the river). These two component have distinct 14 C activity, Publisher: GSA Journal: GEOL: Geology Article ID: G30608

Page 10 of 15 OC petro being 14 C-free (pMC petro = 0). For each sample, the absolute content of Modern C (POC x pMC -"Modern" refering here to a present 14 C standard) can thus be written as:

%Modern C = POC x pMC recent -%OC petro x pMC recent ,
where pMC recent is the 14 C activity of OC recent and %OC petro is the absolute content of OC petro . In a %Modern C vs. POC plot, samples having the same pMC recent and the same %OC petro define a single straight line. The pMC recent is given by the slope of the line and allows the calculation of the age of the recent component. Moreover, the absolute content of OC petro is given by the opposite of the intercept/slope ratio.

Despite the auto-correlated nature of the two plotted variables, and as shown in Tab. 1, the relationships we obtain are more significantly correlated than in the case of randomly distributed POC and pMC (either assuming an uniform or normal distribution, within boundaries defined by the ranges covered by the values measured in our samples).

Uncertainties on the determined slope and intercept (and thus on %OC petro and pMC recent ) are yielded by a full inversion method (Tarantola and Valette, 1982). Relatively low uncertainties on pMC recent (i.e. on the slope) stem from the good alignment of data points.

REFERENCES CITED

FIGURE CAPTIONS Figure 1 .

 CAPTIONS1 FIGURE CAPTIONS

Figure 2 .

 2 Figure 2. Modern C content (POC*pMC, expressed in weight % of the whole sample) vs. POC

Figure 3 .

 3 Figure 3. Representative Raman spectra of riverine and bedrock material, with the location of the

  Melack, J.M., Aufdenkampe, A.K., Ballester, V.M., and Hess, L.L., 2002, Outgassing from Amazonian rivers and wetlands as a large tropical source of atmospheric CO 2 : Nature, v. 416, p. 617-620, doi: 10.1038/416617a. Tarantola, A., and Valette, B., 1982, Generalized nonlinear inverse problems solved using the least squares criterion: Reviews of Geophysics and Space Physics, v. 20, no. 2, p. 219-232, doi: 10.1029/RG020i002p00219. Wallmann, K., 2001, Controls on the Cretaceous and Cenozoic evolution of seawater composition, atmospheric CO 2 and climate: Geochimica et Cosmochimica Acta, v. 65, p. 3005-3025, doi: 10.1016/S0016-7037(01)00638-X.

	microbial assimilation of ancient organic carbon during shale weathering: Science, v. 292,
	p. 1127-1131, doi: 10.1126/science.1058332.
	Richey, J.E.,
	Allègre, C.J., Dupré, B., Négrel, P., and Gaillardet, J., 1996, Sr-Nd-Pb isotope systematics in
	Amazon and Congo River systems: constraints about erosion processes: Chemical Geology,
	v. 131, p. 93-112, doi: 10.1016/0009-2541(96)00028-9.
	Bernard, S., Beyssac, O., and Benzerara, K., 2008, Raman mapping using advanced line-
	scanning systems: geological applications: Applied Spectroscopy, v. 62, p. 1180-1188.
	Berner, R.A., 2004, The Phanerozoic carbon cycle, Oxford University Press, 150 pp.


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

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

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

A top down construction scheme for irregular pyramids

Keywords: Segmentation, Irregular pyramid, Topological model, Combinatorial map

Hierarchical data structures such as irregular pyramids are used by many applications related to image processing and segmentation. The construction scheme of such pyramids is bottom-up. Such a scheme forbids the definition of a level according to more global information defined at upper levels in the hierarchy. Moreover, the base of the pyramid has to encode any single pixel of the initial image in order to allow the definition of regions of any shape at higher levels. This last constraint raises major issues of memory usage and processing costs when irregular pyramids are applied to large images. The objective of this paper is to define a top-down construction scheme for irregular pyramids. Each level of such a pyramid is encoded by a combinatorial map associated to an explicit encoding of the geometry and the inclusion relationships of the corresponding partition. The resulting structure is a stack of finer and finer partitions obtained by successive splitting operations and is called a top-down pyramid.

Introduction

Quadtrees [START_REF] Dyer | Region representation: Boundary codes from quadtrees[END_REF][START_REF] Jolion | A Pyramid Framework for Early Vision: Multiresolutional Computer Vision[END_REF] and regular pyramids [START_REF] Jolion | A Pyramid Framework for Early Vision: Multiresolutional Computer Vision[END_REF] belong to the first hierarchical data structures introduced within the computer vision framework. Both models are based on psycho-visual properties: focus of attention, for data structure based on recursive split such as quadtrees, and successive processings by neural layers, for bottom-up regular pyramids. Segmentation using quadtree data structures is based on a recursive subdivision of a basic shape (e.g. a square).

On the other hand, regular or matrix pyramids are defined as a stack of images with decreasing resolutions. An entity (square or pixel) defined at a given level of a pyramid is associated to a connected set of entities below, called a reduction window [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF]. Both encoding schemes induce several drawbacks on the segmentation process [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF].

The irregular pyramid framework introduced by Meer and Montanvert [START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF] partially solves these drawbacks: the stack of partitions is encoded as a stack of successively reduced graphs. Irregular pyramids [Mee89, MMR91, JM92, BK03] may only be built using a bottom-up construction scheme.

However, a bottom-up scheme requires an explicit encoding of the base level image in order to define regions with any shapes at higher levels. Moreover, in a bottom-up pyramid, each newly created region has no prior information about its parents (defined at a later stage). This last constraint prevents the management of the regions from depending on the properties of their parents in the pyramid.

The objective of this paper is the definition of a top-down hierarchical data structure by extending the model of two-dimensional topological maps. For many applications related to image segmentation, it is critical to minimize memory requirements, mainly for those processing large images. A top-down approach rules out the constraint of the explicit storage for the base: only split regions are kept in memory. Besides, it offers a perceptual advantage as major features of an image are discerned first in the pyramid, contrary to bottom-up models.

We first recall in Section 2, the basics of the different models used to define our top-down irregular pyramid framework. Then, Section 3 defines our model of topdown pyramid. We present in Section 4 its construction scheme. Section 5 details the basic operations used to build a new level of the pyramid. We finally provide, in Section 6, several experiments which allow to evaluate the computational times and memory requirements of our model.

Recalls

Combinatorial maps

A combinatorial map encodes all the subdivisions and incidence relationships of a topological space [START_REF] Lienhardt | Subdivision of n-dimensional spaces and n-dimensional generalized maps[END_REF]. In two dimensions, it is composed of vertices, edges and faces, respectively defined as cells of 0, 1 and 2 dimensions and noted i-cells. The border of an i-cell is a set of (j < i)-cells. Two i-cells are said incident if one belongs to the border of the second while they are said adjacent if they are both incident to the same (j < i)-cell. The degree of an i-cell is the number of adjacent (i + 1)-cells and a dangling edge is an edge incident to a degree 1 vertex. Adjacency relations are represented by operators noted β i and applied to darts, as we will call the abstract basic elements resulting from a complete decomposition of the image (Figure 1). 3. β 2 is an involution2 on D.

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; (a) (b) (c) (d)
Intuitively, a combinatorial map may be understood as a planar graph where relations on edges are explicitly defined by β i operators. Darts allow to differentiate the two extremities of an edge and thus, are assimilated to half-edges. Each dart belongs to a single vertex, edge and face of the map. The β 1 permutation links each dart of a face to the next dart encountered while turning clockwise around the face (Figure 1). The β 2 involution links each dart of an edge to the other dart of the edge which has an opposite orientation (shared edge between the square and the triangle in Figure 1). Two darts linked by β i are said i-sewn and two 2-sewn darts belong to two adjacent faces.

Topological maps

Because 2-maps can only represent the topology of connected objects, we introduce the notion of topological maps [START_REF] Brun | Incremental modifications on segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for twodimensional image representation: definition and optimal extraction algorithm[END_REF], an extension of combinatorial maps that uses three different models to encode: topological relations, geometrical information and inclusion relationships between regions.

Topology is based on a 2-map which is minimal according to its number of cells (Figure 3(a)). Although combinatorial maps only represent the topology of the space, geometric elements can be added easily. This association is called embedding. The geometry relies on the interpixel framework where an image is considered as a subdivision of a two-dimensional space in a set of 2-cells, 1-cells and 0-cells, respectively called pixels, linels, and pointels (Figure 2). Each border between two regions is thus defined as a set of linels. Since each dart corresponds to an oriented boundary, the embedding of a dart defines an order over the set of linels belonging to this border. The set of linels composing a dart can be represented explicitly as a sequence of linels or implicitly, using a two-dimensional matrix of the size of the image [BMD03, DBF04] (Figure 3

(b)).

A region is a set of darts delimited by a β 1 -loop. Each one has a representative dart which allows to retrieve a dart of a given region (e.g. used as a starting point to find the external border of the region). A set of adjacent regions is called a connected component and the union of all the regions create a topologically closed space since we represent the infinite region3 which encodes the background of the image. A region included into another one is called a hole and defines an internal border for the including region. An inclusion tree of regions represents the inclusion relationships of the structure: the father of any region within the tree is defined as the one which includes it in the image (Figure 3

(c)).

A topological map is a suitable model for image processing which has been proven complete (represents both topology and geometry), minimal (retiring any element would change the topology) and unique (two topologically equivalent partitions have the same map) [START_REF] Damiand | Topological model for twodimensional image representation: definition and optimal extraction algorithm[END_REF]. In practice, the minimality is required to decrease the number of cells and minimize memory usage and the completeness insures that we can encode partitions with regions of any geometry.

Pyramids

Simple graph pyramids, first introduced by Meer and Montanvert [START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF], then developed by Jolion [START_REF] Jolion | The adaptative pyramid: A framework for 2d image analysis[END_REF] are defined as a stack of simple graphs successively reduced. Within the segmentation framework, each graph of such a pyramid encodes a partition. Due to the limitation of the simple graph data structure, many issues are encountered when we have to update these graphs after splitting operations.

Combinatorial pyramids [START_REF] Brun | Combinatorial pyramids[END_REF] are built from an initial combinatorial map successively reduced by a sequence of contractions and removal operations. These operations are ruled by a contraction kernel (forest of the initial combinatorial map) and a removal kernel (forest of the dual combinatorial map). These structures are bottom-up and the initial combinatorial map (the base) is the most detailed level: the embedding of each dart of the base corresponds to a linel. Therefore, the receptive field of any dart may be retrieved from its receptive field and the embedding of the darts defined at the base [START_REF] Brun | Combinatorial pyramids[END_REF]. Besides, using forests avoids disjunctions of connected components when performing merging operations: two connected components are linked by a bridge if one is included into the other [START_REF] Brun | Contains and inside relationships within combinatorial pyramids[END_REF]. The model of bottom-up combinatorial pyramid has been generalized to encode all n-dimensional, orientable or not and with or without boundary subdivisions [START_REF] Lienhardt | Subdivision of n-dimensional spaces and n-dimensional generalized maps[END_REF][START_REF] Simon | nd generalized map pyramids: definition, representations and basic operations[END_REF].

Contrary to bottom-up methods, based on an explicit encoding of the base of the pyramid, a top-down approach allows to encode only the upper levels, resulting in a major memory reduction. Moreover, the focus of attention, encoded by the top-down scheme, can adapt the segmentation of each region according to the features of its parents (e.g. with medical images, the segmentation of cells in a tissue depends on the tissue itself).

Within a top-down scheme, we have to give up on bridges to represent inclusion relationships. Indeed, the management of the additional connections encoded by the bridges during splitting operations may induce cumbersome computations. For example, the insertion of an edge at the two endpoints of a bridge may create an artificial face which has to be detected and removed. This is why bridges are replaced by the use of inclusion tree of regions.

Moreover, since the top-down construction scheme avoids an explicit encoding of the base, the geometry of the pyramid's partitions cannot be implicitely encoded at the base level. The borders of the partition have thus to be explicitely encoded. These last arguments justify the use of topological maps as the basis of our top-down model.

Model for top-down pyramids

Each level of our top-down pyramid model is encoded by a topological map, defined by: a 2-map for the topology, an encoding for the geometrical embedding of darts and a tree of regions for inclusion relationships.

Definition 2 (Top-down topological pyramid). Let (n, m, k) ∈ N 3 . A top-down pyramid P is defined by P = {G k } where, ∀k, 0 ≤ k ≤ m: G 1 is deduced from G 0 by splitting region r 1 into two regions r 2 and r 3 .

1. G k = (D k , β k 1 , β k 2 ) is a topological map;
2. G k+1 is deduced from G k by performing splitting operations.

Since any level of the top-down pyramid results from splitting operations (2), every region of G k has a descendant in G k+1 and every region of G k has at most one antecedent in G k-1 (same for darts). Thus, the model is a causal structure [START_REF] Guigues | Scale-sets image analysis[END_REF] and defines a hierarchy of regions.

As a hierarchical data structure, the model has to represent objects and relations through the levels of the pyramid. So, each dart and region of a map G k is connected to its parent in G k-1 and its child in G k+1 (also called ascendant/descendant or up/down). Note that, although each element (dart or region) has a single descendant, there is no loss of information: we can retrieve for each element the corresponding set of elements in a lower level. Indeed, the set of children of a given element is connected so, up and down relations allow to start from a descendant and to find all the neighbors which have the same "up". Neither elements from the top level nor elements newly created on a level have an antecedent and elements belonging to the base do not have a descendant but several elements may have the same parent (Table 1).

D d up d down 1 - 4 2 - 5 3 1 - 4 1 - 5 2 - 6 - - 7 - - 8 2 - R r up r down 1 - 2 2 1 - 3 1 - (a) (b)
In the following, P denotes a top-down pyramid composed of m + 1 levels num-bered from 0 to m (m is called the depth of the pyramid). Globally, an exponent k refers to level k + 1 of the pyramid:

G k is the map of level k + 1, D k (resp. R k )
is the set of all darts (resp. regions) composing level k + 1. An edge may be noted (d, d ) where d and d are the 2-sewn darts which compose it and r k (d) denotes the region of dart d in level k.

Construction scheme

This section outlines the global operations constructing a pyramid. The construction is incremental: it starts from the top and adds new levels one by one at the bottom. It is composed of three main steps: the construction of the first (top) level, the creation of a new level by copying the bottom and the segmentation of the level that has just been added. Several methods can be considered to build the first level of a pyramid but only two are considered so far. The first method creates a map composed of a single region enclosing the image and the infinite region for the outside of the image. The second method extracts a first topological map from a segmentation of the image in few regions.

We create a new level by duplicating the last one of the pyramid. This is why, we build a map equivalent to the bottom (same topology, same geometry and same tree of regions), link corresponding elements between the two levels, and finally, add this map at the bottom of the pyramid (Algorithm 1 and Figure 5(b)).

Algorithm 1: Duplication of a level

Data: A pyramid P of depth m + 1. The last step of the construction process is the segmentation of the level that has just been duplicated. This segmentation is based on splitting and merging operations • line 1: All the edges belonging to the borders of r are split into one-linel long edges to allow further edge insertions;

• line 2: We create a list which initially contains all the darts resulting from the previous decomposition of external and internal borders of the region;

• line 3: We retrieve the geometry associated to the dart. As all edges have been split, the embedding of each dart of list is a single linel;

• line The external border of a region is clockwise oriented. Let us denote by l d and l ⊥ d , the oriented linels encoding respectively the embedding of the dart d and the next linel encountered after l d when turning counter-clockwise around the pointel associated to d (e.g. in Figure 6, l ⊥ 2 = l 1 ). Since the β 1 permutation connects two consecutive darts in a clockwise orientation around a face, only l ⊥ d needs to be considered at this stage. If other darts remain around the vertex incident to β 2 (d), they will be considered during further iterations.

• line 5: Actually, an edge insertion on a dart d consists in adding two one-linel long darts d i and d j (whose embedding is perpendicular to l d ) on the pointel p incident to d. Two configurations may happen as described in Figure 7;

• line 6: In order to sew the 2 darts of the dangling edge e = (d, β 2 (d)), we geometrically look for edges perpendicular to e as illustrated in Figure 8. This operation 1-sew the two darts according to its number (one or two) of perpendicular edges. At least one perpendicular edge exists (inserted during the previous iteration when processing β 2 (d)). If four edges are incident to p, processing e will sew two edges around p and the two others will be sewn in a further iteration (Figure 6).

This process ensures that each linel within the initial region is added. Moreover, no dangling edges remain: the initial region is initially minimal (i.e. without dangling edges) and if one is inserted, it is added to the list and then processed and correctly sewn. Consequently, the splitting operation produces a set of square-unit regions corresponding to the initial region.

Merging operation

Once the splitting process is done, we need to traverse all the created square-unit regions to segment the level according to our merging criterion. Actually, the merging operation is a global process which operates on a list of darts corresponding to the edges that were inserted by the splitting operation. This solution was selected for optimization matter as it avoids a complete traversal of all the regions. Each edge contained in this list is incident to a couple of adjacent regions (r, r ).

Two configurations may be encountered: simple or multi adjacency. In the first case, the edge is removed if the merging criterion is satisfied for (r, r ) (Figure 9(a)). In case of multi-adjacency, r and r share several edges. If the merging criterion determines that (r, r ) must be merged, all the shared edges have to be removed (Figure 9(b)). Algorithm 4 details the whole process:

• line 1: This list allows to traverse the regions created by the splitting operation instead of traversing the whole map. Note that we only need to store one dart d per edge (the second one is β 2 (d));

• line 2: The first condition aims to detect cases of multi-adjacency. The merging (d), the values of tr are respectively set to 80/40/20 and 100/40/10 for the levels G 1 /G 2 /G 3 of the images Lena and Boat. Our splitting and merging operations are independent of any specific criteria: more elaborated ones, using geometrical, colorimetric or topological features, may be designed without modifying our model. 2 gives the number of elements, the memory usage and processing times for each topological map composing the pyramid of the image Lena. The number of darts and regions strongly increases from a level to another as the merging threshold differentiates more regions. It directly impacts the memory size of the associated topological map. Indeed, the topology of a map requires most of the memory, except for low segmented maps where geometry could require more. The construction time of a level remains constant because, although more regions are split, they are smaller in number of pixels.

Conclusion

This paper defines a model of top-down hierarchical data structure based on topological maps. Topological maps are based on three models: a combinatorial map encoding multiple adjacency of regions, an explicit encoding of the geometry of the regions border and an encoding of the inclusion relationships. Such a model provides a complete description of a partition and is adapted to splitting operations. Our top-down pyramid is based on an initial topological map successively refined by splitting operations. This structure is particularly well suited for applications in segmentation that process large images: a top-down construction scheme allows to store, at each step of the algorithm, only the currently split regions and we avoid the storage of very fine partitions (first levels of bottom-up irregular pyramids). Besides, can use global properties of upper levels to refine the segmentation in lower levels and we retrieve the dual relation between quadtrees and matrix pyramids with top-down and bottom-up approaches.

In our future work, we plan to study different encoding of the geometry and of the inclusion relationships of topological maps. We also plan to use other splitting methods such as [START_REF] Brun | Incremental modifications on segmented image defined by discrete maps[END_REF] and to compare our results with results obtained from other kinds of pyramids. Finally, we should define segmentation operations which fully exploit the top-down structure of the pyramid.

Figure 1 :

 1 Figure 1: Construction of a 2-map by successive decompositions. (a) Original image; (b) Disconnected faces; (c) Disconnected edges; (d) 2-map: darts are the basic elements represented by arrows, β 1 relations are represented with arcs and β 2 with bold segments.

Figure 2 :

 2 Figure 2: Representation of the interpixel framework: an image is composed of pixels, linels and pointels.

Figure 3 :

 3 Figure 3: The three different models composing a topological map. (a) A 2-map representing the topology with darts and β i relationships; (b) A geometrical matrix that points out active linels and pointels; corresponding elements are linked together (for visibility reasons, dotted lines represent only up/down relations between regions); (c) A tree of regions for inclusion relations.

Figure 4 :

 4 Figure4: A top-down topological pyramid P , composed of two levels G 0 and G 1 . Numbers designate darts, β 1 relations are represented by arcs and β 2 by segments. G 1 is deduced from G 0 by splitting region r 1 into two regions r 2 and r 3 .

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: Main steps of the construction process of a top-down pyramid. (a) Initial step: the pyramid is composed of a single level G 0 ; (b) Duplicate and link: G 1 is a copy of G 0 and corresponding elements are linked together (for visibility reasons, dotted lines represent only up/down relations between regions); (c) Split: r 0 2 is split into a set of square-unit regions enclosing a single pixel; (d) Merge and simplify: some of the created regions are merged and draw r 1 2 and r 1 3 .

Figure 8

 8 Figure 8: 1-sewing operations when processing dangling edge (1, 2). (a) One perpendicular edge: 1-sew (1, 4) and (3, 2); (b) Two perpendicular edges: 1-sew (1, 4) and (5, 2).

Figure 9 :

 9 Figure 9: Configurations encountered during the merging operation between two adjacent regions. (a) Simple adjacency between (r 1 , r 3 ) and (r 2 , r 4 ): the corresponding edges (1, 2) and (3, 4) are removed if the merging criterion is verified; (b) Multiadjacency between (r 1 , r 2 ): if (1, 2) has been removed, (3, 4) is removed independently of the merging criterion.

Figure 10 :

 10 Figure 10: Visualization of the top-down construction process: first row is the original image followed by levels G 1 , G 2 and G 3 (G 0 is a single region). Segmentations are based on user-defined thresholds (a,d) or rely on the standard deviation of the parent region (b,c).

Table 1 :

 1 Parent/child relations in pyramid P from Figure 4. (a) Between darts; (b) Between regions.

  down in G m+1 ; set r up as parent of r down ; establish inclusions in G m+1 by setting the relations of r down like those of r up ; set G m as parent of G m+1 ;

Result: A pyramid P of depth m + 2. create a new void map G m+1 ; copy the geometry of G m into G m+1 ; foreach dart d up ∈ G m do create a new dart d down in G m+1 ; set d up as parent of d down ; sew (in G m+1 ) d down with the corresponding down darts of β 1 (d up ) and β 2 (d up ); foreach region r up ∈ G m do create a new region r

Table 2 :

 2 Statistics of the top-down construction from the image of Lena (512*512) in Figure 10, column (b).

		G 1	G 2	G 3
	darts	600 7 728 19 090
	regions	134 1 624 3 953
	total memory (KB) 306	808	1 604
	splitting (s)	2.23 1.42	1.29
	merging (s)	0.37 0.27	0.27
	total level construction (s)	3.11 2.05	1.94
	Table

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 .

For visibility reasons, the infinite region may not be represented in some figures.

mark(d);

Acknowledgements

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

that transform the level (Algorithm 2). Algorithm 2 is composed of five main steps:

• line 1: The splitting criterion indicates if a region has to be segmented. It is used upstream from the construction process as an optimization since it moves uninteresting areas further apart (notion of focus of attention [START_REF] Jolion | A Pyramid Framework for Early Vision: Multiresolutional Computer Vision[END_REF]); • line 2: This step decomposes region r into a set of square-unit regions, each one enclosing a single pixel (Figure 5(c)). This operation is detailed in Section 5.1; • line 3: The merging criterion determines if two adjacent regions should be merged. In order to preserve the causality property, we restrict the merging operation to new regions resulting from the split of a same region (Figure 5(d)). Therefore, two different regions of a level G p will never be merged in a level G q , p < q. This operation is detailed in Section 5.2; • line 4: The simplification step removes all remaining 2-degree vertices;

• line 5: Because new regions are created, the tree for inclusion relations has to be rebuilt. Indeed, it would be too expensive to keep it up-to-date as many regions are created from a level to another.

Steps line 4 and line 5 rely on the algorithms defined for topological maps [START_REF] Damiand | Topological model for twodimensional image representation: definition and optimal extraction algorithm[END_REF]. Figure 5 illustrates a simple example of the building process.

Basic operations

Splitting operation

As mentioned in Section 4, our splitting step decomposes a region into a set of basic regions, each one enclosing a single pixel. Later, a merging step will merge these regions: since any couple of adjacent regions may be merged, any subdivision of the initial region can be encoded. The operation insures that each created region is both topologically and geometrically correct (Figure 6).

Assuming that the region to split is denoted r, Algorithm 3 describes the splitting operation which may be divided into the following steps: • line 3: Let the geometry know that the linel is not active any more;

• line 4: This step updates the darts previously composing r(β 2 (d)) as now belonging to r(d);

• line 5: Removal of the two darts, according to the method in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF].

The only constraint applied to the splitting and merging operations is to preserve the causality of the structure: merging is thus restricted to the basic regions generated by the split of a same region. Therefore, within these regions, our merging operation is unrestricted and may group into a single region, any connected set of pixels. Any partition of the initial region may thus be encoded by our split and merge process. Contrary to quadtrees, our splitting operation is independent of any geometrical constraint.

Results and analysis

This top-down model has been implemented in C++ and results have been computed on a personal computer with a CPU AMDX2 3800+ (2GHz) and 1GB of RAM on a Linux system.

The splitting and merging criteria used to obtain the different segmentations in Figure 10 are defined as follow: let (r, r ) a couple of adjacent regions, M, m and A denoting the maximum, minimum and average gray level of r. The symbol tr denotes the threshold used by the merging criterion.

In columns (a) and (d) of Figure 10, the merging criterion is a comparison between the average gray levels of two adjacent regions: (r, r ) is merged if |A -A | < tr. In columns (b) and (c), tr is proportional to the standard deviation of the parent region of (r, r ): the more homogeneous a parent region is, the more our segmentation algorithm will search for fine details within its sons.

The splitting criterion avoids regions with less than ≤ 10 pixels and those which are going to be "completely" merged: r is split if M -m > tr. In columnms (a) and


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

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

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

Extraction of tiled top-down irregular pyramids from large images

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

Processing large images is a common issue in the computer vision framework with applications such as satellite or microscopic images. The major problem comes from the size of those images that prevents them from being loaded globally into memory. Moreover, such images contain different information at different levels of resolution. For example, global features, such as the delimitation of a tissue, appear at low resolution whereas finer details, such as cells, can only be distinguished at full resolution. Thus, the objective of this paper is the definition of a suitable hierarchical data structure that would provide full access to all the properties of the image by representing topological information. The idea consists in transposing the notion of tile for top-down topological pyramids to control accurately the amount of memory required by the construction of our model. As a result, this paper defines the topological model of tiled top-down pyramid and proposes a construction scheme that would not depend on the system memory limitations.

Introduction

The automatic or semi-automatic analysis of high resolution images such as whole slide microscopic images has to face at least two important challenges. Firstly, the size of these images is too important: most of the time, they cannot be stored globally into memory. This drawback induces a decomposition of global images into smaller ones called tiles. Secondly, because of the important amount of information present at full resolution, global structures of images only appear at low resolutions. These images naturally induce a mixed multi-resolution and hierarchical representation. An automatic analysis scheme of such images should thus incorporate these constraints.

The segmentation phase is the first abstraction step of an image analysis or interpretation algorithm. Usually, the data structures used for encoding partitions within a segmentation scheme do not provide a full access to all the properties of a partition. These properties include topological information such as the set of neighbors of a region, the set of regions inside a single region or the region containing a given region. The geometrical information includes the geometrical boundary of a region or the geometrical segment between two regions. Topological maps [START_REF] Brun | Incremental modifications on segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for twodimensional image representation: definition and optimal extraction algorithm[END_REF] have been designed to provide an efficient access to both geometrical and topological information while allowing modifications of the partitions through split and merge operations. However, these models only encode a single partition and thus, do not provide a hierarchy of partitions.

Quadtrees and regular pyramids are the first hierarchical structures used for hierarchical image segmentation. Both structures are based on psycho-visual properties. Quadtrees use the top-down notion of focus of attention: segmentation is performed by recursive splitting operations of a given geometrical shape. Regular pyramids use the bottom-up concept of reduction window [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF]: each pixel of a level corresponds to a larger set of pixels in the level below. However, both structures have several drawbacks [START_REF] Bister | A critical view of pyramid segmentation algorithms[END_REF] concerning their ability to encode connected regions of any size and shape and to provide an efficient access to the neighborhood of a region. The framework introduced by Meer and Montanvert [START_REF] Meer | Stochastic image pyramids[END_REF][START_REF] Montanvert | Hierarchical image analysis using irregular tessellations[END_REF] allows the definition of bottom-up [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] irregular pyramids which encode hierarchies of partitions made of connected regions. This pyramidal model provides an efficient access to the neighborhood of any region of the hierarchy. Finally, in order to access both geometrical and topological information, [START_REF] Brun | Combinatorial pyramids[END_REF][START_REF] Simon | nd generalized map pyramids: definition, representations and basic operations[END_REF] propose a model of irregular pyramids composed of combinatorial maps.

However, a bottom-up analysis scheme induces at least two problems when processing high resolution images. First, the encoding of the initial partition that corresponds to a very large image may require large amount of memory. This problem is accentuated by the computation of the remaining levels of the pyramid. Second, since these images encode different objects at different resolutions, a better analysis would consist in performing a top-down construction scheme of the pyramid where each region (defined at a given level of resolution) may influence the way its sons (defined at higher resolution) will be processed. Therefore, a top-down construction scheme of irregular pyramids based on topological maps have been defined in [START_REF] Goffe | A top-down construction scheme for irregular pyramids[END_REF]. Besides, even when using a top-down analysis scheme, the number of regions defined at a given level of the pyramid is only bounded by the size of the image encoding this level. Since this size may be large for high resolution images, we still have to face the issue of the important amount of memory required by irregular pyramids on high resolution images.

The objective of this paper is the definition of a tiled structure for top-down irregular pyramids. We recall in Sect. 2 the topological models used by our model of tiled top-down pyramid. Section 3 defines the notions of topological tile and tiled pyramid. We detail in Sect. 4 the construction scheme of such a pyramid. Finally, we present some experiments and comparisons in Sect. 5 that highlight involved memory requirements and computational times.

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 | Subdivision of n-dimensional spaces and n-dimensional generalized maps[END_REF]. A complete decomposition of an image results in a set of abstract basic elements that we call darts. We introduce two operators noted β i , i ∈ {1, 2} that apply on darts in order to represent adjacency relationships (Fig. 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 permutation1 on D;

3. β 2 is an involution2 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 the face to the next one encountered while turning in a clockwise orientation. The β 2 involution separates two adjacent regions: it links a dart to the other dart that belongs to the same edge but has an opposite orientation.

Topological Maps

Topological maps extend the model of combinatorial maps in order to provide a full representation for the partition of an image since a 2-map can only encode the topology of a connected set of objects. The definition of a topological map [START_REF] Brun | Incremental modifications on segmented image defined by discrete maps[END_REF][START_REF] Damiand | Topological model for twodimensional image representation: definition and optimal extraction algorithm[END_REF] proposes to combine three distinct models: a 2-map that encodes topological relationships, a matrix of interpixel elements encodes the geometry of the partition elements, and a tree of regions for inclusion relationships.

([Kov89, KKM90]) that (a) (b) (c) (d)
The combinatorial map encodes the topological relationships thanks to the β i operators and is minimal: the removal of any element would change the topology (Fig. 2(b)).

The geometrical matrix uses pointels, linels and pixels to represent the geometry of a partition. Associating a geometrical information to a topological element is called embedding: for example, the embedding of an edge is a sequence of linels (Fig. 2(c)). Pointels, linels and pixels are respectively referred to as i-cells (i ∈ {0, 1, 2}) and we call degree of an i-cell the number of (i + 1)-cells touching this cell.

The tree of regions describes inclusion relationships: a region will be the father of the regions it contains (Fig. 2(d)). The root of the tree is called the infinite region. It encodes the background of the image and allows to close the 2-map topologically. The model links darts and regions: 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.

Top-down Pyramids

In order to fit the hierarchical framework, the topological map model has been extended to top-down pyramids. Each level G k of a top-down pyramid is a topological map where each dart and region is connected to its parent in G k-1 and its first child in G k+1 . These links are called up/down relationships. The hierarchy is induced by sets of connected elements having the same parent.

The construction scheme of such a pyramid extracts a first level from a segmentation of the image in few regions (or even a single region). Then, it duplicates the bottom level, links the darts and regions between the two levels and finally, performs splitting operations based on segmentation criteria that transform the level (Fig. 3). The resolution of the image at level k +1 is always greater or equal to the one defined at level k.

If we consider the construction scheme of a top-down pyramid, its main drawback is that for each level, we have to load the whole image associated with this level and represent the whole topological map which encodes the partition defined at this level. Assuming that the image is small enough not to soak memory, the topological map of a level quickly becomes too large as its number of darts and regions increases.

Definition of a Tiled Top-down Pyramid Model

In order to define the notion of topological tile, we establish an analogy between the common notion of a tile in image processing: in both cases, a tile represents a regular and arbitrary subdivision of a set and reconstructing the whole initial set is obtained by the juxtaposition of all the tiles it has been split into. Therefore, we define a topological tile as a local topological map composed of a combinatorial map, a geometrical matrix associated with the subdivision and a tree of regions. The topological tile also disposes of additional information specific to the concept of tile.

Since a tile corresponds to an arbitrary subdivision of the image, its border may not mark any real frontier between image components and, in such a case, this border should be considered as fictive. Geometrically, two adjacent tiles share a same edge (Fig. 4(c)). Topologically, we define the β 2 operator on the darts that belongs to the border of a tile so that all the darts of the border of the tile know both their β 2 in the tile (those of the infinite region) and their β 2 in the adjacent tile (Fig. 4(d)). Now that the notion of topological tile has been introduced, we can define a hierarchical model based on those tiles, called a tiled top-down topological pyramid. Each level of the pyramid is a set of topological tiles that have the same depth. For each tile, the pyramid assigns a level and a location within the image which is defined at this level. The pyramid also makes the correspondence between the image and the topological maps, handles the fictive borders of the tiles and may swap or load the tiles between memory and disk.

Definition 2 (Tiled top-down topological pyramid). A tiled top-down pyramid P composed of l + 1 levels 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.

Several strategies can be considered for the subdivision in tiles such as a constant size of tiles (in pixels) or a constant number of tiles per level. We will arbitrary choose this last representation since it allows to validate the concept of tiled pyramids and suits the case when the image associated with each level has a constant resolution. The choice of a constant number of tiles per level with a regular subdivision does not impact the irregular pyramid framework of the model: within a tile, the construction scheme remains irregular.

The pyramid defines a hierarchy by introducing up/down relationships between the tiles, similar to the relationships defined on darts and regions by a top-down pyramid. Except for the tiles of top and bottom levels of the pyramid that will not have respectively any parent and any child, each tile knows its single parent (tile up) and its first child (tile down). Note that several tiles of the same level may have the same parent: since all the children of a given tile are adjacent, we can efficiently retrieve all the children of a tile starting from the tile down and finding all its neighbors that share the same tile up.

The interesting point in dividing the levels of the pyramid in tiles is that most of processings and algorithms require only a few tiles at the same time: we can store apart unused tiles 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 identify them in a file on disk.

We introduce the notion of local pyramid which is the set of tiles currently loaded in memory. Since modifications such as splitting or merging operations only apply on the local pyramid, its role is to keep the model coherent by spreading modifications to the other tiles. For example, if we split the border of a tile in memory, the local pyramid updates the adjacent tiles that are either on disk or in memory. Finally, when we load or swap a tile, the local pyramid updates the borders of its neighbors so that adjacent tiles are correctly connected.

Construction Scheme of a Tiled Pyramid

Connection of Adjacent Tiles

If we want a level of the pyramid to be topologically coherent, we have to connect adjacent tiles in order to find darts and regions that belong to several tiles. We will call basic dart a dart d whose edge embedding is a single linel. Algorithm 1 describes the operation and can be divided into the three main steps illustrated by Fig. 5. We will note s (resp. s ) 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 such as they are only composed of basic darts. This splitting operation ensures that s and s share the same number of darts (Fig. 5(a)). Second, we link t and t thanks to the β 2 operator by traversing simultaneously the darts of s and s (Fig. 5(b)). Finally, since the previous steps may have created degree 2 vertices, we have to perform a simplification pass in order to maintain the minimal property of the model. The idea is to process each vertex that belongs to the shared border (s, s ) of two adjacent tiles t and t , and remove it (according to the method in [START_REF] Damiand | Removal and contraction for n-dimensional generalized maps[END_REF]) if its embedding is a pointel whose degree equals two in both t and t (Fig. 5(c))3 .

Extraction Process

The global construction scheme of a tiled top-down pyramid starts with the creation of the first level G 0 . An arbitrary subdivision of the image defines the geometry of the tiles. Each tile of G 0 is composed of a single region that represents its associated • line 3: Creating t = t(i, j, k + 1) from t = t(i, j, k) is similar to adding a level in a top-down pyramid: we first create t as a copy of t , then we set up/down relationships between t and t and finally, we refine t with a split and merge technique [START_REF] Goffe | A top-down construction scheme for irregular pyramids[END_REF]. Note that since the segmentation aspect is not the objective of this paper, we use a criterion based on a basic comparison of average gray levels that was already defined for top-down pyramids. This results in a segmentation which is local to each tile.

• line 4: This step connects the left and top neighbors (t(i -1, j, k), t(i, j -1, k)) with t(i, j, k) according to the method detailed in Sect. 4.1.

• line 5: Since t(i, j, k) has been created, we can record it on disk. It is necessary to save the neighbors too because their borders have been updated in the previous step.

• line 6: An unloading operation removes the tile of the local pyramid.

Step 5 ensures that the information relative to the tile has been correctly recorded.

The operation frees memory so that the size of the local pyramid does not grow too much.

Experiments

We have implemented our model of tiled top-down pyramid in C++. Results have been computed on a personal computer with a CPU AMDX2 3800+ (2GHz) and 2GB of RAM on a Linux system. In order to compare results, all the pyramids have the same number of levels (G k , k ∈ {0, 1, 2, 3}) and each level has the same number of tiles (each tile has exactly one parent and one child). All the pyramids scalings of the image Lena. The second column gives computational times for the whole extraction of the pyramid. The third column is the real memory usage of the application. Fourth and fifth columns give the number of darts and regions for each level. We quickly show the limitations of the top-down model as it cannot process images larger than 2 048 × 2 048. Table 3 shows the advantage of using a tiled top-down model compared to the plain top-down extraction. The fourth column represents the size of the whole pyramid on disc (set of files that encode the tiles). We notice that the tiled approach allows to process any large image because we only need to refine the subdivision of the image (smaller tiles) to decrease the amount of required memory.

G 1 /G 2 /G 3 G 1 /G 2 /G 3 512
Table 4 shows the impact of the tiles size during the construction process of a tiled top-down pyramid associated with the image Lena. It provides memory usage and computational time for four different subdivisions. We can note two interesting points in this experiment. First, the amount of memory required by the local pyramid decreases with smaller tiles. Second, a too fine subdivision increases the computational time of construction and the global amount of memory space. This comes from the additional information required by each tile (labels, up/down relationships, β 2 operators), from the repeated calls of algorithms that connect the tiles and from the increasing number of swapping on disk operations. Therefore, in order to obtain the best extraction time for a given amount of available memory, the size of the tiles should be enlarged as long as the size of the local pyramid does not exceed this amount.

Figure 6 illustrates the tiled construction of a top-down pyramid with a basic segmentation criterion. We can notice that the segmentation may vary although the criterion is the same. Indeed, the split and merge operation that refines a tile is local to this tile and thus, depends on the initial subdivision. Note that fictive borders are represented to illustrate the delimitations of the tiled subdivision. The subdivision has been arbitrary chosen regular (for simplicity and homogeneity between results) but the model is an irregular pyramid since for any tile t(i, j, k + 1) of a tiled topdown pyramid P , the top-down pyramid P = {G 0 = t(i, j, k), G 1 = t(i, j, k + 1)} is irregular.

Figure 7 illustrates the tiled construction of a top-down pyramid associated with a multi-resolution image. Indeed, our model easily adapts to multi-resolution images by associating each level of the pyramid to a level of the image. In this example, we use the same number of tiles for each level: we just need to expand the geometrical matrix to make the correspondence between a tile t(i, j, k) and its descendant t(i, j, k + 1).

Conclusion

In this paper, we have defined a topological model of tiled top-down pyramid. Topdown pyramids are composed of an initial topological map successively refined by splitting operations. The main advantage in extending this model in a tiled structure is to process large images while controlling the memory requirements of the model. Thus, each level of the pyramid is decomposed into a set of topological tiles. A topological tile derives from a topological map and adds complementary information for hierarchical representation between tiles, connecting the border of adjacent neighbors and recording the tile on disk.

We have proposed an algorithm for an incremental construction of a tiled topdown pyramid that ensures that a maximum of four tiles is necessary in the local pyramid (the part of the pyramid that is loaded in memory). Therefore, our experiments have confirmed that we can process any image as long as the size of the local pyramid fits the available memory in the system.

In our future work, we plan to improve the performance of the model with different splitting techniques and multi-threading support. Indeed, the actual model is fast enough for common images but still too slow for very large images although it has shown that the process was viable regarding memory usage. We also intend to compare different strategies of tiled subdivisions in order to improve the association of the pyramid with multi-resolution images. Finally, we will focus on the segmentation aspect in order to define global operations that would not be affected by the local nature of the tiles and would exploit the tiled top-down data structure. This would lead to a structure of tiled top-down irregular pyramid where the irregular aspect is not confined within the tiles.

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: Combinatorial maps: construction by successive decompositions. (a) Original image; (b) Combinatorial map for topology: the image contains four regions r i , i ∈ {1, 2, 3, 4}; (c) Interpixel matrix for geometry: pointels and linels are represented by bold circles and segments and correspond to the embedding of the darts; (d) Tree of regions for inclusion relationships: r 1 contains r 2 , r 3 and r 4 . r 2 and r 3 are adjacent.

Figure 3 :

 3 Figure 3: Representation of a top-down pyramid composed of two levels G k and G k+1 . (a) Original image; (b) 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 k 1 . The splitting operation on G k+1 allows to differentiate the two regions r k+1 2

Figure 4 :

 4 Figure 4: 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 5 :

 5 Figure 5: 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 6 :

 6 Figure 6: Each row represents the levels G 1 , G 2 and G 3 of a tiled top-down pyramid associated with the image Lena. First row uses a subdivision of 64 tiles/level, second row has a subdivision of 4 tiles/level.

Figure 7 :

 7 Figure 7: Extraction of a tiled top-down pyramid from a multi-resolution image based on the image Cameraman. First row displays the resolutions of the original image (16 × 16, 32 × 32, 64 × 64, 128 × 128, 256 × 256). Second row presents the levels G 1 to G 5 of the tiled top-down pyramid (subdivision of 16 tiles/level).

Table 2 :

 2 Extraction of top-down pyramids without tiled subdivision for different scalings of the image Lena. Each level is composed of a single tile.

	image side extraction	ram	darts	regions
	(pixels)	time (s)	(MB)

Table 3 :

 3 Extraction of tiled top-down pyramids from large images based on different scalings of the image Lena. The subdivision in tiles allows to overcome the memory limitations of the system.

			3.7	92.2	70/2 084/47 268	19/460/10 056
		1 024	14.8	366.6	74/1 938/47 242	19/428/10 057
		2 048	58.2 1 412.3	80/2 010/47 098	20/444/10 027
		4 096			na
	image tiles per extraction	ram	disc		darts	regions
	side (px)	level	time (MB) (MB)		G 1 /G 2 /G 3	G 1 /G 2 /G 3
	512	1	5 s	92	7	1 212/5 458/54 222	216/989/10 796
	2 048	16	53 s	95	20	486/4 332/51 460	77/832/10 494
	8 192	256	14 mn	95	272	3 382/9 968/66 764	663/1 757/12 498
	32 768	4 096 6 h 38 mn	111 4 315	35 936/48 280/128 858	8 537/10 228/23 309

Table 4 :

 4 Comparison of computational times and memory usages according to the size of the tiles for a tiled top-down pyramid associated to the image Lena (1024 × 1024).

	tile side tiles per extraction	ram	disc
	(pixels)	level	time (s) (MB) (MB)
	1 024	1	15.0 366.7	6.8
	512	4	14.1	93.4	7.0
	256	16	14.2	24.6	7.9
	64	256	17.3	2.8	22.0

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)).

Acknowledgements

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

subdivision. Then, the creation of a new level only requires a local pyramid composed of four Indeed, we use an incremental algorithm scanning the subdivisions line by line, starting from the top-left subdivision. A tile t(i, j, k + 1) is defined from t(i, j, k) by performing splitting operations. So, we need in memory the tile up t(i, j, k) and the left and top neighbors (t(i -1, j, k + 1), t(i, j -1, k + 1)) to connect the left and top borders of t(i, j, k + 1). The right and bottom borders of t(i, j, k + 1) will be connected when processing respectively t(i + 1, j, k + 1) and t(i, j + 1, k + 1). Note that if t(i -1, j, k + 1) or t(i, j -1, k + 1) are not defined, (i = 0 or j = 0), the tile t(i, j, k + 1) belongs to the border of the image and does not need to be connected with neighbors. Finally, even in the case when those four tiles are still too large for the memory limitations of the system, we can simply adjust the initial subdivision by reducing the dimensions of the tiles to ensure the feasibility of the process. Algorithm 2 describes the main steps of the extraction of a tiled level.

• line 1: Saving a tile records its map, geometry and tree of regions on disk. We have to traverse all darts and regions and save all their connections, geometry and up/down relationships.

• line 2: The loading operation of a tile t reads the corresponding file on disk and constructs a new tile before adding it to the pyramid. We first create darts and regions instances in the topological map before filling their properties from reading the corresponding files. Indeed, the operation cannot be performed in a single pass because darts and regions are linked together (a region has a representative dart, a dart knows its region). A region must have been created before it is assigned to a dart and vice versa. are composed of four levels which are created with the same splitting method defined in [GBD09]: a basic segmentation criterion merges adjacent regions if the difference of their average grey values is below the thresholds defined as 25/15/5 for levels G 1 /G 2 /G 3 . The subdivision of the levels in tiles is regular and tiles and images are squared.

The maximum size of a tile is reached when each pixel corresponds to a different region. In this case, the size of the topology can be estimated by: 4 × sizeof (dart) × pixels + sizeof (region) × pixels. Table 1 presents the required memory for different sizes in our model (sizeof (dart) = 60 bytes and sizeof (region) = 80 bytes). In practice, the values obtained in our experiments are quite similar because the splitting method bursts regions and produces one single region per pixel before the merging step. Thus, in order to process large images, we choose a fine enough subdivision with tiles smaller than 1 024 × 1 024. Note that the real amount of memory which is necessary may be more important as we need to store the geometry and the image. Since we can not load the full image in memory, we use the tiled subdivision of the libtiff library in order to load only the subdivisions that are necessary to the tiles being processed.

Table 2 gives the computational times and memory usages of top-down pyramids that do not take advantage of tiled subdivision. Indeed, each level is composed of a single tile of the size of the image. The results are computed for successive