domain: spi.gproc spi phys

text:
J.-Y Thibault

Derrien

Jörg Krüger

Tatiana E Itina

Sandra Höhm

Arkadi Rosenfeld

Jörn Bonse

Rippled area formed by surface plasmon polaritons upon femtosecond laser double-pulse irradiation of silicon

The formation of near-wavelength laser-induced periodic surface structures (LIPSS) on silicon upon irradiation with sequences of Ti:sapphire femtosecond laser pulse pairs (pulse duration 150 fs, central wavelength 800 nm) is studied theoretically. For this purpose, the nonlinear generation of conduction band electrons in silicon and their relaxation is numerically calculated using a two-temperature model approach including intrapulse changes of optical properties, transport, diffusion and recombination effects. Following the idea that surface plasmon polaritons (SPP) can be excited when the material turns from semiconducting to metallic state, the "SPP active area" is calculated as function of fluence and double-pulse delay up to several picoseconds and compared to the experimentally observed rippled surface areas. Evidence is presented that multi-photon absorption explains the large increase of the rippled area for temporally overlapping pulses. For longer double-pulse delays, relevant relaxation processes are identified. The results demonstrate that femtosecond LIPSS on silicon are caused by the excitation of SPP and can be controlled by temporal pulse shaping. ©2013 Optical Society of America

Introduction

The irradiation of solids with multiple linear polarized femtosecond laser pulses at fluences close to the damage threshold leads to the formation of laser-induced periodic surface structures (LIPSS) on the surface of almost all materials [START_REF] Borowiec | Subwavelength ripple formation on the surfaces of compound semiconductors irradiated with femtosecond laser pulses[END_REF][START_REF] Wagner | Sub-wavelength ripple formation on various materials induced by tightly focused femtosecond laser radiation[END_REF][START_REF] Huang | Origin of laser-induced near-subwavelength ripples: Interference between surface plasmons and incident laser[END_REF][START_REF] Chakravarty | Nano-ripple formation on different band-gap semiconductor surfaces using femtosecond pulses[END_REF][START_REF] Bonse | Femtosecond laser-induced periodic surface structures[END_REF]. Two distinct types of LIPSS are observed upon femtosecond laser pulse irradiation. For strong absorbing materials such as metals or semiconductors, in most cases low-spatial-frequency LIPSS (LSFL) are observed with a period Λ LSFL close to the irradiation wavelength λ [START_REF] Borowiec | Subwavelength ripple formation on the surfaces of compound semiconductors irradiated with femtosecond laser pulses[END_REF][START_REF] Huang | Origin of laser-induced near-subwavelength ripples: Interference between surface plasmons and incident laser[END_REF][START_REF] Bonse | Femtosecond laser-induced periodic surface structures[END_REF]. These LSFL are generated by interference of the incident laser beam with a surface electromagnetic wave (SEW) generated at a rough surface [START_REF] Sipe | Laser-induced periodic surface structure. I. Theory[END_REF][START_REF] Bonch-Bruevich | Surface electromagnetic waves in optics[END_REF]. In contrast, on dielectrics, often high-spatial-frequency LIPSS (HSFL) with spatial periods significantly smaller than the irradiation wavelength (Λ HSFL < λ /2) have been observed [START_REF] Wagner | Sub-wavelength ripple formation on various materials induced by tightly focused femtosecond laser radiation[END_REF][START_REF] Reif | Ripples revisited -non-classical morphology at the bottom of femtosecond laser ablation craters in transparent dielectrics[END_REF]. The origin of the HSFL is controversially discussed in the literature [START_REF] Borowiec | Subwavelength ripple formation on the surfaces of compound semiconductors irradiated with femtosecond laser pulses[END_REF][START_REF] Reif | Ripples revisited -non-classical morphology at the bottom of femtosecond laser ablation craters in transparent dielectrics[END_REF][START_REF] Dufft | Femtosecond laser-induced periodic surface structures revisited -a comparative study on ZnO[END_REF].

On silicon, predominantly LSFL were observed after low repetition rate (≤ 1 kHz) Ti:Sapphire femtosecond laser pulse irradiations in air environment [START_REF] Wagner | Sub-wavelength ripple formation on various materials induced by tightly focused femtosecond laser radiation[END_REF][START_REF] Bonse | Femtosecond laser ablation of silicon-modification thresholds and morphology[END_REF][START_REF] Costache | Sub-damage-threshold femtosecond laser ablation from crystalline Si: surface nanostructures and phase transformation[END_REF][START_REF] Guillermin | Single and multi-pulse formation of surface structures under static femtosecond irradiation[END_REF][START_REF] Bonse | On the role of surface plasmon polaritons in the formation of laserinduced periodic surface structures upon irradiation of silicon by femtosecond-laser pulses[END_REF][START_REF] Bonse | Pulse number dependence of laser-induced periodic surface structures for femtosecond laser irradiation of silicon[END_REF]. Their orientation is perpendicular to the laser beam polarization and the periods typically range between ∼ 0.6λ and λ , depending on the degree of material excitation [START_REF] Bonse | On the role of surface plasmon polaritons in the formation of laserinduced periodic surface structures upon irradiation of silicon by femtosecond-laser pulses[END_REF][START_REF] -Y. Derrien | Possible surface plasmon polariton excitation under femtosecond laser irradiation of silicon[END_REF], and the number of laser pulses per spot [START_REF] Bonse | Pulse number dependence of laser-induced periodic surface structures for femtosecond laser irradiation of silicon[END_REF]. Several authors have suggested that these structures are caused by excitation of surface plasmon polaritons (SPP) at the air -silicon interface when the material turns from a semiconducting into a metallic state [START_REF] Huang | Origin of laser-induced near-subwavelength ripples: Interference between surface plasmons and incident laser[END_REF][START_REF] Bonse | On the role of surface plasmon polaritons in the formation of laserinduced periodic surface structures upon irradiation of silicon by femtosecond-laser pulses[END_REF][START_REF] Martsinovskii | Ultrashort excitations of surface polaritons and waveguide modes in semiconductors[END_REF]. The interference between the electromagnetic field of the SPP and the incident laser pulse leads to a spatially modulated deposition of optical energy to the electronic system of the material. After coupling to the lattice system [START_REF] -Y. Derrien | Application of a two-temperature model for the investigation of the periodic structure formation on Si surface in femtosecond laser interactions[END_REF] and subsequent ablation processes, this results in a periodically corrugated surface topography [START_REF] Tsibidis | Dynamics of ripple formation on silicon surfaces by ultrashort laser pulses in subablation conditions[END_REF]. The corresponding LSFL modulation depths are typically of the order of the optical penetration depth in the laser-excited material (∼ 100 nm) [START_REF] Derrien | Nanostructuration de cellules photovoltaiques par impulsion laser femtoseconde. etude des mécanismes de formation[END_REF][START_REF] Crawford | Crystalline orientation effects on conical structure formation in femtosecond laser irradiation of silicon and germanium[END_REF], which is consistent with the plasmonic scenario acting at the air-silicon interface.

Two different experimental approaches were reported to study the dynamics of the LSFL formation upon irradiation of silicon by ultrashort laser pulses. Recently, in a femtosecond XUV scattering (pump-probe) experiment after single pulse irradiation of a thin silicon film, evidence for intrapulse energy deposition at specific spatial frequencies (associated with LSFL) was presented [START_REF] Sokolowski-Tinten | Short-pulse laser induced transient structure formation and ablation studied with time-resolved coherent xuvscattering[END_REF]. In a second approach [START_REF] Höhm | Area dependence of femtosecond laser-induced periodic surface structures for varying band gap materials after double pulse excitation[END_REF][START_REF] Höhm | Dynamics of the formation of laser-induced periodic surface structures on dielectrics and semiconductors upon femtosecond laser pulse irradiation sequences[END_REF], multiple equal energy double-fs-pulse sequences of variable delay were used to elucidate the importance of interand intra-pulse feedback phenomena [START_REF] Sipe | Laser induced periodic surface structure: an experimental and theoretical review[END_REF]. For silicon, the LSFL spatial period does not significantly depend on the double-pulse delay ∆t [START_REF] Höhm | Dynamics of the formation of laser-induced periodic surface structures on dielectrics and semiconductors upon femtosecond laser pulse irradiation sequences[END_REF], while the LSFL rippled area strongly decreased with increasing delays up to several picoseconds [START_REF] Höhm | Area dependence of femtosecond laser-induced periodic surface structures for varying band gap materials after double pulse excitation[END_REF]. In the latter work, two characteristic exponential decay times of ∼ 0.15 ps and ∼ 11 ps were found.

In this work, we extend a recently developed model [START_REF] -Y. Derrien | Possible surface plasmon polariton excitation under femtosecond laser irradiation of silicon[END_REF][START_REF] Bulgakova | A general continuum approach to describe fast electronic transport in pulsed laser irradiated materials -the problem of coulomb explosion[END_REF] into a double-pulse excitation scheme in order to calculate the carrier dynamics and to investigate the involvement of SPP excitation in LSFL formation on crystalline silicon. The method allows to quantify the SPP active area for different delays which is compared with experimental results. The importance of carrier generation and relaxation processes in the conduction band is demonstrated.

Theoretical model

Upon high-intensity laser irradiation of crystalline silicon with femtosecond laser pulses, electrons can be promoted from the valence band (VB) to the conduction band (CB) via linear and nonlinear optical absorption effects. Once a sufficiently large amount of electrons is promoted, the optical properties (e.g. the complex dielectric permittivity ε * Si ) are affected. In presence of such a dense electron-hole plasma at CB electron densities N e 4 × 10 21 cm -3 , the silicon transiently turns from a semiconducting to a metal-like high-reflective state [START_REF] Bonse | On the role of surface plasmon polaritons in the formation of laserinduced periodic surface structures upon irradiation of silicon by femtosecond-laser pulses[END_REF][START_REF] Shank | Time-resolved reflectivity measurements of femtosecond-optical-pulseinduced phase transitions in silicon[END_REF][START_REF] Sokolowski-Tinten | Generation of dense electron-hole plasmas in silicon[END_REF].

Surface plasmon polaritons can be excited at the air / excited silicon interface when the real part of the dielectric permittivity falls below minus one [START_REF] Raether | Surface Plasmons on Smooth and Rough Surfaces and on Gratings[END_REF], as expressed by :

ℜe [ε * Si ] < -1 (1)
This occurs when a threshold carrier density N SPP th is exceeded. As usually Gaussian beam profiles are used, the spatial distribution of laser-induced electrons in the CB along with the threshold defines an "SPP active area" (A SPP ) in which surface plasmon polaritons can be excited. This idea is illustrated in Fig. 1, where the hatched circular zone represents A SPP . Using numerical methods, the temporal evolution of the A SPP can be evaluated for different double-pulse delays.

Description of optical properties

The dielectric permittivity of laser-excited silicon ε * Si with carrier densities N e up to 10 22 cm -3 can be described using a Drude model given by [START_REF] Sokolowski-Tinten | Generation of dense electron-hole plasmas in silicon[END_REF]

ε * Si (N e ) = ε Si - ω 2 p (N e ) ω 2 1 + i ν ω , (2)
where ε Si = 13.64 + 0.048i is the dielectric constant of the non-excited silicon at λ = 800 nm wavelength [START_REF] Palik | Handbook of Optical Constants of Solids[END_REF], ω p is the plasma frequency defined as ω p = N e e 2 /(m * e ε 0 ) [e: electron charge, m * e = 0.18×m e : effective optical mass, m e : free electron mass, ε 0 : dielectric permittivity of the vacuum], ν -1 = 1.1 fs is the carrier collision time in laser-excited silicon [START_REF] Sokolowski-Tinten | Generation of dense electron-hole plasmas in silicon[END_REF], and ω is the laser angular frequency. Band filling and band gap renormalization effects are neglected here. In order to consider intrapulse changes of the surface reflectivity of silicon, a multilayer model was used for normal incident radiation. The laser-excited region is considered as a layered structure where each layer j has its own optical properties (related to the local free-carrier density), as defined in Eq. ( 2). The fraction of the laser wave amplitude reflected at the interface between layers j and k is calculated by the recurrence formula [START_REF] Bäuerle | Laser Processing and Chemistry[END_REF][START_REF] Bulgakova | Laser-induced modification of transparent crystals and glasses[END_REF] r j,k = r j, j+1 + r j+1,k e 2iφ j+1 1 + r j, j+1 r j+1,k e 2iφ j+1 ,

where r j, j+1 is given by Fresnel equations [START_REF] Jackson | Classical Electrodynamics[END_REF].

φ j+1 = 2πh j+1 λ × √ ε j+1
is the phase shift induced by the j + 1 layer of thickness h j+1 . The final value of the surface reflectivity R is determined by R = |r 0,N | 2 where 0 corresponds to air and N is a layer located at a depth significantly larger than the optical penetration depth.

Free-carrier dynamics

The electron density in the conduction band N e was calculated considering one-and two-photon absorption, carrier diffusion and Auger recombination by solving the following partial differential equation [START_REF] -Y. Derrien | Possible surface plasmon polariton excitation under femtosecond laser irradiation of silicon[END_REF] ∂

N e ∂t = ∇ (k B T e µ e ∇N e ) + G e -R e . (4)
G e = σ 1 I hω + σ 2 I 2 2hω describes the electron generation rate using the one-photon (σ 1 ) and two-photon (σ 2 ) absorption coefficients listed in Table 1. I ≡ I(t, z) is the temporal intensity profile within the sample upon laser excitation. R e = N e τ AR +(C AR N 2 e )

-1 describes the loss rate of CB electrons by Auger recombination [START_REF] Bulgakova | A general continuum approach to describe fast electronic transport in pulsed laser irradiated materials -the problem of coulomb explosion[END_REF], where τ AR = 6 ps is the minimal recombination time due to plasma screening [START_REF] Sjodin | Ultrafast carrier dynamics in silicon: A two-color transient reflection grating study on a (111) surface[END_REF][START_REF] Yoffa | Dynamics of dense laser-induced plasmas[END_REF] and C AR = 3.8 × 10 -43 m 6 /s is the Auger recombination coefficient [START_REF] Driel | Kinetics of high-density plasmas generated in Si by 1.06-and 0.53-µm picosecond laser pulses[END_REF]. The first term on the right-hand side of Eq. ( 4) describes the carrier transport due to diffusion where µ e = e/(m * e ν) is the carrier mobility in the CB, and k B is the Boltzmann constant. Avalanche ionization has been neglected here. The intensity in the sample is calculated by numerically solving the equation

dI dz = -(σ 1 I + σ 2 I 2 ). (5)
The intensity at the sample surface is

I(t, z = 0) = [1 -R] I 0 (t)
, where R is the surface reflectivity at λ = 800 nm described in the previous Section 2.1 and the incident laser intensity I 0 is given by the temporal double-fs-pulse profile via

I 0 (t) = F 0 τ 4 ln 2 π e -1 2 t-t 1 στ 2 + e -1 2 t-t 2 στ 2 . (6)
In this superposition of two individual temporally Gaussian pulses of duration τ (full width at half maximum, FWHM), F 0 denotes the peak fluence of each individual pulse of the doublepulse sequence. t 1,2 denotes the time when the two individual pulse maxima are reached. Then ∆t = t 2 -t 1 defines the double-pulse delay. Note that the first pulse is centered at t 1 = 0 fs. Here, σ τ is given by τ/(2 √ 2 ln 2). For the numerical calculations, a pulse duration τ = 150 fs was selected to match the experimental conditions given in Ref. [START_REF] Höhm | Area dependence of femtosecond laser-induced periodic surface structures for varying band gap materials after double pulse excitation[END_REF].

Energy relaxation

The free-carrier dynamics is additionally affected by carrier diffusion and energy relaxation, which both strongly depend on the temperature. To calculate temperatures of the free-carriers T e and the silicon lattice T Si , a two-temperature model was used. It is assumed here that CB electrons and VB holes both have the same temperature, i.e., T e . A partial differential equation was used to describe the temperature distribution of the free-carriers given by [START_REF] Bulgakova | A general continuum approach to describe fast electronic transport in pulsed laser irradiated materials -the problem of coulomb explosion[END_REF][START_REF] Bäuerle | Laser Processing and Chemistry[END_REF]

C e ∂ T e ∂t = ∇ (κ e ∇T e ) -γ (T e -T Si ) + Q e , (7)
where κ e = 2k B µ e N e T e /e is the free-carrier thermal conductivity. The specific heat capacity of the free-carriers is given by C e = 3 2 k B N e . The energy coupling rate between free-carriers and lattice is γ = C e τ γ , with

τ γ = τ 0 γ 1 + N e N th

2

, N th = 6.02 × 10 20 cm -3 and τ 0 γ = 240 fs [START_REF] Bulgakova | A general continuum approach to describe fast electronic transport in pulsed laser irradiated materials -the problem of coulomb explosion[END_REF][START_REF] Sjodin | Ultrafast carrier dynamics in silicon: A two-color transient reflection grating study on a (111) surface[END_REF]. According to recent experiments, τ γ has been limited to 2 ps at high carrier densities [START_REF] Harb | Carrier relaxation and lattice heating dynamics in silicon revealed by femtosecond electron diffraction[END_REF].

The laser source term

Q e = (hω -E g ) σ 1 I hω + (2hω -E g ) σ 2 I 2 2hω + E g R e -3 2 k B T e ∂ N e
∂t taken from [START_REF] Bulgakova | A general continuum approach to describe fast electronic transport in pulsed laser irradiated materials -the problem of coulomb explosion[END_REF] considers the one-and two-photon absorption of the laser beam, the release of energy (E g R e ) due to Auger recombination (band gap energy E g = 1.12 eV), and the last term accounts for the N e -dependent change of the electronic heat capacity. Free-carrier heating has been neglected.

The lattice temperature T Si is calculated by solving the partial differential equation [START_REF] Bäuerle | Laser Processing and Chemistry[END_REF]:

C Si ∂ T Si ∂t = ∇ (κ Si ∇T Si ) + γ (T e -T Si ) . (8)
The second term on the right hand side of Eqs. ( 7) and ( 8) considers energy transfer between the free-carriers and the lattice via electron-phonon coupling. The heat capacity of silicon C Si and thermal conductivity κ Si both depend on the liquid density fraction η in the laser-excited volume and were calculated here via

C Si (T Si ) = (1 -η)C (s) Si (T Si ) + ηC (l) Si (T Si ) and κ Si (T Si ) = (1 -η) κ (s) Si (T Si ) + ηκ (l)
Si (T Si ). For non-molten (solid) silicon, the heat capacity

C (s)
Si and the thermal conductivity κ

(s) Si are given by C (s) Si [J/(m 3 •K)]= 1.978 × 10 6 + 3.54 × 10 2 T Si -3.68 × 10 6 T -2
Si and κ

(s) Si [W/(m•K)]= 1.585 × 10 5 T -1.23

Si

, respectively [START_REF] Driel | Kinetics of high-density plasmas generated in Si by 1.06-and 0.53-µm picosecond laser pulses[END_REF]. For the liquid state, the corresponding parameters are

C (l)
Si (T Si ) = 2.633 × 10 6 J/(m 3 •K) [START_REF] Desai | Thermodynamic properties of iron and silicon[END_REF] and [START_REF] Magna | A phase-field approach to the simulation of the excimer laser annealing process in Si[END_REF]. The melting temperature T m of silicon is 1687 K at ambient pressure [START_REF] Rhim | Thermophysical properties measurement of molten silicon by high-temperature electrostatic levitator: density, volume expansion, specific heat capacity, emissivity, surface tension and viscosity[END_REF]. Melting is considered in the model of laser heating here by keeping the local temperature constant at T m until the internal energy increase reaches the melting enthalpy ∆H m = 4.2 × 10 9 J/m 3 [START_REF] Korfiatis | Conditions for femtosecond laser melting of silicon[END_REF].

κ (l) Si (T Si )[W/(m•K)]= 50.2 + 29.3 × 10 -3 (T Si -T m )
The boundary conditions for free-carrier transport and thermal energy diffusion were implemented so that free-carriers and energy do not leave the sample of 400 µm thickness. The initial temperature of the system was set to 300 K. The numerical code for solving the partial differential Eqs. ( 4), [START_REF] Bonch-Bruevich | Surface electromagnetic waves in optics[END_REF], and ( 8) was developed by using the method of finite volumes [START_REF] Versteeg | An Introduction to Computational Fluid Dynamics -The Finite Volume Method[END_REF]. The calculations were performed in a one-dimensional approach in the direction normal to the sample surface. The time integration was performed using an implicit scheme. Equation [START_REF] Bonse | Femtosecond laser-induced periodic surface structures[END_REF] has been solved using a Runge-Kutta 4th-order algorithm [START_REF] Press | Numerical Recipes: The Art of Scientific Computing[END_REF]. The numerical time-step δt has been decreased until convergence of the solutions was reached (δt = 10 -16 s). A non-uniform mesh size was used with smaller cells close to the surface. For simplified cases, the validity of the numerical code has been verified with analytical solutions and energy balance monitoring.

Quantification of the SPP active area

The numerical calculations were performed for different laser fluences F 0 up to 0.7 J/cm 2 . For each fluence, the delay ∆t between the two τ = 150 fs pulses was systematically varied between 0 and 3.5 ps.

For quantification of the SPP active area, the following four steps were conducted.

1. For each laser fluence F 0 , and double-pulse-delay ∆t, the free-carrier density N e was calculated as a function of time (up to t = 5 ps). Since the proposed mechanism of LSFL formation involves the excitation of SPP and their interference with the incident laser beam [START_REF] Bonse | On the role of surface plasmon polaritons in the formation of laserinduced periodic surface structures upon irradiation of silicon by femtosecond-laser pulses[END_REF], the carrier density N t max e (F 0 , ∆t) was identified just at the end of the second femtosecond laser pulse, i.e., at the time t max when its intensity dropped to a fraction

ζ of its maximum value [I 0 (t max ) = ζ × max {I 0 (t)} = ζ × F 0 /τ × 4 ln 2/π].
As the interference between the laser and the SPP electromagnetic field should be remarkable, the value of ζ is expected to be close to unity. was used, the relation between radial coordinate r and the local fluence F is given by

As a

r (F) = w 0 1 2 ln F 0 F (9)
3. In the next step, for each fluence F, the radial coordinate r(F) was calculated according to Eq. ( 9), and associated with the corresponding value N t max e (F, ∆t). In this way, a curve N t max e (r(F), ∆t) was constructed.

N SPP th = m * e ε 0 (ℜe [ε Si ] + 1) e 2 ω 2 + ν 2 (11)
Using the parameters introduced in Section 2.1, N SPP th = 5.27 × 10 21 cm -3 is found. With that value, the solution of Eq. ( 10) provides the SPP excited radius r SPP (∆t) as a function of the double-pulse delay ∆t. Finally, assuming a circular shape of the SPP active area,

A SPP is calculated via A SPP (∆t) = πr 2 SPP (∆t) . (12)

Results and discussion

In this section, the results of the numerical calculations based on the model given in the previous Section 2 are presented. The free-carrier density N e is calculated as a function of time t, laser fluence F 0 , and double-pulse delay ∆t. First, the effect of a double-pulse irradiation on the freecarrier density at the surface is analyzed, before the SPP active area is quantitatively evaluated as function of the double-pulse delay and compared to experimental data of the LSFL rippled area.

Figure 2 exemplifies the results of the numerical calculations of the free-carrier density N e at the silicon surface upon irradiation with double-pulses of ∆t = 0.5 ps delay and with three different fluences F 0 = 0.2, 0.3, and 0.5 J/cm 2 . The upper graph visualizes the temporal evolution of N e (left ordinate) on short timescales up to 1 ps, while the lower graph displays the carrier dynamics at longer timescales up to 5 ps. In both graphs the temporal intensity profile of the double-fs-pulse sequence is added for comparison (right ordinate). As seen in Fig. 2(a), the maximum carrier density is reached during the second laser pulse and increases with F 0 . For the lowest fluence of F 0 = 0.2 J/cm 2 , the threshold density N SPP th is not reached, while for F 0 = 0.3 J/cm 2 it is exceeded during the second pulse. For F 0 = 0.5 J/cm 2 , it is passed already during the first laser pulse. Moreover, the decrease rate (∂ N e /∂t) of the carrier density between the two individual femtosecond laser pulses is faster at higher fluences F 0 . This is attributed to Auger recombination and thermal carrier diffusion which are more efficient at larger carrier densities (recombination) and larger electron temperatures (diffusion). The two mechanisms also account for the carrier density decrease after the second laser pulse, as seen at large times in Fig. 2(b). For all selected fluences and at the given delay, the second pulse increases the carrier density N e above the level generated by the first one.

Similar calculations have been performed by systematically varying the laser fluence F 0 (0.15 J/cm 2 -0.70 J/cm 2 ) and the double-pulse delay ∆t (0 ps -3.5 ps). in a false-colour map. The solid black isoline indicates where the carrier density equals the SPP threshold density N SPP th . Above F 0 = 0.17 J/cm 2 , this threshold can be exceeded. Figure 4 represents a vertical cross section at F 0 = 0.25 J/cm 2 through the data previously shown in Fig. 3. Two regimes can be distinguished in the evolution of the maximum carrier density with the delay, i.e., a fast decrease within less than 0.15 ps and a slow decrease with a time constant of approximately 8 ps (see the red solid curve). A variation of the model parameters reveals that the fast decay is caused by the nonlinear (two-photon) absorption in the silicon. As the two-photon absorption scales quadratically with the laser beam intensity (see Eq. ( 5)), it increases the number of laser-generated carriers especially for small delays when the two 150-fs laser pulses are temporally overlapping. Moreover, individually disabling the physical processes confirms that the slow area decrease originates from both the thermal diffusion of carriers and from Auger recombination. The two additional (dashed green and dotted blue) curves represent the values of N that ζ in the temporal interference criterion (see step 1 in Section 2.4) is important here and should be systematically varied in the comparison of the SPP active area A SPP and the LSFL rippled area A LSFL . Following the complete procedure (steps 1 -4) described in Section 2.4, the SPP active area has been calculated for the different values of ζ = 50%, 90% and 99%. Figure 5(a) visualizes the calculated results of A SPP as a function of the double-pulse delay ∆t (red curves) along with the experimental data reported in Ref. [START_REF] Höhm | Area dependence of femtosecond laser-induced periodic surface structures for varying band gap materials after double pulse excitation[END_REF] for the LSFL rippled area after irradiation of silicon by a sequence of 15 double-pulses, each at a total peak fluence of F 0,tot = 2 × F 0 = 0.3 J/cm 2 (blue data points). quantitative agreement between A SPP and A LSFL is obtained for ζ = 99%. It must be noted here that the optimum agreement with the experimental data was obtained for F 0 = 0.40 J/cm 2 which is more than two times larger than the single-pulse fluence F 0 = 0.15 J/cm 2 used experimentally.

In order to explain this discrepancy between the experimental and theoretical fluence values, some additional aspects must be considered. The numerical calculations performed here assume the interaction of a single double-fs-pulse with a geometrically flat surface of single-crystalline silicon. However, in the experiments, multiple double-pulse sequences were required to form the LSFL at the surface resulting in a periodically corrugated surface. Typically, a few incubating pulses are needed to reach the ablation condition and to generate a rough surface [START_REF] Bonse | Structure formation on the surface of indium phosphide irradiated by femtosecond laser pulses[END_REF]. Additional laser pulses then form the LSFL via scattering and SPP excitation and further reinforce the grating-like surface morphology via inter-pulse feedback [START_REF] Bonse | Pulse number dependence of laser-induced periodic surface structures for femtosecond laser irradiation of silicon[END_REF][START_REF] Sipe | Laser induced periodic surface structure: an experimental and theoretical review[END_REF].

Upon irradiation with multiple laser pulses, the maximum number of laser-induced carriers generated at the surface will be additionally affected by several inter-and intra-pulse effectseven if the laser peak fluence (F 0,tot ) is kept constant during the pulse irradiation sequence:

1. Incubation effects (inter-double-pulse): Due to incubation effects, the damage threshold fluence of the material F th decreases with increasing number of (single) laser pulses [START_REF] Bäuerle | Laser Processing and Chemistry[END_REF].

For Ti:sapphire 130-fs laser pulse irradiation of silicon, this effect was studied already in detail in [START_REF] Bonse | Femtosecond laser ablation of silicon-modification thresholds and morphology[END_REF]. For less than N = 1000 laser pulses, an incubation law of the form F th (N) = F th (1) × N ξ -1 was found, with the single-pulse damage threshold F th (1) = 0.26 J/cm 2 and an incubation coefficient ξ = 0.84 [START_REF] Bonse | Femtosecond laser ablation of silicon-modification thresholds and morphology[END_REF]. As a result, for a fixed fluence F 0 , the ratio F 0 /F th increases, resulting in a larger number of laser-generated carriers at the silicon surface. Hence, for N = 15 laser pulses as used in [START_REF] Höhm | Area dependence of femtosecond laser-induced periodic surface structures for varying band gap materials after double pulse excitation[END_REF], the threshold ratio F th (1)/F th (15) is ∼ 1.5. Considering this effect along with the somewhat different pulse duration (τ = 150 fs), the numerical calculations indicate that the experimental value of F 0 = 0.15 J/cm 2 used in [START_REF] Höhm | Area dependence of femtosecond laser-induced periodic surface structures for varying band gap materials after double pulse excitation[END_REF] for the multiple pulse irradiation is equivalent to the irradiation by an increased effective single-pulse fluence of 0.27 J/cm 2 .

2. Geometrical surface modifications (inter-double-pulse): Once the initially flat silicon surface becomes corrugated due to ablation after a certain number of double-pulse sequences, the next laser pulse will significantly change its interaction (absorption) due to geometrical effects. As in the vicinity of sharp features of the surface topography a significant enhancement of the electromagnetic field (by factors up to 10) can occur [START_REF] Derrien | Nanostructuration de cellules photovoltaiques par impulsion laser femtoseconde. etude des mécanismes de formation[END_REF][START_REF] Bogdanowicz | Light absorption in conical silicon particles[END_REF][START_REF] Huang | The significant role of plasmonic effects in femtosecond laser-induced grating fabrication on the nanoscale[END_REF], the spatial carrier density distribution may become inhomogeneous and increases locally at a rough or rippled surface. Along with the increased optical absorption, also the sample reflectivity decreases due to the geometrical corrugation from initially R f lat = 0.33 for a flat silicon surface at normal incidence (λ = 800 nm) down to values below R corr < 0.1 [START_REF] Vorobyev | Antireflection effect of femtosecond laser-induced periodic surface structures on silicon[END_REF]. However, even for a perfectly absorbing surface (R corr = 0) the latter effect can increase the absorbed laser pulse energy by up to 50 %

[(1-R corr )/(1- R f lat )=(1-0)/(1-0.33)=1.5].
3. Structural surface modifications (inter-double-pulse): Upon laser pulse irradiation in the ablative regime, also a residual melt layer is left at the surface which resolidifies after each double-pulse impact. For (single-pulse) fluences below 0.58 J/cm 2 , a superficial amorphous layer of some tens of nanometer thickness is formed at the surface which exhibits a surface reflectivity increased by up to a few percent and which has a 25-times increased linear absorption coefficient compared to crystalline silicon [START_REF] Bonse | All-optical characterization of single femtosecond laser-pulse-induced amorphization in silicon[END_REF]. This interpulse effect additionally may increase the number of laser-induced carriers, as due to the amorphization, the optical absorption occurs in a reduced energy deposition depth. Moreover, laser-generated structural effects in the silicon lattice can lead to trapping of carriers by defect states on the picosecond timescale [START_REF] Esser | Femtosecond transient reflectivity measurements as a probe for process-induced defects in silicon[END_REF].

Phase transitions (intra-double-pulse):

If the delay between the first and the second pulse of the double-pulse sequence is large enough, thermal phase transitions will occur if the fluence of the first pulse is sufficiently high. Thermal melting of semiconductors was shown to occur on the timescale of a few picoseconds [START_REF] Sundaram | Inducing and probing non-thermal transitions in semiconductors using femtosecond laser pulses[END_REF] while ablation starts typically after tens to hundreds of picoseconds [START_REF] Der Linde | The physical mechanisms of short-pulse laser ablation[END_REF]. This effect can contribute to deviations between the experimentally observed LSFL area and the calculated SPP active area. Above a certain number of double-pulse sequences, the silicon melts already after the first pulse. The optical surface properties then turn within a few picoseconds to that of metal with a few nanometer optical penetration depth only acting during the second laser pulse. As the energy deposition depth is simultaneously decreased, the energy of the second pulse is deposited in a layer excited by the first pulse already, which later undergoes almost complete ablation and is, therefore, not contributing to the LSFL topography. In this way, the effect may shield the pulse energy of the second pulse when melting occurs between the two fs-laser pulses.

The theoretical description of these intra-and inter-pulse effects in multiple irradiation sequences is beyond the scope of this work. However, the discussed effects justify that the fluence F 0 was varied systematically in the numerical calculations to obtain the best match between the SPP active area and the LSFL rippled area.

Conclusions

The laser-induced carrier dynamics in the conduction band of silicon upon irradiation with femtosecond double-pulse sequences of varying delays up to ∼ 4 ps was numerically calculated using the two-temperature model, considering carrier generation via one-and two-photon absorption, carrier diffusion and Auger recombination effects as well as their impact on the transient optical properties. At sufficiently high laser fluences, the semiconducting material transiently turns to a metallic state allowing the excitation of surface plasmon polaritons. Additionally taking into consideration a spatially Gaussian beam profile along with an interference criterion between the laser and the plasmon electromagnetic fields, the SPP active area was quantified as a function of the double-pulse delay and compared to experimental data of the LSFL rippled area observed in recent experiments. Both the SPP active area and the LSFL area show two characteristic decay-times -one of τ 1 ∼ 0.147 ps and another one of τ 2 ∼ 13.0 ps. Quantitative agreement between both the experiments and calculations was obtained when multi-pulse driven inter-and intra-pulse feedback effects are considered. Our results directly support the SPP-based LSFL formation mechanism proposed earlier for silicon and identify the nonlinear (two-photon) absorption to be responsible for the rapid area decrease (τ 1 ) while carrier diffusion and Auger recombination effects account for the slower area decrease (τ 2 ).

The temporally resolved calculations of the carrier dynamics manifest that the intra-pulse energy deposition step is responsible for the spatial characteristics of the rippled surface which is later reinforced through inter-pulse feedback.

r w 0 2 #

 2 Gaussian beam with radius w 0 having a spatial fluence profile of F(r) = F 0 e -2 197904 -$15.00 USD Received 17 Sep 2013; revised 23 Oct 2013; accepted 27 Oct 2013; published 22 Nov 2013 (C) 2013 OSA 2 December 2013 | Vol. 21, No. 24 | DOI:10.1364/OE.21.029643 | OPTICS EXPRESS 29649

4 .= - 1 ,

 41 Then, the implicit equation N t max e (r(F), ∆t) = N SPP th[START_REF] Bonse | Femtosecond laser ablation of silicon-modification thresholds and morphology[END_REF] was solved, where N SPP th is the threshold carrier-density necessary for SPP excitation. The value of N SPP th is directly calculated from Eq. (2) using the criterion ℜe ε * Si N SPP th which can be written as[START_REF] Martsinovskii | Ultrashort excitations of surface polaritons and waveguide modes in semiconductors[END_REF]

Figure 3 2 .

 32 visualizes all the results by plotting the maximum of the free-carrier density N max e as a function of both parameters #197904 -$15.00 USD Received 17 Sep 2013; revised 23 Oct 2013; accepted 27 Oct 2013; published 22 Nov 2013 (C) 2013 OSA 2 December 2013 | Vol. 21, No. 24 | DOI:10.1364/OE.21.029643 | OPTICS EXPRESS 29650 Evolution of the free-carrier density (left ordinates) at the surface of silicon irradiated by a femtosecond double-pulse with a delay of ∆t = 0.5 ps and single pulse fluence of F 0 = 0.2, 0.3 and 0.5 J/cm 2 (pulse duration τ = 150 fs, laser wavelength λ = 800 nm). (a) Short timescales up to 1 ps. (b) Long timescales up to 5 ps. For comparison, the temporal double-pulse intensity profile is shown (right ordinates). The horizontal lines indicate the threshold density N SPP th for SPP excitation. The maximum values of the carrier density N max e are marked in (b).

Fig. 3 .

 3 Fig. 3. Maximum free-carrier density as a function of laser fluence F 0 and double-pulse delay ∆t. The black isoline represents the SPP threshold density N SPP th . The three crosses indicate the parameters used in Fig. 2. (Irradiation parameters: τ = 150 fs, λ = 800 nm). The vertical dashed line corresponds to the data displayed in Fig. 4.

Fig. 4 .

 4 Fig. 4. Maximum free-carrier density N max e as a function of the double-pulse delay ∆t (red solid line). The dashed blue and dotted green represent N t max e calculated for ζ = 50% and 99%, respectively. Model parameters: F 0 = 0.25 J/cm 2 , τ = 150 fs, λ = 800 nm. The dotted horizontal line indicates the threshold density N SPP th for SPP excitation.

Figure 5 (

 5 Fig. 5. Calculated SPP active area A SPP as a function of the double-pulse delay ∆t for three different values of ζ = 50%, 90% and 99%) (a). The blue data points of the LSFL rippled area A SPP are taken from [22] for comparison. Model parameters: F 0 = 0.40 J/cm 2 , τ = 150 fs, λ = 800 nm, w 0 = 16.5 µm. In (b), representative scanning electron micrographs for delays up to 2 ps are shown. The LSFL rippled area is marked at ∆t = 0.7 ps.

#

  197904 -$15.00 USD Received 17 Sep 2013; revised 23 Oct 2013; accepted 27 Oct 2013; published 22 Nov 2013 (C) 2013 OSA 2 December 2013 | Vol. 21, No. 24 | DOI:10.1364/OE.21.029643 | OPTICS EXPRESS 29654

Table 1 .

 1 Material parameters used in numerical simulations of femtosecond laser-irradiated silicon (wavelength λ = 800 nm, pulse duration τ = 150 fs).

	Coefficient	Symbol	Value	Unit	Reference
	Band gap energy	E g	1.12	eV	[30]
	Dielectric constant of crystalline silicon	ε Si	13.64 + 0.048i	-	[29]
	One-photon absorption coefficient	σ 1	1.021 × 10 5	m -1	[29]
	Two-photon absorption coefficient	σ 2	6.8 × 10 -11	m/W	[36]
	Carrier collision time	ν -1	1.1 × 10 -15	s	[27]
	Effective optical mass	m * e	1.64 × 10 -31	kg	[27]
	Auger recombination rate	C AR	3.8 × 10 -43	m 6 /s	[35]
	Minimum Auger recombination time	τ AR	6.0 × 10 -12	s	[34]
	Minimum electron-phonon coupling time	τ 0 γ	240 × 10 -15	s	[33]
	Threshold density for electron-phonon coupling	N th	6.02 × 10 26	m -3	[33]

Acknowledgments

T.J.-Y.D. acknowledges a postdoctoral fellowship awarded by the Adolf-Martens-Fond e.V. The authors would like to thank M. Tischer (MBI) for taking the SEM images. This work was supported by the German Science Foundation (DFG) under Grant Nos. RO 2074/7-2 and KR 3638/1-2.


Valentin Leveau
email: valentin.leveau@ina.fr

Alexis Joly
email: alexis.joly@inria.fr

Olivier Buisson
email: olivier.buisson@ina.fr

Pierre Letessier

Patrick Valduriez

Recognizing Thousands of Legal Entities through Instance-based Visual Classification

This paper considers the problem of recognizing legal entities in visual contents in a similar way to named-entity recognizers for text documents. Whereas previous works were restricted to the recognition of a few tens of logotypes, we generalize the problem to the recognition of thousands of legal persons, each being modeled by a rich corporate identity automatically built from web images. We introduce a new geometrically-consistent instance-based classification method that is shown to outperform state-of-the-art techniques on several challenging datasets while being much more scalable. Further experiments performed on an automatic web crawl of 5,824 legal entities demonstrates the scalability of the approach.

INTRODUCTION

Legal entities (such as firms, government bodies, political parties, societies, associations, etc.) are entities other than natural persons (human being) created by law and recognized as having duties and rights. It does not exist any estimation of the number of such legal entities but they are omnipresent in our all day life as well as in all media contents. Beyond their legal identity, most of them also have a corporate visual identity, that is a set of graphical rules and elements providing an organisation with visibility and recognizability (graphic charter, logotype, insignia, colors, polices, fonts, etc.). As for natural persons, it is therefore possible to recognize them automatically in visual contents in order to provide automatic annotations. This is of high interest for many applications involving huge amounts of weakly annotated image or video contents (YouTube, social media, TV archives, etc.). Whereas legal entity recognition is considered as an important challenge in the text community (e.g. the freebase repository contains 741K organisations, 160K educational institutions or 31K sport teams), the problem has received little attention in the multimedia community. Existing works and techniques (see section 2) are limited to the recognition of few tens of classes (37 logos in BelgaLogos dataset 1 , 32 logos in FlickrLogos dataset [START_REF] Romberg | Scalable logo recognition in real-world images[END_REF]), each targeted entity being modeled by a single logotype. In this paper, we generalize the problem to the recognition of thousands of legal persons, each being modeled by a rich visual identity automatically built from web images. The proposed method relies on a geometrically-consistent instance classification technique that is described in section 3 and evaluated in section 4.

RELATED WORKS

As the number of legal entities to be recognized is very large, the problem is primarily related to large-scale image classification. Existing methods and techniques for this problem are typically based on local descriptors pooling techniques (BoW [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF], Fisher vectors [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF], SPM [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]) and the use of efficient classifiers in the high-dimensional embedded space such as linear support vector machines [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]. An alternative is deep convolutional neural networks that have been recently proved to achieve similar results on large-scale image datasets such as ImageNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. The problem we are targeting is however slightly different. Because the visual identity of a legal entity is actually aimed at guarantying its recognizability, it relies on visual objects with small intraclass variations (such as logos, landmarks, insignias, etc.) but in highly cluttered contexts (very small objects & weak image-level annotations). This problem has been referred as instance classification in a recent paper of Krapac et al. [START_REF] Krapac | Instance classification with prototype selection[END_REF] and is at the crossroad between object recognition and instance-level image retrieval. The method they propose is based on a feature-wise prototype selection approach: local descriptors are all kept in their original form (without quantization) and a distance-adaptive prototype is trained for each of them in a supervised way. They report some consistent performance improvements over several state-of-the-art classification methods (including Fisher Vectors [START_REF] Perronnin | Improving the fisher kernel for large-scale image classification[END_REF]). The other family of techniques related to our work is instancebased image retrieval techniques [START_REF] Arandjelovic | Three things everyone should know to improve object retrieval[END_REF] and in particular the ones focused on logo retrieval [START_REF] Romberg | Scalable logo recognition in real-world images[END_REF][START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF]. These techniques are primarily aimed at retrieving instances of a given query object in an unsupervised way but any of them can be used for classification purposes when the search is performed on a labelled set of pictures (typically by voting on the top-K retrieved images or through any other instance-based classifier). They usually rely on local descriptors quantization methods (such as hamming embedding [START_REF] Andoni | Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[END_REF], data-dependent hashing [START_REF] Joly | Random maximum margin hashing[END_REF] or product quantizer [START_REF] Jegou | Product quantization for nearest neighbor search[END_REF]) and scalable indexing structures (such as inverted lists or hash tables). This allows matching all local descriptors one by one in the full index and favors a more precise matching of small objects in highly cluttered pictures. Using geometry in addition to this raw scheme has been proved to achieve further performance gains, either by the inclusion of weak geometry constraints in the matching phase [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] or by post-checking the geometry consistency of the matches, typically by using a RANSAC algorithm [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF]. The method proposed in this paper improves such techniques in order to construct precise class-specific saliency maps and build a strong image classifier highly robust to noise and clutter.

PROPOSED METHOD

We consider a training set S of |S| pictures weakly annotated with one or several labels among |C| classes (corresponding to one or several legal entities presumably recognizable in the picture). Each picture is described by a set of local descriptors (SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] in our experiments) forming a reference dataset of N local features xi. Our instancebased geometrically-consistent classification scheme can be summarized as follows: local descriptors are extracted from the query image Iq and searched independently in the reference set using an efficient K-NN search scheme. A local geometry consistency checking is then performed at every potential region of interest using a newly introduced sliding RANSAC procedure. The resulting lists of checked patches are then back-propagated in the query image and merged in order to produce pixel-wise saliency maps for each of the retrieved label. A strong classifier is finally derived from the class-specific saliency maps through a max-pooling strategy.

Hash-based K-NN search. The approximate K-Nearest Neighbors (K-NN) of each local feature x Q j belonging to a query image IQ are computed efficiently thanks to the hashbased multi-probe search method introduced in [START_REF] Joly | A posteriori multi-probe locality sensitive hashing[END_REF]. Its principle is to train an adaptive search model at indexing time through kernel density estimates computed on exact K-NN samples. This model is used at search time to select the most probable buckets to be visited so as to retrieve on average a fraction α of the real K-NN's (α was set to 0.80 in all our experiments). The advantage of this method compared to other state-of-the-art methods (such as PQ-code [START_REF] Jegou | Product quantization for nearest neighbor search[END_REF] or Soft-Assignment [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]) is that it allows controlling accurately the quality of the retrieved K-NN while being applicable to any quantization function and metrics. In our case, the original scheme is transposed to the use of a more effective hash function and to the application of the Hamming Embedding principle [START_REF] Andoni | Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[END_REF]. More precisely, we used RMMH [START_REF] Joly | Random maximum margin hashing[END_REF], a recent data-dependent hash function family, in order to embed the original feature vectors in compact binary hash codes of 128 bits (the parameter M of RMMH was fixed to M = 32). The k = log2(N ) first bits of the hash codes are used as keys of a hash map containing the N 128-bits hash codes divided into the 2 k buckets. Still at indexing time, the search model is estimated based on the exact K-NN's in the 128-bits Hamming space rather than in the original space. It has actually be shown in [START_REF] Joly | Random maximum margin hashing[END_REF] that RMMH somehow works as an unsupervised metric learning technique and can provide better matches in the embedded space than in the original one. At search time, the query feature x Q j is also embedded via RMMH and the resulting 128bits hash code h Q j is passed to the probabilistic multi-probe algorithm (see [START_REF] Joly | A posteriori multi-probe locality sensitive hashing[END_REF] for more details). Once the most probable buckets have been selected, the top-K matches are computed as the K nearest hash codes according to the Hamming distance between the query hash code h Q j and the hash codes belonging to the selected buckets.

Sliding RANSAC. Post-checking the geometric consistency of the raw visual matches is an efficient strategy to filter false positives and consolidate good matches. The RANSAC algorithm has notably been successful in rigid objects retrieval [START_REF] Philbin | Scalable Object Retrieval in Very Large Image Collections[END_REF] in particular logos [START_REF] Joly | Logo retrieval with a contrario visual query expansion[END_REF]. Some recent variants such as MAC-RANSAC [START_REF] Rabin | Mac-ransac: a robust algorithm for the recognition of multiple objects[END_REF] provide even better results in the context of multiple localized objects by either constraining the distance of the randomized candidate pairs or by iteratively removing validated matches from the pool of candidates. But even with such improvements, a global RANSAC algorithm applied at the image-level is not adapted to the detection of very small objects in highly cluttered images for which the percentage of inlier pairs of matches can be typically lower than 0.1% of the whole set of possible pairs. Furthermore, as it is computed on the retrieved images one by one, it does not allow consolidating locally the matches from different training images. To address these issues, we introduce a sliding RANSAC strategy aimed at checking the geometric consistency locally for each of the NQ query features of the query image IQ. More precisely, for a given local feature x Q j ∈ IQ, its m spatial nearest neighbors are computed so as to define a candidate region of interest to be geometrically checked in all the retrieved pictures (i.e. in the ones having some visual matches within the m + 1 lists of K-NN's). For a given candidate region of interest and a given retrieved image, the RANSAC algorithm then works in a standard fashion (in our experiments, we used a scale-rotation-translation model and 100 iterations per local run). Note that the support of both the random sampling and the consensus phases is bounded by the set of local features belonging to the current region of interest. This allows improving the recall and the precision of the inliers compared to classical global RANSAC algorithm. The parameter m controls the locality constraint of the geometry consistency analysis. Ideally, it should fit the size of the targeted objects of interest. Too large values of m would lead to the same problem than a global RANSAC. Too small values of m would degrade the dynamic of the number of inliers and possibly miss some consistent matches. In our experiments, m was trained by cross-validation.

Class-specific geometry consistency maps. The output of the sliding RANSAC algorithm is a set of NQ lists of consolidated results (i.e. one list per query feature x Q j ). Each consolidated result R Q j,t is itself defined as a set of individual matches of the form (x Q j ′ , x t ′ ) where the x Q j ′ belong to the m spatial neighbors of x Q j and the x t ′ belong to an image It of the training set. In order to construct saliency maps, we first associate each consolidated result R Q j,t with an individual geometry consistency score f Q j,t and a bounding box B Q j,t in the query image. Rather than simply counting the number of inlier matches, the score f Q j,t is computed as the sum of the inverse rank of the matched features x t ′ (rank in the K-NN's of x Q j ′ ). This allows giving more importance to the most confident visual matches. The bounding box B Q j,t is defined as the minimum bounding rectangle containing all the individually matched features x Q j ′ ∈ R Q j,t . The pixel-wise consistency score g Q c (w, h) of a pixel (w, h) according to class label c is then computed by (i) selecting the consolidated results R Q j,t whose bounding box B Q j,t intercepts (w, h) (ii) grouping them according to the provenance image It and averaging the scores f Q j,t for each group (iii) summing the averaged scores of the groups whose provenance images It are labeled with c. This allows voting on the number of pictures retrieved for label c and weighting each vote by an average geometry consistency in each image. Figure 1 displays two saliency maps g Q c (w, h) computed for two distinct class labels in a single query image.

Multi-label Scoring. As illustrated by Figure 1, the saliency maps produced by the previous step could be easily used for a precise localization of the visual patterns recognized for each of the retrieved legal entity. The scope of the present paper is however only on classification so that we only use the maps to build a strong classifier at the image level. This is done by simply taking the value of the most salient pixel in each map (i.e for each returned label):

s Q (c) = max (w,h) g Q c (w, h) (1)
where s Q (c) is the detection score of the label c. As shown in Figure 1, this last step also acts as a disambiguation procedure where different classes can co-occur in different images and bring geometry consistency in other class-specific saliency maps.

To decide whether a given legal entity is detected or not, a threshold τs is applied on the s Q (c) scores (several annotations can thus be produced for each image). To better model the density distribution over the classes, a normalization is then applied according to:

p Q (c) = s Q (c) P c ′ s Q (c ′ ) ( 2
)
where p Q (c) is the probability estimation of the presence of the label c. Discussion. The main line of this paper is to use online geometry consistency checking to disambiguate instance-based matches rather than training discriminative models offline. This is justified in several ways. First, our training phase is reduced to a simple indexing process with a linear time and space complexity O(N ). The prototype selection technique of [START_REF] Krapac | Instance classification with prototype selection[END_REF] requires computing the 20, 000-NN's of each of the N features of the training set, leading to a much more important training time (over-linear in N). Concerning the memory storage, their method requires at least 8 times more RAM to store the original SIFT features. Besides, the complexity of other state-of-the-art methods making use of pooling and SVM's is typically O(N + |C|.|S| 2 ) so that they are less scalable in both the number of classes and the number of images. Beyond scalability, our method has several other advantages including the easy management of multi-labeled images, the fine grained localisation of the recognized patterns making them highly interpretable and the possibility of dynamically inserting additional training images in an incremental way.

EXPERIMENTS

Evaluation metric and datasets. Classification effectiveness is measured by the Mean Average Precision (mAP), which is commonly defined as the mean of the per-class average precisions. The evaluation is performed on 3 datasets of the literature and one newly introduced dataset dedicated to the large-scale recognition of legal entities: FlickrLogos32 [18] -8,240 images composed of 2,240 images labelled with 32 logo classes and 6000 distractors considered as a no-logo class. Evaluation protocol is the same than [START_REF] Krapac | Instance classification with prototype selection[END_REF]. BelgaLogoII [6] -10,000 images containing 2695 instances of 37 different logos. The main difference with FlickrLogos32 is that images are multi-labeled and that that the average size of the logos is much lower. Evaluation is completed by leave-one-out queries. Vehicles29 [8] -10,622 images labelled with 29 car models of 7 brands (divided into 5,266 training and 5,356 test images). Evaluation protocol is the same than [START_REF] Krapac | Instance classification with prototype selection[END_REF]. LegalEntities5K -371,924 images noisy labelled with 5,824 legal entities. This dataset was automatically created by querying Google Image search engine with the entities names. The list of the entities is the union of several thesaurus found on the web and contains world-wide companies, associations, organizations and sport teams. To try limiting noise, we kept only the top-20 to top-1000 results as a function of the popularity of the tag (number of pages returned by Google). A test set was built by taking the 2, 500 of the most popular tags of the dataset. A second test set was created by intersecting the whole Flickr32 dataset with the labels of LegalEntities5K (540 test images belonging to 18 classes).

Method

FlickrL32 Vehicles29 Fisher Vectors (128x4,096) 0.866 0.497 Prototype voting [START_REF] Krapac | Instance classification with prototype selection[END_REF] 0.914 0.557 Our method (S-Ransac) 0.928 0.597 Features and parameters setting. Local features are SIFT features [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] extracted around interest points detected by the rotation-invariant Harris-Hessian-Laplace detector [START_REF] Mikolajczyk | An affine invariant interest point detector[END_REF]. The two main parameters of our method, i.e. the spatial neighborhood size m and the detection threshold τs were trained by cross-validation on the training sets of FlickrL-ogos32 and Vehicles29. m was set to 5% of the number of descriptors for each query image ans τs was set to 5.

Comparative study. Table 1 reproduces the results of [START_REF] Krapac | Instance classification with prototype selection[END_REF] and reports our own results using the same evaluation protocol. It can be seen that our method outperforms the previous baseline of [START_REF] Krapac | Instance classification with prototype selection[END_REF] (and de facto the other stateof-the-art classification methods) on the two experimented datasets, whereas the training stage of our method is much more scalable. It took respectively 13 minutes and 22 minutes to index and to compute the a posteriori multi-probe search model of the 51,054,054 descriptors of the Vehicles29 training set and the 91,800,540 descriptors of the FlickerLo-gos32 training set (including distractors images). The good results achieved by our method on the Vehicles29 dataset shows that it is well suited for such fine-grained image classification tasks even if it is not the primary goal of this paper.

Multiple labels. To evaluate our method in the context of multi-labeled images, we used the challenging BelgaLogos dataset. For this experiment, we randomly chose 1,000 images of the dataset that contain at least one labeled logo. Our method achieves a mAP of 82.30 which is quite impressive knowing that this dataset involves very small objects in highly cluttered contexts. To better illustrate the relevance of the produced labels for each played queries, Figure 2 displays the precision-recall curve of our method when varying the detection threshold τs. It shows that very high precision or recall values might be obtained depending on the applicative constraints.

Large-scale experiment on thousands of legal entities. It took 1 hour and 55 minutes to index the 500,957,407 SIFT features of the LegalEntities5K dataset and to compute the a posteriori multi-probe search model. Table 2 reports the results achieved on the two test tests in terms of mAP and search time. It shows that that the effectiveness of our method is still very satisfactory considering that (i) the number of classes in the training set is two orders of magnitude higher (ii) the training set was built automatically without any human validation and therefore contains a high level of noise.

CONCLUSION

The work reported in this paper was a first attempt towards deploying real-world visual-based entity recognizers at the web scale. It did show the importance of using finegrained geometry in this regard and demonstrated the advantage of instance-based classification methods in terms of scalability. Future works will focus on collecting and denoising training data in a more elaborated way than the proof of concept presented in this paper.

Figure 1 :

 1 Figure 1: Class-specific geometry consistency maps.

Figure 2 :

 2 Figure 2: Recall-precision curve of our method on the multi-labeled dataset BelgaLogos.

Table 1 :

 1 Classification performances.

Table 2 :

 2 Classification results and computation time on the LegalEntities5K dataset (Intel(R) Xeon(R) E5-2650 CPU 2.00GHz).

	Benchmark	mAP Avg Search time
	2.5K images / LegalEntities5K 0.686	7.4 sec
	FlickrLogos / LegalEntities5K 0.648	6.3 sec

http://www-rocq.inria.fr/imedia/belga-logo.html


J.-A Angles D'auriac

N Cohen

A El Maftouhi

A Harutyunyan

S Legay

Y Manoussakis

Connected Tropical Subgraphs in Vertex-Colored Graphs

In this work, we deal with tropical substructures in vertex-colored graphs, first introduced in [START_REF] Anglès D'auriac | Tropical dominating sets in vertex-colored graphs[END_REF]. Vertex-colored graphs are useful in various situations. For instance, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.) [START_REF] Bruckner | Evaluation of ilp-based approaches for partitioning into colorful components[END_REF]. Applications can also be found in bioinformatics ( Multiple Sequence Alignment Pipeline or for multiple proteinprotein Interaction networks) and in data bases (e.g. online social networks or matching products in online stores) [START_REF] Zheng | Omg! orthologs in multiple genomes -competing graph-theoretical formulations[END_REF]. Given a vertex-colored graph, a tropical subgraph (induced or not) is defined to be a subgraph where each color of the initial graph appears at least once. Potentially, any kind of usual subgraphs (paths, cycles, independent sets, dominating sets, vertex covers, etc.) can be studied in their tropical version. Here, we study minimum connected tropical subgraphs in vertex-colored graphs.

Throughout this abstract, we let G = (V, E) denote a simple undirected graph, and G c a (not necessarily properly) vertex-colored simple undirected graph with c different colors. A connected subgraph H of G c is said to be tropical if each color of G c is present at least once in H. The connected tropical subgraph number tc(G c ) is the order of a smallest connected tropical subgraph of G c . A connected rainbow subgraph of G c is a connected subgraph in which each color is present at most once. A connected colorful subgraph of G c is a connected rainbow subgraph which is tropical. We let δ(G c ) denote the minimum degree of G c . In this work, we study the following problem, from both an algorithmic and mathematical point of view:

Minimum Connected Tropical Subgraph Problem (MCTS) Input: Vertex-colored graph G c Question:
Determine the value tc.

In a first series of results below, we deal with NP-hardness, as well as sufficient conditions for MCTS.

Theorem 1. MCTS is NP-Hard on trees, interval graphs and split graphs.

We obtain these results by reduction from Dominating Set, Vertex Cover and Vertex Cover, respectively. Theorem 2. Given a vertex-colored graph G c , MCTS can be solved on G c in O(n 2 × m × 8 c ) time.

We now provide sufficient conditions for the existence of a connected tropical subgraph of a given order.

Theorem 3. Let G c be a connected vertex-colored graph with n vertices and m edges. The bounds of both theorems are tight as we can provide extremal graphs. In addition, the next theorem shows that Theorem 4 cannot be significantly improved.

For each k ∈ N, if m ≥ n-k-2 2 + n -c + 2, then tc(G c ) ≤ c + k.
Theorem 5. Let rδ(G c ) be the rainbow degree, i.e., the smallest number of colors a vertex of G c can have in its neighborhood.

1. Let ǫ, ǫ ′ ∈ [0, 1). There exists a vertex-colored graph G c such that δ(G c ) ≥ ǫn, rδ(G c ) ≥ ǫ ′ c
and G c has no connected colorful subgraph.

2. Let p be an integer. There exists a vertex-colored graph G c such that δ(G c ) ≥ n -c + p and G c has no connected colorful subgraph.

3. Let p be an integer, and ǫ ∈ [0, 1). There exists a vertex-colored graph G such that δ ≥ ǫn, G is p-connected and has no connected colorful subgraph.

In the rest of our work, we study MCTS in the case of vertex-colored random graphs. We recall that the random graph G(n, p) is the graph on n vertices where each of the possible edges appears with probability p, independently. Given a positive integer c, let G(n, p, c) be the graph obtained from G(n, p) by coloring each vertex with one of the colors 1, 2, . . . , c uniformly and independently at random. In what follows, we will say that G(n, p, c) has a property Q asymptotically almost surely (abbreviated a.a.s.) if the probability it satisfies Q tends to 1 as n tends to infinity. The threshold function for the property of containing a copy of a fixed graph G is n -1/m(G) where m(G) is the ratio of the number of edges to the number of vertices in the densest subgraph of G, that is,

m(G) = max e H v H : H ⊆ G , v H > 0 ,
where v H and e H stand for the number of vertices and edges of H, respectively.

The following theorem shows that this threshold also holds for the property of the existence of a tropical copy of a given graph in G(n, p, c). The proof of this result is fully based on that of the theorem of Bollobás.

Theorem 4 .

 4 Let G c be a vertex-colored graph of minimum degree δ. If δ ≥ n 2 and c ≥ n 2 , then G has a connected colorful subgraph, and we can find it in polynomial time.

(

  ii) If r < c(n), then a.a.s. G(n, p, r) contains a complete tropical subgraph of order r.The next theorem finds the distribution of T k for certain values of k.Theorem 9. Let p = θ/n, where 0 < θ < 1 is fixed. Let k = 1 θ -log θ log n -2 log log n + l ,where l is a fixed real number. Denote by T k the number of components of G(n, p, k) that are tropical trees of order k. Then T k has asymptotically Poisson distribution P(λ) with mean λ = (θ -log θ) 2 e l θ .

Theorem 6. Let G be a fixed graph with at least one edge, e G > 0. Let c = v G = |V (G)|. Then

In the next theorem we investigate the case in which pn 1/m(G) → θ as n → ∞, where θ is a positive constant. We are specially interested in a family of graphs called strictly balanced graphs defined as follows.

that is to say that every proper subgraph of G is strictly less dense than the graph itself. Trees, cycles and complete graphs are strictly balanced. Then, for any ǫ > 0, the clique number of G(n, p) satisfies

This leads us to the natural question of what is the maximum number of colors c = c(n) which a.a.s. guarantees the existence of a tropical clique of order r in G(n, p, r), for every r ≤ c(n). The answer to this question is given by the following theorem.