Keywords: Shallow Water equation, Saint-Venant system, analytic solutions, benchmarking, validation of numerical methods, steady-state flow, transitory flow, source terms

Numerous codes are being developed to solve Shallow Water equations. Because they are used in hydraulic and environmental studies, their capability to simulate properly flow dynamics is essential to guarantee infrastructure and human safety. Hence, validating these codes and the associated numerical methods is an important issue. Analytic solutions would be excellent benchmarks for these issues. However, analytic solutions to Shallow Water equations are rare. Moreover, they have been published on an individual basis over a period of more than five decades, making them scattered through the literature. In this paper, a significant number of analytic solutions to the Shallow Water equations is described in a unified formalism. They encompass a wide variety of flow conditions (supercritical, subcritical, shock …), in 1 or 2 space dimensions, with or without rain and soil friction, for transitory flow or steady state. An original feature is that the corresponding source codes are made freely available to the community (http://www.univorleans.fr/mapmo/soft/SWASHES), so that users of Shallow Water based models can easily find an adaptable benchmark library to validate their numerical methods.

e-mail : stephane.cordier@math.cnrs.fr

De nombreux codes sont en cours d'élaboration pour résoudre les équations de Saint-Venant. Parce qu'elles sont utilisées dans les études hydrauliques et environnementales, leur capacité à simuler correctement les flux en eau est indispensable afin de préserver les infrastuctures et la sécurité humaine. Par conséquent, la validation de ces codes et des méthodes numériques associées est un problème essentiel. Des solutions analytiques de référence constitueraient une excellente réponse à ces questions. Toutefois, les solutions analytiques aux équations de Saint-Venant sont rares.

Et surtout, elles ont été publiées sur une période de plus de cinquante ans, ce qui fait qu'elles sont dispersées à travers la littérature. Dans cet article, un nombre important de solutions analytiques aux équations de Saint-Venant est décrit dans un formalisme unifié. Elles englobent une grande variété de conditions d'écoulement (supercritique, sous-critique, choc...), en 1 ou 2 dimensions d'espace, avec ou sans frottement, pluie et topographie, pour des écoulements transitoires ou à l'état stationnaire. Une caractéristique originale est que les codes source correspondants sont mis gratuitement à disposition de la communauté (http://www.univ-orleans.fr/mapmo/soft/SWASHES), afin que les utilisateurs de modèles en eaux peu profondes puissent facilement trouver un banc d'essai adaptable pour valider leurs méthodes numériques

I INTRODUCTION

Nowadays, Shallow-Water equations are widely used to model flows in various contexts, such as: overland flow [START_REF] Esteves | Overland flow and infiltration modelling for small plots during unsteady rain: numerical results versus observed values[END_REF][START_REF] Tatard | Measurement and modelling of the high-resolution flow-velocity data under simulated rainfall on a low-slope sandy soil[END_REF], rivers [START_REF] Burguete | Implicit schemes with large time step for non-linear equations : application to river flow hydraulics[END_REF][START_REF] Goutal | A finite volume solver for 1D shallow-water equations applied to an actual river[END_REF], flooding [START_REF] Caleffi | Finite volume method for simulating extreme flood events in natural channels[END_REF][START_REF] Delestre | Simulation of rain-water overland-flow[END_REF], dam breaks [START_REF] Alcrudo | The Malpasset dam break case study[END_REF][START_REF] Valiani | -Malpasset dam-break simulation using a twodimensional finite volume method[END_REF], nearshore [START_REF] Borthwick | The shallow flow equations solved on adaptative quadtree grids[END_REF][START_REF] Marche | Theoretical and numerical study of shallow water models, applications to nearshore hydrodynamics[END_REF], tsunami [START_REF] George | Finite volume methods and adaptative refinement for tsunami propagation and inundation[END_REF][START_REF] Kim | Propagation and run-up of nearshore tsunamis with HLLC approximate Riemann solver[END_REF][START_REF] Popinet | Quadtree-adaptative tsunami modelling[END_REF]. This system of partial differential equations (PDE-s) proposed by Adhémar Barré de Saint-Venant in 1871 to model flows in a channel [START_REF] De Saint-Venant | Théorie du mouvement non-permanent des eaux, avec application aux crues des rivières et à l'introduction des marées dans leur lit[END_REF], consist in a system of conservation laws describing the evolution of the height and mean velocity of the fluid.

In real situations (realistic geometry, sharp spatial or temporal variations of the parameters), it is impossible to give an analytic formulae for the solutions of this system of PDE-s. Thus, there is a necessity to develop specific numerical schemes to compute approximate solutions for these PDE-s [START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF][START_REF] Leveque | Finite volume methods for hyperbolic problems[END_REF][START_REF] Toro | Riemann solvers and numerical methods for fluid dynamics[END_REF]. Implementation of such methods implies a subsequent step of code validation.

Validation of a model (that is the equations, the numerical methods and their implementation) is essential to know if it describes suitably the considered phenomena. At least three complementary kinds of numerical tests help us ensure that a numerical code is suitable for the considered system of equations. First, we can perform convergence or stability analysis (e.g. by refining the mesh). But this validates only the numerical method and its implementation. Second, approximate solutions can be compared with analytic solutions available for some simplified or specific cases. Finally, numerical results can be applied on experimental data, produced indoor or outdoor. This step should be done after the previous two; it is the most difficult one and must be validated by a specialist of the domain. In [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF], we have focused on the second approach.

In numerical codes validation, analytic solutions seem to be underused. We think that there are two possible reasons. First, each analytic solution has a limited scope in terms of flow conditions. Second, as they are dispersed through the literature, they are difficult to find. However, an important number of published analytic solutions allow to embrace a wide range of flow conditions. Thus, overall, the existing analytic solutions have a large potential for numerical codes validation. In literature, we can find benchmarks for hydraulic river modelling software [START_REF]Flood & Coastal Defence R&D Programme, Benchmarking Hydraulic River Modelling Software Packages[END_REF]. But they are too specific (weirs, pump, culverts... treatment validation) and there are too few tests available for numerical methods for Shallow-Water equations.

In [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF], we have tried to overcome these problems both by gathering a significant set of analytic solutions and by providing the corresponding source codes. [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF] describes the analytic solutions and gives some comments about their use and advantage. The source codes are freely available through the SWASHES (Shallow-Water Analytic Solutions for Hydraulic and Environmental Studies) library. With SWASHES software, we do not pretend to list all existing analytic solutions. Indeed, SWASHES is a framework to which users are invited to contribute by sending other analytic solutions together with the dedicated code.

The paper is organized as follows: in section II, we briefly present the notations we use and the main properties of Shallow-Water equations. In section III, we will focus on stationary solutions which are wellknown by the hydraulics community but much less by mathematicians, i.e. "backwater curves". Lastly, in section IV, we will present SWASHES and the interest of solutions described in [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF].

II EQUATIONS, NOTATIONS AND PROPERTIES

In the first section, we give the "complete" Shallow-Water system in two space dimensions, i.e. with topography, rain, infiltration, soil friction and viscous term. Then, we give this system in one space dimension and its main properties are recalled.

II.1 General settings

The Shallow-Water equations in two space dimensions take the following form:

∂ t h∂ x  hu∂ y hv =R-I ∂ t hu∂ x  hu 2  gh 2 2  ∂ y huv =gh  S Ox -S f x   S d x ∂ t  hv∂ x huv ∂ y  hu 2  gh 2 2  =gh  S O y -S f y   S d y , ( 1
)
where the unknowns of the model are the water height ( h t , x , y  [L]) and u t , x , y  , v t , x , y the horizontal components of the vertically averaged velocity [ L/T ] (Figure 1 a) and g =9.81 m/ s 2 is the gravity constant. The first equation is the mass conservation equation. The other two equations are the momentum conservation equations; they involve forces such as gravity and friction. We give now a short description of all the terms with their physical dimensions.

• z is the topography [ L] , since erosion is not considered here, it depends only on space, z  x , y , and S O x (resp. S O y ) is the opposite of the slope in the x (resp. y ) direction,

S O x =-∂ x z  x , y (resp. S O y =-∂ y z  x , y ); • R0 is the rain intensity [ L/T ] ,
it is a given function Rt , x , y 0 . In [START_REF] Delestre | A numerical scheme for a viscous shallow water model with friction[END_REF], it is considered uniform in space;

• I is the infiltration rate [ L/T ] . It is given by another model (such as Horton, Philip, Green- Ampt, Richards …) and is not taken into account in the following;

• S f =  S f x , S f y  is the friction force/law and may take various forms, depending on both soil and flow properties. In the formulae below, U is the velocity vector U =u , v  with |U|=u 2 v 2 and Q is the discharge Q= hu , hv . In hydrological models, two families of friction laws are encountered, based on empirical considerations. On one hand, we have the family of Manning-Strickler's friction laws

S f =C f U|U| h 4 /3 =C f Q|Q| h 10 /3
(2)

C f =n 2 , where n is the Manning's coefficient [ L -1/ 3 T ] .
On the other hand, the laws of Darcy-Weisbach's and Chézy's family write

S f =C f U|U| h =C f Q|Q| h 3 . ( 3
) With C f = f /8g , f a dimensionless coefficient, (resp. C f =1 /C 2 , C [ L 1 /2 /T ] ) we get
the Darcy-Weisbach's (resp. Chézy's) friction law. Notice that the friction may depend on the space variable, especially for large areas. In the following this will not be considered.

• finally,  S d =   S d x ,  S d y  is the viscous term with 0 the viscosity of the fluid

[ L 2 /T ] .

II.2 Properties

In this section, some properties of the Shallow-Water model are recalled. These properties are useful to the flow description. To simplify, we consider the one-dimensional model, but extensions to two dimensions are straightforward. The 2D Shallow-Water system (1) rewrites

∂ t h∂ x  hu=R-I ∂ t  hu∂ x  hu 2  gh 2 2  = gh  S O x -S f  ∂ x h ∂ x u . ( 4
)
The left-hand side of this system is the transport part of the model. It corresponds to the flow of an ideal fluid in a flat channel, without friction, rain or infiltration. It is in fact the model introduced by Saint-Venant in [START_REF] De Saint-Venant | Théorie du mouvement non-permanent des eaux, avec application aux crues des rivières et à l'introduction des marées dans leur lit[END_REF]. Several important properties of the flow are included in this model. The one-dimensional equations is rewritten using vectors form, in order to highlight these properties:

∂ t W ∂ x F W =0, where W =  h hu  , F W =  hu hu 2  gh 2 2  , (5)
with F W  the flux of the equation. With the following nonconservative form, where AW =F ' W  is the jacobian matrix or the matrix of transport coefficients:

∂ t W  AW  ∂ x W =0, with AW =F ' W =  u 1 u 2 gh 2u  , ( 6
)
the transport is more clearly evidenced. More precisely, when, the matrix turns out to be diagonalizable, with eigenvalues

 1 W =u- ghugh= 2 W  . (7)
In that case, the system is said to be strictly hyperbolic (see among others [START_REF] Godlewski | Numerical approximations of hyperbolic systems of conservation laws[END_REF]). The eigenvalues [START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF] are the velocities of surface waves on the fluid. For dry zones (i.e. if h=0 m ), the eigenvalues coincide. In that case, the system is no longer hyperbolic, and this induces difficulties at both theoretical and numerical levels, such as negative water depths... Designing numerical schemes that preserve positivity for h is very important in this context.

With these formulae, we recover a useful classification of flows. Indeed if |u| gh , the characteristic velocities (of the fluid u and of the waves  gh ) have opposite signs, and informations propagate upward as well as downward the flow. The flow is said to be subcritical or fluvial. In the other case, when |u| gh , the flow is supercritical, or torrential, all the informations go downwards. A transcritical regime exists when some parts of a flow are subcritical, other supercritical.

Since we have two unknowns h and u (or equivalently h and q=hu ), a subcritical flow is therefore determined by one upstream and one downstream value, whereas a supercritical flow is completely determined by the two upstream values. Thus for numerical simulations, we have to impose one variable for subcritical inflow/outflow. For supercritical inflow, we impose both variables and free boundary conditions are considered (see for example [START_REF] Bristeau | Boundary conditions for the shallow water equations solved by kinetic schemes[END_REF][START_REF] Cunge | Practical Aspects of Computational River Hydraulics[END_REF][START_REF] Novak | Hydraulic modelling -an Introduction[END_REF]).

Two quantities allow us to determine the type of flow. The first one is a dimensionless parameter called the Froude number

Fr= |u|  gh . ( 8
)
Its analogue in gas dynamics is the Mach number. If Fr1 (resp. Fr1 ), the flow is subcritical (resp. supercritical). The other essential quantity is the critical height h c which writes

h c =  q  g  2/ 3 , (9)
for a given discharge q=hu . It is a very readable criterion for criticality: the flow is subcritical (resp. supercritical) if hh c (resp. hh c ).

In presence of additional terms, we have to consider other properties, such as the occurrence of steady state (or equilibrium) solutions. In section III, we will focus on backwater curves which are specific steady state solutions.

III BACKWATER CURVES

By considering system (4) at steady state ( ∂ t h=∂ t u=∂ t q ) , without rain and diffusion ( R=0 and =0 ), it rewrites q=q 0

∂ x h= S 0 -S f 1-Fr 2 . ( 10
)
In hydraulics, equation ( 10) is used as a base for theoretical analysis of the water surface profiles obtained for different flow conditions in open channels [START_REF] Chaudhry | Open-Channel flow[END_REF][START_REF] Chow | Open-Channel hydraulics[END_REF][START_REF] Henderson | Open channel flow[END_REF]. It is called the gradually varied flow equation [START_REF] Chaudhry | Open-Channel flow[END_REF][START_REF] Chow | Open-Channel hydraulics[END_REF]. Water-surface profiles can be deduced theoretically and drawn qualitatively by studying the relative position of the profile ( h ) with respect to the critical-depth line ( h c ) and the normal-depth line ( h n , the height solution of equation S 0 -S f =0 ). We notice that the normal height h n depends on the slope S 0 while the critical height h c does not depend on S 0 . Bottom slopes are classified into five categories (designated by the first letter of the name

): mild M if h n h c , critical C if h n =h c , steep S if h n h c , horizontal H if S 0 =0 and adverse A if S 0 0
. Now, we have to designate the relative position of the free-surface. In the cases of the mild and steep slopes, the space above the topography is divided into three regions by the normal height and the critical height (Figure 1 b). For the adverse, horizontal and critical slopes there are only two regions. Because the normal height does not exist for the two first slopes and is the same as the critical one for the critical slope. The region between the lower line and the topography is designated as "zone 3", the region between the upper and lower lines is designated as "zone 2" and that above both lines is designated as "zone 1". Thus, we have 13 different types of water height profiles. This technique allows to make qualitative observations about various types of free-surface profiles. These observations allow to draw the profile without any detailed calculations. For example, we know if the water height increases or decreases with distance, how the profiles end at downstream and upstream limits... It is possible to put end to end several backwater curves to obtain a complete profile. In some cases, it is possible to generate this method to section average model (i.e. to take into account the shape of the cross-section).

For engineering applications, it is necessary to compute the flow conditions. But the gradually flow equation ( 10) is nonlinear, and the dependence on h is complicated, so analytical solution is not possible, so we have to use high order numerical methods [START_REF] Novak | Hydraulic modelling -an Introduction[END_REF]. We start the computations from downstream if the flow is subcritical and from upstream otherwise (see [START_REF] Chaudhry | Open-Channel flow[END_REF][START_REF] Chow | Open-Channel hydraulics[END_REF][START_REF] Henderson | Open channel flow[END_REF]). Some computer computer programs such as HEC-RAS are based on this method. In next section, we will describe SWASHES library.

IV ADVANCED ANALYTIC SOLUTIONS

The Shallow-Water Analytic Solutions for Hydraulic and Environmental Software (SWASHES) is freely available to the community through the SWASHES repository hosted at http://www.univorleans.fr/mapmo/soft/SWASHES. It is distributed under CeCILL-V2 (GPL-compatible) free software licence. When running the software, user must specify the choice of the solution as well as the number of cells for the discretization of the chosen analytic solution. The solution is calculated and is redirected in a gnuplot-compatible ASCII file. SWASHES is written in object-oriented ISO C++ that allows to easily implement a new solution.

We claim that SWASHES can be a useful tool for developers of Shallow-Water codes to evaluate the performances and properties of their own code. Indeed, SWASHES has been created because we have been developing a free software for the resolution of Shallow-Water equations, namely FullSWOF [START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF][START_REF] Delestre | FullSWOF: A software for overland flow simulation/FullSWOF : un logiciel pour la simulation du ruissellement[END_REF], and we wanted to validate it against analytic solutions. With SWASHES, a wide range of flow conditions are available as developed in the following subsection: steady state solutions and transitory solutions.

IV.1 Steady state solutions

In case of steady states ( ∂ t h=∂ t u=∂ t q=0 ), the one-dimensional Shallow-Water equations (4) reduce in the following system q= Rxq 0 11) System [START_REF] Chaudhry | Open-Channel flow[END_REF] enables to produce an infinity of analytic solutions. For these solutions, the strategy consists in choosing either a topography and getting the associated water height or a water height and deducing the associated topography. With the first approach, we can get for example the well-known solutions for flow over a bump [START_REF] Goutal | Proceedings of the 2 nd workshop on dam-break wave simulation[END_REF][START_REF] Houghton | Nonlinear shallow fluid flow over an isolated ridge[END_REF], the backwater curves (section III)... With the second approach, we get the MacDonald's solutions (which are section averaged) [START_REF] Macdonald | Analysis and computation of steady open channel flow[END_REF][START_REF] Macdonald | Analytic benchmark solutions for open-channel flows[END_REF] and all their one dimensional variants [START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF][START_REF] Delestre | A numerical scheme for a viscous shallow water model with friction[END_REF].

∂ x z = 1 gh  q 2 h 2 -gh  ∂ x h-S f h , q  gh ∂ x  h ∂ x q h  . (
Since [START_REF] Bermudez | Upwind methods for hyperbolic conservation laws with source terms[END_REF], it is well known that the topography source term treatment is a crucial point in preserving steady states. Thanks to the steady state solutions gathered in [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF], one can check if the steady state at rest and dynamic steady state solutions are satisfied by the considered schemes. These solutions, integrated in SWASHES, cover a wide variety of flow conditions (fluvial, torrential, transcritical, with shock…). Moreover, different source terms (topography, friction, rain and diffusion) are taken into account which allow to validate each source terms treatment.

IV.2 Transitory solutions

In previous subsection, we spoke about the steady-state solutions of SWASHES. These solutions can be used to check if the numerical methods are able to keep/catch steady-state flows. But even if the initial conditions differ from the expected steady-state, we do not have information about the transitory behaviour. Thus, transitory solutions are also included in SWASHES, such as the dam break solutions of increasing complexity [START_REF] Ritter | Die Fortpflanzug der Wasserwellen[END_REF][START_REF] Stoker | Water Waves: The Mathematical Theory with Applications[END_REF][START_REF] Dressler | Hydraulic resistance effect upon the dam-break functions[END_REF] , 1D and 2D Thacker's and variants solutions [START_REF] Thacker | Some exact solutions to the nonlinear shallow-water wave equations[END_REF][START_REF] Miles | On free-surface oscillations in a rotating paraboloid[END_REF][START_REF] Sampson | Moving boundary shallow water flow above parabolic bottom topography[END_REF]. These solutions allow to test moving wet/dry transitions, moving shock, moving wet/dry transitions with friction...

V CONCLUSIONS

We have developed SWASHES, a free tool for benchmarking in hydraulics. It is opened to user's contributions. We think that it might be useful for codes/numerical testing.

Figure 1 :

 1 Figure 1: Illustration of variables of (a) Shallow Water equations and (b) zones for classification of free surface profiles.

This study is part of ANR METHODE project ANR-07-BLAN-0232 granted by the French National Agency for Research. The authors wish to thank V. Caleffi and A.-C. Boulanger for their collaboration.


Olivier Delestre
email: delestre@unice.fr

Stéphane Cordier
email: stephane.cordier@math.cnrs.fr

Frédéric Darboux
email: frederic.darboux@orleans.inra.fr

Mingxuan Du
email: mingxuanism@gmail.com

Francois James
email: francois.james@math.cnrs.fr

Christian Laguerre
email: christian.laguerre@math.cnrs.fr

Carine Lucas
email: carine.lucas@univ-orleans.fr

Olivier Planchon

François James

FullSWOF: A software for overland flow simulation / FullSWOF : un logiciel pour la simulation du ruissellement

Keywords: Rainfall runoff, Shallow Water system, well-balanced scheme, hydrostatic reconstruction, finite volumes, dry/wet transition, Green-Ampt model

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Olivier PLANCHON

I INTRODUCTION

Rain on agricultural fields can yield to the occurrence of overland flow. At field scale, overland flow may have some undesirable effects such as soil erosion and pollutant transport. Downstream the watersheds, roads and houses may be damaged. Some control measures can be taken such as using grass strips. We have to know how the water is moving in order to put these developments. In overland flow prediction, several methods are used from black box models to physically based models. Two physical models are often used to model overland flow: Kinematic (KW) and Diffusive Wave (DW) equations [START_REF] Moussa | Approximation of the Saint-Venant equations for flood routing with overbank flow[END_REF][START_REF] Novak | Hydraulic modelling -an Introduction[END_REF]. But following [START_REF] Zhang | Modeling of two-dimensional overland flow[END_REF][START_REF] Esteves | Overland flow and infiltration modelling for small plots during unsteady rain: numerical results versus observed values[END_REF][START_REF] Fiedler | A numerical method for simulating discontinuous shallow flow over an infiltrating surface[END_REF], we choose to use the Shallow Water (de Saint Venant [START_REF] De Saint-Venant | Théorie du mouvement non-permanent des eaux, avec application aux crues des rivières et à l'introduction des marées dans leur lit[END_REF]) physical model. Indeed KW and DW models may give poor results in terms of water heights and velocities in case of mixed subcritical and supercritical flow. Inspite of computational time SW is mandatory. MacCormack scheme is widely used to solve SW equations [START_REF] Zhang | Modeling of two-dimensional overland flow[END_REF][START_REF] Esteves | Overland flow and infiltration modelling for small plots during unsteady rain: numerical results versus observed values[END_REF][START_REF] Fiedler | A numerical method for simulating discontinuous shallow flow over an infiltrating surface[END_REF]. But it neither guarantees the positivity of water depths at the wet/dry transitions, nor preserves steady states (not well-balanced [START_REF] Greenberg | A well-balanced scheme for the numerical processing of source terms in hyperbolic equation[END_REF]) as noticed in [START_REF] Rousseau | Overland flow modelling with Shallow Water Equation using a well balanced numerical scheme: Adding efficiency or just more complexity ?[END_REF]. In industrial codes (ISIS, Canoe, HEC-RAS, MIKE11...), SW equations are often solved under non-conservative form [START_REF] Novak | Hydraulic modelling -an Introduction[END_REF] with either Preissmann scheme or Abbott-Ionescu scheme. Thus transcritical flows and hydraulic jump are not solved properly. In order to cope with all these problems, we choose to use the hydrostatic reconstruction [START_REF] Audusse | A fast and stable wellbalanced scheme with hydrostatic reconstruction for shallow water flows[END_REF][START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF]. This positive preserving well-balanced finite volume scheme is integrated in FullSWOF_2D. In what follows, we present the physical model, then the numerical methods. In the end, FullSWOF_2D is applied on a real event measured in Thies by IRD [START_REF] Tatard | Measurement and modelling of high-resolution flow-velocity data under simulated rainfall on a low-slope sandy soil[END_REF].

II THE MODEL

II.1 The shallow water equations

As in [START_REF] Esteves | Overland flow and infiltration modelling for small plots during unsteady rain: numerical results versus observed values[END_REF][START_REF] Fiedler | A numerical method for simulating discontinuous shallow flow over an infiltrating surface[END_REF], we consider the 2D Shallow Water equations (SW2D) which write (see Figure 1 a)

∂ t h+∂ x hu ∂ y hv  =R-I ∂ t hu∂ x  hu 2 +gh 2 /2∂ y huv  =gh  S 0 x -S f x  ∂ t hv ∂ x huv ∂ y hv 2 +gh 2 /2 =gh  S 0 y -S f y  , ( 1
)
where the unknowns are the velocities u  x,y,t and v  x,y,t  [m/s] and the water height h  x,y,t  [m]. The subscript x (respectively y ) stands for the x-direction (resp. the y-direction): S 0 x =-∂ x z  x,y  and S 0 y =-∂ y z  x,y  are the ground slopes, S f x and S f y are friction terms. R  x,y,t  [m/s] is the rainfall intensity and I  x,y,t  [m/s] is the infiltration rate. As in [10], we use the Darcy-Weisbach friction law which writes:

S f x = f u u 2 v 2 8gh , S f y = f v u 2 v 2 8gh . ( 2
)

II.2 The Green-Ampt infiltration model

Infiltration is computed at each cell using a modified version of the Green-Ampt model [START_REF] Green | Studies on soil physics[END_REF][START_REF] Rousseau | Modélisation des écoulements à surface libre : étude du ruissellement des eaux de pluie[END_REF][START_REF] Esteves | Overland flow and infiltration modelling for small plots during unsteady rain: numerical results versus observed values[END_REF]. With this model, the movement of water in soil is assumed to be in the form of an advancing wetting front (located

at Z f n [m]
) that separates a zone still at the initial soil moisture θ s (see

I C n =K s  1 h f -h sur n Z f n  where Z f n = V inf n θ s -θ i , (3)
where h f is the wetting front capillary pressure head, K s the hydraulic conductivity at saturation, h sur n the water height and V inf n the infiltrated water volume. Thus we have the infiltration rate

I n = min h sur n ,  t.I C n   t , (4)
and the infiltrated volume

V inf n1 =V inf n  t.I n , ( 5
)
where  t is the time step. In the case of a two-layer soil, we consider a modification of this model (see [START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF][START_REF] Esteves | Overland flow and infiltration modelling for small plots during unsteady rain: numerical results versus observed values[END_REF]).

III THE NUMERICAL METHOD

The scheme will be presented in one dimension (SW1D)

∂ t h+∂ x hu =R-I ∂ t hu∂ x  hu 2 +gh 2 /2 =gh  S 0 x -S f x  , ( 6
)
it is integrated in FullSWOF_1D. The one dimensional version of FullSWOF has been developped for teaching, academical research and numerical development purposes. The extension of the 1D numerical method to SW2D on structured grid is straightforward and is integrated in FullSWOF_2D (Full Shallow-Water equations for Overland Flow). FullSWOF_2D is an object-oriented C++ code (free software and GPL-compatible license CeCILL-V2, source code available at http://www.univorleans.fr/mapmo/soft/FullSWOF/) developed in the framework of the project ANR METHODE (for details about the code see [START_REF] Delestre | Ecriture d'un code C++ pour la simulation en hydrologie[END_REF][START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF]). FullSWOF is structured in order to ease the implementation of new numerical methods and physical models. In what follows, we note the discharge q=hu [m²/s] and the vector of conservative variables U= h hu  t .

III.1 Convective step

A finite volume discretization of SW1D writes

U i * =U i n -  t  x [ F i1/ 2L n -F i-1 /2R n -Fc i n ] , (7)
with  x the space step and

F i1/ 2L n =F i1 /2 n S i1/ 2L n F i-1/ 2R n =F i-1 /2 n S i-1/ 2R n , (8)
the left (respectively right) modification of the numerical flux Fl for the homogeneous problem (see section

III.3) F i1/ 2 n =Fl U i1/ 2L n ,U i 1 / 2R n  . (9)
The values U i+1/2L and U i+1/2R are obtained thanks to two consecutive reconstructions. Firstly a MUSCL reconstruction [START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF][START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF] is performed on u , h and h+z in order to get a second order scheme in space. This gives us the reconstructed values  U -,z - and  U  ,z   . Secondly we apply the hydrostatic reconstruction [START_REF] Audusse | A fast and stable wellbalanced scheme with hydrostatic reconstruction for shallow water flows[END_REF][START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF] on the water height which allows us to get a positive preserving well-balanced scheme (in the sense it preserves at least steady state at rest)

h i1 /2L =max h i 1 / 2-z i 1/ 2--max z i1/ 2-, z i 1/ 2  ,0 U i1/ 2L =h i1/ 2L , h i1/ 2L u i 1 / 2- h i1/ 2R =max h i1/ 2  z i1 /2 -max  z i1 /2-, z i1/ 2 ,0 U i 1/ 2R =h i1 /2R , h i1 /2R u i 1/ 2  . ( 10
)
We introduce (11) and a centered source term is added to preserve consistency and well-balancing (see [START_REF] Audusse | A fast and stable wellbalanced scheme with hydrostatic reconstruction for shallow water flows[END_REF][START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF])

S i+1 /2L n =  0 g 2  h i+1 /2- 2 -h i+1 /2L 2   , S i-1/2R n =  0 g 2  h i-1/2 2 -h i-1/2R 2  
Sc i =  0 -g h i-1/ 2 +h i+1/2- 2  z i+ 1/2--z i-1/2   . (12)
We have to insist on the positivity and the robustness of this method. But, let us mention that such method requires some condition on the mesh size compared with mean water height (see [START_REF] Delestre | A limitation of the hydrostatic reconstruction technique for Shallow Water equations[END_REF]). The rain and the infiltration are treated explicitly (for details see [START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF]).

III.2 Friction treatment

In this step, the friction term is taken into account with the following system

∂ t U=  0 -ghS f  . ( 13
)
This system is solved thanks to a semi-implicit method (as in [START_REF] Bristeau | Boundary conditions for the shallow water equations solved by kinetic schemes[END_REF][START_REF] Fiedler | A numerical method for simulating discontinuous shallow flow over an infiltrating surface[END_REF])

h n 1 =h * q n1 = q * 1 t f 8 |q n | h n h n1 . ( 14
)
where h * , q * and u

U * =U n  t U n  U * * =U *  t U *  U n1 = U n U * * 2 , ( 15
)
where  is the right part of [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF].

III.3 Numerical flux

We use the HLL flux [START_REF] Bouchut | Nonlinear stability of finite volume methods for hyperbolic conservation laws, and well-balanced schemes for sources[END_REF][START_REF] Delestre | Simulation du ruissellement d'eau de pluie sur des surfaces agricoles[END_REF] which writes

Fl  U L ,U R  = F  U L  if 0 <c 1 c 2 F  U L  -c 1 F  U R  c 2 -c 1  c 1 c 2 c 2 -c 1  U R -U L  if c 1 0 <c 2 F  U R  if c 2 0 , ( 16
)
with two parameters c 1 <c 2 given by

c 1 = min U =U L ,U R  min j ∈{1,2}  j U  , c 2 = max U =U L , U R  max j ∈{1,2}  j U  , ( 17
)
where λ 1 U =u-gh and λ 2 U =u+ gh are the eigenvalues of SW1D. In practice, we use a CFL condition n CFL =0 .5 at second order and n CFL =1 at first order, with

 tn CFL  x max i∈〚1, J 〛 |u i |  gh i  , ( 18
)
where J is the number of space cells. At second order, variables  h i ,u i  in (18) are replaced by the reconstructed values h i 1 / 2-, u i1/ 2- and h i 1 / 2 , u i1/ 2  (detailed in next section).

III.4 MUSCL-reconstruction

We define the MUSCL reconstruction of a scalar function s∈ℝ [START_REF] Van Leer | Towards the ultimate conservative difference scheme. V. A seond-order sequel to Godunov's method[END_REF] by

s i-1/ 2 =s i -  x 2 Ds i , s i 1 / 2-=s i   x 2 Ds i , (19)
with the operator

Ds i =minmod  s i -s i-1  x , s i1 -s i  x  , (20)
and the minmod limiter

minmod  x,y = min  x,y  if x,y≥0 max  x,y  if x,y≤0 0 else . ( 21
)
As mentioned previously, the MUSCL reconstruction is performed on u , h and h+z then we deduce the reconstruction of z . In order to keep the discharge conservation, the reconstruction of the velocity has to be modified as what follows

u i-1/ 2 =u i - h i1/ 2- h i  x 2 Du i , u i 1 / 2-=u i  h i -1/ 2 h i  x 2 Du i . (22)

IV VALIDATION

FullSWOF_2D has already been validated on analytical solutions integrated in SWASHES (Shallow Water Analytic Solutions for Hydraulic and Environmental Studies) a free library of analytical solutions written in object-oriented ISO C++ [START_REF] Delestre | SWASHES: a compilation of Shallow Water Analytic Solutions for Hydraulic and Environmental Studies[END_REF][START_REF] Delestre | SWASHES: a library for benchmarking in hydraulics/SWASHES : Une bibliothèque de bancs d'essai en hydraulique[END_REF]. The purpose of this section is to confront FullSWOF_2D to a real system: the plot of Thies, Senegal [START_REF] Tatard | Measurement and modelling of high-resolution flow-velocity data under simulated rainfall on a low-slope sandy soil[END_REF]. The results presented below are the results preliminary to a more detailed study. They simply aim at illustrating the ability of FullSWOF_2D to simulate a dynamic runoff on real data without any preprocessing. Several experiments have been carried out to test the Salt Velocity Gauge [START_REF] Planchon | An automated salt-tracing gauge for flow-velocity measurement[END_REF] (a new measurement technique) and to study the dynamics of runoff and erosion. The set of measures considered consists of flow measurement at the outlet and the flow velocity measured at 63 locations in the plot. These data have been used to compare different computer codes: NCF and MAHLERAN (based on KW), RillGrow (based on DW) and PSEM_2D (based on SW2D with MacCormack scheme). The dataset is freely available at http://www.umr-lisah.fr/Thies_2004/. In the following, we have used the set of parameters obtained with PSEM_2D and we have observed the sensitivity to infiltration parameters. For all the simulations, we have used  x= y=0.1 m as space steps and f =0.26 as Darcy Weisbach friction coefficient. The average rain intensity was 70 mm /h during two hours. Infiltration parameters used with PSEM_2D [START_REF] Tatard | Measurement and modelling of high-resolution flow-velocity data under simulated rainfall on a low-slope sandy soil[END_REF] were h f =0.06 m ,  s - i =0.12 and K s =4.4e-6 m/ s . We tried this set of parameters. We notice that the simulated velocities with FullSWOF_2D are closed to those obtained with PSEM_2D (Figure 2 b). Small flow-velocities are well caught, excepted for the bigger values. In these cases, values are underestimated both by FullSWOF_2D and PSEM_2D. This means that the friction law is not adapted to do this simulation. Moreover we notice that the simulated hydrograph is under the measured one. Thus we have tried other values for  s - i and K s . We kept h f and  s - i (respectively K s ) values and we changed K s (resp.  s - i ). We notice that decreasing  s - i improves mainly the beginning of the hydrograph (Figure 3 a), while decreasing K s improves the entire hydrogram (Figure 3 b). We notice that the saturated hydraulic conductivity K s is the most influent parameter, as observed in [START_REF] Rousseau | A study of overland flow with uncertain infiltration using stochastic tools[END_REF] a study on the impact of this parameter on the surface runoff. Moreover, we have performed the simulation of this event on the integrated hydrological modelling system: MIKE SHE by DHI. This software is widely used for overland flow simulation, thus it might be used as a reference. In this software, the overland flow is calculated using a finite difference method using the diffusive wave approximation coupled with the one-dimensional Richards' equation [START_REF] Richards | Capillary conduction of liquids through porous mediums[END_REF] for the infiltration. Thus it is an approximation of the physical model included in FullSWOF_2D. We notice that FullSWOF_2D gives water heights very closed to those obtained with MIKE SHE (Figure 4). This work is still in progress, we will have to do more complete comparison between FullSWOF, measured data and other softwares.

IV.1 Experimental data

IV.2 Numerical results

V CONCLUSIONS

FullSWOF is a freely-available object oriented code designed to simulate overland flow on agricultural fields. This code is based on the Shallow Water system. The numerical difficulties such as dry/wet transitions and steady states are dealt with using up-to-date numerical methods. FullSWOF gave good results on real data. Nevertheless, the physical model has to be improved to catch more accurately the measured velocities.

VI ACKNOWLEGMENTS AND THANKS

This work was partially supported by ANR grant "METHODE"#ANR-07-BLAN-0232.

Figure 1 :

 1 Figure 1: Illustration of variables of (a) Shallow Water equations (SW2D) and (b) Green-Ampt infiltration model.

Figure 1 b

 1 ). At the moment t=t n , the infiltration capacity I C n [m/s] is calculated thanks to

Figure 2 :

 2 Figure 2: (a) The topography of the experimental plot and (b) comparison between measured and simulated velocities.

Figure 3 :

 3 Figure 3: Comparison between simulated hydrographs and measures (a) for several values of  s - i and (b) K s .

Figure 4 :

 4 Figure 4: Comparison between the water heights obtained with (a) FullSWOF_2D and (b) MIKE SHE.

  Institut de Recherche pour le Développement (IRD) Postal address: UMR LISAH, 2 Place Viala, 34060 Montpellier Cedex 1, France e-mail : olivier.planchon@gmail.com Le ruissellement sur les terres agricoles peut avoir des effets indésirables tels que l'érosion des sols, les inondations et le transport de polluants. Afin de mieux comprendre ce phénomène et d'en limiter les conséquences, nous avons développé un code à l'aide de méthodes numériques récentes : FullSWOF (Full Shallow Water equations for Overland Flow) un code orienté objet écrit en C++. Il est libre et peut être téléchargé à partir de http://www.univ-

orleans.fr/mapmo/soft/FullSWOF/. Le modèle est basé sur le système de Saint-Venant. Les difficultés numériques viennent des nombreuses transitions sec/mouillé et de la topographie très variable rencontrée sur le terrain. Le code intègre le ruissellement, les précipitations, l'infiltration (Green-Ampt modifié), la friction (les lois de Darcy-Weisbach et de Manning).

Nous présentons d'abord la méthode numérique pour la résolution des équations en eaux peu profondes integrée dans FullSWOF_2D (la version en deux dimensions). Cette méthode est basée sur le schéma de reconstruction hydrostatique, couplée à un traitement semi-implite du terme de friction. FullSWOF_2D a déjà été validé à l'aide des

* are the variables from the convective step. This method allows to preserve stability (under a classical CFL condition) and steady states at test. Finally, these two steps are combined in a second order TVD Runge Kutta method which is the Heun's predictor-corrector method. It writes


Adrien Delaye
email: adrien.delaye@irisa.fr-eric.anquetil@irisa.fr

Eric Anquetil

Learning of fuzzy spatial relations between handwritten patterns

It is widely admitted that modeling of spatial information is very important for interpretation and recognition of handwritten expressions. Two distinct tasks have to be addressed by spatial models in this context. Evaluation task consists in measuring the correspondence between the relationship of two objects and a predefined model of spatial relation. Localization task consists in retrieving objects that are related to a reference object according to a predefined model of spatial relation. In this work, we introduce a new modeling of relative spatial positioning that handles the two tasks under a unified framework and a training scheme for learning spatial models from data. The use of fuzzy mathematical morphology allows to deal with imprecision of positioning and to adapt to varying shapes of handwritten objects. Experimentations of the evaluation task over two datasets of online handwritten patterns prove that the proposed modeling outperforms commonly used relative positioning features.

Introduction

In many computer vision related tasks, spatial relationships between entities convey an important part of the information and should be modeled and processed with special attention. Interpretation of complex hand-drawn schemes involves the analysis of structured two-dimensional patterns where spatial relations between components provide useful information about the global meaning. For example, when dealing with handwritten mathematical equations, one has to analyze the relative positioning of isolated symbols in order to interpret the global meaning of the equation. In this specific case, a semantic (mathematical) operator such as exponent is only expressed by the superscript spatial relation between its two operands.

Structural representations are commonly used for description and analysis of complex expressions. Whether they rely on graphs, trees, grammars or other concepts, they involve description of spatial relations or connections between structural components. In this work, we are interested in the description and modeling of pairwise relations between components of handwritten structures, author but do not consider integration of spatial relation descriptions into higher-level structural representations.

While human beings are able to intuitively think of relative positioning with the help of concepts such as distance (far from, close to. . . ) or directions (on the left of, above. . . ), it is clear that these concepts are not precise by nature, and that they require a flexible modeling supporting reasoning under imprecision and dealing with ambiguity. Actually, applying soft computing concepts for modeling spatial relations is a widely accepted idea, and many methods have been proposed in this direction (see for example the books [START_REF] Matsakis | Applying soft computing in defining spatial relations[END_REF][START_REF]Methods for Handling Imperfect Spatial Information[END_REF]). In the context of hand-drawn patterns processing, it seems natural to make use of these concepts for handling objects that are by nature noisy, imprecise, and subject to a strong variability according to the numerous input conditions (writer identity, nature of the input material, environment, space and time. . . ). Whereas much research effort has been spent on modeling and recognition of isolated shapes [START_REF] Plamondon | Online and off-line handwriting recognition: a comprehensive survey[END_REF], most of spatial positioning models rely on ad hoc measures that do not precisely take into account variations in the shapes of objects and thus lead to poorly intuitive and informative descriptions.

In this work, we introduce a new formalization of spatial relation models based on fuzzy mathematical morphology operators. The original idea, formulated by Bloch in the context of MRI brain imaging [START_REF] Bloch | Fuzzy relative position between objects in image processing: a morphological approach[END_REF], provides a description of relative positioning that perfectly adapts to the variations in object shapes. In previous work, we highlighted the benefits of considering shape variations when describing relative positioning, in the context of handwritten recognition [START_REF] Bouteruche | Fuzzy relative positionning for on-line handwritten stroke analysis[END_REF]. The main contribution of this work is to introduce trainable models of spatial relations that can address the two important tasks related to spatial analysis of structured expressions, namely the evaluation task and the localization task [START_REF] Matsakis | A general approach to the fuzzy modeling of spatial relationships[END_REF]:

• Evaluation of a spatial relationship between two objects A and B consists in qualifying how well their relationship matches the spatial relation M (where M is a model of spatial relation either predefined from expert knowledge or estimated from data). For analysis of complex expressions, it gives an evaluation of spatial relations hypotheses and thus participates in the global interpretation.

• Localization consists in finding objects that best satisfy a predefined or trained spatial relation M with respect to a given reference object R. For expression analysis, it guides the structural parsing by retrieving objects conforming to the spatial relation model with respect to R.

To the best of our knowledge, no existing method combines a direct handling of these two tasks with an automatic training process to learn models from data. Relying on the framework of fuzzy mathematical morphology, we present here a unifying formalization for handling the two aforementioned tasks, and a training scheme for building models from data. Localization task is performed by application of the models on a reference object which results in a description directly defined in the image space. The evaluation of a spatial relationship between two objects can be performed by application of the same model. In addition to proposition of new modeling of spatial relations, we also focus in this work on the integration of distance information in this framework.

Second section reviews methods for relative positioning of objects, either in the context of handwriting recognition or in the more general domain of image processing. Principles of using fuzzy morphological operators for describing spatial relations are then detailed in section 3. Formalization of new models and associate learning process is presented in section 4, and integration of the distance into the positioning models is discussed in section 5. Finally, experimental results obtained in classification of handwritten objects are presented in section 6, followed by concluding remarks and directions for future works.

Related work

This section reviews methods for modeling spatial relations between objects. Note that general representations of complex structures are not investigated here, since we limit the scope of this review to models of pairwise spatial relations between structural components. Methods for spatial relation description can be used in different structural representations of complex handwritten expressions or, for instance, in segmentation graphs for image understanding. We first briefly review methods dedicated to modeling spatial relations between handwritten objects. Then we investigate methods proposed for modeling of spatial relations in the domain of image analysis.

We mainly restrict our review to methods that adopt a fuzzy modeling of relative positioning. Since the use of soft representations for spatial reasoning was suggested by Freeman more than thirty years ago [START_REF] Freeman | The modelling of spatial relations[END_REF], it has been widely applied and development of soft computing methods for spatial reasoning has still been a very active lead of research during the past decade [Blo99, MW99, Blo05, MWN10, MS02, JPPS10].

In the handwriting processing domain

Handwritten objects have several characteristics that make them worth distinguishing from general image objects. In general, handwritten objects are represented as strokes which are linear structures (i.e. that have no thickness), in opposition to areal objects dealt with in image processing domain. While much effort has been spent on precisely modeling the shapes of handwritten strokes, most models for describing their relative positioning rely on rather simple measures provided by ad hoc methods. Common approaches consist in summarizing each hand-drawn primitive by a single synthetic point (e.g. centroid based methods) or a virtual rectangle (minimum bounding rectangle or bounding box based methods) [START_REF] Marukatat | Handling spatial information in online handwriting recognition[END_REF][START_REF] Awal | Improving online handwritten mathematical expressions recognition with contextual modeling[END_REF], thus sacrificing the actual shape of objects. If it is admitted that when two objects are sufficiently far from each other their positioning can be summarized by the relative positioning of their centroids, this simplification practically never holds in the context of strokes within a handwritten expression. Likewise, the bounding box approximation is too coarse for objects that have complex shapes, including singularities, concavities, loops, all of which are common characteristics of handwritten patterns.

To deal with evaluation task, most methods proceed by extracting positioning features from a pair of objects and comparing their adequacy to spatial relation author models defined in the feature space (models can be trained from data, or predefined from expert knowledge). This scheme is commonly used and strongly benefits from statistical classification tools that provide very efficient automated model learning. However, models defined in a feature space distinct from image space cannot be directly used for spatial localization tasks, because features are extracted from pairs of objects (the two objects have to be available for feature extraction, whereas for localization task only the reference object is available).

For handling localization task, existing methods make use of regions empirically defined in the image space. For example, Zhang et al define around a symbol several rectangular regions corresponding to available spatial relations in mathematical expressions (such as superscript, subscript, below . . . ). Regions definitions are based on the bounding box of the reference symbol and their boundaries are parallel to the image axes. This approach is commonly used for mathematical expression analysis [ZBC02] [START_REF] Kim | Top-down search with bottom-up evidence for recognizing handwritten mathematical expressions[END_REF]. Fuzzy extension of region definitions can help handling imprecision of positioning, but it does not improve the adaptability to varying object shapes which remains minimal because of the bounding box approximation [START_REF] Zhang | Using fuzzy logic to analyze superscript and subscript relations in handwritten mathematical expressions[END_REF]. More importantly, several thresholds have to be manually set for constructing the models and no scheme is proposed for automatically building models from samples of the spatial relations, hence a lack of genericity.

In general, positioning methods for handwritten objects are dedicated to very specific domains (e.g. mathematical expressions, Latin characters, Asian characters, . . . ). The bounding box approximation is widely used, and no generic method was proposed that takes into account the actual shapes of handwritten strokes for defining more precisely their relative positioning. On one hand, methods for evaluating spatial relations properly handle variability by training statistical models in a feature space, but are not suited to locate objects. On the other hand, solutions proposed for localization are empirical, require manual definition of spatial regions, and have trouble capturing the variability of spatial positioning.

In the image processing domain

In the domain of image analysis, much more researches were conducted with the aim of defining generic methods for modeling relative positioning of objects. A review of fuzzy-based methods for defining spatial relations in images was proposed by Bloch [START_REF] Bloch | Fuzzy spatial relationships for image processing and interpretation: a review[END_REF]. Among these methods the ones that take into consideration the shapes of the objects involved in the relation, rather than operating a centroid based or box based approximations, are of much interest.

Several approaches provide a rich description of relative positioning by implicitly taking into account the shapes of the objects: they consider all the points from the two objects at hand for describing their spatial relation. This is the case for methods based on histogram of angles (compatibility method), or for the aggregation method [START_REF] Bloch | Fuzzy spatial relationships for image processing and interpretation: a review[END_REF]. The F-histogram method also takes into account object shapes by aggregating positioning relations over longitudinal sections of the objects, and is computationally efficient in comparison with direct computation of histogram of angles [START_REF] Matsakis | A new way to represent the relative position between areal objects[END_REF]. The quality of descriptors extracted by histogram of angles or F-histogram was validated in several applicative contexts. Besides evaluation of spatial relations between objects, F-histograms have also been used for generating linguistic description of relations [START_REF] Bondugula | Force histograms and neural networks for human-based spatial relationship generalization[END_REF], or for retrieving similar spatial relationships among images [START_REF] Matsakis | Understanding the spatial organization of image regions by means of force histograms: a guided tour[END_REF]. However, directly exploiting them for localization task is impossible, because their definition is based on features extracted from a pair of objects.

The authors of F-histogram more recently introduced another representation of spatial relations, dual to F-histogram, called F-template [START_REF] Wang | Fuzzy object localization based on directional (and distance) information[END_REF]. An Ftemplate is a spatial template defined relatively to a reference object, describing for each point of the plane its adequacy to a given spatial relation with respect to the reference. For instance, an F-template can describe the relation to be in direction α from R, where R is a reference object. A F-template is a type of model that can be used for localization of objects, since it is directly defined in the image space [START_REF] Matsakis | A general approach to the fuzzy modeling of spatial relationships[END_REF] and only requires a reference object. The duality of Fhistograms and F-templates concepts has not been fully investigated yet, and no direct transformation is possible from one to the other, but these works constitute an interesting step toward unified models for evaluation and localization tasks.

A similar concept of spatial template has been investigated for about ten years in the works of Bloch. The original idea, formulated separately by Bloch [START_REF] Bloch | Fuzzy relative position between objects in image processing: a morphological approach[END_REF] and Gader [START_REF] Gader | Fuzzy spatial relations based on fuzzy morphology[END_REF] is to describe spatial relations with the help of morphological operations processed in the image space, directly over the reference object. Specifically, fuzzy functions that model predefined spatial relations are applied with the help of morphological operators (mainly dilatation) to build a spatial template (called fuzzy landscape in their terminology). Obtained spatial template is a fuzzy function describing the goodness of a spatial relation with respect to the reference, for any point of the space.

F-templates and morphological fuzzy templates both take into account the shape of the reference object in the description of the spatial relations. Objects shapes are even explicitly considered in the morphological method, and Bloch has shown that the resulting description better fit the intuition in comparison to other positioning descriptions based on histograms [START_REF] Bloch | Directional relative position between objects in image processing: a comparison between fuzzy approaches[END_REF]. F-templates and morphological approach provide two different ways to build spatial templates, and Matsakis pointed out the equivalence of the two definitions under some conditions [START_REF] Matsakis | A general approach to the fuzzy modeling of spatial relationships[END_REF]. Spatial templates effectively handle the localization task, since they are defined directly in the image space and only require the definition of one reference object. However, in the two cases, only predefined spatial relations can be represented (such as on the left, above, close to), and no method was proposed to automatically train such models from data.

In the context of handwriting expression processing, spatial relations are not easy to describe or to model from prior expert knowledge. The need of generic spatial relation models with respect to different types of expressions and objects calls for an automatic training procedure. Moreover, automated learning of spatial relations would be beneficial for better capturing the variability and imprecision of relative positioning of objects.

The main contribution of our work is to propose a new formalization and an associated procedure for learning models of spatial relations from training data. The result of training is an abstraction of the spatial relation (for example superscript). When applied to a given reference object, the model results in a spatial template of the relation in the image space that can be used for localization task. When a pair of objects is available, the learned model can be used for author evaluation of their positioning. The proposed approach is built upon the fuzzy morphological method, because it is flexible and perfectly suited to deal with ambiguous spatial relations. Morphological foundation is also precious for building spatial relation models that can handle a large variability in the shapes of the objects and perfectly adapt to their individual specificities. In the next section, we present the idea of using fuzzy mathematical morphology for describing of relative positioning and then introduce the new proposed modeling in section 4.

Relative positioning description with fuzzy mathematical morphology

We first present the general approach as introduced in [Blo99] for describing relative positions of objects. Although the method was designed to deal with fuzzy objects in images and can be extended to the 3D case, we only present here the concepts required for our target application: space is reduced to the plane, and we only consider crisp linear objects.

A spatial relation is modeled as a fuzzy set describing the adequacy of any point of the plane to the relation at hand relatively to a reference object. Such type of relation can be based on directional information (for example on the right of R, where R is the reference object) or distance information (far from R). The use of fuzzy models is natural, since these concepts cannot be described in a crisp, all-or-nothing fashion.

In the sequel, a fuzzy set describing a spatial relation in the plane is referred to as a fuzzy landscape, according to the vocabulary defined in [START_REF] Bloch | Fuzzy relative position between objects in image processing: a morphological approach[END_REF]. This concept matches the notion of spatial template referred to by Matsakis et. al [START_REF] Matsakis | A general approach to the fuzzy modeling of spatial relationships[END_REF]. Intuitively, a fuzzy landscape can be seen as a map (think of a distance map, or a direction map) which associates to every point of the plane a degree of truth with respect to the relation described, and the chosen reference object. An example of fuzzy landscape describing the spatial relation on the right of an object R is presented in figure 1(b). In this figure, fuzzy membership values from 0 to 1 are represented by levels of gray from black to white (this convention will be kept for representing fuzzy landscapes throughout this paper). Object R is a primitive extracted from a handwritten Chinese character. Since Chinese characters are complex structured patterns, they present a rich set of examples of spatial relations. We choose to illustrate all the concepts and functions presented in this paper with objects taken from handwritten Chinese characters.

Evaluation of a positioning relation for a given object A with respect to the reference R involves two steps: first step consists in defining the fuzzy landscape by operating a morphological operation over the reference object R, and second step consists in evaluating the adequacy of object A with the fuzzy landscape.

Fuzzy landscape definition

First step consists in applying a predefined model of spatial relation, for example on the right of, to the reference object of interest, say R, in order to model the applied relation on the right of R. This is done by applying a morphological dilatation of the reference object with a structuring element (SE) modeling the Brightness reflects membership to the fuzzy functions, from 0 (black) to 1 (white).

relation. For a given reference object R, located in the plane S, the dilatation of R with the SE ν is computed by:

µ R (p) = max q∈R ν(p -q), ∀p ∈ S (1)
(where p and q are points of the plane S, with q belonging to the object R).

The resulting function µ R is the fuzzy landscape, and it describes for each point of the plane its adequacy degree to the relation described with respect to R, illustrating the applied relation. Its definition explicitly takes into account the shape of the reference object R. Note that compared to application in the image domain, the computation of (1) is much facilitated when dealing with linear objects, since R has significantly less points. Dealing with on-line signal (i.e. when the handwritten strokes are described as a temporal sequences of sampled points) is even faster, as the handling of linear sections is straightforward and computationally efficient, as shown in [START_REF] Bouteruche | Fuzzy relative positionning for on-line handwritten stroke analysis[END_REF]. In this case, the computational effort for evaluating µ R at a point p is linear with the number of sampled points in the reference object.

The principle of equation ( 1) is to look for the point of R that best supports the relation held by ν for the point p. Consequently, a point will be considered to be perfectly on the right of R if p is perfectly on the right of any part of R. As a result, one point p can be at the same time perfectly on the right of (some part of) R and perfectly on the left of (some other part of) R. What can be seen as a loss of information (in comparison to methods like histograms of angles where all pairs of points from the two objects are used for describing their relationship) actually permits to get a precise knowledge about the shape of R by considering several directions. For example, a point p located inside the concavity of a Cshaped reference object is simultaneously perfectly above, under and on the right of R. This idea of combining several points of view for building rich descriptions of relative positioning is at the core of the models introduced in the following section.

Structuring element definition

The shape and the fuzziness of SE ν define the spatial relation and the softness of the description provided by the fuzzy landscape (resulting from equation (1)). As author an example, the following definition can be adopted for the fuzzy SE modeling the spatial relation in direction α [Blo99]:

ν α (p) = max 0, 1 - 2 π arccos - → op. -→ u α || - → op|| , ∀p ∈ S ( 2
)
where o is the center of the SE and u α is the unit vector of direction α. SE fuzzy membership function ν assigns to each point p of the plane a degree from 0 to 1, varying linearly with the angle between -→ op and u α . Figure 1 Alternatively, an undirected fuzzy radial SE can be defined for modeling a distance relation (e.g. close to). Figures 1(c) and 1(d) present an example of distance based SE and resulting fuzzy landscape for an object R. Different definitions of structuring elements were proposed in [START_REF] Cinbis | Relative position-based spatial relationships using mathematical morphology[END_REF], where the authors introduce several parameters controlling the flexibility of the radial and directional dimensions to provide a customized family of hybrid distance-direction fuzzy structuring elements.

Evaluation of the relationship

Once the fuzzy landscape is defined for a spatial relation (either based on directional, distance-based, or hybrid structuring elements), it can be used for evaluating the positioning of an object A. Several operators are available for aggregating membership degrees of points of A to the fuzzy landscape so as to obtain a global evaluation. Mean measure simply computes an average adequacy degree (3), while possibility (4) and necessity (5) respectively provide optimistic and pessimistic measures that define an evaluation interval according to the fuzzy pattern matching theory [START_REF] Bloch | Fuzzy relative position between objects in image processing: a morphological approach[END_REF]:

M R (A) = 1 |A| p∈A µ R (p) (3) Π R (A) = sup p∈A µ R (p) (4) N R (A) = inf p∈A µ R (p) (5)
As an illustration, table 1 gives the three degrees measured for the object A embedded in the 4 directional fuzzy landscapes depicted in figure 2. For example, according to direction α = 0, the mean score of 0.87 shows that object A is mostly on the right of R. The two other measures reflect the fact that at least one point of A is perfectly on the right of R in the sense of the fuzzy landscape (hence possibility is equal to one), while at least one point of A is not really on the right of R (hence necessity is 0.6). Because they only rely on one point, measures of necessity and possibility are quite sensitive to outliers, but they provide complementary information about the distribution of degrees reached by points of A. Table 1 Evaluation of the relations Is A in direction α from R ? (for objects of figure 2)

Measure α = 0 α = π 2 α = π α = 3 π 2 M R (A) 0.87 0.05 0.03 0.93 Π R (A) 1 0.2 0.15 1 N R (A) 0.6 0 0 0.77

Learning unifying positioning models

As exposed in the previous section, use of mathematical morphology permits to take into account the actual reference object when defining the fuzzy landscape, so that spatial relation description naturally adapts to the peculiarities of its shape. The fuzzy landscape is suitable to a human-like description of spatial relations and fits the intuition very well, including when the reference object has singularities, concavities. . . Moreover, thanks to its fuzzy definition, it deals well with the imprecise relative positioning of handwritten patterns and the spatial relationship evaluation can be integrated in a general soft computing framework for making recognition decision. Finally, since a fuzzy landscape is a spatial template (i.e. a model of spatial relation that can be represented in the image space), it can be used for addressing the localization task. The several evaluation measures presented offer different strategies for evaluating the matching of a spatial relationship between two objects with respect to a predefined model. Nevertheless, this method only describes predefined linguistic spatial relations (e.g. on the right of, close to). In previous works, we have used combination of several linguistic fuzzy landscapes to evaluate how well the relationship between objects fits with different directional spatial relations. Evaluation results were shown to constitute a powerful set of features for classification of spatial relations between handwritten strokes [START_REF] Bouteruche | Fuzzy relative positionning for on-line handwritten stroke analysis[END_REF].

Our objective is to further exploit the fuzzy morphological framework by automatically learning abstract modeling of spatial relations that will provide learned fuzzy landscapes when applied to a reference object. This modeling allows to cope with both localization and evaluation tasks: Learning of the spatial model should not require any prior knowledge on the spatial relation, such as preferred directions or distance. It should also handle large variety of spatial relations, including different topological situations, with intersecting objects as well as surrounding and inclusion situations.

In this section, we present a method for automatically learning from samples spatial relation models by relying on fuzzy morphology operators. We propose to examine the spatial relation under 4 different points of view (the 4 cardinal directions). For each of them, a partial model can be determined, applicable as a modified fuzzy landscape for describing the area admitted by the model considering this point of view. Global model is ultimately constructed by fuzzy intersection of modified fuzzy landscapes obtained according to the several points of view. Introduction of distance information in the model will be investigated in a dedicated section (section 5).

Partial directional model

From several training instances of objects (R i , A i ) i=1.N that share the same spatial relation to be modeled, we learn a partial model of their positioning according to each of the 4 adopted points of view, oriented by up, down, left and right directions. For a point of view related to direction α, we consider the distribution of the degrees reached by the training points from objects A i with respect to the directional fuzzy landscape built relatively to their associated reference objects R i . We simply approximate this distribution by a histogram function H α , normalized by the maximum frequency. For k = 0..K and (i k ) k=0..K in [0, 1] such that i k = k/K, each histogram section (H α ) k accounts for the number of points from the training samples that reach a degree falling in [i k , i k+1 [ in the fuzzy landscape µ Ri α :

(H α ) k = i=1..N |S i k | where S i k = {p ∈ A i , µ Ri α (p) ∈ [i k , i k+1 [} (6)
After a simple normalization so as to set the maximal histogram value to 1, (H α ) is a function from [0, 1] to [0, 1] approximating the distribution of degrees reached by training points with respect to the relation carried by α. H can be interpreted as a model of to what extent A i objects are in direction α with respect to R i objects in the training set. Figure 3(a) presents a histogram modeling the distribution of degrees reached by points of objects similar to the (R, A) pair of figure 2, considering the direction on the right of.

Exploitation of model H α consists in functional composition of the linguistic directional fuzzy landscape with the function H α :

μR α = (H α • µ R α ) (7)
The result of composition is a modified fuzzy landscape μR α , interpretable as a spatial model of the relation to be located with respect to R according to the model, under the point of view α.

Fusion by fuzzy intersection

The process described in the previous part is repeated for each considered point of view, i.e. for the 4 directions up, down, left, right. When given a new reference object, the four models are exploited separately, resulting in four distinct learned fuzzy landscapes forming sub-parts of a global spatial model. This global model is then constructed by intersecting the fuzzy landscapes obtained by considering each point of view:

μR inter = t[μ R up , μR down , μR lef t , μR right ] ( 8
)
where t is a t-norm fuzzy operator, implementing a conjunction operation. Intuitively, a point p is considered as properly positioned with respect to the model if it fits with the learned landscape according to every point of view. Figure 4 illustrates the fuzzy landscapes obtained for the 4 points of view (a, b, c, d), with the same objects as before. In each case, the white area describes the admitted region according to the model under the considered point of view. The two fuzzy landscapes obtained for points of view up (a) and down (b) are partly redundant. Information extracted from the up point of view is that A should be not above R, while information from the down point of view is that A should be below R. These two points of view actually complement each other, and the fuzzy landscape from the up point of view is not completely included (in the fuzzy inclusion sense) in the one from down point of view. It is then beneficial A global model defined by (H up , H down , H lef t , H right ) is an abstraction of a non-linguistic spatial relation. Given a new reference object R, application of the model results in a fuzzy landscape that is adapted to the shape of the reference. As in the case of predefined spatial relations, representing learned relations with fuzzy landscapes unifies the needs for localization and evaluation task. This learned fuzzy landscape can directly be used for localization task, since it exhibits the area of the plane where argument objects should be looked for. A second exploitation level assesses the matching of the relationship between A and R with respect to modeled spatial relation. Evaluation of the matching of A with the fuzzy landscape defined on R can be seen as an evaluation of the proposition the relative positioning of R and A matches the learned spatial relation model.

Integration of distance information

The models presented in the previous section only involve directional positioning information. The combination of several points of view (i.e. consideration of several directional relations) provides a rich positioning description because different parts of the reference object support the different directional relations. It is however natural to investigate the contribution of distance information for improving the description quality. In this section, we consider two methods for embedding information about the distance between objects in the models. First method is the most straightforward: it simply consists in considering the distance as an additional point of view on the spatial relation. Alternative method associates a distinct distance model to each considered direction. The two methods will be compared in the experimental section (see section 6).

Global distance integration

The most straightforward way to model distance information within our framework is to make use of distance-based fuzzy structuring elements, and to consider the distance as an additional point of view in our model. We propose to define a fuzzy distance-based structuring element as follows:

ν τ (p) = β τ (|| - → op||) with β τ (t) = max 0, 1 - t τ (9)
(for any point p of the plane). o denotes the center of the structuring element, and β is a decreasing function from R to [0, 1], that has a null value when t > τ . It actually defines a model of the spatial relation close to. A distance fuzzy landscape µ dist is obtained by dilatation of a reference object R by the distance structuring element. In order to adapt the distance relation to the size of the reference object, author the scaling factor τ is set proportionally to the length of the diagonal of the bounding box of R. The distance fuzzy landscape is defined as

µ R dist (p) = max q∈R ν τ R (p -q), ∀p ∈ S (10)
The model can be defined and trained just as explained before.

Direction-wise distance integration

Another method for embedding distance information in the models is to consider different distance models depending on the directions.

(∆ α ) k = {µ R dist (p), p ∈ S i k , i = 1..N } S i k = {p ∈ S, µ Ri α (p) ∈ [i k , i k+1 [}
where i indexes a pair (R i , A i ) of training samples, and µ R dist is a distance fuzzy landscape defined as exposed in the previous paragraph. (∆ α ) k is approximated by a fuzzy set (δ α ) k defined with a trapezoidal membership function with parameters a, b, c and d, where a and d are respectively the minimum and maximum values from (∆ α ) k , and b and c are respectively the values of the first and third quartile of (∆ α ) k . All the (δ α ) k , k = 1..K constitute a family of trapezoidal fuzzy sets, that can be integrated in the definition of the new learned fuzzy landscape regarding the direction α.

μR α,d (p) = t[(H α k • µ R α ) direction (p), (δ α k • µ R τ R ) distance (p)] ∀p ∈ S s.t. µ R α ∈ [i k , i k+1 [ ( 11
)
where t is a t-norm fuzzy conjunction operator. A point p fits with the learned landscape μR α,d if it fits with the directional information carried by H α k • µ R α and the related distance model carried by δ α k • µ R τ R . Figure 7(a) gives an illustration of the resulting learned fuzzy landscape for the object R. This figure is to be compared with figure 3(b), where no distance model information was included. Integration of distance models as described for point of view right is repeated for each considered direction, and the four fuzzy landscapes can be intersected just as in equation ( 8). 6 Application to the recognition of handwritten gestures

In order to evaluate the quality of positioning description provided by the models presented in this work, we set up an experiment aiming at recognizing handwritten objects.

Experimental datasets

Experiments were conducted on two distinct datasets of online handwritten gestures.

The first database (IME-OnDB) consists of a set of 5,525 handwritten records, collected from a handwritten input method on a pen-enabled PDA. 15 different writers participated in the collect. Each record is a pair of handwritten objects: a reference (it is one letter from the Latin alphabet), and an associated argument gesture. A gesture can be a punctuation mark, a diacritical, or a predefined In the sequel, we will refer to this dataset as HCC-OnDB.

Experiment design

Writer-independent cross-validation scheme are defined (each fold corresponding to the data from one writer), and recognition rate for each set of features is averaged from a 15-fold cross validation. In the HCC-OnDB database, 15 folds are formed, each fold corresponding to the data from 4 writers, and the same writer-independent cross-validation process is applied to evaluate the average recognition rates.

Classifier parameters

The SVM classifiers have a Gaussian kernel, and their two parameters are optimized independently for each fold of each experiment by a grid search based on a random 10-fold cross validation over the training set. Cost parameter C ranges in 10 -1 , .., 10 4 , and γ parameter ranges in 10 -4 , .., 10 1 .

Feature sets

Different sets of spatial positioning features are utilized for recognizing objects. Two baseline sets are defined for comparing our method to commonly used positioning features. Feature set b is based on bounding box measures (such as horizontal and vertical distances between top, bottom, left and right boundaries of the bounding boxes of the two objects and distance between their center point).

We compute histograms of angles between the objects and quantize angles into 18 bins, providing 18 features for baseline feature set c. Features sets d and e evaluate the power of direct morphological directional and distance description. Mean adequacy degrees are evaluated in the four main directions by application of equation (3), constituting the four features of set d. A mean adequacy measure of distance is added in feature set e.

Finally, the three sets of features f, g, and h are composed of mean adequacy degrees computed for each of the N models learned by the method proposed in this paper, where N is the number of classes in each database (N = 18 for IME-OnDB, and 17 for HCC-OnDB). In other words, these feature sets result from the evaluation of positioning of the two objects in a pair sample calculated with respect to each learned model. Purely directional models are used for feature set f, global distance is incorporated for feature set g, and direction-wise distance modeling is integrated for feature set h. All the models are built with 8 bins histograms (K = 8, see paragraph 4.1). The t-norms used in models exploitation are the product t-norm for both landscapes intersection (see equation ( 8)) and combination of distance and direction in hybrid models (see equation ( 11)).

Results and discussion

Table 3 presents the different features sets and the recognition rates obtained on the two different datasets, average from 15-fold writer-independent crossvalidation. Associate table 4 presents the statistical significance of pairwise feature sets comparison. We evaluated 5% level statistical significance by one-tailed paired student t-test over the 30 experiments conducted with each feature set (15 folds on each database). Justification for this statistical test is that the k-folds are writerindependent, and thus the standard deviation between folds is not meaningful. We consider the k-folds as different datasets (even if most of the training set is common between them). As shown in table 4, we test the hypothesis that each feature set author 3), and validate its significance if the 5% level is validated by the t-test. For instance, the fourth line of the table shows that d is significantly a better feature set than a and b, whereas no such conclusion can be drawn from its comparison with c. Experiment a, where no positioning features are included in the description, confirms the need for a modeling of the relative positioning for recognizing classes in both datasets. Recognizing an editing gesture without description of its position only allows recognition of about half of the samples. In experiment b, a simple bounding boxes based spatial description is included, leading to a significantly increased recognition rate. Histogram of angles (feature set c) performs better than bounding box based features.

Experiments d and e confirm that the morphological description framework provides powerful features for spatial positioning (as we had already observed in [START_REF] Bouteruche | Fuzzy relative positionning for on-line handwritten stroke analysis[END_REF]), performing at least as good as histograms of angles, and significantly better than the two baseline approaches when a distance measure is included (feature set e).

Performance of models described in this paper appears in experiments f, g and h. First, feature set f performs significantly better than d, meaning that learning of models allows a better description of positioning compared to direct morphological author consider the actual shapes of objects in describing their relative positioning. Secondly, the models are not restricted to evaluation of spatial relations, but can also handle localization task, in the sense that they can exhibit the region of the plane where the relation holds to a certain degree. Thirdly, the models can be automatically trained from data, allowing to capture the variability of spatial relationships between training objects. These three properties make the models eligible for dealing with handwritten objects for expression recognition and the experiments prove the superiority of spatial description in comparison to baseline approaches. Generalization capacity of our models was demonstrated by experimenting over different types of handwritten objects: editing gestures and accentuation marks on Latin characters, and strokes extracted from Chinese characters. We highlighted the benefit of distance integration into the models for the task of classifying handwritten objects. Future work directions include the exploitation of localization ability for assisting the segmentation task in structural processing of more complex handwritten patterns such as Chinese characters, or mathematical expressions.

Figure 1

 1 Figure 1 Structuring Elements for spatial relation on the right of (a), and close to (c), and resulting fuzzy landscapes around a reference object R (b, d).Brightness reflects membership to the fuzzy functions, from 0 (black) to 1 (white).

  (a) shows a SE for the relation on the right of defined according to equation (2) with α = 0, and figure 1(b) illustrates the fuzzy landscape obtained by dilatation of a reference object with this SE, according to equation (1).

Figure 2

 2 Figure 2 Is A in direction α from R? (reference object R is in red, argument objectA is in blue)

  1. given a reference object and this spatial model, in what area of the plane should the argument object be located? (localization by definition of the learned fuzzy landscape) author 2. given two objects, to what extent does their spatial relationship fit with the model? (evaluation by matching of the argument object with the learned fuzzy landscape)

  For example, figure 3(b) shows a learned fuzzy landscape representing the spatial relation between objects R and A from figure 2 according to the point of view right. It assigns to each point of the plane its adequacy degree with the learned relation according to this direction and can be interpreted as to be conformely to the model "on the right of R". In other words, the brighter points are those for which the validity of relation to be on the right of R is the most conform to the degrees reached by the training objects. The white area could be used to localize objects, i.e. to predict where it is expected to find an object positioned relatively to this given reference object, according to the model learned and the considered point of view (right).

( a )Figure 3

 a3 Figure 3 Histogram model (a) and resulting learned fuzzy landscape (b) for point of view right, with training objects similar to the (R, A) pair from figure 2

  author to intersect these two landscapes for building a more accurate global model. The same reasoning holds for left and right points of view (c, d). Eventually, the global model computed by intersection is represented in figure 4(e). This global landscape μR inter describes the area of the plane that satisfies the positioning relation with respect to R according to the complete model.

Figure 4

 4 Figure 4 Exploitation of a spatial relation model trained from objects such as the (R, A) pair of figure 2. Partial learned fuzzy landscapes are obtained from the 4 points of view up (a), down (b), left (c) and right (d). Each point of view provides a different information regarding the admitted location of an object with respect to the reference R. The global landscape (e), obtained by intersection of partial models, is a spatial representation of adequacy to the learned spatial relation model.

Figures 5

 5 Figures 5(a) to 5(d) present different fuzzy landscapes obtained by application of the same spatial relation model to several reference objects. Figures 5(e) to 5(h) show the matching of associated argument objects to the fuzzy landscapes and corresponding mean evaluation measures.

Figure 5

 5 Figure 5 Application of a learned spatial relation model to different pairs of objects. Fuzzy landscapes adapted to the reference objects (a)-(d) and associated argument objects (e)-(h) with corresponding mean adequacy scores.

  Figure 6(a) shows the learned fuzzy landscape μR dist obtained for distance point of view. It gives a global representation of acceptable regions of the plane in terms of distance to the reference object, according to the training data. Distance is modeled globally, without considering differences with respect to the directions from R. Exploitation of the global model now involves the additional distance fuzzy landscape in the fuzzy conjunction for combining points of view (see equation 8). Result of the intersection of the 5 points of view (4 directions + 1 distance) is given in figure 6(b), and it can be compared with figure 4(e) (where no distance was included).

Figure 6 A

 6 Figure 6 A fuzzy landscape for distance modeling can be seen as an additional point of view on the relation (a). The result of the global model, obtained by intersection the 5 points of view is presented in (b).

  Figure 7(b) illustrates the intersection result, to be compared with the one obtained in figures 4(e) (without distance) and 6(b) (with global distance integration).

Figure 7

 7 Figure 7 Learned fuzzy landscape with embedded distance for right point of view, and result of application of a full model with embedded distances (b).

author Table 2

 2 Visualization of 16 selected classes from IME-OnDBdatabase (a) and 16 classes from HCC-OnDB database (b).

  (a) Classes of gestures included in IME-OnDB (b) Classes of strokes spatial relations in HCC-OnDBhandwritten gesture for triggering an edition command in the input method (character deletion, case switch, space. . . ). The argument is positioned with respect to the reference according to spatial relations that can be seen as examples of spatial relations classes, just like the superscript example cited above. The dataset is available from the IMADOC research group website a , and is presented in more details in[START_REF] Bouteruche | Description et exploitation du contexte spatial pour l'interprtation de tracs manuscrits : application l'interprtation de gestes graphiques dans les mthodes de saisie de texte[END_REF]. Table8(a) illustrates classes of gestures included in the database. Since examples from different gesture classes can have a similar shape (e.g. comma and acute accent), modeling their positioning with respect to the reference letter is necessary for a satisfactory recognition. The second dataset is an excerpt from an on-line handwritten Chinese characters database collected and provided by CASIA laboratory (Chinese Academy of Sciences, Institute of Automation). Original database contains thousands of classes of characters written by 60 different people. More details about this dataset are given in the works of Ma and Liu about Chinese character recognition [ML08]. For our experiment, we defined 17 classes of pairs of strokes extracted from simple characters. For each class, we isolated about 120 samples (2 per writer), were a sample is a pair of objects, one labeled as the reference and the other being the argument. Reference objects are made of one or two strokes, while the arguments are always a single stroke or a substroke. Table 8(b) illustrates examples of classes retained in our dataset (reference strokes are in red, argument strokes are in blue).

  b to h is actually better than less performant feature sets (according to the average recognition rates from table

  It is expected that a more accurate modeling of the distance can be reached by incorporating a distinct model into each considered point of view. The idea is then to learn a distance-based fuzzy set for each histogram bar in the models introduced in section 4. Formally, if (H α ) k denotes the k-th bar of the histogram model for directional point of view α, associated distance model (δ α ) k should approximate the distribution of distance degrees reached by point of S i k

Table 3

 3 Experiment results. Recognition rates are average on k-fold validation (k=14) for each database

		features	% ( IME) % ( HCC)
	a	(no positioning features)	55.35	66.30
	b	9 bounding box based features	96.18	91.03
	c	18 features angle histogram	96.38	93.09
	d	4 directional morphological features	96.47	93.09
	e 4 directional + 1 distance morphological features	96.67	94.12
	f	N learned models (no distance)	96.72	94.12
	g	N learned models (global distance)	96.72	94.44
	h	N learned models (direction wise distance)	96.79	94.85

Table 4

 4 Statistical significance calculated with pairwise t-test at a 5% level, taking into account results from the two datasets. A checkmark in line x and column y indicates that feature set x is signicatively more performant than y for recognition task.

Acknowledgments

This paper is a revised and expanded version of a paper entitled Learning spatial relationships in hand-drawn patterns using fuzzy mathematical morphology presented at the second international conference on Soft Computing for Pattern Recognition (SoCPaR), held in Cergy-Pontoise (France) on 7-10 of December, 2010.

The authors are grateful to Professor Cheng-Lin Liu from Chinese Academy of Sciences for providing them the HCC-OnDB database used in the experiments.

description. It also performs better than the two baselines approaches. Likewise, learning models with embedded distance (h) significantly improves the recognition in comparison with direct morphological features with distance (e). However, no significant difference is noted between the global and direction wise distance integration (g and h). Actually, a closer look at the results reveals that distance integration only have a small impact on the IME-OnDB database. This is not surprising since the most confusing classes are the different types of accents (acute, grave, circumflex, and the accent deletion gesture) that differ not by their distance to the reference, but by their intrinsic shape. If we limit our statistical significance test to the HCC-OnDB database, it appears that embedded distance is significantly better than global distance integration at a 5% level. In general, the integration of embedded distance significantly outperforms purely directional models (comparison between h and f ).

Facing with two distinct datasets confirms to some extent the genericity of our modeling approach. Expressivity in terms of spatial relations ranges from remote, disconnected objects (most of the classes from IME-OnDB) to more intricate relations such as character deletion class from IME-OnDB, several intersecting cases in HCC-OnDB, or a surrounding relation in the case of case switch class in IME-OnDB. Objects of different graphical complexity are properly handled by the models (substroke, single stroke or multi stroke objects). Table 5 presents visualization of spatial templates learned (with embedded distance) for 16 classes from IME-OnDB. Models adaptivity to varying reference shapes should be emphasized, especially for classes from IME-OnDB. Most classes from this database involve very different references shapes. For example, samples from apostrophe class admit c,d,j,l,m,n,s,t as reference letters. The apostrophe positioning model is then trained and exploited with very different reference letters, and the visual representation given in table 5 shows its good behavior.

Conclusion

In this paper we introduced a new general formalization for the modeling of spatial relations, with the novelty of addressing three major concerns of spatial positioning methods. First, thanks to their fuzzy morphological foundations, the models