Enrico Lovisari
email: enrico.lovisari@gipsa-lab.fr.

Carlos Canudas De Wit
email: carlos.canudas-de-wit@gipsa-lab.fr.

Alain Y Kibangou
email: alain.kibangou@gipsa-lab.fr.

Optimal Sensor Placement in Road Transportation Networks using Virtual Variances

Keywords: Road Transportation systems, Flow reconstruction, Convex relaxation, Sensor placement

This paper addresses the problem of Optimal Sensor Placement in Road Transportation Networks. The performance of the sensors is measured in terms of estimation error covariance of the Best Linear Unbiased Estimator of cumulative flows in the network over a long period. Sensors are to be placed in such a way that the sum of the error covariance and of a cost penalizing the number of sensors is minimized. The problem, inherently combinatorial, is relaxed using the concept of Virtual Variance. The resulting problem can be cast as a convex problem, whose computational load is much lower than the original combinatorial problem. Several variations are discussed, and the algorithm is applied to a regular grid network, for which an explicit comparison with the true optimum is offered, and, using data from the Grenoble Traffic Lab sensor network, to the real-world scenario of Rocade Sud in Grenoble, France.

I. INTRODUCTION

In the last decades the increase of the number of passenger and commercial vehicles has steered several crucial highways and arterial roads towards a state of near saturation, causing the emergence of periods of highly congested traffic on a daily basis [START_REF] Papageorgiou | ITS and traffic management[END_REF]. Traffic congestion is responsible for the increase of travel times and for stop-and-go and other oscillatory phenomena, leading in turn to decreased safety, economical losses, and environmental and psychological hazards in terms of pollution and road rage [START_REF] Bilbao-Ubillos | The costs of urban congestion: estimation of welfare losses arising from congestion on cross-town link roads[END_REF]. Standard practice to solve congestion problem, by augmenting road capacity through extension or construction of highways and other arterial roads, is often infeasible due to physical constraints, roads passing through densely built up areas, and social opposition. Among alternative solutions, Intelligent Transportation Systems (ITSs) are expected to provide better and more robust techniques for real-time monitoring, prediction and actuation of traffic networks via exploitation of recent technological and theoretical advancements.

Of paramount importance is the ability to reconstruct the state of the network, as such an information that is used to forecast traffic evolution, to inform drivers in real-time through navigation systems, to provide statistical information to public authorities to detect in a timely fashion accidents and predict hazardous scenarios, and finally to compute controls and to actuate the network through traffic lights, ramp metering and speed limits, or, in the future, lane change and origin-destination suggestions [START_REF] Papageorgiou | Review of road traffic control strategies[END_REF], [START_REF] Papageorgiou | Alinea: A local feedback control law for on-ramp metering[END_REF], [START_REF] Pisarski | Optimal balancing of road traffic density distributions for the cell transmission model[END_REF], [START_REF] Como | Throughput optimal distributed routing in dynamical flow networks[END_REF].

A primary source of information on the state of the network are fixed traffic detectors, namely, devices able to measure density, flow and average speed of vehicles crossing the section of the road where they are placed. Along with other sources of information, such as Floating Car Data, it can be used as input to observe the traffic state, such as the one designed in the companion paper [START_REF] Lovisari | Data fusion algorithms for density reconstruction in transportation networks[END_REF].

Motivated by the importance of good quality monitoring, in this paper we address the Optimal Sensor Placement problem, namely, the problem of finding the best location where to physically place sensors. This is based on trading off between two contrasting objectives: the first, to maximize the performance of state reconstruction; the second, to minimize the total economic cost of the network.

The performance of the state reconstruction is usually related to the ability to properly estimate the density of vehicles in the roads. The latter is a time-varying quantity whose dynamics can be represented via partial differential equations models, such as the celebrated Lighthill-Whitham and Richards (LWR) model [START_REF] Lighthill | On kinematic waves. ii. a theory of traffic flow on long crowded roads[END_REF], or via their discretizations, as in the well known Cell Transmission Model [START_REF] Daganzo | The cell transmission model, part II: network traffic[END_REF]. Unfortunately, density reconstruction, and its relation with the network topology, is hindered by the complexity and nonlinearity of such macroscopic traffic models.

To simplify the setting, we consider the related problem of reconstruction in a static setting, by considering as performance metric the error covariance of an estimator of the cumulative flows in the network over a long period of time. Since the resulting trading off problem remains a combinatorial problem, we relax it using a method that we call Virtual Variance algorithm, based on the idea to associate to each sensor a virtual variance, which is large when the sensor is not needed for good reconstruction of the flow vector. We also discuss in detail two extensions of the proposed algorithm dealing with important scenarios, dealing with geographical constraints and budget limitations. The only input that the algorithm needs is an estimate of the matrix of splitting ratios and the nominal variance of each sensor. Since in real application a pre-existing sensor network is often unavailable, possible alternatives are field surveys with operators visually counting vehicles, as commonly done for calibration of traffic software, or temporary non-invasive equipment such as radar traffic detectors.

Optimal Sensor Placement is an ubiquitous problem that has received a high degree of attention in several communities due to its importance for network design. In Trans-portation Systems, it is of interest both in the dual-problem of best placement of hubs for cost-efficient transportation of goods and people [START_REF] Shahabi | Robust hub network design problem[END_REF] and Origin-Destination coverage [START_REF] Ehlert | The optimisation of traffic count locations in road networks[END_REF], [START_REF] Hu | A generalized sensor location model for the estimation of network origindestination matrices[END_REF]. In these works, and differently from the present paper, the problem is cast as a mixed integer problem which corresponds to determine the minimal set of locations from which the flows on the whole network can be determined, and sensor measurements are assumed to be perfect.

The contributions of this paper are the following: 1) we formulate the Optimal Sensor Placement problem in terms of positions of sensors in a network of noisy sensors; 2) we propose the Virtual Variance algorithm as a relaxation of the (combinatorial) Optimal Sensor Placement problem; 3) we show the effectiveness of the devised technique on a regular grid, for which the true optimal placement is found by exhaustive search, and a real-world scenario consisting of the freeway "Rocade Sud" in Grenoble, France.

The rest of the paper is organized as follows: after presenting some notation, Section II formulates the Optimal Sensor Placement problem. Section III presents a solution based on the concept of Virtual Variance, while Section IV presents our two numerical experiments. Finally, Section V draws the conclusions and presents several future research directions.

A. Notation

The sets of real and positive real valued vectors of dimension n are denoted R n and R n + , respectively. The set of real valued matrices of dimension n × m is R n×m . D n ⊂ R n×n is the set of diagonal matrices of dimension n × n. A positive definite (positive semidefinite, negative definite, negative semidefinite) matrix A ∈ R n×n is denoted A > 0 (A ≥ 0, A < 0, A ≤ 0), and for A, B ∈ R n×n A > B means A -B > 0 (and similarly for ≥, <, ≤). A T is the transpose of A. For a finite set A, R A denotes the set of vectors indexed by elements of A, and |A| its the cardinality. The identity matrix and the all-one vector (of suitable dimensions) are denoted I and 1, respectively.

A graph G is a pair (V, E), V being the set of nodes and E the set of edges. Edges are equipped with two functions t : E → V and h : E → V, the head and tail functions, respectively, such that e is though to the directed edge between t(e) and h(e). We allow for parallel edges, namely, edges having the same head and tail, but not for loops, namely, edges whose head and tail coincide. A path of length n ≥ 2 is a sequence of edges e 1 , . . . , e n that are consecutive, namely, such that h(e i ) = t ( e i+1 ) for i = 1, . . . , n -1. A path of length 1 is a path made of a single link.

II. PROBLEM FORMULATION

We model a Transportation Network as a graph G = (V, E), in which junctions v ∈ V are interfaces between links, or cells, e ∈ E. Origin cells, which carry vehicles in the network from the external world, and destination cells, which on the contrary let vehicles exit the network, will be referred to as onramps and offramps, respectively. We assume that for every cell there are at least one path from an origin to the cell, and a path from the cell to an offramp.

Let O ⊆ E and D ⊆ E denote the set of onramps and offramps, respectively. Vehicles flow through the cells of the network from their origin to their destination splitting at each junction according to deterministic splitting ratios. In particular, R ej ≥ 0 denotes the fraction of vehicles that exiting from cell e want to enter into cell j. As such, j R ej = 1 if e is not an offramp, and j R ej = 0 otherwise. We assume that the splitting ratios are fixed and perfectly known, and we gather them in a matrix R =

[R ej ] ∈ R n×n where n = |E|.
The next sections are devoted to deriving some properties of the cumulative flows, to providing a simple linear model for the flows, and to formalizing the problem that we address.

A. Flow linear constraints

Let f ∈ R n + be the vector of cumulative flows, namely, the total flow, through the links of the network over a period of time [t 0 , t 1 ]. Let ρ e (t) denote the density of vehicles in cell e at time t, and e the length of cell e. Then the definition of splitting ratios yields the relation e ρe (t) = j∈E R je φ j (t) -φ e (t) for each non onramp cell, where here φ e (t) denotes the instantaneous flow through cell e.

Integrating over [t 0 , t 1 ] yields f e = t1 t0 φ e (s)ds and

e (ρ e (t 1 ) -ρ e (t 0 )) = j∈E R je f j -f e , e ∈ E \ O
Assume that [t 0 , t 1 ] is a long period of time and that at both times t 0 and t 1 the number of vehicles in the network is low, e.g., let t 0 and t 1 correspond to consecutive midnights. Then the magnitude of the elements of { e (ρ e (t 1 ) -ρ e (t 0 )} e∈E\O is negligible compared with the cumulative flows in the network, and the following matrix relation holds approximately

Lf ≈ 0 , (1)
where L ∈ R m×n , m = |E \ O|, is obtained by removing from L = R T -I the rows corresponding to onramps. As already mentioned in the Introduction, estimation of flows needs in principle to be coupled to a dynamical model for densities to realistically monitor a Transportation Network. Since it is however rather difficult to assess the performance of the observer of the density, in the present paper we simplify the problem by limiting our attention to the estimate of a vector of cumulative flow satisfying Eq. (1).

B. Linear measurement model and the Optimal Sensor Placement problem

We study in this section the performance of a linear estimator of the cumulative flows. Let E m ⊆ E be a generic set of cells in which sensors are placed, and consider the following simple linear measurement model

y = H Em f + η (2)
where

• y s is the measurement of the s-th sensor, namely f e +η s if the s-th sensor is located on link e; • H Em ∈ {0, +1} p×n , p being the number of sensors, with [H Em ] se = 1 if the s-th sensor is located on link e, and [H Em ] se = 0 otherwise, so that H Em 1 = 1 and 1 T H Em 1 = p; • η is a random noise vector with zero mean 1 and covariance matrix Σ nom . For sake of simplicity, we assume that noise components are independent with same variance σ 2 nom , so that Σ nom = σ 2 nom I. Let V ∈ R n×r , r = rank{ L}, be a matrix whose columns are an orthonormal basis of the right kernel of LT , i.e., LT V = 0 and V T V = I. Since f belongs to the kernel of L by Eq. ( 1), there exists a vector z ∈ R r such that f = V z. Therefore, we can write y = H Em V z + η.

We consider a linear estimator ẑ = K z y + q z , K z ∈ R r×p and q z ∈ R r . The Best (minimum variance) Linear Unbiased Estimator of z is then obtained solving

min Kz,qz E[(z -ẑ)(z -ẑ) T ] s.t. E[z -ẑ] = 0 ẑ = K z y + q z (3)
Standard and straightforward computations show that (3) is equivalent to

min Kz K z Σ nom K z s.t. K z H Em V = I (4)
and q z = 0. The solution to the previous problem is

K z = (V T H T Em Σ -1 nom H Em V ) -1 V T H T Em Σ -1 nom , with error covariance E[(z -ẑ)(z -ẑ) T ] = (V T H T Em Σ -1 nom H Em V ) -1 . Consequently, the BLUE of f is f = K f y = V (V T H T Em Σ -1 nom H Em V ) -1 V T H T Em Σ -1
nom y and its error covariance is

V p (E m ) = E[(f -f )(f -f ) T ] = V (V T H T Em Σ -1 nom H Em V ) -1 V T .
The quantity V p (E m ) depends on the matrix of splitting ratios and on the nominal variance of the sensors, two given quantities, and on the positions of the sensors, namely on E m . In the following, we use indeed V p (E m ) as a metric to measure the performance of the placement E m . Clearly, with no additional constraint, the optimal placement is simply to equip every cell with a sensor. These devices, however, have a non-negligible purchase and maintenance cost, which has to be considered when designing a sensor network. In this paper, we make the simplifying assumption that the cost of a network over the lifetime of the network is proportional to the number of sensors via a coefficient c > 0.

The problem that we want to address is the following Optimal Sensor Placement problem

min Em trace {V p (E m )} + c|E m | (5)
The optimal solution of the previous problem trades off between network performance, measured as the trace of the estimator error covariance, and the total cost of the network: while the former tends to increase the number of deployed sensors, and also to position them properly, the latter aims to reduce it as much as possible.

The problem is inherently combinatorial, and the determining optimal positions of the sensors, namely, the optimal E m , becomes intractable even for very low network dimensions. In this paper we propose a different strategy, detailed in the next section, after a brief discussion on the minimum required number of sensors.

C. On the minimum number of sensors

Before proceeding, we quickly prove that the minimum number of sensors to estimate the vector of flows is equal to the number of onramps of the system. Assume by relabelling the cells that origin cells are the first 1, . . . , |O| cells. Then the matrix L can be partitioned as

L = -I 0 L on L nn and notice that L = L on L nn . Consider the dual graph G d = (V d , E d ) in which V d = E \ O and (e, j) ∈ E d if L ej = 0. Then it is easy to see that L T
nn is a sublaplacian of G d , namely, it is a Metzler matrix with j L ej ≤ 0. The following result is adapted from [START_REF] Lovisari | Stability of monotone dynamical flow networks[END_REF].

Lemma 1: Let G = (V, E) be a graph and J ∈ R V×V be a weighted sublaplacian of G. Then all the eigenvalues of J have negative real part except possibly eigenvalues in 0. Moreover, if S is the set of nodes v for which u J vu < 0, then J is Hurwitz if for every u there exists a directed path in G from u to a node v ∈ S.

In our case, J = L T nn and S is the set of cells directly following an origin cell. Since by assumption for every cell e there exists an origin j ∈ O and a path from j to e, then there must also exist a k ∈ S and a path from k to e, so that the assumptions of Lemma 1 are thus satisfied. Therefore, L nn is Hurwitz and thus invertible, and in turn L is a full rank matrix, with rank m = |E \ O|, the number of non-onramp cells, and its kernel has rank r = |O|, namely rank {V } = r = |O|.

III. RELAXATION VIA VIRTUAL VARIANCES

It is easy to realize that links in which sensors are not present can be though of as links with sensors whose variance is infinite. Indeed, if by convention we consider +∞ to be an admissible variance, the previous problem is equivalent to assigning a virtual variance σ 2 e to each sensor, and decide for which it should be σ 2 e = σ 2 nom , and for which it should be σ 2 e = +∞. With this interpretation, we can set E m = E, so that H Em = I.

Let Σ be the (diagonal) matrix of virtual variances, and let the corresponding trace of error covariance be denoted, with an abuse of notation, V p (Σ). Our approach is based on the intuitive idea that by increasing the variance on the sensors that are not in the solution to Eq. ( 5) the quantity V p (Σ) does not increase much.

More formally, we consider thus the following problem

min Σ∈Dn trace V (V T Σ -1 V ) -1 V T + f (Σ) s.t. Σ ≥ Σ nom (6)
where f (Σ) is a decreasing function of the diagonal elements of Σ. Notice that Σ is the optimization variable in (6): by reducing the virtual variances, namely, the diagonal elements of Σ, the trace of the error covariance decreases and the term f (Σ) increases, and viceversa. For sake of simplicity, let f (Σ) = 1 T Σ -1 1. With the change of variables Ω = Σ -1 , Ω > 0 diagonal, and noticing that trace

V (V T Σ -1 V ) -1 V T = trace (V T Σ -1 V ) -1
by known properties of the trace and because V T V = I, we obtain the following problem

min Ω∈Dn trace (V T ΩV ) -1 + γ1 T Ω1 s.t. 0 ≤ Ω ≤ Σ -1 nom (7)
Once a solution Ω is found, we obtain the solution of ( 6) by Σ = Ω -1 ; then, we discard all links whose virtual variance is above a certain threshold. We refer to this procedure as the Virtual Variance algorithm. Notice that if the solution provides high virtual variances at locations where sensors are redundant then this is effectively a way to select the most important cells where to place sensors. This is however not enough to solve the problem. As numerical simulations show, it is often the case that ( 7) is solved by assigning low virtual variances to all sensors of the network, rather than keeping it low in some of them and high in others. In order to enhance diversity between sensors, we enrich the cost with a further term that penalizes homogeneity and is reminiscent of works on dissensus (as opposed to consensus) in multi agent networks. choice in this paper is the following: let W ∈ R n×n-1 be an orthonormal base of the subspace orthogonal to 1. The additional considered term is then proportional to e -1 T W * Ω1 , which is, as required, a function that decreases as the diagonal elements of Ω become more and more different. Following this idea, we propose the following optimization problem to solve the original combinatorial problem

min Ω∈Dn trace (V T ΩV ) -1 + γ1 T Ω1 + κe -1 T W * Ω1 s.t. 0 ≤ Ω ≤ σ -2 nom I (8)
which, notice, is convex in the diagonal entries of Ω. Here γ, the total variance weight, and κ, the discrepancy weight, are tunable parameters. In particular, notice that high γ indirectly penalizes the number of sensors, thus yielding to solutions with higher virtual variances at the expense of poor performance. As already mentioned, the cells over which a sensors is to be placed are those whose virtual variance, computed via Σ = Ω -1 , is below a certain threshold. Numerical simulations have shown that the resulting virtual variances are distributed in a highly bimodal way, the low and the large ones being different by several orders of magnitude, thus making easy to distinguish among the two groups.

A. Optimal Sensor Placement with Location constraints

It can be the case, due for example to physical constraints, that some cells cannot be equipped with sensors. This section shows how to adapt the proposed approach to this case.

In particular, let E am ⊆ E, |E am | = k, be the subset of available cells, and let H Eam ∈ {0, +1} k×n be built as in Section II-B. Then the following problem

min Ω∈D k trace (V T H T Eam ΩH Eam V ) -1 + γ1 T Ω1 + κe -1 T W * Ω1 s.t. 0 ≤ Ω ≤ σ -2 nom I (9)
is a restriction of ( 8) once we constrain sensors to be placed on cells in E am only, and the diagonal entries of Ω are the inverse of the virtual variances on the cells in E am . The matrix W is defined as in the previous section, but with suitable dimension (k × k -1). As in the general problem, cells are chosen only if the corresponding virtual variance is below a certain threshold. Remark 1: By the discussion in Section II-C, the minimum number of sensors is r = |O|. As such, if |E em | < |O| the problem ( 9) is not well posed and the solution will only have very high virtual variances. Clearly, such a solution is not acceptable and should be discarded.

B. Optimal Sensor Placement with Number of Sensors constraints

The second scenario that we discuss consists in imposing a constraint on the maximum number of chosen sensor, which might be due to hard budget constraints.

Our solution is based on the following iterative approach:

• Initialization: set γ(0) and κ to chosen nonnegative values; t max to the maximum number of iterations; n max to the maximum number of sensors; • At the t-th step -Solve (8) with γ(t); -If the Virtual Variance algorithm yields a solution with number of sensors less than n max , or if t ≥ t max , stop; -Otherwise, set γ(t + 1) = g(γ(t)), where g is an increasing function of its argument, and iterate. Since, as discussed in the previous sections, γ weights the penalty to low variances, by iteratively increasing it the solution to (8) tends to exhibit more and more high virtual variances, thus reducing the selected number of sensors.

Remark 2: Again by the discussion in Section II-C, the specified maximum number of sensors cannot be be less than r = |O|. If this is not the case the algorithm either does not find a solution and simply cycles until the last iteration step t max , or numerically finds a solution with an extremely high trace (V T H T Eam ΩH Eam V ) -1 .

IV. NUMERICAL EXPERIMENTS

In this section we present the results of two numerical experiments. In the first, we solve the problem of Optimal Sensor Placement in a small (but not trivial) regular grid over which we run an exhaustive search, thus allowing us to explicitly compare the result of the Virtual Variance algorithm with the optimal solution; in the second, we apply the procedure to the real-world case of the peri-urban freeway "Rocade Sud" in Grenoble, France.

A. Regular grid

We consider the 25 cells regular grid illustrated in The results are shown in Figures 1 and2. In the former, we mark the 8 cells chosen by the Virtual Variance algorithm with a green dot, and the optimal cells when the number of possible sensors is 8 with a red dot. As it can be seen, both procedures place the majority of the sensors at the boundary of the network. The cost between the two solutions is not very different, as it can be observed in Figure 2. Here, we plot with crosses the cost V (h) = trace {V p (h)} + ch for h = 4, 5, 6, . . . , 21, where

V p (h) is V p (E m ) with |E m | =
h and E m is the optimal placement. The optimal trade off between cost and performance is in this case 6, as further increasing the number of sensors is not beneficial. The figure also shows that the solution of the Virtual Variance algorithm has 8 sensors, and plots as a circle the corresponding cost trace {V p } + 8c. As it can be seen, not only the Virtual Variance algorithm finds a solution with a number of sensors that is close to the true optimum, but also, for that number of sensors, is able to place them almost in the optimal way.

B. Rocade Sud

Our second experimental setting is the Grenoble Traffic Lab (GTL) [START_REF] Canudas De Wit | Grenoble traffic lab: An experimental platform for advanced traffic monitoring and forecasting[END_REF], a network of sensors deployed for monitoring and research purposes along the "Rocade Sud", a 12 km long freeway surrounding the town of Grenoble, France, see Figure 3. The network consists in 135 magnetometers buried in the asphalt on both lanes of the main line and on each onramp and offramp, totalling 68 sensing locations. For our purposes, each sensing location will correspond to one sensor. For a detailed report on the GTL, we refer to [START_REF] Canudas De Wit | Grenoble traffic lab: An experimental platform for advanced traffic monitoring and forecasting[END_REF].

The Rocade is partitioned in such a way that each cell includes one sensor; furthermore, for sake of simplicity, we do not consider onramps and offramp, limiting our attention to the main line. The corresponding network consists of 46 cells, and a stylized version of it is shown in Figure 4.

To estimate the matrix of splitting ratios R, we considered a period of data from the ten days 1st -10th of April, 2014 (excluding the 5th and the 6th, weekend days), all typical working days, during the six hours time period 6:00 -12:00. We gathered the cumulative measured flows in all 68 cells and we used them to estimate the matrix R as follows: for each junction v, let E - v and E + v be its incoming and outgoing cells, respectively. Also, let f -

+ v (d). Let F - v = [f - v (1), . . . , f - v (8)] and F + v = [f + v (1), . . . , f + v ( 8
)] be the collection in matrices of such flows. Also let R v ∈ R Ev ×E + v be the local matrix of splitting rations, namely, let [R v ] ej be the splitting ratio of cell e ∈ E - v towards cell j ∈ E + v . Then using Eq. ( 1) we have R T v F - v ≈ F + v , so we can cast, for each v ∈ V, the problem of estimation of the matrix of splitting ratios as the optimization problem

min Rv ||R T v F - v -F + v || 2 s.t. R v 1 = 1 [R v ] ej ≥ 0, ∀e ∈ E - v , j ∈ E + v (10)
The matrix of splitting ratios is then projected over a matrix consistent with the graph made of the cells on the main line only, simply deleting rows and columns corresponding to non-main line cells, and renormalizing the rows of the resulting matrix in such a way that the row sum is 1.

We did not run an exhaustive search due to the relatively high dimension of the network. Instead, we compare the results with the locations of fixed loops installed for monitoring purposes by the Government Agency Centre national d'information routiére (CNIR) [START_REF]Centre national d'information routiére (CNIR[END_REF], which are placed on the cells marked with a red dot in Figure 4.

We run the Virtual Variance algorithm in three scenarios: 1) unconstrained scenario with total variance weight γ = 0.2 and discrepancy weight κ = 20; 2) unconstrained scenario with γ = 1 and κ = 20; 3) constrained scenario with number of sensors at most 10, initial γ = 0.2, and κ = 20. We assume that σ 2 nom = 1 and that the cost per sensor is c = 1. The results are summarized in Figure 4 and Table I. In the table we provide the optimal number of sensors computed via the Virtual Variance algorithm, as well as the corresponding estimator error covariance V p (E m ) and the total cost V (E m ) = V p (E m ) + c|E m |. In Figure 4, cells found in the unconstrained scenario with γ = 0.2 are denoted using a green dot. As can be seen in Table I, our algorithm requires 3 sensors less than the network deployed by CNIR, while the error covariance increases only very slightly. In the constrained scenario and in the unconstrained scenario with high γ (which, as explained above, indirectly penalizes the number of sensors), the error covariance V p (E m ) increases, as expected. Interestingly, the chosen cells in the latter two cases are subsets of the cells chosen in the unconstrained case: in particular, in the constrained scenario all cells are kept except 8, 11, 20 and 41, and in the unconstrained scenario with high γ the algorithm further discards cells 17 and 20. Whether this is a feature of the present case study or a more general property will be matter for future research. V. CONCLUSIONS This paper addresses the problem of optimal placement of sensors in transportation networks. The problem, combinatorial by nature, is relaxed into a convex problem using the concept of Virtual Variance. Future research includes 1) addressing the case of uncertain matrix of splitting ratios, 2) providing theoretical guarantees on the robustness of the proposed approach, such as under sensor failure, and 3) investigating the scaling properties of the proposed strategy.

Fig. 1 .

 1 Fig. 1.The regular grid network used in the numerical experiment. The green dots correspond to the 8 cells selected by the Virtual Variance algorithm with γ = 2 and κ = 20. The red dots correspond to cells selected via exhaustive search when the number of possible sensors is 8.

  Figure 1. We assume that all sensors have a nominal variance of σ 2 nom = 1 and that the cost of each sensor is c = 1. First of all, we solve by exhaustive search the problem (5) for |E m | = 4, 5, 6, . . . , 21, considering for each possible number of sensors all possible combinations of cells and finding that which minimizes V p (E m ). Then, we run the proposed Virtual Variance algorithm with total variance weight γ = 2 and discrepancy weight κ = 20, setting the lower threshold on the virtual variance for discarding a sensor to T d = 100.

Fig. 2 .

 2 Fig. 2.Results of the exhaustive search and of the virtual variance algorithm. Crosses represent the cost of the true optimal placement of 4, . . . , 21 sensors. The Virtual Variance algorithm provides a solution with 8 sensors, with cost plotted as a circle.

Fig. 3 .

 3 Fig. 3. The Grenoble Traffic Lab sensor network in Grenoble.

  v (d) and f + v (d) be the vectors of cumulative flows on the incoming and outgoing flows at junction v for day d, namely, f - v (d) = [f e (d)] e∈E - v , and analogously for f

Fig. 4 .

 4 Fig. 4. Stylized representation of the main line part of the Rocade Sud. White ovals represents junctions of the graph. The selected positions of the 17 fixed sensors by CNIR are marked by red dots, those of the 14 sensors by the virtual variance algorithm by green dots.

The case of non-zero mean noise, for example due to more missed vehicles than overcounting, can be treated analogously. We consider the zero mean scenario for sake of simplicity.

This work as been partially

supported by the EU project SPEEDD FP7 n. 619435.


Gaëlle Ferré
email: gaelle.ferre@univ-nantes.fr

Quentin Brisson
email: quentin.brisson@etu.univ-nantes.fr

" This area of rain will stick South in the far North " Pointing and Deixis in Weather Reports

Keywords: pointing, weather reports, viewpoint, frames of reference, deictic shifts

come   L'archive ouverte pluridisciplinaire

Introduction

Pointing has been the object of quite a large body of research as shown by a multidisciplinary publication such as [START_REF] Kita | Pointing. Where Language, Culture, and Cognition Meet[END_REF]. In a variety of areas, from child development to psychology, linguistics and anthropology, research has shown the intimate link between the oral and gestural production in face-to-face interactions, especially as far as deixis is concerned, as noted in [START_REF] Levinson | Explorations in Cognitive Diversity[END_REF]. So, for instance, [START_REF] Levinson | Explorations in Cognitive Diversity[END_REF] and [START_REF] Haviland | How to Point in Zinacantán[END_REF] noted that pointing is culturally determined and that, depending on whether the information encoded in speech is speaker-oriented or not in a given culture, then the information encoded in gesture will be of a completely different nature. Personal, temporal, and spatial deixis is central to discourse in weather reports. Yet, strangely enough, this type of description has only been studied in the field of automatic gesture recognition to the best of our knowledge (as in [START_REF] Kettebekov | Toward Natural Gesture/Speech Control of a Large Display. Engineering for Human-Computer Interaction (EHCI'01)[END_REF] and [START_REF] Poddar | Toward natural gesture/speech HCI: A case study of weather narration[END_REF] to name just a few studies). The reason for this is possibly that weather reports are likely to abound in pointing gestures and that pointing is easier to recognize in terms of form that other more complex gesture types. We are all familiar with weather reports, and at first look, the mapping of gesture-speech units in this type of presentation may seem extremely straightforward, with nothing more than a person pointing to different locations on a map while describing the weather expected in those locations for the next day or couple of days. Now consider the sentence given as a quote from our corpus in the title of this paper: "this area of rain will stick South in the far North", said as the speaker is making a sweeping gesture over an area of the map to his left. What could be the deictic center of such an utterance? If we posit the speaker as deictic center of the utterance, it works well for the beginning of the sentence and for the gesture, but it doesn't work so well for the end of the sentence: "South of what?", "the far North of what?" This is not an isolated case in weather reports. Based on the analysis by [START_REF] Fricke | The impact of cospeech gestures on linguistic deixis theory[END_REF], who describes a deictic split between the verbal and gestural deictic origo in some route directions, we will show how weather reports involve a constant shift of viewpoint and deictic center in the description of weather conditions. Although time plays a major role in weather reports, this paper will focus on person and space deixis, which are complex enough notions in the limited space of this paper.

Theoretical background

In [START_REF] Lyons | Deixis, space and time[END_REF], Lyons defines deixis as referring to "the function of personal and demonstrative pronouns, of tense and of a variety of other grammatical and lexical features which relate utterances to the spatiotemporal co-ordinates of the act of utterance" (p. 636). Levinson ([8]) adds to this definition by describing deixis as pertaining to the personal, temporal, spatial, discursive and social domains.

Orientational frames of reference

As stated by Levinson in [START_REF] Levinson | Explorations in Cognitive Diversity[END_REF], there are several ways in which utterances can be related to the spatiotemporal context of utterance. These ways are what he calls the "orientational frames of reference". A discourse entity may be conceived of in an absolute frame of reference, with fixed bearings like cardinal directions. It may also be conceived of in a relative frame of reference, so that its location is defined with respect to another location (which can be the speaker, but also the viewer or another object in the field). This means that in order to define the location of the discourse entity, you have to identify the element that serves as a reference point and its own bearings. At last, a discourse entity may be referred to in an intrinsic frame of reference, i.e. in relation to a cultural conception of an object. For instance, unless under special circumstances, when we say that we're "sitting in front of a computer", we usually mean that we're facing the screen, not the plugs on the other side.

As shown by [START_REF] Levinson | Explorations in Cognitive Diversity[END_REF] and [START_REF] Haviland | How to Point in Zinacantán[END_REF], there is great linguistic variation as to which frame of reference is preferred in different cultures. In English, there is a strong preference for the relative frame of reference, although speakers may also use the other two frames. Shifts in frames may occur over a discourse unit but also within a single utterance, and this is true of verbal information as well as information imparted in other modalities, like gesture or body orientation.

Deictic center

The reference point in frames was originally called origo by Bühler ([9]), although others call it the deictic center, a term that will be adopted in this paper. Since the frame of reference may change over the course of an utterance, as mentioned in the preceding paragraph, the deictic center may also change, and this applies to both speech and gesture. [START_REF] Levinson | Explorations in Cognitive Diversity[END_REF] mentions for instance that " complex switches of this reference point or origo may occur in a single sequence of gestures" (p. 250). However, he seems to consider examples in which the reference point in speech and co-occurring gesture is the same. In [START_REF] Fricke | The impact of cospeech gestures on linguistic deixis theory[END_REF], Fricke describes an example of route description and shows that there is a mismatch between the deictic center in speech and co-occurring gesture: over the course of the utterance, the origo of the gesture is the speaker's body while the origo in speech content corresponds to the addressee imagined as wanderer. This is a crucial point for the study of weather reports as we will see that the nature of the description involves not only shifts in frames, but also of course shifts in deictic center and that the shifts may also generate mismatches between gesture and speech in terms of reference point.

Data

Corpus

The corpus on which this preliminary study is based consists in a small collection of 10 weather reports posted on the internet between 2011 and 2015. All the reports are in English. 5 of them are presented by female speakers, and the other 5 by male speakers, although no difference was noted in speech or gesture for male and female speakers. The reports we selected were from different TV channels located in various English speaking countries in order to avoid falling into the analysis of presenters' speech and description habits. Table 1 below presents the channels, the location of their head offices, and the number of reports we downloaded from their websites. The total duration of the recordings was 15.41 minutes (8.04 min for male speakers and 7 min for female speakers), with report duration varying from 55 seconds to 2.35 minutes (average report length: 1:30 minutes).

Annotations

Pointing gestures and co-occurring speech in each report were coded using Elan ( [START_REF] Sloetjes | Annotation by category -ELAN and ISO DCR[END_REF]) for easier retrieval and comparison of examples (181 occurrences). As far as gestures are concerned, we counted the preparation and retraction phases ( [START_REF] Kendon | Visible Action as Utterance[END_REF]) as parts of pointing if there were any. We noted hand shape (open palm, extended index finger, or index and middle finger, or thumb, or little finger). We also noted if the gesture was a fixed pointing or described a path (that includes the contour following gestures or area-sweep gestures noted in [START_REF] Pavlovic | Speech/gesture integration for display control[END_REF]). At last, we noted gesture direction (away from or towards speaker) and arm extension (small, medium or full extension).

On two more tracks, we noted the target type of the pointing gesture (point or area), and whether the map was static or dynamic (scrolling map or animated icon on the map) during gesture production.

Formal description of weather reports 4.1. Overall structure

Although everyone is quite familiar with weather reports, a short formal description of their major features will provide a starting point for the analysis of deixis. Basically, a weather man or woman standing beside a map of a region or nation is describing what the weather is or is going to be like in different locations on the map. In addition to location points, icons and drawings representing weather types or fronts but also text may be superimposed on the map. After greetings and an optional short introduction, the speaker launches into the weather report generally starting with the present state of affairs (which constitutes the spatiotemporal reference point) and proceeds with a description of the weather conditions expected for a later time (which can be the same day or the following day). This is immediately followed by a description of the expected temperatures. At last, the forecast is extended to the next couple of days or even the coming week before closing the presentation with farewells to the audience. A weather report is a monologue throughout, although it may be launched with a short question-answer sequence if it is included in the larger context of a news report.

Types of maps

The traditional weather report uses a background projection screen behind the speaker who monitors his gestures with the help of a control screen (placed either in front or to the side) in order to avoid turning his back on the audience during the description. With this setup, speakers point at locations without looking at the map. Some reports use an oblique screen with respect to the speaker and a different camera angle which presents the screen in the larger frame of the recording studio. In this case, no control screen is used and speakers gaze more freely at the map. The difference between the two types of screen is shown in Figure 1. In some reports, the scale of the map remains constant throughout the report with possible dynamic objects superimposed on the map, but in others, the scale of the map changes as the report progresses which has an obvious impact on gesture size and direction as shown in Figure 2. In this report, although the speaker basically points to a same area on the map of the UK in the two frames, the two gestures are radically different due the shift in scale. The fact that the medium may change is specific to weather reports and does not occur when people point at maps in route descriptions where the map is held constant.

This has an impact on gesture-speech mapping in terms of deixis since speakers may refer in speech to locations "further away" from a reference point previously established while gesturing closer to their own bodies. Another aspect of the maps used in weather reports is that at times, the scale may be held constant while the speaker is pointing at two different locations on the map, but the map may be scrolling down which may generate yet another type of gesture-speech mismatch as in example ( 1) below (the two gestures of interest are marked in the text with square brackets and are illustrated in Figure 3 As he mentions Cambria, the weather man points at a location on the map as shown in (a) and he then partly retracts his gesture (arm still extended but somewhat lower, fist closed). While saying "down in Manchester", he opens up his hand and points slightly upwards again towards the location on the map as illustrated in (b). In between the two gestures, the map has scrolled down, which creates the gesture-speech mismatch typical of weather reports when a speaker points upwards while uttering "down". When in "real life", a gesture would follow a moving target; this is not what happens with a scrolling map in the context of a weather report.

Frames of reference

The survey maps in weather reports use an absolute frame of reference with externally fixed coordinates. By convention, the North has been placed at the top of the map since the discovery of the magnetic North and the invention of the compass. However, this absolute frame of reference is inserted in the relative frame of reference of the speaker, since the North point of the map is not oriented to the North in the recording studio, and since the speaker is standing on one or the other side of the map (which may change as well in the course of the report). The two frames of reference are mixed in speech in example (2) below with a first mention of the absolute frame of reference ("the North West", map internal) followed by the relative frame of the speaker ("down across", map external) in the next sentence:

(2) This is the result of this weather front. It's pushing in from the North West. It's gonna sink down across the country overnight.

Viewpoint in weather reports

The viewpoint adopted in weather reports can be quite straightforward. Example (3) below shows a perfect example of a weather woman addressing the audience. The viewpoint adopted is that of the speaker both in speech and gesture:

(3) Let's come back to that cluster of clouds I showed you earlier. In this utterance, the pronoun "I" clearly makes reference to the speaker, and "earlier" makes reference to a time prior to the time of speaking so that the frame of reference is clearly established as the "here and now" of the speaker. The two pointing gestures that accompany speech are static gestures, one being a point with the index finger while she says "there it is", thus locating a precise location on the large scale map, the other a point with extended open palm in the same direction, matching the word "area" in speech. Both gestures locate a point or an area on the map with respect to the speaker's body so that there is a perfect match in between the "here and now" in speech and the "here and now" in gesture, with a viewpoint that is completely external to the map. Such a perfect match is however not always met in weather reports as will be shown below, and mismatches may arise due to switches in viewpoint, in speech, in gesture or both, or to shifts in deictic center.

Switches in viewpoint

Consider the following example from a BBC national report in the UK:

(4) That cloud then stays with us in the South. To the north of it, here we've got some clearer spells.

The question is: Who is "us/we"? Or in other words, what is the viewpoint adopted in this stretch of talk? Traditional grammars describe the pronoun "we" as including the speaker and any number of other people. This is perfectly appropriate for the mention of "us" in the first sentence. Since the recording studio is located in London, it makes sense to consider that "us" refers to the speaker and the part of the audience who lives in the South. The mention of "we" in the second sentence cannot however refer to the same people. For one thing, another part of the audience is included in the reference, and besides, the speaker cannot be "in the South" and "to the north of it" at the same time, which means that "we" can't include the speaker this time. However, in weather reports, speakers are supposed to be objective and not take their hometowns as systematic deictic centers in the description. In order to remain as objective as possible, they generally assume the role of narrator, whose deictic center is as neutral as possible and is placed on the map in the middle of the space they describe (a nation, a country, a region...).

S N A

So in example (4) above, one can consider that in the second sentence "we" refers to the part of the audience living north of the cloud and the narrator of the report. The viewpoint in speech is now map-internal. Yet, the neutral deictic center (supposedly located in the middle of the UK in this national weather report) has shifted north as a new focus of attention ( [START_REF] Grosz | Attention, Intention, and the Structure of Discourse[END_REF]) has been opened and the narrator's deictic center has been "transposed" ( [START_REF] Haviland | Transpositions, and Relativity[END_REF]) to the North as indicated by the use of the proximal deictic pronoun "here". Now consider example (5) from a BBC report that presents the weather in some parts of Africa (some major towns on the continent are mentioned but not in every country though):

(5)

In Maputo we're in for a bit of a deluge over the next couple of days.

The head office for this report is located in London and the report is not addressed to people living in Africa, but actually to people in the UK who might want to travel to the African countries mentioned in the report, or who have relatives there. The speaker of the report is therefore not in Maputo at the time of speaking and neither is the audience. "We" in this utterance includes the space of the narrator again, as well as some imagined people living there but not the audience of the report and the deictic center has once again shifted from some neutral deictic center to "Maputo" which becomes the temporary "present" location for the description. In (a), the gestural viewpoint adopted is that of the speaker, pointing to a particular location on the map (New York City) that establishes a first reference point, but the deictic center is then shifted south and north of New York in (b) and (c) which reveals not the viewpoint of the speaker but that of a narrator moving along the coast as he follows the expected progression of the represented snow front. The deictic center has shifted from New York City to the East end of Long Island which enables the narrator to express a distal information in speech with "all the way up". In (d), the viewpoint is again that of the speaker standing in front of the map (and actually looking at the top right corner of the map where the expected time is noted in script) and addressing the viewers so we are back to a speaker/audience relationship, instead of the previous narrator/narrated object point of view.

As we can therefore see, switches in viewpoint may occur over the course of a verbal utterance, but may also be visible in the gestures made by the weather person. So far, gestures and speech have been congruent in the expression of viewpoint. We will now look at examples in which the viewpoint expressed in speech is not the same as the viewpoint expressed in gestures.

Viewpoint mismatches in speech and gesture

Example ( 7) below was uttered in the same CBS weather report as the extract just mentioned, whose head office is located in New York. The weather reporter is talking of a blizzard over New York City: The verbal viewpoint adopted in this example is multiple since the deictic center shown by the use of "we" is New York City, and this is the space of the speaker, of at least part of the audience, as well as the deictic center of the narrator so the deictic center adopted lies at the intersection of the three spaces as represented in Figure 6 below: Let's now look at the pointing gesture made by the speaker when uttering example [START_REF] Lyons | Deixis, space and time[END_REF]. Index finger extended the speaker points to New York on the map and draws a short a line towards the right, as shown in the left-hand side picture of Figure 7: With this gesture, the weatherman illustrates the route taken by the blizzard overnight away from the city. If we consider the viewpoint of the audience and narrator, then the gesture moves away from the deictic center (a point on the map representing New York City), and this is consistent with the semantics of "off" in speech. But at this time of the report, the Deictic center speaker is standing on the right side of the map, which involves that while saying "off to the East", the direction of his gesture is towards himself, thus creating a mismatch in between verbal content and gesture. The mismatch could have been avoided with a shift of the speaker to the other side of the map as he does later in the video.

Another mismatch is observed in example (8) As he is describing the temperatures in example ( 8), the weatherman is standing beside the map, facing the audience and gesturing but not pointing at the map. The deictic center is neutral, i.e. located towards the middle of the region of the US he is describing. This deictic center is still reflected in speech when he utters "here comes the next front in", with the use of the verb "come in" which is appropriate from a viewpoint located in the middle of the map. The gesture however is made from the speaker's viewpoint, since the weatherman makes a sweeping movement of the end towards the middle of the map.

The viewpoint in gesture is then external to the map as it depicts the route the rain front will adopt.

In example (9) below, the reporter makes a continuous pointing gesture towards the map as she utters:

(9)

The temperatures are rising as we head for the South. This is the same weather woman as for example (5) and we've already said that while describing the weather in parts of Africa, she is not in Africa herself and thus does not share the physical space with the object of her description nor does the audience. So when she says "we head for the South", she adopts the narrator's point of view, as well as the viewpoint of the viewers, not a speaker's point of view. Her gesture, however, is made from the speaker's viewpoint, rather than from the narrator's: she makes a single static gesture to her left, but during the preparation phase of her gesture, the map begins to scroll down so that her pointing gesture encompasses an area of the map, but does not in itself encode movement southward.

Shifts in deictic center

As While uttering this sentence, the speaker makes a sweeping gesture to and fro along the border separating England and Scotland. While the whole gesture is speaker-oriented and map external, speech functions exactly as in example [START_REF] Sloetjes | Annotation by category -ELAN and ISO DCR[END_REF], with a narrative shift from a point in Scotland as the speaker utters "stick South" to a point in the South of England as he utters "in the far North". The role of the gesture in this example is not to accompany the shift in deictic center, but rather to oppose the two locations implied in speech.

Conclusion

This paper presented a preliminary analysis of personal and spatial deixis in weather reports, with a focus on the mapping of gestures with stretches of speech. Beyond the type of map (medium) used in each report, static or dynamic, which has an impact on gesture, creating possible mismatches between the two, it is especially in terms of viewpoint and deictic center that weather reports show real complexity.

In terms of personal deixis, the viewpoint adopted in weather reports corresponds to the "here and now" of the speaker in a relative frame of reference (map-external viewpoint), of a narrator transposed into the absolute frame of reference of the map itself, and/or of viewers (either as people directly sharing the space under description or not). In this Bakhtinian polyphony of voices, gesture and speech may be perfectly congruent as far as viewpoint is concerned, but we have seen as well that a certain viewpoint may be adopted in a modality whereas the viewpoint adopted in the other modality may be different, which is very close to what Fricke ( [START_REF] Fricke | The impact of cospeech gestures on linguistic deixis theory[END_REF]) showed in a face-to-face interaction of a route direction. The externality/internality of viewpoints regarding maps is reminiscent of the distinction made by McNeill ( [START_REF] Mcneill | Hand and Mind: What Gestures Reveal about Thought[END_REF] and [START_REF] Mcneill | Gesture and Thought[END_REF]) for gesture between character or observer-viewpoint.

In terms of spatial deixis, the deictic center is constantly changing as the description of the weather report progresses. Once again, the frequent shifts may result in mismatches in gesture and speech, although this is not necessarily the case.

Because of the already extreme complexity of medium, viewpoint and reference points, the temporal aspects of weather reports were left aside in this paper, but as a weather report is by nature linked with the passing of time, establishing links between past, present and expected weather in the future, all in the condensed form of a one or two-minute presentation, temporal deixis should be included in further studies of weather description. Another possible line of research would be to compare the description of a same event by different channels or in different countries.

Figure 1 :

 1 Figure 1: Traditional background projection screen (left) [17] and oblique screen (right) [18] used by different channels for weather reports.

Figure 2 :

 2 Figure 2: Pointing at the South-East area of the UK on a smaller scale map (left) and larger scale map (right) [19].

Figure 3 :

 3 Figure 3: Two pointing gestures in example (1): effect of scrolling map ([19]).

Figure 4 :

 4 Figure 4: Two pointing gestures in example (3): speaker viewpoint ([20]).

Example ( 6 )Figure 5 :

 65 Figure 5: Four pointing gestures illustrating viewpoint switches over the course of an utterance ([21]).

( 7 )

 7 While we were sleeping [it just pushed a little bit more off to the East].

Figure 6 :

 6 Figure 6: Deictic center at the intersection of speaker (S), narrator (N) and audience (A) space in example (7).

Figure 7 :

 7 Figure 7: Left: pointing gesture made by the weatherman in example (7); right: position of weatherman later in the video ([21]).

( 8 )

 8 Temperatures a little bit warmer, still running low, somewhere about 70 to 75 [and here comes the next front in] which will arrive late Sunday.

Figure 8 :

 8 Figure 8: Dynamic pointing gesture produced during example (8) [22].

Figure 9 :

 9 Figure 9: Pointing gesture made in example (9). Arm position during preparation phase (left) and at the end of preparation (right) [20].

Figure 10 :

 10 Figure 10: Sequence of gestures produced during example (10) [19]. Just before this stretch of talk, the weatherman was describing rainy conditions over Northern Ireland, with an area of rain extending northward (shown in blue on the map). The pointing gesture with index and middle finger extended in (a) enables the narrator to establish a new deictic center located in the middle of Scotland, which serves as a new reference point for the description of the path that will be adopted by the water front over the coming hours. In speech, this shift of deictic center is shown by the use of discourse marker "now" which does not refer to the present time of speaking but opens up a new focus of attention in a new discourse unit. The direction of the water front is itself depicted in the small sweeping hand movement downward illustrated in (b) and (c), with an open palm covering the area, that matches the accompanying speech "sink ... southward". The flip of the hand shown in (d) indicates a new shift in deictic center that is present in speech as well: "the far North of England" implies that the reference point is somewhere towards the South of England, and that matches the location of the speaker in London, who is momentarily abandoning the neutral viewpoint of narrator. Before concluding, let us return to the example given in the title of this paper, and which is reproduced below in (11): (11) [This area of rain will stick South in the far North].

Figure 11 :

 11 Figure 11: Pointing gesture made in example (11) [19].

Table 1 .

 1 Channel, location of head offices, and number of reports downloaded for the present study.

	Channel	Location of head	Nb of
		offices	reports
	National Weather Channel	Atlantla, US	2
	Local CBS	New York City, US	1
	BBC weather	London, UK	4
	eNCA	Johannesburg,	1
		South Africa
	Local CBS	Los Angeles, US	1
	CNN	Atlanta, US	1

Acknowledgements

We would like to thank the students of the Discourse Analysis seminar at the University of Nantes, especially Funmbi Fakua and Christophe Gilson for their comments on our presentation of weather forecasts.


V Baudry

H Mouslim

Aurélien Babarit

Estimation numérique de la matrice de production d'énergie du système houlomoteur Pelamis PII

Estimation numérique de la matrice de production d'énergie du système houlomoteur Pelamis PII

Virginie Baudry (1) , Hakim Mouslim, Aurélien Babarit

Laboratoire LHEEA -CNRS UMR6598 Ecole Centrale de Nantes, LUNAM Université 1, rue de la Noë 44321 Nantes Cedex 3, France (1) : virginie.baudry@ec-nantes.fr Le projet SEAWATT a pour objectif d'installer une ferme houlomotrice de 30 MW au large de Saint Pierre sur l'Ile de la Réunion. L'originalité du projet repose sur le volet SEAWATT R&D dont l'objectif est de développer un système de stockage pneumatique de l'énergie pour une ferme de Pelamis PII. Le dimensionnement de ce système nécessite des enregistrements temporels caractéristiques des flux de puissance instantanée. Il est donc nécessaire de se doter d'un simulateur numérique pour obtenir ces flux de puissance. Son développement a été effectué par l'ECN et l'objet de cette publication est de présenter la méthodologie et les résultats obtenus.

Le Pelamis PII mesure 180m de long, il a un diamètre de 4m, un déplacement de 1300 tonnes, et est constitué de 5 tronçons et de 4 unités de 'Power Take Off' ; il est ainsi plus long et de plus gros diamètre que son prédécesseur le Pelamis PI (150m de long, 3.5m de diamètre).

Pour la modélisation, les hypothèses suivantes ont été effectuées :

1. Mouvement plan : nous considérons un seul degré de rotation en tangage de chacun des tronçons du Pelamis. L'ensemble du système présente également un degré de liberté en cavalament et en pilonnement. Ces résultats indiquent que le modèle numérique est apte à prédire correctement la réponse du système, et est à donc à même de fournir les données nécessaires au dimensionnement du système de stockage dans la suite du projet.

Mouvements

Figure 1 :Figure 2 :

 12 Figure 1 : Le système houlomoteur Pelamis PII en mer

  et houle de faible amplitude. Les effets du second ordre sont négligés et l'équation du mouvement est linéarisée. Les interactions fluide-structure sont représentées dans le cadre d'une théorie potentielle linéarisée. 3. Le convertisseur est modélisé par un amortissement et une raideur linéaire.

Sous ces hypothèses, les équations du mouvement ont été écrites, puis implémentées numériquement. Elles sont résolues pour des cas de houle régulière et irrégulière, et permettent ainsi d'effectuer les calculs suivants :


Stefen Chan

Wai Tim

Michele Rombaut

Denis Pellerin

REJECTION-BASED CLASSIFICATION FOR ACTION RECOGNITION USING A SPATIO-TEMPORAL DICTIONARY

Keywords: Dictionary Learning, Action Recognition, Classification, Videos, Spatio-temporal patches

This paper presents a method for human action recognition in videos which learns a dictionary whose atoms are spatiotemporal patches. We use these gray-level spatio-temporal patches to learn motion patterns inside the videos. This method also relies on a part-based human detector in order to segment and narrow down several interesting regions inside the videos without a need for bounding boxes annotations. We show that the utilization of these parts improves the classification performance. We introduce a rejection-based classification method which is based on a Support Vector Machine. This method has been tested on UCF sports action dataset with good results.

INTRODUCTION

The research on action recognition has developed a lot in the last years along with the rise of video contents, especially because its applications are numerous in surveillance, automatic video annotations or entertainment. Generally, it consists in extracting features either globally (or in successive frames) [START_REF] Efros | Recognizing action at a distance[END_REF][START_REF] Schindler | Action snippets: How many frames does human action recognition require?[END_REF] or locally [START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF]. The goal is to classify some human activities using the data extracted from videos.

Techniques based on dictionaries and sparse representations [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF][START_REF] Guha | Learning sparse representations for human action recognition[END_REF][START_REF] Somasundaram | Action recognition using global spatio-temporal features derived from sparse representations[END_REF] have emerged in action recognition because of the possibility to represent complex patterns using a few dictionary elements. These methods rely on the creation of a dictionary which can encode effectively the information contained in an image.

In this paper, we propose a method for human action recognition in the context of gray-level video sequences. This method learns a dictionary of spatio-temporal atoms coupled with a part-based human detector to select interesting spatio-temporal regions inside a video. We also introduce an original three-stepped rejection-based classification method based on a SVM in order to improve the results. The paper is organized as follows: Section 2 presents the proposed action recognition method, Section 3 describes the results obtained and Section 4 presents the conclusions.

METHOD FRAMEWORK

The proposed method consists in classifying temporal blocks composed of several frames and containing a human who perfoms one particular action which corresponds to a class.

We call temporal block t successive frames of a video. In these blocks, we define spatio-temporal volumes which correspond to the same spatial regions taken in successive frames inside the videos. These spatio-temporal volumes are localized around areas of interest. Spatio-temporal volumes themselves are composed of small spatio-temporal patches which are defined as a succession of spatial image patches (see Figure 1). A dictionary is a learned collection of such patches called atoms. The method described below is based on a previous work [START_REF] Wai Tim | Dictionary of gray-level 3d patches for action recognition[END_REF] and relies on a spatio-temporal patch-based dictionary to represent spatio-temporal volumes. In this paper, we also use a part-based human representation to narrow down the image to interesting regions. This method is described in 3 parts: (i) Dictionary learning, (ii) Spatio-temporal objects and (iii) Classification with rejection.

Dictionary Learning

At first, dictionary learning methods were used for denoising and inpainting [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF][START_REF] Aharon | K-svd: an algorithm for designing overcomplete dictionaries for sparse representation[END_REF] and now, different methods exist in the literature to learn dictionaries for sparse representations. Some of them are specifically designed for classification, for example DKSVD [START_REF] Zhang | Discriminative k-svd for dictionary learning in face recognition[END_REF] or GDDL [START_REF] Suo | Structured dictionary learning for classification[END_REF]. Dictionarybased methods got great success, in particular, in face recognition applications. However, these methods are often application specific and cannot be straightforwardly used in action recognition because they rely on the alignment of the images.

We want to learn a dictionary on spatio-temporal patches in order to describe movement patterns. We cannot utilize large patches and learn a dictionary that can efficiently discriminate between the different classes because the actions are complex and we cannot align these images. As a consequence, we are using small patches compared to the spatiotemporal volumes. Since the patches are small compared to the complexity of the data, there may be no specific or discriminative atoms for each class (different classes may utilize similar atoms) and the recognition is done solely on the proportion of used atoms. That is why we chose to implement K-SVD [START_REF] Aharon | K-svd: an algorithm for designing overcomplete dictionaries for sparse representation[END_REF] for learning the dictionary.

Let p be a spatio-temporal gray-level patch of size (s × s × t), with s being the size of a square patch in the spatial dimensions and t being the number of frames considered in the temporal dimension. The patch p norm is the patch p whose set of pixels are normalized so that it has zero mean and unit norm.

Let Y = [p norm,1 , p norm,2 , ..., p norm,m ] ∈ R n×m be a a matrix composed of spatio-temporal patches, with m being the size of the dataset, n the dimension of the patches and D = [d 1 , d 2 , ..., d Natoms ] ∈ R n×Natoms be the dictionary of N atoms atoms d k , where the number N atoms is chosen empirically.

The dictionary learning algorithm K-SVD [START_REF] Aharon | K-svd: an algorithm for designing overcomplete dictionaries for sparse representation[END_REF] is an iterative algorithm which can solve the optimization problem. The formulation of the dictionary learning algorithm is:

min D,X { Y -DX 2 F } such that ∀i ∈ [1, m] , x i 0 ≤ T 0 (1)
where X = [x 1 , x 2 , ..., x m ] ∈ R Natoms×m contains the coefficients of the decomposition of Y using the dictionary D.

x i = (α j ) j∈[1,Natoms] is a column vector from X describing p norm,i and x i 0 is the norm that counts the number of non-zero entry of the vector. • F is the Frobenius norm:

A ∈ R n×m , A F = n i=1 m j=1 |a ij | 2 . T 0 is the maxi- mum of non-zero entries.
This algorithm is performed in two steps: first by optimizing the codes X with a fixed dictionary and secondly by optimizing D with respect to X.

The output of this learning step is a dictionary D composed of N atoms (Figure 2). Then, we can compute a sparse representation of a spatio-temporal volume Y based on the dictionary.

t = 1 t = 2 t = 3 Fig. 2.
Example of 20 atoms of size (5 × 5 × 3) pixels from a learned dictionary with K-SVD.

Spatio-temporal objects

Our objective is to classify successive frames (temporal block) of the video. To do that, we propose to select interesting regions within the images (see Figure 1) based on the results of a part-based human detection algorithm.

Part-based human detection

We perform the selection of interesting regions within the images thanks to an existing part-based human detection algorithm [START_REF] Yang | Articulated human detection with flexible mixtures of parts[END_REF]. The algorithm is based on a deformable parts model capable of handling large variations in the human poses. The output of the algorithm is a list of square bounding boxes of fixed size corresponding to the localizations of the different parts of the model. In the model chosen, the parts are positioned on specific regions of the human body (head, right/left arm, right/left leg ...). The original part-based model contains 26 different parts and we selected only 9 because they approximatively cover the body (Figure 3) and in order to limit the dimension of the block representation (see Section 2.2.2).

From each of the parts, we construct a spatio-temporal volume Y (see Figure 1) by extending the localization of the parts in the temporal dimension.

Signature computation

We want to classify the human actions represented in videos using the spatio-temporal volumes described in the previous section.

Each volume Y can be described with a histogram:

h = m i=1
x i with the coefficient vectors x i of all the patches within Y . Since we are using 9 parts, we can obtain 9 different histograms h (j) , j = {1, ..9}. The final signature is the concatenation of the histograms for all of the individual parts: 1) , ..., h (j) ]. The final dimension of the signature is N parts × N atoms .

h block = [h (

Classification with rejection

Once we obtain the signatures for each temporal block, we want to retrieve the action classes for each video. The extracted features consist in signatures obtained for each block of t frames, meaning that, for a video of L frames containing a single action, we can get up to L -t + 1 signatures if we use overlapping blocks of frames. We have developed a method that gives a label to each block. The label of the video is obtained by a voting procedure on all the blocks of the video, but since the dimension of the patches and the number of frames t taken into account in each block are small, some signatures may be ambiguous leading to classification errors. That is why we decided to add an extra "rejection" class which regroups these ambiguous signatures when training the SVM. Normally, all the signatures extracted from the blocks for the same video share the same label: as a consequence, the objective of this new class is to prevent some signatures that could be ambiguous from voting for a label.

The SVM is trained in three steps.

In the first step, we divide the training set into groups where each group is the set of signatures belonging to a given video of L frames. Indeed, the signatures within the same video normally share a lot of similarities and thus cannot be processed separately. Then we do a leave-one-group-out setup on the training set to optimize the parameters of the SVM.

In the second step, we use the previous leave-one-groupout setup with the optimized parameters and we look for each signature misclassified in each group. The misclassified signatures are moved into the "rejection" class (see Figure 4).

In the third step, a final classifier is learned using all the signatures and all the classes (including the "rejection" class) as input. The final label for a given video in the test set is obtained by voting using the set of signatures of the videos. Each signature classified in the rejection class is removed from the vote.

We have found that this method can significantly improve the classification results. However, we have to carefully balance the number of elements in the "rejection" class after the second step. Otherwise, it happens that, during the testing phase, all the signatures of a video can end up classified in the "rejection" class. We tried different rules for moving an element into the "rejection" class. The results are presented in Section 3.

EXPERIMENTATIONS

We tested the proposed algorithm of the UCF sports action dataset [START_REF] Rodriguez | Action mach: A spatio-temporal maximum average correlation height filter for action recognition[END_REF]. This dataset is normally composed of 10 classes: "Walking", "Swinging", "Skateboarding", "Running", "Riding horse", "Lifting", "Kicking", "Playing golf" and "Diving". The resolution of the videos is (720 × 480) pixels. We decided to remove the class "Lifting" because of the lack of annotations. In total, we used 9 classes and 140 videos.

For the classification of the videos, we used libLinear [START_REF] Fan | Liblinear: A library for large linear classification[END_REF]. We did a leave-one-group-out using all the signatures computed for a single video as a group. The size of the patches considered is (5 × 5 × 3) pixels. With the selected temporal size t = 3, we obtained between 20 and 90 signatures for each video depending on its length. Each human was described with 9 volumes of (24 × 24 × 3) pixels computed with the part-based detector. The classification label was determined by votes using all the signatures (or the signatures not classified in the "rejection" class). Table 1 shows the different performances with and without the use of the part-based detector and the "rejection" class. We reach 86.4% accuracy with 9 parts and a dictionary D of N atoms = 150 atoms against 72.1% when considering only one full bounding box including all the body. We chose to take the sparsity T 0 = 1 for our experiments. In our previous work, we showed that taking any low value for T 0 did not change the results much but T 0 = 1 gave us the best performance. The choice of patch size is tied with the dictionary size for overcompleteness. A larger dictionary also leads to larger signature size. Empirically, we found that the choice of (5 × 5 × 3) for the patch size was a good compromise.

We also tried learning a specific dictionary for each individual part used in our method but the results obtained were the same. Our hypothesis is that the global motion information of the parts is more important than the local precision in the shape. However, we can also add the precision of the part detection is not perfect for some classes (for example, because of the blur). Moreover, we note that even if many of the boxes are not well-localized, it still improves the classification performance by a good margin (see Table 1). We believe that, when using a single full bounding box, too many spatial information is lost during the pooling. The fact of using the part detector is a way to reintroduce some spatial information and narrowing down some interesting image regions.

We tried different rules for the "rejection" class. The first rule tested is to move the misclassified signatures during the first learning step into the "rejection" class. However, it happened that in some cases, for the test set, all the signatures for a given video could end up rejected meaning that we had to use the classifier learned without our extra class. To prevent that, we tried softer rules: instead of moving all misclassified signatures into the extra class, we only moved signatures with a probability to belong to its true class below a chosen value (see Table 2). These probabilies can be obtained by adding an Methods Accuracy Gray-level + Full bounding boxes 72.1% Gray-level + Part-based detector 80.0% Gray-level + Part-based detector 86.4% (SVM with basic "rejection" class) Table 1. Performance comparison for our method in different conditions. Dictionary size = 150, Sparsity T 0 = 1, video labels obtained by voting using the signatures of the video. option in libLinear and are computed using logistic regression for each class. We can see that our extra learning step serves its purpose since the accuracy at signature level jumps from 53.6% to about 80%. Moreover, we can also observe that balancing the "rejection" class can lead to improved results: going down from 50% rejected signatures to 35% leads to a gain of about 2% in accuracy because of the effects described above. Dictionary size = 150, Sparsity T 0 = 1, video labels obtained by voting using the signatures of the video. The table gives the video label classification accuracy (obtained after voting), the signature classification accuracy and the proportion of signatures rejectedby the classification.

Rejection rule

We compare the proposed method with different algorithms of the literature in the Table 3. We can see that our method achieves good results. Even if the descriptors obtained with the part-based detector alone only reach 80%, the combination of the proposed descriptors and classification method perform really well. The size of the codebook used in our method is 150 compared to 4000 for [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF] and 40 for [START_REF] Qiu | Sparse dictionarybased representation and recognition of action attributes[END_REF] even if the final dimension of the signatures is 1350. Speed wise, the experiments were done on MATLAB so a significant gain in speed is possible: the part-based human detector was the limiting factor with about 0.5 frame per second on a modern computer, once the parts are extracted we can compute about 7 signatures per second. Results from [START_REF] Wu | Action recognition using context and appearance distribution features[END_REF][START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] are given as a comparison: they use techniques different from dictionary-based approach and show that the proposed method is competitive.

Methods

Accuracy Dictionary based methods H. Wang et al. [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF] 85.6% Q. Qiu et al. [START_REF] Qiu | Sparse dictionarybased representation and recognition of action attributes[END_REF] 83.6% T. Guha et al. [START_REF] Guha | Learning sparse representations for human action recognition[END_REF] 83.8% Proposed method 88.6% Other methods X. Wu et al. [START_REF] Wu | Action recognition using context and appearance distribution features[END_REF] 91.3% H. Wang et al. [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] 88.0% Both dictionary-based and non dictionary-based methods are presented.

CONCLUSION

Given a raw video as input, the proposed dictionary-based action recognition method performs efficiently. Despite the small dimension of the patches, we show that using localized spatio-temporal volumes improves the results. We also introduced a rejection-based classification method to select the most descriptive signatures to select the labels. The method has been tested on UCF sports action dataset with good results.

For future work, we are looking for a way to take into account the evolution of the signatures extracted from successive temporal blocks instead of treating them separately. We are also working on more recent databases like UCF50.

Fig. 1 .

 1 Fig. 1. Example of a temporal block of t = 3 frames described with 2 spatio-temporal volumes. Each volume is composed of a collection of small spatio-temporal patches.

  (a) Articulated human (b) Selected boxes

Fig. 3 .

 3 Fig. 3. Example of bounding boxes extracted by [12]. (a) is an example of a full part-based human detection. (b) is an example of the 9 parts selected. The images are obtained from a video of the UCF dataset from the class "Walking".

  (a) One iteration of the leave-one-group-out in the first step. (green = well classified, red = misclassified) (b) One signature of Video 1 is moved to "rejection" class D in the second step.

Fig. 4 .

 4 Fig. 4. Example of the second step of the proposed classification method with 6 videos and 3 classes of actions A, B and C. We use a Leave-one-group-out setup with the signatures of each video as a group. Each signature misclassified during this step goes into the "rejection" class. At the end of this step, the whole training set (signatures) with the extra class serves to learn the final classifier.

Table 2 .

 2 Performance comparison for different rejection rules.

Table 3 .

 3 Performance comparison for different features and methods for the classification on UCF Sports action dataset.

This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025).