Laurent Joly
email: laurent.joly@univ-lyon1.fr

Thierry Biben

Wetting and friction on superoleophobic surfaces

This article describes the physics of superoleophobic surfaces, combining a recently developed free-energy approach and finite element modeling. We start by investigating the peculiar wetting behavior of such surfaces, originating in their "re-entrant" geometry, and discussing a specific mechanism for the "filling transition", leading to the loss of superoleophobicity. We then focus on their friction properties, and establish an important condition for their use as super-lubricating surfaces. This new insight into the underlying mechanisms of superoleophobicity enables us to suggest general principles to optimize the wetting and friction properties of those promising surfaces.

Since the late nineties, micro or nano-structured surfaces have attracted a lot of attention in different fields [1][2][3][4][5][6][START_REF] Roach | Newton[END_REF][8][9][10][11] . This interest is motivated by the "super-wetting" properties of these surfaces (superhydrophobicity, superhydrophilicity, superoleophobicity, superoleophilicity, . . . , generically called superhygrophobicity or superhygrophilicity, as suggested in 12 , whatever the nature of the liquid) and by the consequences these properties have on various transport phenomena at the surface (in particular, matter 13 and heat 10 transfert). One important field of application is microfluidic 14 , where superhydrophobicity of suitably prepared textured surfaces can lower in a substantial way the friction between the surface and water, reducing the viscous dissipation in the device 13,[15][16][17][18] . Similar surfaces can be produced to repel oil, but repelling both oil and water with the same surface is a true challenge since surfaces that repel water are usually attracting oils. The recently introduced "re-entrant" geometries 12,[19][20][21][22][23] (see for instance Fig. 5.b) are interesting in this context since these structures can drive a wetting inversion, leading to surfaces repelling both water and oils (traditionally referred to as superoleophobic surfaces). The geometrical reason responsible for the wetting inversion has been investigated by Marmur in 12 , and results from the multivaluation of the surface (several solutions exist for a given liquid-gas contact area, as defined in 12 ). As a consequence, a Cassie-Baxter state can exist even when the surface is intrinsically wetting. The surfaces we consider have this property. But this peculiar behavior only appears as a metastable state as we shall see, and controlling the mechanism of metastability is the key point. Investigating these mechanisms is the goal of the present study, that extends in some way the work of Marmur. Another important field of application concerns thermal transport, where superhygrophilicity of some nanostructured surfaces can be used to increase the Critical Heat Flux 9,11 , that limits heat transport at the surface, or even to produce super-condensing devices. Controlling the wetting properties of these textured surfaces is thus a key ingredient for many applications. Another issue is the connection between the (static) wetting properties and the (dynamic) transport mechanisms (friction with the liquid in contact for example) 24 . We shall consider in this article these two aspects for different types of structured surfaces, and show that metastability is an important mechanism to understand and design new surfaces with complex and interesting properties.

To introduce the problem, we shall first consider the example of superhygrophobicity, and generalize afterwards to other types of surfaces. Micro or nano-texturing an initially smooth surface increases its roughness, and thus amplifies its wetting properties since the contact area between the surface and the liquid is increased (Wenzel theory 25 ). An initially hygrophobic smooth surface should become even more hygrophobic after structuring. A wetting transition can be induced by roughness as well when hygrophobicity becomes large -as shown by Cassie and Baxter 1 , leading to the "superhygrophobic" state. While the Wenzel state corresponds to a contact of the whole surface with the overlaying liquid, the Cassie-Baxter state corresponds to a composite wetting, where the liquid phase is suspended on the top of the asperities, with a gas phase (air or vapor or both) trapped in between (see Fig. 1). The Cassie-Baxter state is also referred to as the "Fakir" state, and we shall use this simple idiomatic terminology in the following. By opposition, the Wenzel state is often called the "impaled" state, and we shall again use this name in what follows. The Fakir state is interesting since the gas layer trapped between the surface and the liquid plays the role of a lubricant, and can induce a large slippage of the fluid 13,[15][16][17][18] . Slippage is however not perfect since it competes with the friction applied by the roughness 26,27 . Efficiency of slippage is characterized by the slip length b, that gives the position inside the surface where the extrapolated velocity field cancels (see Fig. 2). It has indeed been shown by many authors 13 that far away from any kind of surface, the velocity field corresponds to the field produced by an effective planar surface with the partial-slip -or Navier -boundary condition (BC):

v (z s ) = b ∂v ∂z z=zs , (1)
relating the slip velocity v , the slip length b and the local shear rate on the effective planar surface -often named the 'plane of shear' -placed in z = z s (see Fig. 2). The slip length is very sensitive to the details of the surface texture: Anisotropic textures usually leads to anisotropic slippage, giving rise to interesting applications (mixing in microchannels 28 for instance). More generally, the link between the wetting properties of the textured surface, and of an ideally smooth surface of the same chemical nature (the reference surface), is plotted on a wetting diagram. This diagram gives the variation of the effective contact angle θ eff (more precisely cos θ eff ) of a liquid placed on the textured surface as a function of the intrinsic contact angle θ (in fact cos θ) of the reference smooth surface. The wetting states are clearly visible on these diagrams since they give rise to different branches; The transition points can be identified by the intersections of the branches. The wetting diagram is obtained by using the Young law:

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¡¢
¥ ¡¥ ¥ ¡¥ ¦ ¡¦ ¦ ¡¦ § ¡ § § ¡ § ¡¡ ¨© ¡© © ¡© ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ! ¡! ! ¡! " ¡" " ¡" # ¡# # ¡# $ ¡$ $ ¡$ % ¡% % ¡% & ¡& & ¡& ' ¡' ' ¡' ( ¡( ( ¡( ) ¡) ) ¡) 0 ¡0 0 ¡0 1 ¡1 1 ¡1 2 ¡2 2 ¡2 3 ¡3 3 ¡3 4 ¡4 4 ¡4 5 ¡5 5 ¡5 6 ¡6 6 ¡6 7 ¡7 7 ¡7 8 ¡8 8 ¡8 9 ¡9 9 ¡9 @ ¡@ @ ¡@ A ¡A A ¡A B ¡B B ¡B C ¡C C ¡C D ¡D D ¡D E ¡E E ¡E F ¡F F ¡F G ¡G G ¡G H ¡H H ¡H I ¡I I ¡I P ¡P P ¡P Q ¡Q Q ¡Q R ¡R R ¡R S ¡S S ¡S T ¡T T ¡T U ¡U U ¡U V ¡V V ¡V
cos θ eff = γ eff SV -γ eff SL γ LV , (2)
where γ LV is the liquid-gas surface tension, γ eff SV is the effective surface tension between the gas and the substrate, and γ eff SL is the effective surface tension between the liquid and the substrate. By "effective" we mean that this surface tension is the global surface energy divided by the apparent macroscopic area of the surface (the asperities are not visible at the macroscopic scale, and the textured surface look smooth at this scale). For a particular geometry of the surface, and making assumptions on the possible wetting states, it is possible to get theoretical expressions for these effective surface tensions and to obtain the corresponding branches. We show in Fig. 3 the shape of this diagram for a crenelated surface, where we can identify three branches. While the first one (I) corresponds to the Cassie-Baxter state, a competition between a fakir state for the liquid, and an impaled state for the gas in contact with the surface (see Fig. 3), branch II corresponds to an impaled state for both the gas and the liquid phase (the situation considered by Wenzel), and branch III, very promising in the context of condensation and boiling, corresponds to an impaled state for the liquid, and to a composite wetting situation -with liquid condensed in the asperities -for the gas-substrate surface tension. We shall refer to this last state as the "inverse-fakir" state, since it is the exact inversion of the fakir state described above. As a generic feature, we can see that the structuring of a surface can only enhance its natural wetting property, a smooth hygrophilic surface will become more hygrophilic after texturing, and a smooth hygrophobic surface will become even more hygrophobic once textured. Reversing the wettability is not possible if we refer to Fig. 3. This quite generic wetting diagram, obtained in the macroscopic framework introduced by Wenzel, Cassie and Baxter raises in fact many questions. First, it is derived from a purely macroscopic approach and we can wonder if it is still valid at the nanometric scale. This question received a positive answer thanks to the molecular simulations done by Cottin-Bizonne et al. 29 : The Cassie-Baxter -Wenzel transition is indeed observed even for nanostructured surfaces. Next, only a limited number of wetting states are taken into account in this macroscopic approach, the lowest surface energy state being considered as stable. We can thus also wonder if all the possible states have been found. A more systematic approach would consist in minimizing the free energy of a system presenting a liquid-gas coexistence in contact with the textured substrate. Such an analysis is presented in 12 , with some restrictions (planar interfaces, macroscopic theory), leading to analytical results. We used a more general approach in a previous study 30 , based on numerical minimization of a free energy model, and showed that the Wenzel -Cassie -Baxter framework is correct even at very small scale, provided little corrections accounting for corner energies are made. But the most interesting result concerns metastability. The wetting transitions are first order phase transitions and metastable states are possible. Metastability has already been reported in many experimental situations [31][32][33] , and a very important question is to understand the mechanisms that control it 3,4,[34][35][36] . Metastability usually only delays a transition, but we shall see that depending on the structure of the surface, it can even lead to a reversal of the wettability. A study of metastability requires a model able to cope with free-energy barriers, and this is the reason why we used our free energy model to investigate this problem. Since we are also interested in the determination of the effective hydrodynamic boundary conditionse.g. the slip length -even in the metastable states, the free energy model is combined to a hydrodynamic equation to get both the static and the dynamic properties. We shall restrict our modeling to finite element computations when the thermodynamic aspects are not important.

We discuss in section 2 the main ingredients of the model; A more detailed discussion and justification will be found in 30 . The results are presented in section 3 for the wetting diagram and the discussion on metastability in the context of superoleophobic surfaces. In section 4 we consider the friction properties of these surfaces and section 5 is devoted to our conclusions.

Model and Parameters

Several approaches can be used to model the physics of a fluid close to an interface. At the nanometric scale a fluid is made of molecules, and the standard theoretical and numerical tools at these scales are statistical mechanics and molecular dynamics. These very powerful tools provide interesting informations on the structuring of the fluid close to a smooth surface, and give access to the thermodynamic and the dynamic properties of the fluid at these very small scales. Although fully general in their principle, applying these methods to microstructured surfaces is very difficult due to the huge number of molecules one need to consider at the micron scale (10 9 -10 12 ). Alternatively, continuum models are known to be valid even at very small scales: they can be applied down to the molecular scales with special care. The thermodynamic properties (phase behavior, wetting properties, interfacial tensions...) have been widely investigated in the context of statistical mechanics at the nanometric scale, within the framework of Density Functional Theory (DFT). DFT generalizes the macroscopic thermodynamic potentials, like the Free energy, to very inhomogeneous situations including fluidsurface interactions or liquid-gas coexistences. Instead of minimizing a free energy, we need to minimize a free energy functional F [ρ] where ρ(r) is the density profile of the fluid close to the surface or at a liquid-gas interface. Although DFT provides a formal expression for this functional, it is far from explicit and approximate functionals must be used in practice. It is not our purpose to describe in details the molecular organization close to the surface; Our goal is rather to relate the effective macroscopic wetting and slip properties to the nanometric intrinsic properties of the interfaces. For the wetting properties, this connection is given by the wetting diagram where the macroscopic effective contact angle θ eff is given as a function of the nanoscale intrinsic contact angle θ of the reference atomically smooth surface. To this end, we shall consider the simplest functional we can construct, including only the necessary ingredients to describe the wetting transitions: the free energy functional must account for a possible liquid-gas coexistence induced intrinsically by the roughness, and for the various surface tensions leading to the determination of the contact angles. The simplest free energy we can use to model a liquid-gas coexistence is given by the van der Waals equation of state; Inhomogeneities and interfaces can be treated in the simple square gradient approximation [START_REF] Rowlinson | Molecular Theory of Capillarity[END_REF] :

F [ρ] = dr{f (ρ) + w 2 2 |∇ρ| 2 + ρV wall (r)}, (3)
where f (ρ) = k B T ρ{log( ρb 1-ρb ) -1} -aρ 2 is the van der Waals bulk free energy, the square gradient term w 2 2 |∇ρ| 2 penalizes the formation of an interface and is thus responsible for the liquid-gas surface tension, and V wall (r) is the interaction potential between the molecules of the substrate and the molecules of the fluid. We use a Lennard-Jones potential to model these interactions:

V LJ (r) = 4 [(σ/r) 12 -(σ/r) 6 ],
where σ is a molecular length. V wall (r) thus fixes the intrinsic wetting properties of the substrate, namely θ: by tuning the value of we can scan the whole range of wettability for the reference surface. A minimization of this functional can be performed in various ways, depending on the problem we wish to study. We shall introduce the Grand-potential functional

Ω[ρ] = F [ρ] -µ drρ(r)
where µ is the chemical potential, to write the general equations used in this study. This thermodynamic approach will give us access to the wetting diagram, without a priori assumption on the possible wetting states, but it shall also provide informations on the metastability since the free energy barriers are included in the formulation. In order to probe the dynamic of the fluid, we use a hydrodynamic transport equation to describe the velocity field close to the surface. The validity of hydrodynamics at very small scale has been checked both by molecular simulations [START_REF] Bocquet | [END_REF]39 and by Surface Force Apparatus (SFA) experiments for simple molecular liquids like water or small alcanes 40,41 . The main concern with the use of hydrodynamic at the molecular scale comes from the boundary conditions (BC) that must be redefined. Molecular simulations and SFA experiments showed that the most general formulation for the hydrodynamic BC for a liquid close to an atomically smooth surface is the partial slip BC (1), where the slip length b is a nanometric length in this case, and z s is an atomic size (the effective planar surface is indeed located approximately one or two molecular layer inside the liquid for most liquids and atomically smooth surfaces [START_REF] Bocquet | [END_REF]39 ). Two very different slip lengths thus appear in the study of micro or nanostructured surfaces: the intrinsic slip length b corresponding to the friction of the liquid on the surface at the molecular scale (see Fig. 4 ), and the effective slip length b eff of the textured surface at the macroscopic scale. While b results from the molecular interactions only (b is the slip length of the atomically smooth reference interface), b eff is due to the texture of the surface. b remains of the order of 10 nm for usual non-wetting surfaces 13 , whereas b eff can reach the micron scale depending on the scale of the structure 13 . Since we are not interested in the nanometric effects controlling the intrinsic slip length b in this study, we shall fix its value to reproduce the experimental and numerical observations, and focus our attention to b eff for different structures and wetting properties of the surface. The hydrodynamic equation for the velocity field v reads:

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¡¢
∂ρ m v ∂t + ∇ • (ρ m vv) = ∇ • σ -ρ∇ δΩ δρ + f wall , (4)
where ρ m = M ρ is the local mass density (M is the molecular mass) and σ = η(ρ)(∇v + ∇v t ) is the local viscous stress tensor [η(ρ) ≡ νρ m is the local viscosity, with ν the kinematic viscosity, assumed to be constant in both phases]. The term exhibiting Ω in the hydrodynamic equation accounts both for the pressure tensor of the van der Waals fluid and for the capillary effects, as discussed above. To fix the intrinsic slip length b of the reference surface we introduce an empirical friction force f wall exerted by the walls on the fluid within a small range -equal to the range σ of the wall/fluid interaction potential V wall (r), reflecting the friction force exerted by an atomically smooth wall on the first layer of fluid molecules.

f wall = -k ρ(r)v(r)ρ wall (r). ( 5
)
This force is proportional to the interaction energy between the solid and the fluid 13,39 , and to the density of interacting molecules: the molecules of the fluid -through ρ(r), and the molecules of the wall represented by the local density ρ wall (r). With the spontaneous depletion of the liquid from non-wetting walls, this enabled us to reproduce quantitatively the evolution of b with θ, as will be detailed in section 4. b varies from 0 for wetting situations (θ ∼ 0 • ) to b ∼ 10 nm (depending on the value of k) in nonwetting cases (θ ∼ 120 • ). To account for the phase equilibrium and the macroscopic transport, the minimization of the grand-potential is performed through an Allen-Cahn or Cahn-Hilliard equation including the convective trans-port:

∂ρ ∂t + ∇ • (ρv) = -C δΩ δρ or = C ∆ δΩ δρ (6)
The first writing is a non-conserved Allen-Cahn dynamics, convenient for the study of phase equilibria since the system is in contact with a reservoir of matter fixing the chemical potential µ; in that case C is a constant fixing the relaxation time to equilibrium. The second writing corresponds to a more realistic conserved Cahn-Hilliard dynamics, where the number of molecules is held constant; The constant C is now related to the self diffusion coefficient of the molecules in the fluid, and can be adjusted to match the proper value in the liquid under study. This Cahn-Hilliard formulation is useful, for instance, to study the friction properties of the liquid on the wall. Once the intrinsic slip length b and the intrinsic wetting angle θ of the reference atomically smooth surface have been fixed, the two equations ( 4) and ( 6) can be solved iteratively to measure the effective wetting angle θ eff and slip length b eff of a textured surface. The texture is defined through the spatial variation of ρ wall (r), that can be chosen at will to represent crenelated surfaces, surfaces with posts or reentrant geometries as recently studied in the context of superoleophobic surfaces. gate the very different wetting behavior of these two types of surfaces in this part.

Wetting properties

Two possible ways can be used to determine the contact angles. The most direct way is to measure the shape of a drop placed on the surface, and determine the angle it forms with the substrate at the triple line. The second way is to measure the various surface tensions and use the Young law (2) to deduce the wetting angle.

While the first method is the experimentally efficient way to proceed, the second is in fact the most efficient strategy from the numerical point of view. Although a direct measurement of the contact angle of a drop on a smooth substrate is possible -and has been done as a check, this method is far from optimal since it requires a huge amount of computation time -due to the large scale of the drop, and a careful adjustment of the drop shape -a source of errors. For textured surfaces, a direct measurement of the contact angle is plagued by the roughness: Many metastable states can indeed exist at the triple line, forcing the drop size to be several orders of magnitude larger than the roughness amplitude to expect an accurate determination. This method is not tractable in practice. On the contrary, the measurement of the surface tensions only requires small scale computations (as pre- sented in Fig. 6 where the small rectangles represent the simulation boxes), a single pattern is sufficient to determine the various surface tensions, and this method is numerically very accurate since no adjustment needs to be done (the interfacial energy directly results from the freeenergy model we consider).

The wetting diagram for the two types of structured surfaces described above is probed using the strategy presented in the previous section: the intrinsic contact angle θ is tuned by changing the interaction potential between the molecules of the fluid and the molecules of the substrate (parameter ), and the resulting effective contact angle induced by the structure is determined by a measurement of the surface tensions. To measure γ eff SV we start the computation with a gas phase in contact with the textured surface, and after equilibration the surface energy is computed from the free energy functional. An identical procedure is applied for γ eff SL , where the liquid phase is placed in contact with the textured surface. γ LV does not need to be measured (although we did it to test the accuracy of the numerical scheme) since there is an analytical expression for it [START_REF] Rowlinson | Molecular Theory of Capillarity[END_REF] . To probe metastability, we can vary the initial configurations. Two types of initial configurations have been used for each simulation: An initial configuration corresponding to an impaled state (for example a texture initially filled with liquid for the determination of γ eff SL ) and a composite wetting situation (Fakir state for γ eff SL ). After equilibration, only one state should be obtained if there were no metastability. The results are plotted in Fig. 7 for the crenelated surface, as reported in a previous article 30 . This figure illustrates different features of the wetting transitions. First the overall scenario obtained within the macroscopic Cassie-Baxter -Wenzel approach (Fig. 3) is well reproduced, the three branches corresponding to the stable wetting states are easily observed. We also observe an asymmetry of the wetting diagram not predicted by the macroscopic model. This asymmetry between the wetting and the non-wetting part of the diagram is due to local effects at the internal corners of the structure: an atom of the fluid suffers more attraction from the wall in this region than anywhere else, and the liquid phase is thus favored at the inner corners. While the consequences of these corner effects on the wetting diagram have been discussed in 30 , we mention here that they only modify the position of the wetting branches in a moderate way; The precise effect depends on the size of the texture and becomes negligible for large scale (micronic) textures. But we shall see in the following that the corners actually control the metastability, and this effect remains important even for large scale textures. Finally, we can note that the three branches give rise to metastable states, and we shall investigate below the mechanisms that control this metastability. Before discussing this important point, we must note that an effective non-wetting behavior can only be obtained when the surface is intrinsically (i.e. chemically) non-wetting: the lower right quadrant corresponding to intrinsic wetting and effective non-wetting is not reached. From this point of view, a surface that is intrinsically oleophilic (a common situation for superhydrophobic surfaces) cannot be converted to a superoleophobic surface with this kind of structure. These crenelated surfaces are thus not good candidates to repel both water and oils.

If we now consider the re-entrant geometry schematically represented in reversed at this point. This loss of superrepellency is due to the filling transition: the cavity initially filled with gas in the fakir state suddenly fills with the liquid phase. A control of the factors entering into this transition should enable us to improve those surface, in particular to increase the metastability. Let us thus now < 90 °θ Since the filling of the cavities with the liquid phase does not depend on the nature of the top phase, it is thus a property of the cavity itself. We can also observe that this transition occurs at the same value of the intrinsic contact angle, cos θ 0.58, for both the re-entrant surface (Fig 8 ) and the crenelated surfaces -whatever the height of the crenels (see the inset of Fig 7). This insensitivity of the transition to the global shape of the cavity enables us to conclude further that the mechanism responsible for the filling of the cavities with the liquid is a local effect.

In fact we can monitor the transition with our dynamical model and see that the filling of the cavities with the liquid phase is due to a local condensation of the liquid at the internal corners of the cavity. A movie of the transition for re-entrant surfaces is available as an Electronic Supplementary Information (ESI), and an isodensity plot is given in Fig. 11 for a crenelated surface. The internal corners of the structure are very favorable sites for the molecules of the fluid since they feel at this particular place the attraction of the two faces of the corner. This excess of attraction at the internal corners confers to these sites the property to be natural nucleation sites: liquid droplets spontaneously form at the corners and progressively fill the cavity. To understand why the liquid forms spontaneously at the corners, we can follow the density of the gas phase at these points when we approach the transition value cos θ 0.58. This density in fact corresponds to the maximum density of the gas phase in the cavity. A plot of this quantity for a crenelated surface is given in liquid phase to form spontaneously at the corner, but this transition is only local and an extra energy contribution must be added to form the liquid-vapor interface. It is thus not a surprise if the critical value of the density is significantly higher than the value corresponding to the maximum of the Grand-potential. We mention that the value H = 5 nm is a bit particular since the crenels in this case are so small that we cannot truly distinguish the fakir state from the impaled state. With this interpretation, the transition should be a first order transition involving nucleation-growth processes. In the framework of our model, we do not account for the thermal fluctuations and thus cannot study the nucleation process itself. But we can capture spinodal decompositions, and the liquid formation originates in an instability reminiscent of the crossing of a spinodal line in our approach.

To emphasize this point, we plotted in Fig 11 the variation of the average Grand-potential as a function of time. The latter decreases slowly at the beginning, and then faster until the two droplets formed at each corner enter in contact and merge. The initial configuration is thus unstable, which corresponds to a spinodal situation. We expect that in experimental systems, thermally activated nucleation will be the predominant mechanism, and the transition should thus occur slightly below the critical value we measured in this study. Now that the mechanism underlying the filling of the crenel has been identified, we understand that sharp corners inside the structure must be avoided if one wants to extend the metastability toward more wetting substrates. We applied this principle to our system by smoothing the fluid/wall interaction potential with a gaussian of width 0.5 nm. For a given intrinsic contact angle, the peak density at the inside corners is then much lower, and no filling of the crenels could be observed until cos θ → 1. We also used a slightly larger wall-fluid interaction range σ, here again diminishing the peak density at the corners and therefore extending the metastability toward more wetting situations (Fig 10). Inset: snapshots of isodensity (ρσ 3 = 0.4) lines after 0, 27000, 34000 (just before the contact of the two drops), 35000 (just after the contact), 39000 and 80000 time steps.

Friction properties

We have shown in the previous section that re-entrant geometries can provide metastable superhygrophobic fakir states subsisting even when the surface is intrinsically hygrophilic.

We are now going to investigate the possibility to obtain very low frictions (or equivalently very large effective slip lengths) of liquids on these surfaces by using this fakir state. To measure the effective slip length b eff of the reentrant surfaces, we confined a liquid between a smooth wall (top wall) and the structured surface (lower wall), and probed the effective hydrodynamic Boundary Conditions (BC) on each wall (Fig 12). This geometry enables us to get both the intrinsic slip length b, that corresponds to the atomically smooth top wall, and the effective slip length b eff measured for the structured lower wall, in the same conditions. It must be noted that the partial-slip BC depends on two parameters, the slip length, but also the position z s where the boundary condition is applied, sometimes referred to as the 'plane of shear'. For smooth surfaces, as already discussed in section 2, z s is in general a nanometric distance from the wall, but for structured or rough surfaces, this parameter will give the effective hydrodynamic position of the surface. Let us thus use the notation z eff s to identify the position of this plane for a textured surface; z s will be reserved for the reference smooth surface. The determination of the two parameters b eff and z eff s requires the knowledge of the system response to two different types of flow. We will therefore use a Couette and a Poiseuille flow for this identification. A good indicator of the slip amplitude, often considered experimentally, is the extrapolated no-slip plane position z eff no-slip = z eff s -b eff (Fig 12): the deeper is this position inside the solid, the better is the liquid transport through the channel. We plotted in Fig 13 its evolution for the smooth and textured surfaces, as a function of the intrinsic contact angle θ. On the smooth surface, our model -including a friction force exerted by the walls on the fluid within a small range, as detailed in section 2 -reproduces quantitatively the expected behavior, with almost a no-slip BC in the hygrophilic limit, and a few tens of nanometers slip length for highly hygrophobic surfaces.

More interesting is the slippage on the reentrant ridged surface. A striking point is the quick decrease of liquid slippage as the surface becomes more wetting, even though the surface remains in the fakir state; besides, we did not observe a large change of the slip behavior before and after the filling transition. This can be understood by looking at the dissipation around the structure, as detailed in the ESI. We observed that the maximum value of the viscous dissipation comes from the curved sections of the surface that are oriented at 45 • from the shear direction, due to the elongational component of the flow. A consequence of this large viscous dissipation at the upper edges of the structure is the dramatic reduction of the slip The filling of the cavity with the liquid phase, as observed for cos θ = 0.6, does not change much the situation and only very small differences can be observed in the dissipation profiles (see the ESI), with very little consequences on the slip properties. It has been known since the work of Richardson 26 that roughness goes against hydrodynamic slippage, possibly leading to an effective no-slip BC on a locally perfectly slipping surface. Recently, Steinberger et al. 27 have shown that in the presence of a curved meniscus, SH surfaces could even slip less in the fakir state than in the impaled one. Our point here is that for a re-entrant surface in the fakir state, the curvature of the solid surface reduces slippage even in the ideal situation of a perfectly flat liquid/vapor meniscus. In order to quantify the influence of geometry and contact angle on the slip properties of such surfaces at reasonable computational cost, we turned to finite element calculations. We modeled a newtonian liquid in the Stokes regime confined between a smooth wall and the reentrant ridged surface, in the fakir state, as illustrated in Fig 5 .c. The results are detailed in ESI. On the whole, one can note that the slip properties can be affected significantly for wetting liquids, as soon as the radius R of the 'reentrant' structure (see Fig 5 for the definition of R) is larger than typically one hundredth of the pattern periodicity L. It is therefore crucial to use an extremely sharp 're-entrant' structure (with R/L < 0.01) if one wants oil to slip efficiently on such surfaces.

Conclusion

In this article, we have shown that our recently developed free-energy approach could account for the exceptional wetting properties of the reentrant textured surfaces used for the production of superoleophobic surfaces. In particular, we investigated the mechanism underlying the "filling" transition for the liquid on a such a surface. The liquid/vapor meniscus being unable to invade the re-entrant geometry, this transition originates in the spontaneous filling of the inner cavity with liquid, when the solid surface becomes locally too wetting. We have shown that the filling process was favored by the presence of sharp corners inside the structure; Consequently, internal corners must be avoided in the design of SO surfaces in order to optimize their wetting properties. From the point of view of the slip properties of liquids on SO surfaces, we have shown that the re-entrant curvature in the vicinity of the contact line introduces an additional friction and decreases hydrodynamic slippage. Consequently, SO surfaces should be designed with an extremely flat top and the sharpest 're-entrant' geometry as possible, in order to provide the best slip properties.

Figure 1 :

 1 Figure 1: Wenzel and Cassie-Baxter states for patterned hygrophobic surfaces.

Figure 2 :

 2 Figure 2: Partial slip boundary condition: definition of the slip length b and of the 'shearplane' position z s .

Figure 3 :

 3 Figure 3: Wetting diagram for a crenelated surface. The small boxes show the wetting states considered for the calculation of γ eff SV and γ eff SL .

Figure 4 :

 4 Figure 4: Definition of the slip lengths that enter into play for a patterned surface. b is the nanometric (intrinsic) slip length, corresponding to the slip length on the reference smooth surface, while b eff is the effective slip length, induced by the structure.

Figure 5 :

 5 Figure 5: Systems under consideration. (a) crenelated surface; (b) re-entrant surface; (c) System considered for the finite element modeling, where W * = W/L and R * = R/L.

Figure 7 :

 7 Figure 7: Wetting diagram of the crenelated surface, using various initial wetting configurations: (cross): both liquid and vapor in the impaled state (Fig 6.a); (square): liquid in the impaled state and vapor in the inverse-fakir state (Fig 6.b); (circle): liquid in the fakir state and vapor in the impaled state (Fig 6.c). Inset: Zoom on the filling transition for the vapor/solid interface, with both liq./sol. and vap./sol. interfaces initially in the impaled state (Fig 6.a), and for various crenel heights.

Figure 8 :

 8 Figure 8: Wetting diagram of the re-entrant surface, using the same notations than in Fig 7.

Figure 9 :

 9 Figure 9: Basic principle of superoleophobicity: the pinning of the meniscus at the re-entrant geometry ensures the metastability of the fakir state even for a intrinsically wetting surface.

Figure 10 :

 10 Figure 10: Formation of liquid drops at the inner corner of a crenelated surface: Evolution of the maximum fluid density at equilibrium inside the cavity with cos θ, for different crenel height H and varying wall/fluid interaction range σ; When not specified, H = 10 nm and σ = 0.75 nm. Inset: Representation of the adimensional Grand-potential governing the fluid behavior as a function of the numerical density ρ of the fluid.

Figure 11 :

 11 Figure11: Filling transition on a crenelated surface: Evolution of the total Grand-potential and average density of the fluid in the system during the filling of the crenel with the liquid phase. Inset: snapshots of isodensity (ρσ 3 = 0.4) lines after 0, 27000, 34000 (just before the contact of the two drops), 35000 (just after the contact), 39000 and 80000 time steps.

Figure 12 :

 12 Figure 12: System used to probe the friction properties on re-entrant surfaces: A liquid is confined between a smooth wall and the ridged surface presented in Fig 5.b. In order to determine completely the effective hydrodynamic BC (i.e. measure both the shear plane position and the slip length) on each confining wall, a Couette and a Poiseuille flow perpendicular to the ridges are imposed to the confined liquid, and the (x-averaged) velocity profiles along z are fitted in the middle of the channel, away from the surfaces. It is then straightforward to compute the effective no-slip plane position z eff no-slip = z eff s -b eff .

Figure 13 :

 13 Figure 13: Evolution of the extrapolated no-slip plane position as a function of the Young contact angle θ, for a smooth wall and a re-entrant ridged surface; Notations are explained in Fig 12 and its caption; For the structured surface, z wall is chosen to be the top of the pattern (see Fig 12). The insets represent three fluid density maps at the SO surface, for cos θ = -0.5; 0.5 and 0.6.

  ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¡£ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤

Acknowledgments

We would like to thank H. Rathgen for an enlightening discussion on SO surfaces, and gratefully acknowledge the suggestions of C. Cottin-Bizonne and C. Ybert which helped us improve the manuscript.


Muhammad Imran Razzak

S A Hussain

A Belaid

Muhammad Sher
email: msher@iiu.edu.pk

Multi-font Numerals Recognition for Urdu Script based Languages

Keywords: Numerals Recognition, Online Urdu Numerals, Handwriting, Urdu

Handwritten character recognition of Urdu script based languages is one of the most difficult task due to complexities of the script. Urdu script based languages has not received much attestation even this script is used more than 1/6th of the population. The complexities in the script makes more complicated the recognition process. The problem in handwritten numeral recognition is the shape similarity between handwritten numerals and dual style for Urdu. This paper presents a fuzzy rule base, HMM and Hybrid approaches for the recognition of numerals both Urdu and Arabic in unconstrained environment from both online and offline domain for online input. Basically offline domain is used for preprocessing i.e normalization, slant normalization. The proposed system is tested and provides accuracy of 97.1% .

I. INTRODUCTION

Character recognition is the process of converting the language written in spatial form into computer understandable form (Unicode). Online Recognition provides natural ways to interact with machine without having any typing skills. The character recognition is classified into two main domains with respect to input namely online and offline (Offline is further divided into two categories printed and handwritten). In offline image is available while in online strokes are available with timing information. Thus due to the additional timing information online character recognition is easy than handwritten offline character recognition.

The main problem of online Urdu handwritten digit recognition is to extract proper feature matrix, because both Urdu and Arabic are written. The use of digitizing tablet/light pen makes the data entry easy, flexible and its is a natural way of input while it is difficult to afford keyboard for enormous entries. Numeral for Urdu is written in Arabic script but commonly Roman numeral is used. Urdu, Farsi and Hindi numerals look very similar with minor difference [START_REF] Sadri | Application of Support Vector Machines for recognition of handwritten Arabic/Persian digits[END_REF]. Indian (Hindi, Urdu ) digits are used mostly in Arabic countries while Farsi digits are used mainly in Iran. The Indian digits are normally written in 11 classes. Figure [START_REF] Sadri | Application of Support Vector Machines for recognition of handwritten Arabic/Persian digits[END_REF] compares the Arabic (used in English and Latin), Farsi and Indian (Hindi). Now a day the mostly written digits are written in old Arabic figure 1 digit forms. Urdu numerals consist of line segments and curves and different arrangement of these numerals form different numbers as shown in figure 1 and figure 2.

Urdu digits mostly followed in Pakistan are shown in figure 2. Generally, in Urdu both Urdu numerals and old Arabic (used for English, Latin) are followed. Urdu is written in both but not at the same time. Basically numerals for Urdu are same like Farsi script but commonly written in Old Arabic numeral instead of Urdu numerals. A. Harifi et.al [START_REF] Harifi | A New Pattern for Handwritten Persian/Arabic Digit Recognition[END_REF] presented a technique for Persian digits using multilayer preceptiron and proposed asymmetrical segmentation pattern for feature extraction and 12 segment was used and used the shadow coding and 97.6% recognition is reported. S.V. Rajashekararadhya [START_REF] Rajashekararadhya | Efficient Zone Feature Extraction Algorithm for Handwritten Numerals Recognition of Four South Indian Scripts[END_REF] presented zone centroid and image centroid based distance metric feature extraction system for Indian script numeral recognition. The numerals centroid is computed and the numeral image is divided in to n equal zones. Average distance from centroid to the each pixel in the zone is computed. Nearest neighbor and feed forwards back propagation is used for classification and 99 %, 99%, 96% and 95 % accuracy is obtained for Kannada, Telugu, Tamil and Malayalam numerals. M. Hanmandlu et.al proposed zone based feature extraction for handwritten Hindi numerals. The image is divided into 24 zones for feature extraction. Bottom left corner of the image is considered absolute reference, the distance vector for each pixel present in the zone is computed with respect to reference zone. Then normalized distance vector is then computed by dividing the sum of distances vector of all black pixels in the zone with their total number and the process is repeated to obtain 24 feature sets.

Al-Taani Ahmad et.al, [START_REF] Ahmad | Recognition of On-line Handwritten Arabic Digits Using Structural Features and Transition Network[END_REF] presented structural method for recognizing on-line handwritten digits, input strokes are used for calculating and normalizing slope values of input coordinates. The change of direction is recorded using the successive slopes values. Finite Transition Network that contains the grammar of the digits is used to match primitive's string with corresponding digit to recognize the digit. The method is tested on sample of 3000 digits written by 100 different trained persons.

Chan et al. [START_REF] Chan | Recognizing on-line handwritten alphanumeric characters through flexible structural matching[END_REF] presented a structural approach for recognizing on-line handwriting. Structural features are extracted from the input strokes. The presented approach on 62 character classes (digits, uppercase and lowercase letters) and each class has 150 entries. Experimental results showed that the recognition rates were 98.60% for digits, 98.49% for uppercase letters, 97.44% for lowercase letters, and 97.40% for the combined set.

There are still many issues in Urdu, Persian, Arabic and Old Arabic numerals recognition. The main issue is the lake of standard for handwritten Urdu script. In Urdu, numerals are written in both script Urdu old Arabic forms, mostly old Arabic is commonly used while Urdu is used only when it is written in standard format. The separation of numerals from the words still have big problem. A little research has been done for the separation of numerals from the Urdu, Farsi, and Arabic words. The problem of separation and recognition of old Arabic and Urdu numeral is resolved in this paper. This paper describes the similarities and dissimilarities between the two main used in Urdu numerals writing are Urdu (like Farsi) and old Arabic from the character recognition point of view.

II. PROPOSED SYSTEM

An online numeral recognition system is presented which is capable of recognizing the both Indian and Arabic scripts written through the digitizing tablet or light pen. The system is divided into four parts as shown in figure 3. A structural feature based approach is presented to identify on-line handwritten Urdu Script numerals which depend upon the directional features.

The input strokes are converted into image to process the strokes from offline domain for skew and slant correction and normalization. As handwritten strokes are not uniform and slant may change on some stroke on one line therefore instead of global slant correction that does not guarantee that all the strokes are corrected properly. Hence local slant correction [START_REF] Bouchiareb | New Preprocessing Methods for Handwritten Arabic Word[END_REF] is used by divide the strokes into smaller size unit and perform slant correction on these smaller units. Similarly skew detection is performed through Hough transformation [START_REF] Bouchiareb | New Preprocessing Methods for Handwritten Arabic Word[END_REF], strokes are divided into smaller unit i.e. two to three strokes instead of single stroke to get better skew correction, and not more than three strokes to perform locally skew correction.

The normalization process of the input strokes is essential because of the different writing styles and font which results in several variations in size and shapes of the strokes. Thus to attain proper recognition result input strokes should be normalized. Normalization is performed by defining a uniform grid in the offline domain.

Smoothing [START_REF] Razzak | Combining online and offline preprocessing for online Urdu character recognition[END_REF] is preformed to reduce the variation for better feature extraction. Baseline information is used for many purposes in handwriting recognition which represents orientation in a word and it is essential for many handwriting task i.e character recognition, personality identification, and writer identification [START_REF] Razzak | Combining online and offline preprocessing for online Urdu character recognition[END_REF]. The algorithm used in [START_REF] Razzak | Combining online and offline preprocessing for online Urdu character recognition[END_REF] failed to find the base line properly. Minimum enclosing rectangle is used to find the base line for more than one stroke as shown in figure 4.

The main purpose of feature extraction from the input strokes is the extraction of those distinct patterns that uniquely define the stroke and are most important for classification. The task of human expert is to select those features that allow effective and efficient recognition. In the proposed online handwriting numerals recognition system we focused on the structural features. Structural features include loops, cusp, endpoints, starts points etc. Structural features are the shape defining features and these are based on the instinctive aspects of writing. Due to similarity between numerals of structural features are used. Several shape defining features are extracted as shown in figure 5. Loop is an important feature to differentiate some similar numerals, loop is divided into two categories small (only for zero written in Urdu Numerals) and large for other numerals.

As for Urdu numerals, loop is very small for zero digit, small loop may occur between some numeral due to noisy input as shown in figure. Feature purification process discards the incorrect features by using some defined rules. As small loop exist only in zero written in Urdu digits, thus small loop is removed from other feature matrix. Fuzzy provides a powerful tool for pattern recognition of irregular patterns. Fuzzy linguistic are the formal representation of recognition system made through fuzzy if/then rules. The core of the recognition process is the if/then fuzzy rules. And the features are the input to the fuzzy rules. The features are extracted with respected to timing as they occur. The inputs to the rules are features and timing information of each feature. These features are encoded using the fuzzy if then rules shown below.

Following rules are defined for the recognition of numerals five in Urdu script. The description of the above rules is if the starting and ending is same then loop exist, the starting and ending of the numerals are zero both in Urdu and old Arabic, five in Urdu, and eight in old Arabic. If it consist of two loops then the stroke is eight, else if the cusp exist between ending and starting point then clearly it five in Urdu

C. Hybrid Approach

For some numeral HMM failed where there is the small difference between Indian numerals like 1 and 7, 6 and 8, 4 and 9, similarly for old Arabic numerals. This confliction is resolved using the hybrid approach through fuzzy logics and HMM. A post processing step is applied that future decides upon the structural features and posterior probability obtained from the HMM. Its takes the all the identified ligatures with probability with in the threshold, and then identified the stoke with the help of unique features at starting and ending of the character. If there are no unique features that are helpful in defining the shapes of the output probability form the HMM then the decision is based on the probability form the HMM.

III. Conclusion

This paper presented the similarities and dissimilarities between these two scripts Urdu and old Arabic from the character recognition point of view. Rule based technique, HMM and Hybrid approach is presented to recognize the online digit recognition written in both Urdu and Old Arabic forms from both online and offline domain. As very little research has been done for the separation of numerals from the Urdu, Farsi, and Arabic words. The problem of separation of old Arabic and Urdu numeral is resolved in this paper. The digits are written either in Urdu or Arabic but not both at the same time.

The system provides accuracy of 97.4% using fuzzy rule and 96.2 using HMM and 97.8 using Hybrid approach on 900 samples by taking the input from 30 trained users. There are still many problem exist in Urdu script due to complexities in the script. The proposed technique work only for numerals input. The separation of numerals from the Urdu text still have big problem due to shape similarity.

Figure. 1 .

 1 Figure. 1. (a) Arabic digits (used mainly in Latin and English countries but also in others), (b) Farsi digits (used in Iran), (c) Indian (Hindi) digits (used in Arabic countries).

Figure. 2 .

 2 Figure. 2. (a) Urdu digits (used mostly in subcontinent),

Figure 3 :

 3 Figure 3: Basics structure for numeral recognitionCusp is the sharp turning point exists in some numerals as shown in figure. The cusp is divided into three main categories up, down and right. Up cusp is extracted when movement of pen is from downward after upward, while down cusp is upward after downward. The right cup is extracted when sharp turning point exist with movement left before right.The starting and ending directional features are extracted based on the chain code. Directional features

Figure 4 :

 4 Figure 4: Minimum Enclosing rectangle to find the base line

Figure 5 :

 5 Figure 5: Cups categorization up, down and right

Figure 6 :

 6 Figure 6: Directional features at starting and ending A. Rule Based Approach.Fuzzy provides a powerful tool for pattern recognition of irregular patterns. Fuzzy linguistic are the formal representation of recognition system made through fuzzy

Figure 7 :Figure 8 :

 78 Figure 7: Small loop issue

  Figure 10. Hybrid Approach

  If the written stroke is only one to recognize then it is considered as Old Arabic zero. If size of current stroke is less than the defined size of zero in Urdu then it is close to zero written in Urdu script and vice versa.

	script. Urdu Numerals
	100
	98
	96
	94	Fuzzy Rule
	92	HMM
	90	Hybrid
	88
	86
	84
	1 2 3 4 5 6 7 8 9 0
	Figure 9: Recognition rate of Urdu numerals using
	fuzzy logics
	B. HMM Based Approach
	Separate HMMs is built for each numeral which have 4 Cusp Up Cusp down states and 23 observation symbols. Features matrix is the
	input to the HMM as a observation symbols. For
	observation symbols 12 structural features are extracted.
	These structural features are eight small length directional
	features i.e in numerals 3 and eight long length
	directional features i.e in numeral 1 and 7 obtained from
	the chain code, loops, intersection, cusp upward and cusp
	downward, curve right, left, upward.
	Cusp right
	Up
	Left
		Right
	Diagonal Left	Diagonal Right
	Down

Rule for All other Strokes L i

	For Ligature L,
	Select HMM with maximum Probability L HMM For all other L i where i=1,2,…. 22 Calculate the probability difference L HMM -L i < α For L s = L HMM -L i < α Apply Rules for Post Processing
	Hybrid Approach Rules below
	Otherwise L HMM is the recognized ligature
	Hybrid Approach Rules
	For all ligatures L s Repeat the following steps If L s =1 and 7 If there is small left directional features at starting
	then L s = 7., Else if there is small left to right movement at
	starting and ending is downward with little diagonal
	then L s = 7 Else consider ligature L s = 1.
	Similarly


Dawood A Khan
email: dawood.khan@loria.fr

Nicolas Navet
email: nnavet@loria.fr

Bernard Bavoux
email: bernard.bavoux@mpsa.com

Jörn Migge
email: jorn.migge@realtimeatwork.com

Aperiodic traffic in response time analyses with adjustable safety level

In distributed real-time systems it is crucial to ensure the temporal validity of the data exchanged among the nodes. Classically, the frame Worst Case Response Time (WCRT) analyses, and the software tools which implement them, do not take into account the aperiodic traffic. One of the main reasons for this is that the aperiodic traffic is generally very difficult to characterize (i.e., the arrival patterns of the aperiodic frames). The consequence of this is that one tends to underestimate the WCRT, which may have an impact on the overall safety of the system.

In this paper, we propose a probabilistic approach to model the aperiodic traffic and integrate it into response time analysis. The approach allows the system designer to choose the safety level of the analysis based on the system's dependability requirements. Compared to existing deterministic approaches the approach leads to more realistic WCRT evaluation and thus to a better dimensioning of the hardware platform. * Jörn MIGGE was with PSA Peugeot-Citroën at the time the study was undertaken.

Introduction

Context of the study. In the field of real-time systems, methods to assess the real-time performances of periodic activities (tasks, messages) have been extensively studied. Response times, worst-case or average, and jitters can be evaluated by simulation or analysis for a wide range of scheduling policies provided that the activation patterns of the tasks and messages are well identified. The problem is more intricate for aperiodic activities since, in many practical cases, it is difficult to have a precise knowledge of their activation pattern and because deterministic WCRT analyses have not been conceived to handle aperiodic activities. For example, the arrival pattern of aperiodic frames in the body network of a vehicle is hard to predict, as it is dependent on the user interactions. However aperiodic frames of higher priority exchanged among the Electronic Control Units (ECUs) in the body network of a vehicle can delay periodic traffic. Indeed, most often the Controller Area Network (CAN) priority bus is used and the aperiodic frames do not necessarily get the lowest priority levels1 assigned to them.

Problem definition. In this paper, we address the problem of evaluating response times when both periodic and aperiodic activities are taken into account. Activities are termed frames in rest of the paper, because the approach will be developed and illustrated on the CAN bus, but our approach equally holds for tasks. The increase in the WCRT of the periodic frames which may be caused by the higher priority aperiodic frames could be critical for hard real-time systems as it could lead to the violation of the deadlines. Besides, large response times of aperiodic frames may jeopardize the execution of a function or may even raise safety concerns in some cases (e.g. headlights flashes in a vehicle). In addition, low responsiveness is negatively perceived by the user. It is worth mentioning that activities that are periodic by essence are sometimes implemented in an aperiodic manner in order to save resources.

Whatever the exact approach, one of the main step is to derive a model of the arrival patterns for aperiodic activities, what will be called in the following the aperiodic Work Arrival Function (WAF). Then, this aperiodic WAF has to be integrated into the response time analysis. There are however difficulties:

• obtaining aperiodic data (i.e., by measurements or simulation),

• modelling aperiodic data,

• integrating the model into schedulability analysis.

What we are discussing in this paper is not how to obtain data but how to model it and integrate it into schedulability analysis.

Ways to handle aperiodic traffic and their limitations.

There are two classical approaches to handle the aperiodic traffic:

• A worst-case deterministic approach : aperiodic frames are considered as periodic frames with their periods equal to the minimum inter-arrival times, this is the well known sporadic model [START_REF] Spuri | Scheduling aperiodic tasks in dynamic priority systems[END_REF]. However, in many cases, the minimum inter-arrival time is so small that the resulting workload is unrealistic, and often greater than 100% [START_REF] Zhang | Practical schedulability analysis for generalized sporadic tasks in distributed real-time systems[END_REF].

• An average-case probabilistic approach : the aperiodic traffic is modelled according to a probabilistic inter-arrivals process, the next step is then to estimate the "probable" number of arrivals in a given interval of time. This approach is clearly not suited to real-time systems because it largely underestimates the arrivals of aperiodic traffic which can occur in small time intervals 2 .

A basic probabilistic framework was set for inclusion of aperiodic frames in a controlled manner using a threshold value in [START_REF] Burns | A probabilistic framework for schedulability analysis[END_REF]. This paper builds upon this framework and discusses precisely the mechanism of deriving the aperiodic WAF, as well as it removes some assumptions placed in [START_REF] Burns | A probabilistic framework for schedulability analysis[END_REF].

In particular, we show that in our specific context it is not necessary that the different streams of aperiodic frames are modelled individually.

Overview of our approach. We do not assume any prior knowledge of the aperiodic frame activation pattern, however we assume that it is possible to monitor the system, or a simulation model of it, and gather data about the arrival times of aperiodic frames. Then, from the measurements, we build a probabilistic model of the aperiodic inter-arrival times under the form of an empirical frequency histogram or a distribution obeying a closed-form equation whenever possible. The next step is to derive a deterministic WAFs from the probability distribution of the aperiodic frame inter-arrival times. A general mechanism is provided enabling to derive the deterministic WAF from the underlying probabilistic distributions of the aperiodic traffic even given in form of empirical histograms, which is worthy in practice since aperiodic arrivals do not necessarily obey a closed-form equation.

Another advantage is that the technique is independent of the scheduling and can be used whatever the policy (preemptive, non-preemptive, fixed priority, dynamic-priority, etc) and whatever the task model. All in all, we believe that our proposal offers a better solution for taking into account aperiodic traffic in systems with dependability constraints, compared to worst-case and average case probabilistic approaches.

Organization of the paper. The rest of this paper is organized as follows: the modeling of the aperiodic traffic is described in Section 2. The aperiodic work arrival function is discussed in Section 3. Section 4 describes the schedulability analysis and a small case study. Finally, the conclusion is given in Section 5.

Modeling aperiodic traffic

The data used in this study comes from measurements3 taken on-board of a PSA vehicle but because of confidentiality reasons we have obscured the characteristics which could reflect about the design at PSA Peugeot Citroën. In order to model the interarrival times of the aperiodic traffic, we first analyse some important structural properties of the data (e.g., linear and non-linear correlation) then find out the probability distribution that best fits our data.

Exploratory data analysis

The presence of linear and non-linear dependencies in the data would impact its modelling because it would imply a departure from the i.i.d. property (independent and identically distribution). To test these two kind of dependencies, as classically done in exploratory data analysis, we make use of some visual confirmatory tests, the "run sequence plot" and "lag plot" here, as well as the autocorrelation and BDS test (Brock, Dechert, Scheinkman, see [START_REF] Broock | A test for independence based on the correlation dimension[END_REF]).

Run sequence plot

The run sequence plot displays an observed univariate data in a time sequence. It helps to detect outliers and shifts in the process. Figure 1(upper) is a run sequence plot of our data trace where the data points are indexed by their order of occurrence. The plot indicates that data does not have any long term shifts in heights over time.

Lag plot

A lag plot helps to gain some insight into whether a data set or time series is random or not. Random data should not exhibit any visually identifiable structure in the lag plot. Figure 1(lower) is a lag plot of our data trace (here the lag is chosen equal to 1: x = X k+1 and y = X k , where X k is the kth observation). Since the lag plot appears to be structureless, the randomness assumption cannot be rejected.

Figure 1: Visual analysis of captured data trace. The upper graphic is a run sequence plot where the x-axis is the index of the data points and the y-axis is the time till the next aperiodic arrival expressed in seconds. In the lower graphics, a lag plot, both axes indicates the time till the next aperiodic arrival in seconds.

Autocorrelation analysis

The autocorrelation analysis detects the existence of serial correlations in a data trace. Precisely the correlation of order k indicates the linear relationship that may exist between data values separated by k positions. The first 100 correlation coefficients of the data trace are shown in figure 2 associated with the thresholds beyond which the values are statistically significant (1% significance level here). The graphic visualization of the correlation coefficients makes it possible to evaluate the importance and the duration of the temporal dependencies. Here, serial correlations in the aperiodic traffic are relatively limited:

• limited in frequency: on the entire aperiodic traffic, there are only 19 significant auto-correlations coefficients until a lag of 100,

• limited in intensity: the few significant auto-correlations are below 0.2 which is insufficient to be used at ends of predictions.

Figure 2: Auto-correlation of captured data trace.

These autocorrelations can probably be explained by the fact that the activation of certain functions of the vehicle requires the transmission of several consecutive frames, but, the instants of activations of the functions have small correlations. Also, the spike that can be observed around the lag 50 is likely due to a periodic frame that has not been properly filtered out in the data trace.

BDS analysis

Auto-correlation has the limitation that it can only test the linear dependency in the data. In order to test for non-linear dependencies a more general statistical test than the auto-correlation must be used. One such test is the BDS test [START_REF] Broock | A test for independence based on the correlation dimension[END_REF] which employs the concept of spatial correlation from chaos theory to test the hypothesis that the values of a sequence, in this paper inter-arrival times, are independent and identically distributed (i.i.d.). Deviation from the i.i.d. case will be caused by the non-stationarity of the process (e.g., existence of trends), or the fact that there are linear or non-linear dependencies in the data. We carried out the BDS test for various combinations of its parameters m and d (for example for m = 2 and d = 3) as recommended by the authors of the test. For certain combinations we could not reject the hypothesis that the data points are i.i.d. at the 1% confidence level. The results of auto-correlation analysis and BDS test enable us to conclude that it is possible in our specific context to model the aperiodic inter-arrival traffic by a random variable obeying a memory-less probabilistic distribution without diverging from reality.

Distribution fitting

We now need to find the probability distribution and its parameters which models the experimental data the most accurately. After having drawn aside certain possibilities for obvious reasons (for example, the normal law because its density function of density is not monotonously decreasing), we tested distributions identified by adjusting their parameters according to the principle of the maximum of likelihood (MLE). Specifically, we have successively considered the exponential law, the log-normal law and the Weibull law. The exponential law was plausible a priori taking into account the decrease of the density which one can observe in the data trace, the two other laws have been chosen for their well-known flexibility.

Probability plots for visual selection

The distribution of the observed data is plotted against a theoretical distribution in such a way that the points should form approximately a straight line. Departures from this straight line indicate departures from the specified distribution. If the probability plot is approximately linear, the underlying distribution is close to the theoretical distribution. What can be observed in figure 3 is that the Weibull law is the distribution that best fits the data. This visual conclusion is confirmed by statistical acceptance tests discussed in the next paragraph.

Acceptance test

In previous section evaluation of the quality of results was done visually. In this section we use the statistical tests to verify the assumption that data trace follow a particular distribution. Specifically, we are using the q² and Kolmogorov-Smirnov "goodness-off-fit" tests" [START_REF] Millard | The Kolmogorov-Smirnov tests in signal detection (corresp.)[END_REF][START_REF] Brumback | A Chi-Square test for fault-detection in Kalman filters[END_REF]. The best results were obtained using the Weibull law, followed at some distance by the log-normal law. The conclusion of the two tests is that one cannot reject the assumption that the data follows a Weibull distribution at a significance level of 1%. For a broad data sample collected on a real system, and not artificially generated data, it is a conclusive result.

Figure 4 presents the real data trace and an "artificial" trace generated by a Weibull law with MLE-fitted parameters. It is observed that some "patterns" present in the real trace disappear and that the simulated trace is more homogeneous in time, but overall adequacy of the modeling seems good. From the analysis, carried out in this section, we can conclude that in our specific context the Weibull distribution provides a satisfactory model for the aperiodic traffic interarrival times, followed by log-normal and exponential distributions at some distance.

Parameter estimation without data trace

Because of cost and design time constraints, it is not always possible to derive the interarrival model from a real data trace, or traces of simulation. This is often the case in automobile projects. In such a situation, as an approximation, a solution is to set the parameters of the distribution based on already known parameters corresponding to another electronic architectures. In the following, we show how to adapt a Weibull4 model to a new intensity of the aperiodic traffic.

The expected value of a random variable obeying a Weibull law is:

E(X) = λΓ(1 + 1 k ) (1)
where l is the scale parameter, k is the shape parameter of the Weibull law and the Gamma function is an extension of the factorial function to the real and complex numbers. There exist many, more or less precise, approximations to calculate the gamma function. One good approximation is given by the following formula:

Γ(z) ≈ √ 2π z ( 1 e (z + 1 12z -1 10z )) 2 (2)
To adjust the expected value of the Weibull law for a new vehicle project, one simply has to change the scale parameter l to the targeted intensity of the aperiodic traffic. In first approximation, we assume here that the shape of the distribution should not change very importantly from project to project and so set the parameter k. This assumption should be verified in the light of the analysis of additional data traces but this is left as a future work. The network load of the aperiodic traffic, denoted ρ, obeys the relation:

ρ = ( 1 E(X) ). Ā (3)
where Ā is the average transmission time of an aperiodic frame. From equations 1, 2 and 3, one obtains:

λ = ( 1 Γ(1 + 1 k ).ρ ). Ā (4)
By replacing the values of network load, ρ, and average transmission time, Ā, by the values which correspond to the automotive network that one wants to model, one obtains the new value of λ.

The aperiodic work arrival function S(t)

S(t) is the aperiodic work arrival function which gives us the number of aperiodic frames in a time interval t and that will be used in the response time analysis. S(t) is an increasing "staircase" function such that the "jumps" in the function correspond to the arrival of an aperiodic frame. To construct this function, we propose to discretize the time and calculate the value taken by S(t) for each value of t between 1 and n where n, expressed in milliseconds, is the largest value that we may reasonably require during the computation of a response time. For example, one can set n = 1000ms if the largest period of activity on the bus (i.e.,the largest busy period) does not exceed a second.

Safety threshold α for S(t)

We denote by X(t) the stochastic process which counts the number of aperiodic frames in time interval t. For example, in the data trace which we studied in the preceding sections, inter-arrivals would be controlled by a Weibull law. The idea is to find the "smallest" Ŝ(t) such that the probability of X(t) being larger than or equal to Ŝ(t) is lower than a threshold value α fixed by the designer.

Formally, we are looking for:

Ŝ(t) = min{S(t) | P r[X(t) ≥ S(t)] ≤ α} (5)
For example, if one sets α = 0.01 it means that in no more than 1% of its trajectories the stochastic process X(t) induces more aperiodic traffic than Ŝ(t). If X(t) models the real aperiodic traffic accurately, the number of aperiodic frames integrated in the calculation of the response time of a periodic frame will have more than 99 percent chances to be higher than what each instance of the frame will undergo. Of course, the choice of α depends on the dependability objectives of (SIL, System Integrity Level, for example) but α = 10 -4 seems a reasonnable value in the context of a body network that will be considered in the experiments hereafter.

Computation of S(t)

We need a way to evaluate P r[X(t) ≥ S(t)] at each time instant t. Two cases arise. The first case corresponds to the situation where one can calculate explicitely:

P r[X(t) = n] = P r[X(t) ≥ n] -P r[X(t) ≥ n + 1] (6)
as it is possible for the exponential law. However, this is not analytically feasible when there is no closed-form solution. We should then either resort to numerical integration or to monte-carlo simulation. In the following, we choose to develop the later possibility because it is simple and completely independent of the underlying distribution. 5). It consists in finding the smallest value of k using the CDF of the interarrival distribution according to equations 5 and 6.

Graphical illustration

The case of discrete distributions

In case the distribution followed by the aperiodic frame interarrival is discrete, the equation 6 can be easily evaluated by summation of probabilities. Algorithm 1 describes the process of finding S(t) for discrete distributions where α is the targeted safety level, ∆ is the discrete time step, θ is the set of parameters of the distribution modeling the aperiodic frame arrivals (for example, chosen according to the Maximum Likelihood Estimate principle, MLE) and T is the maximum time one may reasonably require for the computation of a response time (e.g., 1 second for an automotive network).

Input: T ,α,∆,θ Output: S(t): The work arrival function

foreach each IDX ∈ 0:∆:T do k = 0; while 1-CDF(θ,IDX,k) > α do k = k+1; end S(IDX)=k;
end Algorithm 1: Algorithm for computing S(t) in the discrete case.

Monte-Carlo simulation

We do not always have a discrete distribution modelling the data nor a continuous distribution such that equation 5 can be evaluated analytically. We need an alternate method to evaluate equation 6 in such cases. This can be done with numerical integration techniques or using Monte Carlo simulation method. The latter approach is described in algorithm 2 where α is the safety level, ∆ is the discrete time step, θ is the set of parameters of the aperiodic frame arrival distribution, T is the time horizon, N is the number of random samples5 to be drawn for the Monte-Carlo simulation. Basically, S(t) is computed for each time unit by drawing N values from the probabilistic distribution modelling the aperiodic frame arrival process and checking if the accumulated probability value smaller than the probability value for which we are evaluating S(t).

Input: T ,α,∆,θ,N As an illustration of the approach, we derived S(t) in the cases where the aperiodic interarrival distribution obeys 1) an exponential law 2) a Weibull law 3) a log-normal law. The number of random draws of the Monte-Carlo simulations (parameter N in algorithm 2) is set to 5 million for each distribution. For all three distributions, the parameters are fitted using MLE against the data traces and the three distributions lead to the same average intensity. What can be observed is that the distribution, and not only the average intensity of the aperiodic traffic, plays a major role in the shape and height of the aperiodic WAF. 4 Experimentation

Basic schedulability analysis

Classically, schedulability analyses for real-time communication networks assume periodic or sporadic streams of frames [START_REF] Tindell | Calculating Controller Area Network (CAN) message response times[END_REF][START_REF] Davis | Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised[END_REF]. In this paper, for the sake of simplicity, we make use of a sufficient but not necessary schedulability test 6 presented in [START_REF] Davis | Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised[END_REF] as the framework to include aperiodic WAF into the schedulability analysis. However, the approach would remain similar with the sufficient and necessary test proposed in the aforementioned paper.

In the following, we re-use the concepts and notations from [START_REF] Davis | Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised[END_REF]. The worst-case response time of frame m is made up of several elements:

1. An upper bound on the queuing jitter J m , 2. The longest transmission time C m , 3. The waiting delay w m at the sending end, that is the longest time that the frame can wait before it starts being successfully transmitted (i.e., before it wins the arbitration on the CAN bus). This delay is given by equation 9,

The waiting delay w m includes the interference due to the aperiodic frames of higher priority than m, which is given by the function N α,M m (t) defined as follow:

N α,M m (t) = S α M (t). max j∈HpAf (m) C j ( 8
)
where M is the aperiodic interarrival model, α the chosen safety threshold, S α M (t) the corresponding aperiodic WAF and HpAf (m) is the set of aperiodic frames having higher priority than frame m. It has to be pointed out that the definition of N α,M m (t) makes the conservative assumptions that all aperiodic frames are of higher priority than m. How this can be improved is left for future work (see the discussion in the conclusion).

As classically done, the waiting delay w m can be determined with the following recurrence relation:

w n+1 m = N α,M m (w n m ) + max(B m , C m ) + ∑ ∀k∈hp(m) ⌈ w n m + J k + τ bit T k ⌉C k (9)
where hp(m)is the set of frames with priority higher than m, and max(B m , C m ) corresponds to the longest possible time for which an invocation of frame m can be blocked either by lower priority messages or due to the previous invocation of the same frame. The recurrence relation goes on

until J m + w n+1 m + C m > D m or w n+1 m = w n m .
In the former case, the frame is not schedulable while in the latter case the worst-case response time of the frame is given by:

R m = J m + w m + C m (10)

Case study

In this section, we illustrate the analysis on an typical 125Kbit/s automotive body network. To overcome the confidentiality issue that prevent us from giving the details of real sets of messages, we used Netcarbench [START_REF] Braun | NETCARBENCH: A benchmark for techniques and tools used in the design of automotive communication systems[END_REF], a GPL-licensed software that generates sets of messages according to parameters defined by the user (network load, number of ECUs, distribution of the periods of the frames, etc.). The Netcarbench input file used in this experiment is available upon request. The generated periodic message sets under study consists of 120 CAN frames with deadlines equal to periods and data payload ranging from 1 to 8 bytes. The total periodic load is equal to 41.4% while the aperiodic network load is set to 3% with aperiodic frames containing at most 7 bytes of data. The aperiodic WAFs corresponding to this experimental setup for two interarrival distributions and a safety threshold α equal to 10 -4 are shown in figure 7.

Figure 8 shows the worst-case response times of the highest priority periodic frames for the two aperiodic WAFs considered here and a safety threshold α equal to 10 -4 . The WCRT of the frames are computed with the software NETCAR-Analyzer from RealTime-at-Work whose purpose is to analyse the performances of CAN-based communication systems and optimize their design and configuration (e.g., choices for the message priorities and offsets, waiting queue policy and length, etc). Even in this context where the periodic load is moderate (41.4%) and the aperiodic traffic is limited (3%), one observes that aperiodic traffic rather significantly impacts the worst-case response times of the periodic frames. For instance, the WCRT for the frame with id 96 raises from 96.1ms without aperiodic traffic to 116.3ms with 3% aperiodic traffic obeying the Weibull law (+21%). Besides, we see from figure 8 that the exact model of the aperiodic traffic plays some role and thus cannot be overlooked.

Conclusion

In this paper, we develop a new approach for integrating the aperiodic traffic in response time analyses. The main interest of the proposal is that the overestimation of the aperiodic traffic is kept to the minimum that still enables the system to meet some chosen dependability requirements.

However, the resulting response time estimation can be pessimistic especially for high priority frames when there is a large volume of aperiodic traffic, as we have assumed that all aperiodic frames are of higher priority. It is possible to be less pessimistic by modelling each aperiodic stream individually (or consider several distinct groups of aperiodic streams) and integrate only the higher priority aperiodic WAFs into the schedulability analysis. However, we believe that this more finegrained approach will not be always practical since it requires significant modelling efforts and large quantity of data traces. We are working on a more global scheme that would still respect the safety threshold while being as accurate as possible (i.e., discard as much as possible of the lower priority Figure 8: Worst-case response times (WCRT) after inclusion of 3% of aperiodic traffic with different aperiodic frame interarrival models. The frames (x-axis) are sorted by decreasing priorities. The steep increase of the WCRT at time 50 and 100ms can be explained because, in that particular message set, there are several messages with periods equal to 50 and 100ms (resp. 4 and 13), and, at these points, new instances of these frames are causing additional delays. aperiodic traffic). Some of the results shown here hold under the assumption that the aperiodic interarrivals are independent and identically distributed (i.i.d.). In practice, this assumption can be easily tested using statistical tests such as the BDS test statistics but it is clear that it may not hold for all kinds of systems and workloads. It would be interesting to study, for instance by simulation, how departure from the i.i.d. property impacts the accuracy of the results. How non-i.i.d. streams can be handled is another follow-up to this study.

Figure 3 :

 3 Figure 3: Probability plots for 3 candidate distributions, from top to bottom, the exponential law, the log-normal law and the Weibull Law.

Figure 4 :

 4 Figure 4: Comparison between the captured data trace and a random trace generated by a Weibull model with MLE-fitted parameters.

Figure 5 7 )

 57 Figure5illustrates the computation of S(t) for a specific value of t, here t = 5:

Figure 5 :

 5 Figure 5: Graphical representation of algorithm for computation of S(5). It consists in finding the

Figure 6 :

 6 Figure 6: Aperiodic work arrival function up to time t = 125ms for various interarrival distributions.

Figure 7 :

 7 Figure 7: Aperiodic WAFs for inclusion in WCRT computations up to time 250ms. The y-axis starts from value 1.

Because of the incremental design process, in-house usages or constraints of the cooperation process between carmakers and suppliers, priorities on the CAN bus do not necessarily reflect the criticality of the frames (i.e., importance from a functional point of view, deadline constraint).

According to the principle of large deviations: the smaller the interval, the larger (in proportion) the deviation to the mean[START_REF] Navet | Probabilistic estimation of response times through large deviations[END_REF].

What was measured are the times at which the frames started to be transmitted and not the times at which the transmission requests were issued. Especially when the network is loaded, the two can be significantly different because of frames transmissions being delayed by higher priority frames. This could be taken into account by studying the busy periods on the bus and constructing a worst-case activation process. This is however outside the scope of the paper and will be addressed in future work. We would like to thank Reinder J. Bril for pointing this out.

The case of single parameter distribution such as the exponential law is trivial, a similar approach can be used for the log-normal law.

Central Limit Theorem tells us that the convergence rate is of order N 1/2 where N is the number of random draws, which means that adding one significant digit requires increasing N by a factor 100. The value of N should be set depending on the threshold α and accuracy objectives.

This test is applicable when deadlines do not exceed their periods.

Acknowledgements The authors would like to thank the anonymous reviewers and Reinder J. Bril (Eindhoven University of Technology) for their useful comments.