Dr A D'aléo

Dr A Bourdolle

Dr P L Baldeck

Dr C Andraud

Dr O Maury

Dr S Brustlein

Dr S Brasselet
email: sophie.brasselet@fresnel.fr

Dr A Grichine

Dr A Duperray

C Albrieux

N Duchamp

Henriques

Keywords: Biphotonic microscopy, NIR-to-NIR configuration, Lanthanide complex, Ytterbium complex, Bioimaging

1 NIR-to-NIR bioimaging DOI: 10.1002/anie.200((will be filled in by the editorial staff))

Ytterbium based Bioprobes for NIR-to-NIR Two Photon Scanning Laser Microscopy

Imaging. [ ** ]

Anthony D'Aléo, Adrien Bourdolle, Sophie Brustlein, Teddy Fauquier, Alexei Grichine, Alain Duperray, Patrice L. Baldeck, Chantal Andraud [ * ] , Sophie Brasselet [ * ] ,and Olivier Maury [ * ] This paper is dedicated to Dr. Hubert Le Bozec at the occasion of his 60 th birthday.

For decades, optical microscopy has been an essential tool for biological imaging, and more recently luminescence-based techniques have gained widespread utilization for medical analyses and diagnostics. [1] Conventional one-photon microscopy using commercial bio-probes or fluorescent proteins generally proceeds using excitation wavelength in the UV or visible and detection in the visible spectral range. These microscopy configurations will be referred to as UV-to-visible or visible-to-visible according to the excitation-to-detection spectral ranges. Since biological tissues strongly absorb and scatter UV-visible light, such configurations are restricted to surface bio-imaging experiments e.g. 2D cell imaging. On the other hand, the transparency of biological tissues in the near infra-red (NIR) between 700 and 1200 nm, a region called biological window, allows in-depth imaging in this spectral range. [2] Therefore, numerous academic and industrial research endeavors are currently focused on the improvement of microscopy techniques and on the design of new luminescent bio-probes featuring both excitation and emission in this NIR spectral range. Microscopy in this NIR-to-NIR configuration will enable in depth imaging in thick tissues and several bio-probes (cyanine, (aza)-bodipy) combining NIR excitation and emission have been developed and commercialized this last decade. [3] However in these cases, the small Stokes shift between the excitation and the optimal collection range of emitted light is a real technical drawback for microscopy because of the need to cleanly separate the emission from the excitation. Nonlinear biphotonic excitation, that is the simultaneous absorption of two photons of half energy typically in the NIR region, inherently introduces a larger Stokes shift and is therefore an elegant way to circumvent this drawback. [4] However, up to now, all the designed chromophores exhibit an emission in the visible spectral range, and the currently available biphotonic microscopes work in this two photon NIR-to-visible configuration with detection wavelength shorter than the incident laser one. [4,5] In this context, lanthanide complexes and particularly NIR emitters like ytterbium, and neodymium are known to exhibit very large pseudo-Stokes shift, [6a,b] and are therefore potentially well suited for such two photon NIR-to-NIR imaging purpose. In spite of their generally low luminescence quantum yield, such complexes have already been used for NIR bio-imaging applications but with a classical one photon excitation generally localized in the UV-visible up to 550-600 nm. [6,7] The sensitization of lanthanide luminescence by two-photon absorption is currently a challenging field of research but so far, most endeavors were focused on terbium and europium emitting in the green and red, respectively. [6a,8] With regard to NIR emitters, the proof of concept of ytterbium two-photon sensitization has been first described in the early 2000s by Lakowicz et al.. [9] Recently, Wong and co-workers have reported an ytterbium complex that exhibit exceptional luminescence properties in water with remarkable two-photon cross-section. [10] Interestingly, this complex was successfully used as bio-probe to image HeLa cells by two-photon microscopy technique, but working in the classical NIRto-visible configuration with detection in the residual ligand centered emission.

In this article, we report on the proof-of-concept of twophoton NIR-to-NIR microscopy. To that end, we designed water soluble ytterbium complexes, containing extended -conjugated skeleton suitable for two-photon excitation and meanwhile, we built up an unconventional two-photon NIR-to-NIR microscopy set-up.

The target complexes (Figure 1) need to fulfill some requirements to be used as bio-probe, ideally efficient two-photon antenna, high thermodynamical and kinetic stability and good photophysical properties. For initial spectroscopy and microscopy experiments, we chose to use the previously described [11] Yb 1 complex containing bis-PEGamino-(phenylethynyl)-dipicolinic ligands in spite of its limited water stability. [12] In a second time, the analogous macrocylic complex, Yb 2 based on the triazacyclononane plateform [13,14] was designed to increase the stability in biological medium (SI for synthetic details and characterizations). In both cases, the UV-visible absorption spectra exhibit a broad intense transition at 400 nm, assigned to an intraligand charge transfer transition (ILCT) from the dialkylamino donnor part to the chelated dipicolinic electron-withdrawing fragment (Figures 2 andS2). As already observed, [11] the steady-state luminescence spectra obtained by excitation in this ILCT transition is composed of two emission bands: (i) the characteristic ytterbium (III) emission, arising from the 2 F 5/2 → 2 F 7/2 (980 nm) transition in the NIR spectral range and (ii) the broad residual ILCT emission around 600 nm, indicating that the energy transfer to the central metal ion is not complete. The luminescence lifetime associated to the NIR transition was found to be perfectly mono-exponential, with a value of 0.34 and 3 s for Yb 1 and Yb 2 respectively (Figure S3), this later value being in the range of best complexes already reported in water. [10,[START_REF] Moore | For mono-metallic complexes see : a)[END_REF] The strong improvement between the two complexes Yb 1 and Yb 2 featuring similar antenna can be ascribed to the increased stability of the macrocyclic derivative. [13] Under fs-Ti:Sa laser irradiation in the 700-900 nm spectral range (Figure S4), an identical luminescence profile is obtained (Figure 2d) with NIR emission observed at a longer wavelength compared to that of the incident laser one (i.e. unusual spectral configuration for TPA induced luminescence with  det >  ex ). The quadratic dependence of both residual ILCT and Yb(III) emission intensity versus the laser power (Figure 2e) unambiguously established that the NIR Yb(III) emission is that sensitized by a two-photon antenna effect. The twophoton cross-sections could not be accurately determined due to the weak luminescence quantum yields of both residual ILCT and Yb(III) emissions (< 1%), and to the lack of calibration of the TPA experimental set-up in the NIR spectral range. However in a first approximation, these cross-sections should lie in the same range than that of the europium or lutetium analogous estimated to 775 and 500 GM at 740 nm, respectively. [11] Therefore the TPA-induced NIR emission of ytterbium is particularly interesting for in-depth bio-imaging experiments since both excitation (750-850 nm) and emission (980 nm) are localized in the biological transparency window (NIR-to-NIR configuration). Conventional one-and two-photon microscopy imaging experiments were carried out using commercially available epifluorescence and confocal microscopes with either a one-photon excitation in the visible or a two-photon excitation at 760 nm (fs-Ti:Sapphire laser). The complex Yb 1 was incubated with fixed T24 human cancer cells. The one-photon microscopy image (Figure 3a) reveals that the complex successfully stained the cell and localized preferentially in the perinulear areas or nucleoli as already observed for related europium complexes. [12] The conventional two-photon imaging experiments (Figure 3c) were carried out in the NIR-tovisible configuration using a visible detection at lower wavelength than the TPA excitation ( det <  ex ). As expected, this image is very similar to the one-photon one, but the signal-to-noise ratio is lower because the background fluorescence is dramatically reduced using a two-photon excitation. Unfortunately, it was not possible to record any image at the 950-1050 nm emission band since conventional biphotonic microscopes contain optical filtering schemes which do not allow the NIR-to-NIR configuration (that is detection of  det >  ex with both  ex and  det in the NIR range). Additionally, the sensitivity of the standard PMT detectors of the confocal microscope is very low at 980 nm. To tackle these limitations, we developed our own biphotonic microscopy set-up based on adequate optical filtering. The two-photon NIR-to-NIR imaging microscopy set-up (Figure 4a) consists in focusing an incident pulsed Ti-sapphire laser light (100 fs, 80 MHz, 760 nm wavelength) through a high numerical aperture objective (NA 1.15, water immersion). Images are formed using a galvalnometric scanning over typical regions of 100 m x100 m in the sample plane. To reject as much as possible the incident laser light in the detection channel around 1000 nm, the laser is reflected on a dichroic mirror which transmits the fluorescence emission in the epi descanned detection path. The emission is further filtered by two interference filters, and focused on an avalanche photodiode working in the photon counting mode. Validation experiments were first carried out using a thin film of Yb 1 spread on a glass plate as substrate (Figure 4b). Regions where the film is present are clearly visible with a high signal to background ratio comparing to the glass substrate. Both the spectrum of emission (Figure 4c) and the incident intensity dependence (Figure 4d) ascertain the detection of NIR light around 1000 nm in the two-photon mode.

As preliminary to the imaging experiments, the influence of this NIR-to-NIR configuration on the depth of penetration in a scattering sample was studied. To that end, the complex Yb 1 was dissolved in Intralipids solutions of different concentrations, mimicking the scattering ability of the biological media and irradiated by a biphotonic excitation. The variation of the normalized emission intensity in the visible (600 nm) and in the NIR (1000 nm) was measured simultaneously as a function of the depth of the incident laser focusing position (Figure 5a). As anticipated, the visible emission is more affected by scattering than the NIR one: at a depth of 100 m in a strongly scattering medium, almost no visible light is detected whereas more than 20 % of the NIR light remains available for imaging purpose. These data are in agreement with recent results comparing the influence of the detection wavelength for a given TPA excitation [16] both obtained in a classical TPA configuration ( ex >  det ). Note that the data shown in Figure 5 are normalized, and usually the NIR detection range exhibits fewer signal than in the visible range, due to the lower efficiency of both the imaging set-up and the luminescence quantum yield of the complex in this spectral range. Nevertheless, all these experiments unambiguously emphasize the interest of the NIR-to-NIR configuration for in-depth imaging purposes. In order to check the potentialities of this two photon NIR-to-NIR configuration, thick tissues imaging experiments were undertaken. Mouse brain capillary vessels were imaged in-depth using the Yb 2 as luminescent probes. [START_REF]No images could be obtained using Yb 1 as probe certainly due to its[END_REF] A phosphate buffer solution of the complex ([C] ~ 10 -4 mol.L -1 ) was directly perfused in the heart of a mouse. Brains were quickly dissected, post-fixed, and slices (100 m thickness) were cut and conserved between two glass plates. These mouse brain slices were successfully imaged using a biphotonic excitation ( ex = 760 nm) and the 3D blood capillary network is observed using the NIR-to-NIR configuration with a detection at 1000 nm (Figure 5b). This image was recorded at higher laser power to compensate for the lower imaging efficiency in this spectral range. Even though the recorded signal is weak for the reasons given above, it shows stained blood vessels with reasonable signal to noise ratio up to 80 m depths in strongly scattering samples. The integration time of 50 s per pixel, which is essentially chosen to ensure a high signal to noise ratio, could be even more increased to reach larger imaging depth. This would lead to longer time scales imaging, however it is possible to reach faster dynamics by using a higher incident power. This result therefore unambiguously establishes the proof-of-concept of two-photon NIRto-NIR imaging.

In conclusion, this article demonstrates the feasibility of indepth imaging of strongly scattering thick tissue e.g., the vascular network of mouse brain, by two-photon scanning microscopy in an unprecedented NIR-to-NIR configuration. To that end, we developed a new biphotonic set-up and we designed a macrocyclic ytterbium complex functionalized by two-photon antenna combining appropriate stability and efficiency in water. Further studies are currently conducted to improve the two-photon brightness of such probes and to expand the scope of this NIR-to-NIR biphotonic microscope.

Experimental Section

Synthetic procedures and characterizations, spectroscopic and microscopic experimental details and biological samples preparation are described in supporting information. The design and photophysical characterization of a new highly stable macrocyclic ytterbium complex featuring two-photon antenna ligand is described. The biphotonic sensitization of the NIR Yb(III) luminescence and the conception of an unconventional NIR-to-NIR biphotonic microscope allow performing in-depth imaging of thick tissues.

Entry for the Table of Contents

NIR-to-NIR bioimaging

General. 4-ethynyl-N,N bis (2-(2-(2-methoxyethoxy)ethoxy)ethyl)aniline ( 1), 1 and methyl 6-(hydroxymethyl)-4-iodopicolinate (2) 2 were prepared following the published procedures, all other starting materials were commercially available. All solvents for synthesis were analytic grade. NMR spectra ( 1 H, 13 C) were recorded at room temperature on a BRUKER Advance operating at 500.10 MHz and 125.75 MHz for 1 H and 13 C, respectively. Data are listed in parts per million (ppm) and are reported relative to tetramethylsilane ( 1 H, 13 C); residual solvent peaks of the deuterated solvents were used as internal standard. UV/Vis absorption measurements were recorded on an absorption spectrometer JASCO V670. Low resolution mass spectrometry was carried out on an Agilent 1100 Series LC/MSD apparatus.

The ligand under its trimester form (5) was analyzed by RP-HPLC using a Waters Alliance 2695 system coupled with Waters 996 photodiode array detector and Micromass ZQ Waters 2000 mass spectrometer.

Procedure developed was 0.1% formic acid in water / acetonitrile as mobile phase using XBridgeTM C18, 3.5 µm, 4.6 × 100 mm as column. High resolution Mass spectrometry (HRMS) was performed using a Bruker MicroTOF-Q II, apparatus (precision 1-5 ppm) equipped with an electrospray source using highly diluted samples (1-2 mg/ mL) in a methanol/dichloromethane/water/formic acid mixture (46.1/38.4-15.4-0.1 v/v).

3.

In a 100 mL schlenk flask under argon, 1 (1.100 g, 2.68 mmol, 1.3 eq) and 2 (590 mg, 2.01 mmol, 1 eq) were dissolved in a mixture of THF (20 mL) and triethylamine (20 mL). After degassing by argon bubbling, PdCl 2 (PPh 3 ) 2 (141 mg, 0.201 mmol, 0.1 eq) and copper iodide (76 mg, 0.402 mmol, 0.2 eq) were added. The solution was stirred at RT for 20 h. The solution volume was extended to 100 mL by addition of THF, filtered, and solvents were evaporated. The residue was dissolved in DCM (50 mL) washed with saturated NH 4 Cl (2 × 100 mL), water (100 mL), and dried (Na 2 SO 4 ). After evaporation of the solvents under vacuum, the crude product was purified by chromatography (ethyl acetate / methanol 98/2) yielding the desired product as a yellow oil (620 mg, 1.65 mmol, 82 %). 56, 160.37, 148.90, 147.20, 134.64, 133.74, 125.68, 125.07, 111.65, 108.05, 97.86, 72.12, 70.93, 70.86, 70.79, 68.53, 64.72, 59.25, 53.12, 51.03.

4.

In a 50 mL round bottom flask under argon, 3 (300 mg, 0.52 mmol, 1 eq) was dissolved in THF (20 mL) and triethylamine (157 mg, 1.56 mmol, 3eq) and the mixture was cooled down to 0°C. A solution of methanesulfonyl chloride (72 mg, 0.63 mmol, 1.2 eq) in THF (5 mL) was added dropwise and the mixture was stirred at RT for 2 h. After epavoration of the solvent, the residue was dissolved in dichloromethane (50 mL), washed with water (3 x 100 mL), and dried (Na 2 SO 4 ). After evaporation of the solvents under vacuum, the crude product was purified by chromatography (ethyl acetate / methanol 98/2) to afford the desired product as a yellow oil (254 mg, 0.39 mmol, 75 %). 1 H-NMR (500,10 MHz, CDCl 3 ): 8.09 (d,4 J = 1.4 Hz,1H),7.64 (d,4 J = 1.4 Hz, 1H), 7.37 (d, 3 J = 9.1 Hz, 2H), 6.67 (d,3 J = 9.1 Hz,2H),5.37 (s,2H),3.98 (s,3H),3.6 (m,20H),3.51 (m,4H),3.35 (s,6H),3.13 (s,3H); CDCl 3 ): δ 165.22,154.52,149.03,147.90,135.40,133.85,126.61,126.21,111.71,99.02,84.92,72.11,70.97,70.93,70.85,70.79,68.51,59.24,53.29,51.06,38.26. LRMS: m/z = 653 [M+H] + , 675 [M+Na] + 5. To a solution of TACN,3HCl (21 mg, 0.16 mmol, 1 eq) in dry MeCN (20 mL) was added the mesylate derivative 4 (430 mg, 0.66 mmol, 4 eq), sodium iodide (23 mg, 0.16 mmol, 1eq) and dry Na 2 CO 3 (52 mg, 0.49 mmol, 3 eq). The resulting mixture was heated at reflux for 6 d and then filtered off. The filtrate was concentrated in vacuo and the oily residue was partitioned between water (50 mL) and CH 2 Cl 2 (50 mL).

The aqueous layer was extracted with CH 2 Cl 2 (2 × 25 mL). The organic phases were combined, dried over Na 2 SO 4 filtered and concentrated in vacuo. The crude material was purified by flash chromatography (DCM/Acetone/Methanol/Water 78/10/10/2 then 67/15/15/3) yielding a yellow oil (151 mg, 0.08 mmol, 51%). 1 H-NMR (500.10 MHz, CDCl 3 ): 7.97 (s, 3H), 7.33 (s, 3H), 7.24 (d, 3 J = 8.9 Hz, 6H), 6.64 (d, 3 J = 8.9 Hz, 6H), 4.29 (s, 6H), 3.88 (s, 9H), 3.60 (m, 60H), 3.51 (m, 12H), 3.34 (s, 18H), 3.28 (s, 12H). 13 C-NMR (125.75 MHz, CDCl 3 ): 165. 1, 156.5, 148.8, 147.6, 134.7, 133.7, 128.0, 126.0, 111.4, 107.7, 98.5, 84.8, 71.9, 70.8, 70.7, 70.6, 68.4, 60.9, 59.1, 52.9, 50. L 2 : To a solution of triester precursor 5 (110 mg, 0.060 mmol) in EtOH (15 mL) was added a NaOH 6M aqueous solution (15 mL) and the mixture was stirred at RT for 1 h. The organic solvent was evaporated, the aqueous phase was extended to 50 mL, and extracted with EtOAc (2 × 25 mL). After acidification to pH 1-2 (HCl (10%) solution), a second extraction was carried out with CH 2 Cl 2 (3 × 25 mL). The organic phases were combined, dried over Na 2 SO 4 , filtered and concentrated in vacuo. The desired product is obtained as a yellow solid and was further engaged in the next step without further purification (100 mg 0.055mmol, 93%).

Yb 2 : To a suspension of free ligand L 2 (100 mg, 0.055 mmol, 1 eq) and K 2 CO 3 (24 mg, 0.17 mmol, 3.1 eq) in dry MeCN (60 mL) was added YbCl 3 .6H 2 O (21 mg,0.17 mmol, 3 eq). The solution was heated at 50°C for 12 h under inert atmosphere. The mixture was then cooled down to room temperature, filtered off and the filtrate was concentrated in vacuo. Purifications of the complexes were carried out by dialysis in water. After dialysis, the aqueous solution was extracted with dichloromethane (3 x 20 mL). The organic phases were combined, dried over Na 2 SO 4 , filtered and concentrated in vacuo yielding the desired complex as an orange solid (99 mg, 0.051 mmol, 91%). UV-vis (H 2 O)  max = 364 nm ( =34500 L.mol - 1 .cm -1 ),  = 400 nm ( =31000 L.mol -1 .cm -1 ); HRMS m/z: [C 93 H 127 N 9 O 24 Yb] + = 1927.8341 (calcd. 1927.8381). Luminescence. The luminescence spectra were measured using a Horiba-Jobin Yvon Fluorolog-3® spectrofluorimeter, equipped with a three slit double grating excitation and emission monochromator with dispersions of 2.1 nm/mm (1200 grooves/mm). The steady-state luminescence was excited by unpolarized light from a 450W xenon CW lamp and detected at an angle of 90° for diluted solution measurements (10 mm quartz cuvette) by a red-sensitive Hamamatsu R928 photomultiplier tube. Spectra were reference corrected for both the excitation source light intensity variation (lamp and grating) and the emission spectral response (detector and grating). Uncorrected near infra-red spectra were recorder using a liquid nitrogen cooled, solid Indium/Gallium/Arsenic detector (850-1600 nm). For luminescence lifetimes, the sample was excited using a pulsed Nd:YAG laser (SpectraPhysics), operating at 10 Hz. Light emitted at right angles to the excitation beam was focused onto the slits of a monochromator (PTI120), which was used to select the appropriate wavelength. The growth and decay of the luminescence at selected wavelengths was detected using a germanium photodiode (Edinburgh Instruments, EI-P) and recorded using a digital oscilloscope (Tektronix TDS320) before being transferred to a PC for analysis.

Luminescence lifetimes were obtained by iterative reconvolution of the detector response (obtained by using a scatterer) with exponential components for growth and decay of the metal-centered luminescence, using a spreadsheet running in Microsoft Excel.

Two-photon excited luminescence measurements. The TPA cross-section spectrum was obtained by up-conversion luminescence using a Ti:sapphire femtosecond laser in the range 700-900 nm. The excitation beam (5 mm diameter) is focalized with a lens (focal length 10 cm) at the middle of the 10-mm cell. Emitted light was collected at 90° and was focused into an optical fiber (diameter 600 m)

connected to an Ocean Optics S2000 spectrometer. The incident beam intensity was adjusted to 50 mW in order to ensure an intensity-squared dependence of the luminescence over the whole spectral range. The Mice brain preparation. 8-weeks old C57BL/6 mice obtained from our breeding facility were deeply anesthetized before being intracardiacally perfused with Yb 2 dissolved in 0.1M phosphate buffer (PB, pH 7.4) (10 mL, c = 10 -4 M). After perfusion, brains were quickly dissected and post-fixed for 4 hours in 4% paraformaldehyde (in 0.1M PB) and washed 3 times in Phosphate-buffered saline (pH 7.4). 100µm-thick brain slices were made using a a Vibratome (Integraslice 7550 PSDS, Campden Instruments), and stored in PBS until imaging was performed.

NIR-to-NIR Microscopy set up and validation. Two-photon NIR-to-NIR microscopy imaging was performed using a femto-second tunable Ti:sapphire laser (100 fs, 80 MHz) excitation source, which the excitation wavelength fixed at 760 nm. This wavelength is the best compromise between the maximum of excitation for the molecule and the better signal to background obtained after rejection of the incident laser light.

The excitation was reflected on a dichroic beamsplitter (FF720-SDi01, Semrock) with short and long wave pass capability (transmission around 1000nm: 65%). The beam was then focused by a high numerical aperture objective (NA 1.15, x40) (Nikon), also used to collect the two-photon epifluorescence signal from the sample. The emission, detected by avalanche photodiodes, was first reflected on an interference filter tilted at 45° (800DF50, Omega Optical) and furthermore filtered spectrally around 1000 nm in order to avoid any scattering light from the incident laser (1000DF50, Omega Optical).

The image of the sample was performed by galvanometric scanning, with a rate of typically one image every 1 to 2 seconds. The image was obtained by a descanning of the signal through the objective and galvanometric mirrors. The separation of the incident and detected beams was done before the galvanometric mirrors by the FF720-SDi01 dichroic beamsplitter.

The position of the focus position was controlled using a piezo-electric holder for the objective. A spectrum of emission could also be measured using a spectrometer at the exit of the microscope.

Penetration depth measurements on Intralipids

Intralipids solutions of different concentration (10%, 15%, 20%) were prepared from a Intralipids-20% stock solution (Intralipid TM Kabivitrum Inc.) diluted in

Figure 1 .

 1 Figure 1. Structure of the target complexes.

Figure 2 .

 2 Figure 2. Photophysical data of Yb 1 in water solution: (a) absorption spectrum (scale on the left), (b) residual CT fluorescence and (c): NIR emission ( ex = 380 nm) (scale on the right), (d): Uncorrected two photon induced luminescence spectrum ( ex = 760 nm) (scale on the right). Inset (e) variation of the two-photon luminescence intensity with the incident laser power at 573 nm (■) and 981 nm (•).

Figure 3 .

 3 Figure 3. Imaging of the fixed cells stained with Yb 1 using a conventional microscope: (a) one photon imaging using inverted wide field microscope ( ex = 450-490 nm, visible detection) (b) one-and two-photon emission spectra; (c) two-photon NIR-to-visible imaging laser scanning microscope,( ex = 760 nm, 491-673 nm detection).

Figure 4 .

 4 Figure 4. (a) Experimental setup for two photon NIR-to-NIR imaging. O: objective; T: telescope; M: protected silver mirror; GM: galvanometric mirrors; D760: dichroic mirror (FF720-SDi01, Semrock); F800 and F1000: interference filters (800DF50 and 1000DF50, Omega Optical); L: lens; APD: Avalanche Photodiode. (b), imaged two-photon imaging. (b) Two-photon scanning image of a thin film of Yb 1 on a glass substrate, using a 1000 nm detection wavelength. (c) Spectrum measured in a bright region of the image of (b) (a high pass filter at 850 nm is used before the spectrometer). (d) Incident power dependence of the fluorescence signal recorded in the 1000 nm spectral detection range.

Figure 5 .

 5 Figure 5. a) Variation of the normalized luminescence intensity of Yb 1 at 610 nm (green) or 1000 nm (red) with the depth of the 760 nm TPA excitation in two Intralipids solutions of different concentrations (10%, 15%, 20%) mimicking different scattering strengths. b) Biphotonic scanning microscopy 3D imaging using the home made set-up ( ex = 760 nm) of mouse brain slice stained with Yb 2 with detection at 1000 nm (incident power 25mW). Sections of the 3D images of the aforementioned image.

  A. D'Aléo, A. Bourdolle, S. Brustlein, T. Fauquier, A. Grichine, A. Duperray, P. L. Baldeck, C. Andraud*, S. Brasselet*,

  1 H-NMR (500,10 MHz, CDCl 3 ): δ 8.02 (d, 4 J = 1.4 Hz, 1H), 7.52 (d, 4 J = 1.4 Hz, 1H), 7.35 (d, 3 J = 9.5 Hz, 2H), 6.65 (d, 3 J = 9.5 Hz, 2H), 4.81 (d, 3 J = 5 Hz, 2H), 3.97 (s, 3H), 3.6 (m, 21H), 3.51 (m, 4H), 3.35 (s, 6H); 13 C-NMR (125.75 MHz, CDCl 3 ): δ 165.

  9. HRMS m/z: [C 96 H 136 N 9 O 24 ] + = 1798.9631 (calcd. 1798.9693).

Figure S1 .

 S1 Figure S1. Semi-preparative HPLC chromatogram analysis of 5 (retention time, rt = 11.44 min).

Figure S2 .

 S2 Figure S2. Absorption (…) and emission (-,  ex = 365 nm) spectra of Yb 2 (black) and Yb 1 (red) in diluted water solution. (*) Water scattering peak.

Figure S3 .Figure S4 .

 S3S4 Figure S3. Experimental emission decay at 1000 nm for Yb 2 in water solution ( ex =400 nm, ■). The best fit to a single exponential decay is shown in red, the decay is perfectly mono-exponential confirming that only one species is present under these conditions.

  photobleaching was induced during image acquisition.Biological samples. T24 cells (a bladder carcinoma cell line, ATCC HTB-4) were cultured in RPMI 1640 medium supplemented with 10% fetal bovine serum and antibiotics. For imaging experiments, T24 cells were seeded at low density on 2-well Lab-Tek Chambered Coverglass (Dominique Dutscher, Brumath, France) grown for 24h until the ca. 70% confluence before being fixed for 10min with Ethanol 100% at -20°C, washed twice with PBS and incubated with Yb 1 ca. 2.10 -5 M) for 40 min. Fixed cells conserve the appearance of living cells but possess more permeable cell membrane.

(e) log(I) log(P)

Supporting information for:

Ytterbium based Bioprobes for NIR-to-NIR Two Photon Scanning Laser Microscopy Imaging.

Anthony D'Aléo, Adrien Bourdolle, Sophie Brustlein, Teddy Fauquier, Alexei Grichine, Alain Duperray, Patrice L. Baldeck, Chantal Andraud, Sophie Brasselet, and Olivier Maury Synthesis Scheme S1: Synthesis of the ligand L 2 and related Yb 2 complex pure water. The Yb 1 complex was dissolved in the Intralipids solutions with a typical concentration of 10 - 4 M. A drop of the solution was directly deposited on a microscope coverslip. The initial focus (Z = 0 m) was set at the interface between glass and solution. The focus was then controlled such as so enter progressively in the solution with 500 nm steps in the Z depth direction, recording the signal until a depth of Z = 300 m.

NIR-to-NIR imaging in thick tissue slices from stained mouse brains. The tissue slice was directly positioned between glass slide and coverslip. Z-stacks images were obtained by performing an image every Z = 1 m depth penetration step in the sample. Images of 100 m x 100 m were obtained with a sampling of 200 x 200 pixels, with an integration time of 50 µs per pixel, which leads to an imaging rate of about 1 image every 2 seconds. 3 accumulations per images were performed to ensure a correct signal to noise ratio. The incident power (760 nm incident wavelength) at the entrance of the microscope was set at 40 mW for the 610 nm detection wavelength and increased to 250 mW for 1000 nm detection. This leads to powers around respectively 4 mW and 25 mW at the focal spot of the objective. These powers were still low enough to not induce photodamage to the sample.


Loic Le Gratiet
email: loic.le-gratiet@cea.fr

Claire Cannaméla
email: claire.cannamela@cea.fr

Josselin Garnier

Planification d'exp ériences s équentielle dans un contexte de m éta-mod élisation multi-fid élit é. Sequential experimental design in a multi-fidelity computer experiment framework

Résumé. Les gros codes de calcul sont souvent utilisés en ingénierie pour étudier des systèmes physiques. Cependant, les simulations peuvent parfois être coûteuses en temps de calcul. Dans ce cas, une approximation de la relation entrée/sortie du code est souvent faite à l'aide d'un méta-modèle. En fait, un code de calcul peut souvent être lancé à différents niveaux de complexité et une hiérarchie de niveaux de code peut donc être obtenue. Il peut s'agir par exemple d'un modèle éléments finis ayant un maillage plus ou moins fin. L'objectif de nos travaux est d'étudier l'utilisation de plusieurs niveaux de code pour prédire la sortie d'un code coûteux. Le méta-modèle multi-niveaux présenté ici est un cas particulier du co-krigeage. Après avoir détaillé le modèle de co-krigeage utilisé et sa mise en place, nous concentrerons notre présentation sur les stratégies de planification d'expériences séquentielles. En effet, un avantage du co-krigeage est qu'il fournit, au travers de la variance de co-krigeage, une estimation de l'erreur de modèle en chaque point de l'espace des paramètres d'entrée. Ainsi, pour améliorer la précision du méta-modèle on peut enrichir séquentiellement notre base d'apprentissage aux points où la variance est la plus grande. Cependant, dans un cadre de multi-fidélité, il faut également choisir sur quel niveau de code on veut connaître la réponse. Nous présenterons ici différentes stratégies pour choisir ce niveau basées sur un résultat original qui donne la contribution de chaque code à la variance de prédiction du modèle.

Mots-clés. co-krigeage, méta-modélisation multi-fidélité, plan d'expériences, stratégie séquentielle.

Abstract.Large computer codes are widely used in engineering to study physical systems. Nevertheless, simulations can sometimes be time-consuming. In this case, an approximation of the code input/output relation is made using a metamodel. Actually, a computer code can often be run at different levels of complexity and a hierarchy of levels of code can hence be obtained. For example, it can be a finite element model with a more or less fine mesh. The aim of our research is to study the use of several levels of a code to predict the output of a costly computer code. The presented multi-stage metamodel is a particular case of co-kriging which is a well-known geostatistical method. We first describe the construction of the co-kriging model and we focus then on a sequential experimental design strategy. Indeed, one of the strengths of co-kriging is that it provides through the predictive co-kriging variance an estimation of the model error at each point of the input space parameter. Therefore, to improve the surrogate model we can sequentially add points in the training set at locations where the predictive variances are the largest ones. Nonetheless, in a multi-fidelity framework, we also have to choose which level of code we have to run. We present here different strategies to choose this level. They are based on an original result which gives the contribution of each code on the co-kriging variance.

Keywords. surrogate models, co-kriging, multi-fidelity computer experiment, experimental design, sequential strategy.

Introduction

Le krigeage est une classe particulière de méta-modèle qui fait l'hypothèse a priori que la sortie que l'on essaye d'approcher est une réalisation d'un processus Gaussien. On se concentre ici sur ce modèle et son extension pour les sorties à réponses multiples. Le lecteur pourra se référer aux livres de Santner, Williams et Notz (2003) et [START_REF] Rasmussen | Gaussian Processes for Machine Learning[END_REF] pour plus de détails sur le krigeage. Dans le cadre des simulateurs multifidélités, nous possédons un code qui peut être lancé à plusieurs niveaux de précision. Ces niveaux pouvant par exemple correspondre à différentes tailles de mailles pour un code éléments finis. L'objectif de la méta-modélisation sera de construire une surface de réponse du code en utilisant une ou plusieurs de ses versions dégradées. 2007) ont présenté l'utilisation du co-krigeage dans un cadre d'optimisation (basée sur l'algorithme EGO : Efficient Global Optimization). Enfin, certains points limitant de la méthode ont été résolus dans le papier Le Gratiet (2011) qui présente entre autres une procédure d'estimation efficace des paramètres, une réduction de la complexité du modèle et une nouvelle approche Bayésienne évitant une implémentation prohibitive. Dans les papiers ci-dessus, différentes méthodes de planification d'expériences ont été proposées mais aucun auteur ne s'est intéressé à la planification d'expériences séquentielle. Pourtant la hiérarchie de codes disponible peut nous permettre de mettre en place des stratégies intéressantes de planification séquentielle. La question sera la suivante : si nous voulons lancer une simulation en un nouveau point, sur quel niveau de code allons-nous la lancer ? Il va donc falloir trouver le meilleur compromis coût / précision et nous allons pour cela utiliser un résultat utile déduit de Le Gratiet (2011).

2 Construction du méta-modèle multi-fidélité.

Nous présentons ici une nouvelle modélisation multi-niveaux qui est équivalente à celle proposée par [START_REF] Kennedy | Predicting the output from a complex computer code when fast approximations are available[END_REF] et qui se construit de manière récursive.

2.1 Rappels des équations du modèle AR(1) étendues au cas s niveaux.

Supposons que nous ayons s niveaux de code modélisés par des processus Gaussiens (Z t (x)) t=1,...,s , x ∈ Q, classés par ordre croissant de précision et tels que :

   Z t (x) = ρ t-1 (x)Z t-1 (x) + δ t (x) Z t-1 (x) ⊥ δ t (x) ρ t-1 (x) = g T t-1 (x)β ρ t-1 (1)
où l'on définit ∀t = 2, . . . , s :

δ t (x) ∼ PG(f T t (x)β t , σ 2 t r t (x, x ′ )) (2)
et :

Z 1 (x) ∼ PG(f T 1 (x)β 1 , σ 2 1 r 1 (x, x ′ )) (3)
On fait donc ici l'hypothèse a priori que les sorties des codes sont des réalisations de processus Gaussiens. Le méta-modèle sera construit en conditionnant ces réalisations par les sorties connues des codes.

La modèlisation précédente issue de l'article de Kennedy et O'Hagan (2000) définit la relation entre les niveaux de codes. Elle est déduite de l'hypothèse suivante : ∀x, si on se donne la valeur de Z t-1 (x), on ne peut rien apprendre de plus sur Z t (x) à partir des autres résultats Z t-1 (x ′ ) pour x = x ′ . Soit Z = (Z T 1 , . . . , Z T s ) T le vecteur Gaussien contenant le valeurs des processus (Z t (x)) t=1,...,s aux points des plans d'expériences (D t ) t=1,...,s avec

D s ⊆ D s-1 ⊆ • • • ⊆ D 1 . Si on note β = (β T 1 , . . . , β T s ) T , β ρ = (β T ρ 1 , . . . , β T ρ s-1 ) T , σ 2 = (σ 2 1 , . . . , σ 2
s ) et z = (z 1 , . . . , z s ) les réponses connues des codes, on a :

∀x ∈ Q [Z s (x)|Z = z, β, β ρ , σ 2 ] ∼ N m Zs (x), s 2 Zs (x) où : m Zs (x) = h ′ s (x) T β + t s (x) T V -1 s (z -H s β) (4)
et :

s 2 Zs (x) = σ 2 Zs (x) -t s (x) T V -1 s t s (x) (5)
La moyenne de co-krigeage m Zs (x) constituera le méta-modèle sur le niveau le plus précis construit à partir des réponses connues sur les s niveaux de code et la variance de co-krigeage s 2 Zs (x) donnera une estimation de l'erreur de modèle.

La matrice V s représente la matrice de covariance du vecteur Gaussien Z, le vecteur t s (x) est le vecteur de covariance entre Z s (x) et Z, H s β est la moyenne de Z, h ′ s (x) T β est la moyenne de Z s (x) et σ 2 Zs (x) sa variance. Tous ces éléments sont construits à partir du vecteur d'expériences au niveau t et de la covariance entre Z t (x) et Z t ′ (x ′ ) explicités ci-dessous :

h ′ t (x) T = t-1 i=1 ρ i (x) f T 1 (x), t-1 i=2 ρ i (x) f T 2 (x), . . . , ρ t-1 (x)f T t-1 (x), f T t (x) (6) et pour t > t ′ : cov(Z t (x), Z t ′ (x ′ )|σ 2 , β, β ρ ) = t-1 i=t ′ ρ i (x) cov(Z t ′ (x), Z t ′ (x ′ )|σ 2 , β, β ρ ) (7) avec : cov(Z t (x), Z t (x ′ )|σ 2 , β, β ρ ) = t j=1 σ 2 j t-1 i=j ρ 2 i (x) r j (x, x ′ ) (8)

Ecriture récursive du modèle AR(1)

Nous allons ici présenter une nouvelle modélisation multi-niveaux qui est en fait équivalente à la précédente. Considérons la modélisation suivante pour t = 2, . . . , s :

   Z t (x) = ρ t-1 (x)[Z t-1 (x)|Z t-1 = z t-1 ] + δ t (x) Z t-1 (x) ⊥ δ t (x) ρ t-1 (x) = g T t-1 (x)β ρ t-1 (9) avec D s ⊆ D s-1 ⊆ • • • ⊆ D 1 .
La seule différence avec la précédente modélisation est que l'on exprime Z t (x) (le processus Gaussien modélisant le code de niveau t) en fonction du processus Z t-1 (x) conditionné par ses réponses connues z t-1 sur le plan D t-1 . Les (δ t (x)) t=2,...,s sont définis comme précédemment et on a pour tout t = 2, . . . , s :

Z t (x)|Z t = z t ∼ N µ Zt (x), s 2 Zt (x) (10)
où :

µ Zt (x) = ρ t-1 (x)µ Z t-1 (x) + f T t (x)β t + r T t (x)R -1 t z t -ρ t-1 (D t ) ⊙ z t-1 (D t ) -F t β t (11) et : s 2 Zt (x) = ρ 2 t-1 (x)s 2 Z t-1 (x) + σ 2 t 1 -r T t (x)R -1 t r t (x) (12)
Le symbole ⊙ représente le produit matriciel élément par élément. R t est la matrice de correlation de D t avec le noyau r t (x, x ′ ) et r T t (x) est le vecteur de covariance entre x et D t avec ce même noyau. On note ρ t (D t-1 ) le vecteur contenant les valeurs de ρ t (x) pour x ∈ D t-1 , z t (D t-1 ) celui contenant les sorties connues de Z t (x) sur D t-1 et F t est la matrice d'expériences contenant les valeurs de f t (x) T sur D t .

La moyenne µ Zt (x) constitue le méta-modèle sur le code de niveau t sachant les réponses connues des t premiers niveaux de code et la variance s 2 Zt (x) représente l'erreur de ce modèle. La moyenne et la variance de co-krigeage sur le niveau t s'exprimant à partir de celles du niveau t -1, on a bien une expression récursive du modèle proposé par [START_REF] Kennedy | Predicting the output from a complex computer code when fast approximations are available[END_REF]. La modélisation proposée ici est puissante car elle montre que construire un co-krigeage à s niveaux est équivalent à construire s krigeages indépendants.

Planification d'expériences séquentielle pour le cokrigeage

La modélisation récursive présentée précédemment va nous permettre de construire une méthode simple de planification d'expériences séquentielle. Nous travaillerons sur un des principaux critères de planification séquentielle utilisés dans le krigeage : le MSE (Mean Squarred Error). La stratégie consiste simplement à trouver le point maximisant la variance de prédiction s'écrivant :

s 2 Zt (x) = ρ 2 t-1 (x)s 2 Z t-1 (x) + σ 2 t 1 -r T t (x)R -1 t r t (x) ∀t = 2, . . . , s s 2 Z 1 (x) = σ 2 1 1 -r T 1 (x)R -1 1 r 1 (x) Soit x = argmax x s 2
Zs (x). On a alors ∀t = 1, . . . , s :

s 2 Zt (x) = ρ 2 t-1 (x)s 2 Z t-1 (x) + σ 2 t 1 -r T t (x)R -1 t r t (x)
Supposons que l'on décide de lancer le code t -1 en x, on a alors s 2 Z t-1 (x) = 0 et :

s 2 Zt (x) = σ 2 t 1 -r T t (x)R -1 t r t (x) ρ 2 t-1 (x)s 2 Z t-1 (
x) représente donc la part de la variance due au code de niveau t -1 et σ 2 t 1r T t (x)R -1 t r t (x) représente la part de la variance due au code de niveau t. Une stratégie naturelle de planification d'expériences est alors de trouver le point x maximisant la variance, de regarder la part de chaque niveau de code sur s 2 Zs (x) et de lancer une simulation sur le niveau de code le plus intéressant (selon un critère coût/précision qui dépendra du cas d'application).

Il est donc nécessaire de construire un critère qui nous permette de déterminer quel niveau de code est le plus intéressant. Nous illustrons dans ce résumé, une méthode pour choisir ce niveau dans le cas s = 2. On introduit pour cela la moyenne de la variance de prédiction (où µ(x) représente la mesure de la loi des entrées) : imse = Q s 2 Z 2 (x) dµ(x) Considérons x = argmax x s 2 Z 2 (x), dans le cas à 2 niveaux nous pouvons lancer soit z 1 (x) soit z 2 (x). Supposons que l'on connaisse z 1 (x), on aura alors :

s 2 Z 2 (x) = σ 2 2 1 -r T 2 (x)R -1 2 r 2 (x) Si s 2
Z 2 (x) < imse cela signifie que l'erreur de modèle en x est inférieure à l'erreur de modèle moyenne. Il n'est donc pas nécessaire de lancer le code de niveau 2 en ce point car cela n'apportera pas en moyenne plus d'information qu'un autre point. En revanche, si s 2 Z 2 (x) > imse, cela signifie que l'erreur de modèle en x est plus importante que l'erreur moyenne et il sera donc avantageux de lancer le code de niveau 2 en ce point.

Références

  Un premier méta-modèle multi-niveaux a été mis en place par Kennedy et O'Hagan (2000) en utilisant une relation autorégressive d'ordre 1 entre deux niveaux successifs. Ce modèle est un cas particulier du co-krigeage qui est une méthode communément utilisée en géostatistique. Ensuite, Qian et Wu (2008) ont proposé une approche Bayésienne du modèle suggéré par Kennedy et O'Hagan (2000) et Forrester, Sobester et Keane (


Fast Precomputed Ambient Occlusion for Proximity Shadows

Résumé : L'Ambient Occlusion est fréquemment utilisée pour améliorer le réalisme de simulations de l'éclairage en temps-réel. Nous présentons une nouvelle méthode pour stocker l'Ambient Occlusion. Cette méthode est simple et efficace, et n'utilise que très peu de ressources CPU et GPU. Elle peut être utilisée pour stocker et récupérer, soit le pourcentage d'occlusion seulement, soit le pourcentage d'occlusion combiné avec la direction moyenne de l'obstacle. La première méthode est moins couteuse en mémoire, mais la deuxième permet des calculs plus précis, en particulier lorsqu'on combine plusieurs obstacles ensemble. Notre algorithme est indépendant de la complexité, tant des obstacles que de la scène, ce qui en fait un algorithme très pratique pour les jeux et les applications temps-réel.

Introduction

In illumination simulations, it has long been customary to add an "ambient term", to account for the light that remains after secondary diffuse reflections. The ambient term illuminates areas of the scene that would not otherwise receive any light. But ambient light is a uniform light: it illuminates all points on all objects, regardless of their shape or position. This gives objects illuminated mostly with ambient light an unnatural look, flattening their features.

To counter this effect, ambient occlusion was introduced by Zhukov et al. [START_REF] Zhukov | An ambient light illumination model[END_REF]. For every point in the scene, the accessibility to ambient lighting is computed and used to modulate the ambient light. Ambient occlusion is widely used in special effects for motion pictures [START_REF] Landis | Production ready global illumination[END_REF] and for illumination simulations in commercial softwares [START_REF] Christensen | Note 35: Ambient occlusion, image-based illumination, and global illumination[END_REF][START_REF] Christensen | Global illumination and all that[END_REF].

As a positive side effect, using ambient occlusion results in objects having contact shadows: when an object is close to another object, the ambient occlusion creates the shadow of the first object onto the second (see Fig. 1).

In early methods, ambient occlusion was precomputed at each vertex of the model, and stored either as vertex information or into a texture. In recent work [ZHL * 05, KL05], targeting real-time rendering for video games, precomputed ambient occlusion is stored as a field around a moving object, and projected onto the scene as the object moves. Both these methods provide important visual cues on the relative positions of the moving object, in real-time, at the expense of storing extra information.

Both these methods pre-process ambient occlusion, expressing it as a function of space, whose parameters are stored in a 2D texture wrapped around the object. In contrast, we suggest storing it un-processed, in a 3D grid attached to the object. The benefits are numerous:

• faster run-time computations, and very low impact on the GPU, with a computational cost being as low as 5 fragment shader instructions per pixel,

• very easy to implement, just by rendering one cube per shadow casting object,

• shorter precomputation time,

• handles both self-occlusion and inter-object occlusion in the same rendering pass. In particular, the inter-object occlusion has high quality even for receiving points inside the occluding object's convex hull.

• easy to combine with indirect lighting stored in environment maps.

The most obvious drawback should be the memory cost, since our method's memory costs are in O(n 3 ), compared to O(n 2 ) for earlier work [ZHL * 05, KL05]. But ambient occlusion is a low frequency phenomenon, stored in low resolution textures. In [START_REF] Kontkanen | Ambient occlusion fields[END_REF], as in our own work, a texture size of n = 32 is sufficient. And since we are storing a single component per texel, compared to several function coefficients, the overall memory cost of our algorithm is comparable to theirs. For a texture size of 32 pixels, Kontkanen and Laine [START_REF] Kontkanen | Ambient occlusion fields[END_REF] report a memory cost of 100 Kb for each unique moving object. For the same resolution, the memory cost of our algorithm is of 32 Kb if we only store ambient occlusion, and of 128 Kb if we also store the average occluded direction.

We present our method for storing and retrieving ambient occlusion values, with two applications: one where we only store and retrieve ambient occlusion values, and one where we also store the average unoccluded direction. The former is cheaper in memory costs, but the latter is more accurate, takes into account the normal at the receiving point and we show how to use it to compute the combined effects of several occluders and lighting from an environment map.

Background

Ambient light is used as an approximation of the untraced light in a scene. It is modeled as a light received uniformly at all points of a scene. As a result, objects that are illuminated only with ambient light (because direct or indirect lighting does not reach them) have a "flat" aspect, with all their 3D features erased.

To compensate for this, Zhukov et al. [START_REF] Zhukov | An ambient light illumination model[END_REF] suggested multiplying this value by obscurance, w( p), defined as the accessibility to ambient light at each point p:

w( p) = 1 π Ω V (ω)ρ(d(ω)) n• ω dω (1)
In this equation, V (ω) is the visibility function, defined as 0 where there is some geometry occluding the view from point p, and 1 where the direction of view ω is unoccluded. Objects that are closer to p should account more for the obscurance, while objects that are far away from p should account little, if anything. The function ρ(d(ω)) weights the contribution of the occluder in direction ω by its distance (d(ω)). Zhukov et al. [START_REF] Zhukov | An ambient light illumination model[END_REF] suggests using a smooth ρ function, limiting the contribution of occluders as they are further away from point p. The integration is over the hemisphere centered around the normal at p. From a physical point of view, this model can be thought of as an emitting gas, with constant emittance uniformly in all directions, present everywhere in the scene. Zhukov et al. [START_REF] Zhukov | An ambient light illumination model[END_REF] defined obscurance as the percentage of ambient light that should reach each point p. Modern implementations [Lan02, Chr02, Chr03, PG04, Bun05, KL05] reverse the meaning and define instead ambient occlusion as the percentage of ambient light that is blocked by geometry close to point p. To simplify computations, they replace ρ with a step function, just computing the percentage of light that is blocked by occluders located within a given distance from p:

ao( p) = 1 π Ω (1 -V (ω)) n• ω dω (2)
Occlusion values are weighted by the cosine of the angle of the occluded direction with the normal n: occluders that are closer to the direction n contribute more, and occluders closer to the horizon contribute less, corresponding to the importance of each direction in terms of received lighting. Ambient occlusion is computed as a percentage, with values between 0 and 1, hence the 1 π normalization factor.

3 Basic algorithm

Overview of the algorithm

We assume we have a solid object moving through a 3D scene. We want to compute ambient occlusion caused by this object in the scene; our algorithm works as follows:

Precomputation: The percentage of occlusion from the object is precomputed at every point of a 3D grid surrounding the object (see Fig. 2). This grid is stored as a 3D texture, linked to the object.

Runtime:

For every pixel rendered, we get the ambient occlusion value in the 3D texture and use it. Retrieving ambient occlusion values is done by:

• rendering the back polygons of the bounding box of the grid,

• for each pixel rendered, get the world position of the underlying pixel,

• convert this position into voxel position in the grid,

• lookup ambient occlusion value (and, optionally, direction) in the 3D texture;

Figure 2: We construct a grid around the object. At the center of each grid element, we compute a spherical occlusion sample. At runtime, this information is used to apply shadows on receiving objects.

In short, for each moving occluder in the scene, the algorithm requires rendering three polygons and executing a very small fragment program at each pixel rendered. The cost on the GPU at runtime is really small, because we use un-processed values. Our method assumes that the position of the underlying pixel is available. This is naturally the case when using deferred shading, but it is also possible without deferred shading, e.g. by exporting the Z-buffer into a texture.

Detailed description of the algorithm

Our algorithm inserts itself in a classical framework where other shading information, such as direct lighting, shadows, etc. is computed in separate rendering passes. One rendering pass will be used to compute ambient lighting, combined with ambient occlusion.

Our algorithm can either be used with classical shading, or with deferred shading. In the latter case, the world-space position and the normal of all rendered pixels is readily available. In the former, this information must be stored in a texture, using the information from previous rendering passes.

The overall algorithm is:

Step1. Render world space positions and normals: of all shadow receivers in the scene, including occluders. The normals will be used in section 5.1.

Step2. Ambient occlusion: for each occluder, 1. render the back faces of the occluder's grid (depth-testing is disabled).

2. for every pixel accessed, execute a fragment program:

(a) retrieve the world space position of the pixel. (b) convert this world space position to voxel position in the grid, passed as a 3D texture (c) retrieve ambient occlusion value in the grid, using linear interpolation.

3. Ambient occlusion values a from each occluder are blended in the frame buffer using multiplicative blending with 1a.

The entire computation is thus done in just one extra rendering pass. We used the back faces of the occluder's grid, because it is unlikely that they are clipped by the far clipping plane; using the front faces could result in artifacts if they are clipped by the front clipping plane.

The fragment program used in step 2 is shown here, in Cg: FRAGMENT SHADER 1 float4 worldpos = texRECT(PositionTex, screenpos)

Details of the algorithm

Memory costs

Precomputed values for ambient occlusion are stored in a 3D texture, with a memory cost of O(n 3 ) bytes. With a grid size of 32, a typical value we use in our implementation, the memory cost for ambient occlusion values is 32 Kb per channel. Thus, storing just the ambient occlusion value, as in section 4, gives a memory cost of 32 Kb. Adding the average occluded direction, as in section 5, requires three extra channels, bringing the complete memory cost to 128 Kb.

Spatial extent of the grid

An important parameter of our algorithm is the spatial extent of the grid. If the grid is too large, we run the risk of under-sampling the variations of ambient occlusion, or we have to increase the resolution, increasing the memory cost. If the grid is too small, we would miss some of the effects of ambient occlusion.

To compute the spatial extent of the grid, we use the bounding box of the occluder. This bounding box has three natural axes, with dimension 2r i on each axis, and a projected area of A i perpendicular to axis i (see Fig. 3(a)).

Along the i axis, the ambient occlusion of the bounding box is approximately:

a i ≈ 1 4π A i (d -r i ) 2 (3)
where d is the distance to the center of the bounding box.

If we decide to neglect occlusion values smaller than ε, we find that the spatial extent e i of the grid along axis i should be:

e i = r i + A i 4πε (4)
We take ε = 0.1, giving an extent of e i ≈ 3r i for a cubic bounding box (see Fig. 3(b)). For elongated objects, equation 4 gives an elongated shape to the grid, following the shape of the object, but with the grid being thinner on the longer axes of the object (see Fig. 3(c)).

We use a relatively large epsilon value (0.1), resulting in a small spatial extent. As a consequence, there can be visible discontinuities on the boundary of the grid (see Fig. 4(a)). To remove these discontinuities, we re-scale the values inside the grid so that the largest value at the boundary is 0. If the largest value on the boundary of the grid is V M , each cell of the grid is rescaled so that its new value V is: The effect of this scaling can be seen on Fig. 4(b). The overall aspect of ambient occlusion is kept, while the contact shadow ends continuously on the border of the grid. This also resembles Zhukov's et al. [START_REF] Zhukov | An ambient light illumination model[END_REF] weighting with distance, ρ(d(ω)), in equation 1.

V = V -V M 1 -V M

Voxels inside the occluder

Sampling points that are inside the occluder will have occlusion values of 1, expressing that they are completely hidden. As we interpolate values on the grid, a point located on the boundary of the occluder will often have non-correct values.

To counter this problem, we modify the values inside the occluder (which are never used) so that the interpolated values on the surface are as correct as possible.

A simple but quite effective automatic way to do this is: for all grid cells where occlusion value is 1, replace this value by an average of the surrounding grid cells that have an occlusion value less than 1. This algorithm was used on all the figures in this paper, except for the dwarf in Fig. 12 where we obtained better results with a little tweaking by hand.

Shading surfaces with ambient occlusion alone

Standard surfaces

In the "classical" ambient occlusion method, occlusion values are computed at a point p on a surface, with respect to the normal n at that point. The ambient occlusion is defined as the occlusion in the upper hemisphere, centered around the normal. Here, we are computing occlusion values at sample points in the grid, in a void, without any surface or normal. As a consequence, we have to change the definition of occlusion:

ao ( p) = 1 4π Ω (1 -V (ω)) dω (5)
This is the percentage of the full sphere that is occluded by our object. When we apply these occlusion values at a receiving surface, during rendering, the occlusion only happens over a half-space, since the receiver itself is occluding the other half-space. To account for this occlusion, we scale the occlusion value by a factor 2. This shading does not take into account the position of the occluder with respect to the normal of the receiver. This is an approximation, but we found it performs quite well in several cases (see Fig. 1). It is also extremely cheap in both memory and computation time, as the value extracted from the 3D texture is used directly.

In section 5, we explain a modification of our algorithm to account for the average occluded direction.

Self-occlusion

Our algorithm can also handle self-occlusion: ambient occlusion caused by one object onto itself. Self-occlusion will happen for non-convex objects, such as a table (Figure 7) or a character (Figure 12(a)). In that case, the occlusion value computed includes the underlying surface. Before using this value, we have to remove the effect of the underlying surface. Usually, the underlying surface occludes a full hemisphere. As a consequence, we have to use ao ( p) -0.5. If we want to account for self-occlusion, depending on the surface being shaded, we have to use either 2ao ( p) or ao ( p) -0.5. For simplicity, we store:

ao grid ( p) = 2ao ( p)
and when there is self-occlusion, we use:

ao sel f ( p) = ao grid ( p) -1 2
We coded this using the stencil buffer to test for self-occlusion, and used a separate 3D texture to store the occlusion values ao sel f .

Shading surfaces with ambient occlusion and average occluded direction

For better ambient occlusion effects, we also store the average occluded direction, along with the percentage of occlusion. That is equivalent to storing the set of occluded directions as a cone (see Fig. 5). This cone will be used for better accuracy in computing ambient occlusion, combining ambient occlusion from several occluders and computing environment lighting.

The cone is defined by its axis (d) and the percentage of occlusion α (proportional to the solid angle covered by the cone). Axis and percentage of occlusion are precomputed for all moving objects and stored on the sample points of the grid, in an RGBA texture, with the cone axis d stored in the RGB-channels and occlusion value α stored in the A-channel.

Accounting for surface normal of receiver

Compared to the algorithm in section 4, we now have access to more information regarding the relative positions of the occluder and receiver (see Fig. 6). In order to compute the percentage of ambient occlusion caused by the moving occluder, we clip the cone of occluded directions by the tangent surface to the receiver (see Fig. 6).

In step 2 of the algorithm (see Section 3.2), we have access to the world space position and normal of the underlying pixel. The world space position is used to access the cone direction and aperture in the grid. The normal is used to clip the cone of occluded directions: the surface at the pixel is approximated by its tangent plane, and we compute the intersection between this plane and the cone of occluded directions. The percentage of effectively occluded directions is a function of two parameters: the angle between the direction of the cone and the normal of the plane (β ), and the aperture of the cone (α) (see Fig. 6). It is possible to compute this occlusion percentage, but for performance reasons we pre-compute it and store it in a lookup table, T clip . The lookup table also stores the effect of the diffuse BRDF (the cosine of the angle between the normal and the direction).

The fragment shader code, in Cg notation: FRAGMENT SHADER This code translates to 16 shader assembler instructions. Figure 7 and 8 were rendered using this method, with a grid resolution of 32 3 . Note that, compared to the method described in section 4, this method handles self-occlusion at no extra charge; in the case of self-occlusion, the normal of the receiver is generally opposed to the axis of the cone. As a consequence, T clip removes the self occlusion behind the tangent plane and only returns the self occlusion above the tangent plane, e.g. when α > 180 • .

Figure 7: Ambient occlusion computed with our algorithm that accounts for the surface normal of the receiver and the direction of occlusion.

Combining occlusion from several occluders

When we have several moving occluders in the scene, we compute occlusion values from each moving occluder, and merge these values together. The easiest method to do this is to use OpenGL blending operation: in a single rendering Kontkanen and Laine [START_REF] Kontkanen | Ambient occlusion fields[END_REF] show that modulating with (1a i ), for all occluders i, is statistically the best guess. Our experience also show that, for many scenes, it gives very satisfying results.

This method also has the advantage of being very simple to implement. The combined occlusion value for one pixel is independent from the order in which the occluders are treated for this pixel, so it only requires one rendering pass to compute ambient occlusion from all moving occluders.

As we also need the axis of the occlusion cone, along with its aperture, we have to adapt the blending method. The key idea is that we treat occluders sequentially, keeping a cone corresponding to the union of all previous occlusion cones, at each step computing the union of this cone with the occlusion cone from the current occluder, and storing the result as input for the next occluder.

The trouble is that accurately combining one cone of occluded directions with another is a complex operation, which is not feasible using the simple blending operations currently available. It would benefit from either programmable blending or the ability to read and write into the same buffer.

We tested two possible workarounds. The first is the faster and the second is the more accurate:

• blending separately the apertures and the axes of the cone (section 5.2.1),

• keeping two separate buffers, one to be used for reading and the other for writing. After each occluder has been treated, the content of the second buffer is copied to the first. This slows down the computation, but ensures greater accuracy (section 5.2.2).

Simple occlusion blending

This method produces the same ambient occlusion values as the simple occlusion blending, but also outputs cone axes to be used for illumination from environment maps. Each occluder is rendered sequentially, with the fragment shader in section 5.1, into an occlusion buffer. The cone axes are stored in the RGB channels and the occlusion value is stored in the alpha channel. Occlusion values are still blended multiplicatively, while cone axes are blended additively, weighted by their respective solid angle:

α R = (1 -α A )(1 -α B ) d R = α A d A + α B d B
This is achieved using glBlendFuncSeparate(). Like the simple blending method, for this method the occlusion result is independent from the order in which the occluders are treated for this pixel, so it requires only one rendering pass for all the occluders. The resulting cone axes are normalized before usage with environment lighting. Figure 9 shows a comparison of the ambient occlusion values computed by the simple blending method with the ground truth ambient occlusion values, computed by distributed ray-tracing. The ambient occlusion pictures look very similar, showing that even the simplest blending method is quite accurate for blending contributions from different parts.

Two Buffers Blending

The accuracy of blending occlusion cones can be improved by using two separate buffers, one occlusion buffer to be used for reading and one copy-back buffer for writing.

All the moving occluders are treated sequentially. For each occluder, we perform the following tasks:

1. Computing the occlusion cone using the algorithm described in section 5.1, 2. reading the occlusion cone from the occlusion buffer, corresponding to the combined effect of all the previous occluders, and 3. combining the two occlusion cones together and write the result into the copy-back buffer.

After dealing with the occluder, the content of the copy-back buffer is copied to the occlusion buffer, and we move on to the next occluder. Waiting until the treatment of the occluder is finished and copying occlusion values between the buffers slows down the computation.

After each rendering pass, each pixel contains a cone corresponding to the computed ambient occlusion at this pixel, which can be either a null cone, the cone from a single moving occluder, or a cone coming from the combination of several moving occluders.

Finally, when the contribution from all casters have been rendered, the alpha-channel of the occlusion buffer is blended onto the color buffer containing the colors of the receivers, using 1a.

Computing the union of two cones: Figure 10 illustrates combining together two ambient occlusion cones, each of them defined by an axis and an aperture. In the general case, the two cones are not disjoint, so we cannot satisfy ourselves with summing their occluded areas and averaging their central directions. Instead, we use a lookup table T merge (α 1 , α 2 , β ) that returns the union of the two ambient-occlusion cones, taking their possible intersection into account. Here, the α i represent the apertures of each cone, and β corresponds to the angle between the directions of the two cones. The two cones are then replaced by a new cone, whose aperture is given by T merge , and whose axis is the weighted average of the two axes, weighted by their respective solid angle.

Clipping a cone against the tangent plane: When we clip an ambient occlusion cone against the tangent plane at the current receiving pixel, we compute the aperture of the clipped cone using the T clip lookup function, described in In Figure 11(a), the shadow is too dark under the place where the two cubes are overlapping, because the shadow from each cube are added together. Figure 11(c) avoids this pitfall, but the combined shadow is now slightly too light: representing the occlusion from each cube as a cone results in a loss of precision.

Animated rigid body objects (see Figures 13 and9) typically have many intersecting parts or mutually occluding parts. In that case, accurately blending the occlusion from the moving parts is important, and the technique described in this section can be useful. The occlusion cones can also be used to approximate the incoming lighting from an environment map, as suggested by Pharr and Green [START_REF] Pharr | Ambient occlusion[END_REF]. See Figure 12 for an example of environment lighting.

Accounting for illumination from an environment map

Compared to their method, because the ambient occlusion is stored in 3D grids attached to each moving rigid object, we can handle not only self occlusion but also occlusion for animated objects made of several rigid bodies, such as the robot in Figure 13. This method can even be used to handle indirect illumination with color bleeding and local occlusion.

For each pixel, we first compute the lighting due to the environment map, using the surface normal for Lambertian surfaces, or using the reflected cone for glossy objects. Then, we subtract from this lighting the lighting corresponding to the cone of occluded directions.

We only need to change the last step of blending the color buffer and occlusion buffer. Each shadow receiving pixel is rendered using the following code: To be able to use very large filter sizes, lat-long maps were used rather than cube maps, since mipmapping that spans multiple cube sides does not work well on current graphics hardware [START_REF] Pharr | Ambient occlusion[END_REF].

Results

Precomputation

We have implemented three different methods for precomputing the ambient occlusion grids: two methods using graphics hardware and one method based on ray tracing, shooting 256 rays per cell.

The GPU-based approaches renders the caster through the 6 cube sides of each cell, with a resolution of 16 × 16 per face. In the first method, we are only interested in occlusion values, so we use occlusion queries. In the second method, we are also looking for the direction of occlusion, so we read the Z-buffer to the CPU and average the occluded directions.

For all our scenes, a grid resolution of 32 3 was used. Table 1 shows the run-times. For comparison purposes, we have also included one very large model of 1M triangles.

The GPU-based versions are vertex bound and not fill-rate bound. Changing the resolution of the faces of the cubes from 8 × 8 up to 128 × 128 takes approximately the same time. Therefore, changing the projection method using parabolic or spherical projections should result in a 3 times speedup.

Timing results

Our tests were done on a Pentium4 2.8 GHz with a Geforce 6800GT. All images were rendered using a resolution of 800 × 600, and a grid resolution of 32 3 . For all the timing results, we recorded the complete rendering time, that is the time for rendering the scene and computing ambient occlusion, not just computing ambient occlusion. Figure 14: Observed rendering times on our system, with and without Ambient Occlusion computations, depending on the parameters of the scene.

Occluder complexity

Figure 14(a) shows the evolution of rendering time (in ms) as a function of occluder complexity. We rendered the same scene, gradually increasing the complexity of the moving occluder and recording the rendering times, both with and without ambient occlusion.

As can be expected, the total rendering time increases with the occluder complexity. However, you can see that the added cost of using our pre-computed ambient occlusion is constant, roughly 6.5 ms, independently from the complexity of the occluder.

Scene complexity

Figure 14(b) shows the evolution of rendering time (in ms) as a function of scene complexity. We rendered the same occluder, inside a scene of increasing complexity, and recorded the rendering times, both with and without ambient occlusion.

Again, the total rendering time increases with scene complexity. However, the added cost of ambient occlusion is constant, roughly 6.5 ms, independently from the complexity of the occluder. Not surprisingly, the time used for ambient occlusion computations varies linearly with the number of occluders. The important point is the very low cost of our system: we are able to render up to 40 different moving occluders and still render at more than 17 fps. Figure 16 shows, for the robot scene, the evolution of rendering time depending on the activated features: rendering the scene with only standard Gouraud shading, with simple blending of ambient occlusion values, with simple blending and environment lighting, with two-buffers blending and finally with two-buffers blending and environment lighting.

Number of occluders

Feature cost

Each feature improves the realism, but also has a cost in terms of rendering speed. All these costs are still manageable, however, and even with the best blending method and environment lighting, the 11 occluders in the robot are displayed at more than 30 fps.

On current architectures, the best compromise, in terms of rendering speed and aspect of the scene is to use the simple blending, combined with environment lighting.

Increasing scene realism

Figure 1 :

 1 Figure 1: Example of our contact shadows. This scene runs at 200 fps.

  Figure 3: The optimal grid extent depends on the bounding-box of the occluder. Here, grid extents are computed with ε = 0.1.

  (a) Using raw values, discontinuities can appear (b) After re-scaling, ambient occlusion blends continuously

Figure 4 :

 4 Figure 4: We need to re-scale occlusion values inside the grid to avoid visible artifacts.

Figure 5 :

 5 Figure 5: Ambient occlusion is stored as a cone, defined by its direction d and its aperture α

Figure 6 :

 6 Figure 6: The cone of occluded directions is clipped by the tangent plane to the receiver to give the ambient occlusion value.

Figure 8 :

 8 Figure 8: Ambient occlusion values, accounting for the normal of the occluder and the direction of occlusion (80 to 130 fps)

  Figure 9: Checking the accuracy of our blending method: comparison of Ambient Occlusion values computed with ground truth. See Figure 13(c) for a view of the robot parts.

Figure 12 :Figure 13 :

 1213 Figure 12: Using environment lighting: a dwarf model in a Cornell box. a) Notice the red color bleeding, and the dark shadow under his arm, where no color bleeding reaches from the red wall. b) The blue wall bleeds onto the dwarfs right side. c) Without ambient occlusion nor color bleeding.

  using three different method; 1) GPU acceleration and occlusion queries to only compute the ambient occlusion in each cell, 2) GPU acceleration computing occlusion cones, and 3) ray tracing with 256 rays per cell with Monte Carlo sampling PSEUDO CODE 1 Read cone d, α from occlusion buffer 2 Read normal from normal buffer 3 Compute mipmap level from cone angle α 4 A = EnvMap(d, α). i.e., lookup occluded light within the cone 5 B = AmbientLighting(normal). i.e., lookup the incoming light due to the environment map. 6 return B-A.

Figure 14

 14 Figure 14(c) shows the evolution of rendering time (in ms) as a function of the number of occluders. We rendered the same scene, gradually increasing the number of occluders and recorded the rendering times, both with and without ambient occlusion. The scene is shown in figure 15.

Figure 16 :

 16 Figure16: Observed rendering times on our system, depending on the features activated and on the blending method.

Figure 17

 17 Figure17shows a classical test scene for real-time soft shadows[START_REF] Assarsson | A geometry-based soft shadow volume algorithm using graphics hardware[END_REF][START_REF] Lapierre | A survey of real-time soft shadows algorithms[END_REF]. Due to the silhouette problem, most real-time soft shadow algorithms only see the top part of the box, and compute the soft shadow from this top part only. They are unable to compute the part of the soft shadow that is caused by occlusion from the bottom part of the box (see Figure17(a)). Figure17(b)shows a combination of our Ambient Occlusion algorithm with Soft Shadow Volumes, computed separately. As you can see, the resulting picture is much closer to the ground truth (Figure17(c)), and the cost of adding ambient occlusion is almost negligible.

Table 1 :

 1 Preprocessing times for the 3D grid

	#tris	GPU with occl queries full cones tracing GPU with ray
	391	0.45 s	2.75 s	5.58 s
	4.698	8.33 s	9 s	7.46 s
	16.271	50 s	50 s	6.25 s
	378k	230 s	230 s	92 s
	1.1M	-	-	226 s

Acknowledgments

The space ship model used in this paper is a freeware model by Max Shelekhov.

section 5.1. We then compute the new cone's central axis d A as a linear interpolation between the original cone central axis d A and the normal to the tangent plane n:

The blending coefficient, f , is also pre-computed as a function of (α, β ) and is stored in the T clip lookup texture.

List of Figures


Alexis Nasr
email: alexis.nasr@lif.univ-mrs.fr

Frédéric Béchet
email: frederic.bechet@lif.univ-mrs.fr

Jean-Franc ¸ois Rey
email: jean-francois.rey@lif.univ-mrs.fr

Benoît Favre
email: benoit.favre@lif.univ-mrs.fr

Joseph Le Roux
email: joseph.le.roux@lif.univ-mrs.fr

MACAON An NLP Tool Suite for Processing Word Lattices

MACAON is a tool suite for standard NLP tasks developed for French. MACAON has been designed to process both human-produced text and highly ambiguous word-lattices produced by NLP tools. MACAON is made of several native modules for common tasks such as a tokenization, a part-of-speech tagging or syntactic parsing, all communicating with each other through XML files . In addition, exchange protocols with external tools are easily definable. MACAON is a fast, modular and open tool, dis-

Introduction

The automatic processing of textual data generated by NLP software, resulting from Machine Translation, Automatic Speech Recognition or Automatic Text Summarization, raises new challenges for language processing tools. Unlike native texts (texts produced by humans), this new kind of texts is the result of imperfect processors and they are made of several hypotheses, usually weighted with confidence measures. Automatic text production systems can produce these weighted hypotheses as nbest lists, word lattices, or confusion networks. It is crucial for this space of ambiguous solutions to be kept for later processing since the ambiguities of the lower levels can sometimes be resolved during highlevel processing stages. It is therefore important to be able to represent this ambiguity.

MACAON is a suite of tools developped to process ambiguous input and extend inference of input modules within a global scope.

It consists in several modules that perform classical NLP tasks (tokenization, word recognition, part-ofspeech tagging, lemmatization, morphological analysis, partial or full parsing) on either native text or word lattices. MACAON is distributed under GNU public licence and can be downloaded from http://www.macaon.lif.univ-mrs.fr/.

From a general point of view, a MACAON module can be seen as an annotation device1 which adds a new level of annotation to its input that generally depends on annotations from preceding modules. The modules communicate through XML files that allow the representation different layers of annotation as well as ambiguities at each layer. Moreover, the initial XML structuring of the processed files (logical structuring of a document, information from the Automatic Speech Recognition module . . . ) remains untouched by the processing stages.

As already mentioned, one of the main characteristics of MACAON is the ability for each module to accept ambiguous inputs and produce ambiguous outputs, in such a way that ambiguities can be resolved at a later stage of processing. The compact representation of ambiguous structures is at the heart of the MACAON exchange format, described in section 2. Furthermore every module can weight the solutions it produces. such weights can be used to rank solutions or limit their number for later stages of processing.

Several processing tools suites alread exist for French among which SXPIPE [START_REF] Sagot | Sxpipe 2: architecture pour le traitement présyntaxique de corpus bruts[END_REF], OUTILEX [START_REF] Blanc | Outilex, plate-forme logicielle de traitement de textes écrits[END_REF], NOOJ 2 or UNI-TEX 3 . A general comparison of MACAON with these tools is beyond the scope of this paper. Let us just mention that MACAON shares with most of them the use of finite state machines as core data representation. Some modules are implemented as standard operations on finite state machines.

MACAON can also be compared to the numerous development frameworks for developping processing tools, such as GATE 4 , FREELING 5 , ELLOGON 6 or LINGPIPE 7 that are usually limited to the processing of native texts.

The MACAON exchange format shares a certain number of features with linguistic annotation scheme standards such as the Text Encoding Initiative 8 , XCES 9 , or EAGLES 10 . They all aim at defining standards for various types of corpus annotations. The main difference between MACAON and these approaches is that MACAON defines an exchange format between NLP modules and not an annotation format. More precisely, this format is dedicated to the compact representation of ambiguity: some information represented in the exchange format are to be interpreted by MACAON modules and would not be part of an annotation format. Moreover, the MACAON exchange format was defined from the bottom up, originating from the authors' need to use several existing tools and adapt their input/output formats in order for them to be compatible. This is in contrast with a top down approach which is usually chosen when specifying a standard. Still, MACAON shares several characteristics with the LAF [START_REF] Ide | International standard for a linguistic annotation framework[END_REF] The MACAON exchange format is based on four concepts: segment, attribute, annotation level and segmentation.

A segment refers to a segment of the text or speech signal that is to be processed, as a sentence, a clause, a syntactic constituent, a lexical unit, a named entity . . . A segment can be equipped with attributes that describe some of its aspects. A syntactic constituent, for example, will define the attribute type which specifies its syntactic type (Noun Phrase, Verb Phrase . . . ). A segment is made of one or more smaller segments.

A sequence of segments covering a whole sentence for written text, or a spoken utterance for oral data, is called a segmentation. Such a sequence can be weighted.

An annotation level groups together segments of a same type, as well as segmentations defined on these segments. Four levels are currently defined: pre-lexical, lexical, morpho-syntactic and syntactic.

Two relations are defined on segments: the precedence relation that organises linearly segments of a given level into segmentations and the dominance relation that describes how a segment is decomposed in smaller segments either of the same level or of a lower level.

We have represented in figure 2, a schematic representation of the analysis of the reconstructed output a speech recognizer would produce on the input time flies like an arrow11 . Three annotation levels have been represented, lexical, morpho-syntactic and syntactic. Each level is represented by a finitestate automaton which models the precedence relation defined over the segments of this level. Segment time, for example, precedes segment flies. The segments are implicitly represented by the labels of the automaton's arcs. This label should be seen as a reference to a more complex objet, the actual segment. The dominance relations are represented with dashed lines that link segments of different levels. Segment time, for example, is dominated by segment NN of the morpho-syntactic level.

This example illustrates the different ambiguity cases and the way they are represented. Plain lines represent annotation hypotheses within a level while dashed lines represent links between levels. Triangles with the tip up are "and" nodes and triangles with the tip down are "or" nodes. For instance, in the part-ofspeech layer, The first NN can either refer to "time" or "thyme". In the chunking layer, segments that span multiple part-of-speech tags are linked to them through "and" nodes.

The most immediate ambiguity phenomenon is the segmentation ambiguity: several segmentations are possible at every level. This ambiguity is represented in a compact way through the factoring of segments that participate in different segmentations, by way of a finite state automaton.

The second ambiguity phenomenon is the dominance ambiguity, where a segment can be decomposed in several ways into lower level segments. Such a case appears in the preceding example, where the NN segment appearing in one of the outgoing transition of the initial state of the morpho-syntactic level dominates both thyme and time segments of the lexical level. The triangle with the tip down is an "or" node, modeling the fact that NN corresponds to time or thyme.

Triangles with the tip up are "and" nodes. They model the fact that the PP segment of the syntactic level dominates segments IN, DT and NN of the morpho-syntactic level.

XML representation

The MACAON exchange format is implemented in XML. A segment is represented with the XML tag <segment> which has four mandatory attributes:

• type indicates the type of the segment, four different types are currently defined: atome (prelexical unit usually referred to as token in english), ulex (lexical unit), cat (part of speech) and chunk (a non recursive syntactic unit).

• id associates to a segment a unique identifier in the document, in order to be able to reference it.

• start and end define the span of the segment. These two attributes are numerical and represent either the index of the first and last character of the segment in the text string or the beginning and ending time of the segment in a speech signal.

A segment can define other attributes that can be useful for a given description level. We often find the stype attribute that defines subtypes of a given type.

The dominance relation is represented through the use of the <sequence> tag. The domination of the three segments IN, DT and NN by a PP segment, mentionned above is represented below, where p1, p2 and p3 are respectively the ids of segments IN, DT and NN.

<segment type="chunk" stype="PP" id="c1"> <sequence> <elt segref="p1"/> <elt segref="p2"/> <elt segref="p3"/> </sequence> </segment> The ambiguous case, described above where segment NN dominates segments time or thyme is represented below as a disjunction of sequences inside a segment. The disjunction itself is not represented as an XML tag. l1 and l2 are respectively the ids of segments time and thyme.

The dominance relation can be weighted, by way of the attribute w. Such a weight represents in the preceding example the conditional log-probability of a lexical unit given a part of speech, as in a hidden Markov model.

The precedence relation (i.e. the organization of segments in segmentations), is represented as a weighted finite state automaton. Automata are represented as a start state, accept states and a list of transitions between states, as in the following example that corresponds to the lexical level of our example.

<fsm n="9"> <start n="0"/> <accept n="6"/> <ltrans> <trans o="0" d="1" i="l1" w="-7.23"/> <trans o="0" d="1" i="l2" w="-9.00"/> <trans o="1" d="2" i="l3" w="-3.78"/> <trans o="2" d="3" i="l4" w="-7.37"/> <trans o="3" d="4" i="l5" w="-3.73"/> <trans o="2" d="4" i="l6" w="-6.67"/> <trans o="4" d="5" i="l7" w="-4.56"/> <trans o="5" d="6" i="l8" w="-2.63"/> <trans o="4" d="6" i="l9" w="-7.63"/> </ltrans> </fsm>

The <trans/> tag represents a transition, its o,d,i and w features are respectively the origin, and destination states, its label (the id of a segment) and a weight.

An annotation level is represented by the <section> tag which regroups two tags, the <segments> tag that contains the different segment tags defined at this annotation level and the <fsm> tag that represents all the segmentations of this level.

The MACAON architecture

Three aspects have guided the architecture of MACAON: openness, modularity, and speed. Openness has been achieved by the definition of an exchange format which has been made as general as possible, in such a way that mapping can be defined from and to third party modules as ASR, MT systems or parsers. Modularity has been achieved by the definition of independent modules that communicate with each other through XML files using standard UNIX pipes. A module can therefore be replaced easily. Speed has been obtained using efficient algorithms and a representation especially de-signed to load linguistic data and models in a fast way.

MACAON is composed of libraries and components. Libraries contain either linguistic data, models or API functions. Two kinds of components are presented, the MACAON core components and third party components for which mappings to and from the MACAON exchange format have been defined.

Libraries

The main MACAON library is macaon common. It defines a simple interface to the MACAON exchange format and functions to load XML MACAON files into memory using efficient data structures. Other libraries macaon lex, macaon code and macaon tagger lib represent the lexicon, the morphological data base and the tagger models in memory.

MACAON only relies on two third-party libraries, which are gfsm12 , a finite state machine library and libxml, an XML library 13 .

The MACAON core components

A brief description of several standard components developed in the MACAON framework is given below. They all comply with the exchange format described above and add a <macaon stamp> to the XML file that indicates the name of the component, the date and the component version number, and recognizes a set of standard options. maca select is a pre-processing component: it adds a macaon tag under the target tags specified by the user to the input XML file. The following components will only process the document parts enclosed in macaon tags.

maca segmenter segments a text into sentences by examining the context of punctuation with a regular grammar given as a finite state automaton. It is disabled for automatic speech transcriptions which do not typically include punctuation signs and come with their own segmentation.

maca tokenizer tokenizes a sentence into prelexical units. It is also based on regular grammars that recognize simple tokens as well as a predefined set of special tokens, such as time expressions, numerical expressions, urls. . . . maca lexer allows to regroup pre-lexical units into lexical units. It is based on the lefff French lexicon [START_REF] Sagot | The lefff 2 Syntactic Lexicon for French: Architecture, Acquisition, Use[END_REF] which contains around 500,000 forms. It implements a dynamic programming algorithm that builds all the possible grouping of pre-lexical units into lexical units.

maca tagger associates to every lexical unit one or more part-of-speech labels. It is based on a trigram Hidden Markov Model trained on the French Treebank [START_REF] Abeillé | Building a treebank for french[END_REF]. The estimation of the HMM parameters has been realized by the SRILM toolkit [START_REF] Stolcke | Srilm -an extensible language modeling toolkit[END_REF].

maca anamorph produces the morphological analysis of lexical units associated to a part of speech. The morphological information come from the lefff lexicon.

maca chunker gathers sequences of part-of-speech tags in non recursive syntactic units. This component implements a cascade of finite state transducers, as proposed by [START_REF] Abney | Partial parsing via finite-state cascades[END_REF]. It adds some features to the initial Abney proposal, like the possibility to define the head of a chunk. maca conv is a set of converters from and to the MACAON exchange format. htk2macaon and fsm2macaon convert word lattices from the HTK format [START_REF] Young | The HTK Hidden Markov Model Toolkit: Design and Philosophy[END_REF] and ATT FSM format [START_REF] Mohri | The design principles of a weighted finite-state transducer library[END_REF] to the MACAON exchange format. macaon2txt and txt2macaon convert from and to plain text files. macaon2lorg and lorg2macaon convert to and from the format of the LORG parser (see section 3.3).

maca view is a graphical interface that allows to inspect MACAON XML files and run the components.

Third party components

MACAON is an open architecture and provides a rich exchange format which makes possible the repre-sentation of many NLP tools input and output in the MACAON format. MACAON has been interfaced with the SPEERAL Automatic Speech Recognition System [START_REF] Nocera | Phoneme lattice based A* search algorithm for speech recognition[END_REF]. The word lattices produced by SPEERAL can be converted to pre-lexical MACAON automata. MACAON does not provide any native module for parsing yet but it can be interfaced with any already existing parser. For the purpose of this demonstration we have chosen the LORG parser developed at NCLT, Dublin 14 . This parser is based on PCFGs with latent annotations [START_REF] Petrov | Learning Accurate, Compact, and Interpretable Tree Annotation[END_REF], a formalism that showed state-of-the-art parsing accuracy for a wide range of languages. In addition it offers a sophisticated handling of unknown words relying on automatically learned morphological clues, especially for French (Attia et al., 2010). Moreover, this parser accepts input that can be tokenized, postagged or pre-bracketed. This possibility allows for different settings when interfacing it with MACAON.

Applications

MACAON has been used in several projects, two of which are briefly described here, the DEFINIENS project and the LUNA project.

DEFINIENS [START_REF] Barque | From the definitions of the trésor de la langue franc ¸aise to a semantic database of the french language[END_REF]) is a project that aims at structuring the definitions of a large coverage French lexicon, the Trésor de la langue franc ¸aise. The lexicographic definitions have been processed by MACAON in order to decompose the definitions into complex semantico-syntactic units. The data processed is therefore native text that possesses a rich XML structure that has to be preserved during processing.

LUNA 15 is a European project that aims at extracting information from oral data about hotel booking. The word lattices produced by an ASR system have been processed by MACAON up to a partial syntactic level from which frames are built. More details can be found in [START_REF] Béchet | Robust dependency parsing for spoken language understanding of spontaneous speech[END_REF]. The key aspect of the use of MACAON for the LUNA project is the ability to perform the linguistic analyses on the multiple hypotheses produced by the ASR system. It is therefore possible, for a given syntactic analysis, to 14 www.computing.dcu.ie/ ˜lorg. This software should be freely available for academic research by the time of the conference. find all the word sequences that are compatible with this analysis.

Figure 2 shows the interface that can be used to see the output of the pipeline.

Conclusion

In this paper we have presented MACAON, an NLP tool suite which allows to process native text as well as several hypotheses automatically produced by an ASR or an MT system. Several evolutions are currently under development, such as a named entity recognizer component and an interface with a dependency parser.

Figure 1 :

 1 Figure1: Three annotation levels for a sample sentence. Plain lines represent annotation hypotheses within a level while dashed lines represent links between levels. Triangles with the tip up are "and" nodes and triangles with the tip down are "or" nodes. For instance, in the part-ofspeech layer, The first NN can either refer to "time" or "thyme". In the chunking layer, segments that span multiple part-of-speech tags are linked to them through "and" nodes.

Figure 2 :

 2 Figure 2: Screenshot of the MACAON visualization interface (for French models). It allows to input a text and see the n-best results of the annotation.

Annotation must be taken here in a general sense which includes tagging, segmentation or the construction of more complex objets as syntagmatic or dependencies trees.

For readability reasons, we have used an English example, MACAON, as mentioned above, currently exists for French.

<segment type="cat" stype="NN" id="c1"> <sequence> <elt segref="l1" w="-3.37"/> </sequence> <sequence> <elt segref="l2" w="-4.53"/> </sequence> </segment>

ling.uni-potsdam.de/ ˜moocow/projects/ gfsm/

tributed under GNU Public License* This work has been funded by the French Agence Nationale pour la Recherche, through the projects SEQUOIA (ANR-08-EMER-013) and DECODA (2009-CORD-005-01)