Mu Lei

Isaac Caicedo-Castro

Marie-Christine Fauvet

Ahmed Lbath

Context-Aware Service Discovering System for Nomad Users Pathathai Na-Lumpoon* *

Keywords: User privacy, Recommender systems, Web Service Composition, Semantic-based Orchestration, E-Tourism

This paper presents an architecture for a system that provides nomad users, context-aware personalised services. Users might need any sort of services: information about the weather forecast for the next day, or about a museum in the neighbour worth to visit. These services are known as stateless services. More complex situations ocurre when services are stateful. Such services are, for example those which need users to be logged in (e.g. booking a room in a hotel). The question discussed in the text are those related to: i) user's privacy, ii) recommendation and discovery of services, iii) composition of recommended services into a composite service, and iv) execution of the resulting composite service.

Introduction

With the development of pervasive computing and mobile technologies, mobile applications are getting more and more attention. These applications, running on mobile devices, are challenged to locate and deliver the right service to the right person, with the appropriate rendering.

The work reported in this paper is a part of a broader project which aims at designing and implementing a privacy-sensitive framework which provides context-aware personalised services for nomad users according to their needs, profile and context (see Na [START_REF] Na Lumpoon | Illustrating some issues raised when designing context-aware personalized services for mobile users[END_REF]). The issues to be addressed in this project are related to system design, software architecture, distributed and heterogeneous resource access and integration, information retrieval and recommender systems. Specifically, the following research questions are raised: i) How to protect user's privacy using her profile and context? ii) How to provide highest quality recommendation of services to be composed? And iii) How to orchestrate and execute the resulting recommended composite service?

The rest of this paper is organised as follows: Section 3 sketches the architecture and components of the system proposed in this work. Section 2 presents two illustrating examples that motivate the project. Section 4 discusses users' privacy respect and management. Section 5 introduces basic concepts and design of the mechanism to retrieve services which fulfil users' needs. In Section 6 we show how to compose the recommended services, then how to orchestrate and execute the resulting composite service. Eventually, we conclude and propose some perspectives in Section 7.

Motivating examples

We illustrate our approach by the two following scenarios. Bob is from the UK, he likes and practices a lot of sports. He is travelling for work in Chiang Mai, Thailand. He is seeking for some tourism activities he can do during the next two days and which depend on the weather forecast. As, Bob didn't give neither where, nor when he wants to do these activities, this latter information will be taken from his query context (i.e. these values are given by the location and time sensors embedded in Bob's device, see Section 4).

According to his profile, preferences and privacy model (see Section 4) two services are found by the recommendation system (see Section 5): one, named WF, which exposes one operation op1.WS which returns the weather forecast depending on the given location and time, the other service, named AC, with one operation as well op1.AC which returns a list of activities, given a location and weather forecast. These two services are then composed in order to build a new composite service (see Section 6). In this example, when executing the composite service, first the operation exposed by WS is enacted, and second the operation exposed by AC. This execution is orchestrated by our system, and executed in the behalf of Bob, then its result is returned to Bob's mobile device.

Nuts and bolts of the system

According to the fact and problems stated in previous section, we propose the Context-Aware Services Discovering System for mobile users. Figure 1 depicts the components of this system, which are described as follows:

• User Interaction and Query Management: This component aligns the user's query to her profile and context taking into account her privacy model. If Bob does not want to disclose his location, when entering the query, so the location is kept unknown, and will be treated as a parameter of the resulting composite service which will be proposed to him.

• User Management: This component classifies the user into user profile group while protecting the user privacy. Section 4 presents a detailed description about this component. • Service Composition Management: This component receives a set a services to be composed according to an abstract plan deduced from the user's query. Then the resulting composite service is executed on the behalf of the user (see Section 6).

User Management

According to [START_REF] Yang | Ontology-based preference model in digital library[END_REF], as the foundation and core of personalised information service, the accuracy and effectiveness of the description of user preferences by user models, and the reasonableness of the recommendation algorithm, are directly related to the quality of the services. As an information service system especially for mobile users, we take more advantage of context-based services, and also we need to pay more attention to adapt the several of different mobile devices.

Based on this consideration, we need to define the "user profile"and "context"during the research, in order to better adapt to the features of mobile devices. Regarding to our program, the better way to differentiate them, may be evaluating the usage of the descriptions in user profile and context.

In our architecture, there are 3 tables which contain user information, these ones shall be used to index the suitable services that fulfil the user queries, in order to execute the services selected by the users, and to try to predict the potential better parameters for executing services for certain users. Firstly let's start with an example. Bob's profile is [gender: male, citizenship: UK, Occupation: Engineer, age: 28, favourite activities: hiking, museum], with his context: . This record will be matched with the user ID that came alone with Bob's query, and sent to the system in order to retrieve in the service descriptions the available services.

The second table contains the record of Bob's personal information, [Bob, M, UK, Engineer, 28, hiking, museum]. This record will be sent along with the result list of services that fulfil Bob's query, to be part of the parameters needed to execute the service, and also be used to find the best user cluster for Bob (i.e. in which users have the most similar preferences to Bob). The third table contains the potential parameters to be used to execute the selected service for every cluster of users. It should be trained to optimise the parameters for any cluster of users. In order to provide personalised service suggestions, we approach to identify the K Nearest Neighbours (KNN) of the active user (users with similar interests), and calculate a prediction of the active user's potential parameters for a specific service. These parameters can be defined, for example, as the weighted average of the KNN's parameters.

To predict users' potential interest by his "nearest K neighbors", we propose the use of "Group User Profile", which is abstracted from a cluster of users with shorter distance to each other. While users are interacting with the system, their privacy has to be considered. Different users at different time and location might have different understanding or definition of their privacy, in order to meet these requirements; a component which is able to collect and summarise the "privacy rule"of user is proposed to be adopted before using any user information in the database, as shown in Figure 2. In others words, an additional part will be added to the user's profile, which includes the description of her "Privacy".

While clustering, the profiles might be input by users directly or requested from other cooperators' database. For example, some user might login to the system using their Facebook account because they think Facebook will not leak and misuse their personal information. In order to protect the privacy of users who directly saved their profile in our system, we need a privacy sensitive distributed clustering method.

The Protecting might be done by both Data Encryption or Distance based clustering method. As we know, location is a very important parameter in mobile applications, and most of the tourism mobile applications are location-based. Let's take a look at the mostused method for mobile users to get their own location: Global Positioning System (GPS) with Assisted GPS (AGPS).

With GPS, mobile users could get their location by knowing the distance between the device and at least 3 of the 24 satellites working for the system. GPS information is considered the standard of geographical data. But in case we have a capture failure of the GPS satellites navigation signal, or a relatively longer time waiting for the response from the satellite since we were in some particular landscape such as very narrow streets, we will need AGPS module to help us. Mobile devices got their relatively accurate location from Location Provider, and request Location Based Services with these location information.

In other words, beside GPS, we will need to use AGPS module to contact to, which means we will have to send our local network information to the Location Provider, in order to get the right location information. And also we will have to contact to the Location Based Service Provider (LBSP) with the current location information.

In this case, to protect user's current location, we will have to consider both the communication between the mobile device and the Location Provider (LP), and also the communication between the mobile device and the LBSP.

For the LP, to minimum the communication between the mobile device and the LP is the only way. In case that we do not really need a very accurate location, a certain set of information needed by the Location Provider might not be sent, according to the user's preference. Or we can directly use WI-FI access to locate the user directly.

Anonymity and cloaking based methods will be useful for the LBSP. Firstly we will have to consider the detail of the data needed by a certain service, for example, a service for booking a room in hotel, usually asking only the approximate location of the user, like the name of the city. Or we can use an agent-based method in order to be anonymous.

Recommendation system

This system is in charge of retrieving Services whose description matches with the user's query. A Service description is given in its WSDL file (Web Service Description Language) document [START_REF] Chinnici | Web services description language (WSDL) version 2.0 part 1: Core language[END_REF] . This kind of document is coded in a XML format, thereby, a WSDL document describes, in a textual format, a Service, its operations, and its parameters. To represent a WSDL document onto a vector space model is possible due to it is feasible to compute the relevance of each distinct word in this kind of document, also [START_REF] Hess | ASSAM: A tool for semi-automatically annotating web services with semantic metadata[END_REF] assert this assumption. Moreover, a part of a WSDL document could have documentation which is comments (i.e., unstructured text). Therefore, the aim consist of building an index with a corpus composed by WSDL documents onto a vector space model, which allow to retrieve a ranked list of Services, which is decreasing sorted in accord their similarity with the user's query in the same vector space.

Before to index WSDL documents is necessary a preprocessing procedure to extract the comments associated with each service, its operations and parameters. This procedure also splits service identifiers and operation names, which are combinations of more than two words, e.g., "getWeatherForecast"should be separated in the words: "get", "weather", and "forecast". Next, the procedure removes symbols and stop words (e.g., the, is, at, which, of, etcetera), and transforms all words to lower-case. Service identifiers, operation names, and documentation are retrieved as an automatic part of the preprocessing step. This can be implemented by using Java API XML Processing (JAXP), which is an Application Programming Interface (API) for XML processing. Finally, vectors with the frequencies of each. Index terms for all text descriptions are built, in order to make a bag-of-words as a matrix of term frequencies by using Inverse Document Frequency (IDF) weighting to highlight the relevance of each word along the corpus. Let X ∈ R m×n be the matrix of term frequencies, such that m is the number of text terms, and n is the number of WSDL documents in the corpus. This matrix provides information about the occurrence of each term for each WSDL document in the corpus.

After this preprocessing procedure, the next step is to build an index based on latent factors. In this work the purpose of use latent factor analysis is to explain these above mentioned occurrences by characterising the term frequencies by using a set of r factors inferred from occurrence patterns. This factors measure dimensions such as how expensive is to consume a Service, or how much the Service is related to sport tourism activities. This factors can measure less well defined dimensions, or other ones completely uninterpretable.

For every term, each factor measures how much this appears in WSDL documents related with corresponding factor. These factors form new meaningful dimensions to cluster WSDL documents.

Taking into account this model, text terms can be represented in a latent factor space, their relationships may be explained by using the inner product among their corresponding representations. Let {z t ∈ R r } n t=1 be the set of n column vectors of the matrix Z ∈ R r×n , which represent the set of n WSDL documents of the corpus. Let {w t ∈ R r } m t=1 be the set of m column vectors of the matrix W ∈ R r×m , which represent the set of m text terms. The components of the vector z i measure the extent to which the WSDL document i expresses latent factors. On the other hand, the components of the vector w j measure the extent to which the term j appears in the WSDL documents associated to the corresponding factors. Therefore, the problem consist of learning both vectors (z i and w j ), such that the resulting! dot product between these vector is approximated to the occurrence of the term i within the WSDL document j, as follows:

x ij = (w j ) T z i = r k=1 w j k z i k (1)
This can be written in matrix form as follows:

X = W T Z (2)
In consequence, the most appropriated form to solve this problem is by means of matrix factorisation techniques, e.g., Singular Value Decomposition [START_REF] Deerwester | Improving Information Retrieval with Latent Semantic Indexing[END_REF], Non-Negative Matrix Factorisation [START_REF] Xu | Document clustering based on non-negative matrix factorization[END_REF], or Probabilistic Matrix Factorisation [START_REF] Hofmann | Probabilistic latent semantic indexing[END_REF][START_REF] Blei | Latent dirichlet allocation[END_REF]. Theses techniques can be used to compute these matrices (W and Z) out of the original bag-of-terms X, i.e., to find a factorisation of X in terms of W and Z.

The index is used to match similar contents given a particular user's query. Let q ∈ R m be the user's query in the vector space model. All vector in this space can be projected in the latent space by computing z ∈ R r , such that q = W T z. Therefore z can be found with the expression 3 as follows:

z = (W T ) -1 q (3)
Once the user's query has been projected onto the latent space, it is necessary, using a similarity measure, to compute the similarity between vectors in the latent space. So, the expression 4 is used in order to compute this similarity between the user's query and the others WSDL documents indexed in the latent space.

s = Z T z (4)
where s ∈ R n is a vector of similarity scores. Each component s i of this vector is the ranking recommended for each service i, when the user expresses her (or his) needs through the query q. In other words, s is the recommendation, whose services with greatest rank are the most recommended, and those with the lowest are the least recommended to fulfil the user's needs.

Finally, the services retrieved by the recommender system are filtered and orchestrated by the component described in the section 6.

Service Composition Management

The Service Composition Management (SCM in short) has the responsibility for automatically producing the synthesis of the composed service that is built as an orchestration of existing services. The goal of service orchestration is to invoke the existing relevant services according to the designed abstract plan. The SCM involves two processes as described in the following.

1. Service selection process: Many existing works use service description languages such as OWL-S [START_REF] Burstein | OWL-S: Semantic Markup for Web Services[END_REF], WSML (de Bruijn et al., 2006), SAWSDL [START_REF] Farrell | Semantic annotations for WSDL and XML schema[END_REF], USDL [START_REF] Bansal | A universal service-semantics description language[END_REF] to represent both functional and nonfunctional aspects of web services and build up application to use these semantic service descriptions. We adopt SAWSDL as service description standard. Since SAWSDL has been proposed by the recommendation of W3C in 2007, many works have been used it widely. In addition, SAWSDL is a lightweight approach to annotate service descriptions. It uses external extended attributes called ModelReference to establish a relationship between WSDL components and concepts in another semantic model. The figure 3 shows WSDL components and the SAWSDL annotations that point to semantic concepts for specifying semantics or to schema mappings for data transformations [START_REF] Van Assem | Rdf/owl representation of wordnet[END_REF].

2. Service composition process: Dataflow control and artificial intelligence planning approaches are two candidate approaches to compose services. BPMN (Business Process Model and Notation) (see OMG ( 2011)) is the major language for modeling business processes in both industry and academic. As BPEL (Business Process Execution Language) (see [START_REF] Fu | Analysis of interacting bpel web services[END_REF]) is getting less and less attention, we haven't considered it. However, dynamic service orchestration at runtime is a difficult problem and very complicated when the maintenance time arises. For AI planning technique, the goal and requirement definition have to be explicitly specified. Pre-conditions and effects of target services are used in composition of services. For example, [START_REF] Sirin | {HTN} planning for web service composition using {SHOP2}[END_REF] use the SHOP2 planner to build compositions of services described in DAML-S. Similarly, [START_REF] Klusch | Evaluation of service composition planning with owls-xplan[END_REF] use OWLS-XPlan to build composed service in OWL-S. However, these techniques focus on selecting the right services at run-time. However, they caannot dynamic re-plan a composition at run-time. SCM (see Figure 4) is proposed to solve the problems stated earlier which are semantic schema matching and dynamic service composition at runtime. A key to success service composition is to match abstract service or requested service to existing concrete services. In our SCM, we use SAWSDL to represent abstract services and concrete services and apply logic reasoning using AI planning technique to orchestrate engine to orchestrate composed services. The components of our SCM approach to service orchestration are following.

• Interpreter: The Interpreter is the component which is responsible for retrieving the relevant abstract actions given the template id by the User Interface Management (UIM) component. The UIM component provides a template which is a workflow dictating the sequence of tasks to users. Afterward, the UIM passes user arguments to UP Management component and the template id to the Interpreter component. We propose tourist information tasks model to represent the orchestration of tourist task actions. Thus, the Interpreter looks up abstract actions given by template id in the Orchestration Model repository, and send them to the Planner Component.

• Planner: The Planner is the component which is responsible for synthesizing automatically an abstract plan. The abstract plan represents a sequence of abstract actions. In order to automatically build up an abstract plan, the goal and initial states • Orchestration Engine: The Orchestration Engine is the component which is responsible for synthesizing the composed service according to the received abstract plan. The Orchestration Engine will match each abstract action in the abstract plan with concrete service in the list of available services received from the Recommendation System. Afterwards, the Orchestration Engine will develop business process orchestration model and bind the model with the endpoint web services. Finally, the composed web service with the user parameters are ready to be executed. The parameters used in the service execution process are either from user specifies by himself or user preference in the user profile. The resulting service will be executed on the behalf of the user. However, we add an event handler to Orchestration Engine for monitoring unexpected situations which might happen at runtime. For Instance, when the Orchestration Engine receives a notification that a chosen concrete service is no longer available, the event handler will send this message to the Interpreter to re-plan the abstract plan. Our approach is similar to [START_REF] Cugola | Dsol: a declarative approach to self-adaptive service orchestrations[END_REF] who used descriptive language to selfadaptive service orchestration.

However, this approach needs the help from domain expert to set the abstract actions, which are used as the building blocks of orchestration plans, goal and initial state.

To illustrate the orchestration technique, we follow the query, from example, Bob wants to search for tourism activities in Chiang Mai in the next 2 days according to the weather forecast and his preferences. The template and user's context are used to fulfil all required The parameters are kept in object variables, which are used later at service execution time. The discovered abstract actions are sent to the Planner to generate the abstract plan using graph plan. The planner analyses the input and output of each abstract action. From Bob's example, one of inputs of abstract action 2 is weather, which is output of abstract action 1. So the Planner synthesises the graph plan like:

The abstract plan is sent back to the Orchestration Engine to match each abstract action to the concrete service and retrieve all executed parameters in order to produce the composed service. To execute the composed service, the web application is built up to display the resulting service to user.

Conclusion and Perspectives

The contribution of this work is the proposal of a Context-Aware Services Discovering System for Nomad Users which allows reuse of (web) services, automatic orchestration, composition and discovery of services (stateless and state-full) taking into account the profile, context, and explicit user's needs. In the design principles, the user privacy has been considered from inception of the design system. This is a very important contribution of this work, because the system cannot keep protected the user information from unauthorised access.

The perspectives for further work are: i) To integrate machine learning techniques in order to classify, cluster, and associate Web Services. ii) To assess if the learning of features algorithms based on matrix factorisation can infer import an Web service's features as quality of services. iii) To determinate or propose the best matrix factorisation technique to implement the Filtering Collaborative approach proposed in this work. iv) To evaluate the system proposed in this paper by means experiments performed over its implementation. COLCIENCIAS-COLFUTURO (convocatoria 528 de 2011) scholarship, and he is also founded by the University of Córdoba (Colombia). Authors thank the anonymous reviewers for their relevant comments and their help to improve the quality of this paper.

Figure 1

 1 Figure 1 Components of the Context-Aware Services Discovering System for Nomad Users

  [Date: 25 June 2013, Local time: 12 pm, Location: 48 • 52' 25.68" N, 2 • 17' 42" E ]. The first table contains the record of Bob's user Identification (user ID) and his context: [1000, 25 June 2013, Local time: 12 pm, Location:48 • 52' 25.68" N, 2 • 17' 42" E ]

Figure 2

 2 Figure 2 Process of getting individual privacy rules of user

Figure 3

 3 Figure 3 The Web Services Description Language (WSDL) with Semantic Annotations for WSDL and XML Schema (SAWSDL) (taken from Kopecky et al. (2007))

Figure 4

 4 Figure 4 SCM approach to service orchestration

Figure 5

 5 Figure 5 Abstract plan for execution

Acknowledgement

Pathathai Na-Lumpoon and Mu Lei are PhD students supported by European Union's Erasmus Mundus programme. Isaac Caicedo-Castro is a PhD student supported by


Bahjat Safadi

Nadia Derbas

Abdelkader Hamadi

Thi-Thu-Thuy Vuong

Han Dong

Philippe Mulhem

Georges Quénot

Quaero at TRECVid 2013: Semantic Indexing

The Quaero group is a consortium of French and German organizations working on Multimedia Indexing and Retrieval 1 . LIG participated to the semantic indexing main task, localization task and concept pair task. LIG also participated to the organization of this task. This paper describes these participations which are quite similar to our previous year's participations. For the semantic indexing main task, our approach uses a six-stages processing pipelines for computing scores for the likelihood of a video shot to contain a target concept. These scores are then used for producing a ranked list of images or shots that are the most likely to contain the target concept. The pipeline is composed of the following steps: descriptor extraction, descriptor optimization, classification, fusion of descriptor variants, higher-level fusion, and re-ranking. We used a number of different descriptors and a hierarchical fusion strategy. We also used conceptual feedback by adding a vector of classification score to the pool of descriptors. The best Quaero run has a Mean Inferred Average Precision of 0.2848, which ranked us 2 nd out of 26 participants. We also co-organized the TRECVid SIN 2013 task and collaborative annotation.

1 Participation to the organization of the semantic indexing task

For the Fourth year, UJF-LIG has co-organized the semantic indexing task at TRECVid with the support of Quaero. A list of 500 target concepts has been produced, 346 of which have been collaboratively annotated by the participants and by Quaero annotators.

A subset of 60 of them was selected for participants' submissions and 38 of which have been officially evaluated. The 500 concepts are structured according to the LSCOM hierarchy [START_REF] Naphade | Large-scale concept ontology for multimedia[END_REF]. They include all the TRECVid "high level features" from 2005 to 2009, the CU-VIREO374 set plus a selection of LSCOM concepts so that we end up with a number of generic-specific relations among them. We enriched the structure with two relations, namely implies and excludes. The goal was to promote research on methods for indexing many concepts and using ontology relations between them.

TRECVid provides participants with the following material:

• a development set that contains roughly 600 hours of videos;

• a test set that contains roughly 200 hours of videos;

• shot boundaries (for both sets);

• a set of 500 concepts with a set of associated relations;

• elements of ground truth: some shots were collaboratively annotated. For each shot and each concept, four possibilities are available: the shot has been annotated as positive (it contains the concept), the shot has been annotated as negative (it does not contain the concept), the shot has been skipped (the annotator cannot decide), or the shot has not been annotated (no annotator has seen the shot).

The goal of the semantic indexing task is then to provide, for each of the 60 selected concepts, a ranked list of 2000 shots that are the most likely to contain the concept. The 2013 test collection contains 112,677 shots. More information about the organization of this task can be found in the TRECVid 2013 overview paper [START_REF] Over | TRECVid 2013 -An Overview of the Goals, Tasks, Data, Evaluation[END_REF]. A pair version of the task in which 10 pairs of concepts (e.g. Car+Bicycle) has also been proposed this year.

Development and test sets

Data used in TRECVid are free of right for research purposes as it comes from the Internet Archive 1 provides the main characteristics of the collection set. The whole set of videos has been split into two parts, the development set and the test set. The test set has been split in three part dedicated to the TRECVid SIN evaluations of 2013, 2014 and 2015. This has been done in order to be able to measure the performance progress over the three years. All sets were automatically split into shots using the LIG shot segmentation tool [START_REF] Quénot | CLIPS at TRECvid: Shot boundary detection and feature detection[END_REF].

The evaluation measure

The evaluation measure used by TRECVid is the MAP (Mean Average Precision). Given the size of the corpus, the inferred MAP is used instead as it saves human efforts and has shown to provide a good estimate of the MAP [START_REF] Yilmaz | A simple and efficient sampling method for estimating AP and NDCG[END_REF].

Annotations on the development set

Shots in the development set have been collaboratively annotated by TRECVid 2010-2012 participants and by Quaero annotators. As concepts density is low, an active learning strategy has been set up in order to enhance the probability of providing relevant shots to annotators [START_REF] Ayache | Video Corpus Annotation using Active Learning[END_REF]: the active learning algorithm takes advantage of previously done annotations in order to provide shots that will more likely be relevant. Although this strategy introduces a bias, it raises the number of examples available to systems. Moreover, it exhibits some trend in the concept difficulty. As an example, the number of positive examples for the concept Person is larger than the number of negative examples. This means that the active learning algorithm was able to provide more positive examples than negative ones to annotators, meaning that Person is probably a "too easy" concept. 346 concepts were annotated on IACC.1.C (tv12 test) by Quaero annotators. The new annotations were once again using an active learning approach bootstrapped with a fusion of all the TRECVid SIN 2012 submissions. This also ensures that the active learning based annotation is not biased in favour of the system used for the active learning process. An improved algorithm for annotation cleaning has also been used in the annotation tool this year [START_REF] Safadi | Active Cleaning for Video Corpus Annotation[END_REF]. 8,158,517 were made directly by annotators and a total of 28,864,844 was obtained by propagating them using "implies" or "excludes" relations.

Assessments

38 concepts were selected for evaluation out of the 60 ones for which participants were asked to provide results for the main SIN task. Assessments were done partly by NIST (15 concepts) and by Quaero (23 concepts). Assessments were done by visualizing the whole shot for judging whether the target concept was visible or not at any time within the shot. Additionally, all the 10 concept pairs were selected for evaluation of which 5 were annotated by NIST and 5 were annotated by Quaero. A total of 202,707 concept × shots assessments were made by Quaero.

2 Participation to the semantic indexing main task

Introduction

The TRECVid 2013 semantic indexing task is described in the TRECVid 2013 overview paper [START_REF] Smeaton | Evaluation campaigns and TRECVid[END_REF][START_REF] Over | TRECVid 2013 -An Overview of the Goals, Tasks, Data, Evaluation[END_REF]. Automatic assignment of semantic tags representing high-level features or concepts to video segments can be fundamental technology for filtering, categorization, browsing, search, and other video exploitation. New technical issues to be addressed include methods needed/possible as collection size and diversity increase, when the number of features increases, and when features are related by an ontology. The task is defined as follows: "Given the test collection, master shot reference, and concept/feature definitions, return for each feature a list of at most 2000 shot IDs from the test collection ranked according to the possibility of detecting the feature." 60 concepts have been selected for the TRECVid 2013 semantic indexing task. Annotations on the development part of the collections were provided in the context of the collaborative annotation and by Quaero.

As last year, our system uses a six-stages processing pipelines for computing scores for the likelihood of a video shot to contain a target concept. These scores are then used for producing a ranked list of images or shots that are the most likely to contain the target concept.

The pipeline is composed of the following steps: and motion descriptors have been considered (section 2.2).

2. Descriptor optimization. A post-processing of the descriptors allows to simultaneaously improve their performance and to reduce their size (section 2.3).

3. Classification. Two types of classifiers are used as well as their fusion (section 2.4).

4. Fusion of descriptor variants. We fuse here variations of the same descriptor, e.g. bag of word histograms with different sizes or associated to different image decompositions (section 2.5).

5. Higher-level fusion. We fuse here descriptors of different types, e.g. color, texture, interest points, motion (section 2.6).

6. Re-ranking. We post-process here the scores using the fact that videos statistically have an homogeneous content, at least locally (section 2.7).

Additionally, our system includes a conceptual feedback in which a new descriptors is built using the prediction scores on the 346 target concepts is added to the already available set of 47 audio and visual descriptors (section 2.8). Compared to last year, our system has been improved by the inclusion of new descriptors, an improved desctiptor-classifier joint optimization and an improved scheme for hierarchical late fusion.

Descriptors

A total of 57 audio and visual descriptors have been used. Many of them have been produced by and shared with the IRIM consortium and two of them were provided by Xerox (XRCE). These include variants of a same descriptors (e.g. same methods with different histogram size or image decomposition). These descriptors do not cover all types and variants but they include a significant number of different approaches including state of the art ones and more exploratory ones. They are described and evaluated in the IRIM consortium paper [START_REF] Ballas | IRIM at TRECVid 2013: Semantic Indexing and Multimedia Instance Search[END_REF]. They include color histogram, Gabor transform, quaternionic wavelets, a variety of interest points descriptors (SIFT, color SIFT, SURF), local edge patterns, saliency moments, percepts, and spectral profiles for audio description. Many of them rely on a bag of words approach.

Descriptor optimization

The descriptor optimization consists of two steps: power transformation and principal component analysis (PCA). The optimization of the value of the α coefficient is optimized by two-fold cross-validation within the development set. It is done in practice only using the LIG KNNB classifier (see section 2.4) since it is much faster when a large number of concepts (346 here) has to be considered and since it involves a large number of combinations to be evaluated. Trials with a restricted number of varied descriptors indicated that the optimal values for the kNN based classifier are close to the ones for the multi-SVM based one. Also, the overall performance is not very sensitive to the precise values for this hyper-parameter.

Principal component analysis

The goal of PCA reduction is both to reduce the size (number of dimensions) of the descriptors and to improve performance by removing noisy components.

The number of components kept in the PCA reduction is also optimized by two-fold cross-validation within the development set using the LIG KNNB classifier. Also, the overall performance is not very sensitive to the precise values for this number.

Second power transformation

A second power transformation can be applied after PCA dimendionality reduction/ It has an affect which is similar to a post-PCA whitening but is has been proven to be more efficient and easy to tune. The optimal value of α 2 can be optimized by cross-validation and is often close to 0.7 [START_REF] Safadi | Descriptor Optimization for Multimedia Indexing and Retrieval[END_REF].

Classification

The LIG participant ran two types of classifiers on the contributed descriptors as well as their combination.

LIG KNNB:

The first classifier is kNN-based. It is directly designed for simultaneously classifying multiple concepts with a single nearest neighbor search. A score is computed for each concept and each test sample as a linear combinations of 1's for positive training samples and of 0's for negative training samples with weights chosen as a decreasing function of the distance between the test sample and the reference sample. As the nearest neighbor search is done only once for all concepts, this classifier is quite fast for the classification of a large number of concepts. It is generally less good than the SVM-based one but it is much faster.

LIG MSVM:

The second one is based on a multiple learner approach with SVMs. The multiple learner approach is well suited for the imbalanced data set problem [START_REF] Safadi | Evaluations of multi-learners approaches for concepts indexing in video documents[END_REF], which is the typical case in the TRECVid SIN task in which the ration between the numbers of negative and positive training sample is generally higher than 100:1.

LIG BUSEB: Fusion between the two available classifiers. The fusion is simply done by a MAP weighted average of the scores produced by the two classifiers. Their output is naturally (or by construction) normalized in the the [0:1] range. kNN computation is done using the KNNLSB package [START_REF] Quénot | KNNLSB: K Nearest Neighbors Linear Scan Baseline[END_REF]. Even though the LIG MSVM classifier is often significantly better than the LIG KNNB one, the fusion is most often even better, probably because they are very different in term of information type capture. The MAP values used for the weighting are obtained by a two-fold crossvalidation within the development set.

Performance improvement by fusion of descriptor variants and classifier variants

In a previous work, LIG introduced and evaluated the fusion of descriptor variants for improving the performance of concept classification. We previously tested it in the case of color histograms in which we could change the number of bins, the color space used, and the fuzziness of bin boundaries. We found that each of these parameters had an optimal value when the others are fixed and that there is also an optimal combination of them which correspond to the best classification that can be reached by a given classifier (kNN was used here) using a single descriptor of this type. We also tried late fusion of several variants of non-optimal such descriptors and found that most combinations of non-optimal descriptors have a performance which is consistently better than the individual performance of the best descriptor alone. This was the case even with a very simple fusion strategy like taking the average of the probability scores. This was also the case for hierarchical late fusion. In the considered case, this was true when fusing consecutively according to the number of bins, to the color space and to the bin fuzziness. Moreover, this was true even if some variant performed less well than others. This is particularly interesting because descriptor fusion is known to work well when descriptors capture different aspects of multimedia content (e.g. color and texture) but, here, an improvement is obtained using many variants of a single descriptor.

That may be partly due to the fact that the combination of many variant reduces the noise. The gain is less than when different descriptor types are used but it is still significant.

We have then generalized the use of the fusion of descriptor variants and we evaluated it on other descriptors and on TRECVid 2010. We made the evaluation on descriptors produced by the ETIS partner of the IRIM group. ETIS has provided 3 × 6 variants of two different descriptors (see the previous section). Both these descriptors are histogram-based. They are computed with four different number of bins: 64, 128, 192, 256, 512 and 1024; and with three image decomposition: 1x1 (full image), 1x3 (three vertical stripes) and 2x2 (2 by 2 blocks). Hierarchical fusion is done according to three levels: number of bins, "pyramidal" image decomposition and descriptor type.

We have evaluated the results obtained for fusion within a same descriptor type (fusion levels 1 and 2) and between descriptor types (fusion level 3) [START_REF] Gorisse | IRIM at TRECVid 2010: High Level Feature Extraction and Instance Search[END_REF]. The fusion of the descriptor variants varies from about 5 to 10% for the first level and is of about 4% for the second level. The gain for the second level is relative to the best result for the first level so both gains are cumulated. For the third level, the gain is much higher as this could be expected because, in this case, we fuse results from different information sources. The gain at level 3 is also cumulated with the gain at the lower levels.

Final fusion

Hierarchical fusion with multiple descriptor variants and multiple classifier variants was used and optimized for the semantic indexing task. We made several experiment in order to evaluate the effect of a number of factors. We optimize directly the first levels of the hierarchical fusion using uniform or average-precision weighting. The fusion was made successively on variant of the same descriptors, on variant of classifiers on results from the same descriptors, on different types of descriptors and finally on the selection of groups of descriptors.

Re-ranking

Video retrieval can be done by ranking the samples according to their probability scores that were predicted by classifiers. It is often possible to improve the retrieval performance by re-ranking the samples. Safadi and Quénot in [START_REF] Safadi | Re-ranking by Local Rescoring for Video Indexing and Retrieval[END_REF] propose a re-ranking method that improves the performance of semantic video indexing and retrieval, by re-evaluating the scores of the shots by the homogeneity and the nature of the video they belong to. Compared to previous works, the proposed method provides a framework for the re-ranking via the homogeneous distribution of video shots content in a temporal sequence. The experimental results showed that the proposed re-ranking method was able to improve the system performance by about 18% in average on the TRECVid 2010 semantic indexing task, videos collection with homogeneous contents. For TRECVid 2008, in the case of collections of videos with non-homogeneous contents, the system performance was improved by about 11-13%.

Conceptual feedback

Since the TRECVid SIN 2013 task considers a quite large number (346) of descriptors and since these are also organized according to a hierarchy, one may expect that the detection scores of some concept help to imrpove the detection score of related concepts. We have made a number of attempts to use the explicit implies or excludes provided relations but these were not successful so far, maybe due to a normalization problem between the scores of the different concepts. We tried then an alternative approach using the implicit relations between concepts by creating a vector with the classification scores of all the available concepts [START_REF] Hamadi | Conceptual Feedback for Semantic Multimedia Indexing[END_REF].

We used for that the best hierarchical fusion result available. This vector of scores was then included as a 58 th one in the pool of the 57 already available descriptors and processed in the same way as the others, including the power and PCA optimization steps and the fusion of classifier outputs. The found optimal power value was quite different of the ones for the other descriptors (1.800 versus 0.150-0.700) for the other ones. This is probably linked with the way the score normalization is performed. Even though the 2013 evaluation is done on 60 concepts only, as the annotations are available for 346 concepts, we used the full set for the conceptual feedback.

Performances on the semantic indexing task

Four slightly different combinations of hierarchical fusion have been tried. The variations concerned the way the re-ranking was done: it can be locally temporal, globally temporal and or conceptual. Not all combinations could be submitted and the following were selected: 2 shows the performance of the four submitted variants. Our submissions ranked between 5 and 11 in a total of 90 for type A conditions. Our best submission ranked us as the second group out of 26 for the main SIN task. The second iteration of conceptual feedback brings a quite small improvement (from 0.2835 to 0.2848). The runs including uploader information actually [START_REF] Niaz | EU-RECOM at TrecVid 2012: The Light Semantic Indexing Task[END_REF] contained a bug due to our misunderstanding of the data provided by our partner that computed it for us. Then, while we expected an improvement, we obtained a slight degradation, almost negligibe for the 7:1 weighting and still small for the 3:1 weighting.

M A Quaero-2013-
3 Participation to the semantic indexing localization task

Introduction

For this year, TRECVid has started an optional subtask of localization, of the Semantic Indexing task (SIN), is started to challenge systems participating in the SIN task to make their concept detection more precise in time and space. Currently systems are accurate to the level of the shot. In the localization subtask, systems are asked to determine the presence of the concept temporally within the shot, i.e., with respect to a subset of the frames comprised by the shot, and, spatially, for each such frame that contains the concept, to a bounding rectangle. The localization are restricted to ten concepts from those chosen used in the main task of SIN. These concepts are: Airplane, Boat Ship, Bridges, Bus, Chair, Hand, Motorcycle, Telephones, Flags and Quadruped.

Our work for this subtask was inspired by some works on the discriminative color model. A discriminative color model can be used to classify individual pixels of images with regards to whether they may belong to the wanted object. It assigns a Boolean value to each pixel of a query image indicating whether the pixel may belong to an object of the given object class. Thus, the color model yields a binary map of positive and negative pixels.

Color models can be used for pre-filtering images or for creating regions of interest for more sophisticated classification systems. In other words, color models can be useful for large datasets for image classification systems. Also, color models can be used for quickly rejecting unambiguously negative images prior to applying more sophisticated (and thus computationally more expensive) classifiers.

Our work relies to the work done in [START_REF] Ries | Deriving a discriminative color model for a given object class from weakly labeled training data[END_REF], where the authors proposed a method for creating a discriminative color model for a given object class based on color occurrence statistics. However, in contrast to existing approaches, they do not exploit pixel-wise object annotations but only global negative and positive image labels. The authors use their discriminative color model for detecting different brand logos in images and for recognizing different flower classes.

In the following we report our participation at the localisation task in TRECVid.

Approach

The approach is given in figure 2, and it consists of two steps: i) for each concept, we apply the semantic indexing (SIN) system, which aims to choose the shots that contain the target concept; ii) we apply a localisation function on the frames of the top 1000 resulting shots of the SIN system.

Figure 2: The framework of the localization system.

Semantic indexing system

The video semantic indexing system used for the loacalization task is exactly the same as the one used for the semantic indexing main task, see section 2.

Localization algorithm

Since the considered concepts occurs in an unlimited number of different colors and in very different background areas, we choose to compute a discriminative model based on the sift representation instead of color.

Our model is computed from the sift occurrence statistics, which we determine from a set I p of positive images and a set I n of negatives images from the the development data set. The idea is to determine discriminative concept SIFTs, which appears significantly more often in positive images than in negative images. We first compute the interest points for each image and represent these points with the SIFT Harris descriptor.

Then we apply a clustering approach on all the SIFT points, of all the images, in Y different clusters. This results in assigning one specific cluster (y ∈ Y ) to each SIFT point. To determine which SIFT clusters appear more often in positive images as they are likely to indicate the considered concept, we build, for each concept, a Relative Occurrence Frequencies (ROF) of the clusters within the positive and negative images.

For each concept (c ∈ C), let p = |I p | and n = |I n | be the numbers of positive and negatives images, respectively. Then the respective relative occurrence frequencies are given by: ROF p (y) = 1 p p ′ y , and ROF n (y) = n n ′ y , where p ′ y and n ′ y are the absolute numbers of positive and negative images, respectively, in which at least one point belonging to the cluster y is present in the image. However, the set of negative images (i.e. n) is significantly bigger than the set of positive images (i.e. p). We decide to consider only the ROF p for each cluster y. To localize a given concept in an image, we need to determine two points of a rectangle around the concept. Ideally, the good localization is obtained when having SIFT points only on the concept in the image, then it is easy to determine the rectangle which covers these SIFTs. However, in practice the images contain many concepts and the SIFTs appear almost on the whole image. Thus, it is better to filter the SIFT points of each image in a way to have SIFTs only on the considered concept. We propose a method based on this filtering. The method first assigns to each SIFT the ROF of its cluster. Then, we calculate a histogram of the ROF of the image's SIFTs and normalize their locations into s bins, on both X and Y -axis. We define a threshold β to filter the ROF histogram. The idea is to find the two points that cover the SIFTs located on the concept. However, this β is tuned for each concept separately. Since, we don't have yet any evaluation metric for the localization, we have tuned β manually on a small collection. Figure 3(b) illustrates an example of the bounding box and the filtering algorithm we propose. As the plot shows, there are many SIFT points (i.e. the blue points), the rectangular in green presents the localization result of concept Motorcycle by taking all the SIFTs in the image (frame). The blue rectangular defines the localization after the filtering that we propose. As we can see, the filtering can help to precise better the localization of concepts, especially, when the concept appears as the main object in the image. In our work, we have applied the SIFT clustering on Y = 4096 different cluster. We have fixed the number of bins for the histogram of ROF to s = 32.

Experiments

The experiments on the concept localization in videos, were conducted on the TRECVid 2013 collection. This data collection consists of two large sets: the development and the test set. The development set contains 545,923 annotated video shots, while the test set contains 112,677 shots. The evaluations were conducted on the ten semantic concepts, which were provided by NIST and Quaero for the localization subtask and that are included in the list of the concepts for the SIN task. The samples of the development set are annotated as containing the concept or not, however there are no information about the localization of the concept within the shots. This makes the task very difficult since the The tuning parameter β of the localization method was tuned and optimized on the development set, in which we have manually examined the localization in the top 500 retrieval images for each concept. We have choose to fix the β to the value that we think it gives more accurate bounding rectangles around the concepts. Note: since the localization task in TRECVid is a new task, we do not have yet any information about the evaluation metric, which will be used for the evaluation. Thus all the examinations and analysis of the experiments will be based on viewing some of the frames manually by ourselves.

Effectiveness and some results

We have applied the localization algorithm on each of frame of the top 1000 retrieved shots by the SIN system. The SIN system has retrieved coherent number of positive samples for each concept, and the concept may not appear in all the frames of a positive shot. However, the localization algorithm was applied on all the frames and resulted in drawing a rectangle around the region where it expected to contain the concept. Figure 4 shows some examples of the bounding boxes for the learned concepts. By viewing We have observed from the results that the indexing system was quite good for most of the concepts. The localization was quite good for concepts as Airplane, Motorcycle, Hands and Quadruped, which are considered to cover most the shot pixels in the training set. For the other concepts, the localization was not good, since we believe that these concepts do not appear as the main concept in the training set. For example, concept Flags appears always with president, concept Chair appears with people (people sitting on chairs), concept Telephone is normally very small and appears usually with people and other concepts. Some of the concepts are not well detected (the indexing is not very good) but the localization algorithm could find the main concept within the frames. For instance, concept Bus and Boat ship. We submitted only one run based on an unsupervised system. We applied the localization algorithm on each of frame of the top 1000 retrieved shots by the SIN system. The SIN system has retrieved coherent number of positive samples for each concept, and the concept may not appear in all the frames of a positive shot. However, the localization algorithm was applied on all the frames and resulted in drawing a rectangle around the region where it expected to contain the concept. 5 shows the mean iframe fscore obtained over the 10 concepts for the nine runs. Our approach had the best results for the completly unsupervised system with a mean iframe fscore of about 16, 51%. Differently from our unsupervised approach, the first ranked team got the best results for the supervised system with a mean iframe fsore of about 23.36%. They used an approach based on the annotations at the object level. They obtained those annotations by manually adding a bounding box to a small number of image-level labels from the development collection.

Participation to the semantic indexing concept pair task

For the concept pair detection task, we compared a baseline approach in which we simply average the score obtained by the individual concept classifiers with two alternative methods and a combination of all of them. The first alternative method is a direct learning of the concept pair as if it was a single concept. The second one is a two-step ranking.

Baseline: We considered as a baseline system a simple combination of the two single concept detectors.

To detect a pair of concept (c1,c2), we built a single concept detector for c1 and c2, as described above, by considering the annotations by c1 and c2. The new detection score of (c1,c2) is given by : N ewScores

(c1,c2) i = 1 2 (scores c1 i +scores c2 i )
, where scores c1 i and scores c2 i are the detection scores of c1 and c2, respectively. Learning based approach: After generating the annotation per concept pairs, we built concept pairs detectors using MSVM learners for each pair of concepts and each feature. A late fusion of the scores obtained in the first stage is performed in order to improve performance. This is achieved by averaging, for each sample, a number of scores obtained using different descriptors as detailed in 2. We call the results of this fusion in the following late f usion. Two-step ranking We propose a scoring approach which is based on single concepts detectors. The idea consists of detecting a concept pair (c1, c2) based on the results of the detection of the other. So, firstly, we calcule the detection scores of c1 and c2 in the whole dataset to obtain the detection scores scores c1 i , scores c2 i , respectively. Secondly, we rank the samples based on scores c1 i . Finally, we rank the list already ranked in the first stage, by using scores c2 i . We do the same things by interchanging c1 and c2, and we merge the two results obtained. We propose to apply ranking stages by bins of size binSize. Approaches combination We considered the fusion of the "baseline" and "two-steps ranking" as scoring method and the fusion of "baseline", "two-step ranking" and "the learning method" as an hybrid one. We submitted three runs: P A Quaero-2013-P7 7: baseline P A Quaero-2013-P7 6: baseline + two-step ranking P A Quaero-2013-P5 5: baseline + two-step ranking + learning Table 3 shows the performance of the three submitted variants. Our submissions ranked between 6 and 8 in a total of 20 for type A conditions. Our best submission ranked us as the fourth group out of 10 for the concept pair SIN task.

Our submissions were not completely finalized and the results, though quite good, are not fully representative. The single concept scores used used for the baseline and for the two-step ranking came from a hierarchichal fusion procedure which is similar to the one used in our best run in the main task but with not all the finally available descriptors and with less feedback iterations. They were not the finally best available ones. Similarly, the direct bi-concept learning was done in a different and less optimal way so direct comparison is not really meaningful.

It should be noted however that most of the value of the MAP come only from the AP of two concepts, "Chair+George Bush" with an AP of about 0.7 and "Government Leader+Flag" with an AP of about 0.45 while other pair have AP below or well below 0.05 as this can be shown in figure 6. We made post-submission experiments with the final best available individual concept scores (M A Quaero-2013-3 3). We tried four single concept baselines as well as two simple score combination methods: score sum and score product. Results are given in table 4. The sum and product methods has a performance comparable to the performance of the best official submission. At the time of submission of the notebook paper, the computation for learning approach has not been completed and the two-step ranking gave results comparable to the sum combination. From experiments using only a subset of the available descriptors, the learning approach has a lower performance than the simple sum combination.

0

Acknowledgments

This work was partly realized as part of the Quaero Programme funded by OSEO, French State agency for innovation. Results from the IRIM network were also used in these experiments [START_REF] Ballas | IRIM at TRECVid 2013: Semantic Indexing and Multimedia Instance Search[END_REF].

Figure 1 :

 1 Figure 1: Semantic indexing system

1 1 :

 1 combination of M A Quaero-2013-3 3 with uploader information with 3:1 weights; M A Quaero-2013-2 2: combination of M A Quaero-2013-3 3 with uploader information with 7:1 weights; M A Quaero-2013-3 3: manually built hierarchical fusion of a large number (over 100) of jointly optimized descriptor-classifier combinations including two iterations of conceptual feedback combined with temporal re-ranking; M A Quaero-2013-4 4: manually built hierarchical fusion of a large number (over 100) of jointly optimized descriptor-classifier combinations including a single iterations of conceptual feedback combined with temporal re-ranking.

Figure 3 :

 3 Figure 3: Example of the localization of the concept Motorcycle using ROF. a) is the initial image; b) image with SIFT points, and two bounding rectangles around the concept, the rectangle in green is the base-line and the blue one is the proposed method with β = 0.25.

Figure 4 :

 4 Figure 4: Some results of the localization approach.

Figure 5 :

 5 Figure 5: The mean iframe fscore per run Four teams participated in TRECVid 2013 in the subtask of localization for the Semantic Indexing task (SIN) with nine different runs. The used metric is the iframe fscore, the figure5shows the mean iframe fscore obtained over the 10 concepts for the nine runs. Our approach had the best results for the completly unsupervised system with a mean iframe fscore of about 16, 51%. Differently from our unsupervised approach, the first ranked team got the best results for the supervised system with a mean iframe fsore of about 23.36%. They used an approach based on the annotations at the object level. They obtained those annotations by manually adding a bounding box to a small number of image-level labels from the development collection.

Figure 6 :

 6 Figure 6: Comparaison of the results per concept pair for the different approaches, on TRECVID 2013 test corpus.

Table 1 :

 1 Collection feature

	Characteristics	TRECVid 2010
	#videos	27,964
	Duration (total)	∼800 hours
	# shots	879, 873
	# shots (dev)	545, 923
	# shots (test 2013) 112, 677
	# shots (test 2014) 107, 806
	# shots (test 2015) 113, 467
	(http://www.archive.org/index.php). Table

Table 2

 2

	: InfAP result and rank on the test set for all
	the 38 TRECVid 2013 evaluated concepts
	System/run	MAP rank
	Best submission	0.3211	1
	M A Quaero-2013-3 3 0.2848	5
	M A Quaero-2013-2 2 0.2846	6
	M A Quaero-2013-4 4 0.2835	9
	M A Quaero-2013-1 1 0.2827	11
	Median submission	0.1275	46
	Random submission	0.0009	-

Table

Table 3 :

 3 InfAP result and rank on the test set for all the 10 TRECVid 2013 evaluated concepts pairs

	System/run	MAP rank
	Best submission	0.1616	1
	P A Quaero-2013-P5 5 0.1266	6
	p A Quaero-2013-P6 6 0.1205	7
	P A Quaero-2013-P7 7 0.1205	8
	Median submission	0.1126	10

Table 4 :

 4 InfAP result and rank on the test set for all the 10 TRECVid 2013 evaluated concepts pairs

	System/run	MAP
	Single most frequent	0.1096
	Single least frequent	0.1130
	Single with best AP	0.1222
	Single with worst AP 0.1004
	Score sum	0.1613
	Score product	0.1761
	The authors also wish to thank Florent Perronnin from
	XRCE for providing descriptors based on classification
	scores from classifiers trained on ILSVRC/ImageNet
	data.

http://www.quaero.org


Bahjat Safadi

Georges Quénot

Descriptor optimization for multimedia indexing and retrieval

In this paper, we propose and evaluate a method for optimizing descriptors used for content-based multimedia indexing and retrieval. A large variety of descriptors are commonly used for this purpose. However, the most efficient ones often have characteristics preventing them to be easily used in large scale systems. They may have very high dimensionality (up to tens of thousands dimensions) and/or be suited for a distance costly to compute (e.g. χ 2 ). The proposed method combines a PCA-based dimensionality reduction with pre-and post-PCA non-linear transformations. The resulting transformation is globally optimized. The produced descriptors have a much lower dimensionality while performing at least as well, and often significantly better, with the Euclidean distance than the original high dimensionality descriptors with their optimal distance. The method has been validated and evaluated for a variety of descriptors using TRECVid 2010 semantic indexing task data. It has then be applied at large scale for the TRECVid 2012 semantic indexing task on tens of descriptors of various types and with initial dimensionalities from 15 up to 32,768. The same transformation can be used also for multimedia retrieval in the context of query by example and/or relevance feedback.

I. INTRODUCTION

In multimedia indexing, a considerable research effort is directed towards the development of efficient, fast and robust indexing and retrieval systems. There are still some major challenges that need to be tackled to increase the retrieval performance of the indexing system, especially when the datasets are of large-scale. One possibility of increasing the system's performance is to carefully examine the feature normalization techniques, which have the potential to greatly decrease the error rate of the classification, and thus increase the indexing performance. However, it has been so far neglected in many research papers on multimedia indexing. In general, only a few words are devoted to the used normalization technique, even though feature normalization is a crucial step for the multimedia indexing systems.

In general, for video indexing, the Chi-square (χ 2 ) distance is considered to be more suitable than the Euclidean distance for comparing histogram-based visual descriptors like bag of words or BoW [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF]. SVM with RBF kernels can be used with both types of distance, Euclidean or χ 2 . However, the χ 2 distance has two inconveniences: it is significantly more costly to compute because of the divisions in its formula and it is not compatible with PCA-based dimensionality reduction. While the Euclidean distance is conserved during the application of the PCA rotation matrix, the χ 2 distance is completely transformed, almost randomly, and might even become undefined, since it is normally computable only between vectors with positive or null components, a property which is not conserved during the application of the PCA rotation matrix.

In this paper, we investigate a simple descriptor component transformation whose goal is to make the Euclidean distance closer to the χ 2 distance. After this transformation, the Euclidean distance is expected to be as suited as the χ 2 distance for comparing histogram-based image descriptors and a SVM with a Euclidean distance-based RBF kernel is expected to be as suited as a SVM with a χ 2 distance-based RBF kernel for image classification using histogram-based image descriptors. This transformation permits a reduction of the classification time both by using a distance much simpler to compute and by being able to perform a PCA-based dimensionality reduction. We compare the classification performance on TRECVid 2010 using the multi-SVM with RBF kernels [START_REF] Safadi | Active learning with multiple classifiers for multimedia indexing[END_REF] with either the χ 2 or the Euclidean distance. The comparison is complicated because other and complementary normalizations can be performed either at the level of the descriptor vector (e.g. unit length normalization using either a L 1 or L 2 metric) or at the level of the descriptor components (e.g. min max or standard deviation normalization) or a combination of several of them. Furthermore, we present an empirical evaluation of several feature normalization techniques, namely: unit length normalization (L 1 and L 2 ), min max normalization, zeromean and unit-variance normalization (σ norm) and the power transformation. These normalization techniques are applied to several video descriptors and evaluated on the semantic indexing task of the TRECVid 2010 collection.

Another objective, of this paper, is to show that after an appropriate power transformation, the Euclidean distance becomes as effective as the χ 2 distance for image classification using SVMs with RBF kernels. Moreover, PCA-based dimensionality reduction permits a further efficiency while still being effective as well. Finally, post-PCA power transformation are also evaluated and showed to bring a further performance improvement.

II. RELATED WORK

A. Descriptor normalization methods

The main goal of descriptor or feature normalization, is to independently normalize the feature components, in such a way that their values lie within a similar range (e.g. [0, 1] range). The normalization is often done by either using the component values of each vector independently (e.g. the L 1 and L 2 normalization), or by normalizing the vectors using their bin values (e.g. min max normalization). However, other normalization techniques work directly on the values independently, and it does not consider any of the other related values (e.g. power transformation).

Let X be the set of n feature vectors of d-dimensions (components) to be normalized. In the following, we consider five techniques for feature normalization or transformation which are widely used for image and video representation. If we consider X = (x ij ) as a d × n matrix of which columns are the descriptor vectors and rows correspond to vector components, the first two operate on columns independently, the next two operates on rows independently, and the last one operates on elements independently. L 1 or L 2 unit length normalization: These two normalization methods scale independently the components for each vector so that the vector length becomes 1 considering either the L 1 or L 2 metric. The L 1 and L 2 normalization methods are widely used to normalize the feature vectors based on histograms including bag of words (BoW) [START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF], [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF].

Min max normalization: This function aims to scale the values for each feature bin (in a low-level description), so that they all fall in the range of Lower to Upper bounds (l, u). This normalization is used for instance in libsvm [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] with l = 0 and u = 1.

Zero-mean and unit-variance normalization (σ norm):

The feature values are normalized by subtracting the mean value µ i for each feature bin and by dividing the result by the variance σ i of the feature bin.

Power transformation The goal of the power transformation is to normalize the distributions of the values, especially in the case of histogram components. It simply consists of applying an x ← sign(x) × |x| α , transformation on all components individually. The power transformation was applied by [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], in which the authors applied the power only on the Fisher kernel descriptor. They empirically observed that this step consistently improves the quality of the representation. They gave several complementary interpretations that justify this transform. First, it reduces the influence of bursty visual elements, which were shown to corrupt the image similarity in [START_REF] Jégou | On the burstiness of visual elements[END_REF]. Second, assuming the compound Poisson distribution as a good generative model of Fisher Vectors, the power transformation can be interpreted as a variance stabilizing transform, which corrects the dependence between the variance and the mean. The authors have applied the power transformation with α = 0.5. However, the authors used only one descriptor to justify their conclusions and they did not show the impact of the power with different values of α. In the following, we will study the impact of the α parameter with the power transformation on different descriptors. Another interpretation of the power normalization benefit is that power transformation with α values smaller than 1 increases the contrast for low absolute values of the vector components. This can be seen as similar to a gamma transformation on image intensity to better show the details in dark regions of the images.

B. PCA-based dimensionality reduction

Principal Component Analysis (PCA) [START_REF] Bishop | Pattern Recognition and Machine Learning (Information Science and Statistics)[END_REF] is based on a Singular Value Decomposition (SVD) of the X matrix as:

X = U ΣV T
where, U is the d × m matrix of eigenvectors of XX T ; Σ is the m × m diagonal matrix containing the square root of the eigenvalues of XX T ; V is the n × m matrix of eigenvectors of X T X; m is the rank of XX T and X T X; it can also be taken as equal to d by padding the diagonal of Σ with zeros (if d ≤ n).

In this representation, the diagonal entries in Σ are the singular values and they are normally ordered with the largest singular value (largest eigenvalue) first. Dimension reduction is achieved by dropping all but the first k of these singular values. This gives an approximation of the original matrix as:

X ′ = U ′ Σ ′ V ′T
Where U ′ , Σ ′ and V ′ are truncated versions of U , Σ and V where only k rows and/or columns out of m were kept.

As eigenvectors are orthonormal, the Euclidean distances between the columns of X and between the same columns of Y = XV = U Σ are identical. This is the same for the Euclidean distances between the columns of X ′ and between the same columns of Y ′ = X ′ V ′ = U ′ Σ ′ . As X ′ is an approximation of X, the Euclidean distances between the columns of X are approximation of the Euclidean distances between the same columns of Y ′ . Y ′ is also the same as Y in which only the k first rows are kept. The rows in the Y matrix correspond to the principal axes of the covariance matrix sorted in decreasing variance values. Dropping the last components usually does not loose much information (the last ones may be null or very small if many original components are highly correlated); it may even be beneficial since the information associated to small variance axes is generally quite noisy. In practice, it is observed that dropping the last components, an often a large proportion of them, increases the overall system performance both for indexing (classification) or retrieval (query by example or relevance feedback) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF].

There is an optimal number of components to be kept which can be determined by cross-validation within a development collection. In practice also, the mean of the column vectors of X is subtracted to all the columns before applying the PCA; subtraction the mean also does not change the Euclidean distance between column vectors.

C. Post-PCA transformations

A second normalization or transformation can also be applied after the PCA. This includes all the five previously mentioned plus another one called "whitening". L 1 and L 2 unit length can be applied to rescale the vectors and min max and σ norm can be applied to rescale the components. Post-PCA whitening [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF] consists in dividing each component by its variance and is equivalent as such as a σ norm. It also consist in taking Y = XV Σ -1 = U from which Y ′ can still be obtained by dropping components. Whitening is also equivalent to replacing the Euclidean distance between the samples by the Mahalanobis distance [START_REF] Mahalanobis | On the generalised distance in statistics[END_REF]. As Mahalanobis distance is known to become noisy as low variance components are highly scaled, an improved version of the whitening can be obtained by enforcing a minimum ratio B between the first and following variances, thereby bounding the scaling of small variance components [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF]. Also, some intermediate state between the Euclidean and the (improved) Mahalanobis distances can be considered, for instance by dividing by σ β i with 0 ≤ β ≤ 1 with β controlling the "strength" of the whitening.

III. PROPOSED METHOD

The proposed method for descriptor optimization is a combination of a PCA-based dimensionality reduction combined with pre-PCA and post-PCA power transformations. Though the PCA and the non-linear pre-and post-transformations have been used separately before, their specific combination and joint optimization as proposed here have not been tried before.

The main goal of the first power transformation is to transform a descriptor suited for a non-Euclidean distance (typically χ 2 for histogram / BoW-based descriptors) into a descriptor suited for an Euclidean distance with a similar or improved performance. The α 1 exponent in the first power transformation is optimized by cross-validation for obtaining the best possible performance with the Euclidean distance. The dimensionality reduction is also made by optimizing by crossvalidation the k value for obtaining the best performance or the best dimensionality reduction -performance loss compromise.

For the post-PCA transformation, we propose to use a second power transformation rather than whitening. Both have the same effect of increasing small values relatively to large values, and thus preventing components with high amplitude from dominating and masking those with low amplitude, but the whitening does it based on the overall variance of a given component, while the power transformation does it on any element, regardless of it belongs to a small variance component or not. The power transformation will have effect within the values of a given small variance component, while the whitening will act globally on all of them, regardless of whether they are small or very small. As these transformations are made sequentially, it is possible to optimize the corresponding parameters either sequentially or globally. Optimizing them jointly is more costly but it may lead to a better global performance.

IV. EXPERIMENTAL RESULTS

The experiments on the normalization method of video description were conducted on the TRECVid 2010 collection. This data collection consists of two large sets: the development and the test set. The development set consists of 119,685 shots of 3,173 videos with average of 37 shots per video, and the test set consists of 146,788 shots of 8,467 videos with average of 17 shots per video.

A. Video descriptors

We have used several descriptors of different types and sizes, which have been produced and shared by various partners of the IRIM project of GDR-ISIS [START_REF] Gorisse | IRIM at TRECVID 2010: High Level Feature Extraction and Instance Search[END_REF]. Most of the selected descriptors are based on the color histograms or on the bag of words approaches. However, we choose to compare the methods also with different types of descriptors, such as those based on Gabor filter and audio. In practice, we have used 12 descriptors that indicates in table I. Here we detail the used descriptors:

• global labm1x3x192 and global qwm1x3x192: concatenated histogram features [START_REF] Gorisse | Salsas: Sub-linear active learning strategy with approximate k-nn search[END_REF], where: "lab" refers to the use of CIE L*a*b* colors, and "qw" to the use of the quaternionic wavelets (3 scales and 3 orientations). The histogram is calculated for 3 vertical parts, and the dictionary size is 192. Both descriptors have 576 dimensions. • sm462: the Saliency Moments (SM) feature [START_REF] Redi | Saliency moments for image categorization[END_REF],

is a holistic descriptor that embeds locally-parsed information, namely the shape of the salient region, in a holistic representation of the scene, structurally similar to the work presented in [START_REF] Oliva | Modeling the shape of the scene: A holistic representation of the spatial envelope[END_REF]. The resulting signature vector is a 462-dimensional descriptor.

B. Parameter optimization

For the evaluation of each normalization method, we use a multi-learner approach based SVM with RBF kernel (MSVM) as a classifier [START_REF] Safadi | Active learning with multiple classifiers for multimedia indexing[END_REF]. The parameters to be optimized are: the hyper-parameters if the classifier (γ) and the α parameter of the power transformations. The optimization is done by the cross-validation on the development set of TRECVid 2010, in which we split the dataset into two sets: the training and validation sets. In the following, we present the optimization process of these two parameters.

C. Evaluation of baseline normalization methods

The two vector normalization methods (L 1 and L 2 ) and the two component normalization methods (min max and σ norm) can be evaluated separately or as combined, one of each type in two possible orders.

Tables I and II show the system performance on the development set of TRECVid 2010, respectively with the Euclidean and χ 2 distance, using the four baseline normalization methods and some combinations of them (other were tried but appeared less efficient). The results obtained after normalization are compared with the result when the baseline method is used with the both distances, with no normalization at all. As we can see in these tables, the system performance varies significantly with the different normalizations. For the L 1 , L 2 , σ norm and min max normalization, the performance is in most cases closer to the baseline method, and the best normalization among them is not stable across the descriptors. The χ 2 distance is more efficient than the Euclidean one with the best baseline normalizations for the histogram-based descriptors (last eight) but does not make a significant difference for the non-histogram-based ones (first four). Other non-linear transformations, e.g. x ← log(1 + αx) were also considered but none made a significant difference (not shown) probably because the difference would involve a second order effect that cannot be reliably learnt.

D. Evaluation of the power transformation

The power transformation is evaluated in conjunction with the best baseline combination for each descriptor. Results of the α optimization are given in figure 1, for the two considered distances: Euclidean is presented in subfigure 1(a) and χ 2 in 1(b). Each curve in the plots refers to the system performance using one descriptor. As we can see, the α parameter has different values for each descriptor, with both distances. Since we believe that the only difference in the results for each descriptor and the used distance is the value of α parameter, this shows the importance of choosing the best value of α. For instance, with the Euclidean distance the h3d64 descriptor has the best performance with α = 0.3, the dense sift k512 descriptor has the highest performance with α = 0.4. Interestingly, the optimal alpha values for the χ 2 distance are approximately twice those for the Euclidean one. The optimal values for the Euclidean distance are often close to 0.5, which is a commonly used value, but not always. Detailed results per descriptor are given in the next section on the test set when parameter tuning is done by cross-validation in the development set.

E. Evaluation PCA dimensionality reduction

Figure 2 shows the system performance (MAP) obtained by applying the power transformation followed by PCA dimension reduction, with all the considered descriptors. For those with a small dimensionality, the use of the PCA is not that important. The main objective is to show the performance when using a PCA-based dimensionality reduction on high dimensionality descriptors. We have tuned the k number of PCA (i.e. number of important components) on each of the considered descriptors, using fractions from 0.1 to 1 of the original dimensions. As we can see in the figure 2, the number of the important components, varies for each of the descriptors. For long descriptors, we have fixed the k after PCA to be the value of the first fraction that has a higher performance or closer to the performance of the original dimension. For instance, the chosen k-components for the best descriptor (i.e. dense sift k512) is 0.4 × 512 = 204.

F. Evaluation of the power transformation with PCA dimensionality reduction and post-PCA transformation

While the previous results were shown for the analysis of the relevant parameter or parameter combinations within the development set, we summarize here the global results for the proposed method on the test set.

We have evaluated the different combined transformation methods on the TRECVid 2010 test set after having optimized all the relevant parameters by cross-validation for each descriptor and testing condition separately. The testing conditions included: baseline (best combination of baseline normalization); the same with pre-PCA power transformation; the previous one with PCA-based dimensionality reduction; and the previous with either post-PCA power transformation or post-PCA whitening. Results are presented for both the Euclidean and χ 2 distances for the first two and only for the Euclidean distance after PCA (since χ 2 distance in meaningless after PCA). Depending upon the testing conditions, the following hyper-parameters were optimized: α 1 the pre-PCA power transformation exponent; k the optimal number of component to keep after PCA; α 2 the post-PCA power transformation exponent; and (B, β), the optimal whitening parameters. Table III displays the optimal values found for these parameters for each considered descriptor. d is the original dimensionality of the descriptor. σ 2 k /σ 2 d is the fraction of the kept variance in dimensionality reduction.

Results on the 12 considered descriptors are displayed in table IV. They are consistent with those on the development set (not all shown). The table shows the effectiveness of the power-law normalization (+pw) with the both distances. It further shows the effectiveness of the PCA dimensionality reduction with the Euclidean distance and the performance after PCA (+pca) using two normalizations: a second powerlaw and a whitening normalization (+wh). Fusion4 correspond to the performance obtained by the late fusion of the nonhistogram-based descriptors scores; Fusion8 is the same with only histogram-based descriptors; Fusion-all is the same with all the considered descriptors; and Re-ranking is Fusionall after re-ranking using the temporal context. The power transformation performs better than all the other evaluated methods for normalization for all considered descriptors. It is also better with the Euclidean distance than with the χ 2 in most cases. The use of PCA-based dimensionality reduction makes the system faster while preserving or increasing the system performance. A second power transformation improves the performance more than whitening in most cases and globally.

Results are also displayed for a system that makes a simple fusion (average of the classification scores). The fusion was tried separately for non-histogram-based and histogrambased descriptors as well as for all descriptors. The power transformation performs better with the fusion and the global one reaches the score of 0.0707 with PCA and the Euclidean distance and even 0.0807 after re-ranking using the temporal context [START_REF] Safadi | Re-ranking by local re-scoring for video indexing and retrieval[END_REF]. This can be compared to the performance of the best system evaluated at TRECVid 2010 (SIN) that was 0.0900 considering that: more descriptors could have been used; the fusion method was basic; and further post-processing of the fused classification can further improve the performance, for instance using also the conceptual context [START_REF] Hamadi | Two-layers re-ranking approach based on contextual information for visual concepts detection in videos[END_REF].

G. Processing times

All the experiments were done on a machine which has two quad-core processors running at 2.66 GHz and 32 Gbytes of Ram. The execution time depends upon the size of the descriptor. It has been measured for the cumulated training and indexing times for all 30 concepts and 12 considered descriptors in hours. Using always the optimal power transformations, the total execution time is of 201 hours (using eight cores) for the optimal χ 2 distance, it is of 110 hours using the Euclidean distance, and of 53 hours with PCA dimensionality reduction. Meanwhile, as we saw before, the performance is not significantly affected or it is even improved.

H. Application to high-dimensionality descriptors

The proposed method was applied at large scale in the context of TRECVid 2012 semantic indexing task. The collection contains 545,923 video shots, 400,289 for development and 145,634 for test and 346 concepts have to be classified. IRIM produced tens of different descriptors types, many of them with variants (e.g. in the size of the BoW dictionary) resulting into over 100 descriptors, most of them being of very good quality. The dimensionality of these descriptors ranged from 15 up to 32,768. Our approach has been applied to most of them and the observed results on TRECVid 2010 data were confirmed. The optimal k was always found to be much smaller than the original size d and did not exceed 768 even for the d ≥ 10K. This indicates that these very high-dimensional descriptors are highly redundant and have only about a few hundred useful independent components. This dimensionality reduction was again obtained with a simultaneous increase in classification performance. The overall system performance after optimized late fusion combined with the use of temporal and conceptual contexts was of 0.2692 (MAP) for our best submission while the best submitted system at TRECVid SIN 2012 was of 0.3220. The system performance was further increased to 0.3014 when more classification results were finally included.

Though not shown in this paper, additional experiments on other TRECVid and non-TRECVid video collections show that the approach is also valid with other types of video contents and other target concepts. The optimal hyper-parameter values are also quite stable across collections.

V. CONCLUSIONS

We have proposed and evaluated a method for optimizing descriptors used for content-based multimedia indexing and retrieval. This proposed method combines a PCA-based dimensionality reduction with pre-and post-PCA non-linear transformations. The resulting transformation is globally optimized.

The produced descriptors have a much lower dimensionality while performing at least as well, and often significantly better, with the Euclidean distance than the original high dimensionality descriptors with their optimal distance. They also perform better than the same descriptors optimized by classical normalization methods like L 1 or L 2 unit length or per component range (min-max) or variance normalization and simple combinations of them.

The method has been validated and evaluated for a variety of descriptors using TRECVid 2010 semantic indexing task data. It has then be applied at large scale for the TRECVid 2012 semantic indexing task on tens of descriptors of various types and with initial dimensionalities from 15 up to 32,768. The same transformation can be used also for multimedia retrieval in the context of query by example and/or relevance feedback.

Fig. 1 .

 1 Fig. 1. Tuning α parameter of the power transformation on the dev set of TRECVid 2010. The plots show only results with descriptors based on histogram / BoW.

Fig. 2 .

 2 Fig. 2. Evaluating the PCA with Euclidean distance on TRECVid 2010 dev set. The plots show only results with descriptors based on histogram / BoW.

•

  AudioSpectroN b28: Spectral profile in 28 bands on a Mel scale, N: normalized 28 dimensions. • dense sift k512: Bag of SIFT computed with k-bin histograms, thus it has 512 dimensions. • h3d64: normalized RGB Histogram 4 × 4 × 4 64 dimensions. • gab40: normalized Gabor transform, 8 orientations × 5 scales, results in 40 dimensions. • hg104: early fusion of h3d64 and gab40 104 dimensions. • opp sift <method>[ unc] 1000: bag of visual word, opponent SIFT, generated using [15] software. <method> method is related to the way by which SIFT points are selected: har corresponds to a filtering via a Harris-Laplace detector and dense corresponds to a dense sampling; the versions with unc correspond to the same with fuzziness introduced in the histogram computation. We have used four different descriptors of this type. The vocabulary size was of 1000.

TABLE I .

 I MAP VALUES ON THE TRECVID 2010 DEVELOPMENT SET, USING THE BASELINE NORMALIZATION METHODS WITH THE EUCLIDEAN

								DISTANCE.
		Descriptor		Raw	L2	σ norm	Min max	L2-σ norm	σ norm-L2	L2-Min max	Min max-L2
		sm462		0.0095	0.0121	0.0189	0.0115	0.0317	0.0235	0.0152	0.0115
		AudioSpectroN b28		0.0155	0.0156	0.0138	0.0157	0.0148	0.0133	0.0158	0.0154
		vv gab40		0.0265	0.0257	0.0240	0.0182	0.0267	0.0250	0.0195	0.0142
		hg104		0.0368	0.0366	0.0407	0.0278	0.0408	0.0421	0.0323	0.0284
		h3d64		0.0158	0.0159	0.0255	0.0161	0.0227	0.0248	0.0152	0.0160
		global labm1x3x192		0.0346	0.0342	0.0316	0.0355	0.0326	0.0346	0.0348	0.0359
		global qwm1x3x192		0.0312	0.0351	0.0356	0.0373	0.0376	0.0469	0.0362	0.0437
		dense sift k512		0.0572	0.0610	0.0695	0.0636	0.0684	0.0733	0.0676	0.0666
		opp sift har 1000		0.0507	0.0529	0.0485	0.0455	0.0470	0.0472	0.0469	0.0500
		opp sift har unc 1000		0.0539	0.0540	0.0510	0.0516	0.0514	0.0504	0.0513	0.0517
		opp sift dense 1000		0.0441	0.0449	0.0545	0.0494	0.0499	0.0559	0.0511	0.0507
		opp sift dense unc 1000	0.0446	0.0472	0.0617	0.0591	0.0534	0.0626	0.0548	0.0599
	TABLE II.	MAP VALUES ON THE TRECVID 2010 DEVELOPMENT SET, USING THE BASELINE NORMALIZATION METHODS WITH THE χ 2 DISTANCE.
		Descriptor		Raw	L2	σ norm	Min max	L2-σ norm	σ norm-L2	L2-Min max	Min max-L2
		sm462		0.0144	0.0155	0.0243	0.0149	0.0315	0.0219	0.0192	0.0136
		AudioSpectroN b28		0.0030	0.0019	0.0017	0.0096	0.0031	0.0033	0.0150	0.0125
		gab40		0.0247	0.0215	0.0240	0.0186	0.0244	0.0238	0.0192	0.0149
		hg104		0.0378	0.0387	0.0447	0.0350	0.0467	0.0477	0.0363	0.0333
		h3d64		0.0081	0.0124	0.0137	0.0112	0.0326	0.0299	0.0227	0.0254
		global labm1x3x192		0.0424	0.0399	0.0379	0.0435	0.0390	0.0380	0.0423	0.0394
		global qwm1x3x192		0.0504	0.0455	0.0417	0.0430	0.0415	0.0491	0.0439	0.0476
		dense sift k512		0.0784	0.0760	0.0762	0.0841	0.0773	0.0814	0.0820	0.0798
		opp sift har 1000		0.0416	0.0370	0.0367	0.0334	0.0460	0.0448	0.0467	0.0466
		opp sift har unc 1000		0.0485	0.0453	0.0425	0.0432	0.0513	0.0499	0.0511	0.0512
		opp sift dense 1000		0.0623	0.0626	0.0586	0.0572	0.0526	0.0563	0.0537	0.0546
		opp sift dense unc 1000	0.0699	0.0746	0.0688	0.0676	0.0573	0.0652	0.0580	0.0614
		0.08
		0.07
	MAP on 30 concepts	0.01 0.02 0.03 0.04 0.05 0.06	h3d64 labm		opp_sift_har opp_sift_har_unc
		-0.01 0	qwm dense_sift_k512		opp_sift_dense opp_sift_dense_unc
		0	0.2	0.4	0.6		0.8	1
				α-values

TABLE III .

 III OPTIMAL VALUES OF THE PROPOSED NORMALIZATION FOR EACH DESCRIPTOR USING THE EUCLIDEAN DISTANCE.

	Descriptor	d	α1	k (σ 2 k /σ 2 d )	α2	(B, β)
	sm	462	0.200	277 (0.999)	0.6	(4.0, 0.4)
	AudioSpectroN b	28	0.200	28 (1.000)	0.8	(2.5, 0.5)
	gab	40	0.300	40 (1.000)	0.6	(8.0, 0.6)
	hg	104	0.300	104 (1.000)	0.6	(8.0, 0.6)
	h3d	64	0.300	64 (1.000)	0.6	(4.0, 0.6)
	global labm1x3x192	576	0.400	346 (0.980)	0.5	(4.0, 0.7)
	global qwm1x3x192	576	0.500	115 (0.931)	0.7	(2.0, 0.1)
	dense sift k	512	0.400	204 (0.931)	0.8	(2.0, 0.4)
	opp sift har	1000	0.900	400 (0.734)	0.7	(2.0, 0.9)
	opp sift har unc	1000	0.800	500 (0.832)	0.8	(2.0, 0.9)
	opp sift dense	1000	0.400	400 (0.827)	0.8	(2.0, 0.9)
	opp sift dense unc	1000	0.400	400 (0.933)	0.8	(2.5, 0.4)

TABLE IV .

 IV MAP VALUES ON THE TRECVID 2010 TEST SET, USING THE DIFFERENT NORMALIZATION METHODS WITH EUCLIDEAN OR χ 2 DISTANCES.

	Descriptor	Euclidean	χ 2	Euclidean	χ 2	Euclidean	Euclidean	Euclidean
		(baseline)	(baseline)	+pw	+pw	+pw+pca	+pw+pca+pw	+pw+pca+wh
	sm462	0.0104	0.0057	0.0246	0.0178	0.0233	0.0339	0.0273
	AudioSpectroN b28	0.0007	0.0007	0.0011	0.0006	0.0035	0.0036	0.0033
	gab40	0.0106	0.0103	0.0115	0.0104	0.0114	0.0146	0.0144
	hg104	0.0177	0.0214	0.0246	0.0207	0.0240	0.0276	0.0285
	Fusion4	0.0295	0.0307	0.0366	0.0316	0.0403	0.0499	0.0461
	h3d64	0.0053	0.0054	0.0145	0.0046	0.0126	0.0140	0.0127
	global labm1x3x192	0.0126	0.0238	0.0270	0.0288	0.0265	0.0275	0.0255
	global qwm1x3x192	0.0142	0.0213	0.0217	0.0227	0.0214	0.0241	0.0213
	dense sift k512	0.0389	0.0420	0.0418	0.0377	0.0405	0.0456	0.0444
	opp sift har 1000	0.0228	0.0187	0.0223	0.0154	0.0249	0.0254	0.0233
	opp sift har unc 1000	0.0268	0.0284	0.0293	0.0260	0.0313	0.0310	0.0309
	opp sift dense 1000	0.0332	0.0340	0.0375	0.0346	0.0381	0.0399	0.0376
	opp sift dense unc 1000	0.0381	0.0433	0.0433	0.0451	0.0426	0.0457	0.0434
	Fusion8	0.0476	0.0600	0.0624	0.0610	0.0625	0.0669	0.0651
	Fusion-All	0.0523	0.0604	0.0632	0.0618	0.0646	0.0707	0.0688
	Re-ranking	0.0624	0.0674	0.0723	0.0683	0.0731	0.0807	0.0763

ACKNOWLEDGEMENTS

This work was partly realized as part of the Quaero Program funded by OSEO, French State agency for innovation. This work was supported in part by the french project VideoSense ANR-09-CORD-026 of the ANR. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA AL-ADDIN development action with support from CNRS, RE-NATER and several Universities as well as other funding bodies (see https://www.grid5000.fr). The authors wish to thanks the participants of the IRIM (Indexation et Recherche d'Information Multimédia) group of the GDR-ISIS research network from CNRS for providing the descriptors used in these experiments.