Introduction

The core of what is meant today by 'convex analysis' consists in studying convex subsets of linear spaces, convex real fonctions defined on such spaces, the extremal problems involving them and their minimax counter part. This subject has received considerable attention during recent decades, stimulated by the frequent occurrence of convexity assumptions in optimization, economics and the related numerical analysis. Such modern developments as variational inequalities or monotone operators are closely interrelated with convex analysis.

To the author's historical knowledge, mechanics was the first domain of science to make a precise use of the concept of a convex set (17th century): the equilibrium positions of a solid body lying on a horizontal plane and subject to gravity are characterized by the condition that the vertical line drawn through its centre of mass meets the convex bull of the point.s of support. Investigating the statics or the dynamics of systems with unilateral constraints in this spirit constituted the author's primary moti vation for taking some part in the recent development of convex analysis (see, for example, Moreau [START_REF] Moreau | Quadratic programming in mechanics: Dynamics of one-sided constraints[END_REF][START_REF] Moreau | Principes extrémaux pour le problème de la naissance de la cavitation[END_REF]).

On the other hand, the importance of convexity assumptions regarding the potential function of a force law has been repeatedly stressed, mainly after Hill [START_REF] Hill | New horizons in the mechanics of solids[END_REF], in relation to stability, sometimes with hints at ther modynamics.

The concepts of the subdifferential of a convex function, now of general use in many domains, and of the superpotential of a force law, were defined by the author in order to include classical force laws and perfect (possibly unilateral) constraints in a unified treatment (see, for example, Moreau [START_REF] Moreau | Fonctionnelles sous-différentiables[END_REF][START_REF] Moreau | La notion de sur-potentiel et les liaisons unilatérales en élastostatique[END_REF][START_REF] Moreau | La convexité en statique[END_REF]).

The duality of Jinear spaces plays a prominent role in modern convex analysis. Regarding this concept also, mechanist:, acted as forerunners; in fact, the mathematical structure of a pair of linear spaces, placed in duality by a bilinear form, constitutes the essence of the traditional method of virtual work or virtual power.

The present paper, attemptedly self-consistent, develops an example of the application of modern convex analysis to dry friction and ends with two general theorems. This theme was first presented at a small sym posium on convexity in 1970 (Moreau [START_REF] Moreau | Convexité et frottement[END_REF]); subsequently, modern convex analysis has been widely applied to resistance laws of various sorts (Moreau [8]), mainly to plasticity theory , Nayroles [START_REF] Les | Quelques applications variationnelles de la théorie des fonc tions duales à la mécanique des solides[END_REF][START_REF] Nayroles | Opérations algébriques en mécanique des structures[END_REF][START_REF] Nayroles | Point de vue algébrique, convexité et intégrandes convexes en mécanique des solides[END_REF][START_REF] Nayroles | Deux théorèmes de minimum pour certains systèmes dis sipatifs[END_REF], Debordes and Nayroles [START_REF] Debordes | Sur la théorie et le calcul à l'adaptation des structures élastoplastiques[END_REF]) possibly with strain hardening (Nguyen and Halphen [START_REF] Nguyen | Sur les lois de comportement élasto-visco plastiques à potentiel généralisé[END_REF], Nguyen [START_REF] Nguyen | Matériaux élasto-visco-plastiques et élastoplastiques à poten tiel généralisé[END_REF]). The concrete and elementary situation taken as an example in what follows may be studied as an introduction to these more elaborate topics.

The classical formulation of Coulomb's law

Let 9' 0 denote a perfectly rigid body, assumed to be fixed; another perfectly rigid body 9' 1 moves in contact with 9' 0 • This means that the respective boundary surfaces ! 0 and ! 1 , supposed geometrically smooth, remain tangent at a point M, a priori moving in both of them. All the following is relative to some definite instant; in the corresponding config uration, let v denote the unit normal vector to ! 0 and ! 1 at the point M. By definition, the sliding velocity V of 9' 1 on 9' 0 is the velocity vector relative to 9' 0 of the element M 1 of 9' 1 which happens to be in Mat the instant under consideration. Under the usual geometrical and kinematical smoothness assumptions, it is elementarily proved that v •V= 0, i.e., V belongs to the two-dimensional linear spaces II consisting of the vectors tangent at M to ! 0 and ! 1 • The contact forces exerted by 9' 0 on 9' 1 are supposed to reduce to a single force R acting on the element M 1 ; let us decompose this vector into R=F+Nv with FEII.

The Coulomb law of dry friction, when the normal component N-;;,; 0 is treated as known, states a relation between F and V traditionally formu lated as follows.

There exists f-;;,; 0, the friction coefficient, s uch that if V= 0: \F\:,;; fN,

if V ;é O : \F\ = fN (1) (2)
and the vectors F and V are parallel with opposite dir. ::tians. (Here \ \ represents the Euclidean norm.) Such a juxtaposition of two apparently heterogeneous statements con cernîng the events V= 0 and V� 0 might look purely empirical. Actually, the use of some elementary concepts of convex analysis will emphasize their strong consistency.

.Generalization

In the same situation as above, let us consider the closed dise

D = {cf> E ll: J <I> I � fN}.
The Coulomb law is equivalently expressed by FED, } \f <I> ED: V• (<l>-F);;;. O.

In fact, when V� 0, this means that the set

{<l>E ll :V• (<l>-F) � O}, (3)
i.e., the closed half-plane having F as a boundary point and V as an outward normal vector is a supporting half-plane of the set D at the point F (i.e., this half-plane has only boundary points in common with D and F is one of them). By the elementary properties of the circle, this is equivalent to (2). In the case V= 0, the equivalence of (3) to (1) is trivial.

From this stage it is quite natural to generalize the formulation into a law of anisotropie friction, as it may physically result from the directional structure of the material surfaces in contact: the dise D will be replaced by some subset C of ll, containing the origin.

On the other hand, one aim-of this paper is to emphasize the considera tion of many-dimensional pairs of linear spaces. Generally speaking, a linear space of velocities 'V and a linear space of fore es g; will be introduced. These spaces are placed in duality by the bilinear form 'power': for VE'V and FE.<ffe", we shall denote by (V,F)•the power of the force F if the motion has the velocity V. In the preceding example, 'V and g; were two copies of the same two-dimensional Euclidean space II, placed in duality with itself by the Euclidean scalar product.

Similarly to (3), let us define a friction law as the relation between VE 'V and FE g; formulated as follows:

FEC, } \f<l>E C: (V, <l>-F);;;. 0, ( 4
)
where C is a given subset of .<ffe". This subser is assumed to contain the origin of .<ffe", i.e., zero is a possible value of F, compatible in particular with the value zero of V. Then, by setting cf>= 0, it turns out that for every pair F, V satisfying (4), the power (V, F) is non-positive: friction, as described by relation (4), is a dissipative phenomenon.

Relation (4) is obviously equivalent to the following statement: the set of the elements FE g; which the relation associates with a given VE 'Y is identical with the set of the points of C where the function <I>-(V, <I>) attains its infimum relative to C.

In most of the mechanical situations which a relation of the form ( 4) is meant to describe, it is required that every value of V be feasible, i.e., for every VE °V the above set is non-empty. Here is the most usual mathematical assumption ensuring that: there exists a topology on the space g; relative to which the set C is compact, white the real function <P�(V, <I>) is continuous for every V in °V. In the case of finite dimensional °V and s;, this will naturally be the topology defined by the use of components in these linear spaces; then, the continuity of linear functions is automatic and we only have to make the assumption that C is closed and bounded. For infinite-dimensional cases, such as those arising in the mechanics of continua, it is necessary to specify some topology on g; among those which are said to be compatible with the duality defined by the bilinear form (. ,.) or topologies of the dual pair ('Y, s;, (. , .)); in order that compactness involve the mildest restriction about C, this should be the coarsest of these topologies, i.e., the weak topology usually denoted by cr(s;, °V) (see, for example, Robertson and Robertson [START_REF] Robertson | Topological Vector Spaces[END_REF]).

In the proper friction phenomenon, the non-negative expression -(V, F) is equal to the power transformed into heat and is called the dissipated power: thus, relation (4) may be entitled 'the principle of maximum dissipation'.

lndicator functions and subdifferentials

. Every subset C of g; may be described by giving its indicator function t/Jc

(<I>) = {o if <I> E c, t/J c +co if <I>� C.
Using this, one writes relation (4) equivalently in the form V<I> E ClJi: <-V, <l>-F> + t/l c(F) � lf!c{<l>) which st: oes that t/Jc(F) is finite, that the affine function

<I>-<-V,<I>-F>+l/l c (F)
is a minorant of the function t/Jc and that this minorant is exact at the point F, i.e., it takes the same value at this point as l/J c (namely zero). The element -V of 'Y constitutes the slope or gradient of the considered affine fonction in the sense of the duality (. , .). According to the terminology introduced by the author [START_REF] Moreau | Fonctionnelles sous-différentiables[END_REF] and now usual in the whole field of convex analysis, the gradient of an affine minorant of a function g :;!J--]-co, + co] ; if this minorant is exact at the point F, is called a subgradient of g at the point F. The set, denoted by ag(F), of the subgradients of g at the point F is a (possibly empty) convex subset of "JI' called the subdifferential of g at

F.

In this notation, the relation ( 4) is equivalently written as -VEat/fc(F).

(

) 5
Usually, C is a closed convex set (see section 7 below); ( 5) means that FE C and that V is, in a classical generalized sense, a normal in ward vector to this set at the point F (in particular, V= 0 if Fis internai to C).

Dissipation function

Let g be a fonction with values in ]-co, +co], defined, for instance, on the member g;; of the considered dual pair of linear spaces. The handling of the affine minorants of g induces us to construct the fonction g*, with values in ]-co, +co ], defined on 'Y by

g* ( W) = .� [ ( W , cl>) -g(cl>) ] . (6)
It is called the conjugate or polar function of g. An affine fonction <P-(W,cl>)-a is a minorant of g if and only if the real number a satisfies a ;a,, g*(W).

In the special case, g = t/Jc, the expression (W, cl>)-t/fc(cl>) takes the value -co when cl>rt C; therefore, t/l�(W) = suo (W, cl>).

<J>e't:

This fonction is classically known under the (rather improper) name of the support function of the set C, relative to the considered duality. It is evidently sublinear, i.e., convex and positively homogeneous of degree l.

In the present situation, it will prove more convenient to introduce the fonction cp

cp(W) = t/1�(-W) = -inf (W, cl>), <l>EC (7)
i.e., the support fonction of the set -C. Using cp yields an equivalent formulation of the relations (4) or ( 5)

FE C, } -(V, F) = <p(V). (8)
ln othër words, the values of FE ff that the relation associa tes with a given VE 'V are the elements of C such that the dissipated power -(V, F) is eq ual to cp (V).

Hence the name of the dissipation function, given to cp. For instance, in the case of Coulomb's law [START_REF] Hill | New horizons in the mechanics of solids[END_REF],

<p(V) = fN ! V I-

The convexity of C

Returning to the definition (6) of g*, one immediately finds that the relation

W E àg(F) is equivalent to g*(W) + g(F)-(W, F) = 0 ( 9
)
where the = sign may be replaced by � because the left-hand side is essentially non-negative. The above does not, in general, involve the symmetry between the spaces 'V and ff. ln fact, a polar function is, by construction, the supremum of a collection of continuous affine functions; therefore, it is convex and lower semi-continuous (l.s.c.) (relative to every topology compatible with the considered duality). As we started with an arbitrary g: ff-]-oo, +oo ], it cannot be expected, in general, that g would in turn be the polar function of g*. However, standard separation arguments (i.e., the Hahn-Banach theorem) may be used to prove that g is equal to g* if and only if g is convex and lower semi-continuous (for some of the topologies of the dual pair ('V, :IF,(.,.)), consequently for all of them). If such is the case, the symmetry of (9) implies that W E àg(F) is equivalent to FEag*(W).

ln the following, we shall deal with the special case g = 1/Jc; this function is convex and l.s.c. if and only if the subset C of ff is convex and closed. If such is the case, the friction law, as expressed equivalently by (4), ( 5) or [START_REF] Moreau | Sur les lois de frottement, de plasticité et de viscosité[END_REF], is also equivalent to

FE ài/1!(-V),

i.e., in view of the definitior (7) of <p, [START_REF] Moreau | On unilateral constraints, friction and plasticity[END_REF] Remark 1 A relation of this form between some velocity V and some force F may be called a resistance law, admitting the (convex and l.s.c.) function cp as superpotential or pseudopotential. The more general case, where cp is not necessarily sublinear, was studied in Moreau [START_REF] Moreau | Sur les lois de frottement, de plasticité et de viscosité[END_REF], where the connection of the superpotential with the dissipated power was also investigated.

Remark 2 In ail the following, the set C is assumed to be convex. As far as the contact friction is concerned, the contrary would seem unrealis tic. In fact, one must keep in mind that the point contact between two bodies is only a schematic representation of some contact which takes place on a very small area .'/1.. We may imagine, this area to be arbitrarily divided into two others, .'/1.

Product spaces

Let ('V 1 ; fffe 1 , (., .) i ) and ("V 2 , fffe 2 , (., .) 2 ) be two dual pairs of linear spaces. The two product spaces "V= "V 1 x "V 2 and ;ffe = fffe 1 x fffe 2 are placed in duality by the bilinear form (., .), defined as follows:

for v = (v 1 , v 2 ) E "V 1 x "V 2 and f= ( f1 , f2 ) Efffe 1 Xfffe 2 , set (12)
For instance, if v 1 , v 2 are some independent velocity parameters of a mechanical system and f 1 , f 2 are the associated force parameters such that the terms on the right in [START_REF] Les | Quelques applications variationnelles de la théorie des fonc tions duales à la mécanique des solides[END_REF] represent their respective powers, the bilinear form (v, f ) represents the power of the whole.

In this framework, the following is easily established. Let g 1 : fffe 1- ]-00, +oo] and g 2 : fffe 2 -]-oo, +oo] and let g be the function defined for every f=(f1 ,f2) in� by g<n = g1(f1) + g iCf2) .

If gt and g! are the respective polar functions of g 1 and g 2 , the polar function g* in the sense of the duality ( 12) is defined for every

v = (v 1 , v 2) in 'V by g*(v) = gi(v 1) + g!(v 2) .
Concerning the subdifferential sets, on the other hand, one has, in the sense of the three respective dualities, the equivalence 9 An example of composite friction law [START_REF] Nayroles | Opérations algébriques en mécanique des structures[END_REF] Let ;/ 1 be one of the wheels, with radius a, by which some vehicle ;/ 2 is supported, possibly with skidding, upon the horizontal ground ;/ 0 • We shall treat this wheel as a perfectly rigid body presenting a single point of contact M with the plane surface of the ground. Let us describe the friction at this point by means of the notations of section 2. The reaction R exerted by the ground on the wheel is written as R=F+Nv and, in view of (5), the Coulomb law takes the form -VE at/f 0( F ) , [START_REF] Nayroles | Point de vue algébrique, convexité et intégrandes convexes en mécanique des solides[END_REF] where D denotes the closed dise with radius fN, with centre at the origin in the two-dimensional Euclidean linear space II; recall that V is the sliding velocity of El 1 relative to ;/ 0 . On the other band a brake is supposed to act on the wheel. Let i denote a unit vector of the wheel axis, assumed to be parallel to the ground. Let h be the moment, relative to this oriented axis, of the forces that the wheel ;/ 1 experiences from the vehicle body ;/ 2 • Neither the driving torque nor the friction in the bearings are taken into account, so that h is, in fact, the braking torque. Let w be the angular velocity of ;/ 1 relative to El 2 • We assume that the operation of the brake involves a dry friction with a given normal component. This is expressed IJy a relation between the real numbers h and w, namely the one-dime• .sional case of the general formalis•'1 'Jresented in the foregoing. Her.: the space of velocities and the space of forces are two copies of the real line IR and the bilinear form 'power' reduces to the ordinary product. In the sense of this duality, the brake law is written as

(15)
where I denotes a given interval [-b, +b]; this summarizes the familiar relations: h=-bsgnw if w;éO and h arbitrary in

[-b,+b] if w = O.
In view of the preceding section, taking into account ( 14) and ( 15), we note that, equivalently, we have the relation -(w, V) E at/; 1 x o(h, F) [START_REF] Debordes | Sur la théorie et le calcul à l'adaptation des structures élastoplastiques[END_REF] in the sense of the duality ("V, fli, (., .)). Here, "V and f!li are two copies of the three-dimensional linear space IR x II; by definition, ((w, V), (h, F)) = wh +V• F [START_REF] Nguyen | Sur les lois de comportement élasto-visco plastiques à potentiel généralisé[END_REF] is the total power of the torque h and of the ground reaction R = F + Nv acting simultaneously on the wheel.

Here is the first problem we are to deal with in the following. The w. heel load, i.e., the normal component N of R, will be treated as known.

Let GE II denote the horizontal component of the resultant force experi enced by the vehicle f/2 from the wheel f/1. Let W E II denote the velocity of the wheel centre, which is also the velocity of the corresponding point of f/2 or the velocity of M, the 'geometrical' point of contact with the ground. Under the assumption that the wheel is sufficiently light and the motion sufficiently slow for the inertia of the wheel to be negligible, we are to summarize the combination of possible skidding on the ground and of possible brake action into a simple relation between W and G. It will turn out, under the above simplifying assumptions, that the wheel may be forgotten and the interaction between the vehicle and the ground be described as the anisotropie friction related to a certain convex set C.

This consists in the elimination of the variables w, V, h, F from the following set of relations.

(i) The kinematical relation

W=V-waj

expressing the fact that the whee\ is a rigid body; here j is the unit vector v xi. (ii) The quasi-equilibrium equations of the wheel:

G-F=O, h+aj•F=O.

(iii) The composite friction law [START_REF] Debordes | Sur la théorie et le calcul à l'adaptation des structures élastoplastiques[END_REF].

(19) (20)
An adequate use of various rules of the 'subdifferential calculus' would do the job, but it will be more instructive to place the reasoning in a general setting.

Let ('V, .'?1-) and ('V', .'?l-' ) be two dual pairs of linear spaces; both corres ponding bilinear forms will be denoted by (. , .). Let L: .'?l-'-.'?l-be a linear mapping; in infinite-dimensional cases, it will be assumed that L is continuous in the weak topologies of the dual pairs. Let g :.'?1--]-oo, +00] be convex and l.s.c.; then, the composite function g' = g O L: .'?l-' -]-oo , +oo] is convex and l.s.c. A classical rule of the 'subdifferential calculus' is the following (Rockafellar [START_REF] Rockafellar | Integrals which are convex functionals II[END_REF] ):

If there exists a point in the range of L, where the f unction g is fini te and continuous (in some topology of the dual pair ('V, .'?1-)), one has, for every F' in .'?l-',

a(go L)(F') = L *(ag(L( F '))),
where L * denotes the transpose of L. [START_REF] Laurent | Approximation et Optimisation[END_REF] Application Returning to our mechanical problem, let us set 'V= .'?l-= IR x II with the duality defined in [START_REF] Nguyen | Sur les lois de comportement élasto-visco plastiques à potentiel généralisé[END_REF]. Moreover, let 'V'= .'?l-' = II with the duality defined by the Euclidean scalar product and define L: .'?l-'-g; by

L(G) = (-aj • G, G).

Elementary computation yields the transpose L * :'V-'V', namely L *(w, V)= V -waj.

Then, [START_REF] Nguyen | Matériaux élasto-visco-plastiques et élastoplastiques à poten tiel généralisé[END_REF] amounts to W= L *(w, V), while [START_REF] Moreau | Fonctionnelles convexes, Séminaire sur les équations aux dérivées partielles[END_REF] and ( 20) are condensed into (h, F) = L(G).

Take g = t/lrxo, so that ( 16) takes the form

-(w, V) E ag(h, F).
The elimination of w, V, h, F from ( 22), ( 23), ( 24 Thi,;, indeec!. is the necessary and sufficient condition to be satisfi' d t; W and G in order that there exist w, V, h, F which also satisfy the above conditions.

Suppose now that the interval 1 and the dise D do not degenerate into single points; then the zero of .'?l-constitutes a point in the range of L where g is continuous; thus (21) holds, making [START_REF] Moreau | Systèmes élastoplastiques de liberté finie[END_REF]

equivalent to

Here is the expression for the function g O L:

(g 0 L)(G) = t/Jrxo(-aj • G, G) = { 0 if -aj •GE I
-WEàtf; c (G), ( 26
)
which constitutes a friction law in the general sense of section 3. As announced, this presents the interaction between the vehicle and the ground by forgetting the wheel. Recall that N, the load supported by the wheel, is treated as known.

Let us now discuss. the various cases.

(i) If b;;;,, afN, the width of the strip B is greater than or equal to the diameter of the dise D; hence, C = D. This means that the brake is so tightly applied that the wheel stays always locked; thus, the interaction between the vehic\e and the ground amounts to the simple Coulomb friction.

(ii) If b < afN the shape of C is shown in Fig. l. Recall that (26) expresses that GE C and that, in the classical generalized sense, W is an inward normal vector to C at the point G (in particular, W is necessarily zero if G is internai to C). The presence of the rectilinear parts in the boundary of C implies that a value of W parallel to j (i.e., normal to the wheel plane) corresponds to an infinity of possible values of the force G. The presence of corner points in the boundary implies that these corner 0 i Fig. 1 values of G correspond to an infinity of values for W, the set of them form a closed convex angular region in IT.

Note that some more refined arguments of convex analysis (see, for example, Rockafellar [START_REF] Rockafellar | Convex Analysis[END_REF], Theorem 23.8) allow us to remove the assumption b ,t O made in the foregoing. The case b = 0 is that where no brake is applied; then, C reduces to a line segment and ( 26) describes an extreme case of anisotropie friction. Such a side-slipping free wheel is the key device of the Amsler planimeter and of some other ancient integrat ing instruments.

Remark

The above computation involving a pair of mutually transpose linear mappings L and L * is more than an occasional mathematical trick.

It is based on the fact that the rigidity of the wheel constitutes a perfect mechanical constraint; in fact, the externat forces applied to the wheel may be summarized as:

(i) the force F applied to the contact point (as the normal component Nv does not matter here); (ii) the force -G applied to the wheel centre; (iii) the axial torque h.

By the definition of a perfect constraint (see more developments and examples in Moreau [START_REF] Moreau | La convexité en statique[END_REF][START_REF] Moreau | On unilateral constraints, friction and plasticity[END_REF]) the (quasi-)equilibrium condition of the wheel may be expressed by the fact that the above system of forces should yield a zero power for every set of values of the velocity parame ters V, W, w satisfying the kinematical equations of constraint, namely [START_REF] Ekeland | Analyse• Convexe et Problèmes Variationnels[END_REF]. In other words, -G • L*(w, V)+F •V+ hw = 0 must hold for every (w, V); by the definition of transpose mappings, this is precisèly [START_REF] Robertson | Topological Vector Spaces[END_REF].

The principle of minimum dissipation

The purpose of the preceding section was the elimination of V, the sliding velocity of the wheel on the ground, and w, the sliding angular velocity in the brake. A complementary problem now is t.h.e determinati0n of these sliding velocities when the motion of the vehicL: is treated as irnown, i.e., when W is �iven. The existence of at least c .1e solution w, V for every W E IT results from the preceding section, in view of the compactness of C.

For a given W, the set of the pairs (w, V) satisfying the kinematical condition of rigidity of the wheel ( 22) is an affine subrnanifold i of IR x II, namely 't; = {(w, V) E!RX II :V -waj = W}.

Introducing its indicator function ifJ -'61 , one observes that the subdifferen tial set atf!'l! (w, V), empty if (w, V)é 'tJ, consists otherwise in the subspace of IR x II orthogonal to i; this is precisely the set of the pairs (h, F) satisfying the quasi-equilibrium condition [START_REF] Robertson | Topological Vector Spaces[END_REF] for some G. Thus, [START_REF] Ekeland | Analyse• Convexe et Problèmes Variationnels[END_REF] and ( 23) are equivalently condensed into (h, F) E atf!'l! (w, V).

(

(Regarding such an interpretation of perfect constraints as 'resistance laws' with pseudopotentials, see Moreau [START_REF] Moreau | Sur les lois de frottement, de plasticité et de viscosité[END_REF][START_REF] Moreau | On unilateral constraints, friction and plasticity[END_REF].) On the other hand, using section 6, the composite friction law ( 16) is equivalently written as (-h, -F)Eacp(w, V), where cp: IR x II -'>IR de notes the total dissipation function

cp(w, V)= o/ixo (-w, -V)= t/!i' ( -w)+ t/!'b(-V) = b l w l + fNI VI.
The elimination of h and F from ( 27) and ( 28) yields (0, O)Eat/! 'l! (w, V)+acp(w, V).

(28) (29) (30)
Since the function cp is continuous, the addition rule for subdifferentials (cf., Moreau [ 4] or the books [START_REF] Moreau | Fonctionnelles convexes, Séminaire sur les équations aux dérivées partielles[END_REF][START_REF] Rockafellar | Convex Analysis[END_REF][START_REF] Laurent | Approximation et Optimisation[END_REF][START_REF] Ekeland | Analyse• Convexe et Problèmes Variationnels[END_REF]) may be applied so that (30) exactly expresses that (w, V) is a point of !RX II, where the function o/ 'I! + cp attains its minimum. Recalling that the function o/ ii takes the value zero on 'lJ and +oo elsewhere, one concludes as follows.

If W is given, the values of w, V solving the problem minimize the dissipation function (29) under the kinematical condition (18).

Consequently, if one is only interested in the unknown w, it turns out that the values of it which salve the problems are exactly the points of 1R where the function w�fNIW+wajl+b l wl attains its minimum.

Remark The preceding expresses a minimization 'principle' for the dissipation fonction restricted to the set of the 'kinematically admissible' velocities. The same is a cictssical feature in plasticity theory. (Concerning the use of convex analysis in treating the variational properties of elastoplastic systems, see Moreau [START_REF] Moreau | Systèmes élastoplastiques de liberté finie[END_REF].) Another interesting example, involving a continuous system, is that of a heavy perfectly flexible inextensible rope lying with dry friction on a horizontal plane. Here, the velocity distribution entailed in quasistatic evolution by some imposed motion of the rope extremities, is characterized by minimizing the dissipa tion function on the set of the velocity distributions agreeing with these end conditions and with inextensibility.

Quotient spaces

We present now an abstract structure in which the reader will recognize a generalization of the foregoing.

Let us consider a mechanical system in a given configuration. Let 'Y denote a linear space, the elements of which constitute, in some general sense, the possible values of the velocity of the system if it passes through the considered configuration. Let � denote a linear space the elements of which are, in a general sense, the possible values of the various forces the system may experience in this configuration. These two spaces are placed in duality by the bilinear-form 'power' noted (. , .) .

The spaces 'Y and � may have very diverse functional realizations, namely spaces of vector fields, of tensor fields, etc. and the considered mathematical procedure can usually be applied to a given mechanical situation in several different ways (see, for example Moreau [START_REF] Moreau | On unilateral constraints, friction and plasticity[END_REF], Nayroles [START_REF] Nayroles | Point de vue algébrique, convexité et intégrandes convexes en mécanique des solides[END_REF].)

Let us suppose that the system is subject to a friction force F obeying the law (31) where C is a given convex subset of � ' closed in the topologies of the dual pair ('Y,� ' (.,.)) . In addition, the system experiences a moving constraint or 'driving' which implies that its velocity V belongs to a certain affine submanifold 'if; of 'Y, a translate of some given linear subspace "W of "V, closed in the topologies of the dual pair ('Y,�,(., .)) . Specifying 'if; among the various translates of 'W amounts to prescribing an element W of the quotient space "V/"W: we shall refer to this element as the driving velocity (mathematically, 'if; and W are the same thing but using two notations seems clearer in mechanical applications ) .

The moving constraint is assumed to be perfect, i.e., the 'force' RE� exerted on the system by the driving devic is o, thogona. to the affine manifold 'if;, in the sense of the duality ('Y. ffe, (., .)) (32)

The constraint is also assumed to be firm, i.e., the driving device is strong enough to provide any value of R satisfying (32) . (Concerning the concept of the firmness of a mechanical constraint, see Moreau [26].) The opposite, G = -R, may be interpreted as the resistance of the system to the driving.

Inertia is neglected, so that the motion is characterized by the quasi static equation G=F.

(33)

The duality ("Il", ;ffe, (., .)) classically induces a duality between the pair "11"/'W and 'W 1. . Our purpose is the elimination of V and F, yielding a relation between the elements W and G of the latter dual pair. . Converse/y, if 'W 1. meets the interior of C (in some topology of the dual pair "Il", ;j;), every ( W, G) satisfying (34) corresponds to at least one pair ( V, F) agreeing with above conditions.

Under the same topological assumption, the dissipation function 'Y of the friction law (34) is defined on "11"/'W by

-y (W) = min cp(U), U,s� (35)
where cp denotes the dissipation function of the friction law (31).

For the proof, we may call L the natural injection of 'W 1. into g; and L * its transpose, namely the natural surjection of -:Y onto "V/'W. This allows us to write the conditions of the problem in the form

F= L(G)

W= L *(V) by which the elimination of V and F from (31) leads to

-W EL *(at{lc(L( G))). ( 36
)
Since t/lc O L = t/lo, the computation rule of section 10 yields the equivalence of (34) to (36), because the assumption that 'W 1. meets the interior of C means the existence of a point of the range of L where t/lc is finite and continuous. Without this assumption, however, (36) is easily proved to entai! (34); this is the first statement of tliè proposition.

Finally, (35) results from the computation rule for (t/lcoL)* (see Rock afellar [START_REF] Rockafellar | Integrals which are convex functionals II[END_REF], Theorem 3).

The above proposition, involving the quotient space "11"/'W, may be described as a way of processing some partial information about the considered mechanical system. Actually, science is always dealing'with partial information about nature; thus, it could be said that similar constructions of quotient spaces implicitly underlie every scientific act.

As in Section 11, let us turn now to the complementary question of characterizing the value of V corresponding to a given W, which, inciden tally, will throw some light on the expression (35) of y.

Proposition 2 In the affine manifold '€, the set of the elements V satisfying the conditions of the problem, if not empty, is equal to the set of the points where the restriction <p \" of the dissipation function <p attains a finite minimum.

If moreover, there exists a point in '€ where <p is finite and continuous (in some topology of the dual pair 'V, �) the two above sets are equal, even if the first one is empty.

In fact, the conditions VE '8 and FE "W" J. are condensed into FE atfi <t: (V), while (31) is, by section 7, equivalent to -FEa <p (V).

Therefore, the values of V satisfying the conditions of the problem are characterized by o E atfi� (V) +a<p (V).

(37)

In view of the trivial inclusion (38) this property implies that the function t/ J� + cp (equal to cp on '€ and taking the value +oo elsewhere) achieves a finite minimum at the point V. Suppose the existence of at least one pair V, F satisfying the conditions of the problem; then, in view of (8), <p( V) = -( V , F). Let V' denote another point where the restriction of <p to '€ attains its minimum; then, cp(V)= <p (V'). As V-V'E"W" and FE"W" J. , one has (V, F) = (V', F); thus, <p( V')= -(V', F) which proves that V' satisfie�, with the same F, the condit:Jns of the problem. This proves the first part of the proposition.

Finally the existence of a point in '€ where cp is finite and continuous implies that the inclusion (38) is actually an equality of sets (see, for example, Moreau [START_REF] Moreau | Fonctionnelles sous-différentiables[END_REF]; then, the fact that cp I l€ attains a finite minimum at the point V is equivalent to (37).

Re m ark All the preceding could be adapted to the case where the system experiences, in addition, some given constant load, namely GE$. This amounts to replacing C by its translate C + G. If this set meets "W .L , there may exist, for some given driving velocity W E 'V/"W, a quasi-static evolution of the system.

  1 and .'/1. 2 , in which the sliding velocity has the same value, namely zero in what follows. Let R 1 and R 2 be the resultant forces experiènced by 9\ through .'/1. 1 and .'/1. 2 , respectively. Then (11) and, concerning the normal components, one has N = N1 + N2• The values of N 1 and N 2 in the last equation depend on some 'micro-information' about the distribution of pressure in .:/1.. In order to obtain a law which does not depend on the microscopie pressure distribution in .'/1. for the global reaction R, one must admit the followirig as the law of friction in every subarea such as .:/1. 1 (or .'/1. 2 , or .'/1. itself): for zero sliding velocity and an arbitrary non-negative pressure component, the set of the possible values of R 1 (or R 2 or R) is a conic subset I', with vertex at the origin in the space of the three-dimensional vectors. And (11) entails the inclusion r + r Cr, which means that r is convex. Returning to the formulation (4), one finds that I' is the cone generated in the space of three dimensional vectors by the set C + Nv; hence, the convexity of C.

  and GE D, +co otherwise. In other words g O L is the indicator function of the closed convex subset C = B n D of II, where• B denotes the strip B = {GEII:-�.:;;j • G��}-Hence, the final form of (25),

Proposition 1

 1 If the above conditions are satisfied, the elements W and G satisfy (34) in the sense of the dual pair of spaces "11"/'W and 'W 1. , with D= Cn'W 1.


Thi-Lan Le
email: thi-lan.le@mica.edu.vn

Alain Boucher
email: alain.boucher@auf.org

Monique Thonnat
email: monique.thonnat@sophia.inria.fr

Subtrajectory-Based Video Indexing and Retrieval

This paper proposes an approach for retrieving videos based on object trajectories and subtrajectories. First, trajectories are segmented into subtrajectories according to the characteristics of the movement. Efficient trajectory segmentation relies on a symbolic representation and uses selected control points along the trajectory. The selected control points with high curvature capture the trajectory various geometrical and syntactic features. This symbolic representation, beyond the initial numeric representation, does not suffer from scaling, translation or rotation. Then, in order to compare trajectories based on their subtrajectories, several matching strategies are possible, according to the retrieval goal from the user. Moreover, trajectories can be represented at the numeric, symbolic or the semantic level, with the possibility to go easily from one representation to another. This approach for indexing and retrieval has been tested with a database containing 2500 trajectories, with promising results.

Introduction

Advances in computer technologies and the advent of the World Wide Web have made an explosion of multimedia data being generated, stored, and transmitted. For managing this amount of information, one needs developing efficient contentbased retrieval approaches that enable users to search information directly via its content. Currently, the most common approach is to exploit low-level features (such as colors, textures, shapes and so on). When working with videos, motion is also an important feature. When browsing a video, people are more interested in the actions of a car or an actor than in the background. Moving objects attract most of users' attention. Among the extracted features from object movement, trajectory is more and more used. In order to use the trajectory information in content-based video indexing and retrieval, one must have an efficient representation method allowing not only to index trajectories, but also to respond to the various kinds of queries and retrieval needs. For retrieval aspects, the matching strategies is also of importance.

Matching to compare between trajectories can be done globally or partially. For global matching, the whole trajectories are compared to each other. However, objects in videos can undergo complex movements, and global matching can prevent from retrieving a partial but important section of the trajectory. In some cases, the user can be interested in only one part of the object trajectory. Therefore, it is useful to segment a trajectory into several subtrajectories and then match the subtrajectories. How to match subtrajectories and how to combine all partial results into a final retrieval result is not as trivial as it seems. In [START_REF] Chenn | Motion trajectory matching of video objects[END_REF], the authors have segmented the object trajectory into subtrajectories with constant acceleration. But this approach do not consider the case where the object changes direction. In [START_REF] Bashir | Object Motion Trajectory-Based Video Database System Indexing, Retrieval, Classification, and Recognition[END_REF], after segmenting a trajectory into subtrajectories, the authors computed the PCA coefficients for each subtrajectory. However, with only one matching strategy, it cannot satisfy all user needs.

In the retrieval phase, queries from the user can be done at the numeric, symbolic or semantic level. Many interaction levels allow the user to be more flexible regarding his/her needs. Similarly, distances between a query and the database can be measured according to one level or another. Another important aspect in interactive retrieval is the relevance feedback, which allows an user to refine the query. A good representation scheme and efficient matching strategies must take into account all these aspects, taking care of both indexing and retrieval.

After introducing all these aspects, the main contributions of this paper are the following: Integrate into a representation scheme numeric, symbolic and semantic levels for trajectory-based video indexing and retrieval; Propose a trajectory segmentation algorithm working at the symbolic level, to avoid the problem of sensibility to noise at the numeric level, and invariant to rotation, translation or scaling; Present different trajectory and subtrajectory matching strategies; Go toward semantic trajectory-based video indexing and retrieval.

The rest of the paper is organized as follow. In Section 2, we are proposing a structure for a SubTrajectory-based Video Indexing and Retrieval (STBVIR), which includes control point selection, trajectory representation at the numeric and the symbolic level, trajectory segmentation into subtrajectories and matching strategies. In section 3 we are presenting some aspects linked to semantic. Some experimental results are shown in section 4. Section 5 is concluding this paper with some directions for future work.

2 SubTrajectory-Based Video Indexing and Retrieval

General description

We are proposing an architecture of STBVIR (figure 1). In this architecture, object tracking is done by a preprocessing module (not shown here), and object trajectories are taken as input. In the real physical world, a trajectory is represented following 3 dimensions. Without a priori contextual information, trajectories can be represented in 2D. Knowing the application and its context, it can be useful to represent a trajectory in 3D or to map the 2D trajectory into the monitored environment [START_REF] Piciarelli | Trajectory clustering and its applications for video surveillance[END_REF]. In this paper, we will consider only the general case in 2D, without a priori knowledge on the application. For indexing, all object trajectories are processed through four modules. The output is a symbolic representation of the global trajectory or its subtrajectories or only some selected control points along the trajectory. For retrieval, given a trajectory query by the user, comparison is made with the trajectories in the database, at the numeric or the symbolic level. Trajectories that are most similar (given a matching strategy) with the trajectory query will be returned to users.

Control point selection

A symbolic representation can take all the individual trajectory points as input. But doing so, computation time can be high, as well for the symbolic representation as for the trajectory matching. Selecting control points with high curvatures along the trajectory before computing its representing can help greatly. Selected control points can capture the trajectory's various geometrical and syntactic features. As one can see in section 4, the results from the two cases, using all points or only some selected control points, are very similar, but the second case takes much less time to compute. Moreover, selected control points and their symbolic representation allow us to propose a segmentation method as described in the next section.

First, we are describing the control point selection method of [START_REF] Hsieh | Motion-Based Video Retrieval by Trajectory Matching[END_REF]. Given a sequence, T = [(x 1 , y 1 ), ..., (x n , y n )], n being the length of T , T can be represented by T = [p 1 , .., p n ]. Let α(p) be the angle of a point p in T , determined by two specified points p + and p -which are selected from both sides of p along T (figure 2.a) and satisfy

d min ≤ |p -p + | ≤ d max and d min ≤ |p -p -| ≤ d max (1)
where d min and d max are two thresholds. d min is a smoothing factor used to reduce the effect of noise from T . With p + and p -, the angle can be computed using

α(p) = cos -1 ||p -p + || 2 + ||p -p -|| 2 -||p + -p -|| 2 2||p -p + ||||p -p -|| (2)
If α(p) is larger than a threshold T α , set to 150 here, the point p is selected as a control point. In addition to equation 2, it is expected that the two control points are far from each other, to enforce that the distance between any two control points is larger than the threshold defined in [START_REF] Chenn | Motion trajectory matching of video objects[END_REF]. If the two candidates are too close to each other, i.e. ||p 1 -p 2 || ≤ d min , the one with the smaller angle α is chosen as the best control point (figure 2.b).

Numeric trajectory representation module

Working with raw data from the object trajectory is not always suitable because these data are sensible to noise and are affected by rotation, translation and scaling. In order to cope this problem, we have chosen among the existing representation methods the one from [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF], which also uses both direction and distance information of the movement. With a given sequence, T A = [(x a,1 , y a,1 ), ..., (x a,n , y a,n )], n being the length of T A , a sequence of (movement direction, movement distance ratio) pairs M A is defined as a sequence of pairs: M A = [(θ a,1 , δ a,1 ), ..., (θ a,n-1 , δ a,n-1 )]. The movement direction is defined as:

θ a,i =        arctan y a,(i+1) -y a,(i)
x a,(i+1) -x a,(i) -π if x a,(i+1) -x a,(i) ≺ 0 and y a,(i+1) -y a,(i) ≤ 0 arctan y a,(i+1) -y a,(i) x a,(i+1) -x a,(i) if x a,(i+1) -x a,(i) ≥ 0 arctan y a,(i+1) -y a,(i)

x a,(i+1) -x a,(i) + π if x a,(i+1) -x a,(i) ≺ 0 and y a,(i+1) -y a,(i) 0

(3) and the movement distance ratio is defined as follows:

δ a,i = √ (y a,(i+1) -y a,(i) ) 2 +(x a,(i+1) -x a,(i) ) 2 T D(T A ) if T D(T A ) = 0 0 if T D(T A ) = 0 (4) T D(T A ) = 1≤j≤n-1 (y a,(j+1) -y a,j ) 2 + (x a,(j+1) -x a,j ) 2 (5)
Raw trajectory data given to this module become a sequence of pairs of movement direction and movement distance ratio. We can use directly this sequence to compare trajectories or we can use it as an intermediate information for the symbolic representation module.

Symbolic trajectory representation module

Using the previous numeric representation for trajectories, a proposed symbolic representation from [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF] is computed as follows:

Given dir and dis , the two dimensional (movement direction, distance ratio) space is divided into 2π dir * 1 dis subregions. Each subregion SB i is represented by two (movement direction, distance ratio) pairs: (θ bl,i , δ bl,i ) and (θ ur,i , δ ur,i ), which are the bottom left and upper right coordinates of SB i . A distinct symbol A i is assigned for subregion SB i of size dir * dis . A pair of movement direction and movement distance ratio (θ a,i , δ a,i ) will be represented by a symbol A i if θ bl,i ≤ θ a,i ≺ θ ur,i and δ bl,i ≤ δ a,i ≺ δ ur,i .

Segmentation

From an original trajectory composed of n points T = [(x 1 , y 1 ), ..., (x n , y n )], a new trajectory, shorter than the original one, is obtain after control point selection: T = [(x 1 , y 1 ), ..., (x m , y m )] where m ≤ n. This trajectory is transformed into a symbolic representation S = [(A 1 , ..., A m )] using the quantization map shown in figure 3.a.

Let A I be the set of symbols with θ being smaller than 0 and A II be the set of symbols with θ greater than 0. An object going down gets a symbol belonging to A I (down to the left or to the right), and an object going up gets a symbol belonging to A II (up to the left or to the right). Therefore, by scanning a symbolic representation until a change in direction is detected (i.e. symbol at time t belongs to A I and symbol at time t+1 belongs to A II , or the opposite), we can create a new subtrajectory including all the points from the last change in direction to this new change, and so on until the end of the trajectory.

Subtrajectory-based video indexing and retrieval

Let T Q = [(x 1 , y 1 ), ..., (x n , y n )] be a query trajectory. Following the segmentation algorithm that we have described in section 2.5, we can segment it in N subtrajectories T Q = {T 1Q , ..., T N Q }. Let T D be a trajectory from the indexed databases divided into M subtrajectories T D = {T 1D , .., T M D }. With all these subtrajectories, we compute their numeric and their symbolic representations. Doing so, we can compare them using either the Edit Distance on Real Sequence (EDR) on the numeric representation or the Edit Distance on Movement Pattern String (EDM) on the symbolic representation [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF].

For subtrajectory-based video indexing and retrieval, choosing a good and efficient matching strategy is important to take into account the various user needs. If the user is interested in the whole trajectory, a global matching strategy is a valuable choice, and if he/she just makes more attention in few parts of the trajectory, partial matching is then the privileged choice. Inspiring ourselves from [START_REF] Chenn | Motion trajectory matching of video objects[END_REF], we are giving here some different matching strategies: two global matching strategies (dominant segment (GD) and full trajectory (GF) matching) and three partial trajectory matching strategies (strict partial (SP), relative partial (RP) and loose partial (LP) matching). In the following, d Dist (T iQ , T jD ) is the distance between a subtrajectory T iQ and a subtrajectory T jD . Dist can be EDR or EDM . Note that L iQ and L jD are the length of T iQ and T jD respectively.

-Global trajectory matching

• Dominant segment matching (GD) Only the dominant subtrajectory is used to match with those in the database. Dominant subtrajectories can be identified as segments with the smallest EDR or EDM distances.

d Dist (T Q , T D ) = min(d Dist (T iQ , T jD )) (6)
• Full trajectory matching (GF): All subtrajectories in the original trajectory must match those in the database as described above.

d Dist (T Q , T D ) = N i=1 M j=1 w T iQ w T jD d Dist (T iQ , T jD ) (7)
where

w T iQ = L iQ N k=1 L kQ and w T jD = L jD M k=1 L kD (8)
-Partial trajectory matching: A subset of subtrajectories is selected to match those in the database, and matching is specified in terms of order. Matching between two subtrajectories is computed using:

match Dist (T iQ , T jD ) = true if d Dist (T iQ , T jD ) ≤ T hreshold Dist (9) match Dist (T iQ , T jD ) = f alse otherwise (10)
• Strict partial matching (SP): The matched subtrajectories between the query and the database must be strictly in the same order. • Relative partial matching (RP): The relative order of the matched subtrajectories between the query and the database must be the same. • Loose partial matching (LP): No constraint is given on the order of the matched subtrajectories. Just match a subset of subtrajectories between the query and the database.

Toward a semantic trajectory-based video indexing and retrieval

The word semantic is more and more used in the information retrieval domain (in many different ways). The given symbolic representation and segmentation method allow us to go toward a more semantic subtrajectory-based video indexing and retrieval. Using the quantization map of figure 3.a, a sequence of symbols representing a trajectory can be translated into a sequence of semantic words, as shown in figure 3.b.

In order to transform a symbolic representation of a trajectory into a semantic representation, some abstraction heuristics must be used. For example, if more than 80% of the symbols of a trajectory belong to the set {'M','N','E','F'} (figure 3.a) it can be said that this trajectory has the 3 characteristics {Go up, Slow, right}. In the example of 3.b, the original trajectory is segmented into two subtrajectories. After the symbolic representation phase for the selected control points, the trajectory is represented by 8 symbols 'EFEEELLK'. The first subtrajectory has 5 symbols (EFEEE) while the second one has 3 symbols (LLK). This trajectory can be abstracted saying that first the objet Go(es) up Slow ly on the right and then it Go(es) down Slow ly still on the right.

Using this scheme, the user can give a query at the numeric, symbolic or semantic level. Comparison between (sub)trajectories can be done so far at the numeric (EDR distance) or at the symbolic (EDM distance) level (figure 4.a). At the symbolic level, the user gives a query using a sequence of symbols, the EDM distance and the proposed matching strategies are used. At the semantic level, the semantic query is first parsed into a symbolic query. Then, the EDM distance and the symbolic matching strategies are used. (b) A given semantic query is parsed into a symbolic representation following two different parsing methods.

To process a semantic query, one must first parse it into a symbolic representation. But more than one symbol can correspond to a sole semantic word. For this reason, two methods are possible for parsing the semantic query. The first one is to choose a representative symbol from a semantic characteristic of the movement, using an Ap match comparison like in [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF]. A i Ap match A j if and only if A i = A j or A i is neighboor of A j . The second method is to generate all possible symbolic sequences and then, combine or choose between all the matching results (following some pre-defined strategies). In figure 4.b, given the semantic query "Give me a video containing an object that Go(es) up Slow ly on the right in 5 time units", then the two corresponding symbolic sequences, according to both parsing methods, are shown.

This preliminary discussion about semantic aspect in subtrajectory-based video indexing and retrieval is still on-going work, but we can foreseen some promising results in achieving semantic indexing and retrieval.

Experiments and results

In order to analyze our system performances, we have used the free trajectory database4 containing 2500 trajectories coming from 50 categories.

Recall and precision curves are widely used to evaluate performance of information retrieval system. In our tests, we have set n/20 and n/15 for d min and d max respectively where n being the length of T. We have chosen dir = π/4 and dis = 0.125 for the symbolic representation. Figure 5.a shows the results of our system with all individual of trajectory or some selected control points using the EDR distance for numeric representation and the EDM distance for symbolic representation. One can realizes that results using selected control points with the EDR distance are comparable with those using all points from the trajectory. The EDR distance in both cases gives better results than the EDM distance. (a) Recall/precision curve for the EDR and EDM distance with all points from the trajectory and only the selected control points. The curve with green stars and the one with yellow triangles present retrieval results using the EDR distance with all points from trajectories and only selected control points respectively. The curve with violet circles and the one with blue rectangles present retrieval results using the EDM distance with all points from trajectories and only selected control points respectively (b) Recall/precision curve for the EDR distance with different matching strategies. The curve with triangles presents retrieval results using the EDR distance with the Full trajectory (GF) matching strategy while the curve with circles presents retrieval results using the EDR distance with the Dominant segment (GD) matching strategy Figure 5.b shows the results of our system with different global matching strategies, GF and GD with the EDR distance. With this database, the results with the GF matching strategy are better than with the GD matching strategies. However, in the case where the user is interested in only one part of trajectory, the GD matching strategy is an efficient choice. Figure 6.a shows the results for the three partial matching strategies, SP, RP and LP, using a threshold of 60 and the EDR distance.

Query acquisition and result display is an important but difficult task in trajectory-based video indexing and retrieval. We have implemented a retrieval interface, as shown in figure 6.b. The trajectory query drawn on the left and the first sixteen result images on the right are shown sorted with their EDR distance with the trajectory query. It is possible to draw the corresponding trajectories from a numeric or a symbolic representation.

Conclusions and future work

In this paper, a subtrajectory-based video indexing and retrieval system has been proposed. Our system has some notable characteristics. Firstly, it allows the users The curve with green triangles presents the retrieval results using the EDR distance with the SP strategy, the curve with violet circles presents retrieval results using the EDR distance with the RP matching strategy and the curve with blue rectangles presents retrieval results using the EDR distance with the LP matching strategy (b) System interface for retrieval, the trajectory query being on the left and the first sixteen result images on the right shown according to their EDR distance with the trajectory query.

to search desirable trajectory or only part of a trajectory (according to many matching strategies). It effects both EMD and EDR distance that count similar subsequences and assign penalties to the gaps in between these subsequences. Thus, unlike Longest Common SubSequence (LCSS) [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF], it does consider gaps within sequences. Secondly, it offers a fast searching (because the trajectories or their subtrajectories are compared by matching only their selected control points), and it allows an efficient segmentation method based on a symbolic representation that is invariant to rotation, scaling and translation. Finally, all these advantages allows us to go toward semantic trajectory-based video indexing and retrieval system, although further work is needed to fully achieve it.

Fig. 1 .

 1 Fig. 1. Architecture for subtrajectory-based video indexing and retrieval

Fig. 2 .

 2 Fig. 2. Selecting control points along a trajectory T . (a) Control points (like p) are shown along the trajectory T . p -and p + are linked to the point p by satisfying the angle constraint given by the Equation 1. (b) p1 and p2 are two selected control points too close to each other. The one with the smaller angle α will be chosen as the best control point [4].

Fig. 3 .

 3 Fig. 3. (a) Quantization map used for symbolic representation with their corresponding semantic expressions. (b) An example of parsing from a symbolic to a semantic representation using this map.

Fig. 4 .

 4 Fig. 4. (a)Three levels for trajectory representation. At the numeric level, the user draws a query, the EDR distance and corresponding matching strategies are used.At the symbolic level, the user gives a query using a sequence of symbols, the EDM distance and the proposed matching strategies are used. At the semantic level, the semantic query is first parsed into a symbolic query. Then, the EDM distance and the symbolic matching strategies are used. (b) A given semantic query is parsed into a symbolic representation following two different parsing methods.

  Fig. 5.(a) Recall/precision curve for the EDR and EDM distance with all points from the trajectory and only the selected control points. The curve with green stars and the one with yellow triangles present retrieval results using the EDR distance with all points from trajectories and only selected control points respectively. The curve with violet circles and the one with blue rectangles present retrieval results using the EDM distance with all points from trajectories and only selected control points respectively (b) Recall/precision curve for the EDR distance with different matching strategies. The curve with triangles presents retrieval results using the EDR distance with the Full trajectory (GF) matching strategy while the curve with circles presents retrieval results using the EDR distance with the Dominant segment (GD) matching strategy

Fig. 6 .

 6 Fig.6. (a) Results for the SP, RP, LP matching strategies. The curve with green triangles presents the retrieval results using the EDR distance with the SP strategy, the curve with violet circles presents retrieval results using the EDR distance with the RP matching strategy and the curve with blue rectangles presents retrieval results using the EDR distance with the LP matching strategy (b) System interface for retrieval, the trajectory query being on the left and the first sixteen result images on the right shown according to their EDR distance with the trajectory query.

http://mmplab.eed.yzu.edu.tw/trajectory/trajectory.rar