Gauthier Chicot
email: gauthier.chicot@neel.cnrs.fr

Julien Pernot

Jean-Louis L Santailler

Céline Chevalier

Carole Granier

Pierre Ferret

Alexandre Ribeaud

Guy Feuillet

Pierre Muret

Electronic properties of E3 electron trap in n-type ZnO

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

ZnO is a very attractive semiconductor for optoelectronic uses. Indeed, its wide direct band gap (3.37eV) and very large exciton binding energy (60meV), allow ZnO to compete with GaN for LED applications in the UV spectrum. However, p doping of ZnO is still a challenge due to intrinsic and extrinsic n-type conductivity. In this regards, the knowledge of deep levels is an important issue for optoelectronic devices elaboration. Firstly, assessing the presence of deep donors is useful both to understand the origin of n-type conduction and because p-type material will be obtained only if their effect is cancelled. Secondly, deep levels can act as non radiative centers that affect directly the light emission efficiency in p-n junction devices. Deep Level Transient Spectroscopy (DLTS) is a well adapted technique, as it can give physical properties of the deep levels such as their activation energy, capture cross section, trap concentration and their sensitivity to electric field.

In this work, we will focus on a deep level which is common to three non-intentionally doped n-type ZnO samples grown by three different techniques. This level is the well known E3 level, as quoted in literature, found very frequently in ZnO samples. However, its origin is still a matter of controversy [1][2][3][4][5][6][7][8][9] . This paper is organized as follows. In the second section, experimental details about samples and measurements are given. In the third section, DLTS results are analyzed in order to get very accurate values of the activation energy and capture cross section for the E3 level.

Finally, physical origin of E3 is discussed in regards of the absence of electric field dependence of its signature and recent works published in literature.

II. EXPERIMENTAL DETAILS

In this work different kinds of sample were investigated : a MetalOrganic Vapor Phase Epitaxy (MOVPE) epilayer grown at CEA/LETI (label #1) on a commercial hydrothermal ZnO substrate (from Crystech Inc.), a crystal grown from the melt under high-pressure from Cermet Inc. (label #2) and a crystal grown by the hydrothermal method from Tokyo-Denpa Inc. (label #3). The MOVPE layer (#1) was grown at 950 • C using N 2 O and DEZn as precursors. The epilayer is 525 nm thick as given by SIMS analysis. MOVPE layer was firstly cleaned with organic solvents and then processed with Remote Oxygen Plasma (ROP). The sample grown from the melt at high-pressure (#2) was firstly annealed at 1100 • C in order to activate the shallow donors and receive the same conditioning as the hydrothermal sample, then treated by UV Ozone. The hydrothermally grown sample (#3) was firstly annealed at high temperature (1100 • C) by Tokyo-Denpa Inc., and then cleaned in organic solvents before being treated by ROP. On the three surfaces, Pt Schottky contacts (50 nm thick and 500 µm in diameter) were evaporated on the O face and full sheet Ti/Au ohmic contacts (20/80nm thick) were evaporated on the whole Zn face .

Capacitance voltage C(V) and DLTS measurements were performed with a Phystech FT1030 that operates at 1MHz, a frequency which has been checked to be much less than the cut-off frequency of all the diodes. DLTS spectra were obtained from the fast Fourier transform (FFT) of the capacitive transients, delivering up to 23 Fourier coefficients. Current voltage (I(V)) measurements were firstly achieved to check the rectifying behavior of Pt contacts and the leakage current at different temperatures. C(V) measurements were then performed at reverse bias voltage inducing low enough leakage currents to determine the effective doping profile N d -N a (see figure 1). Finally DLTS analysis were performed from 80K to 500K with reverse bias (U r ) of -2 V, pulse voltage (U p ) of 0 V for sample #1 and #3 and with U r =-0.3 V, U p =0.1 V for sample #2 after a filling pulse of T p duration. For all the three samples, different times windows (T w ) ranging between 10 ms and 500 ms were used in order to increase the number of points on the Arrhenius diagram.

III. RESULTS

DLTS spectra showed up several peaks, but only one (the E3 level) is common to the three samples described above. In figure 2, the experimental and simulated DLTS spectra found in the three samples are plotted. A good agreement appears between experimental and simulated spectra, the latter being calculated with a single emission time constant at each temperature (with parameters determined by the Arrhenius diagram, see below), generally associated to a point defect rather than to an extended defect for which fluctuating environment generates broadening of the emission rate distribution.

The Arrhenius diagram (figure 3) was obtained by extracting both temperature and emission rates from the maxima detected in DLTS spectra using up to 23 distinct and independent correlation functions yielding back as much Fourier coefficients 10 . By linear 1 5 0 2 0 0 2 5 0 3 0 0 1 . 2 x 1 0 1 1 . 4 x 1 0 1

1 . 6 x 1 0 1 1 . 8 x 1 0 1 2 . 0 x 1 0 1 # 1 # 3 N d -N a ( c m -3 ) D e p t h ( n m ) # 2 FIG. 1. N d -N a versus depth obtained by C(V) measurement on (#1) MOVPE sample, (#2)
high-pressure grown sample and (#3) hydrothermal sample.

fitting, the activation energy (from the slope) and the capture cross section (from the Yintercept) can be obtained using the emission rate formula :

e n = σ n v th N C exp -E an k b T (1)
where e n is the emission rate, σ n the apparent capture cross section, v th the thermal velocity, 4).

N
Samples N T < N d -N a > |F | (cm -3 ) (cm -3 ) (MV.cm -1 ) #1 8.0 × 10 +15 1.5 × 10 +17 0.19 #2 1.5 × 10 +15 1.0 × 10 +17 0.09 #3 8.6 × 10 +14 3.1 × 10 +16 0.07
cross section can be obtained from an overall least mean square fit (line in figure 3) of all the (T ; e n ) points : E a = 0.275 ± 0.002 eV and σ n = 2.3 ± 0.3 × 10 -16 cm 2 where the uncertainties are derived from the standard deviations and ensure that the actual values lie within this confidence interval with a 95 per cent probability. The fairly small capture cross section is characteristic of a neutral or eventually repulsive trap before electron capture, confirming the Auret et al. The sample diversity in term of doping level (cf. table I) enable us to investigate the effect of electric field. The electric field versus depth F (x) was calculated using the integrated Poisson equation :

F (x) = e < N d -N a > r 0 (x -w(U r )) ( 2
)
where e is the elementary charge, < N d -N a > the average effective doping given in table I, r = 8 the relative permittivity of ZnO, 0 the vacuum permittivity, w(U r ) the WSCR under U r bias obtained by w(U r ) = r 0 S/C(U r ) (S is the Schottky contact area) , and x the abscissa along the WSCR which origin is at the Schottky contact/semiconductor interface.

As N T is negligible compared to < N d -N a >, the abscissa where the quasi-Fermi level E F coincides with the energy level of the trap E T 11 is defined by w(V ) -L 0 (where V is the applied voltage) where

L 0 = L D √ 2 E F -E T k b T -1 1/2 (3)
with L D the Debye length. Considering a full filling of the traps, the electrons released during the emission phase come from the range of abscissa between w(U p )-L 0 and w(U r )-L 0 . The mean value of electric field experienced by an electron captured under U p bias and released under U r bias (given in table I) is calculated using the formula 2 as follow :

F = F (w(U p ) -L 0 ) + F (w(U r ) -L 0 ) 2 (4)
The electric field can affect the emission rate along different mechanisms [12][13][14][15][16] : Poole-Frankel effect, phonon assisted tunneling effect or direct tunneling effect. Considering only the Poole-

Frankel effect for a Coulombic potential using the model described in Ref. 13 , we should find a emission rate more than 10 times greater for sample #1 than for sample #3, that is obviously not the case on the Arrhenius diagram (Fig. 3). Thus, no significant dependence of the electric filed on the emission rate is observed (also noticed by Auret et al. 5 ) in agreement with a neutral trap before electron capture. This observation is valid for mean electric field values varying from 0.07 MV.cm -1 to 0.19 MV.cm -1 . In sample #1 (i.e. highest doping level), experiments with higher reverse voltage U r were performed in order to widen the electric field range of investigation of this work. Unfortunately, the deeper space charge region (region probed by DLTS) includes an additional deep level with an emission time constant very close to the one of the E3 level, which makes the interpretation of the Arrhenius diagrams unreliable at such reverse voltage.

Therefore, it appears that the E3 level is a very deep acceptor, lying 0.275 eV below the conduction band, since it becomes negatively charged after electron capture and hence experiences a 0/-elementary charge change.

IV. DISCUSSION

By finding the E3 level in three different samples, we confirm its presence, irrespective of the synthesis method used to grow the samples considered here. In other studies, this level has also been detected in vapor phase grown samples 1,3,5,8 , in PLD thin films 6,7 and in hydrothermally grown sample 4 . Therefore, E3 is a defect found in both single crystal and polycrystalline ZnO, that had been formerly attributed to isolated oxygen vacancies 2,8 . But this assumption is now under debate : recently von Wenckstern et al. 6 found that the concentration of E3 in annealed samples is independent of the annealing ambient.

V O 1,
Monakhov et al. 2 also questioned this attribution because the peak associated to E3 has a very weak dependence on the ions irradiation dose and, thus, an assignment to a primary defect as V O is not obvious. Other observations, along the same way, show that the Schottky pre-treatments (such as oxygen plasma, H 2 O 2 treatment, UV ozone) which are supposed to bring in oxygen atoms have no effect on E3 2 . These experimental facts are in agreement with theoretical calculations from Janotti et al. 17 . Indeed, ab initio calculations based on

Local Density Approximation show that the singly charged oxygen vacancy V + O cannot be stable because of too a high formation energy. Only V 2+

O is stable in ZnO and its activation energy for the transition (2+,0) is estimated to be 1 eV or more.

Profiling using DLTS isothermal measurements was performed on the sample #1 (MOVPE layer). The E3 trap concentration increases with depth away from the surface, when the interface with the substrate is approached. In the case of the MOVPE epilayer, if E3 were attributed to V O , the increasing concentration with depth could be due to the effect of the ROP filling the oxygen vacancies more efficiently near the surface than deeper into the layer.

But considering that E3 probably experiences (0/-) charge states in contrast to (2+,0) for V O , with an energy around 1.2 eV for the transition 17 , an assignment of E3 to the donor V O is highly unlikely. However, a complex involving an oxygen vacancy cannot be discarded.

Since the E3 level appears in ZnO whatever the fabrication technique, this level is related to a native defect (such as a vacancy, for example) or to an impurity which is always present in ZnO. Therefore two hypothesis can be formulated : i) On the one hand E3 might be assigned to an impurity. DLTS and SIMS analysis were led on a total of 10 samples (4 grown by Chemical Vapor Transport, 4 by hydrothermal method, 1 by high pressure melt method and 1 by MOVPE). E3 level was detected in 5 of these samples but no clear correlation between E3 presence and impurities (Li, Fe, Al, N, C, Si) concentration was found. It must be noticed that the SIMS detection limit of such impurities is in most cases larger than N T detected by DLTS. So, an attribution to an impurity cannot be discarded.

ii) On the other hand, as the level is present whatever the growth method, an attribution to a native defect seems also to be more relevant. Assignment of E3 to the isolated V O has been previously discarded but a complex involving V O may be considered. An attribution of E3 to the isolated V Zn is also not possible since V Zn is too deep (2.1 eV below the conduction band) to be detected by DLTS 9 . Recently, Dong et al. 9 proposed that the E3 might be related to a complex involving V O such as V O -V Zn . Although based on other statements that those contained in Dong et al. paper 9 , the origin of E3 may rely on a complex involving two defects or impurities charged differently on adjacent sites, due to the insensibility of E3 physical properties to the electric field that we have demonstrated in this work. Such a combination of the two previous cases is discussed deeper in the following.

All the models, either semi-classical 12,13 or involving quantum theory [14][15][16] , dealing with the influence of the electric field on the deep level of an isolated charged impurity, concluded to a strong effect, typically of several hundreds of percents for the variation of the emission rate when the field varies only of some tens of percents. No such effect were observed on our sample even considering only Poole-Frenkel effect. All these models assume that the deep level lies in a potential well of spherical symmetry around the impurity, which originates from the charge including the nucleus and the inner electrons located on the rare gas core of the foreign atom, thus producing a net positive charge. Adding the valence electrons cloud may change the net global charge of the potential well felt by itinerant carriers. But in any case, such a picture led invariably to a deformation of the potential well by the macroscopic electric field and therefore to strong changes of the emission rate 18 , contrary to what happens for the E3 level. Consequently, the E3 level cannot be related to an isolated impurity alone, either substitutional or interstitial. On the contrary, if either the positively charged center is missing, like in the vacancy case, or a two centers defect is present with different charges on the two adjacent sites, the insensibility of the E3 level to the macroscopic electric field can be understood because the former is so weaker than the internal field inside this defect (about 10 10 V m -1 for two elementary charges with opposite signs on two adjacent sites) that its effect is negligible. In other words, the shape of the potential well of such a defect is so asymmetric that it cannot be appreciably changed by the macroscopic field. Because isolated V O or V Zn are not likely, dual center defects with different charges and probably opposite ones on each site to give a net neutral center are the best candidates. Hence, the E3 level could be due to either the dual vacancy V O -V Zn , or the combination of an interstitial and a substitutional impurity like Li Zn -Li i or any impurity associated to a vacancy, provided their charges are opposite.

V. CONCLUSION

DLTS measurements performed on three samples provided accurate values of activation energy and capture cross section for the well known E3 electron trap. DLTS technique and associated characterization methods also provided interesting characteristics about E3 such as its presence whatever the synthesis method used for the fabrication of the sample, its independence to electric field and the prominence of this peak in all three samples. Neither an attribution to a native defect (like V O ) nor to an impurity can be firmly established but a dual center defect composed of two sites with opposite charges is very probable.

The authors gratefully acknowledge support from National Research Agency (ANR) and Carnot funding.

2 FIG. 2 .

 22 FIG. 2. Experimental and simulated DLTS signal for (#1) MOVPE sample, (#2) high-pressure grown sample and (#3) hydrothermal sample. The lines are the simulated signal for the E3 level for each sample.

FIG. 3 .

 3 FIG. 3. Arrhenius diagram of E3 level for #1 MOVPE layer (open triangle), #2 high-pressure grown samples (open circle) and #3 hydrothermally grown sample (open square). The solid line is the global fit of all these points.


Mickaël Dardaillon

Kevin Marquet

Tanguy Risset

Jérôme Martin
email: jerome.martin@cea.fr

Henri-Pierre Charles
email: henri-pierre.charles@cea.fr

Compilation for heterogeneous SoCs : bridging the gap between software and target-specific mechanisms

Keywords: D, 3, 2 [Programming Languages]: Language Classifications-Data-flow languages; D, 3, 3 [Programming Languages]: Processors-Retargetable compilers

Current applications constraints are pushing for higher computation power while reducing energy consumption, driving the development of increasingly specialized socs. In the mean time, these socs are still programmed in assembly language to make use of their specific hardware mechanisms. The constraints on hardware development bringing specialization, hence heterogeneity, it is essential to support these new mechanisms using high-level programming. In this work, we use a parametric data flow formalism to abstract the application from any hardware platform. From this premise, we propose to contribute to the compilation of target independent programs on heterogeneous platforms. These developments are threefold, with 1) the support of hardware accelerators for computation using actor fusion, 2) the automatic generation of communications on complex memory layouts and 3) the synchronization of distributed cores using hardware mechanisms for scheduling. The code generation is illustrated on a telecommunication dedicated heterogeneous soc.

INTRODUCTION

Throughout its history, processor development has been driven by the Moore law, but was also by technology constraints. The power wall, whereby instruction level parallelism was not improved effectively by increasing transistor count and frequency growth as halted, was answered by the apparition of multi-core processors. We now enter the dark silicon era [START_REF] Esmaeilzadeh | Dark silicon and the end of multicore scaling[END_REF], which fixes a limit on the number of transistors that can be powered on at a given time. To answer this new limitation, chip designers are specializing parts of their design for application-specific constraints (e.g. video decoding, voice recognition), which leads to more and more heterogeneous System on Chip (soc) [START_REF] Burger | The Golden Age of Computer Architecture May Be Now[END_REF]. We now find hardware acceleration not only in computation, but also in communication and control, making it ubiquitous and which must be programmed efficiently.

From the software point of view, programming efficiently each new kind of architecture is a renewed challenge. The multiplication of cores requires explicit parallelism in the application, with several solutions from imperative concurrent models (e.g. Pthreads, MPI), but also approaches like the data flow model of computation (MoC). The emergence of heterogeneity brings a new constraint, each platform requiring specific instructions in order to take advantage of the specialized parts.

Our problem is to find how to program these new heterogeneous platforms efficiently. This efficiency has to be found both in terms of raw computing performance, but also in terms of time and difficulty to write new programs or adapt existing programs to new platforms. To reach this objective, a high-level language is necessary, current targets being too complex to be programmed using assembly language. Another constraint is the platform abstraction for both having a portable implementation and reducing the requirements on the platform mechanisms knowledge.

Another problem is that the targeted applications on these platforms adds both performance and timing constraints. As an example, telecommunication protocol lte-advanced requires 40 GOP S and a latency less than 2 µs [START_REF] Clermidy | A 477mW NoC-Based Digital Baseband for MIMO 4G SDR[END_REF]. In order to achieve the performance target, software optimizations can be done both at compilation time and at runtime. Runtime optimizations are able to reach high throughput by leveraging runtime knowledge, at the cost of an initial overhead. This overhead is usually made profitable given compatible time constraints, but is clearly not possible within our latency requirements.

To answer the high-level representation and parallelism constraints, we propose to use a parametric data flow MoC. In this model, data and task parallelism are exposed to the compiler. Moreover, this MoC permits many static analyses and associated optimizations to match the constraints of our target application.

In this paper, we propose compilation methods which do not exist in current state of the art data flow compilers. Our contribution is threefold :

• Platform independent language primitives thanks to the use of actor fusion.

• Compilation of parametric inter-core communications.

• Code generation for distributed scheduling targeting specialized controllers.

The remaining of the paper is built as follow: we describe our target demonstrator as well as related work on heterogeneous soc compilation in section 2 to motivate our work; the compilation MoC and language are introduced in section 3; contributions are described in section 4; results sustaining our approach are presented in section 5 before the conclusion.

MOTIVATION AND RELATED WORK

To better understand the characteristics of heterogeneous socs targeted by our compilation flow, we look at the cea Magali platform [START_REF] Clermidy | An Open and Reconfigurable Platform for 4G Telecommunication: Concepts and Application[END_REF], before reviewing related work in heterogeneous programming.

Heterogeneous SoC example : Magali

The Magali chip [START_REF] Clermidy | An Open and Reconfigurable Platform for 4G Telecommunication: Concepts and Application[END_REF] is a system on chip dedicated to physical layer processing of ofdma radio protocols, with a special focus to 3gpp lte-advanced as reference application. It includes heterogeneous computation hardware, with very different degrees of programmability, from configurable blocks to dsps programmable in C. As an example, one reconfigurable block is used to perform both an fft and a deframing (removing some of the resulting data). This operator permits to preserve only the significant data, hence reducing the data transmission time, but is also platform specific and needs to be abstracted away.

Communications between blocks use a 2D-mesh network on chip (Network-on-Chip). All the data communications are programmed statically on a credit/data mechanism between source and destination called icc for input, occ for output. One big difficulty when programming this platform is to guarantee consistency for all communications between all blocks, which for non trivial applications makes manual writing a daunting task. The example on Fig. 1 illustrates this on a toy application with 4 cores. In this example, core A sends 30 data to core C using occ 0. The occ configuration for sending data needs to know which icc it addresses and how many data it sends. Likewise, the icc 0 on core C needs to know how many credits to send and to which occ. found in [START_REF] Clermidy | A Communication and configuration controller for NoC based reconfigurable data flow architecture[END_REF]. The controllers in charge of the program sequences are limited in scope and platform specific, but also essential to efficiently use Magali. They are illustrated in Fig. 1. Core C distributed controller is programmed to repeat two times a first configuration, before switching to a second configuration. Using the same distributed control mechanism, communications sequences are also programmed for each input/output.

Looking at this example platform, we see that computation, communication and control are hardware accelerated and need to be supported in the programming flow. In the next section, we look at some significant works in the domain of heterogeneous soc programming from the target perspective, starting from general solutions before focusing on data flow programming.

Related work

For an embedded software programmer, the easiest way to program an heterogeneous platform is to use an imperative language (generally C language) associated with threads to express parallelism. It has been used to program both heterogeneous and homogeneous parallel platforms. For instance, the different units of the bear sdr platform [START_REF] Palkovic | Future Software-Defined Radio Platforms and Mapping Flows[END_REF] are programmed using C and Matlab code.

The ExoCHI [START_REF] Wang | Exochi: architecture and programming environment for a heterogeneous multi-core multithreaded system[END_REF] programming environment and Merge [START_REF] Linderman | Merge : A programming model for heterogeneous multi-core systems[END_REF] framework (based on ExoCHI) are proposals aiming at easing the programming of heterogeneous platforms while achieving good performances. The proposed solution extends OpenMP with intrinsic functions and dynamically maps the software on available resources. Similarly, OpenCL [START_REF] Jääskeläinen | OpenCL-based design methodology for application-specific processors[END_REF] can be used for heterogeneous platforms support.

The main limitation of these approaches is their lack of abstraction, requiring to program explicitly all hardware mechanisms. Even if using a high-level representation, the programmer still needs precise knowledge of the platform's specific resources, in order to write the required platformspecific program.

Numerous research works present arguments in favor of a paradigm shift and propose to program waveforms using data flow languages. These languages relies on a data flow Model of Computation (MoC) where a program is represented as a directed graph G = (V, E). An actor v ∈ V represents a computational module or a hierarchically nested subgraph. A directed edge e ∈ E represents a fifo buffer from its source actor S to its destination actor D. Data flow graphs follow a data-driven execution: an actor v can be executed (fired) only when enough data samples are available on its input edges. When firing, v consumes a certain amount of samples from its input edges and produces a certain number of samples on its output edges.

SDF/CSDF SP DF DDF

o o / / P rovability Expressivity Figure 2: Representation of the balance between provability and expressivity in data flow computation models.

Many data flow-compliant programming models have been proposed for specific applications; they are illustrated in Fig. 2. Synchronous Data Flow (sdf) means that the number of tokens necessary for an actor to fire is known at compile-time. In this case, static scheduling of actors can be performed and the size of the buffers between actors can be bounded. In Dynamic Data Flow, data samples consumed and produced by an actor at each firing can vary dynamically at runtime, and can even be 0 in order to provide more flexibility for programming. As a drawback, theoretical analysis capabilities are reduced. Between synchronous and dynamic data flow formalisms, a wide amount of models have been proposed, e.g. Cyclo-Static Data Flow (csdf) [START_REF] Bilsen | Cyclo-static dataflow[END_REF], Schedulable Parametric Data Flow (spdf) [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF]. The goal was to look for a trade-off between the ability to statically analyze programs and the expressivity of the languages.

ΣC [START_REF] Goubier | ΣC: A programming model and language for embedded manycores[END_REF] is a proposal to program waveforms using an extension of C. The corresponding MoC is more expressive than sdf thanks to non-deterministic extensions but still allows some static analyses to be performed such as bounding memory usage. However it does not allow dynamic behavior of actors. MAPS [START_REF] Castrillon | Component-based waveform development: the Nucleus tool flow for efficient and portable software defined radio[END_REF] is also based on a C extension, and uses a dynamic data flow MoC. The dynamicity is supported through a dynamic mapping, with high level operators mapped on accelerators at runtime. We can also mention work on the Magali platform using the kpn MoC [START_REF] Mrabti | Abstract Description of System Application and Hardware Architecture for Hardware/Software Code Generation[END_REF]. The mapping is done on abstract architecture and platform to reduce the platform dependency.

One common pattern in these approaches is the use of C language or a derivative to represent computation in a familiar manner, while using high level concepts such as threads or actors to convey parallelism. Platform specific operators are supported by libraries and apis, with some environments such as ExoCHI allowing to split operators to fit the platform granularity.

The recent progress of significative works such as ExoCHI and MAPS testifies to the importance of research in heterogeneous soc programming. However, these approaches uses dynamic MoCs which are supported by multi-core processors, but falls outside the scope of our platform. We propose to work on a parametric data flow MoC to get the desired expressivity while keeping analyzability. Starting from this premise, we put forward a new compilation flow and runtime for this MoC.

FRAMEWORK 3.1 Model of computation

In this work, we chose to start from a data flow MoC to harness its inherent parallelism and analyzability. Moreover, the need for verifiable but still flexible data flow MoCs recently lead to the appearance of two new MoCs: Scenario-Aware Data Flow [START_REF] Stuijk | Scenario-aware dataflow: Modeling, analysis and implementation of dynamic applications[END_REF] and Parametric Data Flow [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF]. Fradet and Girault identify a subclass of this MoC called schedulable parametric data flow (spdf) where the schedulability of the data flow graph can still be assessed statically. We chose to experiment using this MoC, but most of the contribution remains valid for analyzable data flow models. Moreover, sdf being a subset of spdf without parameters, our work and the resulting compiler applies to sdf.

To introduce spdf, a program is represented on Fig. 3 with four data flow actors named A,B,C and D. As in a classical data flow graph, the integers on the arcs represent the number of samples produced or consumed by the actor at each execution. In spdf, this number can be a symbolic parameter, the value of which is produced by an actor (e.g. the set p [START_REF] Bebelis | A Framework to Schedule Parametric Dataflow Applications on Many-Core Platforms[END_REF] in the left actor of Fig. 3).

A set p[1] B set q[p] C D 2p 1 2p p q pq p p
Figure 3: A simple schedulable parametric data flow graph [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF], p and q are parameters instantiated at execution.

One interesting feature of spdf is the ability to generate one schedule per actor, which is repeated at each iteration of the graph. The data flow graph being parametric, so is the number of iterations, and the generated schedule is a quasi-static schedule. As an example, the schedule for actor B in Fig. 3 is (pop p; (B p ; push q) 2 ), which reads as: get parameter p, then repeat twice the following: execute p times the core code of B, provide parameter q (computed in the core code of B). The reader is invited to refer to [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF] for implementation details.

Language

The language we propose is based on C++. It consists of a set of classes allowing to describe a parametric data flow graph. Fig. 4 illustrates the language on a small example.

Each actor has a single compute method that represents the execution of one iteration of the actor. The code of this method is written in C++ and uses various push/pop intrinsics to send/receive data, as well as set/get for parameters. An intrinsic api is also used for each application domain. It includes common, platform agnostic operations such as fft.

Choosing C/C++ language for the core code of the actors presents many advantages: it allows to reuse legacy code and highly optimized tools such as C compilers, do not require to learn a new language, and permits easy simulation and functional validation. Moreover, the support of a general purpose language for describing the graph structure greatly simplifies the development of complex applications. Having a graph representing all computations and communications is half of the work. We will explain in the next section how we use this representation to generate code for hardware accelerated computation, communication and scheduling.

void MIMO : : compute ( ) { [ . . . ] f o r ( i =0; i <n b a n t ; i ++) { v a l [ i ]= i n [ t a b [ i ] ] . pop ( ) ; } [ . . . ] (a) Core computation SRC s r c [ NB ANT ] ; FFT f f t [ NB ANT ] ; MIMO mimo (NB ANT) ; f o r ( i = 0 ; i <NB ANT ; i ++){ f f t [ i ] . i n <= s r c [ i ] . o u t ; mimo . i n [ i ] <= f f t [ i ] . o u t ; } (b) Graph code

CONTRIBUTIONS 4.1 Computation

In section 2.2 we have seen that support for hardware acceleration can be done using an api, which is the case in our approach. The difficulty to solve here is when a hardware accelerator covers several operations of the api. In that case the operations may be distributed into several actors, possibly preventing to take full advantage of the accelerator's capabilities. To solve this problem, we chose to repurpose the notion of actor fusion to support hardware acceleration.

Filter fusion was first introduced by Proebstring et al. [START_REF] Proebsting | Filter fusion[END_REF], and adapted to data flow in StreamIt [START_REF] Gordon | A stream compiler for communication-exposed architectures[END_REF]. Fusion is a transformation which assembles together two actors by merging their compute functions, enabling optimizations inside the resulting function. In previous works, optimization consists in inlining the code of the two actors, replacing fifos by local variables. This transformation enables code optimization on the resulting function, with buffer minimization or loop unrolling. In our case, it also enables the support of complex hardware accelerators by merging intrinsic calls in the same actor compute function, allowing the resulting actor to match the hardware granularity. We show below how to support spdf actor fusion and set conditions for fusing actors in an arbitrary complex graph. A B p q Figure 5: Simple parametric graph example. Fig. 5 illustrates a minimal parametric graph with two actors A and B we want to fuse. When fusing actors in sdf, rates between the two actors are used to compute the execution order of the resulting actor. Contrary to sdf programs where rates are statically known, here p and q are parametric expressions unknown at compilation time.

To fuse two actors in a parametric graph, we use the concept of local solution from spdf [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF] to solve the execution order. The local solution defines for a subset of actors the minimal number of iterations of an actor to return the subset to its initial state, and is denoted #LX. Using these local solutions, code is generated for the composite actor. The code resulting from fusion of actors A and B from Fig. 5 is illustrated in Fig. 6. The compute function of each actor Xi is inlined inside a loop repeated #LXi times, with #LA = q and #LB = p in our example. Local variables replaces fifo connecting actors. It is worth noting that push and pop access to this fifo in A::compute() and B::compute() are replaced by access to local variable fifo_AB. At this point, code optimization is applied on the generated function.

void AB : : compute ( ) { d a t a t f i f o A B [ p * q ] ; f o r ( i =0; i < q ; i ++) { A : : compute ( ) } f o r ( i =0; i < p ; i ++) { B : : compute ( ) } }
On the graph level, a composite actor is created with the two fused actors. The fifo between actors have been replaced, and others input/output fifos are connected to the resulting actor. Safe actor fusion is conditioned by the graph topology, some fusions possibly creating a graph deadlock. For example, in Fig. 7 the fusion of actors A and C would create an interdependency between resulting actor AC and B. Indeed, AC is waiting for data on edge (B,C) to start, while actor B is waiting for data on edge (A,B). From this interdependency ensue a deadlock between AC and B. In order to avoid such deadlock, we define a criterion for fusion safety.

Definition 1 (Fusion Safety). Let P (Xi, Xj) be the set of paths connecting actors Xi and Xj. The fusion between two actors Xi and Xj is safe if all paths between the two actors are a direct edge between them. Formally, ∀p ∈ P (Xi, Xj), p = (Xi, Xj)

Intuitively, this condition prevents the creation of new loops in the graph, effectively avoiding interdependency creation resulting in a deadlock. A similar condition is present in StreamIt, where vertical fusion is limited to pipeline construct [START_REF] Gordon | A stream compiler for communication-exposed architectures[END_REF].

Feedback loops are not accounted in our safety criteria, which ignores edges with initial tokens. Indeed, edges used for feedback loops have initial tokens to permit execution of the graph cycle. The liveness property defined in spdf [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF] ensures that enough tokens are available on each feedback edge to avoid deadlock. On this condition, the graph is said to be loosely connected, and we can safely ignore edges containing initial tokens in our fusion criterion.

Based on fusion mechanism, the mapping of actors on cores is responsible for the support of hardware mechanisms. If two actors are using api calls which are supported by a single core, these two actors are mapped on the same core and fused. Code specialization is applied in the resulting actor to match the platform operator granularity, optimizing hardware resources. Currently, due to resources constraints, the mapping in our compilation flow is provided manually by the programmer. Automation of this mapping could rely on a model of the platform cores and their affinity to api calls, which would take advantage of the platform heterogeneity. We describe concrete fusion example on our experimentation platform in section 5.

Communication

All communications in a data flow graph are explicit by construction, actors having no side effects. Using this property, we know statically all communications, with their sources, destination and the (potentially parametric) number of data exchanged. From this analysis, we can guarantee that the data flow graph can be executed in bounded time, with bounded memory, or send feedback to the programmer as to which part of his application is defective.

In our compilation flow, actors are statically allocated to cores. Using this mapping, fifo memory can be allocated locally to minimize the memory access cost. We note that application graphs have no prerequisite on the platform memory layout. From this observation, we conclude that our data flow application is platform-agnostic. Such a property is very important, as it unlock programming of very different platforms with possibly complex memory layouts, without putting the burden on the developer. Moreover, using the communication and placement information, we are able to generate all configurations for communication hardware mechanisms automatically. Compared with of the difficulty encountered when writing these configurations manually, as described in section 2.1, the data flow abstraction is a real game changer. The added bonus of this method is that communications are verified in the data flow graph, and the generated code is correct by construction.

Scheduling

Distributed scheduling of tasks is a hard problem to tackle by itself. The distributed controllers add to this complexity by requiring a specific model of execution (MoE), potentially different for each targeted platform. To solve this problem, we use the quasi-static schedule from spdf. This schedule model is interesting as it makes no assumptions on the underlying MoE. Looking at the bibliography, we back-up that claim with implementation on several platforms with very different MoE.

Dynamic scheduler. The authors of spdf propose a first model for parameter communications, using up and down samplers [START_REF] Fradet | SPDF: A Schedulable Parametric Data-Flow MoC[END_REF]. Their model can be scheduled as a dynamic data flow graph by existing approaches.

Slotted scheduler. In another approach on the Sthorm platform [START_REF] Bebelis | A Framework to Schedule Parametric Dataflow Applications on Many-Core Platforms[END_REF], the parametric data flow graph state is used to schedule actors in time slots. This approach could easily be adapted to use quasi-static schedules instead of the graph.

Split scheduler. We propose to use a new approach, splitting the schedule between central and distributed controllers, to demonstrate the versatility of our approach for platforms such as Magali.

To illustrate this splitting, we use the schedule of actor B from Fig. 3, (pop p; (B p ; push q) 2 ). In this schedule, B p is managed by the distributed controller, while parameter communication is managed by the central controller. For a large parameter p this distributed scheduling saves a lot of potentially costly synchronizations.

RESULTS

In the previous section we described how we abstract hardware acceleration using a data flow MoC, especially for computation, communication and scheduling. We are now going to demonstrate the viability of our approach on the cea Magali platform, answering the needs from section 2.1. We extracted representative parts of the lte protocol to illustrate the challenges in terms of programmability and dynamicity, and split them into 3 test case applications.

The mapping of the applications on the Magali architecture is illustrated in Fig. 8a. The FFT test case in Fig. 8b is a simple application demonstrating the support of platform specific operators. The parametric demodulation test case is presented in Fig. 8c. The upper part corresponds to demodulation of a lte frame header, which enables determination of the modulation scheme mod used to demodulate the remaining of the frame, as shown on the bottom part of the figure. An intermediate test case has also been set-up, which corresponds to the first part of previous test case, i.e. without the actors that depends on mod.

Computation

The fft test case showcases the support of platform specific accelerators using abstract operators because the ofdm core is capable of performing both an fft and a deframing operation, which are implemented using two actors in the application graph. The fusion of these two actors enables full support of the ofdm core. The fusion is also used on the sme core in the parametric demodulation. The split actor mapped to the sme is only doing data manipulation and can be processed by the occ mechanism on the sme core, reducing the required number of fifos. More complex fusions involving parameters have also been performed, for example on the rx bit core in the parametric demodulation test case.

Besides, to tackle the lack of support for variable modulation offered by the rx bit core, another feature has been introduced in our compilation chain: to address the translation of the mod parameter into real rx bit core configuration, and since the parameter has a limited set of possible values, the compilation flow generates for each value the corresponding configuration. Control code is automatically inserted in the scheduling to choose the correct configuration depending on the parameter value at runtime. Use of this feature is of course possible for other parameters and cores.

DSP$1$ CPU$ SME$1$ OFDM$1$ SME$2$ DSP$3$ DSP$4$ CHAN$DEC$ OFDM$2$ DSP$2$ SME$3$ RX$BIT$ NoC$I/O$Interface$ (a)

Communication

Reminding the constraints of the platform exposed in section 2.1, all communications on the Magali platform need to be statically generated. As we have seen, data flow exposes all communications, and we are able to assess statically for each communication the cores involved, the number of data sent, the parameters used and their producer. Using this knowledge, generation of the configurations for all icc/occ communications accelerators is automatic and suffers none of the complexity of the hand written approach, while resulting to similar performances (see section 5.4).

Scheduling

Once computation and communication are generated, the next step consist in scheduling them. From section 2.1, we know the Magali platform offers limited distributed scheduling capabilities. Expressivity of the quasi-static scheduling is supported by splitting the control between the central controller (an arm processor) and the distributed controllers (ccc), as illustrated in the split scheduler approach from section 4.3.

To make this splitting clear, we reuse the schedule example of actor B in Fig. 3: (pop p; (B p ; push q) 2 ). The ccc cannot produce or consume parameters, excluding pop p and push q commands. These steps are performed by the central controller. In turn, this controller sends the B p schedule to the ccc for distributed scheduling when knowing the p value.

The split quasi-static schedules are generated automatically by our compiler and benefit from the Magali platform specific support for parameters, which was not the case in previous works. This shows the relevance of the spdf to address distributed hardware constraints.

In terms of execution model, the central controller manages schedules for all cores using one thread per core. The synchronization with the distributed hardware is provided by interrupts and semaphores from the eCos operating system.

Performances

To assess the performances obtained using our compiler, we present execution times in Tab. 1. Results are compared between hand-written code, generated code and a previous work on the Magali platform [START_REF] Risset | Digital Front-End in Wireless Communications and Broadcasting, chapter Programming models and implementation platforms for software defined radio configuration[END_REF] for the first test case. This work uses a radio virtual machine to brings portability and flexibility, at the expense of byte code interpretation overhead. Moreover, the physical layer description model used is too simple to effectively take advantage of the distributed control features offered by Magali, resulting in an important increase of execution time. Indeed, the results on the fft test case showcase the need for distributed controller support, with ten times less overhead in our approach than in [START_REF] Risset | Digital Front-End in Wireless Communications and Broadcasting, chapter Programming models and implementation platforms for software defined radio configuration[END_REF]. For the two others test cases, the platform is correctly supported with our abstraction and applications are running faultlessly. The main reason for the overhead in the compiled application is the MoE used on the central controller. Typically, hand written code is synchronized on parameter exchange at the graph level, splitting the application in so-called phases. Our compiler generates a dedicated thread for each core on the central controller, aiming at a finer-grained control. This fine-grained control induces a higher number of synchronizations on the central controller, resulting in an important overhead.

It should be noted that the MoE used in Magali is independent from the compilation flow. In order to improve performances on this target, ongoing work is done to improve this model to fit the platform constraints. This can be done on the one hand by specializing the scheduler for the types of synchronizations required by data flow, on the other hand a better use of static knowledge harvested on the graph to reduce the number of synchronizations. This can be done while maintaining the same compilation flow, and will further prove the relevance of our approach.

CONCLUSION

Current architectural trend, especially in embedded applications, is leaning towards heterogeneous, specialized socs to answer energy and performance constraints. Programming these platforms is inherently difficult, with a lack of adapted tools and abstractions. New data flow MoCs such as spdf provide sufficient expressivity to describe the complex applications targeted by these platforms, as well as a relevant abstraction level to ease the programmer's work.

Based on that premise, we have shown how the analysis made on spdf can be used to generate code that takes benefits from the acceleration hardware mechanisms found in nowadays socs. We described the framework provided by our compilation flow for analysis on computation, communication and scheduling. Using these informations, we demonstrated the viability of our approach on the Magali lte modem prototype for each of these hardware mechanisms, backed by performances results on a real-world application.

Adapting this compilation flow to other heterogeneous platforms is currently ongoing, as well as optimization of the central scheduler to reach better performance on Magali.

Figure 9 :

 9 Figure 9 : Data and processing flows example

Figure 1 :

 1 Figure 1: Data and processing flows example in Magali (from [7])

Figure 4 :

 4 Figure 4: A simple program excerpt and the corresponding part of the graph for NB_ANT=4.

Figure 6 :

 6 Figure 6: Resulting code of actor A and B fusion in Fig. 5.

Figure 7 :

 7 Figure 7: Fusion example of actors A and C would lead to a deadlock.

Figure 8 :

 8 Figure 8: Mapping of the test case applications on Magali.

Table 1 :

 1 Performance result of generated code with respect to hand-written code

	Application hand-written generated	[17]
	fft	149 µs	168 µs	500 µs
			(+13%)	(+236%)
	demodulation	180 µs	283 µs	-
			(+57%)
	parametric	288 µs	558 µs	-
	demodulation		(+94%)

Acknowledgment

This work is sponsored by Région Rhône Alpes ADR 11 01302401.


Nabil Gader
email: nabil.gader@mvs.fr

Sandrine Ollinger
email: sandrine.ollinger@atilf.fr

Alain Polguère
email: alain.polguere@univ-lorraine.fr

One Lexicon, Two Structures: So What Gives?

We present a reinterpretation of lexical information embedded in the English WordNet in an alternate type of structure called lexical system. First, we characterize lexical systems as graphs of lexical units (word senses) connected mainly by Meaning-Text lexical function relations, then introduce a hand-built lexical system: the French Lexical Network or fr-LN, a lexical resource that implements a new lexicography of virtual dictionaries. We later explain how a corresponding en-LN has been generated from the English WordNet. Finally, we propose a topological contrastive analysis of the two graphs showing that both structures can be characterized as being Hierarchical Small World Networks.

Introduction 1.Context: the French Lexical Network

The RELIEF project [START_REF] Lux | Construction of a French Lexical Network: Methodological Issues[END_REF] is the first stage of a long-term lexicographic enterprise that aims at developing a broad-coverage French lexical resource: the French Lexical Network, hereafter fr-LN. This resource possesses two main characteristics.

Firstly, it is the product of actual lexicographic work but does not involve the writing of dictionary articles. Rather, textual dictionary-like descriptions can be automatically generated from linguistic information contained in the fr-LN, which can thus be considered as having embedded in it virtual dictionaries. For comparable approaches to the design of lexical resources, see for instance [START_REF] Atkins | Bilingual Dictionaries: Past, Present and Future[END_REF] and [START_REF] Spohr | Towards a Multifunctional Lexical Resource. Design and Implementation of a Graph-based Lexicon Model[END_REF].

Secondly, it possesses a very specific type of graph structure called lexical system, conceptualized in [START_REF] Polguère | Lexical systems: graph models of natural language lexicons[END_REF]. While WordNets are before of all graphs of synsets, lexical systems are graphs of specific word senses-i.e. lexical units, in our terminology-, connected by a rich set of lexical relations based on Meaning-Text lexical functions [START_REF] Mel | Lexical Functions: A Tool for the Description of Lexical Relations in the Lexicon. Lexical Functions in Lexicography and Natural Language Processing[END_REF][START_REF] Mel | Explanatory Combinatorial Dictionary[END_REF]. For instance, below is a typical synset relation taken from WordNet:

{army#1,regular army#1,ground forces#1} member meronym -------------→ {corps#1, army corps#1}

whereas only lexical function relations holding between specific word senses such as:

ARMY 1 Sing --→ CORPS 1
exist in a lexical system. 1In addition, each piece of information in a lexical system (mainly, lexical nodes and lexical function arcs connecting nodes) is supplied with a trust value, that is a measure of the validity of lexical information. For instance, information directly entered by lexicographers receive high or, even, maximal trust values, while information automatically generated by analogy-based algorithms should receive a low trust value. This allows for the implementation of "fuzzy" reasoning on lexical information.

At the time of writing, the fr-LN's wordlist contains 14,311 vocable entries-the term vocable designates a (potentially) polysemic word-, and 20,791 lexical units-actual word senses. Complete statistical data on the fr-LN are provided in section 3, including data on lexical function relations that weave the lexical network. Notice that these relations are not the only lexical connections encoded in the fr-LN. Each idiom, i.e. phrasal lexical unit, is connected to the lexemes it formally contains. For instance, the noun POMME DE TERRE 'potato' is connected to the corresponding lexemes POMME 'apple', DE 'of' and TERRE 'soil', via the description of its internal syntactic structure. Additionally, we have just started to encode copolysemy links: i.e. metonymy, metaphor, etc. links that connect senses belonging to the same vocable and form its polysemic structure.

Going English

The goal of this paper is to present an experiment that we have conducted in order to automatically generate an English Lexical Network, hereafter en-LN, from the English WordNet. Such task presents some similarity with previous attempts at compiling WordNet into specific data structuressee for instance [START_REF] Graves | Data Representations for WordNet: A Case for RDF[END_REF] and [START_REF] Xiao | An OWLbased WordNet lexical ontology[END_REF]. However, in our case, we "transmute" WordNet data into an informational content that is fundamentally different in nature.

One consequence is that information embedded in WordNet that is "deeper" (more conceptual) than strict linguistic knowledge is lost. This loss of information is compensated by a very important gain: a data structure that allows us to perform lexicographic work on the English lexicon using exactly the same advanced lexicographic tools we are using in our fr-LN project [START_REF] Gader | Hand-Crafting a Lexical Network With a Knowledge-Based Graph Editor[END_REF]. In other words, we can perform a lexicographic "graph weaving" activity on both French and English networks (cf. section 4).

The remainder of the paper is organized as follows. Section 2 describes how the task of compiling the English WordNet into an en-LN has been performed. Section 3 presents a contrastive topological analysis of the graph structure of both networks. Section 4 concludes on the practical interest of our experiment.

2 From WordNets to lexical systems

General characterization of the task

The extraction of an English lexical system out of WordNet's data is a process of bridging the gap between two non-equivalent information structures. The structure of lexical systems has been introduced in section 1.1. The structure of WordNet is well-known [START_REF] Kamps | Visualizing WordNet structure[END_REF] and a presentation in the present context would be overkill. It is however useful to summarize the main formal differences that exist between our source and target structures, i.e. to recapitulate our "one lexicon, two structures" problematics: see Table 1 This Prolog version of WordNet is made up of 21 files, each containing a Prolog database that is a set of Prolog "fact" clauses for a given predicate. For instance, the wn_s.pl file contains 212,558 clauses for the s/6 Prolog predicate (the 6-place s(ense) predicate), each clause encoding the description of one WordNet sense. The structure of the s/6 predicate is described as follows in the prologdb.5.pdf documentation file: s(synset_id,w_num,'word', ss_type,sense_number,tag_count).

For example, the following Prolog clause:

s(107544351,4, 'infatuation',n,2,0). asserts that there exists a WordNet nominal sense infatuation#2, that is the fourth sense in the synset whose id is 107544351 and that was not semantically tagged in WordNet's Semantic Concordances [START_REF] Miller | A semantic concordance[END_REF].

Out of the 21 Prolog files, 18 have been identified as containing information that could indeed be translated into lexical system data.2 Such data belong to three main categories: (i) lexical entities (mainly, lexical units and vocables), (ii) individual properties of lexical units (parts of speech, semantic gloses, etc.) and (iii) lexical function relations between lexical units.

Next section explains how this information has been generated from WordNet's Prolog files.

Generation of lexical data

For lack of space, we cannot account for all aspects of the compilation process. We focus on the insertion of pieces of information into the en-LN that are central to the characterization of this database as a lexical system.

Lexical entities

As shown earlier in Table 1 (section 2.1,above), there are no lexical entities corresponding to synsets in a lexical system. The nodes of such lexical networks are mainly lexical units, i.e. words taken in a well-specified meaning.

Our first task was to compile the en-LN's wordlist, i.e. the set of all its lexical units, grouped under poly-or monosemic vocables. In order to do so, we implemented the three following operations, using information from the wn_s.pl sense file (presented in 2.1 above).

Operation 1 We had to perform a preliminary clean-up of Prolog data, as we found a significant number (5,580) of duplicated clauses in the s/6 predicate database. 3Operation 2 We then created one vocable (new entry in the en-LN wordlist) for each distinct pair: word form, synset grammatical type . If there were two vocables with identical form but different synset grammatical types, we added the appropriate subscript to vocable names. For instance, from the two pairs:

'package', n and 'package', v , we generated two distinct vocables: PACKAGE N and PACKAGE V .

Operation 3 For each sense in the s/6 Prolog database, we created one lexical unit and connected it to the corresponding vocable-based on the word form, synset grammatical type pair found in the Prolog clause for the WordNet sense.

• If only one lexical unit was attached to a given vocable, its WordNet sense number4 was ignored-e.g., we generated the BACKGAMMON lexical unit in the corresponding monosemic vocable.

• If several lexical units were attached to a vocable, each one received the number of the corresponding WordNet sense-e.g., we generated two lexical units, GEEK 1 and GEEK 2, in the GEEK polysemic vocable.

The process of lexical entity generation resulted in a huge fully disconnected graph (a cloud of nodes without connecting arcs) comprising 206,976 lexical units-nodes in the graph-associated to 156,584 vocables,5 which gives a polysemy rate of around 1.322.

To conclude on the topic of the generation of lexical entities, it is important to recall that not all WordNet senses are indeed lexical units. There is a very significant quantity of phrasal entities6 in WordNet's synsets, and only a small proportion of those phrases are actual idioms, i.e. lexical units [START_REF] Osherson | The Representation of Idioms in WordNet[END_REF]. The automatic processing of WordNet data cannot separate true idioms from compositional phrases, and a manual post-processing of the en-LN will be necessary in order to validate the en-LN wordlist.

Important remark Our data structure allows us to specify a probability-understood as a measure of trust value-for each piece of lexicographic information entered into the en-LN (cf. properties of lexical systems, section 1.1 above). We have decided that information that is automatically generated will receive a 0.5 probably. This is true for the validity of vocables and lexical units, but also for lexical links and individual properties of lexical units that we have computed from WordNet. This strategy boils down to considering the current en-LN as being a "hypothesized lexical database."

Individual properties of lexical units

Five different types of individual properties have been assigned to lexical units in the en-LN: socalled WordNet "sense keys," parts of speech, syntactic features, semantic glosses and syntactic government patterns (subcategorization frames).

WordNet sense keys We found it essential to encode in the en-LN the correspondence between lexical units and WordNet senses, using WordNet IDs called sense keys. These IDs were extracted from the wn_sk.pl Prolog file and encoded as WordNet source features in the Grammatical Characteristics zone of the en-LN lexicographic articles. For instance, the lexeme INFATUATION 2 has received the value 'infatuation%1:12:02::' as WordNet source feature.

Semantic glosses In WordNet, semantic glosses are associated to synsets and not to individual senses.

Synset, gloss pairs were extracted from the wn_g.pl file and the en-LN article of each member of a given synset received the same gloss attribute. Computationally, glosses are simply stored as strings of characters in the Definition lexicographic zone, more precisely in its Comments section. tion (wninput.5.pdf file). Then, for each sense member of a given verbal synset, we entered the associated frame description into the Government Pattern zone (Comments section) of the corresponding lexical unit. Now that the generation of lexical properties has been explained, let us move to the crucial topic of weaving lexical function relations, that give the en-LN its connected graph structure.

Lexical function relations

In total, 12 Meaning-Text lexical functions [START_REF] Mel | Lexical Functions: A Tool for the Description of Lexical Relations in the Lexicon. Lexical Functions in Lexicography and Natural Language Processing[END_REF] have been used to encode lexical relations extracted from WordNet. They can be grouped into three different classes:

• 7 standard lexical functions: Syn∩, Anti∩, Gener, Mult, Sing, A 2 and Caus;

• 4 that have been "standardized" [START_REF] Polguère | Lexical function standardness. Selected Lexical and Grammatical Issues in the Meaning-Text Theory[END_REF] in the context of previous projects: Cf, Hypo, Holo and Mero;

• 1 non-standard: Unspecified derivative. For lack of space, we focus below on the generation of only three lexical links, that are the most significant statistically: Syn∩, Gener and Hypo.

Extraction of Syn∩ relations The Syn∩ lexical function stands for 'intersecting synonym'; its extraction from WordNet was done as follows:

If

sense 's' belongs to synset S And L 's' is the lexicalization of 's' in the en-LN Then the lexicalizations of all other senses belonging to S are targets of Syn∩ links originating from L 's' And the same principle applies recursively to all other senses of S.

This principle entails the "saturation" of all possible Syn∩ links among all elements of all synsets in WordNets. And each application of this principle on a synset generates a saturated subgraph.

Figure 1 below shows the Syn∩ saturated subgraph generated from synset (1).

(1) {puppy love,calf love, crush#3-n,infatuation#2}

PUPPY LOVE CALF LOVE CRUSH N 3 INFATUATION 2 Figure 1: Syn∩ saturated subgraph for synset (1)
We made the hypothesis that most synset members in WordNet are connected by the intersecting approximate synonymy relation Syn∩, rather than by exact synonymy Syn. We expect that our strategy will entail less manual corrections when the en-LN will be used for lexicographic purposes (section 4). Synset (1) is a clear illustration of the potential relevance of our hypothesis, as senses in (1) are indeed not exact synonyms.

Extraction of Gener ∼ Hypo relations Gener is a Meaning-Text standard lexical function and stands for 'generic term'. Though it is close to WordNet's hypernymy, it was not possible to systematically extract Gener relations from WordNet's hierarchical organization, for two reasons.

Firstly, the hypernymy relation holds between synsets, whereas Gener connects lexical units.

Secondly, Gener is more specific than Word-Net's hypernymy. It holds between two lexical units in only two specific cases, illustrated below.

A. FRUIT is a Gener of BANANA because it is possible to say (2).

(2) bananas, apples, oranges and other fruits B. SUBSTANCE is a Gener of GAS because (3a) can be paraphrased as (3b) using GASEOUS, the adjectival counterpart of GAS.

(3) a. gas b. gaseous substance

Gener is thus before all a lexical, rather than conceptual or denotational relation. In the context of our lexical projects, Gener is paired with a symmetrical lexical function called Hypo, for 'hyponym'. Notice that this latter lexical function does not belong to the original set of Meaning-Text standard lexical functions. Gener ∼ Hypo relations were mainly extracted from hypernym relations between synsets (wn_hyp.pl file) as follows:

If synset S 1 is a hypernym of synset S 2
And S 1 is the hypernym of more than 15 synsets Then all senses of S 1 are targets of Gener links originating from of all senses of S 2 And all senses of S 2 are targets of Hypo links originating from of all senses of S 1 .

This ensures that there is no explosion of the number of invalid Gener and Hypo links. After doing some testing with different thresholds, we reached the conclusion that a synset that happened to be the hypernym of more than 15 other synsets had the greatest chance to contain true generic terms (in our sense). 7With this strategy, we caught in our nets "only" 111,032 Gener relations and the same number of Hypo relations. Without the ">15" constraint, numbers would have been much higher and en-LN data much less accurate.

A smaller set of Gener and Hypo relations (69,696) has been extracted from instance→type relations between nominal synsets (wn_ins.pl file) based on the following principle:

If

synset S 1 is a type of synset S 2 (that is its instance) Then all senses of S 1 are Gener of all senses of S 2 And all senses of S 2 are Hypo of all senses of S 1 .

To conclude this section, notice that the strategies applied for extracting Syn∩, Gener and Hypo relations-which implies symetric relations-are chiefly responsible for the very high proportion of "mutual arcs" in the graph-see section 3.1 below, that presents a topological comparison of the frand en-LNs.

Accessing the resulting en-LN

Once the interpretation of WordNet information into a lexical system structure is performed, we are able to access and navigate through the en-LN with the Dicet lexicographic editor, designed for lexicographic work on the fr-LN. In actual fact, we are now able to edit and transform the newly generated en-LF using our lexicographic approach.

In order help the reader have a more concrete grasp of how different the English lexical system is from WordNet, we provide in Figure 2 below a lexicographic view of the first sense of the GEEK vocable. For a presentation of the specificity of lexicographic editing by means of the Dicet editor, see [START_REF] Gader | Hand-Crafting a Lexical Network With a Knowledge-Based Graph Editor[END_REF].

Graph properties

The aim of this section is three-fold:

1. to determine to what extent the fr-LN and the en-LN differ in terms of mathematical organization;

2. to formally characterize the structure of both networks as so-called Hierarchical Small World Networks, which is the expected graph type for lexical systems;

3. to use the full-scale nature of the en-LN, inherited from WordNet, to anticipate future formal properties of our "adolescent" fr-LN.

Section 3.1 presents a formal characterization of the fr-/en-LNs from the viewpoint of their graph structure. Topological analyses of both graphs allow us to mathematically compare their formal structure. Section 3.2 summarizes this comparison in layman terms and draws conclusions from formal differences that have emerged.

Formal topological analysis

Structural properties of our lexical systems were studied using pedigree.py, a Python script developed by Emmanuel Navarro [START_REF] Gaillard | Invariants and Variability of Synonymy Networks: Self Mediated Agreement by Confluence[END_REF]. This script performs topological analyses-called graph pedigrees-, that allow for rigorous graph characterization and comparison. More specifically, we seek to determine if the fr-/en-LNs are Hierarchical Small World Networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF][START_REF] Mark | The structure and function of complex networks[END_REF][START_REF] Gaume | Balades Aléatoires dans les petits mondes lexicaux[END_REF].

Hierarchical Small World Networks, hereafter HSWN, exhibit four properties: 1. low density, i.e. small number of arcs compared to the number of nodes;

2. high global clustering coefficient, i.e. high number of connected neighbor nodes;

3. distribution of degrees (probability distribution of number of arcs associated to a node) that follows a power law;

4. low average path length, i.e. small average minimal number of arcs between two nodes for each possible pairs.

Table 5 below shows the pedigree of our two lexical systems.

The current fr-LN comprises 9.9 times less nodes (n) than the English network-straight from the oven-, for 27.1 times less arcs (m). To determine if these densities are low, we compare m to n 2 and nlog(n). n 2 is the maximum amount of arcs that can exist for a given number of nodes and a unique relation type. 8 It is about 432 × 10 6 for the fr-LN and 43 × 10 9 for the en-LN. From this point of view, their densities are low. nlog(n) represents the order of magnitude of HSWN's density [START_REF] Gaume | Balades Aléatoires dans les petits mondes lexicaux[END_REF]. It is about 89,773 for the fr-LN, which is twice the current amount. For the en-LN, it is about 1,100,267, which is close to what we measured. The fr-LN is a work in progress. It includes a high proportion of single nodes (17%), which implies a high number of strongly connected components (ncc) 9 and explains its small largest con-9 Single nodes are considered to be strongly connected components.

nected component (LCC). The network increases in arcs more quickly than in nodes, due to the organization of the lexicographic work. In addition, the amount of single nodes decreases. The en-LN has not undergone any evolution yet. However, it will be manually transformed in the future. Some arcs will be added and its proportion of single nodes (2%) will decrease. Some arcs will also be modified or deleted. For example, its unique loop is a WordNet error and will be eliminated from the en-LN (as it should be from WordNet). 10The French network, which contains a wide variety of links (662), has 44.6% of mutual arcs-i.e. arcs a → b for which a reverse arc b → a exists. They are many more in the en-LN (99.5%), due to the nature of the 12 lexical links encoded.

To For our networks, C may seem small. However, as Table 7 shows, they are higher than for similar classical random graphs [START_REF] Mark | The structure and function of complex networks[END_REF]. In other words, these networks hold sets of highly connected lexical units.

To assess the structure of these lexical agregates in the network, we need to examine the distribution of degrees and the average path length (L).

As our networks are oriented, we focus only on their out distribution of degrees. Both networks follow a power law with a good correlation coefficient (r 2 ). In Table 5 above, a stands for the coefficient of the best fitting power law of these distributions. Such a distribution is in the same range as for typical HSWNs. This means that a few number of lexical units are highly connected to a slightly higher number of other lexical units, themselves connected to a slightly higher number of other lexical units. To put it differently, our networks contain lexical hubs and are hierarchically structured. [START_REF] Bollobás | The Diameter of a Scale-Free Random Graph[END_REF] have shown that the L of HSWNs does not exceed logn/ log logn. Such a value for L means that it is possible to move rapidly from a node of the network to another.

As our networks have more than one component, measure of their L is problematic [START_REF] Mark | The structure and function of complex networks[END_REF]. In fact, it is difficult to define a path length between two non-connected nodes. A possible alternative can be to consider the L of LCC (L_lcc). Table 8 shows that L_lcc of our networks are higher than expected. For the French network, LCC is very small and probably not representative of the whole network. For the English network, the problem is different. The original structure of WordNet keeps separate the synsets of the four major parts of speech (with marginal transversal connections). It is reasonable to believe that some structuring lexical relations between agregates belonging to different parts of speech are missing.

To conclude, our fr-and en-LNs seem to be both structured as HSWNs, but have an average path length higher than they should have.

In layman terms

As indicated in section 3.1 above, the en-LN is substantially larger than the current fr-LN. In contrast, lexical relations are more diverse in the latter.

Despite such differences, the global structure of both networks appear to be similar. They seem to represent the same type of lexical organization. In both cases, senses are organized in highly connected subsets and some lexical units assume a pivotal role. These characteristics appear consistent with a semantic field structure. Further investigation is required to learn more about highly connected components, like the nature of links and lexical units involved. Some new similarities might then emerge.

The question of a fast and easy access between lexical agregates remains. More detailed observation would be required to determine why such an access is not possible in the LNs. The en-LN is made up mostly of paradigmatic links. Maybe this characteristic is the cause of our trouble. But this explanation does not hold in the case of the fr-LN. In a study of WordNet, where the different parts of speech are structured together, [START_REF] Sigman | Global organization of the Wordnet lexicon[END_REF] propose to introduce polysemous links to improve access between lexical units. We are currently implementing the weaving of such links in the fr-LN and more will be known soon about their incidence on the global structuring of LNs.

So what gives?

In form of conclusion, we summarize the practical interests of performing the WordNet → en-LN compilation. Two main points should highlighted.

First and foremost, as stated in section 2.3, we are able to wade through the en-LN and edit it using our "graph weaver:" the Dicet lexicographic editor. This is essential to us as we believe that the lexical system model ought to be extensively tested as an alternative to more ontological approaches to lexical knowledge structuring, such as WordNets.

Second, thanks to WordNet, we now have at our disposal a lexical unit-based access to the English lexicon that can be used to explore structural behavior of full-scale lexical systems, in anticipation of the fr-LN reaching lexicographic maturity.

Figure 2 :

 2 Figure 2: (Partial) lexicographic view of GEEK 1.

  below.

	English WordNet	en-LN
	Synsets as structural units	Lexical units as structural
	of description	units of description
	Global partition based on	No part of speech parti-
	parts of speech (N, V, Adj,	tion
	Adv)
	Top-down hierarchical or-	Multidimensional organi-
	ganization	zation
	Chiefly based on the	Based on a set of lexi-
	hyper-/hyponymy relation	cal function relations be-
	between synsets	tween lexical units
	Table 1: One lexicon, two structures.
	Computationally, our source dataset was the
	ANSI Prolog version of Princeton WordNet 3.0.

  Parts of speech (POS) WordNet 'synset types' have been retrieved from the wn_s.pl Prolog file and encoded as Part of speech features in the Grammatical Characteristics zone. The correspondence between WordNet synset type codes-SType-and en-LN's parts of speech-POS-is given in Table2below.

	SType	POS
	v	'verb'
	n	'proper noun' if name starts with a capital
		letter, 'common noun' otherwise (of course,
		a very approximate rule of thumb)
	a and s 'adjective'-we used only one part of
		speech for adjectives as we consider that
		WordNet's class of satellite adjectives (s
		type) pertains to WordNet internal organiza-
		tion rather than to the identification of gram-
		matical behavior
	r	'adverb'

Table 2 :

 2 en-LN interpretation of synset types.

	Syntactic features Features corresponding to
	information on syntactic behavior of adjectives
	(syntactic role and linear positioning) were re-
	trieved from the wn_syntax.pl Prolog file,
	where they are associated to individual senses.
	Table 3 below describes how this information
	has been encoded as features in the Grammatical
	Characteristics zone of the en-LN.

Syntactic government patterns

We retrieved associations between synsets and WordNet's syntactic frame codes in the wn_syntax.pl Prolog file. The definitions of syntactic frames themselves where taken from WordNet's documenta-

Table 3 :

 3 en-LN interpretation of syntactic features.

Table 4 :

 4 Table4below gives statistics on the distribution of lexical links pulled in the en-LN for each of those twelve lexical functions. Lexical function links in the en-LN.

	Number of links Lexical function
	315,984 Syn∩
	145,880 Gener
	145,880 Hypo
	89,107 Unspecified derivative
	59,981 Mult
	59,981 Sing
	50,746 Cf
	35,663 Mero
	33,684 Holo
	7,979 Anti∩
	1,250 Caus
	73 A 2

Table 5 :

 5 Pedigree of the fr-/en-LNs.

		fr-LN	en-LN
	n	20,791 206,976
	m	34,920 946,208
	<k>	3.3406	5.9029
	Directed	true	true
	Mutuals	15,576 942,795
	Loops	46	1
	Single	3,540	19,756
	Multiples	432	124
	ncc	14,295	34,342
	C	0.1058	0.1031
	Out degree distribution
	a	-2.0243 -1.8479
	r 2	0.9572	0.8453
		LCC
	n_lcc	1,788 144,294
	m_lcc	5,973 851,748
	C_lcc	0.2816	0.0980
	L_lcc	13.0861 10.1479

Table 6 :

 6 Table 6 shows this evolution over five months. Evolution of the fr-LN.

		June 2013 Oct. 2013 Evolution
	Arcs	25,932	34,920	+35%
	Nodes	18,057	20,791	+15%
	Single	3,614	3,540	-2%

Table 7 :

 7 estimate how nodes and arcs are locally or-ganized in networks, one needs to examine their global clustering coefficients (C). Global clustering coefficients.

	Nodes	Arcs C Lexical C Random
	20,791	34,920	0.1058	0.00016
	206,976 946,208	0.1031	0.00004

Table 8 :

 8 Average path lengths.

		n_lcc logn/ log logn	L_lcc
	fr-LN	1,788	6.350 13.0861
	en-LN 144,294	7.240 10.1479

Sing is the singulative lexical function.

The three unused files are: wn_cls.pl (class relations between synsets), wn_sa.pl (rather heterogeneous relations between verbal or adjectival senses) and wn_vgp.pl (similarity relations between verbal synsets).

We actually discovered other errors in the Prolog files (mainly, but not only duplicates) that we had to circumvent in order to avoid the generation of inconsistent data in the resulting en-LN. The list of errors can be provided on request.

WordNet sense number is necessarily 1 in such cases.

Cf. section 1.1 above: vocables are considered as more abstract lexical entities and are not counted as actual nodes of the lexical graph.

Phrasal senses are called collocations in WordNet terminology. This is a different notion from that of collocation understood as semi-phraseological expression-e.g. support verb constructions such as take a nap[START_REF] Benson | The Structure of the Collocational Dictionary[END_REF].

For instance, the WordNet sense car#1 belongs to a synset that is the hypernym of 31 other synsets. It has thus been identified as good candidate for generic term; as a result, the corresponding lexical unit is the Gener of 66 other lexical units in the en-LN. In contrast, desk#1 belongs to a (singleton) synset that is the hypernym of only 3 other synsets; no Gener link has been pulled from the DESK lexical unit.

In our case, there are 662 different relations involved in the fr-LN and 12 in the en-LN. The maximum amount of arcs increases proportionaly.

This is a derivationally related form arc connecting unicyleN to itself, that is present in both the on-line WordNet 3.1 and the Prolog database we used.

Acknowledgments

Work on the fr-LN is supported by a grant from the Agence de Mobilisation Économique de Lorraine (AMEL) and Fonds Européen de Développement Régional (FEDER). We are grateful to Veronika Lux-Pogodalla and two GWC2014 reviewers for their comments on the first version of this paper. Emmanuel Navaro has been very helpful in providing feedback on the use of Pedigree.py.


Marouan Bouali
email: marouan.bouali@inria.frhussein.yahia@inria.fr

Hussein Yahia

Antonio Turiel
email: turiel@icm.csic.espatrice.henry@cnes.fr

Patrice Henry

A Multifractal approach for sun glint in medium resolution satelite imagery

Sun glint, the specular reflection of sunlight off the ocean surface and into the satellite sensor, compromises data processing in ocean remote sensing imagery. Several correcting algorithms and models have been developed to improve satellite high-level products quality in glint-contaminated areas. Some rely on radiative transfer equations and others on in-scene information analysis, but most of these methods are based on an estimation of the sun glint contribution in terms of radiance.

In this paper, we introduce a new approach for sun glint study in medium resolution satellite images, derived from multiscale/multifractal techniques. Since sun glint introduces long range effects and occurs at a scale much smaller than pixel dimensions, multiscale techniques are well suited to analyse such complex signals and are able to extract features related to the oceanic flows. First, we apply a multifractal decomposition scheme to generate the signal singularity exponents and retrieve the so-called "most singular manifold". Using the main streamlines of the signal, we compute a reduced image containing the same multiscale structures as the original one but a naive distribution of the gradient.

We will then show that the correlation between the original image and the reduced one, also known as the source field in the microcanonical multiscale formalism, displays a signature related to the presence of sun glint.

INTRODUCTION

The revolution introduced by remote sensing and the increasing amount of data collected by earth observing satellites are expected to deliver major advances in earth observational geophysical sciences. In a socio-political context where global warming and climate changes have become a priority, cooperations between different scientific communities are quickly gearing towards a better understanding of the Atmosphere/Ocean interactions. Although products from medium resolution satellites provided great success in the fields of geophysical phenomena and ocean processes modelling, many issues currently persist and are yet to be solved. Among these issues, sun glint is the most recurrent one.

Since Cox/Munk's model [1] established more that a half century ago, many different approaches have been suggested in the literature to deal with the sun glint issue, however, most of them rely on a sun glint radiance estimation through complex radiative transfer modelling [2][3] or in-scene information analysis [4][5]. Given the huge multidisciplinary interest in the study of ocean tracers dynamics, the exact value of a given pixel radiance is of poor interest compared to the local variations that can be observed within a specific geophysical signal. In medium resolution imagery, suffice it to notice the small-scale effect associated with sun glint, to immediately invoque multiscale techniques.

In this paper, we make use of the most known "microcanonical multiscale formalism" (MMF) as a new approach for sun glint in medium resolution images. On the assumption that sun glint and atmospheric effects have little impact on the signal local behaviour, multiscale techniques should be able to detect many sharp transitions that correspond to oceanic features such as sea surface temperature or water-leaving radiance streamlines.

This paper is organised as follows: In section 2, we present the basis of the multifractal decomposition scheme used to generate the singularity exponents and retrieve the "most singular manifold". In section 3, we illustrate the results obtained on MODIS images. The chromatically reduced signal and source field framework will also be presented in this section. Discussion, conclusion and future work are given in section 4.

ASPRS 2009 Annual Conference

Baltimore, Maryland March 9-13, 2009

SECTION II: MICROCANONICAL MULTISCALE FORMALISM

In the following sub-section, we outline the main concepts of our approach. However, the reader is invited to read [6-7] for a complete presentation of the theoretical background and experimental results obtained with the MMF.

Singularity Exponents

The fundamental idea of the MMF consists in defining a local singularity exponent for each pixel of an acquired signal.

In the following, we denote ( ) I x r the signal associated to the image, where x r represents the two-spatial coordinates of a pixel. Using the modulus of the image spatial gradient ( )

I x ∇ r
, we define the density measure μ as:

d I dx μ = ∇ v (1) Since I is defined over a compact subset 2 A ⊂ ( ) ( ) A A d x I x μ = ∇ ∫ r v ( 2 )
For a wide variety of geophysical signals [8][9], the measure μ behaves in such a way that every pixel x r of the image satisfies the following power-law behaviour equation:

( ) ( ) ( ) ( ) ( ) ( ) d h x d h x r B x x r o r μ α + + = + r r r r (3)
where r B is a ball of radius r centred at x r and d the space dimension (d=2).

The coefficient ( ) h x r

in the previous equation is the local singularity exponent. This exponent quantifies the local transition of grey level values in each pixel of the image. In practice, a direct log-log linear regression on the previous formula will provide inaccurate numerical results for the exponents due to the discretization of the radius r . To overcome this issue, we take advantage of the fact that a wavelet projection of the measure defined in (2) also scales as a power law in r, with the same parameter ( ) h x r

. Let ψ be an appropriate wavelet. The projection of μ over ψ at the point x r is given by:

( ) ( ) 1 , d x y x r d y r r ψ μ μ ψ ⎛ ⎞ - Τ ≡ ⎜ ⎟ ⎝ ⎠ ∫ r ur r u r (4)
and satisfies the following law:

( ) ( ) ( )
( ) ( ) , d h x d h x x r x r o r ψ ψ μ α + + Τ = + r r r r ( 5 )
The singularity coefficients ( ) h x r are then obtained with a linear regression between

( ) ( ) log , x r ψ μ Τ r and log r .
In the MMF, the singularity exponents have proven to hold a very good description of the thermodynamic powerlaw behaviour associated with turbulent phenomena in sea surface temperature [8]. Baltimore,2009

ASPRS 2009 Annual Conference

Most Singular Manifold

According to [11], the existence of a multifractal measure implies an organisation of the signal in multifractal sets which dimensions can be predicted by its statistical properties. By assigning to each a singularity exponent, the image can be decomposed into several hierarchical sets that correspond to superstructures with the same geometrical and statistical properties.

In the MMF theory, experimentation shows that the singularity spectrum is bounded and that there exists a specific exponent h ∞ , called the most singular exponent that characterizes the strongest irregularities of the signal.

We define the Most Singular Manifold (also denoted F∞ ) as the following set of pixels:

( ) { } ~: F x h x h ∞ ∞ ≡ = r r ( 6 )
In the implementation process, we also take into consideration the parameter h Δ that allows us to define the range of values retained for F∞ . In other words, the level-set F∞ contains all the pixels which singularity exponent lays

in the interval [ ] ; h h h h ∞ ∞ -Δ + Δ .
From a statistical point of view, the MSM will contain most of the signal's information. Therefore using only the spatial gradient over pixels of the MSM, it is possible to estimate the intensity field of every pixel and to compute the fully reconstructed image (FRI) with the following reconstruction formula:

( ) ( )

I x g I x ∞ = ⊗∇ uur r r r (7)
where ⊗ is the convolution symbol, I ∞ ∇ uur is the essential gradient (equals ( )

I x ∇ uur r
over the MSM and 0 elsewhere) and g r is the universal reconstruction kernel. In Fourier space, the kernel propagator can be expressed as:

( ) 2 ˆf g f i f = r r r r (8)
leading to the following reconstruction formula in Fourier space:

( ) ( ) 2 . i f I f I f f ∞ ∇ = uu ruur ur ur $ (9)
where f r is the frequency vector and i the imaginary unit ( 1 i = -).

Reduced Image

In this section, we go further in the multifractal analysis in order to characterise the sun glint. The concept of chromatically reduced image has been initially introduced in [9] and applied to meteorological images to improve the detection of rainfall areas. It relies on the separation of the luminance distribution from the multifractal sets of the signal. The chromatically reduced image is computed so that it contains the same distribution of singularity exponents than the original image. Consequently, the reduced signal will display the same multifractal structures as the original one, but it will have a different distribution of the gradient over the MSM.

The reduced image essential gradient R I ∇ is computed so that:

ASPRS 2009 Annual Conference Baltimore, Maryland March 9-13, 2009 - ( ) 1 MSM 0 R if x I x otherwise ⎧ ∈ ⎪ ∇ = ⎨ ⎪ ⎩ r uuuu r r - ( ) R I x MSM ∇ ⊥ uuuu r r - ( ) ( ) . 0 R I x I x ∇ ∇ > uuuu r

Source Field

The source field expresses the relationship existing between the original image and its reduced part. Since these two images have exactly the same multifractal structure, the source field can be viewed as a nonmultiscaling functional representative of the image dynamics.

To define the source field, we generalize the multifractal measures defined in equation ( 2 ( ) ( )

I A A dx I x μ = ∇ ∫ uur r v (10) and ( ) ( ) R I R A A dx I x μ = ∇ ∫ uuur r v (11)
The complex vectorial source field is then defined as the Radon-Nykodin derivative: Because the source field represents the ratio between two multifractal measures, it's reasonable to assume that it will contain an information independent of the ocean tracers turbulent character.

SECTION III: APPLICATION TO OCEANOGRAPHIC MODIS DATA

In this study, we have used both MODIS Terra and Aqua Level 1B data consisting of calibrated Top Of Atmosphere (TOA) radiances at 1km resolution, downloaded from http://ladsweb.nascom.nasa.gov/ and the corresponding level 2 products downloaded from http://oceancolor.gsfc.nasa.gov/.

Singularity Exponents and Sun Glint

The goal of this sub-section is to show that in spite of the long range effect introduced by sun glitter, some of the information related to oceanic tracers streamlines is yet accessible through multiscale techniques.

To illustrate this idea, we have selected a 512×512 sub-image with moderate sun glint, extracted from a Modis Aqua image captured on August 3 2007, in the Mediterranean Sea.

Figure 1 shows the singularity exponents computed on both band 23 (4 µm) and 31 (11µm). The reason why these bands have been chosen for our study relies on the fact that they are both used for the retrieval of Modis level 2 Sea Surface Temperature. Whereas the emissive bands 31 (11µm) and 32 (12µm) always provide a reliable SST, the computation of the STT with short wave bands 22 and 23, is generally discarded for day time measurements because of sun glint. However, as seen in figure (1), it is clear that despite the sun glitter effect, ASPRS 2009 Annual Conference Baltimore, Maryland March 9-13, 2009 the MMF is still able to extract many significant superstructures that can be correlated with those extracted in long wave bands.

In figure (2), we have computed the singularity exponents on the level 2 SST and the 412 nm water-leaving radiance corresponding to the same time period and location as figure (1). Once again, several identical features can be identified through the multiscale singularity analysis, confirming the idea that sun glint and atmospheric effects do not significantly alter the multifractal character of the oceanic flows. Besides the numerous common filamentary structures observed in figure (1) and figure (2), it is interesting to point out that the singularity exponents are also contaminated with striping effect. The scan line noise due to imperfect detectors calibration introduces periodic lines in the singularity exponents that do not reflect any real geometrical irregularities and therefore harden the analysis of the signal dynamics.

Characterisation of Sun Glint

The source field framework, which theoretical content has been presented in section 2 is used here to characterize the presence of sun glint in images. The information contained in the source field illustrates the existing deviation between the original signal and its reduced part leading the later to act as a synthetic template containing all the multiscale features. Because the original image and the reduced one both share the same multifractality, strong deviations in the source field will be automatically associated with perturbations that do not hold any particular multiscale properties.

In figure (3), we illustrate the reduced image and source field framework on a 512×512 sub-image extracted from a Modis Terra image captured on August 1 2008, in the Mediterranean Sea, and heavily affected by sun glint. The island at the left top corner is Sicily.

A clear signature can be seen in the source field, in the middle of the glinted area. It appears as a concentration of poles and zeros in the modulus of the source field. To make sure that this signature is related to the sun glint, the source field has been also computed in the band 17 (890-920 nm), where the water leaving radiance is known to be very weak.

This characterization of sun glint with the source field framework is quite promising if we keep in mind the fact that any signal is reconstructable just knowing its reduced part and the source field.

SECTION IV: DISCUSSION AND CONCLUSION

In this paper we have introduced a new approach to analyse medium resolution images contaminated with sun glint.

The detection of filamentary structures within areas affected by sun glint underlines the potential of the MMF to process oceanographic data through singularity analysis and constitutes a preliminary result that deserves further work. Application of the MMF on Modis level 1B TOA radiances and level 2 products displayed many interesting similarities in the extracted streamlines. It is obvious that sun glint and atmospheric components have their own multifractal distribution, but their contribution to the TOA signal do not always mask the sharp transitions associated with water leaving radiance or SST features, which allows multiscale techniques such as the MMF to extract them.

The source field framework presented in section 2c and 2d offers an interesting decomposition of the image, in that a robust modification of the source field could reduce the effects of sun glint and therefore improve the detection and classification of the observed singularities. However, the manipulation of the source field is extremely sensitive and further research is being conducted to reconstruct an image with a modified source field without introducing any artefacts.

ASPRS 2009 Annual Conference

Baltimore, Maryland March 9-13, 2009 Also, with our multifractal approach, the detection of geometrical structures associated with ocean flow dynamics, relies on the assumption that the sun glint contribution to the signal can be considered as an additive smooth radiance without any strong geometrical irregularities.

However, we have noticed that in many cases, Modis images display anomalous features that appear as "glint gaps" within the characteristic white stripe. For instance, it is well know that in medium resolution satellite imagery, sun glint tends to highlight many phenomena such as oil slicks or internal waves [10].

Future improvement of our work consists in providing an accurate discrimination of the extracted features. A possible methodology could be to integrate in the MMF algorithms, additional data related to the sun glint spectral properties.

  gradient vector instead of its norm:

Figure 1 .Figure 2 .

 12 Figure 1. Top: Image from Modis Aqua band 23 (4.020-4.080 µm) captured on August 3 2007 in the Mediterranean Sea affected by sun glint. The sun glint intensity gradually decreases from left to right. The two islands in the middle left are Minorqua and Majorqua (left); Image from Modis Aqua band 31 (10.780-11.280 µm). Modis band 31 is used to retrieve the day time SST and offers the advantage of glint free data (right). Bottom: Graylevel representation of the singularity exponents computed on band 23 (left) and band 31(right); The brighter the pixel, the greater the singularity at this point.

  Figure 3. Top: Image from Modis Terra band 10 (483-493 nm), captured on August 1 2008, in the Mediterranean Sea; the island in the top right corner is Sicily (left). Chromatically Reduced Image (right). Bottom: Modulus of the source field computed on band 10 (left) and band 17 (890-920 nm) (right). The greater is the modulus, the brighter is the point according to a logarithmic scale. A clear vertical signature can be seen in the source field in both band 10 and 17.