Jean-Marc Conrat
email: jeanmarc.conrat@orange-ftgroup.com

Patrice Pajusco
email: patrice.pajusco@orange-ftgroup.com

Typical MIMO propagation channels in urban macrocells at 2 GHz

A directional wideband measurement campaign was performed in urban macrocells at 2 GHz using a channel sounder and a 8-sensor linear antenna array at the base station. Directions of arrival at the Base Station (BS) were estimated by beamforming using the antenna array. Directions of arrival at the Mobile Station (MS) were estimated by beamforming using parts of the measurement route. Global parameters (delay spread, azimuth spread at BS, maximum factor and street canyon factor) were processed from the Azimuth-Delay Power Profiles (ADPP) at BS and MS. In this paper, we compare the statistics of these four parameters with the statistics of those simulated by the 3GPP-SCM system-level model and the statistics of those reported in the literature. We find an acceptable agreement between our measurements and the SCM model except for the delay spread and the street canyon factor. The azimuth spread at BS mean value (9.5°) and delay spread mean value (0.250 µs) are also in accordance with values reported in other references. Azimuth spreads are ranged from 7° to 11°, and delay spreads are ranged from 0.1 µs to 1 µs. From a statistical analysis of global parameters, we show that most of the measured propagation channels can be classified in three main categories: low spatial diversity at MS and BS, high spatial diversity at MS and BS, low spatial diversity at BS and high spatial diversity at MS.

I. INTRODUCTION

Multiple antenna radio access (MIMO) based on antenna arrays at both the Mobile Station (MS) and the Base Station (BS) has recently emerged as a key technology in wireless communication, increasing the data rates and system performance [START_REF] Gesbert | From theory to practice: an overview of MIMO space-time coded wireless systems[END_REF][START_REF] Goldsmith | Capacity limits of MIMO channels[END_REF]. This technique exploits both the spatial and polarization diversities of multipath channels in rich scattering environments. The benefits of multiple antenna technologies can be shown by achieving link-level or system-level simulations. Both studies require a realistic MIMO propagation channel model.

There are two principal MIMO propagation channel types [START_REF] Yu | Models for MIMO propagation channels: a review[END_REF][START_REF] Molisch | Effect of far scatterer clusters in MIMO outdoor channel models[END_REF]: physical and non-physical models. Nonphysical models are based on the statistical description of the channel using non-physical parameters, such as the signal correlation between the different antenna elements at the receiver and transmitter [START_REF] Kermoal | A stochastic MIMO radio channel model with experimental validation[END_REF][START_REF] Pedersen | A stochastic multiple-input-multiple-output radio channel model for evaluation of space-time coding algorithms[END_REF]. In contrast, physical models provide either the location and electromagnetic properties of scatterers or the physical description of rays. A ray is described by its delay, Direction of Arrival (DoA), Direction of Departure (DoD) and polarization matrix. Geometrical models [START_REF] Correia | Mobile Broadband Multimedia Networks: Techniques, Models and tools for 4G[END_REF][START_REF] Ertel | Overview of spatial channel models for antenna array communication systems[END_REF][START_REF] Hofstetter | A twin-cluster MIMO channel Model[END_REF], directional tap models [START_REF]Spatial channel model for Multiple Input Multiple Output (MIMO) simulations[END_REF][START_REF] Hao | A generalized space-time multiple-input multiple-output (MIMO) channel model[END_REF] or ray tracing [START_REF] Agelet | Efficient Ray-Tracing Acceleration Techniques for Radio Propagation Modeling[END_REF][START_REF] Fugen | Verification of 3D Ray-tracing with Non-Directional and Directional Measurements in Urban Macrocellular Environments[END_REF] are examples of physical models. Both approaches have advantages and disadvantages but physical models seem to be more suitable for MIMO applications because they are independent of the antenna array configuration [START_REF] Jensen | A review of antennas and propagation for MIMO wireless communications[END_REF][START_REF] Steinbauer | The doubledirectional radio channel[END_REF]. Furthermore, they inherently preserve the joint properties of the propagation channel in temporal, spatial and frequential domains. By taking into account antenna diagrams, Doppler spectrum or correlation matrices can be coherently deduced from a physical model.

For outdoor wide area scenarios, the most commonly used physical MIMO propagation channel is the 3GPP/3GPP2 SCM model [START_REF] Gpp | Spatial Channel model for MIMO Simulations[END_REF]. In the SCM system-level model, most parameters are defined by their probability density functions. This randomized approach gives a very realistic description of the propagation channel in the sense that it provides a very large variety of channels. However, the use of a randomized model in link-level simulations implies a great number of simulations in order to comply with the probability density function of randomized parameters. In the case of accurate link-level simulation, it leads to an enormous simulation time. More recently, the 3GPP have defined new models based on tapped delay-line models with fixed values for angular parameters or correlation matrices. These models simplify link-level simulations and reduce the amount of simulation time but on the other hand, the great variability of MIMO propagation channels is not taken into account. For instance, [START_REF] Gpp | Physical layer aspects for evolved Universal Terrestrial Radio Access (UTRA)[END_REF] defines only two profiles in urban macrocell environment.

The scope of this paper is to investigate an intermediate modeling approach between the full randomized approach and the single profile approach. The basic idea is to define a limited number of channels with fixed values for power, delays and angular parameters, and for each channel to give a percentage of occurrences. The definition of these channels is performed in four steps: 1-Measurement campaign and physical parameter estimation. (part 2) 2-Global parameter processing: global parameters are an extension of the traditional synthetic parameters used in wideband analysis. They represent all possible metrics that characterize the propagation channel, for example the delay spread, the azimuth spread, the number of paths, the Rice factor, etc. A similar concept can be found in the SCM model that defines the azimuth spread, delay spread and shadowing factor as "bulk parameters". Part 3 describes the different global parameters that were used, gives their Probability Density Function (PDF) and compares them to the PDF given by the SCM model when possible. 3-Group detection (part 4): during this step, measured channels fall into groups, where the global parameters of channels in the same group are similar and the global parameters of channels in different groups are dissimilar. In the field of statistics, this is called clustering analysis. In this paper, we prefer to use the term group instead of cluster to avoid the confusion with the cluster defined in geometrical models. 4-Typical case selection: A typical case for a given channels group corresponds to a measured channel whose global parameters are close to the median global parameters of the given channels group. A typical case is then considered as a model and the physical parameters estimated in step 1 can be used in link-level or system-level simulation. [START_REF] Conrat | A Versatile Propagation Channel Simulator for MIMO Link Level Simulation[END_REF] describes a channel simulator that processes the impulse response (or impulse responses matrix in the case of MIMO simulation) from the physical parameters of a set of rays.

Finally to complete the typical case analysis and the statistical analysis of global parameters, part 5 comments on the correlation between the global parameters.

II. MEASUREMENT CAMPAIGN AND DATA PROCESSING

The measurement scenario emulated an up-link, the transmitter of a propagation channel sounder being the mobile and the receiver the base station (fig. 1). The carrier frequency was 2.2 GHz and the analyzed bandwidth 10 MHz. A standard vertical dipole antenna was used at the transmitter and was located on the roof of a car. An antenna array made up of 10 vertical sectorial sensors regularly spaced (5 cm = 0.36 λ) was used at BS. The array antenna was set up on the rooftop of 3 buildings and oriented in 3 directions for each building. One snapshot was a simultaneous measurement of 10 complex impulse responses (CIRs). A measurement route consisted of 600 snapshots triggered in time. The mobile terminal vehicle was driven at a predetermined speed such that the snapshots were collected each λ/3. The measurement was conducted in urban and dense urban macrocells. The main difference between the two environments is the building height. In urban macrocells (Mulhouse, east of France), the average height is approximately 20 meters, in dense urban macrocells (Paris), the average height is approximately 30 meters. Further details about the measurement setup and the previous propagation analysis can be found in [START_REF] Laspougeas | Radio propagation in urban small cells environment at 2 GHz: experimental spatio-temporal characterization and spatial wideband channel model[END_REF][START_REF] Laspougeas | Spatial radio channel model for UMTS in urban small cells area[END_REF][START_REF] Conrat | Clusterization of the MIMO Propagation Channel in urban macrocells at 2 GHz[END_REF].

The measurement route was divided into sections containing 50 snapshots and consecutive sections were shifted by the section size. A section defines a virtual linear antenna array at the mobile and can be considered as a 10*50 MIMO measurement point. A total amount of 804 MIMO points was selected for this study. The distance BS-MS (Dist) ranges between 0 m and 750 m (fig. 3). The mobile azimuth (MS-Azi) is roughly uniformly distributed between 0° and 90° (fig. 4). MS-azi is the difference between the mobile motion azimuth and the BS-MS azimuth. It ranges between 0° and 90 °. 0° indicates a car trajectory parallel to the line BS-MS. 90° indicates a car trajectory perpendicular to the line BS-MS. Azimuth Power Delay Profile (ADPP) at BS and MS were estimated by a Bartlett beamforming method. Such an approach is fast and very convenient for analyzing a large collection of data. Examples of space-time diagrams are given in figures 14-19. Rays with a zero BS-azimuth are in the perpendicular direction to the BS antenna array. Rays with an MS-azimuth equal to -180° or 0° are in the direction of the car motion, 0° being the front direction, -180° being the back direction. The vertical dark line indicates the BS-MS direction.

Linear antenna array (10 sensors)

From an extended visual inspection of ADPP MS (τ,φ) and ADPP BS (τ,φ), some preliminary conclusions can be drawn: The propagation channel is clustered at BS and MS, i.e. ADPP MS (τ,φ) and ADPP BS (τ,φ) show local areas centered around an azimuth and a delay where the power is concentrated. Delays, azimuths and powers of clusters were estimated by local maximum detection on ADPP BS (τ,φ) and ADPP MS (τ,φ). Due to the limited angular and temporal resolution of the estimation method, the intra-cluster characteristics were not investigated in this paper. A more detailed description of this method can be found in [START_REF] Conrat | Clusterization of the MIMO Propagation Channel in urban macrocells at 2 GHz[END_REF]. We define a mobile cluster (MS-cluster) as a local maximum of ADPP MS (τ,φ) and note P MS-cluster (i) and φ MS-cluster (i) the power and azimuth of the ith MScluster.

A significant drawback of the data processing is the conical ambiguity for the MS-DoA estimation. If we assume that rays arrive at the mobile in a horizontal plane, we cannot distinguish the right and left parts of ADPP MS (τ,φ). The right and left sides are defined compared with the mobile direction. Such an analysis can not properly characterize MS-DoAs but it is simple and provides valuable information on particular phenomena at MS. For instance, it can be used to evaluate the street canyon or dominant path effects. The street canyon effect corresponds to the situation where the received power is concentrated in the street axis. The dominant path effect corresponds to the situation where the ADPP MS (τ,φ) is dominated by a single MS-cluster.

III. STATISTICAL ANALYSIS

A. Definition of global parameters

In this section, we present the global parameters that were used to identify typical/atypical measurement files. Global parameters were processed from delays, azimuths and powers estimated in the previous section. The key idea in the global parameters definition was to quantify the frequential diversity, the spatial diversity at BS and spatial diversity at MS. We also tried to limit the number of global parameters in order to optimize the group detection analysis. For instance, we did not keep global parameters that were redundant.

The first two global parameters are the traditional azimuth spread at BS (AS), and delay spread (DS) that characterize the spatial diversity at BS and the frequential diversity. At MS, no azimuth spread can be processed due to the conical ambiguity in the azimuth estimation. Two alternative parameters that represent as realistically as possible the spatial diversity at MS were defined. The first one is the maximum factor (MaxF) defined by ( 1):

( ) ( ) ( ) ( ) ∑ - - = i cluster MS Cluster MS i i P i P MaxF max (1)
A maximum factor close to 0 tends to indicate a uniform distribution of the power around the mobile and thus a high potential spatial selectivity at MS. A maximum factor close to one indicates a quasi-LoS situation and thus a low potential spatial diversity at MS. The second one is the street canyon factor (ScF) defined by [START_REF] Goldsmith | Capacity limits of MIMO channels[END_REF]. The street canyon area is defined by figure 2. -

C. Literature review

In this paragraph, the global parameter values are compared with values reported in previous references. Table 1 sums up MISO, SIMO or MIMO measurement campaigns in urban environment that present a statistical analysis of the delay spread and azimuth spread at BS. Table 1 also contains the elevation spread at BS or MS or azimuth spread at MS when these parameters could be extracted from the measurement data. There is an acceptable agreement between our results and those listed in table 1. Nevertheless, the dispersion of the delay spread values is somewhat unexpected. It is perhaps due to the large variety of urban environments including different averaged building heights, street widths, etc. We note that there are still very few available results on the spatial properties of the propagation channel at the mobile.

Regarding ScF and MaxF, the comparison is not straightforward. Firstly, there are few references that have investigated the street canyon effect [START_REF] Kuchar | Directional macrocell channel characterization from urban measurements[END_REF][START_REF] Laurila | Wideband 3D characterization of mobile radio channels in urban environment[END_REF][START_REF] Vuokko | Analysis of propagation mechanisms based on direction-of-arrival measurements in urban environments at 2 GHz frequency range[END_REF][START_REF] Kalliola | 3-D double-directional radio channel characterization for urban macrocellular applications[END_REF] or the dominant path effect [START_REF] Toeltsch | Statistical characterization of urban spatial radio channels[END_REF] and secondly, the definition of metrics used to characterize these two propagation mechanisms are different from those given in section III-A. For example: - [START_REF] Vuokko | Analysis of propagation mechanisms based on direction-of-arrival measurements in urban environments at 2 GHz frequency range[END_REF] defines the street canyon area as being the area where the elevation at the mobile is lower than 10°. In urban macrocell environments, ScF is ranged between 30% and 40%. - [START_REF] Toeltsch | Statistical characterization of urban spatial radio channels[END_REF] analyses the DoAs at BS. Space-time power diagrams are compared with geographical maps by visual inspection and clusters are classified into three main classes: street-guided propagation, propagation over rooftops and scattering from high rise objects. A cluster is defined as a group of paths which have similar azimuth, elevation and delay values. [START_REF] Toeltsch | Statistical characterization of urban spatial radio channels[END_REF] indicates that the power of clusters belonging to the class "street canyon" is generally higher than 80 % of the total received power. [START_REF] Toeltsch | Statistical characterization of urban spatial radio channels[END_REF] also shows that, in 90 % of cases, 55% of the total received power is concentrated in the strongest cluster. In our measurement, 55% of the power is concentrated in the strongest cluster in only 25

% of the cases. The differences between [START_REF] Toeltsch | Statistical characterization of urban spatial radio channels[END_REF] and our results could be explained by the definition of the cluster concept: a cluster according to the definition of [START_REF] Toeltsch | Statistical characterization of urban spatial radio channels[END_REF] may gather one or several clusters according to our definition (local maxima of ADPP MS (τ,φ)).

Location R&D institutions Bandwidth Frequency DS (µs) BS-AS (°) BS-ES (°) MS-AS (°) MS-ES (°)

Ref. To identify the different groups, a hybrid method combining hand-made filtering and K-means algorithm was used. The K-means method partitions the MIMO points into K mutually exclusive groups, such that MIMO points within each group are as close to each other as possible, and as far from MIMO points in other groups as possible. The hand-made filtering was applied to extract atypical groups and the K-means algorithm was applied to identify typical groups. The K-means algorithm gave the best results when the number of groups were equal to three and when the global parameters used in the partitioning were DS, AS and MaxF normalized to their standard deviation.

Paris Mulhouse

France

The partitioning proposed in this paper is a little arbitrary and alternative partitioning schemes may be found. Furthermore, the percentage of occurrences depends strongly on the measurement locations. For instance, if Dist was limited to 200 m, the atypical group HighDS would be mutated into a typical group. Nevertheless, the selected groups give a general and realistic overview of the various propagation channels experienced by the mobile in a macrocell environment. The global parameter statistics of the typical and atypical groups are summarized in table 2. Group HighDS (fig. 17): This group gathers MIMO points with a delay spread higher than 0.4 µs. In most cases, the impulse response is divided into two discontinuous parts. The second part generally occurs at an excess delay higher than 2 µs. Group HighAS (fig. 18): This group is more representative for a microcell environment than a macrocell environment (higher AS, lower DS). The power angular dispersion at BS created by scatterer objects in the vicinity of the BS is intensified by the short MS-DS distance (Dist median value =32m). Group LowAS (fig. 19): This group was obtained by filtering measurements with MS-Azi smaller than 10°. In this case, we obtain a group of MIMO points with very low AS, and very large MaxF and ScF. It physically corresponds to scenarios where the street canyon and dominant path effects dominate the propagation conditions. Group Typical1 (fig. 14): The vast majority of channels of this group have characteristics similar to those extracted from LOS measurements (low spatial diversity, low frequential diversity) even if there is no BS-MS visibility. Group Typical2 (fig. 15): This group differs from Group Typical1 with a median value of MaxF equal to 0.3 which indicates a relatively higher diversity at MS. Group Typical3 (fig. 16): The features of group Typical3 indicate a relatively high frequential diversity and a relatively high spatial diversity at BS and MS. For groups Typical2 and Typical3, the street canyon effect is no more dominant as it was for group Typical1. The partitioning of MIMO points could be refined by dividing both groups into two sub-groups, one with a high street canyon effect and one with an almost uniform distribution of the MS-clusters around the mobile.

V. PARAMETER CORRELATION DISCUSSION

In this section we introduce the correlation between the different global parameters. In order to continue the comparison with the SCM model we added a new global parameter: the shadowing factor (SF). The shadowing factor is defined by (3):

Pe Pr Ploss dB SF - + = ) ( (3)
with Pe: transmitted power Pr: received wideband power averaged on 15 λ Ploss: linear regression of the measured path loss

The path loss linear regression was processed on an extended set of measurement data (3000 instead of 804) (fig. 12). The histogram of SF is plotted in fig. 13. The standard deviation of SF is equal to 5.7 and is slightly lower than the standard deviation in the SCM urban macrocell model (8 dB). 2 sums up the global parameter correlation coefficients. The top right part contains correlation coefficients that were processed for all groups (typical and atypical). The bottom left part contains correlation coefficients that were only processed on the typical groups. The most significant difference concerns the correlation between AS and DS (0.21 with all groups, 0.6 with typical groups). This difference highlights the impact of the selected set of measurement data. A reduction of only 20 % of the total amount of data can significantly modify the correlation. It can partially explain divergent results found in the literature about the AS/DS correlation [START_REF] Laspougeas | Radio propagation in urban small cells environment at 2 GHz: experimental spatio-temporal characterization and spatial wideband channel model[END_REF][START_REF] Nilsson | Measurements of the spatio-temporal polarization characteristics of a radio channel at 1800 MHz[END_REF][START_REF] Pedersen | A stochastic model of the temporal and azimuthal dispersion seen at the base station in outdoor propagation environments[END_REF][START_REF] Algans | Experimental analysis of the joint statistical properties of azimuth spread, delay spread, and shadow fading[END_REF]. Global parameters are slightly correlated with Dist or MS-Azi. The most correlated parameter with the distance is AS (-0.37). The correlation ScF/MS-Azi confirms the trend pointed out in groups Typical1 and LowAS: the street canyon effect is emphasized when MS-Azi decreases. Finally, the correlations DS/AS, DS/SF, AS/SF calculated on typical groups are close to those given by the SCM urban macro model. (AS/DS=0. In this paper, we have presented a method to create link-level propagation channel models from measurement data. This method was applied to measurements in macrocell environments at 2 GHz and we show that in 80 % of cases, the large variety of propagation channels could be represented by 3 typical files. Due to the conical ambiguity of the angle estimation method, the selected propagation channels do not properly model the elevation and azimuth at MS. Furthermore no information concerning the polarization is included. As a result, future work will focus on the analysis of the MS-DoAs and the polarization diversity. A measurement campaign using a bi-polar planar antenna array at MS is currently being processed. The results issuing from this campaign will complete the propagation channel models proposed in this paper.

Figure 1 :

 1 Figure 1: Measurement campaign description

Figure 2 :

 2 Figure 2: Sc area definition

Figure 3 : 4 : 5 :

 345 Figure 3: Histogram of Dist Figure 4: Histogram of MS-Azi Figure 5: Histogram of DS

Figure 6 : 7 : 8 :

 678 Figure 6: Histogram of AS Figure 7: Histogram of ScF Figure 8: Histogram of MaxF

Figure 9 :Figure 10 :Figure 11 :

 91011 Figure 9: Selection of typical and atypical files

  Figure 12: Shadowing factor estimation

Figure 13 :

 13 Figure 13: Histogram of SF Table2sums up the global parameter correlation coefficients. The top right part contains correlation coefficients that were processed for all groups (typical and atypical). The bottom left part contains correlation coefficients that were only processed on the typical groups. The most significant difference concerns the correlation between AS and DS (0.21 with all groups, 0.6 with typical groups). This difference highlights the impact of the selected set of measurement data. A reduction of only 20 % of the total amount of data can significantly modify the correlation. It can partially explain divergent results found in the literature about the AS/DS correlation[START_REF] Laspougeas | Radio propagation in urban small cells environment at 2 GHz: experimental spatio-temporal characterization and spatial wideband channel model[END_REF][START_REF] Nilsson | Measurements of the spatio-temporal polarization characteristics of a radio channel at 1800 MHz[END_REF][START_REF] Pedersen | A stochastic model of the temporal and azimuthal dispersion seen at the base station in outdoor propagation environments[END_REF][START_REF] Algans | Experimental analysis of the joint statistical properties of azimuth spread, delay spread, and shadow fading[END_REF]. Global parameters are slightly correlated with Dist or MS-Azi. The most correlated parameter with the distance is AS (-0.37). The correlation ScF/MS-Azi confirms the trend pointed out in groups Typical1 and LowAS: the street canyon effect is emphasized when MS-

  DS values are overestimated by the SCM macrocell model. A DS mean value of 0.65 µs corresponds to the atypical group HighDS described in part IV. Relative to DS values, our measurements are better fitted by the SCM urban micro model. -No comparison is performed for MaxF, which strongly depends on the number of MS-clusters.

	The mean
	number of MS-clusters calculated from the
	measurement data is 20. But, the SCM model assumes 6
	paths defined at MS by a mean direction and a power
	angular Laplacian distribution with a 35° standard
	deviation. A straightforward comparison would
	automatically lead to erroneous conclusions.
	-The statistical distribution of ScF with the standard
	SCM model is shown in figure 7. If the street canyon
	option of SCM is selected, then, in 90% of cases, ScF is
	equal to 1 and the mean direction at MS of the 6 paths
	is either 0° or 180°. Compared to our measurements, the
	standard version of SCM underestimates ScF and the
	street canyon option overestimates it. If we consider
	that a mobile experiences the street canyon effect when
	ScF is higher than 0.6, then the percentage of MS that
	experiences a SC effect would be equal to 38%.

Table 1 :

 1 Delay spread and azimuth spread comparison

		Télécom R&D	10 MHz	2.2 GHz	0.25	9.5				This paper
	Frankfurt	Deutsche Telekom	6 MHz	1.8 GHz	0.5	8				[27]
	Norway	Telenor	50 MHz	2.1 GHz	0.056	9.9				[28]
	Sweden	Telia	150 MHz	1.8 GHz	0.11	8				[29]
	Sweden	Telia	150 MHz	1.8 GHz	0.075	7				[30]
	Aarhus Stockholm	Uni. Aalborg	5 MHz	1.8 GHz	0.6 / 1.2	7.5 / 11				[31]
	Bristol	Uni. Bristol	20 MHz	1.9 GHz	0.44	10				[32]
	Bristol	Uni. Bristol	20 MHz	1.9 GHz 2.1 GHz	0.13	9				[33]
	Bristol	Uni. Bristol	20 MHz	1.9 GHz 2.1 GHz	0.3			73.5		[34]
	Helsinki	Uni. Helsinki	60 MHz	5.3 GHz		7.6	1.7	52.3	7.7	[35]
	Helsinki	Uni. Helsinki	30 MHz	2.1 GHz	0.65 / 1.27					[23]
	Munich	Uni. Illmenau	120 MHz	5.3 GHz	0.06	7		70		[36]
	Stockholm	Ericsson	200 MHz	5.25 GHz	0.250	20		75	20	[37]

Table 2 :

 2 5, SF/AS=-0.6, SF/DS=-0.6) Global parameter correlation VI. CONCLUSION

		Dist. Az. MS	DS BS-AS	Max fact.	SC fact.	Sh. Fact.
	Dist.	1.00	-0.28	0.16 -0.55	0.19 0.28	0.16
	Az. MS	-0.20	1.00 -0.02	0.32 -0.46 -0.60 -0.48
	DS	0.03	0.03	1.00	0.21 -0.39 0.10 -0.32
	BS-AS	-0.37	0.14	0.60	1.00 -0.46 -0.21 -0.40
	Max Factor	0.09	-0.37 -0.45 -0.38	1.00 0.46	0.51
	SC Factor	0.18	-0.53	0.00	0.02	0.46 1.00 -0.11
	Sh. Factor	0.23	-0.32 -0.19 -0.37	0.33 -0.10	1.00


Maribel Fernández

Bruno Pinaud

János Varga
email: janos.varga@kcl.ac.uk

A Port Graph Rewriting Approach to Relational Database Modelling

Keywords: relational databases, database design, port graph, graph transformation, functional dependency, minimal cover

We present new algorithms to compute the Syntactic Closure and the Minimal Cover of a set of functional dependencies, using strategic port graph rewriting. We specify a Visual Domain Specific Language to model relational database schemata as port graphs, and provide an extension to port graph rewriting rules. Using these rules we implement strategies to compute a syntactic closure, analyse it and find minimal covers, essential for schema normalisation. The graph program provides a visual description of the computation steps coupled with analysis features not available in other approaches. We prove soundness and completeness of the computed closure. This methodology is implemented in PORGY.

Introduction

Relational database design includes conceptual and logical modelling, as well as physical modelling. The theory behind these steps is well-understood (it is part of the syllabus of many databases courses [START_REF] Garcia-Molina | Database systems -the complete book[END_REF]), and highlights the advantages of developing normalised database designs. Yet, database professionals often consider normalisation too cumbersome and do not apply normalisation theory, due to the lack of adequate tools to support logical modelling [START_REF] Badia | A Call to Arms: Revisiting Database Design[END_REF].

Formal, graph-based approaches to database design have used labelled graphs or hypergraphs [START_REF] Abrial | Data semantics[END_REF][START_REF] Ausiello | Graph algorithms for functional dependency manipulation[END_REF][START_REF] Batini | Rewriting systems as a tool for relational data base design[END_REF]. We advocate a new approach to database modelling using attributed port graphs, which are graphs where edges are connected to nodes at specific points, called ports. Attributes of nodes, edges and ports are used to represent properties of the system modelled. Port graphs were introduced in [START_REF] Andrei | Rewriting Calculus for Graphs: Applications to Biology and Autonomous Systems[END_REF] to model biochemical systems and have been used in various domains [START_REF] Fernández | Strategic Port Graph Rewriting: an Interactive Modelling Framework[END_REF]. Port graphs are a good data structure to store and to visualise relational schema: ports provide additional visual information about the design. We propose to represent relational attributes and functional dependencies as nodes, and use edges to link attributes and dependencies; ports indicate the role of the attribute in the dependency. This representation has advantages when computing properties of the schema, such as syntactic closure of the set of dependencies, a crucial step in producing a normalised schema. We specify an algorithm to compute closures using port graph rewriting rules controlled by strategies. Our system has been implemented in Porgy [START_REF] Andrei | Porgy: Strategy-driven interactive transformation of graphs[END_REF] -a visual, interactive modelling tool. Porgy provides a graphical interface to specify an initial model, port graph rewriting rules and strategies. It displays the set of rewrite derivations (a derivation tree) and includes features such as cycle detection, to facilitate debugging.

Summarising, our main contributions are:

1. a Visual Domain Specific Language (VDSL) specifically tailored to model relational database schemata (Section 3); 2. a new visual representation of Armstrong's axioms to infer functional dependencies, using the port graph VDSL mentioned above (Section 4.1); 3. a sound and complete strategic graph program to compute the syntactic closure of a set of functional dependencies, with examples (Sections 4.2,4.3); 4. an implementation3 in Porgy, together with a set of techniques to query the relational database design, using Porgy's derivation tree and graphical interface to analyse properties of the model: In particular, we show how to solve the membership problem (Section 4.4); 5. a strategy and a set of transformation rules to simplify sets of dependencies, as required to compute a minimal cover (Section 5).

Related Work. Hypergraphs are used for relational database design in [START_REF] Batini | Rewriting systems as a tool for relational data base design[END_REF][START_REF] Embley | Mapping Conceptual Models to Database Schemas[END_REF].

Using directed graphs candidate keys of a relation are computed in polynomial time [START_REF] Saiedian | An efficient algorithm to compute the candidate keys of a relational database schema[END_REF]. A special family of labelled graphs, FD-graphs, were introduced in [START_REF] Ausiello | Graph algorithms for functional dependency manipulation[END_REF] to obtain closures of functional dependencies. In terms of graph transformations for database modelling we highlight two works. Hypergraph rewriting was used for the representation of functional dependencies [START_REF] Batini | Rewriting systems as a tool for relational data base design[END_REF] and Triple Graph Grammars were used to optimise a database schema [START_REF] Jahnke | Applying Graph Transformations to Database reengineering[END_REF].

Our contribution and main difference with respect to these works is the design of a domain-specific visual language with emphasis on interactive modelling, including strategies to control the application of rules, and the use of the derivation tree as part of the visualisation framework, giving the modeller access to all the sequences of transformation steps, to facilitate the analysis of the system. Port graphs were used to compute transitive closures in [START_REF] Varga | Finding the Transitive Closure of Functional Dependencies using Strategic Port Graph Rewriting[END_REF]. Here we compute the full Armstrong closure (not just transitive closure), and show how to use the derivation tree to analyse closures and answer queries about the database model, such as whether a given functional dependency is in the closure of a set of dependencies (the membership problem), and compute minimal covers.

Porgy's strategy language is strongly inspired by PROGRES [START_REF] Schürr | The PROGRES Approach: Language and Environment[END_REF], GP [START_REF] Plump | The design of GP 2[END_REF] and by strategy languages developed for term rewriting [START_REF] Borovanský | An overview of ELAN[END_REF]19]. None of the available graph rewriting tools permits users to visualise the derivation tree, as in Porgy, where users can interactively visualise alternative derivations, follow the development of specific redexes, etc. When computing the closure of a set of dependencies, the derivation tree permits to see how each dependency is generated, offering a direct visualisation of the inference steps according to Armstrong's axioms.

Background

Relational Databases

We assume that the reader is familiar with the theory of logical design of relational databases [START_REF] Maier | The Theory of Relational Databases[END_REF], in particular, the definitions of: relation schema, attribute, candidate key and functional dependency (FD). We refer to a single attribute with letters from the beginning of the alphabet A, B, . . . and to attribute sets with letters from the end of the alphabet W, X, Y, Z. Let R(A) = {R 1 , . . . , R k } be a set of relation schemata over a set A of attributes. Let FD = {Σ 1 , . . . , Σ k } be the respective sets of functional dependencies and CK = {C 1 , . . . , C k } be the respective sets of candidate keys. A relational database schema is a tuple DB = (R(A), FD, CK).

We assume familiarity with the inference rules known as Armstrong's Axioms: Reflexivity (or Trivial Dependency), Augmentation, Transitivity, Union, Decomposition, Pseudotransitivity. These rules are sound and complete [START_REF] Armstrong | Dependency structures of data base relationships[END_REF][START_REF] Beeri | A complete axiomatization for functional and multivalued dependencies in database relations[END_REF]. From now on, by syntactic closure we will mean Amstrong's syntactic closure, that is, the set Σ + of all FDs that can be inferred from Σ using Armstrong's Axioms, or equivalently, using the sound and complete subset consisting of Reflexivity, Transitivity and Augmentation, stated below following Beeri et al. [START_REF] Beeri | A complete axiomatization for functional and multivalued dependencies in database relations[END_REF].

(A1) Reflexivity: if Y ⊆ X then X → Y . (A2) Augmentation: if Z ⊆ W and X → Y then XW → Y Z. (A3) Transitivity: if X → Y and Y → Z then X → Z.
Syntactic closures are used to compute minimal covers of sets of FDs. The minimal cover Σ min of Σ is a set of dependencies that fully represent Σ and satisfy the following three conditions [START_REF] Maier | Minimum Covers in Relational Database Model[END_REF]:

1. all the FDs in Σ min have singleton right sides; 2. Σ min is left-reduced: if one attribute is removed from any left side then Σ can no longer be inferred from Σ min ; 3. Σ min is nonredundant: if any FD is removed from Σ min then Σ can no longer be inferred from it.

Our goal is to provide visual algorithms to compute syntactic closures and minimal covers. This work assumes that a) FDs have singleton right sides and b) there are no cyclical dependencies. Assumption (a) is standard in the relational database literature, without loss of generality, under Armstrong's Decomposition rule. The problem of cyclical dependencies reduces to kernel search in a directed graph which is NP-complete.

Port Graph Rewriting and Porgy

We recall the notion of attributed port graph rewriting (see [START_REF] Fernández | Strategic Port Graph Rewriting: an Interactive Modelling Framework[END_REF] for more details).

Definition 1 (Attributed port graph). An attributed port graph G = (V, P, E, D) F is a tuple (V, P, E, D) of pairwise disjoint sets where:

-V is a finite set of nodes; n, n 1 , . . . range over nodes; -P is a finite set of ports; p, p 1 , . . . range over ports; -E is a finite set of edges between ports; e, e 1 , . . . range over edges; two ports may be connected by more than one edge; -D is a set of records, which are sets of pairs attribute-value; and a set F of functions Connect, Attach and Label such that:

for each edge e ∈ E, Connect(e) is the pair (p 1 , p 2 ) of ports connected by e; for each port p ∈ P , Attach(p) is the node n to which the port belongs; -Label : V ∪ P ∪ E → D is a labelling function that returns a record for each element in V ∪ P ∪ E.

For each node n ∈ V , Label(n) contains an attribute Interface whose value is the list of names of its ports.

A port graph rewrite rule is itself a port graph L ⇒ C R consisting of two subgraphs L and R, called left-hand side and right-hand side, respectively, together with an arrow node that links them. Each rule is characterised by its arrow node, which has a unique name (the rule's label), an optional attribute Where defining a Boolean condition C that restricts the rule's matching, and ports to control the rewiring operations when rewriting steps are computed. Each port in the arrow node has an attribute T ype that can have one of three different values: bridge, wire and blackhole. A port of type bridge must have edges connecting it to L and to R (one edge to L and one or more to R): it thus connects a port from L to ports in R. A port of type blackhole must have edges connecting it only to L (one edge or more). A port of type wire must have exactly two edges connecting to L and no edge connecting to R.

The ports and edges associated with the arrow node specify a mapping between ports in the left and right-hand sides of the rule, following the Single-PushOut approach [START_REF] Löwe | Algebraic approach to single-pushout graph transformation[END_REF]. This mapping is used during rewriting, to redirect the edges that connect the redex to the rest of the graph once the redex is rewritten (as explained below).

For examples of rewrite rules, we refer the reader to Section 4. It is possible to specify a rule condition requiring that a particular edge does NOT exist in the graph to be rewritten. In Porgy such conditions are graphically represented as a double line grey edge with an X, which is called an anti-edge [START_REF] Fernández | Labelled graph strategic rewriting for social networks[END_REF].

A match g(L) of the left-hand side is found in G if there is a total port graph morphism g from L to G such that if the arrow node has an attribute Where with value andsaturated(g(p i )) holds if there are no edges between g(p i ) and ports outside g(L) in G -this ensures that no edges will be left dangling in rewriting steps. B is a Boolean expression such that all its variables occur in L.

C, then g(C) is true in G. C is of the form saturated(p 1 ) ∧ ... ∧ saturated(p n ) ∧ B,
Let G be a port graph. A rewrite step G ⇒ H via the port graph rewrite rule L ⇒ C R is obtained by replacing in G a subgraph g(L) by g(R), where g is a morphism from L to G satisfying C, and connecting g(R) to the rest of the graph as indicated by the arrow-node edges in the rule: Any edges arriving to a port in g(L) connected by a bridge arrow port to R are transferred to the corresponding ports in g(R); edges connecting to ports in g(L) that are connected to a blackhole port in the arrow node are deleted. Wire ports in the arrow node trigger a rewiring: the ports in G that connect to the ports in g(L) associated to a wire port in the arrow node are linked by an edge in the rewritten graph.

A sequence of rewriting steps is called a derivation. A derivation tree is a collection of rewriting derivations with a common root.

Porgy [START_REF] Fernández | Strategic Port Graph Rewriting: an Interactive Modelling Framework[END_REF] includes functionality to create port graphs and port graph rewrite rules, and to apply rules to graphs according to user-defined strategies. The functions Connect and Attach (see Definition 1) are represented as attributes in records (i.e., records contain data attributes, visualisation attributes such as colour or shape, and structural attributes such as Connect and Attach). Rules are displayed as graphs, and edges that run between ports of L, R and the arrow node are coloured red to distinguish them from normal edges. Porgy also provides a visual representation of the rewriting derivations, which can be used to analyse the rewriting system. Porgy's strategy language allows us to control the way derivations are generated. We can specify not only the rule to be used in a rewriting step, but also the position where the rule should (or should not) be applied. Formally, the rewriting engine works with graph programs.

Definition 2 (Graph Program).

A graph program consists of a located port graph, a set of port graph rewriting rules, and a strategy expression. A located port graph is a port graph with two distinguished subgraphs: a position subgraph and a banned subgraph, denoted G P Q . Rewrite rules can only be applied to G if they match a subgraph which superposes P and does not superpose Q.

We briefly describe below the strategy constructs that we use in our programs (see [START_REF] Fernández | Strategic Port Graph Rewriting: an Interactive Modelling Framework[END_REF] for more details). The keywords crtGraph, crtPos, crtBan denote, respectively, the current graph being rewritten and its Position and Banned subgraphs. For example, the strategy expression setPos(crtGraph) sets the position graph as the full current graph. If T is a rule, then the strategy one(T ) randomly selects one possible redex for rule T in the current graph G, which should superpose the position subgraph P and not overlap the banned subgraph Q. This strategy fails if the rule cannot be applied. Constants id and fail denote success and failure, respectively. while(S)[(n)]do(S ) executes strategy S (not exceeding n iterations if the optional parameter n is specified) while S succeeds. repeat(S)[max n] repeatedly executes a strategy S, not exceeding n times. It can never fail (when S fails, it returns id).

Port Graphs for Database Modelling

First, we define a visual domain specific language (VDSL) for logical design of relational databases. It includes a class of attributed port graphs to represent objects of a relational database, and a language to specify rewrite rules and strategies for those graphs. We also define Database Port Graphs, to represent a relational database schema DB = (R(A), FD, CK) (see section 2.1).

A Visual Domain Specific Language for Database Modelling

The visual building blocks of the language correspond to those of relational databases. Port graph nodes will have an attribute DbType whose value indicates the role of the node. To avoid confusion, we will use Proper Case for relational database concepts (e.g., Attribute) and lower case for port graph concepts (e.g., attributed port graph).

We note here that an Attribute can occur in multiple relations. To this end, we can define a conceptual attribute node. Then we can define an attribute occurrence node to distinguish between appearances in different Relations. In this work, from now on, we only use occurrences and we call them Attribute.

Definition 3 (Relational Database Port Graph VDSL, RDPG-VDSL).

A Relational Database Port Graph VDSL is an attributed port graph G RDB = (V, P, E, D) F , such that V includes the following disjoint sets of nodes (as well as application specific nodes):

-V R : relation nodes (DbType = REL); -V A : attribute nodes (DbType = ATTR); -V F D : functional dependency nodes (DbType = FD); -V CK : candidate key nodes (DbType = CK).

P includes the following disjoint sets of ports:

-P AT T : contained attribute ports pATT; -P REL : parent relation ports pREL; -P DA : dependency attribute ports pFD; -P F D : functional dependency ports pFDLHS and pFDRHS; -P CK : relation candidate key ports pCK; -P KEY : (candidate) key attribute ports pKEY. and the functions Attach and Connect are such that:

-if p ∈ P AT T , Attach(p) ∈ {V R ∪ V CK }; -if p ∈ P REL , Attach(p) ∈ {V A ∪ V CK }; -if p ∈ P DA , Attach(p) ∈ V A ; -if p ∈ P F D , Attach(p) ∈ V F D ; each node in V F D has two ports, pFDLHS and pFDRHS; -if p ∈ P CK , Attach(p) ∈ V R ; -if p ∈ P KEY , Attach(p) ∈ V A .
Connect includes the following pairs of ports (and associated edges):

-Functional Dependency: (pFD, pFDLHS) and (pFDRHS, pFD), where pFD ∈ P DA and pFDLHS, pFDRHS ∈ P F D . Given a dependency ϕ : X → A the pFD port of every attribute node corresponding to X will be connected to the pFDLHS port of the dependency node corresponding to ϕ and the pFDRHS port of the FD node representing ϕ will be connected to the pFD port of the attribute node representing A.

-Attribute in relation: (pATT, pREL), where pATT ∈ P A and pREL ∈ P REL . Given a relation R i and its attribute A, the pATT port of the node representing R i will be connected to the pREL port of the node representing A. -Attribute in candidate key: (pATT, pKEY), where pATT ∈ P A and pKEY ∈ P CK . Given a candidate key CK i and every attribute A j ∈ CK i , the pKEY port of the node corresponding to A j will be connected to the pATT port of the node corresponding to CK i . -Candidate Key of Relation: (pREL, pCK), where pREL ∈ P REL and pCK ∈ P CK . Given a relation R i and its candidate key CK j , the pCK port of the node representing R i will be connected to the pREL port of the node representing CK j .

As a particular case of the above defined class, we now define the Database Port Graph (DBPG) that represents DB = (R(A), FD, CK). Most importantly, we constrain that one Relation is represented by only one relation node and similarly, one FD is represented by only one FD node. Also, each Attribute occurrence is represented by one attribute node. This design decision is based on the separation of concerns principle. The Functional Dependency Port Graph (FDPGs) [START_REF] Varga | Finding the Transitive Closure of Functional Dependencies using Strategic Port Graph Rewriting[END_REF] is a particular case of the above defined Database Port Graph, with Attribute and FD nodes only. An example FDPG is given in Figure 10 in Appendix E.

Variadic Rewriting Rules

To deal with functional dependencies of various arities, previous works used multiple rules [START_REF] Varga | Finding the Transitive Closure of Functional Dependencies using Strategic Port Graph Rewriting[END_REF] or internal data structures (e.g. compound node in [START_REF] Ausiello | Graph algorithms for functional dependency manipulation[END_REF]). Here, we present an extension to the port graph rewriting rule language, called variadic rewriting rules (VRRs), inspired by Variadic Interaction Nets [START_REF] Jiresch | Extending the interaction nets calculus by generic rules[END_REF]. A variadic rule represents a family of rules that differ only in the number of times a subgraph is repeated. First, we propose a container structure that clearly identifies in a port graph the subgraph that will be repeated.

Definition 5 (Pattern Container).

A pattern container is a subgraph within a port graph such that if an edge links two ports that belong to the container, the edge also belongs to the container.

A pattern container has two attributes: a name, and a multiplicity that specifies the maximum number of times the encapsulated pattern will be repeated.

Edges that connect a port in a pattern container and a port in the outside graph are called variadic edges. Variadic edges also have an attribute multiplicity to control the number of repetitions.

Definition 6 (Variadic Port Graph Rewrite Rule, VRR). A variadic port graph rewrite rule, denoted L ⇒ V R, is a port graph rewrite rule with at least one pattern container on the LHS. Multiple pattern containers must not overlap. Pattern container names must be unique on the LHS.

Given a VRR, we obtain its family of rules by running the Expansion algorithm defined below.

Definition 7 (Variadic Pattern Expansion).

For each pattern container, we generate i copies, where i is the value of the multiplicity attribute, as follows:

1. Synchronized Expansion:

If a pattern container is present on both sides of a VRR (i.e. their names are identical), then the pattern is expanded in an iterative way on both sides of the rule until i number of copies of the encapsulated subgraph are generated. If variables are used in attributes then a different variable should be used in each copy. The expansion iterator works pairwise; that is, not all combinations of expansions are generated on LHS and RHS, but only the same number of repetitions on the two sides.

LHS-only Expansion:

If the pattern container is defined on LHS only, the expansion happens on LHS only, in the same iterative way.

If multiple patterns are defined, they are expanded independently, i.e. all combinations are generated, by nested iteration. Generally, the order in which the combinations are generated, does not matter. A variadic edge is expanded based on the value j of its multiplicity attribute. If it equals the multiplicity i of the container it belongs to, then it is fully expanded, i.e. it is created in all i instances of the container. A partially expanded variadic edge (j < i) is only created in the first 1 . . . j instances. In other words, in the nth iteration of the expansion of the pattern container the variadic edge belongs to, if n < j then n copies are created; otherwise j copies are created.

In Porgy, which does not have a mechanism to define variadic rules, Definition 7 can be implemented as a macro expansion. The pattern container is visually represented by an enclosing rectangle (a metanode): attributes name and i are displayed at the top of the rectangle; and, on the LHS, a + sign in its upper-right corner as shown in the example below (Figures 1 and2). Fully expanded variadic edges are also marked with a + sign over them and partially expanded variadic edges have the attribute value j displayed over them.

In this example, because the pattern appears in both sides, the expansion will generate a rule version with one node Y, another with 2 and another with 3, we show in the picture just the version corresponding to 3. If the node Y has an attribute a whose value is an expression containing variables, for example x, then each copy of the node Y will have attribute a with values x 1 , x 2 , x 3 .

Rewriting Rules

In the rules below, x, y, . . . represent name variables for attribute nodes, and f 1, f 2, . . . are name variables for FD nodes. Augmentation. The Augmentation rule (see Figure 3) finds every attribute node y that doesn't have an edge into the FDLHS port of f 1, regardless of what other attributes are connected there already. We find all non-connected attribute nodes by using the anti-edge feature [START_REF] Vallet | Where Social Networks, Graph Rewriting and Visualisation Meet: Application to Network Generation and Information Diffusion[END_REF] of Porgy. An anti-edge is represented by a grey double line in the rule editor. The matching algorithm deems the candidate sub-graph isomorphic if no edge is to be found between the two ports connected by the anti-edge. The rule creates a new FD node and assigns all pre-existing attributes and y to the left side of f 1. The original f 1 dependency node is also kept. We use bridge ports (red edges) to keep and copy the already existing edges into the FDLHS ports of f 1 and NEW. If f 1 was trivial then the new dependency will also be marked trivial. The rule also increases the FunctionalArity counter by 1 indicating that a new attribute is connected to the FDLHS port. Reflexivity. The Reflexivity rule (Figure 4) applies to a node representing the attribute x and generates a trivial dependency x → x.

Then the attribute node x is banned so the rule cannot apply again on the same attribute. The red edges in the arrow node indicate that when applying the rule, any edges connected to the pFD port of x in the left-hand side should be transferred to the corresponding pFD port of x in the right-hand side. Transitivity. A family of Transitivity rules was described in [START_REF] Varga | Finding the Transitive Closure of Functional Dependencies using Strategic Port Graph Rewriting[END_REF] to detect transitive functional dependency chains f 1 : X → Y and f 2 : Y → A. Instead, here we provide a compact representation of the transitivity axiom in the form of a variadic rule, shown in Figure 5. This rule subsumes the family of Transitivity rules used in previous work.

As mentioned in Section 3.2,

|Y | = k ≥ 1 means that f 1 turns into a set of dependencies f 1 1 . . . f k 1 .
The connections between the pFD ports of X attribute nodes and the pFDLHS ports of f 1 1 . . . f k 1 nodes have to be preserved as well as copied onto the pFDLHS port of the newly created FD node (called NEW in Figure 5). We achieve this without needing to include the attribute nodes representing X in the rule, thanks to the bridge ports of the arrow node and the connecting red edges, as explained in Definition 6. Then, to cover all cases, we define a VRR pattern over f 1 and Y , with i = 1 . . . k. By definition the bridge ports, red edges and the normal edges into y 1 .pFD, . . . , y k .pFD will be repeated during the expansion. We show an example expansion of the Transitivity VRR to Transitivity-3, i.e. with 3 repetitions, on Figure 11 in Appendix E. FD nodes are labelled by records containing an attribute UID that uniquely identifies the Functional Dependency, except for trivial dependencies that are all given UID = 1. Nodes representing non-trivial FDs are given a prime number as UID. This offers extra, domain-specific backtracking functionality for dependencies, as explained below.

Note that the Reflexivity, Augmentation and Transitivity rules never remove the matching subgraph. Therefore, these rules could run for ever. To prevent this, we use conditional rules and focusing constructs in Section 4.2 to define the Syntactic Closure strategy. To ensure that the iteration of the Transitivity rule terminates when no new transitive dependencies can be inferred, we use the UID attribute of FD nodes. When the Transitivity rule creates a transitive dependency node, it multiplies the UIDs of the contributing FDs and assigns the result as UID of the new FD node. We forbid the application of the rule if a node already exists with that UID (using NotNode() in the rule condition).

Syntactic Closure Strategy

The Strategy 1: Syntactic Closure applies first the Reflexivity rule as much as possible in the current graph. Each application bans an Attribute node, which ensures termination since matching is not allowed on banned nodes.

In lines 5-6, we set the Position subgraph to be the whole graph and the Banned subgraph to empty. Then, while there is at least one FD node the Augmentation rule hasn't visited and iterated, one(AugIterOn) sets AugIter and AugVisit flags to true on a randomly selected FD node. The Augmentation rule will be applied on this FD node and all attribute nodes that are not connected to the FDLHS port of said FD node. Every attribute node used by this rule is banned to prevent re-application. Once all possible applications are processed, AugIter flag is set to false and the Banned subgraph to empty. The iteration proceeds to the next, not yet visited, FD node. All new FD nodes, created by the Augmentation rule, are assigned a unique UID using the update() construct to call the function, GenerateNextPrime(), using Porgy's Python API. Since the rewrite rules may generate functional dependencies that already exist in the graph (despite the condition in the Transitivity rule), we add CleanUp rules to remove duplicates: see the Cleanup VRR in Figure 12 and an example expansion in Figure 13, both in Appendix E.

Example of application

Our strategy computed the syntactic closure of Σ = {AB → C, ABC → D}; the resulting FDPG can be seen on Figure 6.

Visual Analysis of the Closure

We now turn our attention to usual questions about Σ + . For example, using the derivation tree in Porgy, it is possible to track how and when a particular dependency was generated: If we alter the colour of any FD node in a leaf node of the derivation tree, Porgy will back-propagate this change up the tree. This way, we can identify the exact step where the FD was created, and by zooming on the edges of the derivation tree we can see which of Armstrong's axioms generated the dependency. Another important question in database design is the Membership Problem [START_REF] Beeri | Computational problems related to the design of normal form relational schemas[END_REF]: given a set of FDs Σ, and an FD, ϕ, determine if ϕ ∈ Σ + . Two groups of algorithms were developed to solve the membership problem: 1. generate a syntactic closure and check if ϕ : X → A is in it, or 2. compute the closure of X, X + and check if A is in it. Following the first approach, we can solve the problem by running a strategy to find and highlight the FD node that represents ϕ in the syntactic closure, if it exists, and fail if ϕ ∈ Σ + . For example, Strategy 2 was used to find the dependency ABD → C, highlighted in Figure 6 (due to space constraints, we refer the reader to [START_REF] Fernández | Strategic Port Graph Rewriting: an Interactive Modelling Framework[END_REF] for explanations of the constructs used). Following the second approach, we can simply use Strategy 1 but focusing on the set X of attributes. We only need to replace the expression setPos(all(crtGraph)) with one that describes X, then the rewriting steps will apply on the attribute set in question. For example, if X = B, we write setPos(all(property(crtGraph, node, DbType =="ATTR" && viewLabel=="B"))).

Correctness

The strategic program Cl = [F, closure] consisting of an initial port graph F representing a set of functional dependencies Σ, and the syntactic closure strategy defined in Strategy 1, correctly computes the syntactic closure Σ + . Proofs of the propositions stated below are given in the Appendix.

Proposition 1 (Termination). For any initial FDPG F, the strategic program Cl = [F, closure] terminates.

To prove the correctness of our program, we first show that the three rules Reflexivity, Augmentation and Transitivity are sound and complete, that is, given Σ, we can compute Σ + by using these three rules.

Proposition 2 (Soundness and Completeness of the Rules). The Reflexivity, Augmentation and Transitivity rules stated below are sound and complete:

1. Reflexivity: for any attribute A, A → A. 2. Augmentation: If X → A then XY → A for any attribute A and sets X, Y of attributes.

Transitivity: If

X → A i (1 ≤ i ≤ n) and A 1 , . . . , A n → B then X → B.
Since the Reflexivity, Augmentation and Transitivity port graph rewriting rules implement the rules stated in Proposition 2, to prove that Cl is sound and complete it suffices to show that any sequence of applications of these three rules can be transformed into a sequence in the order defined by the closure strategy.

Definition 8 (Canonical Form). A sequence of applications of Reflexivity, Augmentation and Transitivity is in canonical form if it consists of applications of Reflexivity, followed by Augmentation, followed by Transitivity and Augmentation: (Ref lexivity) * (Augmentation) * (T ransitivity; Augmentation * ) * Proposition 3 (Soundness and Completeness of the Strategy). Canonical sequences are sound and complete.

Finding a Minimal Cover

To generate a Minimal Cover (see Section 2 for the definition) we have to ensure that there are no extraneous attributes on FD left sides and there are no redundant FDs (we already have singleton right sides). Standard algorithms check this by running the Membership algorithm on an altered Σ: remove X → A and replace it with X \ B → A. If this still yields the same Σ + then B is extraneous in X. Instead, since we have Σ + at hand, it suffices to check if there exists Z ⊂ X → A, for all proper subsets Z. We use a variadic rewriting rule (Section 3.2) to specify a family of rules for every possible subset pair (n, k), where n = |X| and k = |Z|. Since Z ⊂ X, we make use of the partially expanded variadic edge feature by restricting one variadic edge to only k expansions. We show the variadic rule (parameterised already with n = 3, k = 2) in Figure 7 (and an expansion in Figure 14 in Appendix E).

Next, we have to remove redundant FDs. A functional dependency ϕ : X → A is redundant, if (Σ \ ϕ) + = Σ + [START_REF] Maier | Minimum Covers in Relational Database Model[END_REF]. Previously published algorithms detected this by running a Membership check on (Σ \ ϕ) to see if it yields ϕ. We note that in an FDPG representing (Σ \ ϕ) + there is an FDPG-Path from X to A. This path exists as an FD node created by the Syntactic Closure strategy, and if a dependency can be inferred in multiple ways, it is present multiple times.

Since |X| ≥ 1, we use a VRR to detect and remove the redundant FD nodes. We present the rule and an expansion in Figures 8 and9.

Using the Extraneous and Nonredundancy rules, Strategy 3 computes a Minimal Cover. We reuse the Syntactic Closure strategy, but without the Clean Up rules. The Nonredundancy rule gets rid of duplicates. Lastly, we remove trivial dependencies (FD nodes where UID = 1), as they are not in the minimal cover.

Conclusion and Future Work

We introduced variadic rewriting rules and used these rules to define strategies that compute and analyse the syntactic closure of a set of Functional Dependencies. We have shown that these strategies are terminating, sound and complete. We have also defined additional rules and a strategy to compute Minimal Covers. A minimal cover is the input of algorithms to find candidate keys [START_REF] Saiedian | An efficient algorithm to compute the candidate keys of a relational database schema[END_REF] and of Bernstein's 3NF Synthesis Algorithm [START_REF] Bernstein | Synthesizing third normal form relations from functional dependencies[END_REF]. The strategies that find these will make use of the already defined CK and Relation nodes. Furthermore, 3NF Relations will require the introduction of the notion of Foreign Key.

Proof. Since the strategy applies three strategies sequentially (Reflexivity, Augmentation and Transitivity), it is sufficient to show that each of them terminates. For this, we show that for each of them there is a measure which is strictly decreasing with respect to a well-founded ordering.

Reflexivity Strategy: The measure in this case is the number of non-banned nodes in the graph. Each application of the reflexivity rule (Figure 4 strictly decreases the number of non-banned nodes. Since the rule can only apply to nonbanned nodes, the iteration defined in line 3 of the closure strategy terminates.

Augmentation Strategy: Two looping constructs are used in this strategy, a while-loop starting in line 7 and a repeat-loop in line 9. The while-loop is controlled by a condition match(AugIterOn), which requires a non-visited node to succeed. The rule AugIterOn applied in line 8 sets the AugIter and AugVisit flags to true on a randomly selected FD node that has AugVisit flag = False. Each application of the Augmentation rule in the loop in line 9 bans the attribute node used, so the the repeat loop terminates, and afterwards the AugIter flag is set to false but the AugVisit flag remains untouched. This means that each iteration of the while loop in line 7 decreases the number of non-visited nodes, thus the strategy terminates.

Transitivity Strategy: This strategy, without the calls to the Augmentation strategy in line 17 and line 23, was shown to be terminating in [START_REF] Varga | Finding the Transitive Closure of Functional Dependencies using Strategic Port Graph Rewriting[END_REF]. We use the same measures, since they are not affected by the call to the Augmentation strategy: For repeat(one(T ransitivity k ); #Augmentation#), the measure is the number of possible matches of the LHS subgraph of f1. This is a good measure because a) the Rule Condition on UID in T ransitivity k prevents reapplication of the rule to the same nodes and b) even though the NEW node is added in the right-hand side, it is not part of the LHS subgraph of f1. Similarly, the nodes added by Augmentation are not connected to f1. By the time we call the Augmentation strategy from Transitivity, f1 will have been augmented and its AugVisit flag is permanently set to True. The only FD node Augmentation will be able to touch at this point is NEW.

For while(match(IterOn))do(...) the measure is

|V F D | G0 + |Σ + | -|V F D | Gi .
That is, the number of FD nodes in the initial graph plus the size of the closure less the number of FD nodes after the i-th application of the loop. With one successful application of the Transitivity rule, the number of FD nodes increases therefore the measure decreases.

Termination of the CleanUp rule iteration is straightforward, since these rules decrease the size of the graph.

Definition 4 (

 4 Database Port Graph, DBPG). A Database Port Graph is an RDPG such that the following constraints are satisfied: -V R : one node DbType = REL per Relation schema in R; -V A : one node DbType = ATTR per Attribute occurrence in any of the R i ; -V F D : one node DbType = FD per Functional Dependency in FD; -V CK : one node DbType = CK per Candidate Key in CK.

Fig. 1 :Fig. 2 : 3 4

 123 Fig. 1: VRR example

Fig. 3 :

 3 Fig. 3: Augmentation rule.

Fig. 4 :

 4 Fig. 4: Reflexivity rule.

Fig. 5 :

 5 Fig. 5: Variadic Transitivity rule.

Strategy 1 :

 1 Syntactic Closure 1 //----Reflexivity ----2 setPos(all(crtGraph)); 3 repeat(one(Ref lexivity)); 4 //----Augmentation ----5 setPos(all(crtGraph)); 6 setBan(all([emptySet])); 7 while(match(AugIterOn))do( 8 one(AugIterOn); 9 repeat(one(Augmentation)); 10 one(AugIterOf f ); 11 setBan(all([emptySet])) 12 ); 13 update("GenerateN extP rime"{result : U ID}); 14 //----Transitivity ----15 while(match(IterOn))do( 16 one(IterOn);

17 repeat

 17 (one(T ransitivity); #Augmentation#); 18 update("GenerateN extP rime"{result : U ID}); 19 one(IterOf f ) 20 ); 21 repeat(one(ResetV isitedF lags)); 22 //----Cleanup ----23 repeat(one(Cleanup)) Next, we compute transitive dependencies (lines 15-21), calling the Augmentation strategy (lines 5-12) after each application of the Transitivity variadic rewriting rule in line 17.

Fig. 6 :

 6 Fig. 6: Syntactic closure of Σ = {AB → C, ABC → D}.

Strategy 2 :

 2 Membership Problem1 setPos(all( 2 property(crtGraph, port,DbType == "FDLHS" && FunctionalArity == 3) 3 ∩ ngb(property(crtGraph, node,DbType == "ATTR" 4 && viewLabel == "A"), edge,DbType == "L") 5 ∩ ngb(property(crtGraph, node,DbType == "ATTR" 6 && viewLabel == "B"), edge,DbType == "L") 7 ∩ ngb(property(crtGraph, node,DbType == "ATTR" 8 && viewLabel == "D"), edge,DbType == "L") 9 ∩ ngb(property(crtGraph, node,DbType == "ATTR" 10 && viewLabel == "C"), edge, DbType == "R") ) ); //end setPos 11 (isEmpty(crtPos))orelse(repeat(one(Highlight)))

Fig. 7 :

 7 Fig. 7: Extraneous variadic rule.

Fig. 8 :

 8 Fig. 8: Nonredundancy VRR. Fig. 9: Nonredundancy rule, i 1 = 3, i 2 = 2.

Strategy 3 :

 3 Minimal Cover 1 #Syntactic Closure without Cleanup# 2 setPos(all(crtGraph)); setBan(all([emptySet])); 3 repeat(one(Extraneous)); repeat(one(N onredundancy)); 4 repeat(one(RemoveT rivial));

github.com/janos-varga/Porgy

Appendix A Proof of Proposition 1

Proposition (Termination). For any initial FDPG F, the strategic program Cl = [F, closure] terminates.

Appendix B Proof of Proposition 2

Proposition (Soundness and Completeness of the Rules). The Reflexivity, Augmentation and Transitivity rules stated below are a sound and complete:

1. Reflexivity: for any attribute A, A → A. 2. Augmentation: If X → A then XY → A for any attribute A and sets X, Y of attributes.

Transitivity: If

Proof. First, we observe that the rules are sound: they are particular cases of the axioms A1-A3 given in Section 2, which are sound and complete. Hence, it is sufficient to prove that the rules permit us to derive the axioms A1-A3.

Remark. Our rules assume that right sides of functional dependencies consist of only one attribute. Since the Union and Decomposition Axioms can be derived from A1-A3 and by them one can infer X → Y Z from X → Y and X → Z, and reciprocally, from X → Y Z one can infer X → Y and X → Z, it is sufficient to consider single attributes in right-hand sides of dependencies.

Axiom A1 can be derived as follows: Let Y = {A 1 . . . A n } and assume Y ⊆ X. Using the Reflexivity rule, we can derive A i → A i and using Augmentation, we derive A i X → A i for each A i ∈ Y . This is sufficient as explained in the remark above.

Axiom A2 can be derived as follows: Let Y = {A 1 . . . A n }, Z = {A n , A n+1 , . . . A p } and W = {A n , A n+1 , . . . A p , A p+1 , . . . , A k } and assume X → Y , that is, X → A i for each A i ∈ Y as explained in the remark above. By repeated applications of the Augmentation rule, we derive XW → A i for each A i ∈ Y . Note that by Reflexivity, we can derive A j → A j for any A j ∈ Z and by repeated applications of Augmentation, we obtain XW → A j , since A j ∈ W . Therefore XW → A i for each A i ∈ Y Z, as required.

Axiom A3 is derived using the Transitivity rule: Assume X → Y , that is, X → A i for each A i ∈ Y , and Y → B i for each B i ∈ Z. Using the Transitivity rule, we derive X → B i , as required.

Appendix C Proof of Proposition 3

Proposition (Soundness and Completeness of the Strategy). Canonical sequences are sound and complete.

Proof. By Proposition 2, Reflexivity, Augmentation and Transitivity are sound and complete. Assume a set Σ of functional dependencies is inferred using a non-canonical sequence S of applications of Reflexivity, Augmentation and Transitivity rules. We show that the steps of application of the rules can be reorder to obtain a canonical sequence that derives the same set of dependencies. Since applications of Reflexivity are independent of other rules, we can reorder the steps, to move all applications of Reflexivity to the start of the sequence, obtaining a sequence S 1 = S Ref l S that derives Σ and such that S Ref l contains only applications of the Reflexivity rule, and S has no applications of Reflexivity.

Similarly, any application of Augmentation in S on a dependency that exists in Σ or has been obtained by Reflexivity or by a previous Augmentation step can be moved towards the start of S , obtaining a sequence S Aug S where S Aug consists only of Augmentation steps and all the applications of Augmentation in S use a dependency obtained by transitivity.

The sequence S Ref l SAugS is therefore canonical and derives the same set of functional dependencies as S. It follows that canonical sequences are sound and complete.

Appendix D DBPG and FDPG Examples

The functional dependency graph Σ = {AB → C, ABC → D}:

Appendix E Variadic Rewriting Rule Expansion Examples

Example expansion of Transitivity VRR to Transitivity-3, where i = 3.


Chloé Artaud
email: chloe.artaud@univ-lr.fr

Antoine Doucet
email: antoine.doucet@univ-lr.fr

Jean-Marc Ogier L3i
email: jean-marc.ogier@univ-lr.fr

Vincent Poulain D'andecy
email: vincent.poulaindandecy@yooz.fr

Receipt Dataset for Fraud Detection

The aim of this paper is to introduce a new dataset initially created to work on fraud detection in documents. This dataset is composed of 1969 images of receipts and the associated OCR result for each. The article details the dataset and its interest for the document analysis community. We indeed share this dataset with the community as a benchmark for the evaluation of fraud detection approaches.

I. INTRODUCTION

Recent research in document forensics are mostly focused on the analysis of images of documents. One of the frequent tasks consists in retracing the course of document images [START_REF] Shang | Detecting documents forged by printing and copying[END_REF], identifying the use of different printers or scanners for a single document to detect inconsistencies [START_REF] Elkasrawi | Printer identification using supervised learning for document forgery detection[END_REF]. Some other tasks concern the analysis of the contents of images. Printed text is analyzed to find all abnormalities: characters with identical shapes [START_REF] Bertrand | A system based on intrinsic features for fraudulent document detection[END_REF] or irregular fonts [START_REF] Bertrand | A conditional random field model for font forgery detection[END_REF], or lines that are skewed, misaligned, bigger or smaller than others [START_REF] Van Beusekom | Document inspection using text-line alignment[END_REF]. Graphical elements of documents are another subject of research, such as signatures, logos or stamps [START_REF] Micenková | Stamp verification for automated document authentication[END_REF], for instance.

While image analysis is the main field of document forensics, we believe that Natural Language Processing (NLP) and Knowledge Engineering (KE) could be used to improve the performance of fraudulent document detection. Document is not only an image: it contains textual information that can be processed, analyzed and verified. The aim of our work is to provide an Image-Text parallel corpus with a view to create a toolbox that could be combined with previously presented tasks.

In order to build a representative and sound framework for this kind of research, a dataset of genuine documents is needed. In the case of synthetically-created document datasets, the documents fields are generally filled with random information and are thus unrealistic. Such datasets of document images with randomly generated forgeries are good to apply imagebased methods, but do not satisfy the needs of informationbased methods since information is fake and inconsistent.

Therefore we decided to create a real-life dataset of documents with both images and texts and share it with the community 1 . Section 2 presents the collection of document images while Section 3 describes the OCRed text corpus. Finally, we discuss the use of such a corpus for the document forensics community (Section 4). Creating a public administrative document dataset is a difficult task: most of documents are personal or sensitive, they contain private information about individuals, administrations or companies and people want to keep originals [START_REF] Bertrand | A system based on intrinsic features for fraudulent document detection[END_REF]. One type of document that people easily accept to share is receipts, since they preserve anonymity and for most people and in most cases, saving them is essentially useless.

From December 2016 to June 2017 we collected around 2,500 documents by asking members of the L3i laboratory, families and friends. After removing receipts which are not French, not anonymous, not readable, scribbled or too long, we captured 1969 images of receipts. To have the best workable images, we captured receipts with a fixed camera in a black room with floodlight. Receipts were placed under a glass plate to be flattened. Each photography contained several receipts, so we extracted and straightened each one of them to obtain one receipt per document without much borders. The resolution of these images is 300 dpi.

These pictures are split into 3 categories corresponding to their origin:

• 454 receipts from one same franchise with homogeneous size (23% of total corpus), • 148 receipts from other shops of the same retail company (8%), • 1367 receipts from other stores (69%) Images have different sizes because of the nature of receipts: it depends both on the number of purchases and on the store that provides the receipt. The first subset is homogeneous from There is a lot of noise due to paper type, the print process and the state of the receipt, as they are often crumpled in pockets or wallets and generally handled with little care. Noises can be folds, dirts, rips. Ink is sometimes erased, or badly printed. This is a very challenging dataset for document image analysis.

III. TEXT DATASET To extract text from images, we applied Abbyy Finereader 11's Optical Character Recognition engine. Since image quality is not perfect, so are the OCR results. The dataset we propose is actually the result of an automatically corrected corpus, in which we corrected the most frequent errors, such as "e" symbols at the end of lines or "G" characters (for "grammes") after sequences of 2 or 3 digits. The Table I shows the average of characters and automated corrections per documents for each subset. Of course, after these corrections there are still OCR errors, and it would be interesting for the community to improve quality of low resolution documents OCR. A participative platform will be implemented to correct texts and get a sound ground truth.

On the first subset, receipts are generally very small and contain 17 lines on average. On these 17 lines, we can always find:

• 4 or 5 lines with the name of shop and its contact information • 1 line for the table header • 1 line about the total amount • 2 lines about payment information • 1 line about receipt details and time and date information • 1 or 2 lines of thanks To these lines are sometimes added a few lines about fidelity card or to encourage clients to sign up for it. Finally, the other lines detail the price and title of the purchased products. This subset stems from very little shops and most of the purchases consist in meals and other staples.

As to the other two subsets, the length and content of receipts is more variable: the average number of lines is 30. In France, sellers have no obligation to provide receipts to private persons for the sale of products. Consequently, standards are not strictly followed regarding the content of receipts, which is thus rather irregular, sometimes not even containing the shop's name or that of products as shown in Figure 1.

The text of the receipts is very challenging to extract, analyze, model and verify because of the way the information is expressed in them. In general, approaches to address document understanding are based on NLP techniques using lexicon and syntactic rules, which generally requires wellformed sentences consisting of dictionary words, and following grammars.

Working with the texts found in receipts does not allow the use of such approaches. We have to work with the partial structure of these "semi-structured" documents to create a context and to be able to tag each part of document. We can not apply Part of Speech tagging but we can for example detect recurrence and patterns to tag and extract the price or the name of a product.

Another difficulty of this type of documents is the need to be concise to put all information on a small paper. Indeed, receipts contain numerous acronyms and abbreviations, in addition to named entities, which provides a very hard challenge for information processing. For example, we can find expressions such as "BRK SQR 1L PJ POMM 1.54e" for "Brick square 1 litre Pur Jus de Pomme 1.54" (i.e. "one liter brick of pure apple juice").

IV. A DATASET TO BE FALSIFIED

This parallel dataset of images and texts is intended to undergo realistic forgeries. By "realistic forgeries", we mean modifications that could happen in real life, as in the case of insurance fraud when fraudsters declare a more expensive price than true for objects that were damaged or stolen. Victims of fires or theft have to provide evidence of purchases, namely receipts or invoices, to prove their existence. Falsifying a receipt to earn more money from insurance is very tempting and quite simple.

Each part of receipt information is verifiable with external knowledge, and we think that suspicious details can be detected by semantic comparison. To prove this assertion, we need fake information, therefore fake -but real-life-basedtexts. A fraud campaign with non-specialists of fraud will be organized to get realistic falsifications (price raises, changes of product titles, hotel address changes, etc.).

Having real and original documents lets us know the truth before falsification. This is very useful to analyze the falsification process and compare versions. So far, image-based and text-based methods have already proven useful to detect distinct cases of fraud [START_REF] Goasdoué | Fact checking and analyzing the web[END_REF]. Image-based methods can detect poor falsification, but not the perfect imitations; text-based methods can detect unlikely information, but not the reasonable frauds. The combination of the two types of approaches should be able to allow further improvement to fraudulent document detection. The receipts dataset will provide a unique benchmark to test and evaluate such approaches.

V. CONCLUSION

This new dataset, composed of 1969 images of receipts and their associated OCR results is a great opportunity for the computational document forensics community to evaluate and combine image-based and text-based methods for the detection of fake, forged and falsified documents.

Fig. 1 .

 1 Fig. 1. Example of receipt

The dataset is available online: receipts.univ-lr.fr


Frederic Barbaresco

François Desquibet

Johann Dreo

Jean-Marie Mirebeau

Generalized fast marching method for computing highest threatening trajectories with curvature constraints and detection ambiguities in distance and radial speed

We present a recent numerical method devoted to computing curves that globally minimize an energy featuring both a data driven term, and a second order curvature penalizing term. Applications to image segmentation are discussed. We then describe in detail recent progress on radar network configuration, in which the optimal curves represent an opponent's trajectories.

1 Globally optimal paths with a curvature penalty This paper is concerned with planar paths minimizing certain energy functionals, between two given points and with prescribed tangents at these points. The path energy model features a low order data-driven term, and a higher order regularization term. A globally optimal path is found, using optimal control techniques, which involve numerically solving a PDE on the configuration space of positions and orientations. We discuss applications to image segmentation, and motion planning in §2Threatening trajectories and radar network configurationsection.2.

Path energy models In the models of interest to us, the cost of a smooth planar path x : [0, T ] → Ω, parametrized by Euclidean arc length and within a domain Ω ⊂ R 2 , takes the following form:

C(x) := T 0 α(x(s), ẋ(s)) C( ẍ(s) ) ds. (1)
We denoted by α : Ω × S 1 →]0, ∞[ an arbitrary continuous data-driven term, depending on the path position and direction. The path local curvature κ = ẍ(t) (recall that ẋ(s) ≡ 1) is penalized in (1.1Path energy modelsequation.1.1) by a cost function C(κ), which may be chosen among the following classical models, here sorted by increasingly stiffness:

Reeds-Shepp: 1 + κ 2 , Euler-Mumford: 1 + κ 2 , Dubins: 1 κ ≤ 1, ∞ else. ( 2
)
They are respectively representative of (i) a wheelchair-like robot, (ii) the bending energy of an elastic bar, and (iii) a vehicle with a bounded turning radius. In the case of the Reeds-Shepp model, one must further distinguish between the classical model with reverse gear, and the forward only variant [START_REF] Duits | Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis[END_REF].

Viscosity solutions, and the Fast marching algorithm. Data-driven path energies, subject to e.g. fixed endpoints, usually possess many local minima. In order to guarantee that the global minimum is found, path energy minimization must be reformulated as an optimal control problem.

The corresponding value function is the unique viscosity solution to a PDE of eikonal type, and the optimal paths can be extracted by backtracking once it is numerically computed [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF].

Only simple first order energies, such as T 0 α(x(s)) ẋ(s) ds could originally be addressed in the viscosity solution framework, typically using the Fast Marching Method (FMM) which solves the eikonal PDE in a single pass over the domain [START_REF] Laurent | Global minimum for active contour models: A minimal path approach[END_REF]. Recent progress [START_REF] Duits | Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis[END_REF][START_REF] Chen | Global Minimum for a Finsler Elastica Minimal Path Approach[END_REF][START_REF] Mirebeau | Fast-marching methods for curvature penalized shortest paths[END_REF] enabled the extension to (1.1Path energy modelsequation.1.1) of the FMM. For that purpose the path is lifted in the configuration space of positions and orientations, defining γ(t) = (x(t), θ(t)) subject to the constraint ẋ(t) = n(θ(t)) where n(θ) := (cos θ, sin θ). This non-holonomic constraint allows to reformulate (1.1Path energy modelsequation.1.1) as a first order energy, since |ẍ(t)| = | θ(t)|. The energy of a non-admissible path γ = (x, θ) : [0, 1] → R 2 × S 1 , defined in the augmented space but such that ẋ(t) is not positively proportionnal to n(θ(t)) for some t ∈ [0, 1], is defined as +∞. See [START_REF] Mirebeau | Fast-marching methods for curvature penalized shortest paths[END_REF] for details and comparison with alternative approaches such as [START_REF] Strandmark | Shortest Paths with Curvature and Torsion[END_REF][START_REF] Liao | Globally Optimal Curvature-Regularized Fast Marching For Vessel Segmentation[END_REF].

At the request of a reviewer, we do provide some additional detail on the theoretical and numerical approach. Denote by u(x, θ) the minimal cost (1.1Path energy modelsequation.1.1) of a path from the domain boundary ∂Ω to the endpoint x with final tangent (cos θ, sin θ). Then u, known as the value function to the optimal control problem, is a (possibly discontinuous) viscosity solution [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF][START_REF] Mirebeau | Fast-marching methods for curvature penalized shortest paths[END_REF] to the Bellman equation

F * (x,θ) (∇u(x, θ)) = α(x, θ) in Ω × S 1 , u(x, θ) = 0 on ∂Ω × S 1 ,
where the α is the data-driven term appearing in (1.1Path energy modelsequation.1.1). The Hamiltonian F * in the l.h.s. has the following expression: denoting x := ∇ x u(p), n(θ) and θ := ∂ θ u(p)

Reeds-Shepp: x2 + + θ2 , Euler-Mumford: x + x2 + θ2 , Dubins: max{0, x + θ, x -θ}.
These expressions are derived from the curvature dependent cost C (1.2Path energy modelsequation.1.2) as sup{(x + θκ)/C(κ); κ ∈ R}. Using adequate techniques, we approximate this Hamiltonian in the following generic form

F * (x,θ) (∇u(x, θ)) 2 ≈ max 1≤k≤K 1≤i≤I α ik (θ) ∇u(x, θ), e ik (θ) 2 + 1≤j≤J β jk (θ) max{0, ∇u(x, θ), f jk (θ) } 2 ,
(3) where the weights α ik , β jk , are non-negative, and the offsets e ik , f jk have integer coordinates. The directional derivatives are then approximated using upwind finite differences as in (1.4Viscosity solutions, and the Fast m below, and the coupled system of equations resulting from the discretized PDE is solved in a single pass over the domain [START_REF] Mirebeau | Hamiltonian fast marching: A numerical solver for anisotropic and non-holonomic eikonal pdes[END_REF]. It would be too long to describe here the approximation procedure [START_REF] Mirebeau | Fast-marching methods for curvature penalized shortest paths[END_REF][START_REF] Mirebeau | Hamiltonian fast marching: A numerical solver for anisotropic and non-holonomic eikonal pdes[END_REF] yielding (1.3Viscosity solutions, and the Fast marching algorithmequation.1.3), which involves a relaxation parameter ε > 0 and techniques from algorithmic geometry. Nevertheless let us mention the meta parameters (I, J, K) used: Reeds-Shepp (1, 3, 1), Euler-Mumford (0, 27, 1), Dubins (0, 6, 2).

For comparison, the standard d-dimensional isotropic fast marching method [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF] can be framed in a similar setting, with (I, J, K) = (d, 0, 1): denoting by (e i ) d i=1 the canonical basis of

R d ∇u(x) 2 = 1≤i≤d ∇u(x), e i 2 ≈ 1≤i≤d max 0, u(x) -u(x -he i ) h , u(x) -u(x + he i ) h 2 . ( 4
)
Applications to image processing. Image segmentation methods based on active contours typically involve path energies balancing low-order data-driven terms, and higher order regularization terms. Unfortunately, many second order models can only be locally optimized [START_REF] Kass | Snakes: Active contour models[END_REF], resulting in spurious local minima and high sensitivity to initialization. In contrast, first order models [START_REF] Laurent | Global minimum for active contour models: A minimal path approach[END_REF] can be globally optimized using the FMM, but the lack of smoothness penalization gives way to various artefacts referred to as leaks, shortcuts, and branches combination problems [START_REF] Chen | Global Minimum for a Finsler Elastica Minimal Path Approach[END_REF].

Our numerical method combines the best of the two worlds: a second order energy model (1.1Path energy models and fast global minimization, with prescribed endpoint positions and tangents. This enables new developments, see for instance [START_REF] Chen | Global Minimum for a Finsler Elastica Minimal Path Approach[END_REF] on the retina vessel tree segmentation, and [START_REF] Duits | Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis[END_REF] on white matter fiber path extraction.

Threatening trajectories and radar network configuration

In a collaboration work with the company Thales, we optimize the configuration of a radar network for protecting an objective within a region, against an enemy assumed to have unlimited intelligence and computing power, and yet whose vehicle is subject to some manoeuverability constraints. The goal is to maximize the probability of detection of the most dangerous trajectory between a given source and target, which will take advantage of any hideout in the terrain, blind spot or physical limitation in the radar network. The trajectory is only subject to a lower bound in the turning radius, due to the vehicle high speed. See also the companion paper [START_REF] Dreo | Netted multifunction radars positioning and modes selection by non-holonomic fast marching computation of highest threatening trajectories[END_REF].

We model this problem as a non-cooperative zero-sum game: a first player chooses a setting ξ for the radar detection network Ξ, and the other player chooses a trajectory γ from the admissible class Γ with full information over the network ξ. The players' objective is respectively to maximize and minimize the path cost:

C(Ξ, Γ) := sup ξ∈Ξ inf γ∈Γ C ξ (γ)
where C ξ is the function C defined in (1.1Path energy modelsequation.1.1) but with a data-driven cost term α ξ depending on the setting ξ of the network, and accounting for the local probability of detection. Minimization over γ ∈ Γ (given ξ ∈ Ξ) is performed using the fast and reliable techniques of §1Globally optimal paths with a curvature penaltysection.1. We rely on the CMA-ES algorithm [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF] for the subsequent optimization over ξ ∈ Ξ, which is rather difficult (non-convex, non-differentiable).

In comparison with earlier works [START_REF] Barbaresco | Computation of most threatening radar trajectories areas and corridors based on fast-marching & Level Sets[END_REF][START_REF] Strode | Optimising multistatic sensor locations using path planning and game theory[END_REF], we use the curvature bounded Dubins model (1.2Path energy modelsequation.1.2, right) to reject non-physical attacking trajectories, featuring e.g. angular turns or oscillations in the vehicle direction. We also considerably improve, relative to [START_REF] Mirebeau | Automatic differentiation of non-holonomic fast marching for computing most threatening trajectories under sensors surveillance[END_REF], the detection probability model, used to define α ξ (x, ẋ), taking into account the three following factors respectively related to the radar, the target, and the terrain [START_REF] Ivan | Radar handbook[END_REF].

• The blindness map accounts for the probability of detection of a generic target by a radar, depending on the distance and the radial speed of the target relatively to the radar, see Figure 1., left. There are blind areas, due to the fact that a radar cannot listen to its signal while emitting it, and to the Doppler effect, which respectively causes blind radial distances and blind radial speeds. The positions of the blind areas are periodical and depend on internal parameters of the radar that can be optimized: signal wavelength, and pulse repetition interval.

• The radar cross section accounts for the probability of detection of a specific target, depending on its orientation relative to the radar. For instance, a furtive plane often has a low probability of detection if seen from the front, and a higher one if seen from the side.

• The elevation map is used to determine blind regions in the terrain due to obstruction of the radar line of sight. In a mountainous area, a target can take advantage of valleys to move "under the radar". The Earth curvature is also taken into account.

The profile of the cost function with regard to the direction of movement is typically non-convex, which is significant only in the presence of a curvature penalization. For that, we choose the Dubins model, in which the curvature radius is bounded. We showcase the following three phenomena.

• Trajectories dodging radars through their blind distances (cf Figure 1., top right). In this picture, only the positional factor in the cost map is shown in greyscale, and not the part of the cost depending on the orientation. The red line represents the optimal trajectory of the target, going from the left to the right of a rectangular domain, with a radar in the center. It features a circle arc, at a precise blind distance from the radar, and two spiral arcs, see below.

• Spiraling threatening trajectories, taking advantage of the blind radial speed (cf Figure 1., bottom right). The red line represents the trajectory of the target, going from the left to the center of the domain where the radar is located, maintening a constant angle with the radar in order to minimize visibility, except at the end due to the imposed bound on path curvature.

• Hiding in valleys (cf Figure 2.). A digital elevation map, of 50km×50km around the city of Davos in the Alps, is used to construct a probability of detection map, see Figure 2Threatening trajectories, from a circular region towards its center point, with optimized radar positions.

(left) Positional factor α ξ (x) in the cost map, where ξ is the radar configuration. (right) Digital elevation map.figure.caption.5. Threatening trajectories tend to concentrate in valleys. The optimized radar positions are close to the target to be defended, and either on high ground or in alignment with long valleys.

Future works will be devoted to further enhancing the model, taking into account limited knowledge of the attacker (e.g. due to the use of passive radar receivers), introducing success criteria more complex than mere detection (e.g. requiring detection early enough for interception), and considering speed and altitude variations along the trajectory.

Figure 1 :

 1 Figure 1: (left) blindness map of a radar (simulated data). (top right) dodging a radar through a blind distance, (bottom right) spiraling threatening trajectory

Figure 2 :

 2 Figure 2: Threatening trajectories, from a circular region towards its center point, with optimized radar positions. (left) Positional factor α ξ (x) in the cost map, where ξ is the radar configuration. (right) Digital elevation map.

This project was partly support by ANR research grant MAGA, ANR-16-CE40-0014