Cyprien Mauroy

Clément Levard

Céline Moreau

Vladimir Vidal

Jérôme Rose

Bernard Cathala

† Cerege

Elaboration of Cellulose Nanocrystal/Ge-Imogolite Nanotube Multilayered Thin Films

Keywords: nanomaterial, cellulose nanocrystal, nanotube, imogolite, thin film, layer-by-layer

Multilayered thin films combining two oppositely charged nanoparticles (NPs), i.e. cellulose nanocrystals (CNC) and Ge-imogolites have been successfully obtained by the layer-by-layer (LbL) method. CNC/Ge-imogolite (NP/NP) film growth patterns were studied by comparing growth mode of the all nanoparticles thin films to those of films composed of CNC or Geimogolites combined with polyelectrolytes (PE), i.e. cationic poly(allylamine) hydrochloride (PAH) and anionic poly-4-styrene sulfonate (PSS) (NP/PE films). NP/NP and NP/PE films growth patterns were found to be different. In order to get a deeper understanding of the growth mode of NP/NP, impact of different parameters such as imogolites aspect ratio, adsorption time, ionic strength, repeated immersion/drying were evaluated and influence of the drying step is emphasized. The aspect ratio of imogolites was identified as an important feature for the films

architecture. The short Ge-imogolites form denser films since the surface packing was more efficient.

INTRODUCTION.

For many years, the use and production of materials made from renewable and sustainable resources has been greatly increasing due to environmental concerns. Among the strategy reported in literature, the elaboration of greener materials with enhanced properties has attracted attention. Especially the combination of renewable materials such as nanocellulose based materials and clays have been proven to be extremely promising to promote efficient and sustainable materials that present for instance efficient mechanical properties or excellent gas barrier properties. [START_REF] Wu | Ultrastrong and High Gas-Barrier Nanocellulose/Clay-Layered Composites[END_REF][START_REF] Aulin | High strength, flexible and transparent nanofibrillated cellulose-nanoclay biohybrid films with tunable oxygen and water vapor permeability[END_REF][START_REF] Svagan | Biomimetic foams of high mechanical performance based on nanostructured cell walls reinforced by native cellulose nanofibrils[END_REF] Cellulose, because of its wide availability, amazing physical-chemical properties, low toxicity, renewability and biocompatibility has been the focus of tremendous interest. Within plants, cellulose is made up of fibrillated structures consisting of crystalline parts and less organized (amorphous) regions linked together and arranged periodically along the microfibrils. [START_REF] Rowland | The nature of accessible surfaces in the microstructure of cotton cellulose[END_REF] In the 1990s, extracting cellulose at the nanoscale became a relevant and innovative strategy to develop materials for a large scope of applications. [START_REF] Klemm | Nanocelluloses: A New Family of Nature-Based Materials[END_REF][START_REF] Siqueira | Cellulosic Bionanocomposites: A Review of Preparation, Properties and Applications[END_REF][START_REF] Lavoine | Microfibrillated cellulose -Its barrier properties and applications in cellulosic materials: A review[END_REF] Two major families of nanocelluloses are currently extracted from plant cell walls at the industrial scale. Nanocellulose could be obtained as nanofibers, or so-called cellulose nanofibrils (CNF), when wood pulp is mechanically delaminated. [START_REF] Nechyporchuk | Production of cellulose nanofibrils: A review of recent advances[END_REF] The second type of nanoparticles are obtained when the amorphous domains of cellulose are hydrolyzed, keeping the crystalline regions intact, so as to isolate the stiff rod-like nanocrystals, or so-called cellulose nanocrystals (CNC). [START_REF] Habibi | Cellulose Nanocrystals: Chemistry, Self-Assembly, and Applications[END_REF] CNC were widely used as building blocks to design new nanocomposite materials as filler to increase mechanical properties, or as elementary components for multilayer thin films assembled using the layer-bylayer (LbL) method. Initially described by Iler, [START_REF] Iler | Multilayers of colloidal particles[END_REF] and developed for polyelectrolytes assembly by Decher,[START_REF] Decher | Fuzzy nanoassemblies: Toward layered polymeric multicomposites[END_REF] this method consisted of alternate coatings on a substrate, of opposite charged components. LbL has mostly been reported in the case of polymers, but multilayer thin film development was extended to nanoparticles such as nanocellulose (i.e. nanofibril and nanocrystal). 12, 13, 14 15 Nanocellulose based LbL assemblies involve the use of polymers with attractive properties, e.g. cationic polyelectrolytes, [START_REF] Cranston | Morphological and Optical Characterization of Polyelectrolyte Multilayers Incorporating Nanocrystalline Cellulose[END_REF][START_REF] Wagberg | The Build-Up of Polyelectrolyte Multilayers of Microfibrillated Cellulose and Cationic Polyelectrolytes[END_REF][START_REF] Podsiadlo | Layer-by-layer assembled films of cellulose nanowires with antireflective properties[END_REF][START_REF] Podsiadlo | Molecularly engineered nanocomposites: Layer-by-layer assembly of cellulose nanocrystals[END_REF] or xyloglucan. [START_REF] Cerclier | Coloured Semi-reflective Thin Films for Biomass-hydrolyzing Enzyme Detection[END_REF][START_REF] Jean | Non-Electrostatic Building of Biomimetic Cellulose-Xyloglucan Multilayers[END_REF][START_REF] Cerclier | Elaboration of Spin-Coated Cellulose-Xyloglucan Multilayered Thin Films[END_REF] But nanocellulose-based LbL assemblies have seldom been described. For instance CNC have been combined with chitin nanocrystals or cationized cellulose nanofibrils and more recently with gibbsite nanoplatelet as cationic nanoparticles. [START_REF] Olszewska | All-cellulose multilayers: long nanofibrils assembled with short nanocrystals[END_REF][START_REF] Qi | Multifunctional Coating Films by Layer-by-Layer Deposition of Cellulose and Chitin Nanofibrils[END_REF][START_REF] Martin | Structural Variations in Hybrid All-Nanoparticle Gibbsite Nanoplatelet/Cellulose Nanocrystal Multilayered Films[END_REF] Such elaboration of all nanoparticle allowed porosity generation, leading to surface modifications, or refractive index modulation. [START_REF] Qi | Multifunctional Coating Films by Layer-by-Layer Deposition of Cellulose and Chitin Nanofibrils[END_REF][START_REF] Martin | Structural Variations in Hybrid All-Nanoparticle Gibbsite Nanoplatelet/Cellulose Nanocrystal Multilayered Films[END_REF] . In this study, multilayer coatings were investigated for the association of two oppositely charged anisotropic nanostructures by dipping, i.e. anionic CNC and Ge-imogolite nanotubes.

Imogolite is a natural aluminosilicate occurring as a nanotube of 2.0 nm diameter and around 100 nm in length. [START_REF] Levard | Synthesis of Imogolite Fibers from Decimolar Concentration at Low Temperature and Ambient Pressure: A Promising Route for Inexpensive Nanotubes[END_REF] The imogolite structure has been described as aluminum octahedra arranged in a gibbsite layer (dioctahedral aluminum layer) on the outer surface, and silicon tetrahedrons linked to aluminum layer vacancies on the inner surface. [START_REF] Cradwick | Imogolite, a hydrated aluminum silicate of tubular structure[END_REF] Although the incorporation of imogolite in thin film has seldom been described in the literature, [START_REF] Jiravanichanun | Preparation of hybrid films of aluminosilicate nanofiber and conjugated polymer[END_REF][START_REF] Jiravanichanun | Fabrication of conjugated polymer hybrid thin films with radially oriented aluminosilicate nanofibers by spin-assembly[END_REF] the incorporation of these anisotropic particles in LbL assemblies offered new potential functionalities due to their unique physical properties (high aspect ratio, rigid rod-like nanoparticles) through an understanding of the influence of processing parameter control of the final architecture. Imogolites exist also as synthetic analogue in which silicon was replaced by germanium (Ge-imogolite). [START_REF] Wada | Effects of substitution of germanium for silicon in imogoloite[END_REF] Natural imogolites display low toxicity [START_REF] Rotoli | Imogolite: An Aluminosilicate Nanotube Endowed with Low Cytotoxicity and Genotoxicity[END_REF] while toxicity of Ge-imogolite has been shown to vary as a function of structural properties such as length. In particular genotoxicity was observed for very short DW nanotubes and precursors (particle length < 10 nm) while longer DW Ge-imogolite nanotubes were shown to be non cytotoxic and exhibit a low genotoxicity. [START_REF] Liu | Influence of the Length of Imogolite-Like Nanotubes on Their Cytotoxicity and Genotoxicity toward Human Dermal Cells[END_REF] Nevertheless, this substitution enables modulation of the nanotube diameter [START_REF] Maillet | Growth kinetic of single and double-walled aluminogermanate imogolite-like nanotubes: an experimental and modeling approach[END_REF] and length . [START_REF] Avellan | Accelerated microwave assisted synthesis of alumino-germanate imogolite nanotubes[END_REF][START_REF] Amara | Single-step formation of micron long (OH)(3)Al2O3Ge(OH) imogolite-like nanotubes[END_REF] In our study, we take advantage of these morphological variations to investigated how the assemblage of these two rigid nanoparticles with varying aspect ratios (for Ge-imogolite) affects film growth compared to the growth of more conventional polymer/nanoparticle multilayered thin films. In particular, varying deposition conditions were explored to gain further insight into the mechanisms involved in CNC/Ge-imogolite interactions and subsequent film growth. For comparison, reference films were also formed by the combination of each nanoparticle with polyelectrolytes of opposite charge in the pH conditions of the solutions, i.e. poly(allylamine) hydrochloride (PAH) and poly-4-styrene sulfonate (PSS) for CNC and imogolite, respectively. EXPERIMENTAL SECTION Materials PAH (poly(allylamine) hydrochloride, Mw = 120-200 000 g.mol -1 ), PSS (poly-4-styrene sulfonate, 1 000 000 g.mol -1 ), aluminium perchlorate nonahydrate (Al(ClO 4 ) 3 .9H 2 O, 98%), TEOG (germanium IV ethoxide, ≥99.95%), sodium hydroxide (≥97%), urea (≥99.5%), sulfuric acid (95.0-98.0%), and hydrogen peroxide (≥30%) were purchased from Sigma-Aldrich.

Ultrapure water (18.2 MΩ, Millipore Milli-Q purification system) was used for all experiments.

Ge-imogolite synthesis

To synthetize short/long Ge-imogolites, TEOG was added to a 0.5/0.2 mol.L -1 aluminum perchlorate solution with an initial Al/Ge molar ratio of 2. [START_REF] Amara | Single-step formation of micron long (OH)(3)Al2O3Ge(OH) imogolite-like nanotubes[END_REF][START_REF] Levard | Synthesis of large quantities of single-walled aluminogermanate nanotube[END_REF] To synthetize short Geimogolites, the mixture was slowly hydrolyzed with a 0.5 mol.L -1 sodium hydroxide solution at a flow rate of 1 mL.min -1 delivered by a peristaltic pump. The OH -/Al hydrolysis molar ratio was 2. After the hydrolysis step, the mixture was heated in an oven at 95°C for 10 days. To synthesize long Ge-imogolite, urea was added with a urea/Al hydrolysis ratio of 1 (thermal decomposition of urea releases 2 OH -). The mixture was heated at 140°C in an autoclave for 4 days. Finally, the suspensions were dialyzed against ultrapure water using a 10 kDa dialysis membrane until the conductivity reached less than 3 µS. Final suspensions were approximately 14 g.L -1 and 12 g.L -1 for long and short Ge-imogolites, respectively (obtained after freeze-drying 5 mL of the solution and weighing the dried Ge-imogolite powder). ICP-AES measurements gave a final Al/Ge molar ratio of 1.77±0.03 and 1.67±0.04 for long and short Ge-imogolites, respectively. FTIR spectra of imogolites are displayed in Figure SI4.

CNC preparation

Cotton linters were hydrolyzed with sulfuric acid H 2 SO 4 (64% wt) at 65°C for 35 min. [START_REF] Revol | Helicoidal Self-Ordering of Cellulose Microfibrils in Aqueous Suspension[END_REF] When the reaction was finished, ice-cold water was immediately added to the mixture until a temperature of 10°C is reached to stop the hydrolysis. The suspension is then centrifuged repeatedly at 10 000 g for 30 min and washed with water. The suspension was purified against ultrapure water using a 30 kDa dialysis membrane to remove the residual acid. The suspension was sonicated for 4 min before ion exchange resin (Sigma TMD-8) was added to the suspension under stirring for 48 h. The final suspension was obtained at 20 g.L -1 , and the sulfate charge density of the final suspension was 0.3 e.nm -2 , as measured by conductimetric titration. CNC are negatively charged thanks to ester-sulfate groups formed during acid hydrolysis. FTIR spectra of CNC is displayed in Figure SI4.

LbL assembly

Multilayered thin films were coated on silicon wafers as solid substrate, previously cleaned for 30 min in a piranha bath (H 2 SO 4 /H 2 O 2 (7/3, v/v)), rinsed with ultrapure water, and finally dried under a nitrogen stream. PE+NP thin films were prepared using the conventional LbL dipping method. Typically, silicon wafers were alternately immersed in the respective cationic PAH solution (4 g.L -1 , containing 1 M NaCl) or Ge-imogolite suspension (12-14 g.L -1 ) for 5/1 min, with anionic CNC suspension (20 g.L -1 ) or PSS solution (4 g.L -1 ) for 1/5 min, respectively. After each immersion step, coated substrates were rinsed in ultrapure water (three baths) and dried under a nitrogen stream. The operation was repeated by alternating coatings of negative and positive layers to build (PAH/CNC) n , and (Ge-imogolite/PSS) n thin films, with n referring to the number of bilayers. Similarly, NP/NP (Ge-imogolite/CNC) thin films were built by alternate immersions in anionic CNC suspension and positively charged Ge-imogolite suspension.

Electrophoretic mobility measurement

Electrophoretic mobility values were obtained with a zetasizer Nano ZS (MALVERN). Briefly, Ge-imogolite and CNCs suspensions were introduced into the measurement cell without preliminary dilution. Calibration using standard silica particles was performed prior to analysis.

Atomic force microscopy

The topography of the multilayer thin films was characterized by AFM using a Bruker INNOVA device. The properties of probes used are given below: silicon nitride, 2 nm diameter, spring constant k=0.35 N.m-1, frequency f 0 =65 kHz. The AFM tip had a nominal tip radius of 2nm and a resonant frequency of 125 kHz (supplier specifications, MSNL-10, Bruker). Surfaces of thin films on silicon wafers were imaged using the tapping mode in air, and analyzed with WsXM 5.0 software. Ge-imogolites were also imaged on freshly cleaved mica sheets, and individual CNC on PAH-coated silicon wafers.

Scanning electron microscopy.

Non-metallized thin film analyses were performed with an SEM Zeiss GeminiSEM 500 ultrahigh resolution FESEM at 1 kV. In-lens secondary electron detection was used for imaging. At 1 kV, the resolution was 1.1 nm.

Ellipsometry

Film thicknesses were estimated using a spectroscopic ellipsometer M-2000U (J.A.Woollam, Lincoln, NE). The ellipsometric angles Δ and Ψ were obtained over a wavelength ranging from 400 nm to 800 nm at three different angles of incidence: 65°, 70°, and 75°. Data processing was performed using CompleteEASE software (J.A.Woollam Co., Inc.). The fit model used was composed of three layers: silicon substrate, a SiO 2 layer, and the film as a Cauchy layer. All thicknesses given in this study are the average of eight measurements performed at different places on each film.

RESULTS AND DISCUSSION

Nanoparticle characterization

An AFM image (Figure 1A) showed short Ge-imogolite average dimensions of 35±10 nm in length and 4.1±0.3 nm in diameter (Figure SI1A-SI2A-SI3), corresponding to an aspect ratio of 8.5. The average length was similar to that noted in an Avellan et al. study. [START_REF] Avellan | Accelerated microwave assisted synthesis of alumino-germanate imogolite nanotubes[END_REF] The average diameter was found to be in accordance with the results described by Maillet et al., and it corresponded to a double-walled structure. [START_REF] Maillet | Growth kinetic of single and double-walled aluminogermanate imogolite-like nanotubes: an experimental and modeling approach[END_REF] Long Ge-imogolites (Figure 1B) displayed average dimensions of 85 ±45 nm in length and 4.6±0.4 nm in diameter, corresponding to an aspect ratio of 18.5 (Figure S1B-S2B). These dimensions are in good agreement with those obtained by Amara et al. [START_REF] Amara | Single-step formation of micron long (OH)(3)Al2O3Ge(OH) imogolite-like nanotubes[END_REF] and confirmed an increase in length in comparison with working conditions previously given. Here, around 58% of the Ge-imogolites were below or equal to 100 nm in length, and 42% of them were longer (Figure S1B). Final pH suspensions were found to be 6.5 and 6.8, with a electrophoretic mobility values of 4.57±0.13 µm.cm.V -1 .s -1 and 5.81±0.20 µm.cm.V -1 .s -1 for short and long Ge-imogolites, respectively.

The Ge-imogolite charge density was found to be 0.7e.nm -2 due to Al-OH 2 0.5+ groups mainly located on the edges of tubes and on vacant sites in the outer surface, and a weak positive charge along the tubes due to the slight charge delocalization generated by the tube curvature. [START_REF] Gustafsson | The surface chemistry of imogolite[END_REF][START_REF] Paineau | A liquid-crystalline hexagonal columnar phase in highlydilute suspensions of imogolite nanotubes[END_REF] Finally, CNC were imaged by AFM (Figure 1C) as stiff nanorods with average dimensions of 125±25 nm in length and 7.45 ±1.50 nm in height (Figure S1C-S2C), and with an aspect ratio of 16.8, which was in accordance with previous values described for CNC from cotton linters. [START_REF] Capron | Surfactant-Free High Internal Phase Emulsions Stabilized by Cellulose Nanocrystals[END_REF] The electrophoretic mobility of the CNC suspension indicated that particles were negatively charged at a pH of 3.5 (-3.89±0.13 µm.cm.V -1 .s -1 ). Negative charges originated from ester-sulfate groups formed during hydrolysis with sulfuric acid. Multilayer thin films were prepared by the LbL method to investigate the interaction between CNC and Ge-imogolites. As CNC and Ge-imogolites were negatively and positively charged, respectively, in the deposition conditions and with similar charge densities, interactions between these two nanoparticles were expected.

Growth patterns of polylectrolyte/nanoparticle (PE/NP) and CNC/Ge-imogolite (NP/NP) films.

In this study, we investigated the adsorption behaviour of CNC and Ge-imogolite in relation with LbL film growth.

As a comparison, the growth of PE/NP films (Figure 2A) were studied. Negatively charged CNC were assembled with cationic PAH and, conversely, Ge-imogolites bearing positive charges were assembled with anionic PSS. The film thicknesses increased linearly as a function of the number of deposited bilayers, with a bilayer being the deposition of one NP layer associated with one PE layer. This growth pattern indicated that charge reversal upon NPs and polymer adsorption occurred. The Figure 2A inset highlights the increase in thickness for each half-bilayer. When a PE layer was deposited, the increased thickness was not detected by ellipsometry, while the deposited NP layer could be measured and thus a "stair step" pattern was observed (Figure 2A, inset). Thus the thickness increments observed for a bilayer (NP+PE) resulted from the NP layer deposition. (PAH/CNC) n films displayed an increment per bilayer of about 17, i.e. twofold the height of a single CNC (around 7 nm). This value was in agreement with previous results of Moreau et al. [START_REF] Moreau | Tuning the Architecture of Cellulose Nanocrystal-Poly(allylamine hydrochloride) Multilayered Thin Films: Influence of Dipping Parameters[END_REF] Indeed, in ionic strength conditions, and due to charge screening repulsive electrostatic interactions, PAH chains adopt a random coil conformation upon adsorption, leading to the adsorption of a CNC double-layer. [START_REF] Moreau | Tuning the Architecture of Cellulose Nanocrystal-Poly(allylamine hydrochloride) Multilayered Thin Films: Influence of Dipping Parameters[END_REF][START_REF] Jean | Structural Details of Cellulose Nanocrystals/Polyelectrolytes Multilayers Probed by Neutron Reflectivity and AFM[END_REF] In the case of (Ge-imogolite/PSS) n thin films, increments were found to be 3.57±0.01 nm and 6.20±0.03 nm when short and long Geimogolites were used, respectively. When short Ge-imogolites were used, the slope value was close to the height of one Ge-imogolite (~4 nm/bilayer). When short Ge-Imogolites were used, the slope value is close to the average vertical distance between the center of the particles of two layers in a packing of aligned cylinders or tubes (or close packing of spheres) i.e. d×cos(π/6)=4.1 nm×cos(π/6)=3.55 nm.

We could therefore hypothesize that a Ge-imogolite monolayer was deposited. In the case of long Ge-imogolites, the slope value (~6 nm) was higher than. This could be explained by the higher aspect ratio of long Ge-imogolites that limit efficient packing on the surface to create more superposed structure. Indeed, surface adsorption is driven by physicochemical forces, but the geometrical characteristics of nanoparticles likely play a role in the layer arrangement. Long Ge-imogolites displayed a higher aspect ratio (18.5) than short Ge-imogolites (8.5). It was thus likely that long Ge-imogolites could more easily overlap to form porous matchsticks, resulting in a deposition thickness greater than the diameter height. On the contrary, short Ge-imogolites were sometimes arranged in a more homogeneous layer with a thickness in the range of the Geimogolite nanotube diameter. Figure 2B shows the growth pattern of NPs based films. The thickness of (CNC/Ge-imogolite) n thin films increased linearly with the number of coated bilayers (please note that the intercept of the curve is not zero since the first bilayer if deposited on a PAH anchoring layer resulting in the deposition of 18 nm height bilayer). Growth was also confirmed by the structural colors displayed by the films as a function of the number of deposited bilayers (Figure SI7). Thus, interactions between CNC and Ge-imogolites occurred to allow the adsorption of NPs of opposite charge. Moreover, the charge reversal was also supported by control experiments that were performed by measuring the thickness of CNC or Ge-imogolite layers after dipping in the same suspension several times, where no growth occurred (Figure SI5). This confirmed that the film growth resulted from interactions between CNCs and Ge-imogolites likely due to their opposite charges.

However, NP/NP films displayed different growth patterns than NP/PE films. Firstly, only a minor difference in increment per bilayer was observed when the aspect ratio of Ge-imogolites was modified. Secondly, the bilayer increments were surprisingly lower than expected. Indeed, the height of CNC determined by AFM was approximately 7 nm and about 4 nm for Geimogolite. Thus, if one layer of each NP had been deposited at each dipping cycle, the expected increment would have been approximately 11 nm per bilayer. Here, the increments measured were approximately 4 nm lower than expected (Figure 2B). When looking closely at the growth after deposition of each NP, we measured a thickness increase of 4.83±0.79 nm, and 4.52±0.90 nm when CNC were coated on short and long Ge-imogolites, respectively, and 1.17±0.42 nm and 1.31±0.68 nm when short and long Ge-imogolites were coated on CNC (Figure 2B inset).

The low thickness values obtained suggested that NPs behaved differently when associated with another NPs than associated with polymeric PE. Different processing parameters such as immersion time or ionic strength of Ge-imogolite suspensions were varied to gain further insight into the growth pattern of all particle films.

Dipping parameter variations

The following set-up was used to examine the effect of dipping parameters. The first four CNC/Ge-imogolite bilayers were coated according to the protocol described in the first part of the study (Figure 3A-B, black dots), while the following six bilayers were built by varying the dipping parameters (Figure 3A-B, blue, green, and red symbols). When no dipping parameters were modified, the increments were 5.71±0.21 nm (Figure 3A), and 6.46±0.18 nm with short and long Ge-imogolites, respectively (Figure 3B).

The parameters that were varied for Ge-imogolite suspensions were as follows:

-Dipping time (i),

-Ionic strength (ii), -Immersion frequency/drying step (iii).

(i) Dipping times were adjusted on the basis of practical considerations. Nevertheless, they usually ranged from 10 to 20 min, but shorter times were used in some cases. [START_REF] Martin | Nanocellulose/polymer multilayered thin films: tunable architectures towards tailored physical properties[END_REF][START_REF] Olivier | Cellulose Nanocrystal-Assisted Dispersion of Luminescent Single-Walled Carbon Nanotubes for Layerby-Layer Assembled Hybrid Thin Films[END_REF] In this study, the chosen dipping time of the film in the nanoparticle suspensions was 1 min, Thus, the dipping time was increased up to 20 min to investigate the possible effect of slow kinetic or rearrangement processes (Figure 3, blue inverted triangles). No influence on the thickness increment was observed, indicating that very fast kinetic adsorption occurred. It could therefore be concluded that the final architecture of a CNC/Ge-imogolite-based thin film was not dependent on the dipping time. (ii) Electrostatic repulsions between Ge-imogolite nanotubes adsorbed on the surface and/or present in solution could be responsible for the limited NP adsorption. The screening of electrostatic repulsions by increasing the ionic strength has been widely studied in the literature since it can increase adsorption by lowering electrostatic repulsion between NPs but also by changing the conformation of PE, which could promote the formation of denser NP layers. [START_REF] Dammak | Influence of cellulose nanocrystals concentration and ionic strength on the elaboration of cellulose nanocrystals-xyloglucan multilayered thin films[END_REF][START_REF] Azzam | Cellulose Nanofibril-Based Multilayered Thin Films: Effect of Ionic Strength on Porosity, Swelling, and Optical Properties[END_REF] To avoid NP aggregation, a salt concentration of 5 mmol.L -1 was chosen at which short and long Ge-imogolites displayed an electrophoretic mobility of about 3 µm.cm.V -1 .s -1 (vs 5-6 µm.cm.V - 1 .s -1 without salt) (Figure SI6). A 0.93 nm and 1.73 nm thickness increment increase was observed when short and long Ge-imogolites were used, respectively (Figures 3A and3B, red squares). Thus, screening of the Ge-imogolite charges seemed to indicate an increase in the amount of NP adsorbed on CNC layers, but the increment expected (~10 nm), according to the pattern noted with PE+NP thin films, was not reached. This effect could have been due to densification of the NP layer, as reported by Dammak et al. [START_REF] Dammak | Influence of cellulose nanocrystals concentration and ionic strength on the elaboration of cellulose nanocrystals-xyloglucan multilayered thin films[END_REF] who noted a decrease in the porosity of CNC/xyloglucan multilayered films upon the addition of low concentrations of monovalent salt to the CNC suspension. From this work it was concluded that the screening of electrostatic repulsion allowed CNCs to pack more closely on the surface, which could explain the small thickness increment observed when NaCl was added to the Ge-imogolite suspensions.

(iii) Finally, the immersion frequency in the Ge-imogolite suspensions was increased and each immersion was followed by drying of the layer by a nitrogen stream. Indeed, the effect of drying has already been reported to have a very strong effect on the film construction and stability. [START_REF] Moreau | Tuning the Architecture of Cellulose Nanocrystal-Poly(allylamine hydrochloride) Multilayered Thin Films: Influence of Dipping Parameters[END_REF] Here, a typical CNC/Ge-imogolite bilayer was composed of:

-A layer of CNC, which was coated by dipping the film for 1 min in the suspension. This step was followed by washing and drying, -Twenty dipping steps by dipping the film 20*1 min in the Ge-imogolite suspension. Each 1 min immersion was followed by washing and drying.

When short Ge-imogolites were used (Figure 3A, green triangles), the increment increase of 2.00 nm (7.71±0.01 nm) and +3.19 nm (9.65±0.16 nm) when long Ge-imogolites (Figure 3B, green triangles) were used. In the case of long Ge-Imogolites, the increment is slightly smaller than the theoretical value in the case of close packing (12.05xcos(pi/6)=10.43 nm expected), suggesting only little spacing between particles. In the case of short Ge-Imogolites the increment is much lower than for a close-packing (11.55xcos(pi/6)=10.00 nm expected) suggesting a larger spacing between nanoparticles. However, the protocol enabled a significant increase of the increments.

Increasing the number of dippings and subsequent dryings is essential to increase the Ge-imogolite amount adsorbed. Electrostatic interactions occurred when Ge-imogolites were coated on a CNC layer. Nevertheless, both CNCs and Ge-imogolites were loosely charged materials compared to polymeric PE. Moreover, the stiffness of the particles limited the rearrangement of the architecture to increase the ion pairing as compared to more flexible polymeric PE. It was thus likely that during the adsorption step, the wet structure could be seen as a loose gel of NPs on the surface that was thick enough to allow the charge reversal. When the film was dried, the gel collapsed due to the removal of water and NPs flattened on the surface, but without complete coverage and complete compensation of charges arising from the n-1 layer. Thus a new dipping sequence allowed the adsorption of additional NPs leading to an increase in the film thickness to achieve a more complete layer.

To investigate the hypothesis of the influence of the drying step on a NP/NP thin film, CNC double layers were coated on PAH, and imaged by SEM. The first and twentieth coatings of Geimogolites were compared for the two the aspect ratios. A non-metallized-CNC double layer is presented in Figure 4A. CNCs were hardly visible due to the insulating properties of CNC. A loose and porous layer appeared when long and short Geimogolites (Figure 4B-4D) were coated. Imogolites appeared as fiberlike networks and seemed to form bundles. This is consistent with the findings of a previous study showing the formation of these Ge-imogolite bundles when the suspension was dried at room temperature. [START_REF] Amara | Hexagonalization of Aluminogermanate Imogolite Nanotubes Organized into Closed-Packed Bundles[END_REF] However, the nature of the inter-tube interactions is not yet sufficiently understood to be discussed in detail in this study. This architecture has yet to be investigated and is probably a complex interplay between charge distributions along the tube and various interaction forces (e.g. capillary forces, electrostatic, hydrogen bonding). Nevertheless, obviously repetitive immersions in Geimogolites increase the amount of NPs (Figure 5C-5E) to achieve more complete surface coverage. A more in-depth AFM investigation of the surface morphologies was carried out.

Surface topography of the first bilayer CNC/Ge-imogolite.

The film topographies measured by AFM are presented in Figure 5. For each thin film (CNC bilayer (Figure 5A), short Ge-imogolite layer on a CNC double layer (Figure 5B), and long Geimogolite layer on a CNC double layer (Figure 5C)), a height profile is displayed. In addition, height profiles were integrated on the entire images. Firstly, the CNC layer on PAH (Figure 5A) appeared as a dense layer, in accordance with previous results obtained for CNC from cotton linters on salted-PAH. [START_REF] Moreau | Tuning the Architecture of Cellulose Nanocrystal-Poly(allylamine hydrochloride) Multilayered Thin Films: Influence of Dipping Parameters[END_REF][START_REF] Jean | Structural Details of Cellulose Nanocrystals/Polyelectrolytes Multilayers Probed by Neutron Reflectivity and AFM[END_REF] The average height profile displayed an unusual organization for a homogeneously distributed CNC layers that is reminiscent of a double layer of CNCs already described in previous work. [START_REF] Moreau | Tuning the Architecture of Cellulose Nanocrystal-Poly(allylamine hydrochloride) Multilayered Thin Films: Influence of Dipping Parameters[END_REF][START_REF] Jean | Structural Details of Cellulose Nanocrystals/Polyelectrolytes Multilayers Probed by Neutron Reflectivity and AFM[END_REF] Indeed, the lower layer was denser than the surface layer. This result is in accordance with the architecture reported by Moreau et al. [START_REF] Moreau | Tuning the Architecture of Cellulose Nanocrystal-Poly(allylamine hydrochloride) Multilayered Thin Films: Influence of Dipping Parameters[END_REF] , and the CNC distribution described by Jean et al. by neutron reflectivity and AFM. [START_REF] Jean | Structural Details of Cellulose Nanocrystals/Polyelectrolytes Multilayers Probed by Neutron Reflectivity and AFM[END_REF] The authors noted that the CNC double layer deposited on PAH display a densities of 50% and 25% for the lower and upper layers, respectively. When short Geimogolites were added on CNC, the adsorption of NP was visually unclear (Figure 5B). The bimodal distribution profile changed and was less marked than for that with CNCs alone. This suggested that short Ge-imogolites filled pores between CNCs (Figure 6). Short Ge-imogolites had an average length of about 35 nm and a diameter of 4 nm, with an aspect ratio of 8.5.

Previous studies have reported marked variations in the porosity of dense materials obtained from rod/fiberlike particles as a function of the aspect ratio. For example, as the aspect ratio of cylinders varied from 5 to 50, the porosity increased dramatically from 0.42 to 0.90. [START_REF] Nan | DEM simulation of the packing of rodlike particles[END_REF] CNCs and short Ge-imogolites could thus be more efficiently packed by co-alignment, in turn optimizing ion pairing and resulting in a charge reversal, but without the formation of a distinct Geimogolite layer, leading to a lower thickness increment than obtained with PE/Ge-imogolite systems.

Long Ge-imogolites appeared more clearly on the image as long and thin nanorods (Figure 5C).

The bimodal distribution profile also changed and the first population was hardly distinguishable. Since long Ge-imogolites had a higher aspect ratio than short Ge-imogolites, a more porous structure with lower packing could be expected. In a first approximation, this seems to be out of line with the more homogeneous profile obtained. However, the tip penetration in the film must be taken into account. Since long Ge-imogolites could not efficiently fill holes in the CNC film, they likely formed a more homogeneous layer on the top of the film (Figure 6). This could thus limit the tip penetration, leading to a more homogeneous image profile. Nevertheless, it is obvious that aspect ratio of Ge-imogolites play a crucial role in the nanoparticle distribution in the film and, besides morphology changes, porosity should also be affected. found that all nanoparticle multilayered films grew differently than PE and NP based films. We showed that the growth of CNC/Ge-imogolite-based multilayer films was insensitive to some dipping parameters, such as ionic strength or dipping time, while repeated immersion/drying steps had an effect on film growth. We highlighted the essential effect of the drying step on the architecture of the final all nanoparticle multilayered films. AFM images demonstrated that the film architecture was dependent on the NP aspect ratio. The influence of architecture variations on the porosity and associated functionality of such optical or diffusion features will be investigated in future work.

This work is a contribution to the Labex Serenade programme (no. ANR-11-LABX-0064) funded by the "Investissements d'Avenir" programme of the French National Research Agency (ANR) through the A*MIDEX project (no. ANR-11-IDEX-0001-02).

Figure 1 :

 1 Figure 1: AFM images on a 2 µm*2 μm area of: A) short Ge-imogolites, B) long Ge-imogolites,

Figure 2 :

 2 Figure 2: PE/NP (A) and NP/NP-based (B) thin film thickness patterns as a function of the

Figure 3 :

 3 Figure 3: Dipping parameter variations to find the optimal growth of: A) (CNC/short Ge-

Figure 4 :

 4 Figure 4: SEM investigation of the adsorption mechanisms of Ge-imogolites on CNC with the

Figure 5 :

 5 Figure 5: AFM images on a 2 μm*2 µm area of: A) (PAH/NCC) 1 , B) (CNC/short Ge-

Figure 6 :

 6 Figure 6: Schematic representation of the adsorption mechanism of Ge-imogolites on CNC as a

Table 1 :

 1 Average dimensions of Ge-imogolites and CNC from AFM images

	Nanoparticules	pH of suspensions	electrophoretic mobility (µm.

cm.V -1 .s -1 ) Average dimensions from AFM Length (nm)

					Diameter/Height
					(nm)
	Short Ge-imogolites	6.5	+4.57±0.13	35 ±10	4.1 ±0.3
	Long Ge-imogolites	6.8	+5.81±0.20	85 ±45	4.6 ±0.4
	CNC	3.5	-3.89±0.13	125 ±25	7.45 ±1.50

ACKNOWLEDGMENTS

We thank ad ge eur for her excellent technical support for LbL assembly and ellipsometry.

We are also grateful to Andrea Campos from the CP2M laboratory for her SEM imaging technical support.

Funding Sources

Cellulose nanocrystals

Short imogolites

Long imogolites

TABLE OF GRAPHIC CONTENT ASSOCIATED CONTENT

Supporting Information

Length and height distributions of CNC and Ge-imogolites, example of particles determination measurement, FTIR spectra of CNC and imogolites, film thickness patterns when only one of them was coated on a silicon wafer, electrophoretic mobility of Ge-imogolite suspensions as a function of NaCl addition, and structural colors obtain as a function layer deposition.

AUTHOR INFORMATION

Corresponding Author

*E-mail bernard.cathala@inra.fr (B.C.). *E-mail rose@cerege.fr (J.R.).

Notes

The authors declare no competing financial interest.


Guillaume Damiand
email: damiand@sic.univ-poitiers.fr

Patrick Resch
email: resch@lirmm.fr

Split and Merge Algorithms Defined on Topological Maps for 3D Image Segmentation

Keywords: topological maps, split-and-merge, image segmentation, image processing

Split-and-merge algorithms define a class of image segmentation methods. Topological maps are a mathematical model that represents image subdivisions in 2D and 3D. This paper discusses a split-and-merge method for 3D image data based on the topological map model. This model allows representations of states of segmentations and of merge and split operations. Indeed, it can be used as data structure for dynamic changes of segmentation. The paper details such an algorithmic approach and analyzes its time complexity. A general introduction into combinatorial and topological maps is given to support the understanding of the proposed algorithms.

Introduction

The region segmentation was studied in many different works in 2 dimensions. It consists in making a partition of an image into connected sets of pixels which verify an homogeneity criterion, and which are called regions. A classical approach to region segmentation is the split-and-merge method and all its variants. The top-down approach [START_REF] Lee | Recursive region splitting at hierarchical scope views[END_REF][START_REF] Ohlander | Picture segmentation using a recursive region splitting method[END_REF] consists in taking big regions and cutting them into smaller and smaller regions. The bottom-up approach [START_REF] Brice | Scene analysis using regions[END_REF][START_REF] Fiorio | Two linear time union-find strategies for image processing[END_REF] is the opposite one. It begins with many small regions that are progressively merged into bigger and bigger regions. At last the mixed approach [START_REF] Horowitz | Picture segmentation by a directed split-andmerge procedure[END_REF][START_REF] Pietikainen | Split and link algorithms for image segmentation[END_REF] consists in combining the two previous ones.

These approaches require a "good" model of images representation. Many works in 2 dimensions [START_REF] Braquelaire | Image segmentation with topological maps and inter-pixel representation[END_REF][START_REF] Brun | Segmentation d'images couleur à base Topologique[END_REF][START_REF] Brun | A new split and merge algorithm with topological maps and inter-pixel boundaries[END_REF][START_REF] Domenger | Conception et implémentation du noyeau graphique d'un environnement 2D1/2 d'édition d'images discrètes[END_REF] have shown that topological maps constitute an efficient framework for these segmentation algorithms. Moreover, thanks to that model we can also define several post-processing algorithms that access or modify the result of this segmentation.

Recently, topological maps have been extended in dimension 3 [START_REF] Bertrand | Topological map: Minimal encoding of 3d segmented images[END_REF][START_REF] Braquelaire | A topological structuring for aggregates of 3d discrete objects[END_REF]. Indeed, more and more domains need to deal with 3D images, such as medical imagery, geology, or industry. Topological maps are a very efficient model of 3D images representation, both to represent images partition and to make it evolve through merging and splitting operations. This lets us consider the definition of efficient 3D segmentation algorithms which is a difficult problem. Indeed, there are complexity constraints, in memory space as well as in execution time, that are much more important than in 2D, due to the bigger amount of data in a 3D image.

In this paper, we present the two operations of merge and split on the 3D topological maps. With these operations, split-and-merge region segmentation algorithms can be written. Topological maps induce a generic definition of these operations since they work on any configurations. Moreover, they allow the definition of local operations since we visit the map element by element, only looking at the direct neighborhood of the current element. These two properties make these algorithms simpler to understand and more efficient in complexity.

We first present in section 2 the combinatorial maps and the topological maps that are combinatorial maps verifying specific properties. Then we present our two algorithms: merge in section 3 and split in section 4. In section 5, we present a computer software for cerebral tumor diagnosis which is based on topological maps. At last, we conclude and present some perspectives in section 6.

Topological Maps Presentation

Topological maps are an extension of combinatorial maps in order to represent discrete images. We first recall some notions around combinatorial maps that are helpful to the understanding of this paper. This is just a short presentation; a more detailed description can be found in [START_REF] Bertrand | Topological encoding of 3d segmented images[END_REF][START_REF] Braquelaire | A topological structuring for aggregates of 3d discrete objects[END_REF][START_REF] Damiand | Définition et étude d'un modèle topologique minimal de représentation d'images 2d et 3d[END_REF].

Combinatorial Maps

Combinatorial maps are a mathematical model of representation of space subdivisions in any dimension. They were first introduced by [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF] as a planar graph representation model, and extended by [START_REF] Lienhardt | Subdivision of n-dimensional spaces and n-dimensional generalized maps[END_REF] in dimension n to represent orientable or not-orientable quasi-manifold. They are a boundary representation model (B-Rep) because they represent objects by their borders. Combinatorial maps encode space subdivisions and all the incidency relations. They are made of abstract elements, called darts, on which are defined applications, called β i . We are giving here the 3D combinatorial map definition that we can find for example in [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF].

Definition 1 (3D combinatorial maps) A 3-dimensional combinatorial map, (or 3-map) is an 4-tuple M = (D, β 1 , β 2 , β 3 ) where:

(1) D is a finite set of darts;

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

(3) β 2 and β 3 are involutions 2 on D;

(4) β 1 • β 3 is an involution.
In this definition, there is an application β i for each dimension of space (except for dimension 0) that puts in relation two i-dimensional cells. When two darts are linked with β i , we say that they are β i -sewn, and we call i-sewing (resp. i-unsewing) the operation that puts in relation two darts for β i (resp. that removes an existing β i -relation).

We can see in Figure 1 an example of a 2D combinatorial map (we chose to present here a 2D example in order to simplify the map representation; there are 3D combinatorial maps examples in the following of this paper). This map can be explicitly defined by giving the set of darts and the two applications β 1 and β 2 . We can verify on this explicit definition that β 1 is a permutation and β 2 is an involution. We can also remark that some darts are invariant for β 2 (for example darts numbered 1, 2 and 3). This case occurs when for a dart, it does not exist another dart incident to the same edge but not to the same 1 A permutation on a set S is a one to one mapping from S onto S. 2 An involution f on a set S is a one to one mapping from S onto S such that f = f -1 . face. These darts are said 2-free (and we speak about i-free dart for a dart d such that β i (d) = d. When it is necessary to represent loops, this definition is modified and a i-free dart is then a dart d such that β i (d) = NULL).

In combinatorial maps, space cells are implicitly represented by orbits. Intuitively, an orbit can be seen as the set of darts that can be reached by a traversal starting from d and using only the given permutations (or any permutation that can be obtained from the given permutations by composition and inverse). For example, in 2 dimensions, the edge incident to a dart d is < β 2 > (d) and the face incident to d is < β 1 > (d). If we look at the combinatorial map presented in Figure 1, the edge incident to the dart numbered 1 is < β 2 > (1) = {1}, the edge incident to the dart numbered 4 is < β 2 > (4) = {4, 6} and the face incident to the dart numbered 6 is < β 1 > (6) = {6, 7, 5, 8}.

Combinatorial maps encode only objects topology, and not their geometry. But it is very easy to add some geometry elements to some (even all) cells of the combinatorial map. We speak about embedding for the geometry associated with a combinatorial map. The simplest embedding of a combinatorial map, and also the most used, consists in linking each vertex of the map with the coordinates of an Euclidean space point. But there are many different way to embed a map, and the choice of one of these methods depends on the application. The distinction between topology and embedding allows the differentiation of operations. Indeed, some operations only deal with the topological model, others only with the geometrical one, and some with both of them.

Topological Maps

Topological maps are an extension of combinatorial maps in order to represent 3D images. Indeed, in the combinatorial maps framework, different maps may represent the same object. This could be a problem for some image processings, for example to perform image analysis by using isomorphism algorithms. Topological maps solve this problem by adding some properties that ensure the uniqueness of the representation.

A topological map represents a 3D labelled image. This is a 3D image where each voxel has a label (which can be for example the voxels colors). A region is a set of 4-adjacent voxels having same labels. A boundary face is a maximal connected surface between two neighboring regions. We consider here the image as a space subdivision [START_REF] Ahronovitz | The star-topology: a topology for image analysis[END_REF][START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF][START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF] and call voxels the 3-cells, surfels the 2cells, linels the 1-cells and pointels the 0-cells. Two adjacent regions can share several boundary faces. We give here the general definition of a 3D topological map:

Definition 2 (3D topological map) Let I be a 3D image. The topological map corresponding to I is the combinatorial map M = (D, β 1 , β 2 , β 3 ) so that:

(1) M represents the space subdivision given by I;

(2) M is embedded so that the geometry of M represents the intervoxel contours of I;

(3) M is added with an inclusion tree on the regions of I; (4) each face of M corresponds to a boundary face of I;

(5) each face of M is homeomorphic to a topological disk; (6) M is minimal. A map that verifies the previous properties with a smaller number of darts does not exist.

Now we are going to explain more precisely all the different parts of this definition. Topological map is an extension of combinatorial map to represent an image (Definition 2, part 1). It is added with an inclusion tree (part 3) which represents the volumes inclusions. Each node corresponds to a region of the image, and its sons correspond to included regions. The root of the tree is R 0 , the infinite region which surrounds the image. Each dart d of the map knows its belonging region (noted region(d)) and each region R i of the tree knows one dart of the map that belongs to the region (noted dart(R i )). We develop below part 2 of the definition concerning the embedding of the map, after having presented the other parts of the definition.

The most important parts of Definition 2 relate to the three additional properties that a topological map has to verify. times topological face in order to avoid confusion with the embedding). This point of the definition fixes the number of faces of a topological map for a given image.

Second, each face of a topological map has to be homeomorphic to a topological disk (Definition 2, part 5). This property solves the face disconnection problem that occurs for boundary faces that are not homeomorphic to a topological disk, like the upper face of the paving (in light grey) presented in Figure 2.a. This face has two distinct borders and the corresponding map

(shown in Fig- ure 2.b) is made of two different connected components.
We have lost the topological information that allows to place the two connected components relating to each other. To solve this problem, a solution consists in keeping each face homeomorphic to a topological disk. We obtain the map shown in Figure 2.c which is composed by a unique connected component. For that, we need to add edges which cut faces that are not topological disks. These additional edges do not represent the border of a boundary face and because of that are called fictive edges (in opposition, we call real edge an edge that is not a fictive edge). We can see a fictive edge in thick black on the map shown in Figure 2.c. This solution was already used to solve the same problem in other models, for example in dual graph [START_REF] Kropatsch | Building irregular pyramids by dual-graph contraction[END_REF]. A fictive edge is a one degree edge (that is adjacent twice to the same face). We need to distinguish the two kinds of edges because they do not have the same role (real edges represent borders of boundary faces and fictive edges keep faces connected). This distinction leads to different processings during algorithms on topological maps, as we will see in the following parts.

The last property that a topological map has to verify is: a topological map has to be minimal (Definition 2, part 6). As the number of faces is fixed, for a given image, by part 4 of the definition, we can only modify here the number of edges (that is linked by the Euler formula to the number of vertices). A map is minimal if it does not contain any degree two vertex. Indeed, when we a. A 3D subdivion.

b. The same subdivion where degree two vertices were removed. c. The minimal subdivision: we need to shift the fictive edge. have this kind of vertex, we can merge the two edges incident to this vertex without losing any information as we can see in Figure 3. Figure 3.a shows a subdivision that represents the object already used in Figure 2. All degree two vertices (drawn in black) can be removed by the edge merging operation. We can verify in Figure 3.b that we actually represent the same object (to simplify the drawing we have only represented edges and vertices of the map and not all the darts). But the obtained subdivision is not minimal, because of the fictive edge (the black edge in the figure): the black vertex in Figure 3.b is then not a degree 2 vertex. But the fictive edge only keeps the upper face connected, and its position is not significant. If we shift this edge, the black vertex becomes a degree two vertex and can be removed. We thus obtain the subdivision shown in Figure 3.c that is the minimal subdivision (for the fixed faces given in Figure 3.a). These two operations are the basic ones used to define a simplification algorithm which takes a map in input and simplifies it in order to obtain the minimal representation (see [START_REF] Damiand | Définition et étude d'un modèle topologique minimal de représentation d'images 2d et 3d[END_REF] for the detail of this algorithm).

With all these properties, we can prove that topological map is minimal and stable for translation, rotation and scaling (two equivalent images up to these operations are represented by two isomorphic topological maps). Moreover, with fictive edges, we can represent all the different kinds of surfaces and correctly capture their topology.

We can see in Figure 4.a an example of a 3D image composed with three regions (R 1 , R 2 and R 3 ) plus the infinite region R 0 , in Figure 4.b its boundary faces, and in Figure 4.c the corresponding topological map. We can verify that all boundary faces are actually represented in the topological map. As each boundary face of this image is homeomorphic to a topological disk, there is no fictive edge in the topological map. All edges are real edges and represent a border of a boundary face. Note that in Figure 4.c, we do not represent all the darts of the topological map. Indeed, each boundary face is represented in the map by two half-faces that are identical and β 3 -sewn each other. These two half-faces represent the same boundary face which is seen according to the two regions around this boundary (as we can see in Figure 4.c for the boundary face between R 1 and R 2 ). In order to simplify the drawing, we do not represent the second half-face for the three boundary faces with R 0 . But even if these half-faces are not drawn, they are of course present in the topological map.

We can see in Figure 5 an example where a boundary face (between R 1 and R 2 ) is not homeomorphic to a disk. Figure 5.c shows the topological map restricted to that boundary face: two fictive edges (in grey) have been added to make the topological face homeomorphic to a disk. As we have already seen above, these fictive edges have no fixed position. For that reason, the topological map obtained is unique, except for the position of the fictive edges. We hope to solve this drawback by adding some properties to fix more precisely this position, but we need some additional works. This drawback is not so important in this work as we do not use here the position of the fictive edges during our algorithms and shift these edges when it is necessary.

We can see in Figure 6 another example of a topological map when a boundary face is closed, here for a torus. This torus is represented with a single closed boundary face and this face is represented in the topological map shown in Figure 6.c by two fictive edges. Indeed, real edges represent only borders of a boundary face, and here this face has no border. We obtain a classical minimal a. A torus. b. Corresponding topological map. representation of the torus composed by one face, two edges and one vertex. For all boundary faces with no border, we obtain a representation that is equivalent to a canonical polygonal schema [START_REF] Dey | Computing homology groups of simplicial complexes in R 3[END_REF][START_REF] Fomenko | Topological Modeling for Visualization[END_REF] with one face, one vertex and 2G edges, with G the genus of the object. Now that topological map have been described, we present how to embed them. This embedding represents the intervoxel contours of the corresponding image. There are several ways to realize this embedding, for example by linking to each topological face the set of corresponding surfels or by giving explicitly all the voxels of each region. In this case, the embedding of the boundary faces has to be computed from the array of voxels by a surface tracking algorithm. We use in this work another solution that consists in linking to each topological face an embedding surface as we can see in Figure 7. This figure shows the embedding of the topological map of Figure 4. Each dart of the topological map is linked with the border of an embedding surface. One way to represent the embedding surfaces is to use 2-dimensional combinatorial maps. We obtain thus a hierarchical model. These 2-maps are embedded in the 3D Euclidean space, simply by linking to each vertex of the map the coordinates of the corresponding pointel. Moreover, we represent each maximal set of coplanar surfels by a unique face in order to limit the memory space. Given a dart d, we call embed(d) the dart of the embedding surface linked with d. Reciprocally given a dart d ′ of an embedding surface, we call dart(d ′ ) the dart of the topological map linked with d ′ (these relations are shown in light gray on the figure). For each dart d of the map we have dart(embed(d)) = d. Only darts belonging to the border of an embedding surface (drawn in thick black in Figure 7) are linked with a dart of the topological map. For other darts of the embedding surfaces we fix dart(d) = NULL.

The merge operation

The merge operation consists, starting from two adjacent regions R 1 and R 2 , in gathering them into a single region union of the two first. Algorithm 1 makes this operation on a topological map. Generally, an algorithm that modifies a topological map has three different steps: first it modifies the combinatorial map and/or the embedding, second it updates the inclusion tree if it is necessary, and at last it ensures that the modified map is actually a topological map, that is to say it verifies the properties given in Definition 2. The merge algorithm follows this principle.

The merge algorithm

The merge algorithm is composed of three parts. The first part (Algorithm 1.1) consists in marking all darts of the orbit < β 1 , β 2 > (dart(R 1 )) and < β 1 , β 2 > (dart(R 2 )) without passing through a fictive edge belonging to a boundary face between R 1 and R 2 . Given a dart d, the orbit < β 1 , β 2 > is the set of darts belonging to the faces connected to d. But here we just want to mark all the darts belonging to the faces of R 1 and R 2 which are the future exterior faces3 of R 1 ∪R 2 . This is simply done by avoiding to pass through fictive edges of boundary faces between R 1 and R 2 as we can see on the example presented in Figure 8. In the first example (Figure 8.a), we do not mark all the faces of R 3 because we cannot pass by the fictive edge (in thick black) that belongs to the boundary face between R 1 and R 2 . But these faces are not exterior faces of

R 1 ∪ R 2 as R 3 is included in R 1 ∪ R 2 .
In the second example (Figure 8.b), we mark all faces because, even if we still cannot pass by the fictive edge that belongs to the boundary face between R 1 and R 2 , we can here pass by the other fictive edge (e) that belongs to the boundary face between R 2 and R 0 .

Algorithm 1: Merge 3D Input: Two adjacent regions R 1 and R 2 . Result: The two regions are merged into R 1 .

1 Mark all darts of < β 1 , β 2 > (dart(R 1 )) and < β 1 , β 2 > (dart(R 2 )) without passing through a fictive edge of a boundary face between R 1 and R 2 ; Destroy the fictive edge incident to d;

2 foreach dart d of R 2 do if region(β 3 (d)) = R 1 then if d
5 Set daughters of R 2 as daughters of R 1 and remove R 2 in the inclusion tree;

6 Simplification of R 1 ; R 0 R 1 R 2 R 3 R 0 R 1 R 3 R 2 e
a. Marking only faces between R 1 and R 0 and those between R 2 and R 0 .

b. Here all faces are marked since we may go through the fictive edge e. Indeed, R 3 is not included in R 1 ∪ R 2 (a boundary face between R 3 and R 0 exists), so faces with R 3 are also exterior faces of

R 1 ∪ R 2 .
This step is necessary to test when the removal of a boundary face leads to the disconnection of the map by creating new inclusions. It is achieved by a traversal which uses the involutions β 1 and β 2 and tests if the current dart belongs or not to a fictive edge of a boundary face between R 1 and R 2 . We will see how we use these marks in the following explanations.

The second part of the algorithm (Algorithm 1.2-4) realizes the merging. This is done in a local way because since each dart of R 1 that belongs to a boundary face with R 2 is processed independently and since the modification of the map is local. There are two different cases depending if the current dart belongs to a real edge or not. When the current dart belongs to a real edge (Algorithm 1.3, and shown in Figure 9), we just β 2 -sew β 2 (d) and β 2 (β 3 (d)) then we destroy the two darts β 3 (d) and d. We can see in Figure 9.b the map before this modification, and the result in Figure 9.c. At the end of the loop, when we have processed all the darts of R 1 , we obtain the map shown in Figure 9.d. The boundary face between R 1 and R 2 is completely deleted and the sewings of darts that were incident to this face are updated (in black in Figure 9.d ).

When the current dart belongs to a fictive edge (Algorithm 1.4), we have to test if this leads to the disconnection of the map in order to eventually update the inclusion tree. For that, we just test if the two darts β -1 1 (d) and β 1 (d) have the same mark. If that is the case, then they both belong to the exterior border of R 1 ∪R 2 and there is no new inclusion (case shown in Figure 8.b). Otherwise, we know that the merging will create new inclusions and we need to update the inclusion tree. To do that, we traverse all darts that belong to the connected component of the dart which is not marked (the orbit < β 1 , β 2 , β 3 > (d 2 ) but without passing through a fictive edge belonging to a boundary face between R 1 and R 2 in order to stay on the included regions) and just put all the regions thus visited as daughters of R 1 (except of course regions R 1 and R 2 ). At last we can destroy the fictive edge. We do not need to update some sewing as there is no surviving dart incident to the removed edge.

Finally, we need to put all regions that are daughters of R 2 as daughters of R 1 and remove R 2 from the inclusion tree (Algorithm 1.5) and simplify R 1 (Algorithm 1.6). This last operation is necessary to ensure that the obtained map is a topological map, that is to say it verifies all the properties of the topological map definition. Indeed, the removal of boundary faces between R 1 and R 2 could have made the map not minimal. This simplification is made by the algorithm briefly presented in section 2. It guarantees the minimality of the topological map. During the simplification step, we can control the evolution of topological characteristics, in order to prove that we do not lose some topological information. This step can be performed during the merging, but this leads to a more complex algorithm where we need to study many different cases.

Time complexity analysis of merge operation

First, we are going to study the basic operations used by the merge algorithm. We can get the region of a dart in O(1), so test if a dart belongs to a region can also be done in O(1). The mark operations (set or test) can also be done in O(1), as the test if a dart belongs to a real or a fictive edge. This can be easily achieved, for example by putting a particular mark on darts that belong to a fictive edge.

The complexity of step 1 of the merge algorithm is in O(|R 1 |+|R 2 |) (we denote by |R| the number of darts that belong to a region R). This step is indeed achieved by a breadth first search algorithm of the darts of these two regions, by testing for each dart if it belongs to a fictive edge before continuing the algorithm.

The complexity of step 2 is in O(|R 1 | + number of darts of included regions in R 1 ∪ R 2 ). Indeed, during this step, we pass through all the darts of R 1 . When the current dart belongs to a fictive edge and β 0 (d) and β 1 (d) have different marks, we need to traverse all darts of the included regions in R 1 ∪ R 2 in order to update the inclusion tree. This is also made by a breadth first search algorithm.

The inclusion tree updating (step 5) is in O(number of included regions in R 2 ) that is obviously smaller than the number of darts of included regions in R 1 ∪ R 2 , and the simplification of the new region

R 1 is in O(|R 1 | + |R 2 |).
So, the merge algorithm complexity is

O(|R 1 | + |R 2 | + number of darts of included regions in R 1 ∪ R 2 )
It is thus linear in the number of darts of the two merged regions and the included regions in R 1 ∪ R 2 . The classical merge algorithm defined on voxels matrix is also linear but in number of voxels of the two regions. This lets us view an important gain of time for our algorithm since we change the unit of the complexity order. Our algorithm will be very efficient to merge big regions that are represented by few darts. On the other hand, it will not be efficient to merge two regions that are each composed by a unique voxel.

The split operation

This operation consists in splitting a region by a separation face. This face is given to the algorithm by an ordered list of vertices which represent the intersections of an orthotropic plane and the edges of the map. The first vertex of this list must belong to a topological edge of the map, or in other words it must belong to the border of an embedding face, and two successive vertices must belong to the same embedding surface. Moreover, this list must be closed: the last vertex is equal to the first one. These constraints have been fixed in order to simplify the algorithm and to limit the number of different cases to process. They can be checked before calling the split algorithm, and the list of vertices can be built given a topological map and an orthotropic plane. A simple solution to do complex split is to combine several basic split and merge operations. The principle of the algorithm is to insert a new boundary face in the map which represents the region to split. This is achieved in a local way by processing each dart of the region.

The split algorithm

The split algorithm (Algorithm 2) is composed of three parts. The first part (Algorithm 2.1) cuts all the faces of the map and of the embedding. For that, we begin by initializing a dart of the embedding prevE as the dart that contains the first vertex of the separation face and that belongs to a face that contains the second vertex of this face. We also initializing prevT with the dart of the combinatorial map such that embed(prevT ) = prevE. We can see in Figure 10 the topological map that corresponds to the image shown in Figure 4, in grey the separation face given by the four vertices V 1 . . . V 4 and in thick black the two darts prevE and prevT . To find the dart prevE, we just have to traverse all the embedding surfaces of R and test for each edge if it contains vertex V 1 . When it is the case, we have to check if the incident face contains vertex V 2 , by another simple traversal of the orbit < β 1 >. This step is necessary in order to ensure that prevE is in the correct embedding face. Indeed, as we can see in Figure 10, there is another dart that contains see in Figure 11.a the map obtained after this step (we do not represent all the embedding surfaces in order to simplify the figure). This is the end of the embedding modification. Then we test if d belongs to the border of an embedding face (dart(d) = NULL). When it is the case (Algorithm 2.4), we have to insert an edge in the topological map. For that, we first insert a vertex in the edge incident to dart(d) (the topological dart linked with the current embedding dart d) then an edge between this new vertex and the previous topological vertex (given by prevT ) and we keep the inserted edge in the list L. We update prevT with β 2 (prevT ): the next face we are going to process is indeed the one which is β 2 -linked with the current dart. We also update prevE with embed(prevT ) in order to point to the embedding face linked with the current topological dart. We also need to insert vertex V i in the edge incident to prevE because we are going to use this vertex during the processing of the next vertex. When the current embedding dart is not on a border of an a. Map after vertices and edges insertion. embedding face (Algorithm 2.5) we need to set prevE on the next face of the embedding face in order to insert correctly the next edge on the embedding. At the end of the processing of vertex V i , we have updated the two darts prevE and prevT and so we can pass to the next vertex of the separation face. Before inserting an edge in the topological map, we test if the two end vertices of the edge belong to the same connected component or not (Algorithm 2.3). When it is not the case, we need to update the inclusion tree because included regions in R become not-included. For that, we just set each region of the connected component previously included in R as daughter of f ather(R).

V 2 V 3 V 4 V 1 prevE prevT R
At the end of the loop, we have cut all the faces incident to the separation face (the embedding faces as well as the topological faces). We can see in Figure 11.b the obtained map (partial representation, inserted edges are drawn in black on this figure, with an arrow for topological darts and without it for embedding darts). Then we can insert the new boundary face along the new edges previously inserted (Algorithm 2.6). This is achieved by a simple traversal of the edges of L. During this traversal, we create two darts β 3 -sewn, insert them between the two darts of the current edge (by two β 2 -sewings) and β 1 -sew them with the two darts created for the previous edge (see example in Figure 12).

The last step of the split algorithm consists in simplifying the map. Indeed, we have perhaps inserted too many edges and the resulting map is thus not minimal. The simplification algorithm ensures the minimality of the map. As for the merge algorithm, we can modify the split algorithm in order to avoid this simplification step. For that, we have to insert only necessary edges. This leads to a more complex algorithm where we need to test several different cases.

Time complexity analysis of split operation

All the relations between embedding darts and topological darts (dart(d) and embed(d)) can be retrieved in O(1). The initialization step of the split algorithm has a complexity in O(|embedding of R|). Indeed, to initialize the dart prevE we need in the worst case to traverse all the darts of all the embedding surfaces of R, but each dart is visited only once.

The loop processes the k vertices of the list. For each one, we first find the embedding dart that contains V i and that belongs to the same face. This is done in O(number of embedding darts of the current face). When we traverse some darts for a given vertex V i , we never traverse them again for another V j because we insert an edge for the shortest way between two vertices. Vertex insertion is realized in O(number of darts incident to the edge). But as we work with particular map that represent discrete image, we know that we have, in the worst case, 8 darts incident to an edge, so the vertex insertion can be realized in constant time. Edge insertion is realized in O(1) because there are always only two volumes incident to a face, so we do not need a loop. The operations performed when dart(d) = NULL are similar and are also in O(1) for the same reasons. The test "if prevT and dart(d) belong to the same connected component" can be performed in O(1) by using the same technique than for the merge algorithm. The traversal of all the darts of the connected components included in R in order to update the inclusion tree is in O(number of darts of included regions in R).

So, the loop takes O(|embedding of R|+number of darts of included regions in R) due to the first operation in this loop (research of the embedding dart d), as we do not traverse more than once each dart of the embedding, and due to the inclusion tree updating.

The boundary face creation takes O(k) because we traverse all the inserted edges, and there is one edge for each vertex. At last, the map simplification can be achieved in O(|R|) (number of darts of the splitted region).

So the split algorithm is in O(|embedding of R| + number of darts of included regions in R)

Indeed, there are obviously more darts in the embedding than in the topological part of the map. This algorithm takes more time than the merge algorithm. Indeed, the latter is driven by the topology while the first is driven by the geometry. Generally, a topological map algorithm is more efficient when it is driven by the topology because we first traverse topological darts, then only few geometrical elements linked with particular darts.

Notes about implementation

We have developed a computer software for the CHU of Poitiers [START_REF] Cayrous | Développements autour d'un noyau de cartes généralisées : Modélisation 3d d'environnement urbain et logiciel d'aide au diagnostic par IRM de tumeurs cérébrales[END_REF], which is based on topological maps. First this software allows to load a set of 2D images, result of brain MRI, that represent a 3D image. Then, we can segment this image and control the result, and possibly change the segmentation parameters in order to observe the result on the final segmentation. To perform the segmentation, we have worked in collaboration with a research team on signal processing and used their algorithms [START_REF] Capelle | Segmentation of multi-modality MR images by means of Evidence Theory for 3D reconstruction of brain tumors[END_REF]. Finally we compute the topological map representing the 3D image obtained after the segmentation. We can see in Figure 13 an example of a topological map obtained from MRI images. Currently, this software only allows to visualize the entire map, a particular region selected in the 2D mode or the connected regions of a selected one. We are going to implement the merge and split operations in this software in order to develop split-and-merge segmentation algorithms but also to allow some human corrections of the segmentation.

Conclusion

In this paper, we have presented the basic operations to define an efficient 3D split-and-merge segmentation algorithm: merge and split. These operations are defined on the 3D topological map, a mathematical model of 3D images representation. We have also recalled the main principles and properties of this model in order to make easier the understanding of our algorithms.

These two operations were already presented in [START_REF] Braquelaire | 3d split and merge with 3-maps[END_REF], but our approach differs from this solution since our operations are locals. Indeed, [START_REF] Braquelaire | 3d split and merge with 3-maps[END_REF] use a model equivalent to the topological map but with a different embedding. Their solution consists in keeping the voxels matrix with an explicit representation of all the cells of the intervoxel space. Due to this embedding, they must modify this matrix during the split and merge algorithms, by using the classical algorithms. For this reason, their algorithms have obviously a greater complexity than ours. Moreover, the split operation is performed by rebuilding the map on the new voxels matrix. Our solution is more efficient because we modify directly the map and so avoid a destruction and reconstruction of the map, and more elegant because we use the topological map structure and make it evolve through different processings.

Now, we are going to implement these operations in our computer software, to finally obtain some 3D split-and-merge segmentation algorithms. We are currently working on how to use these algorithms to perform segmentation refinement by adding pre or post-processings. We are also working to the definition of some other operations that could be combinations of the basic operations presented in this work, or some specific ones as the chamfering or boolean operations. We already have defined an interesting operation, the corefining, which can be used to segment big images in parallel.

  object. b. Corresponding map. c. Simplified representation.

Fig. 1 .

 1 Fig. 1. A 2D object and the corresponding combinatorial map represented by two different ways. A 2-map is a 3-tuple M = (D, β 1 , β 2 ) where β 1 is a permutation and β 2 an involution. b. Darts are represented by numbered segments, the β 1 relation by light grey arrows and the β 2 relation by black arrows. β 1 puts in relation a dart and the next dart of the same face, and β 2 puts in relation two darts incident to the same edge but not to the same face. c. A simplified representation of the same map. Darts are represented by black arrows and β i applications are not drawn explicitly but can be easily deduced by the darts positions: two darts in relation by β 1 are drawn consecutively and two darts in relation by β 2 are drawn parallel and close to each other.

  First, each face of a topological map corresponds to a boundary face of the image (Definition 2, part 4). Each boundary face is represented in the topological map by a face (called some-a. A 3D object. b. Problem of face disconnection. c. Solution: keep each face homeomorphic to a topological disk.

Fig. 2 .

 2 Fig. 2. The problem of face disconnection and our solution: keep each face homeomorphic to a topological disk.

Fig. 3 .

 3 Fig.3. The two operations used to obtain a minimal representation: edges merging to remove degree two vertices and shift fictive edges to release degree two vertices.

  image b. Its boundary faces. c. Topological map.

Fig. 4 .

 4 Fig. 4. A 3D image, its boundary faces and the corresponding topological map.

Fig. 5 .

 5 Fig. 5. An image example where a boundary face is not homeomorphic to a disk.

Fig. 6 .

 6 Fig. 6. Topological map of a closed boundary face, here a torus.

Fig. 7 .

 7 Fig. 7. Topological map embedding with 2D maps.

Fig. 8 .

 8 Fig. 8. Marking the exterior faces of R 1 ∪ R 2 .

  map. b. d belongs to the boundary face.

β

  32 (d) β 2 (d) c. After the β 2 -sewing. d. Final result.

Fig. 9 .

 9 Fig. 9. Basic example of Merge 3D.

Fig. 10 .

 10 Fig. 10. Initialization of the split algorithm.

Fig. 11 .

 11 Fig. 11. First step of Split 3D, partial representation of the embedding.

  b. Insertion of a part of the boundary face. c. Final map with the boundary face.

Fig. 12 .

 12 Fig. 12. Insertion of the boundary face after vertices and edges were inserted.

Fig. 13 .

 13 Fig. 13. Application for MRI: 3D mode representing the topological map.

  belongs to a real edge then and β 1 (d) have different marks thend 2 ← the dart among β -1 1 (d) and β 1 (d) which is not marked; foreach dart i of < β 1 , β 2 , β 3 > (d 2 )without passing through a fictive edge of a boundary face between R 1 and R

	3	β 2 -sew(β 2 (d),β 2 (β 3 (d)));
		Destroy β 3 (d) and d;
		else
	4	if β -1 1 (d)

2 do if region(i) = R 1 and region(i) = R 2 then

Set region(i) daughter of R 1 in the inclusion tree;

An exterior face of R i is a boundary face with R j such that R j is not included in R i .

Acknowledgements

We wish to thank Valerie Gral and Magali Delobbe for useful comments and careful reading of this paper. We also are grateful to anonymous referees and to Pascal Lienhardt for their useful suggestions and comments which essentially improved the paper.

Algorithm 2: Split 3D Input: A list of vertex {V 1 , . . . , V k } representing the separation face A region R. Result: R is split along the separation face.

1 prevE ← the embedding dart that contains V 1 and that belongs to a face containing V 6 Build the new boundary face along the edges of L; 7 Simplify the map; vertex V 1 but the embedding face does not contain V 2 . Once the dart prevE is found, we initialize as prevT its corresponding dart in the topological map, ie dart(prevE). We need to keep these two darts because during the loop of the split algorithm, we are going to split simultaneously the embedding surfaces and the topological faces. At last, we just initialize L, a list of edges, that we are going to use to store all the edges added to the combinatorial map.

After these initializations, we begin the loop on all the vertices of the separation face (Algorithm 2.2). First, we find the dart d of the embedding face incident to prevE that contains V i . Such a dart always exists because of the constraints fixed on the list of vertices. First a vertex is inserted in the edge incident to d with its coordinates given by V i , then an edge is inserted between the two darts prevE and d (they belong to the same face). We can