Olivier Traxer

WJU special edition: surgical and medical management of stones

The development of urology over the years has been advancing along with that of stone disease. The management of patients affected with urolithiasis remains a major public health issue worldwide with a constant increase in its prevalence and incidence. Over the last three decades, the technological innovations have significantly reduced complications of open surgery while optimizing stone-free rate. Moreover, understanding the mechanisms of stone formation has allowed to identify lifestyle changes and specific drugs which should be adopted for reducing the risk of stone recurrence.

Nowadays, it is no longer possible to separate surgical treatment from medical management of urolithiasis. Indeed, all the clinicians approaching patients with urinary stones need to know not only all the surgical techniques available and their indications, but also they should offer them a metabolic evaluation and be able to manage the medical aspects of urolithiasis. This special edition of the World Journal of Urology sought to make an update on the medical and surgical management of stone disease.

The first six articles are focused on the medical aspects of urolithiasis. Thirdly, Margaret Pearle described all the links between diet and kidney stones.

Fourthly, Jean-Philippe Haymann reported all those rare diseases which can be revealed by the discovery of urinary stones.

In addition, since radiology is essential for the evaluation of urinary stones, I asked to Raphaëlle Renard-Penna to describe the developments of imaging techniques in this field. Finally, Palle Osther explained the medical treatment of acute renal colic, which is still the most common symptom of urinary stones, and its evolution over the last years focusing also on the indication for medical expulsive therapy (MET).

The second part of this "special issue" is purely centered on all the different treatment modalities.

Thomas Knoll provided a focus on extracorporeal lithotripsy, although this option seems to have lost a bit of appeal among the urological community compared with percutaneous nephrolithotomy (PCNL) and to the recent spread of ureterorenoscopy (URS).

In addition, Jean de la Rosette summarized the results of the international survey of CROES (Clinical Research Office of Endourological Society) on the PCNL, and Mahesh Desai made a specific point on the miniaturization of technology and equipment in the field of percutaneous approach.

Finally, three articles are dedicated to the youngest, most innovative and most promising minimally invasive technique: the flexible ureterorenoscopy with laser fragmentation of the stone (f-URS).

Glenn Preminger exposed all the disposable equipment necessary for f-URS, while Michael Grasso described the different ureteroscopes and lasers available on the market.

In conclusion, Guido Giusti evaluated the state of the art of f-URS when applied in challenging cases and with particular indications. I guess this "special issue" will fascinate the readers, as the management of stone disease patients does with me in my daily clinical practice.

A special thanks goes to all the authors, who really represent leading experts in this field, for their kind contribution to this special edition of the journal.

There is no doubt that this special issue of the World Journal of Urology will remain for a long time a reference for anyone who is interested in endourology and in the medical and surgical management of urinary stones.

Firstly,

  Michel Daudon, who is one of the biggest expert of the biologic mechanisms of stone formation, illustrated a morpho-constitutional classification of urinary stones underlining all the medical and environmental factors correlated with each type and sub-type of stone. Secondly, Luc Valiquette and Julien Letendre explained how to interpret metabolic evaluation of stone patients and clarify what any urologist should know about this issue in 2015.


Florence Bannay

Romain Guillaume

Towards a transparent deliberation protocol Inspired from supply chain collaborative planning *

Keywords: Decision process, Argumentation, Supply Chain Management

In this paper we propose a new deliberation process based on argumentation and bipolar decision making in a context of agreed common knowledge and priorities together with private preferences. This work is inspired from the supply chain management domain and more precisely by the "Collaborative Planning, Forecasting and Replenishment" model which aims at selecting a procurement plan in collaborative supply chains.

Introduction

In the supply chain management (SCM) domain, collaborative planning is the process of finding a production plan which is suitable for every agent involved in the supply chain (SC). In this domain, a useful requirement is that the agents have agreed about some general conventions concerning the eligible criteria wrt production plans (avoiding more discussions about criteria). From Artificial Intelligence point of view, the SCM collaborative plan problem is a particular case of a collaborative decision given a background consensual knowledge and the particular preferences of each agent. This decision is the selection of a candidate according to a global convention and according to the precise arguments uttered by them about each candidate. In the classification of dialogs given by Walton and Krabbe [START_REF] Walton | Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning[END_REF], we are facing a deliberation process, since the initial situation is a dilemma (the agents need to find a good plan among several options), each agent aims at coordinating its goals and actions with the others in order to decide the best course of action that will be beneficial for all the participants. In existing process, supply chain participants are compelled to provide numerical data (which may require some expensive computation, or may be based on some debatable numerical evaluations). Our main goal is to design a formal framework in which (qualitative) arguments in favor or against a plan maybe expressed and may interact with each-other. This framework will enable to conceive systems that could facilitate and guide the agents to converge rationally towards a set of consensual plans. Moreover, the production plan that will be chosen should have a guaranteed quality: if the selection leads to a set of plans that are under an admissibility threshold then the process is aborted and an exception is raised. Otherwise, if several plans are admissible then the customer (or the most important actor playing a role similar to a customer wrt a supplier ( [START_REF] Marcotte | Cooperation models for supply chain management[END_REF]) has usually the last choice. Thus, our aim is twofold, enlarge the expressive power and readability of the decision protocols concerning collaborative planning in SCM domains, import these ideas to AI field in order to propose a new rational model of collaborative decision making (or deliberation) under clear admissibility criteria. More precisely we propose a new deliberation process based on bipolar argumentation where the arguments, their incompatibilities (called attacks) and their importance levels are commonly agreed before the deliberation. We directly apply this process for collaborative planning in supply chain using CPFR R (see Section 2.3). In AI literature some models have already been proposed based on a bipolar view of alternatives. Indeed, it is often the case that human people evaluate the possible alternatives considering positive and negative aspects separately [START_REF] Slovic | Rational actors or rational fools? Implications of the affect heuristic for behavioral economics[END_REF]. Moreover, argumentation has already been proposed to govern decision making in a negotiation context (see for instance [START_REF] Amgoud | A formal analysis of the role of argumentation in negotiation dialogues[END_REF] and [START_REF] Rahwan | Argumentation-based negotiation[END_REF] for a survey). But, as far as we know, the use of bipolar argumentation in order to govern a deliberation process under instantiated arguments had never been studied. Moreover, in context of supply chain the agents only require to obtain admissible production plan and do not necessarily need to class them (in the worst case the best plan can be inadmissible, in other cases every plan may be admissible). Hence, we propose and study the rationality and the calculability of the admissible set. Furthermore, the notion of efficiency and simplicity that are central in SCM domain can bring a new perspective for modeling deliberation process in AI. We first recall the basis of qualitative bipolar decision, classical argumentation and supply chain planning. In a second step, we define a common decision making structure gathering the concepts of bipolarity and argumentation, then we propose admissibility thresholds. We apply this deliberation process to an example of collaborative planning.

Background

Qualitative bipolar decision

In this paper we focus on the problem of qualitative bipolar decision, this problem can be formalized as follows. Let C be a finite set of potential choices and A be a set of arguments (or criteria) viewed as decision attributes ranging on a bipolar scale {-, +}. More precisely if a ∈ A and c ∈ C then a(c) is either an argument in favor of the choice c (when a(c) = +) or against it (a(c) = -). Let us consider a totally ordered scale level expressing the relative importance of arguments:

∀a 1 , a 2 ∈ A, if level(a 1 ) > level(a 2 )
then a 2 is more important than a 1 (the best level is 1). In this paper, a set A ⊆ A of arguments is called a bipolar leveled set of arguments abbreviated bla, and A + = {a | a(c) = +} and A -= {a | a(c) = -} denote respectively the set of arguments in favor and against the choice c. The problem of rank-ordering the possible choices has been well studied in the literature. For this purpose, decision rules which build preference relations between decisions were proposed [START_REF] Jf. Bonnefon | An overview of bipolar qualitative decision rules[END_REF]. Most approaches in the literature focus on preferences but do not discus the problem of admissibility threshold. In this paper we propose such kind of thresholds. Note that classical models do not take into account the conflicts that may occur between arguments, indeed the presence of some arguments may decrease the validity of other arguments. In this paper we propose a model that takes into account both the importance of arguments and the relations between them.

Classical argumentation

In the abstract argumentation theory, Dung [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] has defined several ways, called "semantics", to select admissible arguments. Given a graph (X, R), called argumentation system where X is a set of arguments and R is a binary relation on X called attack, the selected sets of arguments S ∈ X, called extensions, should be conflict free (i.e. should not contain internal attacks). Most of the extensions proposed by Dung are based on a defense notion1 that is not very intuitive in our context. Including defended arguments would amount to accept every positive argument as soon as one positive argument is not attacked (and similarly for negative arguments). Moreover, as already noticed by Amgoud and Vesic [2] "Dung's framework cannot be used for decision making since it simply selects groups of arguments containing at last, one of the strongest (positive or negative) arguments". Hence, Dung's framework is not useful in our context: it will give the same results with a more complex computation, as the results obtained by simply selecting the unattacked arguments.

Supply chain planning

A supply chain is "a network of connected and interdependent organizations mutually and cooperatively working together to control, manage and improve the flow of materials and information from suppliers to end users" [START_REF] Christopher | Logistics And Supply Chain Management: Creating Value-Adding Networks[END_REF]. Handling a supply chain is called supply chain management and can be defined as "the management of upstream and downstream relationships with suppliers and customers to deliver superior customer value at less cost to the supply chain as a whole" [START_REF] Christopher | Logistics And Supply Chain Management: Creating Value-Adding Networks[END_REF]. Two types of supply chains can be distinguished: decentralized supply chains (SC where actors are independents) and centralized supply chains (SC where decision authority and information is hold by one single party) [START_REF] Albrecht | Supply Chain Coordination Mechanisms: New Approaches for Collaborative Planning[END_REF]. In this paper we focus on decentralized supply chains. The key of successful SCM for decentralized supply chains is the collaborative process. The collaborative processes are usually characterized by a set of point-to-point customer / supplier relationships with partial information sharing [START_REF] Dudek | Collaborative Planning in Supply Chains: A Negotiation-based Approach[END_REF]: one or several procurement plans are built and propagated through the supply chain using negotiation processes. One of the most popular collaborative processes has been standardized under the name of "Collaborative Planning, Forecasting and Replenishment" (CPFR R ) [START_REF] Ireland | Supply Chain Collaboration: How To Implement CPFR And Other Best Collaborative Practices[END_REF]. It is also a registered trademark of Voluntary Inter-industry Commerce Standards (VICS). The CPFR R is a hierarchical process (strategic, tactical and operational) and is decomposed into four main tasks: Strategy and Planning, Demand and Supply Management, Execution and Analysis. In this paper, we are interested by the collaborative task of Demand and Supply Management, and more precisely by Order planning/forecasting and replenishment planning which are tasks that aim to determine future product ordering and some delivery requirements based upon the sales forecast, inventory positions, transit lead times, and other factors. In the literature of production planning, the collaborative order planning and replenishment planning are based on linear programming and/or mixed integer programming where the actors negotiate about a cost function which aggregates the inventory, the capacity, the production consequences ... (see [START_REF] Dudek | Collaborative Planning in Supply Chains: A Negotiation-based Approach[END_REF] and [START_REF] Albrecht | Supply Chain Coordination Mechanisms: New Approaches for Collaborative Planning[END_REF] for a survey). Since some coefficients of the cost function are difficult to estimate for these actors, the analyses of resulting plans become difficult. Another method, is to propose a set of plans to the supplier. Then the supplier evaluates the plans in terms of risk of back-ordering [START_REF] Guillaume | Management of the risk of backorders in a mto-ato/mts context under imperfect requirements[END_REF] and chooses the less risky plan. However, the risk of back-ordering is still poor information regarding the multi-dimension nature of evaluation of a production planning process [START_REF] Lu | Collaborative design and analysis of supply chain network management key processes model[END_REF]. Another part of SCM literature focuses on the actor planning process and on how to take into account the multi-objective nature of the problem and the qualitative evaluation of a production plan. For these purposes, the fuzzy goal programming approach [START_REF] Jamalnia | A hybrid fuzzy goal programming approach with different goal priorities to aggregate production planning[END_REF] and the fuzzy multi-objective approach [START_REF] Baykasoglu | Multi-objective aggregate production planning with fuzzy parameters[END_REF] have been proposed. The fuzzy goal programming approach consists in defining goals in terms of fuzzy intervals, the more the result belongs to the goal the more pleased is the decision maker. The fuzzy multi-objective approach takes into account the fuzziness of the importance of the criteria. For the problem of production distribution planning, a collaborative fuzzy programming approach has been developed in [START_REF] Selim | Collaborative production-distribution planning in supply chain: A fuzzy goal programming approach[END_REF] which proposes a hierarchy of priority levels for the objective functions of the model, taking into account the dominance of each firm. Those models do not take into account the bipolarity of decision. Our proposal aims to generalize the approach of [START_REF] Guillaume | Management of the risk of backorders in a mto-ato/mts context under imperfect requirements[END_REF] by taking into account the multi-objectives and qualitative nature of the problem using a bipolar argumentative framework.

A Formal Framework for Bipolar Argumentative Deliberation

A collaborative deliberation process involves several agents that want to select a candidate (or an option) in a "rational" manner. In order to do this selection, the agents are going to present arguments in favor or against some candidates. Then the system will aggregate their arguments and return the winner(s). The idea, borrowed from collaborative planning, is that the agents should first agree on general criteria in terms of arguments that may be used in favor or against a decision, and in terms of dominance/defeat relations between those arguments. After this agreement stage which is done once and for all, they can proceed to the selection of the candidates by giving arguments in favor or against some of them according to their private knowledge and preferences.

Bipolar Leveled Features Set

Let C = {c 1 , . . . c n } be a set of candidates (choices) and V = {v 1 , . . . v n } a set of voters, we are going to consider the arguments in favor or against the different candidates from the point of view of each voter. Arguments are entities representing a particular feature that may characterize some candidates, and influence their selection.

Example 1 In supply chain planning the problem is to find a production plan which satisfies both customers and suppliers. Thus, the set of candidates is the set of possible production plans and the customers and the suppliers are the voters. In this example, we consider three plans c 1 , c 2 and c 3 and two voters v 1 (the supplier) and v 2 (the customer).

Definition 1 (instantiated argument) An instantiated argument a v (c) is a predicate based on an argument a, given a voter v and a candidate c. Let I be the set of all instantiated arguments2 , namely,

I = {a v (c) | v ∈ V, c ∈ C, a ∈ A}. Moreover for any c ∈ C, I (c) = {a v (c) | a ∈ A,v ∈ V } denotes the set of instantiated arguments about c.
Given a set of arguments the universe is the structure that contains those arguments together with their interactions.

Definition 2 ((instantiated) universe) A universe (respectively instantiated universe) (A U , R U ) is a graph whose vertices are arguments A U ⊆ A (respectively instantiated arguments A U ⊆ I ) and arcs are conflict

relations between arguments such that R U ⊆ A U × A U .
If R is an attack relation then (a, b) ∈ R means that the argument a defeats the argument b. In our context a is a possible feature, thus (a, b) ∈ R means that if a characterizes a candidate then the fact that b also holds for this candidate has no interest nor influence on the final result (b is invalidated by a). Note that a universe is a Dung argumentation system [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. Now, let us consider that the protagonists have agreed about a consensual universe. This consensual agreement concerns the features that will be used in arguments, it concerns also the way they are divided into two sets (features "in favor of" and features "against" the candidates). Finally the agreement between the participants concerns also the importance accorded to each feature, it is translated by a level, the higher level corresponds to the features that play the smaller role in the decision. Note that the different features in A + are arguments in favor of a candidate hence they are, by nature, opposed to the arguments against this candidate i.e. features in A -(and conversely). This is why a bla will be associated with a graph in which each argument in A + is attacking any less important argument in A - (i.e. belonging to a greater level). For arguments situated at the same level λ, the relation is not so systematic. Let us denote by A λ the set of arguments at level λ, we consider that a relation R λ should be defined in order to express the attacks between A + λ and A - λ . These attacks are not necessarily symmetric. We can be confronted to three relationships between a positive and a negative feature of the same level:

• they may have a completely independent impact on the accuracy to select a candidate having these features: no attack (e.g. in the supply chain management domain, the carbon impact and the stability of the production plan)

• they may have an opposite impact: hence when they appear together the attack is symmetric (e.g., a plan that may be considered both satisfactory and not satisfactory for personal reason)

• they may be related in a way that the presence of the first one outperforms the other (although they have the same level of importance) for instance a plan that may imply a high inventory level for an actor of the supply chain is bad even if this plan makes a quick flow for an other actor. This is why the relation R λ should be given for each level λ.

Definition 3 (universe associated to a bla) Let A be a bla with l levels. The universe associated to A given a family of l binary relations on

A, (R λ ) λ≤l such that ∀λ ∈ 1, l , R λ ⊆ (A + λ × A - λ ) ∪ (A - λ × A + λ ), is the graph (A, R) with R = {(x, y) ∈ (A + × A -) ∪ (A -× A + ) and level(x) < level(y)} ∪ λ∈ 1,l R λ

The instantiated universe associated to a bla A given R and given a set of instantiated arguments I included

in I A,V,C is a graph (I, R I ) where R I is s.t. (a 1v 1 (c 1 ), a 2v 2 (c 2 )) ∈ R I iff c 1 = c 2 and a 1 , a 2 ∈ A and (a 1 , a 2 ) ∈ R.
In other words, an instantiated universe is a graph of instantiated arguments. Each argument is a feature relative to a given candidate according to the opinion of a voter. Attack relations are induced between two arguments that concern the same candidate when the features described in those arguments were consensually said incompatible.

Example 2 This example is inspired from the literature on multi-criteria production planning. The supply chain characteristics and objectives give us concrete features that are used in industrial domain. Here, each argument corresponds to a given industrial objective, then, an argument is enabled for a given production plan if the plan achieves this objective. The definition of arguments is done at the same time as the definition of the bla. We consider that the customer and the supplier deliberate on the basis of the following table A (which is a bla) containing the features that may characterize a plan The three leveled bla proposed in this example is consistent with the standard ideas used in the supply chain management domain. This is why we consider at the most important level that the supply chain has to satisfy the final customer (hence avoid the risk of back-ordering Rb). The supply chain should also have a quick flow of production (Q f ) (hence the inventory level should not be high: Hi). A good production plan should ensure a proper management of the storage (i.e a stable load St and no waste in the storage capacities Hci). Moreover, the supply chain is supposed to have a low risk of failure (Ru f ) and to be cost effective (hence avoid expensive maintenance (Me) and allow for regrouping lots Rl). At the second level, it is interesting (but not crucial) to have stability on production and delivery (a stable plan Sp, a constant quantity delivered Qd and periodic delivery dates Pd) in order to satisfy the workers unless this could increase the cost or induce some errors. Besides, here, the actors are considering that subcontracting (Sc) increases the risk of back-ordering, hence they prefer not to use overtime (Ot) because it is expensive. Temporary workers (Tw) decrease the productivity because they need some learning time.

Since the environmental impact has to be integrated in the decision process (according to the idea of "Green SCM"), the actors should consider carbon impact (Ic). The third level takes into account the good impact on environment (Lic) and the actors personal preferences (a plan may be satisfactory -or not-for personal reason Pr -NPr) witch are not mandatory.

Let us justify the attack relation R 1 of the highest level of this bla, Rb attacks St, Rl and Q f since the primary objective of the supply chain is to fulfill the demand. Rb does not attack Ru f because this feature limits the risk to increase the level of back-ordering. Hi attacks Rl because the actors want to enforce regrouping the lots unless the inventory level becomes to high. The attack between Hi and Q f is different because for a voter the two arguments may coexist (or may be exclusive). So this attack can be described as follow "if the plan makes quick flow for one of the voter then it is acceptable only if this plan does not deal with a high inventory level for an other voter". Hi is attacked by St and Ru f because St or Ru f may justify Hi. Me attacks Ru f since a robust plan is a benefit only if this robustness is not too expensive to guarantee.

Hci is attacked by Q f since it is better to have a quick flow of production than to under-exploit the storage capacity. An example of set of instantiated arguments I B for c 1 , c 2 and c 3 is given below together with a picture of the part of the instantiated bla obtained for candidate c 3 :

I + (c 1 ) I -(c 1 ) I + (c 2 ) I -(c 2 ) I + (c 3 ) I -(c 3 ) 1 Q f v 2 Ru f v 1 , Q f v 1 , Hci v 2 St v 1 2 Sp v 1 Pd v 1 , Qd v 1 Ic v 2 Qd v 2 , Sp v 2 Tw v 1 , Ic v 1 3 Pr v 1 , Pr v 2 , Pr v 1 , Lic v 1 NPr v 2 Pr v 2 NPr v 1 Lic v 2
Part of the bla relative to c3:

Qd v 2 Tw v 1 Sp v 2 Ic v 1 Pr v 2 NPr v 1
Proposition 1 (compactness of inputs) When the bla contains at least two levels, the framework used to express arguments concerning a set of candidates from the point of view of a set of voters with all the corresponding attacks is more compact 4 in the bla framework than in a classical argumentation system.

Decision protocol

Given a bla A, the set of possible candidates C is given to all voters then each voter v:

-divides privately C into two sets C + v and C - v , -instantiates the features concerning each candidate5 c, collected in I v (c), -and finally chooses for each candidate the arguments that he wants to present. For instance, in our example, v 1 's private preferences are

C + v 1 = {c 1 , c 2 }, C - v 1 = {c 3 } and v2's ones are C + v 2 = {c 1 , c 3 }, C - v 2 = {c 2 }.
In order to select admissible candidates, we can focus on the existence of non attacked arguments that are in favor and against them. Given a candidate c, the set of non-attacked arguments concerning c, are denoted S(c) (for "sources"), they are the vertices in I(c) that have no predecessors. We may consider six main cases: Definition 4 (admissibility status) Given a bla A with an associated instantiated universe (I, R I ), and a candidate c, let S(c) = {x ∈ I(c) | ∀y, (y, x) / ∈ R}, the status of c is necessary admissible

(N ad ) if ∅ ⊂ S(c) ⊆ I + (c) -possibly admissible (Π ad ) if S(c) ∩ I + (c) = ∅ -indifferent (Id ad ) if S(c) = ∅ -controversial (Ct ad ) if S(c) ∩ I + (c) = ∅ and S(c) ∩ I -(c) = ∅ -possibly inadmissible (Π ¬ad ) if S(c) ∩ I -(c) = ∅ -necessary inadmissible (N ¬ad ) if ∅ ⊂ S(c) ⊆ I -(c)
In other words, a necessary admissible candidate has an argument in its favor that is unattacked and no unattacked argument against it; a possibly admissible candidate has at least one unattacked argument in its favor. An indifferent candidate has no unattacked arguments in its favor or against it, while a controversial candidate is both supported and criticized by unattacked arguments. A candidate is possibly inadmissible if there is an unattacked argument against it and necessary inadmissible if there is an unattacked argument against it and no unattacked argument in favor of it.

Example 3

The arguments given by v 1 and v 2 about c 1 belong only to I + , thus c 1 ∈ N ad , they seem to agree to select candidate c 1 . c 2 is also in N ad , c 3 is only possibly admissible (c 3 ∈ Π ad ) because Qd v 2 and Tw v 1 are not attacked.

The above definition is related to possibility theory [START_REF] Zadeh | Fuzzy Sets as a Basis for a Theory of Possibility[END_REF][START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF], where necessary (resp. possibly) admissible could be understood as it is certain (resp. possible) that the candidate is admissible. The indifference case is linked to an impossibility to have unattacked arguments in favor and against a candidate, thus an impossibility to decide. However it is not related to a standard definition of possibilistic ignorance about the admissibility of a candidate, which rather corresponds to a controversial candidate that is both possibly admissible and possibly inadmissible. With these definitions we get: The following property reveals that if a candidate is acceptable for all the voters then it is necessary admissible, similarly, if a candidate is unacceptable for all the voters then it is necessary inadmissible.

Proposition 3 (unanimity) Considering a set of voters V using the basic strategy, for any candidate

c ∈ C • If ∀v ∈ V, c ∈ C + (v) and I + (c) = ∅ then c ∈ N ad . • If ∀v ∈ V, c ∈ C -(v) and I -(c) = ∅ then c ∈ N ¬ad .
With these admissibility status, we can propose 3 thresholds of admissibility (from the strongest to the weakest): the first threshold contains the candidates such that all the unattacked arguments about them are positive, the second threshold can be divided into two sets: 2a is the set of candidates under the first threshold together with the candidates for which no unattacked argument concerning them is available (neither positive nor negative), the set 2b tolerates candidates that are concerned by negative unattacked argument provided that they are also concerned at least by one positive unattacked argument. The third threshold is the union of the sets 1, 2a and 2b as shown in the figure below: Note that qualitative explanations of the selection can be drawn on a graph, they are simple and clear compared to quantitative explanations (that may result from complex and obscure numeric computation and that are not necessarily based on a consensual agreement). How to compute the admissible sets? Given a candidate c, we first consider the set of unattacked arguments concerning c (i.e. S(c) = {x ∈ I(c) | ∀y, (y, x) / ∈ R) and then according to this set, we may assign one of the six status (necessary/possibly admissible/inadmissible, indifferent/controversial) to c by using Def. 4. Building the sets N ad , Π ad , Id ad , N ¬ad and Π ¬ad can be done in polynomial time wrt |I|.

Conclusion

This paper introduces a new approach for SCM collaborative planning which is the basis of a new framework for collaborative group decision making. The proposed process is a kind of bipolar argumentative vote with more expressive power than standard vote procedures but also a more compact representation of an argumentation system which focus on admissibility of candidate and not on a ranking. There are numerous benefits of this new decision process. First, our framework follows the standard principles defined by CPFR R that are commonly used by industrialists. Moreover our proposal handles multi-criteria expression which is often not the case for classical approaches or done roughly by using arbitrary aggregation functions. Furthermore, it guarantees a succinct expression. And finally, the qualitative aspect of this approach enables to justify the decision in an understandable and clear way to the actors. However there are some drawbacks, for instance the need to define a protocol for reaching a bla and a common definition of conflicts and priorities which maybe a difficult task (but it has only to be done once). This difficulty may be increased in domains with more open criteria than in the SCM field where standard criteria are already well established. In order to complete the definition of this bipolar deliberation protocol, a study is still needed to establish that the admissible sets are rational regarding classical decision rules such as Pareto, BiPoss and BiLexi [START_REF] Jf. Bonnefon | An overview of bipolar qualitative decision rules[END_REF].

R 2 R 3

 23 In this bla A, the set of arguments is A = {St, Rb, Ru f , Hi, Rl, Me, Q f , Hci, Pd, Sc, Qd, Ot, Sp, Tw, Ic, Pr, NPr, Lic}. This bla has three levels of importance. The family of attack relations (R λ ) λ≤3 between arguments of the same level is s.t. R 1 = {(St, Hi), (Rb, St), (Rb, Rl), (Rb, Q f ), (Ru f , Hi), (Hi, Rl), (Hi, Q f ), (Me, Ru f ), (Q f , Hci), (Hci, St)}, R 2 = {(Pd, Ic), (Sc, Pd), (Sc, Qd), (Qd, Ic), (Tw, Sp), (Ot, Sp)} and R 3 = {(Pr, NPr), (NPr, Pr), (Lic, NPr)}. For sake of clarity, the other attack relations from any argument towards each opposite argument of a greater level are not shown on the picture.

Proposition 2

 2 Inclusion and Duality: -N ad ⊆ Π ad and N ¬ad ⊆ Π ¬ad -Ct ad = Π ad ∩ Π ¬ad and Id ad = (C \ Π ad ) ∩ (C \ Π ¬ad ) -N ad = C \ (Π ¬ad ∪ Id ad ) and N ¬ad = C \ (Π ad ∪ Id ad ).

• threshold 1 :

 1 c ∈ N ad • threshold 2a: c ∈ N ad ∪ Id ad (or in C \ Π ¬ad ) • threshold 2b: c ∈ Π ad (or in N ad ∪Ct ad ) • threshold 3: c ∈ Π ad ∪ Id ad (or in C \ N ¬ad )

A set of arguments Y defends an argument x iff for any argument y s.t. (y, x) ∈ R there exists an argument z ∈ Y such that (z, y) ∈ R.

In the literature, the instantiated arguments could be called practical arguments while generic arguments are more related to epistemic arguments.

In real life, the establishment of this table is more complex and depends on the particular objectives and priorities of the suppliers and the customers.

in terms of number of symbols used to represent the same information in the worst case

In this paper we suppose that a voter v uses the following basic strategy: if c ∈ C + v then he only gives arguments in I + (c), if c ∈ C - v then he only gives arguments in I -(c).


Thanh Phuong Nguyen
email: thanh-phuong.nguyen@ensta-paristech.fr

Antoine Manzanera
email: antoine.manzanera@ensta-paristech.fr

Matthieu Garrigues
email: matthieu.garrigues@ensta-paristech.fr

Ngoc-Son Vu

International Journal of Pattern Recognition and Artificial Intelligence

Keywords: action recognition, semi dense trajectory beam, local binary pattern, dynamic texture,

A new action model is proposed, by revisiting local binary patterns for dynamic texture models, applied on trajectory beams calculated on the video. The use of semi dense trajectory field allows to dramatically reduce the computation support to essential motion information, while maintaining a large amount of data to ensure robustness of statistical bag of features action models. A new binary pattern, called Spatial Motion Pattern (SMP) is proposed, which captures self similarity of velocity around each tracked point(particle), along its trajectory. This operator highlights the geometric shape of rigid parts of moving objects in a video sequence. SMPs are combined with basic velocity information to form the local action primitives. Then, a global representation of a space × time video block is provided by using hierarchical blockwise histograms, which allows to efficiently represent the action as a whole, while preserving a certain level of spatiotemporal relation between the action primitives. Inheriting from the efficiency and the invariance properties of both the semi dense tracker Video extruder and the LBP based representations, the method is designed for the fast computation of action descriptors in unconstrained videos. For improving both robustness and computation time in the case of high definition video, we also present an enhanced version of the semi dense tracker based on the so called super particles, which reduces the number of trajectories while improving their length, reliability and spatial distribution.

Introduction

In the last decades, action recognition in videos has become a very active domain of computer vision research. To face the increasingly rapid proliferation of video contents, the design of a rapid and reliable method to automatically exploit videos is now a crucial challenge. The recognition of activities occurring in videos is a key problem in many applications, such as video surveillance, video annotation and retrieval, video summarization, human computer interaction and so on.

According to [START_REF] Poppe | A survey on vision-based human action recognition[END_REF], the design of automated activity recognition systems faces three major problems. The first one is intra-and inter-class variations; for example speed or stride length may vary much from one gait to the other, whereas running and jogging are different but similar actions. The second one comes from the huge variety of environments and recording settings, such as lighting conditions, viewpoints, backgrounds, camera motions, etc. The third one is the difficulty to obtain relevant training data and to label them. For these reasons, and in spite of many existing methods, designing a reliable action recognition system in real conditions is still an open problem.

One of the most critical parts of action recognition systems is the design and computation of the action model: what information should be extracted from the video, and how. Many methods have been proposed for action representation (see [START_REF] Aggarwal | Human activity analysis: A review[END_REF] for a comprehensive survey). One first way to classify them is according to the data used to calculate the features, which can be (1) Space-time appearance [START_REF] Laptev | On space-time interest points[END_REF][START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF][START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF][START_REF] Klaser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF][START_REF] Willem | An efficient dense and scale-invariant spatiotemporal interest point detector[END_REF],

(2) Apparent motion [START_REF] Efros | Recognizing action at a distance[END_REF][START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF], or (3) Body silhouette [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF][START_REF] Blank | Actions as space-time shapes[END_REF].

Another way to classify the existing action models is to distinguish global vs local features. Global features are obtained using top-down strategy to encode the visual observation as a whole. Such approach generally represents an action by characterizing a region of interest. It often requires the detection of human body in videos. Due to this pre-processing step that is usually based on background subtraction or object tracking, these features are more sensitive to noise, occlusions or viewpoint change. If these factors are well controlled, the global features are a powerful representation because they encode most of the information. Therefore, they work well in controlled environments such as the KTH dataset [START_REF] Schuldt | Recognizing Human Actions: A Local SVM Approach[END_REF] but are less effective in more realistic environments such as UCF Youtube [START_REF] Liu | Recognizing realistic actions from video "in the wild[END_REF] dataset. The global features are often derived from silhouettes, edges or optical flow. Bobick and Davis introduced MHI (Motion History Images) and MEI (Motion Energy Images) [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF] for encoding evolution of human body movements in temporal and spatial dimensions. Blank et al. [START_REF] Blank | Actions as space-time shapes[END_REF] described human actions as 3d shapes generated by the silhouettes in the spatio-temporal space. The actions are then modelled by Poisson equations. Efros et al. [START_REF] Efros | Recognizing action at a distance[END_REF] represent action by global patterns produced by optical flow fields on a figure-centric spatio temporal volume for each person in a video.

On the other hand, the local representations rather follow a bottom-up strategy. They are made from a collection of local patterns, usually descriptors calculated on a set of spatio-temporal interest points. Then the collection of patterns is reduced using statistical techniques such as bag of features, to construct the action descriptor. The main advantage of these approaches is that they are more robust to noise and partial occlusions than the global representations. In addition, they don't require a segmentation step like background subtraction or human tracking. On the other hand, their results depend more strongly on the choice of input feature, and the performance of statistical classification depends on the amount of extracted local patterns. Let us give some important examples of local feature approaches.

Many local spatio-temporal features are designed by extending classical space detectors and descriptors, such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], SURF [START_REF] Bay | Speeded-up robust features (surf)[END_REF], or HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] to 3d space-time. Laptev [START_REF] Laptev | On space-time interest points[END_REF] detected space-time interest points in videos extending Harris corner criteria from 2d images to 3d. Similarly, Dollár [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] extracted spatio temporal keypoints in the energy map referred to as cuboids by performing symmetric temporal Gabor filtering. It avoids the problem of sparse corner detection reported in [START_REF] Laptev | On space-time interest points[END_REF]. A 3d extension of SURF descriptor is given in [START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF] using 3d Haar wavelets. Klaser [START_REF] Klaser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF] introduced HOG3D by using polyhedral structures for quantization of the 3d spatio-temporal edge orientations. Inspired from HOG, Histogram of Oriented Optical Flow (HOOF) [START_REF] Dalal | Human detection using oriented histograms of flow and appearance[END_REF] that was first proposed for human detection, uses the optical flow instead of the gradient as basis of the orientation distribution. Willems [START_REF] Willem | An efficient dense and scale-invariant spatiotemporal interest point detector[END_REF] performed an extension of the Hessian saliency measure to detect dense and scaleinvariant spatio-temporal interest points. Chakraborty [START_REF] Chakraborty | A selective spatio-temporal interest point detector for human action recognition in complex scenes[END_REF] proposed a surround suppression of detected interest points combined with spatial and temporal constraints to be robust with respect to camera motion and background cluster. An interesting approach is to consider the action as a texture pattern, and to apply dynamic or static texture based methods to action modelling and recognition. Thanks to the effective properties of Local Binary Patterns (LBP) for texture representation, several LBP-based methods have also been proposed for action recognition. The existing LBP-based methods will be reviewed in the next section.

In this paper, we present a new action model which can be seen as a hybrid solution between optical flow methods and dynamic texture based approaches. The motion is locally represented using a binary pattern, whose support is a space-time neighbourhood, located along a trajectory obtained by point tracking. We propose a new self-similarity operator to capture spatial relations in a trajectory beam, by representing the similarity of motion between the tracked point along its trajectory, and its neighbourhood. The semi-dense point tracker computes the displacement of many points in real time, then we apply self-similarity operator on appearance information to represent the motion information of a larger zone surrounding the trajectory.

The remainder is organized as follows. Section 2 presents the background knowledge on LBP based (dynamic) texture representations. Section 3 presents the algorithm used to extract the trajectories. Section 4 combines trajectories and LBPs to form the Spatial Motion Patterns (SMP), which are the descriptors used in action classification. Section 5 presents and discusses the evaluation of the SMP for action recognition on three classic datasets. The last section presents the conclusion and perspectives of this work.

LBP based representations

Brief review of LBP

Local Binary Patterns [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] were introduced by Ojala et al. Their idea is to capture the local structures of texture images using binary patterns obtained by comparing a pixel value with its surrounding neighbours. The LBP encoding of one pixel can Spot Flat Line end Edge Corner Fig. 1. Texture primitives corresponding to Uniform LBPs [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF].

be defined as follows:

LBP P,R = P -1 p=0 s(g p -g c ).2 p , s(x) = 1, x ≥ 0 0, otherwise
where g c is the value of the pixel c and {g p } 0≤p<P are the values of the P neighbours evenly located on a circle of radius R and centre c. The values of neighbours can be obtained by direct sampling or estimated by interpolation.

Ojala et al. observed that most of the patterns in natural images have 0 or 2 bitwise transitions (i.e. 0-1 or 1-0 change occurring in a circular scan). Such patterns are called uniform (LBP u2 ) and defined by U (LBP P,R ) ≤ 2, where:

U (LBP P,R ) = P p=1 |s(g p -g c ) -s(g p-1 -g c )|, with g P = g 0 .
The LBP operator has two important properties: it is invariant to monotonic gray scale changes, and its complexity is very low. Initially proposed for texture modelling and recognition, LBP-based approaches have proved suitable for many other applications, including face recognition, object modelling and action recognition. The uniform pattern coding (LBP u2 P,R , which corresponds to ignoring the non uniform patterns) is widely used in real applications because it reduces significantly the length of feature vectors while capturing important texture primitives: Fig. 1 displays the local geometry classification induced by LBP u2 P,R .

Dynamic texture representation using LBP-based methods

An intuitive extension of LBP is to represent dynamic texture in a 2d+t space, and applying the notion of self-similarity to the spatio-temporal domain. We recall hereafter two spatio-temporal LBP operators for image sequences.

VLBP

Volumetric LBP [START_REF] Zhao | Dynamic texture recognition using volume local binary patterns[END_REF] is a direct extension of [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] for image sequence. Zhao and Pietikäinen defined dynamic texture at voxel c(x, y, t) considering 3P neighbours located on 3 circles of radius R, and centres c 1 (x, y, t -δt), c(x, y, t) and c 2 (x, y, t + δt), where δt is a time interval. Each circle provides a LBP binary code of length P . Similarly, comparing the values of the 3 centres c, c 1 and c 2 leads to a 2-bit code. Finally, the VLBP, made by concatenating the 4 patterns, is a (3P + 2)-bit code.

LBP-TOP

VLBP produces very long codewords when P is large, and only takes into account one time interval δt. LBP-Three Orthogonal Patterns [START_REF] Zhao | Dynamic texture recognition using local binary patterns with an application to facial expressions[END_REF] were also introduced by Zhao and Pietikäinen to address this problem. LBP-TOP pattern at pixel c is made by the LBPs on 3 circles from the 3 orthogonal planes (x, y), (x, t) and (y, t) which intersect at c. This approach provides 3 shorter codewords which, unlike VLBP, are gathered in separated histograms.

LBP-based methods for action recognition

Kellokumpu et al. [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF] used dynamic texture operator (LBP-TOP) to represent human movements. They also presented another approach [START_REF] Kellokumpu | Texture based description of movements for activity analysis[END_REF] using classical LBPs on temporal templates (MEI and MHI images [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF], which are gray level images representing motion information). In the two methods the features were used as observations of a Hidden Markov Model which actually represented the action. Mattivi and Shao [START_REF] Mattivi | Human action recognition using LBP-TOP as sparse spatiotemporal feature descriptor[END_REF] presented a different method using LBP-TOP to describe cuboids detected by Dollár's feature detector. Nanni et al. [START_REF] Nanni | Local ternary patterns from three orthogonal planes for human action classification[END_REF] improved LBP-TOP using ternary units in the encoding step. Yeffet and Wolf proposed LTP (Local Trinary Patterns) [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF] that combines the effective description of LBP with the adaptivity and appearance invariance of patch matching methods. They capture the motion effect on the local structure of self-similarities considering 3 neighbourhood circles at a spatial position and different instants. Kliper-Gross et al. developed this idea by capturing local changes in motion directions with Motion Interchange Patterns (MIP) [START_REF] Klipper-Gross | Motion interchange patterns for action recognition in unconstrained videos[END_REF].

Motion Representation from a Beam of Trajectories

Trajectories are compact and rich information source, and a natural support for the representation of actions. They have been used before for action recognition [START_REF] Wang | Action recognition by dense trajectories[END_REF]. However, to obtain reliable trajectories, the spatial information is often dramatically reduced to a small number of keypoints, and then it may be hazardous to compute statistics on the set of trajectories. In this work we use Video Extruder [START_REF] Garrigues | Video extruder: a semi-dense point tracker for extracting beams of trajectories in real time[END_REF], a semi dense point tracking method (see also Fig. 2) which is a trade-off between long term tracking and dense optical flow, and allows the tracking of a high number of weak keypoints in a video in real time, thanks to its high degree of parallelism.

To optimise the recognition, it is important to have a flexible compromise between the number of trajectories and their reliability. To this end, we introduce in this paper the new concept of super particles, which aggregate the information worn by a set of particles forming different trajectories. Super particles lead to a better distribution of motion information, reduce the influence of noise and provide longer trajectories. We give in this section a brief overview of the tracker, explain how the super particles are formed and tracked, and finally compare them with the original Video Extruder.

Overview of Video Extruder

To improve robustness to large motion (including motion of the camera itself), Video Extruder follows a coarse to fine pyramidal scheme: It starts by estimating the motion at the coarsest resolution level and iterates to the finest resolution level. For each level l of the pyramid, Video Extruder performs the following steps :

• Particle detection: A weakly salient point detector [START_REF] Garrigues | Video extruder: a semi-dense point tracker for extracting beams of trajectories in real time[END_REF], designed to detect as many trackable points as possible, extracts a semi dense field of key points (particles). • Particle matching and tracking: The matcher finds the new position of each particle in the current frame. Using velocities estimated at level l + 1 and the previous velocity of the particle, it predicts the position, and then minimises the distance between descriptors using a gradient descent (the descriptor is a vector of 16 pixel values sampled at two different scales). • Error filtering: A filtering step finally remove particles that diverge from their neighbours.

Table 1 shows how the tracker performs on a GPU, a CPU, and two low-powered ARM processors.

Super particle segmentation and tracking

We present the algorithm to segment and track groups of analogous particles. Such groups are called super particles in the following. From the semi dense field of keypoints, a super particle is a set of particles that are close in both image and motion spaces.

Initialisation: The image is split in a grid of D × D pixel cells, and assume that every particle of cell x belongs to the super particle P x . The position of P x is initialised to the centre of its cell.

The super particles are updated as follows: Let m x and m y be the median horizontal (resp. vertical) displacement of the particles that belong to P x . We compute the new position of P x as: P x t = P x t-1 + (m x , m y ) . To add the new particles and discard the divergent particles from the super particle, we apply the following: If the distance between an orphaned particle and P x is smaller than D pixels, we add it to P x . If the distance between a particle and P x is bigger that 2D, it is removed from the super particle and set as orphaned. Finally, to enhance the robustness of super particles, they are discarded if they contain less than θ particles.

This algorithm can be seen as a simplified mobile object segmentation and tracking. It does not segment objects, but aggregates small groups of particles moving with similar motion.

Super particles have several advantages over simple particles. The trajectories of these groups are more robust and then track motion over a longer period of time. Furthermore, they are better distributed over the image domain, lowering the over-representation of highly textured areas in the statistics. Figure 2 and Table 2 compares the trajectories of the particles and the super particles on the same video. In this example D = 10 and θ = 5. It is also the configuration chosen for experimentation in Section 5.4.

Action Descriptor using Spatial Motion Patterns

This section details the construction of our action descriptor. The input data is the semi-dense trajectory beam described in Section 3, and no appearance information is explicitely used. A classic approach to action description using velocity information is to consider histogram of (orientation of) optical flow (HOOF). This method is simple and computationnally efficient, but suffers from limited discrimination capability, since it neglects the spatio-temporal relations between moving points. One partial solution is to compute the histograms in different sub-volumes defined by a spatio-temporal grid. The descriptor defined in this section aims at addressing more finely this problem. It is constructed in a way to exploit motion information at different context levels:

• Point level: The velocity vector is provided by the semi-dense tracker, at each frame and for every particle (or super particle). • Local spatio-temporal level: Spatial Motion Pattern (SMP) is defined as a self-similarity operator for capturing the motion similarity between every (super) particle and its surrounding points. • Regional to global spatio-temporal level: A hierarchical bag of feature (BoF) histogram vector is built to describe the action at different spatiotemporal scales.

These levels are detailed in the following subsections, then we discuss the properties of this action model, compared with other descriptors from related works.

Point level

The velocity of particles from frame to frame is provided by the semi-dense tracker. Let -→ p t be the 2d displacement of the particle between frames t and t + δ. The first part of the encoding is simply a dartboard quantisation of vector -→ p t (see Fig. 3).

In our implementation, we used intervals of π/6 for the angles and 2 pixels for the norm (the last interval being [6, +∞[), resulting in 12 bins for direction angle, 4 bins for norm. This code corresponds to motion information at the finest level, i.e. point context. However, its information range is much wider than the pixel, since a particle represent a certain spatial structure, and in the case of super particles, the range is even wider, since it depends on D, the space radius of super particles.

-→ p i Fig. 3. Dartboard quantisation of the motion vector.

Local spatio-temporal level

At the local spatio-temporal level, we use an LBP-based representation to capture the relations between a point and its neighbours. The idea is to capture the intertrajectory relations among a beam of trajectories. We combine the LBP-based selfsimilarity operator [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] and the appearance invariance of patch matching method inspired by [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF]. This operator, called Spatial Motion Pattern (SMP), is presented below.

Consider a (super) particle p that moves from position P 1 at frame t to position P 2 at frame t + δ, provided by the semi dense tracker. The similarity of motion between this particle and its surrounding neighbours is assessed by considering the 2 × n patches sampled on the circles of radius r centred at P 1 and P 2 in their corresponding frames (see Fig. 4). Every index i ∈ {0, . . . , n -1} represents a neighbour, which is encoded by 0 if its motion is similar to the motion of the centre particle, and by 1 otherwise. Because semi-dense point tracking is applied instead of dense optical flow, the velocity information is not available everywhere. Following [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF], SSD (sum of square difference) score is used as similarity measure to check the consistency of motion.

Let {∆(p, t) i } n-1 i=0 be the set of n patches surrounding particle p on the circle of radius r, at frame t. The corresponding SMP n,r codeword (b 0 , b 1 , . . . , b n-1 ) is calculated as follows:

b i = 1 If SSD ∆(p, t) i , ∆(p, t + δ) i ≥ τ 0 otherwise ,
where δ is the time interval between two frames, τ is the SSD threshold. Overall, there are 2 n different possible values for a SMP, and only n(n -1) + 3 different values for SMP u2 , i.e. if non uniform patterns are discarded and grouped in a unique symbol [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF].

SSD t + δ t P 1 P 2 ∆(p, t + δ) 1 ∆(p, t + δ) 0 ∆(p, t) 0 ∆(p, t) 1
Fig. 4. The SMP descriptor is calculated for each tracked particle along its trajectory. The consistency of motion in every direction is checked by computing the SSD between the corresponding image patches.

Regional to global spatio-temporal level

To represent the action as a whole, while preserving the main trends of the spatiotemporal relations between its different components, a hierarchical bag of feature (BoF) model [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] is used. An action is represented by histograms of codewords formed by the two previous primitives (motion code and spatial motion patterns) on spatio-temporal volumes. Note that unlike many BoF approaches, no vector quantisation is performed, and the number of codewords simply corresponds to the number of different motion code multiplied by the number of different SMP u2 , i.e. 48 × (n(n -1) + 3). In the hierarchical approach, the considered volumes can be the entire sequence, or a set of sub-sequences defined by a spatio-temporal grid. All histograms are concatenated into one vector that is then normalised to form the action descriptor. Fig. 5 shows an exemple of hierarchical BoF descriptor constructed using three different grids:

1 × 1 × 1, 2 × 2 × 2 and 4 × 4 × 4.

Properties of Spatial Motion Patterns

Spatial Motion Patterns have attractive properties, most of which are inherited from [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF][START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF], :

• Efficient computation. They use SSD scores on small image patches, calculated on tracked keypoints only, thus avoiding many irrelevant calculations. • Appearance invariance. This property is due to: (1) the LBP based encoding and (2) the input data itself, which only relates to the trajectory, not to the appearance. • Robustness against complex background. Unlike many methods, SMP works better when the background is more complex. Indeed, in that case the SSD is more significant, and then the SMP will also better describe the local Fig. 6. SM P u2 configurations allow to determine the shape of the rigid parts of the moving object around the keypoints (in red points). In the neighbouring circles, image patches in green (resp. blue) indicates that they belong to the same rigid part of the moving object as the keypoint (resp. another rigid part or the background).

motion information.

SMP uniform patterns and primitive actions

An important property of SMPs is the interpretation of the corresponding uniform patterns. In an analog manner as LBP u2 (see Fig. 1), SMP uniform patterns (SMP u2 ) capture local action primitives. They characterise the motion between foreground objects and the background in videos, and more generally, between two rigid parts of a moving object. The interpretation of SMP u2 as action primitives can be done as follows (see Fig. 6, and refer to Fig. 1 for the name of primitives):

• Spot: Small foreground object moving on the background.

• Flat: Rigid part of an object (or background).

• Line end: End of a thin rigid part of a moving object.

• Edge: Frontier object/background, or between two parts of an object.

• Corner: Corner of a rigid part of a moving object.

Comparison with Local Trinary Patterns

Although inspired by them, the Spatial Motion Patterns (SMP) differ from Local Trinary Patterns (LTP) [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF] in several aspects. Let us first recall the LTP principles. They use sum of squared differences (SSD) between patches centred at different space and time locations in order to capture the motion effect on the local structures. Let SSD ∆x ∆t be the SSD between the patch centred at pixel x at frame t and the patch centred at pixel x + ∆ x at frame t + ∆ t . One ternary code {-1, 0, 1} is obtained for each shift direction ∆ x , by comparing SSD ∆x -∆t and SSD ∆x +∆t . Figure 7 illustrates this principle.

We list hereunder the main differences between SMP and LTP: • Encoding process. Unlike LTP, SMP use only 2 bits. The encoding of LTP is done by comparing SSD scores between neighbouring patches of past and future frames, and the centre patch of the middle frame. For SMP, SSD scores between two corresponding patches are calculated in two consecutive frames and the binary code is deduced by thresholding. • Neighbouring configuration. LTP used three circles centred at the same position in 2D space. For SMP, the two neighbouring circles are centred at the tracked position of each particle. Then these circles are not always located at the same position. • Interpretation. LTP aims to represent motion information at a given position, whereas for SMP, the motion information is already known, the SMP is interpreted as a local disparity map of velocities around each trajectory. It describes the relative similarity between the small patch in the middle frame and its neighbouring patches in the previous and next frames.

Experimentation on Human Action Classification

To perform action classification, we apply SVM classifier to action descriptors (made by concatenation of different SMP histograms). We choose the method of Vedaldi et al. [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF] which approximates a large scale support vector machines using an explicit feature map for the additive class of kernels. Generally, it is much faster than classic kernel based SVMs and it can be used in large scale problems. We evaluate our descriptor on several well-known datasets. The first one (KTH) [START_REF] Schuldt | Recognizing Human Actions: A Local SVM Approach[END_REF] is a classic dataset, used to evaluate many action recognition methods. The second and third ones are UCF Youtube [START_REF] Liu | Recognizing realistic actions from video "in the wild[END_REF] and UCF Sport [START_REF] Rodriguez | Action mach: a spatio-temporal maximum average correlation height filter for action recognition[END_REF], which are more realistic and challenging datasets.

Parameter settings

SMP configuration

There are several parameters concerning the construction of SMP. Like [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF], we compute SSD score on image patch of size 3 × 3 with threshold τ = 1000 that represents 0.17% of the maximal value of SSD. The time interval δ is set to 1.

In addition, because every tracked keypoint already represents a certain spatial structure, the radius of SMP must be sufficiently large to better capture the geometric shape of rigid parts of moving object surrounding the keypoints. This differs from the typical LBP operator that uses small radius of spatial support (from 1 to 3) in order to capture "micro" structure of textured images. In our implementation, we consider 16 neighbours sampled on a circle of radius 9, as this configuration proved to obtain good results. To reduce the feature vector size, only uniform patterns (SMP u2 16,9 ) were considered. Due to the intrinsic anisotropy of motion in real scenes, the rotation invariant uniform patterns (riu2) were not considered.

BoF configuration

Bag of Feature is a popular approach to build descriptor from local features in videos. Lazebnik et al. [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] showed that a hierarchical BoF still enhances the performance by capturing spatial relations in the distribution of codewords in subvolumes at different scales. They used 3 different grids (scales): 1 × 1 × 1, 2 × 2 × 2 and 4 × 4 × 4. To reduce the dimensionality of feature vector, we used the 3 spatiotemporal grids: 1 × 1 × 1, 2 × 2 × 2 and 3 × 3 × 3 to construct the histograms of codewords.

Experiments on KTH dataset

The dataset contains 25 people for 6 actions (running, walking, jogging, boxing, hand clapping and hand waving) in 4 different scenarios (indoors, outdoors, outdoors with scale change and outdoors with different clothes). It contains 599 a videos, of which 399 are used for training, and the rest for testing. As designed by [START_REF] Schuldt | Recognizing Human Actions: A Local SVM Approach[END_REF], the test set contains the actions of 9 people, and the training set corresponds to the 16 remaining persons. Table 3 shows the confusion matrix obtained by our method on the KTH dataset. The ground truth is read by row. The average recognition rate is 93.33 % which is comparable to the state-of-the-art of LBP-based approaches (see Table 4). The main error factor comes from confusion between jogging and running, which is a typical problem in reported methods. We remark that unlike [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF][START_REF] Kellokumpu | Texture based description of movements for activity analysis[END_REF] that work on segmented box, our results are obtained directly on unsegmented videos. Applying the same pre-processing step would probably improve our result.

a It should contain 600 videos but one is missing b Ours 1: with particle trajectories; Ours 2: with super particle trajectories. c Ours 1: with particle trajectories; Ours 2: with super particle trajectories. d This result is obtained combining several local descriptors: TD, HOG, HOF, MBH. Using one descriptor, the result may vary from 58.2 % to 72.9% on KLT trajectories, from 67.2 % to 83.9 % on dense trajectories. 92.08 [START_REF] Klipper-Gross | Motion interchange patterns for action recognition in unconstrained videos[END_REF] 93.0 [START_REF] Mattivi | Human action recognition using LBP-TOP as sparse spatiotemporal feature descriptor[END_REF] 88.38 [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF] 93.8 [START_REF] Tabia | Motion histogram quantification for human action recognition[END_REF] 82.36 [START_REF] Kellokumpu | Texture based description of movements for activity analysis[END_REF] 90.8 [START_REF] Wang | Action recognition by dense trajectories[END_REF] 94.2 [START_REF] Jargalsaikhan | Action recognition based on sparse motion trajectories[END_REF] 97.1

Experiments on UCF Youtube dataset

The UCF Youtube dataset records 11 categories (basketball shooting, cycling, diving, golf swinging, horse back riding, soccer juggling, swinging, tennis swinging, trampoline jumping, volleyball spiking and walking with a dog), and contains 1 600 video sequences. Each category is divided into 25 groups sharing common appearance properties (actors, background, or other). It is much more challenging than KTH because of its large variability in terms of viewpoints, backgrounds and camera motions. Following the experimental protocol proposed by the authors [START_REF] Liu | Recognizing realistic actions from video "in the wild[END_REF], we used 9 groups out of the 25 as test and the 16 remaining groups as training data. Table 5 presents our results compared to other recent methods while Table 6 shows the confusion matrix of our method (Ours 1) on this dataset. The worst classification rate corresponds to confusions of "walking with dog" action with "biking" and "horse riding" actions. Our mean recognition rate on UCF Youtube dataset is 72.07 %, which is comparable to recent methods.

Experiments on UCF Sport

The UCF Sport dataset [START_REF] Rodriguez | Action mach: a spatio-temporal maximum average correlation height filter for action recognition[END_REF] contains a set of action clips from different sport videos, including 9 categories (diving, golf swing, kicking, lifting, riding, running, skate- [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 77.3 From [37] Harris3D [START_REF] Laptev | On space-time interest points[END_REF] + HOG/HOF [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 78.1 From [37] Yeffet and Wolf [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF] 79.1 Hessian [START_REF] Willem | An efficient dense and scale-invariant spatiotemporal interest point detector[END_REF] + HOG/HOF [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 79.3 From [37] Dense + HOF [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 82.6 From [37] Cuboids [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] + HOG3D [START_REF] Klaser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF] 82.9 From [37] Wang et al. [START_REF] Wang | Action recognition by dense trajectories[END_REF] 88.2 e boading, swing and walking). Testing is based on Leave One Out cross validation, selecting one video at a time for testing, and the others for training. Following [START_REF] Klaser | A Spatio-Temporal Descriptor Based on 3D-Gradients[END_REF], a horizontally flipped version of each video was added to increase the number of training samples. UCF Sport is a challenging dataset, because it contains a wide range of scenes and viewpoints. Compared with UCF Youtube, the resolution is higher and the actions are shot from closer. This results in a much larger number of trajectories, which implies higher computation time. Then, we chose this dataset to evaluate the super particle based enhanced trajectories. Table 7 presents the results of our descriptors on this dataset using the two types of trajectories as input (particles or super particles), compared with existing methods. Working with super particles gives a comparable result as original particles. However the super particule strategy accelerates dramatically the computation time of the descriptor. Indeed, the tracking of particles or super particles takes approximately the same time, whereas the computation cost of the action descriptor essentially depends on the total length of tracked trajectories. As a typical example, it can be deduced from the figures of Tab. 2 that the super particle approach should imply more than 8 times fewer SMPs to compute.

Discussions

From the above experiments on three datasets, we can do the following remarks.

• For low resolution videos like KTH or UCF Youtube datasets, the super particles do not improve the performance. This is due to the loss of activity information when the number of trajectories is limited

• For high resolution videos like UCF Sport dataset, the super particles are a good way to accelerate the computation of descriptors without reducing the discrimination capability of the method. • The proposed method outperforms LBP-based methods and is comparable to other recent methods. • Two trajectory-based methods [START_REF] Wang | Action recognition by dense trajectories[END_REF][START_REF] Jargalsaikhan | Action recognition based on sparse motion trajectories[END_REF] have better results than ours. However their computation time is much higher, due to their combination of a large number of different descriptors such as TD, MBH, HOF and HOG, and, in the case of [START_REF] Wang | Action recognition by dense trajectories[END_REF], their use of dense trajectories, whose computation cost is higher than (semi-dense) VideoExtruder.

The comparison with [START_REF] Wang | Action recognition by dense trajectories[END_REF][START_REF] Jargalsaikhan | Action recognition based on sparse motion trajectories[END_REF] leads to different remarks. The performance of trajectory-based methods depends on the type of trajectories. For example, changing KLT for dense trajectories improves for more than 6% on UCF Sport. Also, a combination of different descriptors can improve the performance. So experimenting on different kinds of trajectories and combining with other descriptors can be considered in future works. Due to the difficulty in re-implementing existing methods, we did not quantitatively compare the computation time for the different methods. However, the efficiency of the proposed method can be justified by its components:

• The extraction of trajectories is very fast thanks to VideoExtruder • The computation of SMP is simple like other LBP-based variants. Moreover, SMP code is not calculated at each voxel of the video. It is only calculated along the tracked trajectories, whose number can be adjusted using the super particle framework.

Conclusions

We have presented a new method for action recognition based on semi-dense trajectory beams and a LBP based local motion pattern, which captures spatial relations of moving parts, along their trajectories. It inherits good properties of invariance and computational efficiency from Video Extruder and LBPs, and it is designed to work in unconstrained videos with complex background. To enhance the robustness of the trajectories, and to reduce the computation time of the action descriptors, the new concept of super particles was introduced, leading to fewer trajectories, but longer, more stable and better space distributed. In the future, we are interested in several perspectives related to this method, such as multi-scale SMPs, and improving the results in the case of moving backgrounds.

Acknowledgment

A preliminary version of this article was presented in [START_REF] Nguyen | Revisiting lbp-based texture models for human action recognition[END_REF]. This work was supported by the French Ministry of Economy (DGCIS), as part of a European ITEA2 project.

We thank the anonymous referees for their constructive comments and suggestions.

Fig. 2 .

 2 Fig. 2. Comparison of the particles and the super particles.

Fig. 5 .

 5 Fig. 5. Action modelling by SMP histogram concatenation.

Fig. 7 .

 7 Fig. 7. Local Trinary Patterns [25].

Table 1 .

 1 Performances of Video extruder semi dense tracker. # p is the number of particles, Mpix/s (resp. fps) is the computation frequency, in Megapixels (resp. in frames) per second, cpp is the number of cycles per particle.

	Architecture	Resolution # p Mpix/s (fps)	cpp
	GPU Geforce GTX 460 1.35GHz	640 × 480 8 500	50 (166)	957
	CPU quad-core I5 2500k 3.3GHz	640 × 480 8 500	46 (152)	2 550
	ARM dual-core STE U8500 1GHz 320 × 240 3 000	0.84 (11)	30 300
	ARM single-core IMX.53 1GHz	720 × 288 2 000	2.07 (10)	50 000

Table 2 .

 2 Comparison of moving particles and super particles. An entity is classified as moving if it moved more than 100 pixels over its entire life. The average trajectory lifetime represents the average number of frames the particles were tracked.

	Particles Super particles

Table 3 .

 3 Confusion matrix on KTH dataset.

		Box. Clap. Wav. Jog. Run. Walk.
	Box. 97.5 2.5	0	0	0	0
	Clap. 2.5	97.5	0	0	0	0
	Wav. 2.5	0	97.5	0	0	0
	Jog.	0	0	0	95.0 0	5.0
	Run. 0	0	0	12.5 82.5	5.0
	Walk. 0	0	0	10.0 0	90.0

Table 4 .

 4 Comparison on KTH dataset.

	Method b	Result Method Result
	Ours 1	93.33	[25]	90.17
	Ours 2

Table 5 .

 5 Comparison on UCF Youtube.

	Method c	Result	Method	Result	Method Result
	Ours 1	72.07	[34]	64	[13]	71.2
	Ours 2	70.85	[35]	64	[27]	84.2 d

Table 6 .

 6 Confusion matrix on UCF Youtube dataset.

		Walk. Volley. Tramp. Tennis Swing Soccer. Horse. Golf.	Div.	Biking Bask.
	Walk. 38.64	0	6.82	2.27	6.82	4.55	18.18	4.55	0	18.18	0
	Volley. 0	74.36	0	2.56	7.69	2.56	0	2.56	0	0	10.26
	Tramp. 0	2.33	88.37	0	0	4.65	0	0	0	4.65	0
	Tennis 1.59	0	1.59	79.37	0	0	4.76	3.17	3.17	4.76	1.59
	Swing 5.36	0	8.93	0	78.57	0	0	0	0	7.14	0
	Soccer. 5.56	3.7	1.85	16.67	0	55.56	1.85	7.41	0	0	7.41
	Horse. 1.29	0	0	4.84	0	0	70.97	0	0	9.68	1.61
	Golf.	1.85	0	0	0	0	0	0	92.59	3.7	0	1.85
	Diving 5	1.67	1.67	1.67	0	0	0	1.67	88.33	0	0
	Biking 0	0	6.25	0	0	12.5	6.25	2.08	0	72.92	0
	Bask.	0	2.34	4.26	6.38	2.13	0	4.26	2.13	4.26	0	53.19

Table 7 .

 7 Comparison on UCF Sport dataset.

	Method	Result Remark
	Ours	81.3	Super particle trajectories
	Ours	80.7	Particle trajectories
	Rodriguez et al. [31]	69.2
	Hessian [7] + ESURF

e This result is obtained combining several local descriptors: trajectory, HOG, HOF, MBH. Using one descriptor, the result may vary from 72.7 % to 80.2 % on KLT trajectories and from 75.2 % to 84.8 % on dense trajectories.


Thanh Phuong Nguyen

Antoine Manzanera

Ngoc-Son Vu

Matthieu Garrigues

Revisiting LBP-based Texture Models for Human Action Recognition ⋆

Keywords: action recognition, local binary pattern, dynamic texture,

A new method for action recognition is proposed by revisiting LBP-based dynamic texture operators. It captures the similarity of motion around keypoints tracked by a realtime semi-dense point tracking method. The use of self-similarity operator allows to highlight the geometric shape of rigid parts of foreground object in a video sequence. Inheriting from the efficient representation of LBP-based methods and the appearance invariance of patch matching method, the method is well designed for capturing action primitives in unconstrained videos. Action recognition experiments, made on several academic action datasets validate the interest of our approach.

Introduction

Human activity recognition has been an active research topic in recent years due to its interesting application domains such as video surveillance, human computer interaction, video analysis, and so on. Many approaches have been introduced using different video features for action representation, we refer to [START_REF] Aggarwal | Human activity analysis: A review[END_REF] for a comprehensive survey. However a robust and real time method for action recognition with unconstrained videos is still a difficult challenge.

An interesting approach is to consider the action as a texture pattern, and to apply dynamic or static texture based methods to action modelling and recognition. Thanks to the effective properties of Local Binary Patterns (LBP) for texture representation, several LBP-based methods have also been proposed in the past for action recognition. Kellokumpu et al. [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF] used dynamic texture operator (LBP-TOP) to represent human movement. They also presented another approach [START_REF] Kellokumpu | Texture based description of movements for activity analysis[END_REF] using classical LBP on temporal templates (MEI and MHI images [START_REF] Bobick | The recognition of human movement using temporal templates[END_REF]) that were introduced to describe motion information from images. All extracted features in the two methods are then modelled using HMM (Hidden Markov Model). Mattivi and Shao [START_REF] Mattivi | Human action recognition using LBP-TOP as sparse spatiotemporal feature descriptor[END_REF] presented a different method using LBP-TOP to describe cuboids detected by Dollar's feature detector. Recently, Yeffet and Wolf proposed LTP (Local Trinary Patterns) [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF] that combines the effective description of LBP with the adaptivity and appearance invariance of patch matching methods. They capture the motion effect on the local structure of selfsimilarities considering 3 neighbourhood circles at a spatial position and different instants. Kliper-Gross et al. developed this idea by capturing local changes in motion directions with Motion Interchange Patterns (MIP) [START_REF] Klipper-Gross | Motion interchange patterns for action recognition in unconstrained videos[END_REF]. Nanni et al. [START_REF] Nanni | Local ternary patterns from three orthogonal planes for human action classification[END_REF] improved LBP-TOP using ternary units in the encoding step.

In this paper, we revisit dynamic texture based methods for action recognition. We are inspired by 2 popular LBP based representation: uniform LBP for texture coding and LTP for motion coding. We propose a new self-similarity operator to capture spatial relations in a trajectory beam, by representing the similarity of motion between the tracked point along its trajectory, and its neighbourhood. The semi-dense point tracker computes the displacement of many points in real time, then we apply self-similarity operator on appearance information to represent the motion information of a larger zone surrounding the trajectory. Our method can be seen as a hybrid solution between optical flow methods and dynamic texture based approaches. The rest is organised as follows. Section 2 briefly presents the basic material. The next section proposes our approach for action representation. The last sections are experiments and conclusions.

Basic Materials

LBP based operators

Uniform LBP Local Binary Patterns [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] were introduced by Ojala et al. Their idea is to capture the local structures of texture images using binary patterns obtained by comparing a pixel value with its surrounding neighbours. LBP operator has two important properties: it is invariant to monotonic gray scale changes, and its complexity is very low. As a consequence, LBP-based approaches are suitable for many applications, aside from texture recognition. A LBP is called uniform if the number of binary transitions (from 0 to 1, from 1 to 0) while scanning the circle clockwise is at most 2. The uniform pattern coding (LBP u2 n,r , corresponding to ignoring the non uniform patterns) is widely used in real applications because it reduces significantly the length of feature vectors while capturing important texture primitives (see Fig. 1).

Spot Flat Line end Edge Corner

Fig. 1. Texture primitives corresponding to Uniform LBPs [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF].

LTP Local Trinary Patterns [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF] use sum of squared differences (SSD) between patches centred at different space and time locations. Let SSD ∆x ∆t be the SSD between the patch centred at pixel x at frame t and the patch centred at pixel x + ∆ x at frame t + ∆ t . One ternary code {-1, 0, 1} is obtained for each shift direction ∆ x , by comparing SSD ∆x -∆t and SSD ∆x +∆t .

Motion Representation using a Beam of Dense Trajectories

Trajectories are compact and rich information source to represent motion in videos, and have been used already for action recognition [START_REF] Wang | Action recognition by dense trajectories[END_REF]. Generally, to obtain reliable trajectories, the spatial information is dramatically reduced to a small number of keypoints, and then it may be hazardous to compute statistics on the set of trajectories. In this work we use the semi dense point tracking method [START_REF] Garrigues | Real time semi-dense point tracking[END_REF] (see also Fig. 2) which is a trade-off between long term tracking and dense optical flow, and allows the tracking of a high number of weak keypoints in a video in real time, thanks to its high level of parallelism. Using GPU implementation, this method can handle 10 000 points per frame at 55 frames/s on 640 × 480 videos. In addition, it is robust to sudden camera motion changes.

Action Descriptor using Spatial Motion Patterns

We present now our descriptor for action representation. The input data is the semi-dense trajectory beam described in Section 2. The classic approach to build motion information from optical flow is to consider histogram of optical flow (HOOF). This approach is simple to compute but neglects the spatio-temporal relation between moving points. One popular but limited solution is to consider the extracted histograms in different sub-volumes defined by a spatio-temporal grid. In this section, we introduce a descriptor that addresses more finely this problem. Briefly, the motion information is exploited at different context levels:

(1) Point level; [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF] Local spatio-temporal level; (3) Regional to global spatiotemporal level. This is detailed hereafter.

Point level

Let -→ p t be the 2d displacement of the point between frames t and t + δ. The first part of the encoding is simply a dartboard quantisation of vector -→ p t (see Fig. 3). In our implementation, we used intervals of π/6 for the angles and 2 pixels for the norm (the last interval being [6, +∞[), resulting in 12 bins for direction angle, 4 bins for norm.

-→ p i Fig. 3. Dartboard quantisation of the motion vector.

SSD t + δ t P 1 P 2 ∆(p, t) 0 ∆(p, t) 1 ∆(p, t + δ) 0 ∆(p, t + δ) 1
Fig. 4. The SMP descriptor is calculated at each tracked keypoint, along its trajectory. The consistency of motion in every direction is checked by computing the SSD between the corresponding image patches.

Local spatio-temporal level

At the local spatio-temporal level, we use an LBP-based dynamic texture to capture the relations between a point and its neighbours. Our idea is to capture the inter-trajectory relations among a beam of trajectories. We propose to combine the LBP-based self-similarity operator [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] and the appearance invariance of patch matching method inspired by [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF]. This operator, called Spatial Motion Pattern (SMP), is presented below.

Spatial Motion Patterns

Consider a point p that moves from position P 1 at frame t to position P 2 at frame t + δ, provided by the semi dense tracker [START_REF] Garrigues | Real time semi-dense point tracking[END_REF]. The similarity of motion between this point and its neighbours is obtained by considering the 2×n patches sampled from circles centred at P 1 and P 2 in their corresponding frames (see Fig. 4). Every index i ∈ {0, n -1} represents a direction, which is encoded by 0 if the motion in this direction is similar to the motion of the centre point, and by 1 otherwise. Following [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF], SSD (sum of square difference) score is used as similarity measure to check the consistency of motion.

Let {∆(p, t) i } n-1 i=0 be the set of n patches surrounding particle p at frame t. The corresponding SMP codeword (b 0 , b 1 , . . . , b n-1 ) is constructed as follows:

b i = 1 If SSD ∆(p, t) i , ∆(p, t + δ) i ≥ τ 0 otherwise
where δ is the time interval between two frames, τ is the SSD threshold.

Our local descriptor differs significantly from LTP in several aspects:

-Encoding process. Unlike [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF], our descriptor uses only 2 bits. The encoding of LTP is done by comparing SSD scores between neighbouring patches of past and future frames, and the centre patch of the middle frame. Our method estimates the SSD scores between two corresponding patches in two consecutive frames. -Neighbouring configuration. LTP used three circles centred at the same position in 2D space. In our approach, the two neighbouring circles are centred at the tracked position of each keypoint. -Interpretation. LTP aims to represent motion information at a given position, whereas in our case, the motion information is already known, the SMP is interpreted as a local disparity map of velocities around each trajectory.

Properties of Spatial Motion Patterns

Inheriting from [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF][START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF], Spatial Motion Patterns have attractive properties:

-Simple computation. They use SSD scores on small image patches. In addition, the calculation is only applied on tracked keypoints, not on the whole image, avoiding many irrelevant calculations. -Appearance invariance. This property is due to: (1) the LBP based encoding and (2) the basic information which only relates to the trajectory, not to the appearance.

SMP uniform patterns (SM P u2

) captures local primitives action in a similar way as LBP uniform patterns (LBP u2 ). They detect the motions between foreground objects and the background in videos, and more generally, between two rigid parts of a moving object. We can point out the relation between SM P u2 and action primitives as follows (see also Fig. 1).

-Spot: A small foreground object move on the background.

-Flat: A big rigid part of a moving object.

-Line end: End of a thin foreground object.

-Edge: Border between two parts of a moving object, or between a foreground object and the background. -Corner: A corner of a rigid part of a moving object. It is also worth mentioning that, unlike many other methods, the more complex the background, the more efficiently should the SMP describe the rigid parts of the moving object. Fig. 5. SM P u2 configurations allow to determine the shape of the rigid parts of the moving object around the keypoints (in red points). In the neighbouring circles, image patches in green (resp. blue) indicates that they belong to the same rigid part of the moving object as the keypoint (resp. another rigid part or the background).

Regional to global spatio-temporal level

In this context, a pyramidal bag of feature (BoF) [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] is used to represent action by histograms of codewords made of the two previous primitives (motion code and spatial motion patterns) on spatio-temporal volumes. All histograms are concatenated into one vector that is then normalised for action representation. Fig. 6 shows how to construct the action description using three different grids.

Experimentation on Human Action Classification

Classification

To perform action classification, we choose the SVM classifier of Vedaldi et al. [START_REF] Vedaldi | Efficient additive kernels via explicit feature maps[END_REF] which approximates a large scale support vector machines using an explicit feature map for the additive class of kernels. Generally, it is much faster than non linear SVMs and it can be used in large scale problems.

Experimentation

We evaluate our descriptor on two well-known datasets. The first one (KTH) [START_REF] Schuldt | Recognizing Human Actions: A Local SVM Approach[END_REF] is a classic dataset, used to evaluate many action recognition methods. The second one (UCF Youtube) [START_REF] Liu | Recognizing realistic actions from video "in the wild[END_REF] is a more realistic and challenging dataset. Parameter settings There are several parameters concerning the construction of SMP. Like [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF], we compute SSD score on image patch of size 3 × 3 with threshold τ = 1000 that represents 0.17% maximal value of SSD. The time interval δ is set to 1. Because every tracked keypoint already represents a certain spatial structure, the radius of SMP must be sufficiently large to better capture the geometric shape of rigid parts of moving object surrounding the keypoints. In our implementation, we consider 16 neighbours sampled on a circle of radius 9. In addition, only uniform patterns (SMP u2 16,9 ) are considered. To construct the histograms of codewords, we used 3 spatiotemporal grids: 1 × 1 × 1, 2 × 2 × 2 and 3 × 3 × 3.

Experimentation on KTH dataset

The dataset contains 25 people for 6 actions (running, walking, jogging, boxing, hand clapping and hand waving) in 4 different scenarios (indoors, outdoors, outdoors with scale change and outdoors with different clothes). It contains 5993 videos, of which 399 are used for training, and the rest for testing. As designed by [START_REF] Schuldt | Recognizing Human Actions: A Local SVM Approach[END_REF], the test set contains the actions of 9 people, and the training set corresponds to the 16 remaining persons. Table 1 shows the confusion matrix obtained by our method on the KTH dataset. The ground truth is read by row. The average recognition rate is 93.33 % which is comparable to the state-of-the-art of LBP-based approaches (see Table 2). We remark that unlike [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF][START_REF] Kellokumpu | Texture based description of movements for activity analysis[END_REF] that work on segmented box, our results are obtained directly on unsegmented videos. Applying the same pre-processing step would probably improve our result. Method Result Method Result Ours 93.33 [START_REF] Yeffet | Local trinary patterns for human action recognition[END_REF] 90.17 [START_REF] Kellokumpu | Texture based description of movements for activity analysis[END_REF] 90.8 [START_REF] Klipper-Gross | Motion interchange patterns for action recognition in unconstrained videos[END_REF] 93.0 [START_REF] Mattivi | Human action recognition using LBP-TOP as sparse spatiotemporal feature descriptor[END_REF] 88.38 [START_REF] Kellokumpu | Human activity recognition using a dynamic texture based method[END_REF] 93.8 Experimentation on UCF Youtube dataset The UCF Youtube dataset records 11 categories (basketball shooting, cycling, diving, golf swinging, horse back riding, soccer juggling, swinging, tennis swinging, trampoline jumping, volleyball spiking and walking with a dog), and contains 1 600 video sequences. Each category is divided into 25 groups sharing common appearance properties (actors, background, or other). It is much more challenging than KTH because of its large variability in terms of viewpoints, backgrounds and camera motions. Following the experimental protocol proposed by the authors [START_REF] Liu | Recognizing realistic actions from video "in the wild[END_REF], we used 9 groups out of the 25 as test and the 16 remaining groups as training data. Our mean recognition rate on UCF Youtube dataset is 72.07 % (see Table 3), which outperforms recent methods.

Fig. 2 .

 2 Fig. 2. Several actions of KTH dataset and their corresponding beam of trajectories. Red points represent tracked particles, green curves describe their trajectories.

Fig. 5

 5 Fig. 5 illustrates the interpretation of SMP uniform patterns (SM P u2 ).It is also worth mentioning that, unlike many other methods, the more complex the background, the more efficiently should the SMP describe the rigid parts of the moving object.

Fig. 6 .

 6 Fig. 6. Action modelling by SMP histogram concatenation.

BoxTable 2 .

 2 Comparison on KTH dataset.

Table 1 .

 1 Confusion matrix on KTH dataset.

Table 3 .

 3 Comparison on UCF Youtube.

	Our method [16] [17] [15]
	72.07	64 64 71.2

It should contain 600 videos but one is missing

We have presented a new method for action recognition based on semi-dense trajectory beam and the LBP philosophy. Its main idea is to capture spatial relation of moving parts around the tracked keypoints, along their trajectories. Our descriptor is designed to capture geometric shape of the rigid parts of moving object in unconstrained videos with complex background. In the future, we are interested in several perspectives related to this method such as multi-scale SMPs, and extension to moving backgrounds.

⋆ This work is part of an ITEA2 project, and is supported by french Ministry of Economy (DGCIS).