Thị Lê

Alain Lan

Monique Boucher

Thonnat

AN INTERFACE FOR IMAGE RETRIEVAL AND ITS EXTENSION TO VIDEO RETRIEVAL Xây

Keywords: Image and Video Indexing and Retrieval, Visualization, Relevance Feedback Tóm tắt:

Semantic video retrieval is still an open problem. While many works exist in analyzing the video contents, few ones present the retrieval results to the users and interact with him/her. In this article, firstly, we propose a 2D graphic interface adapted to the problem of image retrieval that enables a bidirectional communication: from the system towards the user to visualize the current research results and from the user towards the system so that the user can provide some relevance feedback information to refine his/her query. In this interface, the visualization shows the image query in the middle of the screen and the result images in a 2D plan with distances showing the similarity measures between images and the query. We propose also a method of relevance feedback in form of validation, in this interface, for image retrieval. This approach has been implemented and tested with different image databases. Secondly, we analyze the extension of this approach for video retrieval. For this, we extract the key frames from video and use them to represent the research results of video as well as to do the relevance feedback.

Tìm kiếm video theo ngữ nghĩa vẫn còn là một vấn đề mở. Trong khi có rất nhiều nghiên cứu về phân tích nội dung của video, chỉ một số rất ít các nghiên cứu về biểu diễn kết quả tìm kiếm và tương tác với người sử dụng. Trong bài báo này, đầu tiên chúng tôi sẽ đề xuất giao diện đồ hoạ 2 chiều phù hợp cho hệ thống tìm kiếm ảnh, cho phép giao tiếp theo hai chiều : chiều từ hệ thống tới người sử dụng cho phép hệ thống biểu diễn kết quả tìm kiếm hiện thời đối với người sử dụng và chiều từ người sử dụng đến hệ thống cho phép người sử dụng cung cấp các thông tin phản hội lại hệ thống.

Trong giao diện này, ảnh truy vấn sẽ nằm ở giữa trục toạ độ, các ảnh kết quả sẽ nằm trên hệ trục toạ độ 2 chiều với các biên độ là các độ đo tương tự theo các đặc trưng của ảnh kết quả và ảnh truy vấn. Một giải thuật cho phép hệ thống học các thông tin phản hồi từ người sử dụng cũng được đề xuất. Giải thuật này được cài đặt và thử nghiệm trên nhiều cơ sở dữ liệu khác nhau. Sau đó, một khả năng mở rộng cách tiếp cận này cho tìm kiếm video cũng được trình bày. Các khung hình chính được trích chọn từ video và được sử dụng để tìm kiếm cũng như tương tác với người sử dụng.

Từ khoá: Chỉ số và tìm kiếm ảnh và video, biểu diễn kết quả, phản hồi người sử dụng

INTRODUCTION

Image indexing and retrieval appeared from 1992 [START_REF] Kato | Query by visual example in content-based image retrieval[END_REF]. Up to now, some results has been obtained but it's still an open problem in comparing with obtained results in text retrieval. It's still true that concerns the semantic image indexing and retrieval. Indeed, the images in image databases were indexed by their low features but not by their semantic contents. Therefore, it has always a semantic gap [START_REF] Smeulders | Content-Based Image Retrieval at the End of the Early Years[END_REF].

In order to fill up this semantic gap, two main approaches are possible: one is to index the images by their semantic contents in the form of ontology [START_REF] Maillot | Ontology Based Object Learning and Recognition[END_REF], another that we will present in this paper is to interact with the users in order to understand their needs [START_REF] Rui | Relevance Feedback: A Power Tool for Interactive Content-Based Image Retrieval[END_REF].

Video indexing and retrieval was born later than image indexing and retrieval. With the video, we have other information that is the motion. In some cases, this information will help to fill up the semantic gap. The problem of semantic video indexing and retrieval is considered as video event recognition. Therefore, the semantic video indexing and retrieval has the results for some specific domains. However, we believe that with general video databases, the participation of the users in the form of relevance feedback is obligatory. Unfortunately, nowadays, we do not have yet any work dedicated for it because of its difficulty.

Therefore, in this article, firstly, we propose a 2D graphic interface adapted to the problem of image retrieval that enable a bidirectional communication: from the system towards the user to visualize the current research results and from the user towards the system so that the user can provide some relevance feedback information to refine his/her query. In this interface, the visualization shows the image query in the middle of the screen and the result images in a 2D plan with distances showing the similarity measures between images and the query. We propose also a method of relevance feedback in form of validation, in this interface, for image retrieval. This approach has been implemented and tested with different image databases. Secondly, we analyze the extension of this approach for video retrieval. For this, we extract the key frames from video and use them to represent the research results of video as well as to do the relevance feedback

The paper is organized as follows. In the next section, we review some related works in image and video indexing and retrieval. A proposed interface and a method of relevance feedback are presented in section 3. Some experiments and results are introduced in section 4. Finally, for concluding this paper, we give some conclusions and perspectives.

RELATED WORKS

In this paper, we are interested in the second approach in two above presented approaches. This approach has two challenges:

• The improvement the kernel of system (methods of relevance feedback) for corresponding better the user's need

• The visualization that allows the system to present the results to the user and to ask him/her the feedback information Concerning to the first challenge, a lot of works have been carried out. Those works are either to modify the query and the used similarity measure [START_REF] Rui | Relevance Feedback: A Power Tool for Interactive Content-Based Image Retrieval[END_REF] or to try to approximate the decision surface that separates the relevant images and the non relevant images in the feature's space [START_REF] Zhang | Region-Based Image Clustering and Retrieval Using Multiple Instance Learning[END_REF]. Concerning to the second approach, the traditional interface that shows the image query and a fixed number of image results in the form of a list, becomes unsuitable for interactive image indexing and retrieval system. In the last years, the visualization has drawn the attention of many researchers in the field of image indexing and retrieval domain and some methods of visualization were proposed. In [START_REF] Rubner | A Metric for Distributions with Applications to Image Databases[END_REF], the EMD (Earth Mover's Distance) and MDS (Multidimensional Scaling) are used to present the image results in a plan 2D according to only one similarity measure. This work lacks of the relevance feedback. In 2004, Deng [START_REF] Deng | Visualization and Comparison of Image Collections based on Self-organized Maps[END_REF] has been proposed a method of visualization and comparison the images based on the SOM. At the beginning, this method does not support the relevance feedback. At present, some current works [START_REF] Laaksonen | Emergence of semantic concepts in visual databases[END_REF] try to add the relevance feedback in it.

In the video indexing and retrieval, many works dedicated for video indexing and retrieval from the approaches based on the motion and trajectory [START_REF] Dagtas | Models for motion based video indexing and retrieval[END_REF] to the approaches, that are more semantic, based on event recognition [START_REF] Calic | Towards Intelligent Content Based Retrieval of Wildlife Videos[END_REF]. Because, with the video beside the visual features, we have also audio features and text features. Therefore, some authors consider also the multi modality mode [Babaguchi02] [START_REF] Huang | Integration of multimodal features for video scene classification based on HMM[END_REF]. Some researchers are interested in adding the relevance feedback in video indexing and retrieval. At present, some works [START_REF] Yan | Negative Pseudo Relevance Feedback in Content based Video Retrieval[END_REF] [Aksoy05] are presented for video indexing and retrieval with the relevance feedback, but indeed, they work with the still images.

Our work is aim to solve two challenges in image indexing and retrieval in the same time by a proposed interface and a corresponding method of relevance feedback. We extend our interface to video indexing and retrieval based on their key frames.

PROPOSED INTERFACE AND RELEVANCE FEEDBACK

Figure 1 shows the architecture of our approach for the image and videos indexing and retrieval. The distance computing, results displaying and feedback processes will be described in section 3.1 and section 3.2. In this architecture, for working with video, at first, we select some key frames from the video and then use the same process of image indexing and retrieval. In the section 3.3, we will present some works for key frame selection.

Figure 1. Architecture of proposed approach

Proposed interface

Our idea is to conceive an interface that allows to gather around the image query the images that are similar to. The user, then, select a region on the screen to refine his/her query. The figure 3 shows our proposed interface. This interface consists 5 zones: one of function, one of initial examples, one of positive examples, one of negative examples and another of results. The zone of result is the most important zone. In this zone, the image query is middle, the image results are shown according to 2 axes. We can use some different extracted features and their similarity measures to compute the position of result images in this plan. Without lost of generality, in this article, we present our approach by using the histogram intersection of RGB color space for one axe and that of HSV color space for the other. The position (x, y) of image I in the image databases is computed as:

Intersection Intersection ( ) ( ( ), ( )) ( ) ( ( ), ( ))
= = = > = - = > = -
)

Where E is the entropy, H RGB , H HSV are the histogram in the RGB and HSV color spaces and d Intersection is the distance between two histograms [START_REF] Swain | Color indexing[END_REF]. With this interface, we use only the global features. The local features might be added to improve the results.

Relevance feedback in the proposed interface

The presented method of relevance feedback in this section consist to do the relevance feedback by the modifying the query. We keep the value of sign(x) and sign(y) for sign(x') and sign(y'). The next results are shown according to their new positions. The users can do this process many times until he/she is satisfied.

Its extension to video retrieval

Temporal video segmentation is the first step towards video retrieval. Its goal is to divide the video stream into a set of meaningful and manageable segments (shots) that are used as basic elements for indexing. A shot is defined as an unbroken sequence of frames taken from one camera. There are two basic types of shot transitions: abrupt and gradual. Abrupt transitions (cuts) are simpler, they occur in a single frame when stopping and restarting the camera. Although many kinds of cinematic effects could be applied to artificially combine two shots, and thus to create gradual transitions, most often fades and dissolves are used. More than eight years of temporal video segmentation research have resulted in a great variety of algorithms. Early work focuses on cut detection, while more recent techniques deal with the harder problem -gradual transitions detection. A full overview of temporal video segmentation will be found in [START_REF] Koprinska | Temporal Video Segmentation: A survey[END_REF]. After shots are segmented, the key frames that represent the salient content of the shot will be extracted. Depending on the content's complexity of the shot, one or more key frames can be extracted from a single shot. Because of its importance, much research effort has been given in key frame extraction. Progress has been made in this area, however, the existing approaches either are computationally expensive or can not effectively capture the major visual content. In [START_REF] Zhuang | Adaptive key frame extraction using unsupervised clustering[END_REF], the authors proposed a clustering based approach which is both efficient and effective. In [START_REF] Wolf | Key Frame Selection by Motion Analysis[END_REF], the authors proposed a new algorithm for identifying the key frames by using the motion information. Since effective temporal segmentation techniques and key frames extraction techniques exist in the literature, we will use these techniques in our system.

EXPERIMENTAL RESULTS

Image/video databases

In order to evaluate our system, we used a subset of Corel's image databases (http://wang.ist.psu.edu/docs/related/). This image databases consist of 1000 images divided into 10 classes. The image size is either 384 × 256 or 256× 384. Figure 2 gives some images in this image database. We have also tested our system with a video database. We have chosen CAVIAR video database [START_REF] Fisher | The PETS04 Surveillance Ground-Truth Data Sets[END_REF]. This video database consists of two sets. The first set contained 28 videos were filmed for the CAVIAR project with a wide angle camera lens in the entrance lobby of the INRIA Labs at Grenoble, France. The resolution is half-resolution PAL standard (384×288 pixels, 25 frames per second) and compressed using MPEG2. The second set of data contained 52 videos also used a wide angle lens along and across the hallway in a shopping center in Lisbon. For each sequence, there are two time synchronized videos, one with the view across and the other along the hallway. The resolution is half-resolution PAL standard (384×288 pixels, 25 frames per second) and compressed using MPEG2. This video database is used in video surveillance.

Some results with proposed interface

Some results with image database

Figure 3 and figure 4 give a result of our proposed system with the corresponding method of relevance feedback. In this case, the users search the images containing one (some) horse(s). The figure 3 shows the results without the relevance feedback, while figure 4 shows the new results in this case, the users choose 4 positive examples. The new results show an improvement after one time of relevance feedback. Most images around the image query contain one or some horses. Figure 5 and figure 6 give the room of centered region in two cases.

Some results with video databases

For using proposed interface to present and retrieve the videos, some key frames must be extracted from these videos. For simplifying this task, with each video, we extract only one key frame. We propose here a method of extracting the key frames that is suited for this video database, based on the histogram intersection [START_REF] Swain | Color indexing[END_REF]. We compare all of frame in the video with the first frame and choose the frame that has the largest distance with the first frame, as the key frame. In this paper, we compute histogram 24 bin of RGB color space (8 bins for each component). The figure 7 shows the key frame of scenario Meet Crowd. The figure 8 gives one result of the extension of our proposed interface for video indexing and retrieval based on the key frames.

Some comparisons

In order to compare our approach (proposed interface + relevance feedback) with others approaches (traditional interface + relevance feedback), we have also developed the proposed algorithm [START_REF] Rui | Relevance Feedback: A Power Tool for Interactive Content-Based Image Retrieval[END_REF] in the traditional interface. The figure 9 shows the first sixteen images results without relevance feedback. In this figure, the images in rectangle red are irrelevant, the others are relevant. The figure 10 shows the first sixteen images results after one time of relevance feedback. From the observations of obtained results, we give here some comparisons:

• The traditional interface presents the results in the mono dimensional way while our proposed interface presents these images in the bi-dimensional way. Therefore, it allows to show more information than the traditional interface. Our proposed interface gives implicitly the similarity between some groups of images ( the traditional interface gives only the similarity between image query and the results images);

• Our interface allows to group the images that are similar (ex: in the figure 4 the group of flowers is on the right and below);

• The traditional interface limits the number of show image results, it is difficult for the users to give enough negative and positive examples. Our interface can solve this problem.

CONCLUSIONS

In this paper, a graphic 2D interface and a corresponding method of relevance feedback were presented. The presented experimental results of this interface and method of relevance feedback have been proved the efficiency. An extension to video indexing and retrieval is also introduced. However, there are some problems to solve for this interface such as: display the images in this interface when the image databases are large, relevance feedback with negative examples. In this paper, we have implemented an 2D interface and have tested only with histogram in RGB and HSV color spaces, this doesn't mean that we use only two features. With the images, we have more than 2 features, therefore, we are looking to two directions: one is to manipulate with an space more than 2 dimensions, another is to use the principal component analysis to reduce the number of dimensions. With the video indexing and retrieval, we consider also an interface that enables to present not only the key frames of the videos but also other information such as the motion and trajectory.

Figure 2 .

 2 Figure 2. Some images in subset of COREL's image database

Figure 3 .

 3 Figure 3. Results without relevance feedback, image query is center of the screen, image results are shown along to two axes: the vertical axe using the intersection histogram in RGB color space, the horizontal axe using the intersection histogram in HSV color space.

Figure 4 .

 4 Figure 4. Results after one time of relevance feedback, four positive examples have been chosen

Figure 7 .

 7 Figure 7. An extracted key frame for video of scenario Meet Crowd

Figure 9 .

 9 Figure 9. The first sixteen images results without relevance feedback, the images in rectangle red are irrelevant, the others are relevant

Proceedings of ICT.rda'06. Hanoi May.[20][21] 2006

E-mail: Alain.Boucher@auf.org


Weak and Strong Solutions of Dual Problems

J.J.MOREAU §1. Introduction.

Many problems arising from various domains of physics consist in the investigation of functions defined, for instance, on a subset S of lR P , fulfilling certain requirements at each interior point of S and other requirements at each boundary point. Such conditions, expressing physical laws of local character, generally in volve continuity of the functions and their partial derivatives up to a cer tain order. At this stage of the problem, physicists frequently characterize the solution, if it exists, by variational proper tie s or even extremal propertie s: it is that element of a cer tain class of functions where a certain functional attains its minimum.

These variational characterizations of solutions have suggested to mathematicians the idea of shifting from the so called strong formulation of problems -i.e. the na ive formulation provided by physics -to milder systems of require ments, yielding solutions denoted as weak and whose exist ence is more easily established. For instance, the function space to which the expected solution of the physical problem belongs is endowed with a topology (and a structure of uni form space); a minimizing sequence of the functional in question does not necessarily converge relatively to this topology, but in some typical cases one proves that conver gence is achieved by imbedding the function space in its completion: the element of this completion to which the sequence converges is called a weak s.olution of the problem, and it is proved that it coincides with the so-called strong solution -i. e. the solution agreeing with the strong formulation-whenever the latter exists.

Another common feature in this connection is the duality between variational properties of solutions. In the classical case where the conventional machinery of the cal culus of variations can be applied (this means that the con sidered functionals are, in some sense, differentiable on the function spaces where they are defined) this duality is well known : see Courant, Hilbert [l]. Dirichlet' s problem gives the primary example of such a situation: Let n be a bounded open subset of ffi. n ; one looks for a numerical function u , continuous on the closure Q , harmonie on n and coinciding with a prescribed continuous function on the boundary an. Let us suppose here that the boundary data can be extended as a function f , continuous on Q , possessing a squareintegrable gradient on n . A first extremal characterization of the solution u (if it exists) is that, in the set of the func tions v , continuous on Q , agreeing with f on an , possessing a square -integrable gradient on n , this solution is the (unique) element that realizes the minimum of the func tional V -J I grad V 1 2 dT n (dT: volume or Lebesgue measure on n). As a dual char acterization of u , or rather of the vector field grad u , we have the following: in the set of the square -integrable vec tor fields on n which are the gradients of harmonie fonctions, grad u is the (unique) element for which the functional wf lw-grad f 1 2 dT n achieves its minimum (for more sophisticated versions of so called Dirichlet's principle see e.g.: Brelot [l], [2]; Deny, Lions [l]). The underlying geometric pattern is that of pro jecting a known point of a certain pre -Hilbert s pace onto two orthogonal affine manifolds. These two projections are known to be complementary to each other by their common equivalence to a third operation of a different sort, the decomposi tion of a given element of the pre -Hilbert space into the sum of two elements belonging respectively to a certain pair of orthogonal vector subspaces.

ln what follows we present a rather general model involving such triplets of equivalent ways of characterizing elements in a function space which is a priori not complete: two minimization properties, said to be dual to each other, and a decomposition property. This is done for nonlinear problems, without differentiability being considered for the functionals in question, but under certain convexity hypothe ses. It is stressed that when imbedding the functional space initially considered into its completion, each of the three properties induces, in a natural way, a concept of weak solution, but these extensions do not in general agree with each other; in other words, the weakening procedure may not preserve duality, The core of this report consists in formu lating a series of necessary and sufficient conditions for the consistency of the weakening procedures.

For sake of clarity we restrict ourselves to the case where the function space under consideration is endowed with a pre -Hilbert structure, as in the above example of Dirichlet' s problem, Such a space making with itself a dual pair, the elements involved in dual minimization properties all belong to the same space, allowing a simple form for the as sociated decomposition pattern. Such a pre -Hilbert structure is usual in physics: the quadratic form whose polar form provides the scalar product will represent a kinetic energy, an electromagnetic energy, the potential energy of a linear elasticity law, the dissipation function of a linear viscosity law, etc ... First, in Section 2, we recall the necessary basic elements of the duality theory of convex fonctions defined on vector spaces. This theory, which originated in an idea of W. Fenchel [l], [2] has been extensively developed in recent years as a systematic tool for bringing out duality in convex extremal problems, without differentiability assumptions.

For detailed accounts and bibliography the reader might refer to R. T. Rockafellar' s book [ 3 ], devoted to finite -dimen sional spaces but containing many guiding ideas for the general case, or, for a systematic study of convex fonctions defined on topological vector spaces, to J. J. Moreau [START_REF]Fonctionnelles convexes, Séminaire sur les équations aux dérivées partielles[END_REF]. More recent developments appear in J. L. Joly [l ] , M. Valadier [l], [2 ]. For applications to optimization problems in general or to the theory of approximation see e. g. Rockafellar [2], Laurent-Joly [l], Moreau [START_REF]Distance a un convexe d'un espace normé et caractérisation des points proximaux[END_REF]. Following Rockafellar [l] and Ioffe-Tihomirov [l], the theory has been applied to fonc tionals defined by integrals, thus to the calcul us of variations and optimal control: see Rockafellar' s contribution to this volume. In the same connection these methods have recently proved usefol in the study of certain partial differential equatians: see Temam [l], [2], [3], [4]. Subdifferential mappings, as defined in paragraph 2. d, provided the primitive example of monotone mappings (G. J. Minty [l]).

The author's interest in this theory was motivated by the mechanics of continua (see: Moreau [4], [START_REF]Principes extrémaux pour le probléme de la naissance de la cavitation[END_REF], [lü], [START_REF]Sur les lois de frottement, de plasticité et de viscosité[END_REF] and Nayroles [l]).

From Section 3 onward, we restrict ourselves to pre Hilbert or Hilbert spaces, Proximation mappings defined in this context generalize projections on convex sets; thus the present paper is connected to E. H. Zarantonello' s article in this volume. §2. Elements of the Duality of Convex Functions.

a. Polar fonctions.

Let X and Y be a dual pair of a real vector spaces; we de note by (.,. ) the bilinear form which "puts the se two spaces in duality". For instance X may be a given topo logical vector space and Y its topological dual, but in what follows X and Y will play perfectly symmetric roles. Each of the two spaces may be endowed with various topologies (actually equivalent when the dimension is finite) said to be compatible with the duality: on the space X , for instance, the se are the locally convex topologies relative to which the continuous linear forms consist exactly of the functions expressed as x -(x, y) with y E Y (and each continuous linear form on X corresponds to only one y E Y if the usual separation condition is fulfilled). Among the se topologies, the Mackey topology T(X, Y) is the finest, the weak topology cr(X, Y) is the coarsest.

An affine function on X ( one should understand: continuous for topologies compatible with the duality) is written as

(2. l) X_,. (x, Y ) -P
with y E Y (called the slope of the fonction) and p E lR..

Let f E iR X (i.e. a function defined on X with values in ÏR= [-co, +co]). The affine function (2.1) is, all over X , a minorant of f if and only if

,,, (2. 2
) p � sup { (x, y) -f(x) :x E X} = f'''(y)
The function f': ' defined thereby on Y is called the polar function of f ( or conjugate; in Rockafellar' s book [ 3] the word "polar function" is used in another sense ).

Example: Take as f the indicator function y; ,.., of a subset S of X , i. e.

.::,

G� if X E S lj;s (x) = if X � S
The polar function tj;;(y) = sup {(x,y) -y; 8 (x): x EX} = S up { (X, y) : X E S} is conventionally called the support function of the set S , with respect to the duality (X, Y). Using the asterisk indifferently to denote the polarity from m_ X to m_ Y or from m_ Y to m_ X , the polar (: ": ' of f': ' is t': '(x) = sup { (x, y) -l'(y) : y E Y} .

From Condition (2. 2) it is easily found that f': ": ' equals the pointwise supremum of the affine functions such as (2. 1) which minorize f . Denote by r(X, Y) the set of the numerical functions defined on X which are pointwise suprema of families of such affine functions. By standard separation arguments (i.e. the Hahn-Banach theorem), it may be proved that r(X, Y) consists of:

1. The constant fonction +oo .

2. The constant function _oo (it is the supremum of an empty family of affine functions:) 3. The set of all functions called closed proper con vex on X , namely the functions with values in ]oo, +oo] , not everywhere +oo, which are convex and lower semi-continuous for one (thus for all) of the (locally convex) topologies compatible with the duality (X, Y). This latter set will be denoted by r 0 (X, Y).

Similar notations when exchanging X and Y .

Ex.ample. The indicator l\J s of S c X belongs to r(X, Y) if and only if the set S is convex and closed for one (thus for all) of the above topologies; l\J s belongs to r 0 (X, Y) if in addition .: 3 is not empty.

,, Clearly f': ' e r(Y, X) for any f E m_ X ; forthermore C E r 0 (Y, X) if and only if f is not everywhere +oo and possesses at least one affine minorant such as (2. 1). The fonction f": ' is the greatest element of r(X, Y) minorizing f ; thus it is called the r -hull of f .

In particular f = f': ": ' if and only if f E r(X, Y); this shows that polarity defines a one -to-one correspondence between r(X, Y) and r(Y, X). As the constants +oo and _oo are polar to each other, the correspondance is also oneto-one between r 0 (X, Y) and r 0 (Y,X).

In other words if it is supposed that f E r(X, Y) and g E r(Y, X)' the relation f = g': ' is equivalent to e: , = g ; in such a case f and g will be said to be mutually polar.

Example.

Let A and B respectively be nonempty sub set of X and Y ; it is easily found that the indicators ljJ A and 4J B are mutually polar fonctions if and only if A and B are mutually polar canes, i.e. A= {x E X : (x, y)_::::. O for any y E B} and symmetrically (such canes are convex, with vertex at the origin, and closed for the topologies compatible with the duality).

2. c. Lower semi-continuous hull and r-hull.

Suppose now that the fonction f is convex on X , with values in ]-oo,+oo], not everywhere +oo; let _i be its lower semi-continuous hull with regard to some (locally convex) topology compatible with the duality (X, Y), i. e. the greatest 1. s. c. numerical fonction minorizing f . It is known that this 1. s. c. hull may be constructed pointwise by

(2. 3) f(x) = lim. inf f(u) . - U ._ X
It is elementary that the convexity of f implies the convexity of !__; thus, as soon as it is checked that !__ takes nowhere the value -oo (a common method for this is to check that f possesses at least one continuous affine minorant) one con cludes that _i E r 0 (X, Y) and, consequently, _i = f": ' .

Observe at this stage that, due to the convexity of f the choice of the topology when writing (2. 3) is immaterial, as long as this (locally convex) topology is compatible with the duality (X, Y) .

The following consequence of (Z. 3) will play an essential part in Section 4: Suppose that the restriction of f to its effective domain dom f = {x E X : f(x) < + oo} is lower semicontinuous (for the topology induced on this domain); then _!_ has the same restriction to this domain as f .

d. Subgradients and subdifferentials.

Let f E :iR. X ; y E Y is called a subgradient of t at the point x if y is the slope of an affine minorant of f exact at the point x (i.e. taking at this point the same value as f ). This requires that the value f(x) is finite and that the supposed minorant has the form u --. ( u-x ,y)+ f(x).

Using Condition (2. 2) for an affine fonction to minorize f , one obtains the following representation for the set, denoted by af(x), of the subgradients of f at the point x af

(x) = { y E Y : l'(y) -(x, y) _:s. -f(x) }•
This set is called the subdifferential of f at the point x .

Clearly the convexity and the lower semicontinuity of f': ' imply that ôf(x) is a convex (possibly empty) subset of Y , closed for the topologies compatible with the duality (Y, X). If ôf(x) is not empty the fonction f is said to be subdiffer entiable at the point x .

Suppose for instance that the fonction f is convex and weakly differentiable at the point x, with respect to the duality (X , Y) ( such is a fortiori the case when X is a normed space, Y its topological dual with f Fréchet differentiable at the point x ) with the element y E Y as differential or "gradient"; then it is easily found that 0 f(x) consists of the single element y (About relations between differentials and subdifferentials, see Asplund-Rockafellar [l ]).

An evident use of the concept of subdifferential is the characterization of a minimum: the fonction f attains its infimum at the point x if and only if the set af(x) con tains the origin of Y . There thus arises a need for a "sub differential calculus "; in addition to Rockafellar' s book [ 3] (for general bibliography and finite dimensional cases) the reader might refer to Mo�eau [START_REF]Sous -différentiabilité[END_REF], [START_REF]Fonctionnelles convexes, Séminaire sur les équations aux dérivées partielles[END_REF], Valadier [l], [2]. The simplest rules of this calculus concern addition : if f 1 and f 2 are numerical functions on X , one trivially has, for any XE X

(2. 4)

af 1 (x) + af 2 (x) c 8(f 1 + f 2 )(x)
and it is important to formulate sufficient conditions for this inclusion to be an equality of sets. We shall only make use in this paper of this simple one ( see Moreau [START_REF]Un cas d'addition des sous-différentiels[END_REF]): If f 1 and f 2 are convex, one of them weakly differentiable at the point x , then the inclusion (2. 4) is an equality of sets.

e. Conjugate points.

The preceding facts find their clearest setting when one starts with a pair of mutually polar functions f e r 0 (X, Y), g e r 0 (Y, X). Then, for x e X and y e Y , the three follow ing properties are equivalent:

(2. 5) (2. 6) (2. 7) y E af(x) X E é)g(y) f (X) + g (y) -(X, y ) = Ü •
(Note that, by the definition of polarity, the left member of this latter equality is essentially nonnegative, whichever are x e X and y e Y). In such a case the points x and y are said to be conjugate relative to the pair of mutually polar functions (f, g).

For instance, if A C X and B C Y are mutually polar cones, Condition (2. 7) for x and y to be conjugate relative to the pair of mutually polar functions f = l(i A and g = l(J B becomes:

x e A , y e B , ( x ,y ) = 0

In the very special case where A and B are two vector subspaces of X and Y , each being the orthogonal of the other with respect to the duality, this latter condition reduces to: x e A and y e B .

As a usefol example of the equivalence between (2. 5) and (2. 6) let us note the following: The (possibly empty) set of the points where the fonction f attains its infimum equals ôg( 0), the subdifferential of the fonction g at the origin of Y.

f. Infimal convolution.

Let f 1 and f 2 be � wo elements of iR X ; we denote by f 1 V f 2 the element of lR X defined as the fonction (o r equivalently

The possible values of u such that the above sum takes the indeterminate form oo -oo must be omitted when constructing the "inf". The operation V, called infimal convolution , is a commutative and associative composition law in JRX . If f 1 and f 2 are convex, so is fi V f 2 (at least in an extended sen se, since it may take the value -oo at some points: for the technique of overcoming such difficulties see Moreau

[ 1 3]). Example 1. If f 2 is the indicator fonction of a singleton {a} , then f 1 V f 2 is a translate of f 1 , namely the fonction x-f 1 (x-a) Example 2.
If A is a subset of X and I l• I l a norm on this vector space, then ( lj; A V I l• I l )(x) is the distance of the point x to the set A .

Taking now polar fonctions, easy computation yields (2. 9)

This fc-mula provides an answer to the following question: observing that addition is a composition law in r(Y, X) (at least when extended by the convention °<uio = _oo ) and that polarity maps r(Y,X) one-ta-one onto r(X, Y), what direct interpretation can be given of the composition law obtained in r(X, Y) as the image of addition ? Suppose that f 1 and f 2 belong to r(X, Y) and that g 1 and g 2 , in r(Y, X), are their polar functions. E '-J. uation (2. 9 ), now written as

(f 1 v f 2t = 91 + 92 implies (g l + 92/ = (f l v f 2 /": ,
Thus the desired operation is the r-hull of infimal convolu tion. This gives a great practical importance to cases where f 1 V f 2 happens to belong to r(X, Y) sa that the double asterisk may be omitted. As already mentioned, the convex ity of f 1 and f 2 guarantees that of f 1 'vf 2 ; in view of para graph 2. c. it just remains to check whether f 1 'il f 2 is lower semi-continuous (with nowhere the value -oo). This lies beyond the scope of the present paper (see Moreau [l], [START_REF]Fonctionnelles convexes, Séminaire sur les équations aux dérivées partielles[END_REF]).

3. Dual Extremum Problems in a Pre -Hilbert Space.

a. Definitions

Let H be a pre -Hilbert opace over the real numbers, i.e. a real linear space on which a certain positive definite quadratric form has been defined once and for all; the square root of this quadratic form provide s the norm I l• I l on H ; its polar form gives the scalar product of any two elements x and y of H , denoted by (x !y). This bilinear form puts H in duality with itself; as a topology compatible with this duality, the weak topology <T(H, H) will be considered; but it must be stressed that the norm topology is not compatible with the duality (H H) if H is not norm-complete, i.e. if it is not a Hilbert space.

Denote by Q the quadratic form

Q(x) = i ll x 11 2
Easy computation yields that Q is Fréchet-differentiable, and also weakly differentiable relative to the duality (H, H), with

grad Q(x) = x .
The function Q is convex; it belongs to r 0 (H, H) and equals its polar function.

Given z e H , we shall denote by Q

2 the function x-+ Q(z-x), so that grad Q (x) = x-z . z
Let f be a convex numerical function defined on H with values in ]-oo, +oo ]; let z be an element of H . The strict convexity of Q implies that the function f + Q 2 at tains its infimum at at most one point (incidentally, this infimum is (f v'Q)(z)); if such a point exists, it will be de noted by prox (f;z). The mapping z-+ prox (f;z) is called a proximation (Moreau [3]).

Example.

Take as f the indicator function l\J c of a nonempty convex subset C of H ; the point prox (l\Jc;z), if it exists, is the nearest point to z in C , frequently called the projection of z onto C and denoted by proj(C;z).

b. Duality properties

Proposition.

Let (f, g) be a pair of mutually polar functions on H and let z be an element of H .

If there exists prox(f;z), denoted by x , then there exists prox(g;z), denoted by y; the points x and y are conjugate with respect to (f, g) and x+y = z

Conversely if there exists a pair of points x and y which are conjugate with respect to (f, g) and such that x+y = z, then prox(f;z) and prox(g;z) exist and equal x and y , respectively.

Proof:

The relation x = prox(f;z) means that the ongm belongs to the subdifferential of the function f + 0 2 at the point x . By the differentiability of the function 0 2 and by the fact mentioned at the end of paragraph 2. d, this is equiv alent to Ü E X-Z + âf(X) or, when putting y = z-x , equivalent to y E af(x), i.e. : the points x and y are conjugate with respect to (f, g). From this equivalence, the proof is completed by exchanging f with g and x with y . D Corollary 1.

Let A and B be a pair of mutually polar canes in H and let z E H .

If there exists proj{A;z), denoted by x , then there exists proj{B;z), denoted by y ; one has (x IY) = 0 and x+y = z .

Conversely, if there exists a pair of points x E A , y E B , such that (x J y) = 0 and x+y = z , then proj(A;z) and proj(B;z) exist, respectively equal to x and y .

Proof:

Take f = t\; A and f = t\; B in ab ove Proposition. D

Particularizing more, we obtain:

Corollary 2.
Let F and G be a pair of vector subspaces of H , each being the orthogonal of the other, and let z E H.

If there exists proj{F;z), denoted by x , then there exists proj{G;z), denoted by y , and x+y = z .

Conversely if there exists a pair of points x E F and y E G such that x+y = z , then proj(F;z) and proj{G;z) exist and equal x and y , respectively.

Proof:

F and G are mutually polar cones, lik.e A and B in the above Corollary; here (x!y) = 0 is automatically ensured by x E F and y E G . D 3. c. A functional example.

The following is a special case of a situation de scribed, in a context of hydrodynamics, in Moreau [ 4], [START_REF]Principes extrémaux pour le probléme de la naissance de la cavitation[END_REF]; such "unilateral" functional problems have been extensively studied in the recent years by various authors (see e. g. Brezis -Stampacchia [l], Lewy-Stampacchia [l), [2)).

Let ri be a bounded open subset of lR. n ; take as H the space of the vector functions defined and continuous on the closure f2 and which are the gradients of numerical functions. The scalar product of two elements u and v of H is defined by

(U Jv) = J ri U(ç) • V(ç) dT(ç)
(s: generic point of ri; dT: Lebesgue measure; the dot represents the scalar product of the two elements u(s) and v(s) of lR. n ) For the sake of simplicity we make in this paper the assumption that ri is "very smooth" , in order that: i) there exists on ari a continuous field of outward normal unit vectors, denoted by s ... v(s ).

ii) The solutions of the conventional Dirichlet and Neumann problems exist, with gradient in H for any "very smooth" data on ari (say twice differ entiable data, while ari is a twice differentiable hypersurface).

We are given:

1. An element z = grad r of H (then the numeri cal function r is finite and continuous on r.?). 2. A nonnegative "very smooth" function b on ari. Call D the ( convex) set of the elements v = grad q E H . such that div v (i.e. the laplacian .6,,q), understood in the sense of distributions on the open set Q , is nonnegative, i.e. is a nonnegative measure on Q; note that this me a sure is bounded, by virtue of the continuity of v on fi.

Call f the indicator function of C and define another (convex, non finite) numerical function g on H as taking, for any v = grad q E H , the following values (der denotes the area me a sure on é)Q):

g(v) = J b v • grad q der , é)Q g(v) = +oo if VE D if v f D .
Decomposition problem.

As it naturally arises from hydrodynamics this problem is formulated: to find in H the elements x = grad p and y = grad q such that The latter condition means that the product of the non negative measure ticr and the continuous function p is the zero measure on Q ; in view of ( 3. 2) it may equivalently be written Using an integration by parts, the joint conditions (3. 2) and ( 3. 3) are then found eguivalent to (3. 4) f(x) + g(y) -(x IY) = 0 Thus the present situation will reduce to the pattern described in paragraph 3. b if we prove that f and g are mutually polar ( or in other words that the convex set C is closed for the topology c,(H, H) and that g is its support fonction). Actually the same integration by parts as above shows that the left member of (3. 4) is non-negative for any x and y in H , i.e. each of the two fonctions f and g majorizes the polar of the other. Therefore we need only prove the two reverse inequalitie s:

1. Let us prove that f _s g\ i.e. for any u = grad p E H f(u) _s sup {( grad pl grad q) -J b v. grad q dcr :grad q E D }

8!:2 •-
From g being positively homogeneous it follows that g�-is an indicator. As f is the indicator of C and in view of the same integration by parts, this inequality reduces to the fol lowing statement: "if u is such that (3. 5) sup {-J p t.q -J (b-p) v, grad q dc,: grad q ED }= 0 n an then u E C" . In fact, if u folfills condition (3. 5), one may first choose q harmonie, and thus conclude that the integral J (b-p) v • grad q dcr a n is nonnegative, and finally zero since q may be changed into -q . Now v • grad q may be identified with any "very smooth" fonction having a zero integral over an (this con sists in solving a Neumann problem); thus b-p is constant on an or, adjusting the arbitrary constant in the determina tion of p , p = b on an. Therefore (3. 5) reduces to r pt.q>O Jn for any grad 4 E D ; now t.q may be chosen with an arbi trary support in n and this yields the nonnegativity of p all over n.

(3. 6) 2. Let us prove that g < f ,: , , under the definition: t': '(v) = sup {(grad p Jgrad q): grad p E C} where v = grad q e H. First if v does not belong to D there exists an indefinitely differentiable nonnegative fonction cp , with compact support in n , such that ( cp , �q ) = -{ grad cpj grad q) <O.

Then , by taking p = b + À cp (b denotes here an extension of b to f.i , with gradient in H) and giving to the positive number X. arbitrarily large values, one proves that the right member of (3. 6 ) is +oo, Suppose now v = grad q e D ; in view of the defini tion of g , we have to prove that, for any e > O , there exists grad p e C such that J b v• grad q d1T � (grad p Jgrad q) + e an or , using the integration by parts, In fact , as �q is a nonnegative bounded measure on n , there exists K , a compact subset of n , such that the integral of �q over n \ K is less than e / B, where B > O de notes a constant ma j orizing b . As the fonction p may be chosen ma j orized by B and null over K , this completes the proof.

d. lnfimal convolution with Q .

We take again 9 n arbitrary pre -Hilbert space and a pair (f, g) of mutually polar fonctions belonging to r 0 (H , H). As Q = Q,: , and f': ' = g , equation (2. 9 ) yields (3. 7) ::::::

(f v' Q ) = g + Q .
Since g+Q is not everywhere +oo , this proves that f "v Q possesses affine minorants; thus this fonction takes nowhere the value -oo ; clearly also , by definition (2. 8 ) , it nowhere takes the value +oo; the same conclusions apply to g V Q . Now {3.7) implies ,: ::, : :: ,: ::

(f V Q) = (g + Q)
where the right member may be computed as follows, for any z E H:

(g+Q{(z) = sup { (z IY ) -g(y) -Q{y) :

y E H} = sup {Q(z) -g(y) -Q(z-y): y e H} = Q(z) -(g V Q){z) .
As (f V Q)' : "� minorizes f V Q ( see Paragraph 2. b), this yields in particular the following inequality

( 3. 8) (f V Q) + (g V Q) � Q
The case of equality will be studied in Paragraph 5. a. given z e H , to find x = prox(f;z) or to find y = prox(g;z) appear as equivalent problems under the relation y = z-x . Furthermore, this pair of equivalent minimization problems has been found equivalent to a third problem of a different sort: that of decomposing z into the sum of two elements x and y which are conjugate relative to (f, g). In what follows we shall refer to any of these three prcblems as a strong problem: such a problem does not necessarily possess a solution.

In the physical context, it is usually the decomposi tion problem which directly arises from phenomenological laws: the two minimization "principles" are subsequently derived. So, when going to the task of defining weak solu tions of the physical problem variationally, no reason appears for preferring one of them to the other. Now the two choices do not in general provide the same concept of weak solution.

Remark 1.

In order to obtain a simpler pattern of implications, we restrict ourselves in this paper to problems associ ated with a pair of mutually polar functions; actually several results may be obtained under the less stringent hypothesis that f and g are only "superpolar", i.e. : for any x and y in H the inequality f(x) + g(y) -(x IY) � 0 holds (this means that each of the two functions majorizes the polar of the other).

Remark 2.

Results generalizing certain basic facts of the pre sent the ory may be formulated when cons ide ring, instead of pre -Hilbert or Hilbert s pace s, s orne normed or Banach vector spaces ( see Lescarret [l]).

b. The imbedding of H in its completion.

Let us denote by H the Hilbert completion of the pre -Hilbert space H; we shall treat H � s imbedded in H, hence dense in it for the norm topology. H may as well be considered as the topological dual of H when this latter space is endowed with the norm topology. The scalar product in H is an extension of the scalar product ( • I •) in H so that there is no need of a different notation for it. This bi linear, Jorm puts H in duality with itself; it puts in the same way H in duality with itself; it also puts in duality the two spaces H and H. To these three dualities correspond dis tinct classes of compatible topologies.

On H, for instance one may consider: (i) the norm topology, which is compatible with the duality (H, H) (this is actually the Mackey topology T(H, H)) ,

(ii) the topology a-(H, H), coarser than the pre ceding one but compatible with the same duality, so that the family of the closed convex sets or the family of the 1. s. c. convex numerical functions are the same for both, (iii) the topology a-(A, H), coarser than a-(H, H).

On the subspace H of H , these three topologies respectively induce:

( Let us start, as in Section 3, with a pair of numerical functions f and g , belonging to r 0 (H, H), mutually polar for the duality (H, H).

A

We shall denote by f' and g' their extensions to H with the value +oo outside of H; these extensions are convex on H.

The function g defined for every y e H by g(y) = sup{(x Jy) -f(x) : x e H} A = sup {(x Jy) -f' (x) : x e H} A is indifferently the polar of f for the duality (H, H) or the polar of f' for the duality (H, H); clearly it is an exten sion of g . Similarly f is the polar of g' for the duality (H, H); thus g is the bipolar of g' for the same duality, i.e. , in view of paragrapl}__ 2. c, the 1. s. c. hull of g' with r E;_ spect to a topology on H cs_mpatible with the duality (H, H), e. g. the topology a-(H, H) (in fact g' possesses at least one continuous affine minorant since its polar function f is not everywhere +oo ).

The polar of g for the duality (H, H) , i.e. the bi polar of f' for this duality will be denoted by f; it is the 1. s. c. hull of f' relatively to any topology compatible with this duality, in particular the norm topology. As f' agrees with f over the set (contained in H) of the points where it differs from +oo , and as f is 1. s. c. on ,.. . H for cr(H, H) which is coarser than the norm topology, f is an extension of f (see the end of paragraph 2. c. ).

Symmetrically we define on H the function g , na;::nely the norm -1. s. c. hull of g', and :f , namely the cr(H, H)-1. s. c. hull of f' , with similar polarity relations. The following inequalities hold:

-" f < f < f' -"
g.::: g_::: g' "

d. Proximations in H.

The properties of proximations presented in Section 3 for an a;:_bitrary pre -Hilbert space are true in the Hilbert space H with this additional simplification: for arbitrary <p e r 0 (H, H) and arbitrary z e H, the point prox (<p ; z) exists (uniquely). This is easily proved from the weak compactness of closed balls in a Hilbert space ( see Moreau [ 3 ]) or by using general conditions for the "exactness" of infimal con volution (i.e. cor..ditions for the infimum in (2. 8) to be a minimum; see Moreau [l] [START_REF]Fonctionnelles convexes, Séminaire sur les équations aux dérivées partielles[END_REF]). "

Therefore the existence of the following elements of H is ensured (4. 1) x = prox (f; z) , y = prox(g ; z)

these being equivalently characterized by

(4. 2)
" -

X+ y= Z f(x) + g{y) -(x IY) = 0
Symmetrically, the existence is ensured of (4. 3) x = prox (f; z) y = prox (g; z)

equivalently characterized by

- X+ y= Z f(x) + g(y)-(xiy) = o
Proposition.

Suppose z E H if one of the four points

x, y, x, y happens to lie in H , so do the other three and then (4. 4) x = x = prox(f ; z) ( 4. 5) y = y = prox ( g ; z)

(these proximations referring to f and g are evidently to be understood relative to H ). Conversely, if z E H and if there exists x = prox(f; z) in H (or equivalently by paragraph 3. b, if there exists y= prox(g; z)), equalities (4. 4) and (4. 5) hold.

Proof:

This immediately follows from the above charg._ cterizations of "prox" , since f equals the restriction of f or Î to H and g equals the restriction of g or g to H. D At this stage, the replacement of f and g , mutually polar numerical functions on H , by their extensions f and g , mutually polar numerical functions on H, appears as a weakening procedure for the so-called strong problem of Paragraph 4. a: In fact,.._this replacement yields a similar problem formulated in H instead of H and which possesses a solution for any z ; this solution coincides with the solu tion of the strong problem whenever the latter exists.

The same is true for the replacement of f and g by their extensions f and g , which yields another weakening procedure for the initial problem. More generally, one may choose r E r o (Î-I , H) such that

1 < f " < f A A
The polar fonction g of f for the duality (H, H) satisfies and the same arguments as above show that, for a given z E H, the elements prox(f; z) and prox(g ; z) of H, respectively, coincide with prox(f; z) and prox(g; z) whenever one (then both) of the latter exist. Thus we are in the presence of an infinity of weaken ing procedure s for our initial "strong" problem.

4. e. Use of minimizing sequences.

Let <p E 1c/H, H); a sequence (u n ) of points of H is classically called a minimizing sequence of the fonction

<fJ + O z if lim [ <p (u )+ O (u )] = inf { <p (u) + O (u): u E H } n -+ oo n z n z
Standard arguments, essentially using the convexity of <p and the uniform convexity of O z , yield: Any minimizing sequence of <p + 0 2 converges to prox( <p ; z) relative to the norm topology of tl " Now we remark that, f being the norm-1. s. c.,__ hull of f' and O z being norm-continuous, the fonction f + O z is the norm-1. s. c. hull of f'+O z and one has

" " inf{f(u) + O (u): u E H} = inf {f(u) + O z (u): u E H} z
{the same would not be true in general if we used instead of f the fonction f, which is also an extension of f to H but inferior to f ). Therefore a sequence (u n ) of points of H which in this space is minimiz�ng for the fonction,__ f + O z is also a minimizing sequence in H for the fonction f + O z ; thus:

Proposition.

Any minimizing sequence of f + Q in H

A Z converges in the norm topology of H to the element prox(f; z), denoted above by �; symmetrically any mini�izing � equence ,__ of g + Q 2 in H is normwise convergent in H to y = prox ( g ; z) . This proposition just describes the conventional weakening procedure for the two "strong" minimization prob lems in H whose the supposed solutions have been denoted by prox(f; z) and prox(g; z) (for a given z E H). Unfortu-

" A "-
nately the sum of the elements x and y of H does not in general equal z ; in other words this weakening de stroys the pattern of duality between the two minimization problems and also it destroys their equivalence with a decomposition problem.

Our purpose now is to formulate a series of necessary and sufficient conditions concerning f and g , in order that the above minimizing sequence device preserves these basic features; at the same time these conditions will be necessary and sufficient for the various weakening procedures described in Paragraph 4. d to coincide. It must be stressed that properties (v) to (vii) only involve elements of the pre -Hilbert space H where the so called strong problem was formulated; the same is true for property (iv) if it is interpreted in terms of minimizing sequences.

Property (v) was published in S. Maury [l); it says that any z E H can be "approximately decomposed" into the sum of two elements which are "approximately conjugate" relatively to (f, g) (in other words, y é: is an "approximate subgradient" of f at the point x é: ; concerning this concept, see: Broendsted-Rockafellar [l)). It may equivalently be formulated as follows: for •any z E H , there exists in the product space H XH a sequence (x n , Y n ) which is mini mizing at the same time for the two functions (x, y) _,. l! x+y-z I l and (x, y)_,. f(x) + g(y) -(x Jy) (in fact bath func tions are nonnegative and their infima are zero since f and g are mutually polar).

Proof of the proposition:

The equivalence between (i), (ii) and (iii) follows immediately from the fact that polarity reverses the ordering of functions.

Property (ii) implies the equality of the elements y and y as they are defined by (4. 1) and (4. 3); so property (iv) follows, by equality (4. 2). Conversely, in view of (4. 2), assertion (iv) implies that, for any z E H , prox (g; z) = prox (g ; z) .

But proximation mappings are norm-continuous from H into itself (they are �on-expanding: see Moreau [3]) and H is norm-dense in H. Therefore this equality also holds for

A A
any z E H, implying that the functions g and g differ only �Y a constant (see Moreau [3]) ; this constant is zero since g and g agree with g on H (and g is not everywhere +oo ). These assertions also imply (v) : in fact consider in H a minimizing sequence (x n ) of the function f + O z and a minimizing se quence ( y n ) of the function g + Q z . By paragraph 4. e these sequences are respectively normwise convergent in H to � and y, whose sum equals z accord ing to assertion (iv); thereby J lx n + Y n -z Il � s 11}._ade arbi trarily small. Furthermore (x n I Y n i tends to (x I y) and, as the function O z is norm-continuous, f(x n ) tends to f(x) and g(y n ) tends to g(y) : then the � econ � part" of assertion (v) follows from the fact that f(x) + g(y) -(x I y) is zero.

That conversely (v) implies (iv) may be deduced from the following identity:

f(x) + 0 (x) + g(y) + O z (Y) = O(z) + O(x+y-z) + f(x) + g(y) z -(x J y)
In fact property (v) means that, for each z E H , there exists a sequence (x n , Y n ) E H X H which is minimizing for the right member of this identity, the infimum of which is O(z). Now

inf{f(x) + O (x): x E H} = (f v'O)(z) z inf{g(y) + Q 3 (y) : y E H} = (g 'v O)(z)
Comparing this with inequality (3. 8), one finds that the sequence (x n ) is minimizing for the function f + O z and that the sequence (y n l is minimizing for the function g + O 2 ; as the sequence (x n , Y n ) is minimizing for the function (x, y) -Q(x+y-z), the sum X n + Y n is normwise convergent to z and that implies (iv).

To finish the proof the same identity shows immediately that properties (v) and (vi) are equivalent. Furthermore paragraph 3. d yields

(f v'Q)'; n; , + (g v'Q) = Q so that ( 5. 1) is equivalent to (f y' Q) ... .. .. ,, .. r ... r• =fv'Q .
In view of paragraph 2. c this is just property (vii) . D

The meaning of properties (vi) and (vii) becomes clearer in some special cases: Special Case 1.

Suppose that f is the indicator function of a subset C of H (convex and o-(H,H)-closed); for this particular form of f , property (vii) means that the distance function

z -dist (C, z) is o-(H, H)-1. s. c.
In fact (f v' Q)(z) e,wals half the square of this distance.

Another equivalent assertion is: Any ball in H , the radius of which is strictly smaller than the distance of its center to C, can be separated from C by a o-(H, H)-closed hyperplane (i.e. a hyperplane possessing a normal vector in H) .

In fact the distance function is o-(H, H)-1. s. c . if and only if, for any p � 0 , the (convex) set {z E H : dist (C ; z) _:: p} is o-(H, H)-closed. This in turn is equivalent to the separation property for any point z 0 e H which does not belong to this set and, finally to the asserted separation property between C and a ball with center z 0 and radius p . Actually direct arguments would easily show that this separation property between C and the balls in H is necessary and sufficient for the norm-closure of C in H to coincide with the cr(H, H)-closure of C : this is just the form taken in the present case by property (i). Special Case 2.

Suppose that f and g are respectively the indicator functions of two mutually polar canes A and B. Then property (vi) reduces to the following "Pythagorean" relation

[dist(A; z)] 2 +[dist(B; z)J 2 = [[zl[
2 holding for any z E H .

b. Functional example.

Let us show that in the functional example presented in paragraph 3. c the preceding properties hold, in fact that assertion (v) is verified.

The given continuous function b on the (compact) set ari was supposed nonnegative; just to simplify the following suppose here b > 0 .

Suppose z arbitrarily given in H; thus z can be approximated as nearly as desired, in the sense of the norm, by an element grad r E H such that r is a "very smooth" numerical function on ari ( see the smoothness assumptions made in paragraph 3. c).

First construct Y o = grad q 0 E D with the following propertie s: q o .S r on ri q o = r-b on ari .

For this purpose call '{ the Green potential of some negative smooth measure with compact support in ri and call h the solution of the Dirichlet problem for the data r-b on ari .

In view of our smoothness assumptions, the functions '{ and h have their gradients in H ; the function '{ is negative on ri ; thus q 0 = h + À'{ fulfills ab ove requirements when the positive constant À. is chosen sufficiently large.

Our ide a consists in applying Poincaré' s sweeping out process to the fonction q 0 , but "conditionally" with regard to the inequality q _::: r .

Denote in general by q a fonction satisfying the same conditions as above for q 0 , with gradient belonging to D ; the Laplacian b.q is a bounded nonnegative measure in Q • Let B C Q be a closed ball ; the fonction q' defined as equal to q in f.l \B and equal in B to the "harmonie interpolate" of q (i.e. the Poisson integral which salves the Dirichlet problem in the ball B with q as data on 8B) is continuous on f.l , subharmonic on Q , greater than or equal to q . As q' agrees with q on a neighborhood of 8!:2 , the nonnegative bounded measures b.q and �q' have the same total mass on Q.

Gall "conditional harmonization of q for B under r" the replacement of q by q' if this latter fonction satisfies q' _::: r , the conservation of q if not.

Choose then a sequence of balls forming a base for the topology of Q ; a classical construction yields another sequence in which each of the se balls recurs infinitely. Starting with the fonction q 0 constructed above, iterate conditional harmonization, using successively the balls of the latter sequence. This generates a non-decreasing se quence of continuous subharmonic minorants of r , all agreeing with r-b on 8!:2 ; arguments in the style of the theory of potential ( see Moreau [START_REF]Majorantes sur-harmoniques minimales d'une fonction continue[END_REF]) prove that this sequence converges uniformly on each compact subset of Q to a fonction q possessing the following properties: q is a continuous sub harmonic minorant of r , agreeing with r -b on 8!:2 and harmonie on the ( open) subset of Q where it differ.3 from r (in other words the nonnegative measure (r-q)b.q is null). As we have supposed b > 0 on 8!:2 , the set K on which q = r is a compact (possibly empty) subset of Q. Therefore, given i:: > 0 , one can stop the process of successive harmon izations after a finite number of steps, obtaining a fonction q 1 which folfills the following requirement: The difference r -q 1 is uniformly less than e on a compact set K 1 , with K C K 1 C Q • This compact set can be constructed with smooth boundary; perform an ultimate "harmonization" by replacing q 1 on n \K 1 by its harmonie interpola te, without al te ration on K

1 . The function q 2 constructe � thereby is again a continuous subharmonic minorant of q ( since this latter is harmonie on n\K 1 ) thus of r ; it agrees with r-b on an . The nonnegative measure l!..qz has a total mass on n not greater than the total mass µ of L!..q 0 : in other words our initial measure L!..q 0 has been "swept out" to the boundary of n and to a region where r-q 2 � e . This yields the in equality J (r-q 2 ) L!.. q 2 � µ e . n But q 2 possesses a piecewise continuous gradient, square integrable on n ; by putting r-q 2 = Pz , this allows an integration by parts transforming this inequality into J p v • grad q der -J grad p • grad q 2 dT < µe an It remains only to approximate, in the sense of the 1 2 norm, the vector fields grad Pz and grad q 2 by elements grad p and grad q of H , respectively belonging to the subsets C and D (alternatively one could have, in the previous process, "smoothed the transitions" after each step of harmonization, so as to deal all the time with functions having their gradients in H ); grad r was defined as approxi mating z . In that way one constructs elements x = grad p and y = grad q of H , the sum of which is approximately z, and such that f(x) + g(y) -(x [ y) is approximately zero, with f and g defined as in paragraph 3. c. This is precisely property (v) of paragraph 5. a.

This example is obviously connected to the study of the regularity of solutions of certain variational inequalities, as developed in Lewy-Stampacchia [l], [2 ].

  2. b. Closed proper convex functions.

  Cal! C the (convex) set of the elements u = grad p E H such that p � O on ri and p = b on ari.

4 .

 4 Weakening Procedures and Duality. 4. a. Strong problems. Paragraph 3. b described a rather general situation in vol ving a pair of extremum propertie s, formulated in the same pre-Hilbert space H , and said dual to each other:

4

  . c. Sorne extensions of f and g to H .

5 .

 5 The Case of Uniqueness. 5. a. Necessary and sufficient conditions.Proposition.With the notations defined in the previous paragraphs, the following assertions are equivalent: Any pair (f , g) of mutually polar fonctions on H which respective !)' ,._ minorize f and g on H coincides with (f, g). (iv) Any z E H equals the sum of � = prox(f; z) and of y= prox(g; z) (let us recall here that x and y have been interpreted in Paragraph 4. e as the limits in H of minimizing sequences for the functions f + O z and g + O z in H ) . (v) For any z E H and any é: > 0 there exist x é: and y é: in H such that I l X + y -z Il < é: The function f V O (resp. g V 0) is l. s. c. in H relative to the topology o-(H, H) .


Lan Le Thi

Alain Boucher

Monique Thonnat

Trajectory-Based Video Indexing and Retrieval Enabling Relevance Feedback

Keywords: Video Indexing and Retrieval, Trajectory Matching, Relevance Feedback I

This paper is proposing an approach for retrieving videos based on object trajectories. First, a trajectory is translated into a sequence of symbols based on a symbolic representation, beyond the initial numeric representation, which does not suffer from scaling, translation or rotation. Then, in order to compare trajectories based on their symbolic representations, two similarity measures are proposed, inspired by works in bioinformatic. Moreover, based on these similarity measures, two relevance feedback strategies are given. Experimental results for two databases show that the proposed similarity measures gave results as good as other existing measures. Real advantages of these measures are the possibility for the partial matching and for relevance feedback.

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, shape 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 strategy is also of importance.

Many works exist on trajectory representation, which can be classified into 3 levels of representation: numeric, symbolic and semantic. At the numeric representation level, one can use directly the raw data from a tracking module like in [START_REF] Dagtas | Models for motion-based video indexing and retrieval[END_REF]. However, data from tracking contain much noise because they are obtained from algorithms tracking motion from frame to frame based on low-level features. Therefore, some methods of preprocessing such as trajectory smoothing [START_REF] Sahouria | A trajectory Based Video Indexing System for Street Surveillance[END_REF] are proposed. However, citing [START_REF] Lin | A Symbolic Representation of Time Series, with Implications for Streaming Algorithms[END_REF] from the domain of temporal data mining, using directly the raw numeric values from trajectories can limit the efficiency of the algorithms, data structures, and some methods, or algorithms, are not (well) defined for numeric approaches but exist for symbolic approaches. Moreover, symbolic representation is closer to human perception (although not yet semantic). For trajectories, researchers have proposed many symbolic representations from one dimension [START_REF] Agrawal | Querying shapes of histories[END_REF], [START_REF] Chen | Video Retrieval Based on Motion Tracks of Moving Objects[END_REF] to two dimensions [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF]. A semantic representation is also of high interest for trajectories, translating values into concepts. Some preliminary works are proposed in [START_REF] Li | Modeling of moving objects in a video databas[END_REF].

Despite of much effort in trajectory representation, one does not have yet a successful trajectory-based video indexing and retrieval approach. One problem is that the user is not included in the retrieval loop when conceiving a representation scheme. In information retrieval, user-centered scheme are very important because a simple query can rarely fit the complete user needs. An approach enabling interaction with the user allows him/her not only to refine the query but also to judge the results given by the system.

From this previous observation, our work is aiming to add relevance feedback ability in some existing and efficient trajectory representations. Relevance feedback ability can be expressed by the possibility to change the measure distance or by a representation that can adapt better with the user needs.

Our work is concentrating on the symbolic level because of its robustness to noise, and its ability to link with the semantic level. Chen has proposed an efficient symbolic representation, beyond the numeric presentation, which does not suffer from scaling, translation or rotation [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF]. In this paper, we are reusing this representation method and we are extending it with two new similarity measures inspired from the idea of sequence alignment in the bioinformatic domain [START_REF] Atlschul | Basic local alignment search tool[END_REF].

The main contributions of our paper are the following:

• Propose two similarity measures for trajectory comparison at the symbolic level.

• Present two methods for relevance feedback in trajectory-based video indexing and retrieval based on the proposed similarity measures.

The rest of the paper is organized as follow. In Section 2, we are proposing a structure for a Trajectory-Based Video Indexing and Retrieval Enabling Relevance Feedback (TBVIREF) which includes trajectory representation at the numeric and symbolic level, sequence alignment and feedback. Some experimental results are shown in section 3. Section 4 is concluding this paper with some directions for future work.

II. TRAJECTORY-BASED VIDEO INDEXING AND RETRIEVAL ENABLING RELEVACE FEEDBACK (TBVIREF)

A. General description We are proposing an architecture for TBVIREF (Fig. 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. But without a priori contextual information, trajectories are 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 numeric and symbolic representation modules. The output is a symbolic representation of the global trajectory.

For retrieval, a given trajectory by the user is also processed through these two modules, and comparison is made with the trajectories in the database based on two available similarity measures (section II.D). Trajectories that are the most similar (given the chosen similarity measure) with the trajectory query are returned to users. Moreover, unlike other approaches for trajectories, this approach includes the user in the retrieval loop. The user judges the returned results as relevant or irrelevant through an interface. Then, retrieval loops again and continues until the user is satisfied.

B. Numeric trajectory representation

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 with 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.

Given a 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:

,( 1) ,( ) , , ( 1) ,( ) a,i ,( 1) ,( ) ,, ( 1 ) , ( ) ,, ( 1 ) , ( ,, ( 1 )
- = - -≥ +Π - =- -Π - , ( 1)
,( )

0 ai ai yy + ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ -≤ ⎩ > (1)
and the movement distance ratio is defined as:

22 ,( 1) , , ( 1) , A
, A 22 ,( 1) , , ( 1)
, 11

() () TD(T ) 0 () 0 TD(T )=0 () ( ) ( ) ai a i ai a i ai A Aa j a j a j a j jn yyxx TD T TD T y y x x δ ++ ++ ≤≤- ⎧ -+ - ⎪ ≠ = ⎨ ⎪ ⎩ =- + - ∑ (2)
Raw trajectory data given to this module are transformed into 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.

C. Symbolic trajectory representation

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 , two dimensional (movement direction, distance ratio) space is divided into 21

dir dis π εε ⎛⎞ ⎛ × ⎜⎟ ⎜ ⎝⎠ ⎝ ⎞ ⎟ ⎠ subregions.
Fig. 2 gives an example of this quantization map, dir and dis are chosen π/4 and 0.125. 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 the upper right coordinates of SB i . A distinct symbol A i is assigned for subregion SB i . 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 . Once the two threshold values dir and dis are given for the trajectory data, the size of movement pattern alphabet is fixed.

D. Sequence alignment and matching

The sequence alignment consists in the construction of a dictionary and the trajectory matching. Dictionary construction transforms a sequence of n symbols S=[s 1 , …,s n ] into a set of distinct ℓ length-words {w j }, ℓ being the length of a word. This word set is called a dictionary. Lets D Q being the dictionary for a sequence query S Q (D Q consists of r distinct ℓ length-words {w iQ }), D T being the dictionary of a sequence S T in the database (D T consists of k distinct ℓ length-words {w jT }). Because a word may appear several times in a sequence and in the dictionary, we store the position of each word and the number of their occurrences.

Before presenting the proposed similarity measures, we give here two notations: Hit and Ap_hit notations.

Definition: Hit

Given two sequences S Q =[s 1Q , …,s nQ ] and S T =[s 1T , …,s mT ] after the dictionary construction process, S Q can be represented by r distinct ℓ length-words {w iQ }, i from 1 to r and S T can be represented by k distinct ℓ length-words {w jT }, j from 1 to k. A Hit can be identified between S Q and S T if one find a word w iQ in S Q and a word w jT in S T satisfy w iQ = w jT , i from 1 to r and j from 1 to k.

Definition: Ap_hit

Given two sequences S Q =[s 1Q , …,s nQ ] and S T =[s 1T , …,s mT ] after dictionary construction process, S Q can be represented by r distinct ℓ length-words {w iQ }, i from 1 to r and S T can be represented by k distinct ℓ length-words {w jT }, j from 1 to k. A Ap_hit (approximate hit) can be identified between S Q and S T if one find a word w iQ in S Q and a word w jT in S T satisfying w iQ = w jT or w iQ being a neighbor of w jT . Two words are neighbor if their orderly symbols are assigned for the neighbor regions in the quantization map.

One can realize that the Ap_hit notation can resolve the problem of quantization (two close numeric values being assigned different symbols because of the quantization). We give in Fig. 3 some examples of these notations. With two given words: word1 is 'MNOP' and word2 is alternatively 'MNOP', 'MVOP' and 'MFGH', using the same quantization map in Fig. 2, Hit and Ap_hit notations give different values. Based on these Hit and Ap_hit notations, we propose two similarity measures:

• Scanning the sequence S Q until detecting a Hit or a Ap_hit at i th word between this sequence with a sequence S Q in the database, making an extension alignment in [START_REF] Atlschul | Basic local alignment search tool[END_REF] and computing a similarity measure d(S Q , S T , i). This first similarity measure is computed as:

2 Q T i=1...r d( S, S) = m a x ( ( , ,) ) QT dS S i (3)
• This similarity measure take into account the number of the Hit or the Ap_hit between the sequence query S Q and a sequence S Q in the database. A word hit vector word_hit, for j from 1 to k, each element word_hit[i] storing the number the Hit or the Ap_hit of word w j between the S Q and the S T . This second similarity measure between S T and S Q is defined as:

r 2Q T i=1 d (S , S )= word_hit [i] ∑ (4)
From these definitions, one can see that partial matching can be used for both of the proposed similarity measures. By identifying a subsequence inside the trajectory query, the similarity measures (3) and ( 4) between this subtrajectory query and trajectories in the database can be computed. Furthermore, the proposed similarity measures allow the user to decide the importance of some parts in the trajectory query by giving their weight.

Because the proposed similarity measures are sensible to the starting point for comparing two trajectories, we detect the point in the sequences where the first Hit or Ap_hit is found and then compute the similarity from this point

E. Relevance Feedback

Relevance feedback is a well known technique in the information retrieval domain. It covers a range of techniques intended to improve a user query and facilitate retrieval of information relevant to the user needs. This technique has been firstly used for text retrieval, but now it becomes more and more important for image and video retrieval as well. Up to now, to our knowledge, there is not any work dedicated to the trajectory-based video indexing and retrieval enabling relevance feedback.

In our approach, associated with the two proposed similarity measures, we have developed two new methods for including feedback. Even if results are not yet available for these methods, we present them in this section as current development and to stress the possibility of including interactions in the presented similarity measures.

Let RT be the set of N the most similar trajectories RT= [RT 1 ,…,RT N ] at current search result.

Relevance feedback 1:

The user is judging the results of the current search as being relevant or irrelevant. From this feedback information, one can know which word hit is more significant than the others for this query. Let index_hit be the index of this word. For the next retrieval loop, in spite of using the similarity measure (3), a new similarity measure is defined as:

1, (,) (,, new Q T Q T d S S d S S index = ) ) (5)
Relevance feedback 2: A given query S Q consisting of r distinct ℓ length-words, a weight vector is specified where weight[i,t] is the weight for the words w j at t, j from 1 to r. At t=0, this vector is initialized with the number of occurences of the word w j in the trajectory query. From the feedback information, with each result sequence RT j , this vector is updated as: For the next retrieval loop, in spite of using the similarity measure (4), a new similarity measure is defined as:

(6) j j [ , 1]) [ , ]) _ [ ] if RT is relevant [ , 1]) [ , ]) _ [ ] if
r 2,new Q T i=1 d( S , S ) = ( _ [ ] * [ , 1 ] word hit i weight i t + ∑ (7)
One can see that a word often appearing in the relevant examples means that this word is more important. Therefore, in the next retrieval loop, this word is chosen to compute the similarity measures (relevance feedback 1) or to add more weight on its hit (relevance feedback 2) and the opposite for irrelevant words. From this observation, the proposed relevance feedback methods can take into account the user needs.

III. EXPERIMENTS

A. Video and trajectory databases

As said in section II.A showing the general description of our architecture, we are supposing that object tracking is done by a preprocessing module, and object trajectories are taken as input for our work. Therefore, in this section, in order to test our approach, we are using two trajectory databases. We are comparing our proposed similarity measures with the existing Edit Distance on Movement Pattern (EDM) [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF].

The ASL data set from UCI KDD1 data archive consists in samples of signs from the Australian Sign Language. More than 95 signs were collected from 5 different writers. In total, this sign database comprises 6577 signs. Fig. 4 gives some samples of the word 'eat' written by 5 different writers.

The trajectory database of Yuan Ze University2 containing 2500 trajectories which comes from 50 categories was generated. Fig. 5 shows all kinds of trajectory types used in this database. Each category includes 50 samples that were drawn in different sizes, moving directions, rotations, and translations.

B. Experiments

In these experiments, dir and dis are chosen as π/4 and 0.125 for the symbolic representation.

In order to evaluate and compare the results, we use a wellknown measure in the information retrieval domain: recall/precision curve [START_REF] Muller | Performance Evaluation in Content-Based Image Retrieval : Overview and Proposals[END_REF]. Recall defines the number of relevant documents retrieved as fraction of all relevant documents and precision defines the number of relevant documents as a fraction all the documents in retrieved by the system. The better method, the nearer it approaches to the ideal point where recall is 100% and precision is 100%. Fig. 6 is giving the retrieval results for the ASL trajectory database. In this experiment, the chosen length ℓ for words is 5. The curve with violet circles presents the retrieval results using the EDM distance, the curve with blue rectangles presents retrieval results using the second proposed similarity measure (4). One can see that for this database the proposed similarity measures give results comparable with those for EDM. Moreover, with a small number of returned results (recall is between 0 and 10), the proposed measure gives a lightly better result. This characteristic can be useful because in the information retrieval domain, the user is usually interested in only some relevant results. However, the results for both measures on the ASL database are not very good because the ASL database is a difficult database. One word can be written in different ways by the same writer (different trajectories); moreover, the trajectories in this database are acquired by extracting a glove position during the writing phase, with much noise. The presented experimental results here are obtained without using any pre-processing on the data like noise filter. Fig. 7 gives the retrieval results for the second proposed similarity measure (4) for the Yuan Ze University database with different word lengths. For this database, results are better for a short word length like 3 than for longer word lengths. Figure 6. Recall and precision curves for the ASL trajectory database. The curve with violet circles presents the retrieval results using the EDM distance [START_REF] Chen | Symbolic Representation and Retrieval of Moving Object Trajectories[END_REF], while the curve with the blue rectangles presents the retrieval results using the second proposed similarity measure.

Figure 7. Recall and precision curves of the proposed similarity measures on the second trajectory database with different word lengths. The curve with blue diamonds presents the results with the used word length is 2, the curve with violet rectangles presents results with the used word length is 3, the curve with yellow triangles presents results with the used word length is 5, the curve with green circle presents results with the used word length is 10 and the curve with red dot presents results with the used word length is 20.

As one can see from above results, choosing the word length affects significantly the retrieval results, so it could be useful to develop some heuristics. Moreover, a fixed length is not always suitable for various types of trajectories.

From the obtained results, we can see that the proposed similarity measures can give interesting and good results for partial matching, as shown in Fig. 8. Using a simple trajectory query (Fig. 8a) for retrieving more complex trajectories which include the query trajectory (Fig. 8 b,c,d). This characteristic can be very important in trajectory-based video indexing and retrieval when users are interested in only one part of object trajectory, or for retrieving trajectories containing a given pattern.

Apart from the above advantages, the proposed similarity measures have some weakness. They suffer from the starting point from which we divide the words and the length of words. For the starting point, we are using the sequence alignment to detect the first Hit or Ap_hit between two trajectories and are computing distances between them from this point. The alignment method that we used needs to be improved in order to be more robust. For choosing the word length, it could be useful to develop some heuristics.

Two methods of relevance feedback are also proposed. From the theoretical analysis, these methods promise giving a retrieval improvement. The implementation and some experimentation should be done to prove their performance.

IV. CONCLUSIONS AND FUTURE WORK

In this paper, a Trajectory-Based Video Indexing and Retrieval Enabling Relevance Feedback approach has been proposed. In this approach, trajectory matching is effected at the symbolic level based on a numeric representation that does not suffer from noise, rotation, translation. Two similarity measures have been presented. From these measures, two ways for making the relevance feedback have been proposed. Some experimental results have been shown.

As we have discussed in the experiment section, the proposed measures enable doing some partial matching and relevance feedback. These are important techniques to improve the retrieval results. However, they are affected by the starting point from which we divide the words and the length of word.

Figure 1 .

 1 Figure 1. Architecture for Trajectory-Based Video indexing and Retrieval Enabling Relevance Feedback

Figure 2 .

 2 Figure 2. A quantization map for the symbolic representation (reprinted from [6])

Figure 3 . 2 ,

 32 Figure 3. Some examples of Hit and Ap_hit notations with two given words.word1 is 'MNOP' and word2 is alternatively 'MNOP', 'MVOP' and 'MFGH', using the same quantization map as in Fig.2, Hit and Ap_hit notations give different values.

Figure 4 .Figure 5 .

 45 Figure 4. Some samples from the ASL database of the word 'eat' from 5 different writers

Figure 8 .

 8 Figure 8. Partial matching using the proposed similarity measures. (a) simple trajectory query (b)(c)(d) complex retrieved trajectories which include the initial query.

http:// kdd.ics.uci.edu/databases/auslan/

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

Further work is needed to strengthen the methods on this point.

In addition, in this paper, two methods for enabling relevance feedback in trajectory retrieval have been proposed. Further work will provide experiments to prove their effectiveness.