Hamid Hrimech
email: hrimech@hotmail.fr

Leila Alem

How 3D Interaction Metaphors Affect User Experience in Collaborative Virtual Environment

In this paper we presents the results of our experimental study which aims to understand the impact of three interaction 3D metaphors (ray casting, GoGo, and virtual hand) on the user experience in a semi-immersive collaborative virtual environment (the Braccetto System). For each session, participants are grouped in twos to reconstruct a puzzle by an assemblage of cubes. The puzzle to reconstruct corresponds to a gradient of colors. We found that there is a significant difference in the user experience by changing the interaction metaphor on the copresence, awareness, involvement, collaborative effort, satisfaction usability, and preference. These findings provide a basis for designing 3D navigation techniques in a CVE.

Introduction

The CVEs technology aims at transforming the Internet networks into 3D navigable and populated spaces which allow the work of collaboration and the social play; however, the use of CVEs creates a mediatization of the collaboration; which means that we pass from a real situation face to face to a situation where we use a virtual world artificially created by computer programs to work together. Unfortunately, quite often this new way of working degrades among users some information necessary to the collaborative process, which includes the following.

(i) The actions of the partner.

(ii) The intentions of the partner.

(iii) The point of view of the partner.

The design of a CVE is regarded today as a real challenge. T h ep r o b l e m sa r en u m e r o u sa n dh a v eat e c h n o l o g i c a l , cognitive, and social character strongly coupled.

In our study, we were focusing on the following research question "What is the impact of 3D interaction metaphors on the user experience in a CVE-oriented task." the understanding of these metaphors will help us to define the criteria, which are to be taken into account when designing a CVE. The next section reviews the literature, Section 2 presents our research approach. In Section 3 we describe the experiment and research hypotheses. Section 4 presents the experimental results which are discussed in Section as well as a conclusion and further work.

Background and Previous Studies

2.1. 3D Interaction. In VR the manipulation of the objects is a very important element in 3D interaction. The quality of the VE depends on the level of interaction between the user and this environment. n3D manipulation is a joint task between the real and the virtual world. In our everyday life we use our hands in order to interact with objects, the hand can be regarded as a perfect peripheral of interaction. It allows to manipulate different types of object in an effective and fast precise way. For example, if we want to carry a book from a point A to a point B, we carry out the following stages: one takes the book → one moves it → one over turns the book according to the desired orientation → onelaysoutthe book.

According to Coquillart et al. [START_REF] Coquillart | Le Trait de la Ralit Virtuelle: Interfaage, Immersion et Interaction en Environnement Virtuel[END_REF], 3D interaction techniques are regarded as a set of methods or scenarios of the use of a hardware interface, allowing the user to carry out a specific task in a virtual environment (VE). According to Mine [START_REF] Mark | ISAAC: a virtual environment tool for the interactive construction of virtual worlds[END_REF], 3D interactions are composed of four virtual behavioral primitives.

(i) Navigation: navigation in VE consists of two components: (1) a motor component of user movement or displacement in space and (2) a cognitive component or what one calls the "wayfinding," a cognitive process which makes it possible to define a way in a virtual environment by building a "cognitive map" of this space [START_REF] Bowman | 3D User Interfaces: Theory and Practice[END_REF].

(ii) Selection: selection of an object among others is considered by [START_REF] Mark | ISAAC: a virtual environment tool for the interactive construction of virtual worlds[END_REF] as the action of pointing an object and validating it.

(iii) Manipulation: manipulation indicates the modification of the state of an object often beforehand selected. This modification breaks up into two subtasks: the translation and rotation. Mine also include in the notion of manipulation, the modification of the object properties such as size, texture, or transparency [START_REF] Mark | ISAAC: a virtual environment tool for the interactive construction of virtual worlds[END_REF]. But these actions are often carried out by using specific menus (widgets).

(iv) System control is a fundamental elementary task with any application enabling the dialogue between the user and the application. Indeed, the goal of the system control is the release of functions and options of the application.

In our work, we use a decomposition similar to that evoked previously, that is, for us the task of manipulation consists of the following.

(i) Selection: the selection consists of distinguishing an object among others (to take the book), the selection can then be presented in the following way:

Selection = pointing + validation. (1)
(ii) Translation: it is the task of change of the position 3D of an object often beforehand being selected (to move the book).

(iii) Rotation: rotation is the task of change of orientation of an object (to turn over the book).

Classification of the 3D Manipulation Techniques.

There are several types of 3D manipulation techniques. These manipulation techniques can be structured by a classification, this classification can be used in order to better include/understand these techniques and also to evaluate them. There are classifications which have been proposed in order to structure the manipulation techniques, one can quote, for example, the classification by metaphor.

According to Fuchs an interaction metaphor is a symbolic system image of an action or a perception used to carry out a precise task in a VE. It is about the transposition of an object or a real concept in the virtual world [START_REF] Coquillart | Le Trait de la Ralit Virtuelle: Interfaage, Immersion et Interaction en Environnement Virtuel[END_REF]. One speaks, for example, about virtual hand metaphor: it is about the transposition of the hand of the user in the virtual environment. For Fuchs it is strongly advised to have recourse to a metaphor of interaction only when it is not possible to exploit a natural interaction directly [START_REF] Coquillart | Le Trait de la Ralit Virtuelle: Interfaage, Immersion et Interaction en Environnement Virtuel[END_REF].

(i) The egocentric metaphors: a metaphor egocentric is a metaphor in which the user acts directly from the interior of the virtual environment, as if it formed part of it. This type of metaphor is generally less appropriate to the manipulation tasks on a large scale, these metaphors are generally used for the manipulation of object with precision. The metaphors egocentric are divided into two families:

(a) virtual hand metaphors (b) virtual pointer metaphors (ii) The exocentric metaphors: they place the user on an external level. Hi interacts on the outside of the virtual environmet. Consequently these metaphors of interaction are particularly usable in the situations where the task is distributed at relatively large distances in the scene, such as the mobile objects. However, the manipulation of object which requires a very precise interaction, such as the deformation of object, will be more difficult with this type of metaphors.

User Performance in VE.

Some user studies have been conducted in an attempt to investigate task performance when people use 3D interaction metaphors in single-user VEs.

Bowmann used testbed to evaluate 3D interaction metaphors like the ray casting, the GoGo, or the image plane, to carry out simple tasks and generic 3D interaction [START_REF] Bowman | Testbed evaluation of virtual environment interaction techniques[END_REF]. There are two tasks: (1) the selection, the user must select an object among a group of objects, the variables intrasubject variables for this task are the distance between the user and the targeted object (3 levels) and the size of object to be selected (2 levels). (2) Manipulation, the user must move and orient the object according to the information contained in a target. The intrasubject variables for this task are the relative size of the object compared to the final position (2 levels), and the degree of freedom, to test the effectiveness of the technique (2Dof, 6Dof). The results of this experiment show that the space skill and the former experiment in VE cannot be used to predict the performances of the users, the selection by occlusion can cause the tiredness of the arms, the male subjects had better performances, also the results show that manipulation by scaling can cause giddiness's after the experiment, the size and the distance do not significantly affect the user performance for pointing techniques.

Poupyrev also carried out an evaluation of the 3D interaction techniques [START_REF] Poupyrev | A framework and testbed for studying manipulation techniques forimmersi v eVR[END_REF]. In this experiment, the user must carry out two tasks: the selection and manipulation in order to evaluate two interaction metaphors: GoGo, and ray casting. The intrasubject variables for the selection are the distance between the user and the targeted object (5 levels), and the size of object to be selected (3 levels). The intrasubject variable for manipulation is the relative size of the object compared to the final position (3 levels). The results of this experiment show that the technique of ray casting gives better results than GoGo.

Empirical Studies in CVE.

Various empirical studies have been done in CVE. The studies we quote are not exhaustive but they make it possible to depict some human factors which influence the interaction in a CVE. These factors are numerous.

The level of realism in CVE has been studied under different perspectives in order to investigate its impacts on social interaction in CVE. Gerhard showed that the degree of presence is higher when using an avatar of a humanoid type compared to an avatar of a shape type or a cartoon-type avatar [START_REF] Gerhard | Continuouspresence in collaborative virtual environments: towards a hybrid avatar-agent model for user representation[END_REF]. Also, the use of a humanoid type generates more immersion, communication, engagement, and awareness. Nevertheless Garau showed that the use of a little anthropomorphic (attribution of human characteristics, or behavior to inanimate objects, animals, or natural phenomena) representation leads to a higher sense of copresence and social presence than the use of a precise anthropomorphism or no anthropomorphic representation [START_REF] Garau | The impact of avatar realism and eye gaze control on perceived quality of communication in a shared immersive virtual environment[END_REF]. Bailenson suggested that visual and behavioral realism must be carefully balanced [START_REF] B A I L E N S O N | The independent and interactive effects of embodied-agent appearance and behavior on self-report, cognitive, and behavioral markers of copresence in immersive virtual environments[END_REF].

In order to investigate small groups dynamics Slater conducted an experiment where groups of three people carried out a collaborative task [START_REF] Slater | Smallgroup behavior in a virtual and real environment: a comparative study[END_REF]. Two participants used a simple screen (computer screen), and a third subject used a head-mounted display (HMD) device. The group performed a collaborative task in a face-to-face condition and in a virtual condition. The results of this study show that the participants with HMD developed leadership behavior. Casanueva study reports that the copresence score was much higher in the high-collaboration VE than in the lowcollaboration VE [START_REF] Casanueva | Small group experiments in collaborative virtual environments[END_REF]. Also, Schroeder study shows that the immersed users naturally adopt dominant roles against users of desktop screens [START_REF] Schroeder | Collaborating in networked immersive spaces: as good as being there together?[END_REF].

Rudlle in his studies [START_REF] Ruddle | Symmetric and asymmetric action integration during cooperative object manipulation in virtual environments[END_REF][START_REF] R U D D L E | V e r b a l communication during cooperative object manipulation[END_REF] looks at the verbal communication of participants in CVE. The authors used the problem of piano movers (maneuvering a large object through a restricted space). The task consisted of moving collaboratively an object from a starting point to an end point. Participants performed this task under two conditions: in a symmetric interaction where only the synchronized actions are allowed and in an asymmetric interaction and in two different configurations of the CVE, an offset CVE and a C-shaped CVE. The study reports that the subjects communicate better in the symmetric interaction condition than in the asymmetric one. It also reports that the speed and the direction of the movements of the hand coordination was poor under the two conditions.

In Hindmarsh et al. study [START_REF] Hindmarsh | Object focused interaction in collaborative virtual environments[END_REF] participants were asked to collaboratively arrange the layout of furniture in a virtual room and agree upon a single design. They were given conflicting priorities in order to encourage debate and discussion. This study shows that participants were able to make reference to objects in the shared environment through pointing gestures. However, problems of fragmentation were observed. These problems were due to a discontinuous visualization during the realization of the task caused by the desktop screen. In order to compensate for the fragmentation of the workspace, users increase their verbal communication using audio. Also Ruddle's et al. [START_REF] Ruddle | Symmetric and asymmetric action integration during cooperative object manipulation in virtual environments[END_REF] study explains that a high quantity of verbal communication is employed to compensate for the fragmentation of the work place on a desktop screen.

Nakanishi compared the movement of users in three different conditions, that is, face-to-face, videoconference, and FreeWalk [START_REF] Nakanishi | Free-Walk: A Three-Dimensional Meeting-Place for Communities[END_REF]. FreeWalk is a desktop meeting environment that provides a 3D community common where everybody can meet and can behave as in real life. Participants are represented as a pyramid of 3D polygons on which individual live video is mapped and can move freely. The results show that the participants have better communication in FreeWalk compared to the other two conditions. Participants also moved better in FreeWalk. Sallnas compared three types of communication (chat, audio, and audio-video) and their effects on presence. Their findings show that the level of social presence and virtual presence is higher with the audio condition. The audio-video users dialogue less than with chat and audio [START_REF] Sallnäs | Effects of communication mode on social presence, virtual presence, and performance in collaborative virtual environments[END_REF].

Most of the precedent studies use evaluation method for a single user in virtual environment. The impact of different avatar appearances on social interaction is among these studies. Most research works done studied design parameters in CVE research. Whereas for executing a specific task in CVE, it is necessary to have exchanges and interactions between the participants and the VE.

Understanding of these metaphors will help us to define the criteria, which are to be taken into account when designing a CVE. To our knowledge, a few studies have been conducted investigating the effectiveness of supporting teamwork between a geographically distributed group for the shard manipulation of objects [START_REF] Roberts | Constructing a gazebo: supporting teamwork in a tightly coupled, distributed task in virtual reality[END_REF][START_REF] Wolff | As t u d yo fe v e n t traffic during the shared manipulation of objects within a collaborative virtual environment[END_REF], the cooperative object manipulation [START_REF] Pinho | Cooperative object manipulation in immersive virtual environments: framework and techniques[END_REF]. But not the effect of 3D interaction metaphors on the user experience in a CVE-oriented task.

In collaborative scenario, a number of issues need to be addressed. The research question arising from these problems is the following:

"What is the impact of 3D interaction metaphors on the user experience in a CVE-oriented task?"

To address this research question, we conducted an experimental study. In this study, we would systematically vary three 3D interaction metaphors (conditions or independent variables), (1) the virtual hand metaphor, (2) the ray casting metaphor, and (3) the GoGo metaphor, and investigate their impact on several dependent variables (collaborative effort, involvement, awareness, copresence, usability, satisfaction, and preference).

Experiment

3.1. Task. In this experiment, participants will be grouped in pairs. We chose the collaborative task "3D puzzle," each pair will be asked to build collaboratively a 3D puzzle. The task requires the participants to work together in three conditions as a team to resolve the puzzle. The participants must build a 3D puzzle (of nine cubes) from an image, the goal of this puzzle is the color alignment of cubes. These cubes are initially positioned on a table in a random way and the participants can select these cubes and position them by using the 3D interaction metaphors on a skeleton in order to build the puzzle, see Figure 1.

This task has been chosen because it engages the participants to work together in order to find the good position of the cubes. That requires communication and a participation between the subjects. Also, this task makes it possible to use the interaction metaphors to select or manipulate the cubes.

This task is used in previous work and is considered a reference task in the studies of collaborative work. It is inspired by the famous task of Rubik's cube puzzle used in previous work. However, we have adapted this task to our research context below the main differences between our task and the task used in the Schroeder study. In the Schroeder study participants manipulate the cubes using avatars [START_REF] Schroeder | Collaborating in networked immersive spaces: as good as being there together?[END_REF], then in our study we have chosen not to use avatars. We use 3D interaction metaphors. Also the task used by Schroeder was to solve a puzzle involving 8 blocks with different colors on different sides and to rearrange the blocks such that each side would display a single color 4 squares of the same colour on each of the six sides [START_REF] Schroeder | Collaborating in networked immersive spaces: as good as being there together?[END_REF], in our work participants must reconstruct an image by an assemblage of 9 cubes. The image to reconstruct corresponds to a gradient of colors.

During the experiment participants could not see their partners directly, but only the interaction metaphors represent the users in the virtual environment. They solely communicated by using the audio connection. We give the participants 15 minutes to solve the puzzle for each condition; if they exceed this time limit, we consider that they failed.

Independent Variables.

In our study, we used three egocentric interaction metaphors. A metaphor of virtual pointer (ray casting) and two virtual hand metaphors type (a classic virtual hand metaphor and a GoGo metaphor). The choice of these metaphors is justified by the fact that they are the metaphors most representative of their family of metaphors, ray casting for the metaphors of virtual pointer and the virtual hand and GoGo for the virtual hand family of the metaphors. Also we decided to choose these three metaphors, they are used in the majority of the applications for the interaction 3D.

The Virtual Hand

Metaphor. The virtual hand moves in the virtual environment based on the movement of the user's physical hand. A virtual object can be selected by touching or by intersection between the virtual hand and the object. The virtual object is then attached to the virtual hand and can then be manipulated. Manipulation of the object is done by direct transcription of the movements of the hand to the object see Figure 2.

The Ray Casting

Metaphor. This metaphor allows the user to select an object by pointing to it with a virtual ray. The pointer direction was defined by the position and orientation of the user hand. Once selected, the virtual object can be manipulated as if it is attached to the ray see Figure 3.

The GoGo

Metaphor. This metaphor gives the user an "elastic" virtual arm, to reach distant virtual objects. Space around the user is divided into two areas centered on him. When its hand evolves/moves in the proximal area, the "traditional" metaphor of virtual hand is used. When the user extends his hand beyond this zone, its movements are amplified and the coefficient of amplification increases when the arm of the user extends, see Figure 4.

Dependent Variables.

According to our study, different dependent variables have been chosen. These variables are detailed here.

The Collaborative Effort.

The collaborative effort is the work which two partners provide to achieve a specific task collaboratively. We use Biocca measure of collaborative effort [START_REF] Biocca | The networked minds measure of social presence: pilot test of the factor structure and concurrent validity[END_REF]. Four statements addressed a perceived sense of collaborative effort, on a Likert scale from 1 to 7. This questionnaire was used by Biocca in an experiment comparing face-to-face interaction with audio-video teleconferencing [START_REF] Biocca | The networked minds measure of social presence: pilot test of the factor structure and concurrent validity[END_REF].

Questionnaire items:

(1) "My partner worked with me to complete the task,"

(2) "I did not help my partner very much?"

(3) "Mypartnerdidnothelpmeverymuch, "

(4) "I worked with my partner to complete the task?" 3.3.2. Awareness/Involvement. In the case or two people being in the same VE, these people generate signs enabling them to have knowledge of the actions and intentions of their partner. This knowledge of the other which results from its interactions with the environment is often indicated in the literature by the "awareness." The awareness makes it possible for two partners to adapt and plan their behaviors according to what they mutually know of each other. According to Hofmann the involvement is a presence facets [START_REF] Hindmarsh | Object focused interaction in collaborative virtual environments[END_REF]. Involvement describes to what extent the participant's attentional resources are directed to the VE. We use Gerhard measure of awareness, four items captured the perceived sense of involvement and three items the awareness on a Likert scale from 1 to 7. This questionnaire was used by Gerhard to investigate the influence of the appearance of avatars on involvement and awareness. Subjects (n = 27) performed a collaborative judgment task [START_REF] Gerhard | Continuouspresence in collaborative virtual environments: towards a hybrid avatar-agent model for user representation[END_REF]. Questionnaire items (involvement):

(1) "Were you involved in communication and the experimental task to the extent that you lost track of time?" (2) "To what extent did events occurring outside the 3D scene distract from your experience in the virtual environment?" (3) "I was an active participant in the task," (4) "I enjoyed the virtual environment experience."

Questionnaire items (awareness):

(1) "I was aware of the actions of other participants,"

(2) "I was immediately aware of the existence of other participants," (3) "How aware were you of the existence of your virtual representation?"

Copresence.

Copresence means the subjective sense of being together or being colocated with another person in a computer-generated environment. Two items address copresence, on a Likert scale from 1 to 7, from the Schroder questionnaire [START_REF] Schroeder | Collaborating in networked immersive spaces: as good as being there together?[END_REF]. Questionnaire items:

(1) "To what extent did you have a sense of being in the same room as your partner?"

(

2) "When you continue to think back on the task, to what e x t e n td oy o uh a v eas e n s et h a ty o ua r et o g e t h e rwi t h your partner in the same room?"

3.3.4. Usability. According to Brooke, usability is a general quality of the appropriateness to a purpose of an artefact [START_REF] Brooke | System Usability Scale[END_REF]. That means the context which a system is employed influences the usability of this system or tool [START_REF] Van Wyk | Usability context analysis for virtual reality training in South African mines[END_REF]. Four items captured the usability of each metaphor, on a scale of 1 to 7. Questionnaire items:

(

1) " I ti se a s yt ou s et h i st e c h n i q u ef o rs e l e c t i o n / manipulation?"

(2) "This interaction technique is flexible for selection/ manipulation?"

(3) "I can recover from mistakes quickly and easily?"

(4) used the interaction technique successfully every time?"

Advances in Human-Computer Interaction 3.3.5. Satisfaction. Three items addressed the satisfaction, on a Likert scale from 1 to 7. Questionnaire items:

(1) "How satisfied are you by using this selection/ manipulation technique?"

(2) "I would recommend this interaction technique to a friend?"

(3) "This interaction technique is fun to use?" 3.3.6. Preference. User's preferences for the three conditions were assessed using four items. Questionnaire items:

(1) "If I had the choice when solving tasks like these I would choose:"

(2) "It was easiest for me to coordinate my actions with my partner when I used:"

(3) "It was easiest for me to predict my partner action when his/her used:" (4) "It was easiest for me to manipulate objects when I used:" 3.4. Experimental Platform. For providing motion capture into our platform, we integrate a hybrid motion tracking system for full six degrees of freedom (6-DOF). This system is the result of the combination of our own 3D tracking system and the Nintendo Wiimote. Our 3D tracking system works with two infrared cameras and reflecting markers.

Our tracking system uses stereoscopy where two cameras are used and equipped with infrared projector. The resulting monochromic images are processed in order to compute the 3D positions of the markers in realtime. The Nintendo Wiimote is a wireless versatile interaction device with several functions. We use this device for capturing orientation in the 3axis.

Our collaborative platform is made of two Braccetto systems (see Figure 5). The platform is composed of a computer Intel Xeon CPU 3.0 GHz, equipped with two 1920 × 1080 resolution LCD screens. The configuration of these two screens can be changed depending on the application.

These two systems are connected by UDP/IP network architecture (see Figure 6). The server is launched initially. It plays a double role. First of all, it must ensure the routing of the data of a transmitting client towards the other clients. Then, it must ensure of the safeguards of the VE state with regular time intervals.

Participants.

We recruited the majority of our participants at the Macquarie University in Sydney, Australia. Participants were recruited via email advertisements and by flyers posted around the campus. The total number of participants was 32 (female participants represent 34.37% of the sample). Altogether, they were 16 sessions (two participants for each trial). The age of these participants was from 18 to 57 years with an average age (M) of 28.68 years and a standard deviation (SD) of 10.73. The necessary conditions for including potential participants were age more than 18 years, a normal or a correct vision, and fluent spoken English. At the end of the trial, each participant received a movie ticket for their participation.

3.6. Procedure. We placed the participants in two rooms that were approximately about thirty meters apart from one another. Before the experiment, participants read the general instructions. Then, they signed a consent form.

Then we trained the participants in how to control the system and explained the use of each metaphor. This took approximately 10 to 15 minutes. They then answered an entry demographics questionnaire online to collect some details about the participants such as gender, age, occupation, proficiency of English language, video game experience, and previous use of Wiimote. We asked the participants in each session to carry out the task collaboratively by using interaction metaphors and to answer after each condition an online questionnaire. For the last condition they also answered an exit questionnaire to choose their preferences. Each trial lasted approximately 45 minutes. At the end of the experiment, the participants were brought together in one room for a debriefing and to ask them about their experiences and impressions of the trial.

Hypotheses.

We conducted a pilot study with 4 trials, 4 weeks before the actual experiment, from the first impression of the users and the questionnaire results, we derived 3 general hypothese.

Hypothesis 1. "The ray casting metaphor increases copresence and awareness more than the virtual hand metaphor."

Hypothesis 2. "The ray casting metaphor leads to higher involvement level than that of the virtual hand." Hypothesis 3. "The GoGo metaphor leads to higher collaborative effort level than that of the virtual hand and ray casting metaphors."

3.8. Results. The results presented in this section have been analyzed using SPSS version 16. We used one-way ANOVA to compare mean differences using both 5% and 1% confidence levels. We used Scheffeposthocc omparisonst o determine which pairs of groups are significantly different. Also, we used a Person's correlation analysis to investigate the relationship between dependent variables.

3.8.1.

Copresence. The average copresence value of the participant using the ray casting metaphor is 4.90, compared to 3.81 of the GoGo metaphor user and 3.75 for the virtual hand metaphor user. The differences between the three groups are significant (F(2, 93) = 3.96, P = 0.022, see Figure 7). Post hoc testing revealed that ray casting and virtual hand are significantly different (P = 0.048) see Table 1(a).

3.8.2. Involvement. The average involvement value of the participant using the ray casting metaphor is 4.96, compared 4.40 of the GoGo metaphor user and 4.15 for the virtual hand metaphor user. The differences between the three groups are significant (F(2, 93) = 4.79, P = 0.01, see Figure 8). Post hoc testing revealed that Ray casting and Virtual hand are significantly different (P = 0.013), see Table 1(b).

Awareness.

The average awareness value of the participant using the ray casting metaphor is 5.73, compared to 5.29 of the GoGo metaphor user and 4.90 for the virtual hand metaphor user. The differences between the three groups are significant (F(2, 93) = 4.50, P = 0.014, see Figure 9). Post hoc testing revealed that Ray casting and virtual hand are significantly different (P = 0.014), see Table 1(c).

Collaborative Effort.

The average collaborative effort value of the participant using the GoGo metaphor is 4.56, compared to 4.19 of the virtual hand metaphor user and 4.02 for the ray casting metaphor user. The differences between the three groups are significant (F(2, 93) = 3.31, P = 0.041, see Figure 10). Post hoc testing revealed that ray casting and GoGo are significantly different (P = 0.046), see Table 1(d). 3.8.5. Satisfaction. The average collaborative effort value of the participant using the GoGo metaphor is 4.76, compared 3.77 of the virtual hand metaphor user and 3.53 for the ray casting metaphor user. The differences between the three groups are significant (F(2, 93) = 3.74, P = 0.027, see Figure 11). Post hoc testing revealed that ray casting and GoGo are significantly different (P = 0.04), see Table 1(e).

3.8.6. Usability. The average collaborative effort value of the participant using the GoGo metaphor is 4.36, compared to 3.87 of the virtual hand metaphor user and 3.34 for the ray casting metaphor user. The differences between the three groups are significant (F(2, 93) = 3.18, P = 0.046, see Figure 12). Post hoc testing revealed that ray casting and GoGo are significantly different (P = 0.046), see Table 1(f).

3.8.7. Preference. The analysis of the results of the questionnaire about relating to the user preference shows that 56.25% of users prefer the GoGo metaphor, 31.25% of the participants preferred the virtual hand metaphor and 12.5% of participants preferred the ray casting metaphor.

3.8.8. Correlation. A Person's correlation analysis was performed between the various variables, in each condition, to check if there were significant relationships between them. We obtained the following results ( see Table 2).

Discussion

The results of this study showed significant differences between the three conditions (virtual hand condition, ray casting condition, and GoGo condition) with respect to the dependent variables chosen (awareness, copresence, collaborative effort, satisfaction, usability, and involvement). The statistical result of this experiment shows that the level of copresence is higher by using the ray casting metaphor compared to the GoGo and virtual hand metaphors, the post hoc test shows a significant difference between ray casting and the virtual hand. This result confirms Hypothesis 1. By analyzing the behavior of subject and during the debriefing meeting we noted a feeling of disappointment in using the virtual hand metaphor by the subjects, because they await a metaphor with more realistic behavior, for example, the fingers animation, closing or the opening of the hand, whereas the hand that used by us does not make it possible to have this type of behavior, it is a simple hand without animation (in our study we used a simple hand without animation). Nowak and Biocca study [START_REF] Nowak | The effect of the agency and thropomorphism of users sense of telepresence, copresece, and social presence in virtual environment[END_REF] shows that a low level of anthropomorphism gives a more important level of copresence and social presence than a higher level of anthropomorphism or null anthropomorphism. In fact, a high level of anthropomorphism induces more hopes which are usually not reached and implies a reduction of the presence. The level of awareness is higher by using the ray casting metaphor (ray casting > GoGo > virtual hand). The post hoc test shows a significant difference between ray casting and the virtual hand, during the realization of the task the metaphor of ray casting makes it possible to better include/understand the actions of the partner, this comprehension facilitates actions of the other taking part and facilitates the process of awareness. That justifies the fact that the level of awareness is higher by using ray casting compared to the virtual hand. Also we found a significant correlation between copresence and awareness. According to Ruth [START_REF] Ruth | Social presence as presentation of self[END_REF], copresence refers to the mutual awareness between participants. This explains the relationship between the copresence and the awareness.

The ray casting metaphor gives a level of involvement higher than the other metaphors (ray casting > GoGo > virtual hand). this confirms Hypothesis 2. The analysis of the results of post hoc raises a difference significant between the ray casting metaphor and the virtual hand metaphor. Also the results show a positive correlation between involvement, and the copresence but also between involvement and the awareness. The copresence, the involvement and the awareness are three concepts which are dependent. This result is logical, indeed these three concepts take part in the psychological acceptance process of the user presence in a CVE.

We noticed that there is a positively significant relationship between usability and satisfaction, usability and satisfaction are higher when using the GoGo condition, compared to the virtual hand and the ray casting conditions. At the debriefing time the majority of the participants announced that the GoGo metaphor is an intuitive metaphor pleasant to use compared to the other metaphors. Indeed the virtual hand metaphor represents the advantage of being simple and natural to use, but the disadvantage raises of this metaphor does not make it possible to select the objects which are far from the user. The ray casting metaphor arises well for the selection of the objects moved away, but rotation is difficult with this metaphor whereas the GoGo metaphor is a metaphor which makes it possible to select and to handle objects which are far from the user in a simple and intuitive way. That justifies the fact of it having a higher level of satisfaction and usability (GoGo > hand virtual > ray casting).

The perception of the collaborative effort is higher with the GoGo metaphor (GoGo > hand virtual > ray casting), this result confirms Hypothesis 3;aswementioned previously this metaphor represents the advantage of being intuitive and pleasant to use, that creates in the participants a feeling of motivation to achieve the task, this motivation results in the collaboration effort which increases by using the GoGo metaphor.

We also find that the collaborative effort and satisfaction and the collaborative effort and the usability are positively correlated. When an interaction metaphor has the advantage Advances in Human-Computer Interaction of being easy to use, and the user is satisfied by the use of the metaphor, that motivates the participants and supports the process of collaboration.

The work completed in this experimental study enabled us to show the importance of the choice of the interaction metaphor. Also thanks to the results of our experiment, we could draw up a list of recommendation to support the 3D interaction in a CVE where the human factor elements are the essential elements in the loop of the design of CVEs.

(i) A direct control of the user actions, to have an interaction metaphor with a direct control makes it more interactive and supports the collaboration in the CVE.

(ii) Use interaction metaphors with a high level of cognitive effort only when necessary. An interaction metaphor with a high cognitive load requires of the user to make considerable mental effort, this effort decreases the collaboration level between the participants for the achievement of the task.

(iii) To have a balance between visual and behavioral realism. We note that if behavioral realism in adequacy with visual realism is not used in the interaction metaphor, it creates in the participants a feeling of disappointment, which influences in a negative way the copresence, the involvement, and the awareness.

(iv) It is important to take into account the ergonomic factors of the interaction metaphor. These factors influence the usability, satisfaction, and the collaborative effort. It is thus necessary to use interaction metaphors that are intuitive and pleasant to use.

We chose three interaction metaphors according to criteria which correspond to the context of our application (the type of the input device and the output display), we think that it would be interesting to evaluate the interaction metaphors in other types of environment like the CAVE or the head-mounted display HMD.

In this work, we did not use any peripherals with haptic feedback, it would be interesting to be interested in the collaborative interaction, by using these peripherals in an EVC on scale 1, like the Spidar [START_REF] Buoguila | Multi-modal haptic device for large-scale virtual environment[END_REF].

Finally the number of users in our experiments was limited to two users whereas situations of collaborative work ask for the intervention of more than two users, it would be interesting to have a collaborative platforms with more than two users, in order to study various problems like the management of the turn taking, the management of the conflicts, and the intentions of the participants.

Conclusion

This paper reports the results of an experiment study conducted to evaluate the impact of 3D interaction metaphors on the user experience in a CVE-oriented task. The results demonstrate that there is a significant difference by changing the interaction metaphor on the copresence, awareness, involvement, collaborative effort, satisfaction usability, and preference. The results confirm our overall working hypothesis, that the choice of 3D interaction metaphor affects significantly user's experience in CVE.

In that way, we hope that such research works will help to improve the design of a new enjoyable and efficient CVE generation.

  (i) How to maintain awareness of who is in the virtual environment, who the other users are, and what are they doing? (ii) How to support nonverbal communication: pointing and gesturing?

Figure 1 :

 1 Figure 1: Virtual environment used.

Figure 2 :

 2 Figure 2: Screenshot of virtual hand metaphor.

Figure 3 :

 3 Figure 3: Screenshot of ray-casting metaphor.

Figure 4 :

 4 Figure 4: Screenshot of virtual GoGo metaphor.

Figure 5 :Figure 6 :

 56 Figure 5: The experimental platform.

Figure 7 :

 7 Figure 7: Mean difference in copresence.

Figure 8 :Figure 9 :

 89 Figure 8: Mean difference in the involvement.

Figure 10 :Figure 11 :

 1011 Figure 10: Mean difference in the collaborative effort.

Table 1 :

 1 Post hoc Comparisons between conditions.

				(a)
	Factor	F	df	P		Post hoc comparisons
	Copresence 3.96 2 0.022 ray casting > virtual hand
				(b)
	Factor	F	df	P		Post hoc comparisons
	Involvement 4.79 2 0.01 ray casting > virtual hand
				(c)
	Factor	F	df	P		Post hoc comparisons
	Awareness 4.50	2	0.014 ray casting > virtual hand
				(d)
	Factor		F	df	P	Post hoc comparisons
	Collaborative effort 3.31 2 0.041 GoGo > ray casting
				(e)
	Factor	F	df	P		Post hoc comparisons
	Satisfaction 3.74	2	0.027	GoGo > ray casting
				(f)
	Factor	F	df	P		Post hoc comparisons
	Usability 3.18	2	0.046		GoGo > ray casting

Table 2 :

 2 Person's correlations between variables (legend: + = (positively) significant on 1% confidence level).

		Copresence	Involvement	Satisfaction	Usability
		+
	Involvement	r = 0.512
		P = 0.001
		++
	Awareness	r = 0.479	r = 0.599
		P = 0.001	P = 0.001
			+
	Satisfaction		r = 0.406
			P = 0.001
			++
	Usability		r = 0.309	r = 0.309
			P = 0.001	P = 0.001
				++
	Collaborative effort			r = 0.343	r = 0.264
				P = 0.001	P = 0.001
		Usability
	5
	4.5
	4
	3.5
	3
	2.5
	2
	1.5
	1
	0.5
	0
	Ray casting	Virtual hand	GoGo
	Usability
	Figure 12: Mean difference in the usability.


Alexis Lechervy
email: alexis.lechervy@ensea.fr

Philippe-Henri Gosselin
email: philippe-henri.gosselin@ensea.fr

Frédéric Precioso
email: precioso@polytech.unice.fr

Boosted Kernel for Image Categorization

Keywords: Image categorization, Kernel Machines, Boosting

Recent machine learning techniques have demonstrated their capability for identifying image categories using image features. Among these techniques, Support Vector Machines (SVM) present the best results, particularly when they are associated with a kernel function. However, nowadays image categorization task is very challenging owing to the sizes of benchmark datasets and the number of categories to be classified. In such a context, lot of effort has to be put in the design of the kernel functions and underlying high-level features.

In this paper, we propose a framework to learn an effective kernel function using the Boosting paradigm to linearly combine weak kernels. We then use a SVM with this kernel to categorize image databases. More specifically, this method create embedding functions to map images in a Hilbert space where they are better classified. Furthermore, our algorithm benefits from boosting process to learn this kernel with a complexity linear with the size of the training set.

Experiments are carried out on popular benchmarks and databases to show the properties and behavior of the proposed method. On the PASCAL VOC2006 database, we compare our method to simple early fusion, and on the Oxford Flowers databases we show that our method outperforms the best MKL techniques of the literature.

Context

Recent years have seen exponential growth of image and multimedia data. Recent machine learning techniques have demonstrated their capability for identifying image categories from image features, like SVM or Boosting. On the one hand, SVM classifiers can be successfully applied to all datasets requiring few training samples, thanks to kernel trick [START_REF] Shawe-Taylor | Kernel methods for Pattern Analysis[END_REF]. However, the performance of classification depends highly on kernel design. On the other hand, the boosting classifiers have good performance [START_REF] Tieu | Boosting image retrieval[END_REF] and they can be tuned more easily by using weak classifiers based on simple features but they require to be trained on large training sets.

Nowadays, the challenges of Image categorization task lie in the size of the test databases and the large number of categories to be considered. The SVM has been originally proposed for binary classification contexts and its extension to multi-class problems is not straight forward. In most cases, one-against-all or one-versus-ones strategies are considered. In other words, multi-class learning is derived to multiple binary classification problems. Several adaptations have been recently proposed for multi-class [START_REF] Vert | Designing a m-svm kernel for protein secondary structure prediction[END_REF][START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF][START_REF] Hazen | Multi-class svm optimization using mce training with application to topic identification[END_REF][START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF][START_REF] Gehler | On feature combination for multiclass object classification[END_REF].

One of the main issues when designing a multi-class method is to achieve both a good inter-class separability while being robust to intra-class variations. It is obvious that not any unique descriptor can have the same discriminative power for all classes. In this paper we propose an intrisically multi-class method to learn a major kernel function as a combination of a set of diverse and complementary minor kernels. There are several ways to learn and combine kernels such as linear combinations [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF][START_REF] Cortes | Two-stage learning kernel algorithms[END_REF], geometric combinations [START_REF] Picard | Learning geometric combinations of gaussian kernels with alternating quasi-newton algorithm[END_REF] or even more general combinations [START_REF] Varma | More generality in efficient multiple kernel learning[END_REF]. When working on the Gram matrix, values of the kernel function itself can be learnt directly [START_REF] Gosselin | Combining visual dictionary, kernelbased similarity and learning strategy for image category retrieval[END_REF] or indirectly with metric learning [START_REF] Davis | Information-theoretic metric learning[END_REF].

In this paper, we propose a method to learn a combination of kernels using the Boosting approach. In the remaining of this section, we present techniques for linear combination of kernels and the involved objects like Alignment and centering. Then, we present the Boosting in this specific context. In Section 2, we present the approach we propose. It differs from other approaches thanks to choice of rank one weak kernels, and more specifically to the design of the learners target used in the Boosting process. In Section 3, we propose a detailed algorithm to implement the learning method. We also show, assuming that the number of categories is negligible against the training set size, that the complexity of this method is linear according to the size of the training set. Finally, in the last section we present comparisons to others methods on image databases.

Learning kernels as linear combinations

We want to address large multi-category databases thus memory and computational complexity will drive many of our choices in this paper. We thus focus on building a major kernel K T as a linear combination of minor kernel functions k t :

K T (x, y) = T t=1 β t k t (x, y), (1)
where x and y are two images and β t ≥ 0. First methods to learn linear combinations are based on a joint optimization of the coefficients in a conic combination of kernel matrices and the coefficients of a discriminative classifier, usually Support Vector Machines [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF]. In this context, combined kernels k t are called base kernels, and they are related to high level features. For instance, in the Multimedia Retrieval community each base kernels correspond to high level features like Bag-of-Words (BoW) [START_REF] Kawanabe | A procedure of adaptive kernel combination with kernel-target alignment for object classification[END_REF].

Recently, the one-stage approach is criticized, since achieving a performance superior to that of the uniform combination of kernels has proven to be surprisingly difficult [START_REF] Cortes | Invited talk: Can learning kernels help performance?[END_REF]. As a result, Cortes et al. propose a two-stage procedure: in the first stage, the method finds the optimal weights to linearly combine the kernels, and in the second stage a SVM learns the optimal hyperplane using the learn kernel [START_REF] Cortes | Two-stage learning kernel algorithms[END_REF]. For these reasons, we also use the two-stage approach in this method proposed in this paper.

In order to use the two-stage approach, a criterion is required to evaluate the kernel combination, like the Kernel Alignment [START_REF] Cristianini | On kernel target alignement[END_REF]:

A(K, K ⋆ ) = K, K ⋆ K K ⋆ ( 2
)
where K is the n × n kernel matrix to evaluate, K ⋆ is the n × n target kernel matrix, K, K ⋆ is the Frobenius inner product, K ⋆ is the Frobenius norm, and n is the number of images in the training set.

Let us note that this criterion evaluates a kernel function K using the values of its Gram matrix K on a specific training set X. In the following we will use bold symbol to represent all values of a function on a training set, for instance K ij = K(x i , x j ) with X = (x i ) i∈ [1,n] .

For example the target kernel matrix K ⋆ can be defined from the n × c ′ matrix L of labels on the training set, K ⋆ = LL ⊤ , with c ′ the number of categories and L ij = 1 if image i is in category j, 0 otherwise.

In order to deal with the unbalance of training data, an interesting approach we will use in this paper is the Centered Kernel Alignment [START_REF] Kawanabe | A procedure of adaptive kernel combination with kernel-target alignment for object classification[END_REF]:

A H (K, K ⋆ ) = K, K ⋆ K K ⋆ (3)
where K denote a centered matrix K:

K = HKH
with H = I-1 n 11 ⊤ , I being the n×n identity matrix and 1 a n×1 vector full of ones. Note that Centered Kernel Alignment invariant to scale:

A H (λK, K ⋆ ) = A H (K, K ⋆ ) and shift: A H (K + λ11 ⊤ , K ⋆ ) = A H (K, K ⋆ ).
1.2 Boosting: a way for combining a large number of kernels First MKL techniques were used to combine high-level kernels. In Multimedia Retrieval context, this approach allows to combine different visual descriptors like colors, textures, keypoints, histogram of gradients, etc. Considering or not their performance when compared to uniform combinations, this approach requires already effective kernels and features. In other words, a lot of research design is required to build the base kernels. Furthermore, it does not really allow the learning of completely new kernel functions.

In order to be able to get a wider range of learning is to considerer a large number of simple base kernels. To illustrate this idea, we can see these simple base kernels as words, and a kernel combination as a sentence or a text. Then, finding a kernel combination can be interpreted as the best description of a database using relevant words. An example of this approach is proposed in [START_REF] Gosselin | Incremental kernel learning for active image retrieval without global dictionaries[END_REF], where each simple base kernels is related to a visual word, and the kernel combination is then related to a visual dictionary. A more mathematical view of this idea is to considerer a family of kernel functions span by a set of "atomic" simple kernel functions.

Before considering these simple kernel functions, we have to considerer the method that will combine them. Actually, usual MKL techniques are not able to process this case because of their computational complexity according to the number of base kernel to combine, which is in most cases quadratic. Furthermore, they are made to combine a finite set of base kernel.

In order to handle this, a strategy we propose to follow in this paper is the Boosting approach [START_REF] Crammer | Kernel design using boosting[END_REF]. In this context, the base kernels used to be called weak kernel and the kernel combination the strong kernel. This approach iteratively selects weak kernel functions k t and their corresponding weight β t during a Boosting round t. There is several way to selects weak kernels. A first one is to consider a finite set of weak kernel candidates, and select the one that maximize some evaluation criterion. A second one is to ask a weak trainer for a relevant weak kernel. The weak trainer is a procedure that creates a new weak kernel that maximize the evaluation criterion. As a result, the possible kernel combinations (or strong kernels) that can be built using a Boosting approach is very large, allowing infinite possibilities in most cases.

Furthermore, the complexity linearly depends on the number T of selected weak kernels, and not on the total number of possible weak kernels. The method is not really sensitive to the setting of this hyperparameter T since, as stated in very recent paper, "Boosting has demonstrated a remarkable (and perhaps unique) resistance to overfitting, although it is affected by the presence of outliers or high levels of noise" [START_REF] Figueiras-Vidal | An exploration of research directions in machine ensemble theory and applications[END_REF].

2 Proposed Approach

Rank one weak kernels

In order to learn our mapping, we propose to considerer rank one weak kernel functions k t (x, y) = f t (x)f t (y), thus leading to the following strong kernel expression:

K T (x, y) = T t=1 β t f t (x)f t (y) (4)
Since they are related to weak kernel functions k t , we call the functions f t weak functions.

Eq. ( 1) becomes equivalent to:

K T (x, y) = F T (x), F T (y) = F T (x) ⊤ F T (y), (5)
where

F T (x) = β 1 2 ⊙ f 1 (x) f 2 (x) . . . f T (x) (6)
with ⊙ the Hadamard product.

As we need to evaluate functions on a training set X ⊂ X , we consider their values on this set using bold symbols. For instance, values of weak functions f t (.) on training set X are denoted f t ∈ R n defined by, with n the size of the training set:

∀x i ∈ X (f t ) i = f t (x i ) (7)
Similarly, values of the strong kernel can be expressed on the training set as:

K T = T t=1 β t f t f ⊤ t = F T F ⊤ T . (8)

Boosting approach

We propose to build the major kernel K T using the Boosting approach. In the literature, there is several definitions and interpretations for Boosting. In this paper, we consider the one that attempts to minimize, or make small, a continuous bound on the classification error (see for instance [START_REF] Friedman | Additive logistic regression: a statistical view of boosting[END_REF] and the references therein). This approach iteratively selects weak functions f t (or equivalently weak kernels k t ):

F t = F t-1 β t f t ⇔ K t = K t-1 + β t k t . (9)
For each boosting round t, we have to find the weak kernel k t or function f t that increases the most the alignment on training set:

{β t , f t } = arg max β>0,f A H (K t-1 + βff ⊤ , K ⋆ ) ( 10
)
We perform this task in two stages. During the first stage, the basic idea is to require from the weak learners to build a set K t of weak kernel candidates k. We expect that the weak learners provide weak kernels which increase the overall alignment. As usually in boosting processes, the alignment increment must be a weak increment, in order to get good generalization properties.

Actually, as we focus on rank one weak kernels k(x, y) = f (x)f (y), we consider weak learners defining weak functions f . Hence, for each boosting round t, we build a set F t of weak function candidates. We also expect that the weak learners not only provide weak functions but also increase the overall alignment. However, as they are learners for functions rather than kernels, we have to define a target function f ⋆ which leads to a (weak) increment of the overall alignment. We will present a solution for this problem in section 2.3, but for now we assume that the weak learners provided us with a set F t of weak function candidates.

Thanks to this set F t , we can run the second stage of resolution of Eq. ( 10). For each weak function candidate f ∈ F t , we compute the weight β ⋆ (f ) maximizing the alignment:

β ⋆ (f ) = arg max β>0 A H (K t-1 + βff ⊤ , K ⋆ ). ( 11
)
We end up with a set of candidate weak functions and their corresponding weights. We then select the pair (function, weight) maximizing the alignment.

An interesting point about Eq. ( 11) is that it can be solved analytically [START_REF] Cortes | Two-stage learning kernel algorithms[END_REF].

Learner targets

Rather than using usual target kernels K ⋆ like LL ⊤ , with L the label matrix, we propose to consider the matrix Q of the QR decomposition of HL. We center the matrix L with H to deal with unbalanced classes [START_REF] Kawanabe | A procedure of adaptive kernel combination with kernel-target alignment for object classification[END_REF]. We only select columns of Q whose corresponding diagonal element in R are not zero (a.k.a. economic QR). Thus Q is a n × c full rank matrix. Our target Gram matrix is then defined as K ⋆ = QQ ⊤ . This choice of kernel target matrix is to overcome the correlation between classes, thanks to the orthogonalization performed by the QR decomposition.

Considering the weak function target f ⋆ , we propose a solution based on equidistance of class centers, in order to deal with multi-class problems. In the case of two-class context, this function can be defined by f ⋆ (x i ) = 1 if the sample x i is in the first class, -1 otherwise. However, in the case of multiclass context, building f ⋆ is not as straightforward since we need to spread each class data around equidistant class centers [START_REF] Vapnick | Estimation of Dependences Based on Empirical Data[END_REF][START_REF] Vert | Designing a m-svm kernel for protein secondary structure prediction[END_REF][START_REF] Gosselin | Feature based approach to semi-supervised similarity learning[END_REF]. The idea of our method is then to move each center to make it equidistant from the others.

We propose to consider the barycenters of (orthonormalized) classes in the space induced by the current combination kernel

K t = F t F ⊤ t : G t = Q ⊤ F t . (12)
Each row of matrix G t is the barycenter of one class in the space induced by K t . If we want equidistant class centers, it is sufficient to get matrix G ⋆ t such that G ⋆ t (G ⋆ t ) ⊤ is proportional to the identity matrix. Based on this idea, we propose to work on the eigenvalues of G t G ⊤ t . More specifically, we propose a strategy that will turn all eigenvalues of G t G ⊤ t to 1, which is equivalent to get the identity matrix, and thus equidistant class centers. This can be achieved by working on the lowest eigenvalue of G t G ⊤ t :

ϕ(G t ) = K ⋆ K t arg min λ {λ ∈ spec(G t G ⊤ t )} (13)
Note that it can be shown that ϕ

(G t ) ∈ [0, 1].
As we proceed iteratively, we can only focus on the new column g ⋆ t to be added to

G ⋆ t = [G t-1 , g ⋆ t ]
. In order to increase ϕ(G ⋆ t ), we propose to consider a vector collinear to the eigenvector v associated to ϕ(G t-1 ):

g ⋆ t = 1 -ϕ(G t-1 )v (14)
The normalization term 1ϕ(G t-1 ) ensures that G t G T t = I. Thanks to this result, we can define the target function f ⋆ t for weak learners. We propose to use

f ⋆ t = arg min f Q ⊤ f -g ⋆ t 2 2 subject to minimizing f 2 . The solution is f ⋆ t = Qg ⋆ t .

Learning semantic features

As F T (.) will be the result of a training on high-level concepts, values f t (x) of function f t on an image x are interpreted as semantic features.

In this article we propose a new supervised method to learn semantic features for image categorization task. Since this new feature space is created using supervised data, i.e. image labels on a training set, we call this space the semantic space. The idea is to learn an explicit embedding of the most relevant features to better represent each image category.

If we denote by X the low-level feature space (color, texture, keypoints...), and S the semantic space, the mapping function F is:

F T : X → S x → F T (x) (15)
Let us note that the function F T is independent from the learning process that created it. Furthermore, it can be used to map any image inside or outside the training set.

In this paper, we consider linear combination of kernels. The semantic space S is thus a Hilbert space, i.e. a vector space with a dot product ., . . More specifically, the dot product of S is the major kernel K T we aim to learn:

K T (x, y) = F T (x), F T (y) (16)
As usual in kernel machines, two formulations represent the same object: the vectorial (or primal) view F T of the semantic S, and the kernel (or dual) view K T .

Algorithm 1. Learn boosted kernels

Input: Low-level feature spaces Xs, Orthogonal n×c label matrix Q, threshold θ, maximum number T of weak functions Compute initial weak functions (f 1 (x) f 2 (x) . . . fc(x)) using Algorithm 2 For rounds t=c+1,...,T:

[1] Compute barycenters matrix G t-1 = Q ⊤ F t-1 [2] Compute eigendecomposition G t-1 G ⊤ t-1 = VΛV ⊤ Sort eigenvalues Λ in ascending order For (λ, v) ∈ Λ × V: [3] Compute g ⋆ = 1 -λ K ⋆ K t-1 v [4] Compute weak target f ⋆ = Qg ⋆
Foreach low-level feature space Xs Run weak learner on training set X ⊂ Xs: Compute fs using weak learner on training set X ⊂ Xs

[5] f = arg min w∈Xs ||Xw -f ⋆ || 2 s.t. ||w|| 2 = 1 [6] Compute β ⋆ (f ) using Eq. (11) [7] If A H (K t-1 + β ⋆ ff ⊤ , K ⋆ ) > A H (K t-1 , K ⋆ ) + θ Update Ft = (F t-1 √ βtft) Proceed to next round t + 1 Endif Endforeach Endfor If no weak kernel increases Alignment T = t Stop Endif Endfor Output: Strong kernel K T (x, y) = F T (x), F T (y)
If A H (fsf ⊤ s , K ⋆ ) > 0 Update Ft = (F t-1 fs) Proceed to next round t + 1 Endif Endforeach Output: Weak functions (f 1 (x) f 2 (x) . . . fc(x))
3 Algorithm

Initialization

At the beginning no class is learnt, therefore we initialize our method accounting for each class at least once. The first c target functions f ⋆ t are then the columns of the matrix, i.e. ∀t ∈ [1, c] f ⋆ t = Q(:, t). These target functions are used independently to train weak learners. Weak learners is a free component of our method that depends on the low-level features. In this paper, we used Least Mean Square (LMS), but other functions can be used. We present this initialization in Algorithm 2. Note that weak functions can be created thanks to each available low-level feature (color, texture, keypoints, ...) but also to different descriptor parameters (feature size, metric, ...). Consequently, the low-level feature spaces X s in Algorithm 2 denotes different features with different parameters. Then, for each class t ∈ [1, c], we select the first one that lead to a positive Alignment.

The result of initialization is c weak functions: F c = f 1 f 2 . . . f c , with c the width of matrix Q.

Boosting rounds

Once the width of F equals the rank of Q, we can start the main learning, as presented in Algorithm 1. For each round t, we first compute the barycenters G t , and the eigendecomposition of G t G ⊤ t . Then, we try each eigenvalue from the smallest to highest. For each eigenvalue λ and its corresponding eigenvector v, we compute a target function f ⋆ (line [START_REF] Crammer | Kernel design using boosting[END_REF] in Algo. 1). Once we have a target function, we run a weak learner in order to get a weak function f for each low-level feature space X s . In this paper, we present this algorithm using LMS (line [START_REF] Cristianini | On kernel target alignement[END_REF] in Algo. 1), but other methods can be used.

Note that, as we are subject to the low-level features, weak learners will not necessarily create weak functions f that match the weak target f ⋆ . For the same reasons, each weak function f will not necessarily leads to a significant increasing of Alignment. As a result, if we do not find a relevant weak function, we proceed to the next low-level feature space X s , until we find one. After several rounds, the algorithm may not find a new weak function to add, and the algorithm stops. Thus, the algorithm can select less weak functions that the number T a user can ask for.

In order to help the creation of a strong kernel with a better generalization capacity, we sort the different low-level feature spaces X s according to their expected generalization capacity. Thus, the algorithm first tries feature spaces with the highest generalization capacity. In case of selection, we obtain the most interesting weak function. This is usually the case during the first rounds, but in the latter ones it is more and more difficult to select a weak function with high generalization capacity.

To get low-level feature spaces with different level of generalization, one can perform a PCA for each low-level feature, and then create new features depending on the number of principal components. We assume that features with fewer components less overfit than features with more components. This example of algorithm based on PCA to arrange features according to their hypothetical overfitting can certainly be improved in many ways.

Linear complexity

In this section, we show that each round t of Algorithm 1 has a computational complexity of O(nt), with n the size of the training sample.

Algorithm starts with the computation of the eigendecomposition of c × c matrix G t G T t (lines [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF] and [START_REF] Cortes | Invited talk: Can learning kernels help performance?[END_REF]). The full eigendecomposition of this matrix has a computational complexity of O(c 3 ), but since we only consider first eigenvalues, a O(c 2 ) algorithm can be used. Concerning the computation of the matrix G t G T t , we proceed iteratively:

G t G T t = G t-1 G T t-1 + β ⋆ t g t g T t
Consequently, the main computations are the computations of g t g T t , which can be performed in two steps. Firstly, we compute g t = Q ⊤ f t , which complexity is O(nc) since f is a n vector and Q a n × c matrix. Secondly, we compute g t g T t which complexity is O(c 2 ). Similarly to g t , f ⋆ = Qg ⋆ is computed in O(nc) operations (line [START_REF] Crammer | Kernel design using boosting[END_REF]). In the remaining of the algorithm, computations mainly depend on variables g ⋆ (line [START_REF] Cortes | Two-stage learning kernel algorithms[END_REF]), β ⋆ (line [START_REF] Davis | Information-theoretic metric learning[END_REF]) and A H (K t-1 + β ⋆ ff ⊤ , K ⋆ ) (line [START_REF] Figueiras-Vidal | An exploration of research directions in machine ensemble theory and applications[END_REF]).

To compute these terms, we only need the following values:

K ⋆ , ff ⊤ , ff ⊤ , K t-1 , ff ⊤ , K ⋆ , K t-1 , K ⋆ and K t-1 .
In fact, we have:

g ⋆ = 1 -λ K ⋆ K t-1 v.
The solution of Eq. ( 11) is

β ⋆ = K t-1 2 k, K ⋆ -K t-1 , k K t-1 , K ⋆ k 2 K t-1 , K ⋆ -K t-1 , k k, K ⋆ .
And by definition, we have:

A H (K t-1 + β ⋆ k, K ⋆ ) = K t-1 + β ⋆ k, K ⋆ K ⋆ K t = K t-1 , K ⋆ + β ⋆ k, K ⋆ K ⋆ K t
Firstly, in our case, K ⋆ = √ c since Q is a full rank n × c orthonormal matrix:

K ⋆ 2 = Tr(K ⋆ K ⋆⊤ ) = Tr(QQ ⊤ QQ ⊤ ) = Tr(QQ ⊤ ) = Tr(Q ⊤ Q) = Tr(Id c ) = c. Secondly, computation of value ff ⊤ is O(n) since ff ⊤ = Hf 2 and Hf = f -1 n 11 ⊤ f = f -mean(f ) ∈ R n .
Thirdly, values ff ⊤ , K ⋆ and ff ⊤ , K t-1 can be computed using the following property:

If v is a n vector and M is a n × c matrix, then vv

⊤ , MM ⊤ = v ⊤ M 2 , v ⊤ M ∈ R n and the computation complexity is O(nc). Consequently computation of value ff ⊤ , K ⋆ = f ⊤ Q 2 is O(nc), and ff ⊤ , K t-1 = (Hf ) ⊤ F t-1
2 is O(nt). Finally for values K t-1 and K t-1 , K ⋆ we propose an iterative formulation, which complexity is also linear using the same properties as previously:

K t 2 = K t-1 2 + ff ⊤ 2 + 2β ⋆ K t-1 , ff ⊤ , and K t , K ⋆ = K t-1 , K ⋆ + β ⋆ ff ⊤ , K ⋆ .
To conclude about the complexity of the proposed algorithm, each round t has a computational complexity of O(c 2 + nc + nt) = O(nt), since c < n and c < t.

Note that we did not considered the complexity of wear learners. This is a free parameter the user of our method have to choose. Depending on the choice of this parameter, one can get very different levels of complexity. In this paper, we use LMS which training complexity is O(nd), with d the dimension of visual features. In order to respect Boosting paradigm, one should choose weak learner, corresponding thus to visual features with low dimensions. Furthermore, in this case the computation of ff ⊤ , K t-1 can be performed in O(dt) operations. Consequently, the complexity of the whole learning process in the following experiments is linear with the size of the training set.

Experiments

In this section, we show the advantages of our method through various experiments. We have carried out two sets of experiments on real data. The first experiments compare our method to a simple feature concatenation method, and the second experiments compare it to MKL techniques proposed in the literature.

Comparison to feature concatenation

In this experiments, we compare our method to a simple method using concatenation of features. We evaluate the performance on Visual Object Challenge We first carried out experiments using histogram visual features based on CIEL ⋆ a ⋆ b ⋆ colors (lab) and textures using quaternionic wavelets filters (qw). Visual descriptors are projected on visual dictionaries of various size (from 16 et 128 visual words) to create different histogram features. Then, for each feature and for each category, we train a linear SVM to classify the test set of the database. The result of these runs are presented in the first rows of Fig. 2. We also present in the ever last row the result using a concatenation of all these features. In the latter case, the mean Average Precision (mAP) is 45.3%.

We also carried out an experiments using the proposed method. The process is almost the same, except that we used the method to combine the histogram features to create an embedding function F T (x) using the supervised data on the train set. This function is then used to create a new feature x ′ = F T (x) for any image x. This can be compared to the concatenation method, which is another way to combine the histogram features. The new feature is then used to train a linear SVM and to classify the test set. As one can see in Fig. 2, we obtain a significant increment of 3% when compared to a concatenation method. Note that we present here result with few visual features, but the method can also be used with a very large number of visual features. In fact, our method will produce better semantic features, or in the worst case the performance will not change. This has to be compared to the concatenation method whose performance can drop if too much visual features are used. Fig. 2 Average Precision (%) on VOC2006 database, Image categorization using linear SVMs and different features. Each column presents results from one of the 10 categories, except for the last one which presents result mean Average Precision. Correspondence between category number and category name can be found in Fig. 4.1. The ever last row present the result using a concatenation of all lab and qw features. The last row presents the result using the proposed method to combine lab and qw features.

Comparison to Multiple Kernel Learning (MKL)

In this section, we compare our method to state-of-the art Multiple Kernel Learning (MKL) techniques. We use the Oxford databases [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF], a usual database in communities to compare kernel combination techniques. In these experiments, we use the χ 2 distance matrices D provided by the authors [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF].

For each distance matrix, we compute a new matrix X = e -µ f D , where µ f is set to be 1 over the mean value of the χ 2 distances over all the training images (like stated in [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF]). Then we use the method based on a PCA to generate many features with different hypothetical generalization capacities (cf section. 3.2).

Our method then produces a new feature thanks to the learned embedding function F T (x), which is further used to train a SVM with a Gaussian ℓ 2 kernel. We conduct the experiments with the same protocol as in [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF], we use the same features, the same data split and the same performance metric (average accuracy).

Flowers 17

Flowers 17 is a database of 17 categories of common flower in England. Each category have 80 flower images. The dataset is made of 3 predefined random splits. Each split is composed of 3 sets: training (40 images per class), valida-tion (20 images per class) and test (20 images per class). We consider the visual features given by the authors of this base1 . These authors provide 7 χ 2 distance matrices to describe different properties of the flowers: colour, shape and texture histogram, HSV histogram, SIFT inside the foreground region, SIFT on the foreground region boundary and Histogram of Oriented Gradients. We run our method with different settings. In section 3.2 we discussed the importance of the granularity of feature for a good generalization. In fact, we build our classifier with features of different granularity. Initially, the coarsest features (i.e in our case the feature with low dimensions) are tried first. If the boosting algorithm fails to find a good kernel from these, then we consider more refined features with more information and detail. In practice, after PCA we keep features of 16, 32, 64, 128, 256, 512 and 1024 dimensions and we start our selection with low dimensions features.

The results of this strategy are reported in Fig. 3. This table presents the classification rate for different maximum values of feature dimensions and rounds T (see Algorithm 1). For example, in the case where T is 300 and the maximum feature dimension 128, the algorithm is allowed to select up to 300 weak kernels using features of dimension 16, 32, 64 or 128. In some cases the algorithm does not select as much weak kernels as requested, for instance with a maximum feature dimension of 16 (first column of results) and with T values of 300, 400 and 500. In those cases, we did not report a result because it is the same as for T = 200 since the algorithm did not select more than 200 weak kernels.

One can also see that results are the same in the first row of results (T = 50). Whatever is the maximum size of low-level feature dimensions, the accuracy is always 78.24%. That means that, during the 50 first rounds of the algorithm, only features of dimension 16 are selected. The same can be observed in the second row of results (T = 100), and we have to wait for T = 200 rounds to see the first selection of features of dimension 32. This behavior is repeated with the increasing of rounds, showing the ability of the method to selected more and more complex features as the number of rounds increases.

We reported results from the literature [START_REF] Mikolajczyk | Augmented kernel matrix vs classifier fusion for object recognition[END_REF] in Fig. 4. Our method outperforms these reference results, and gets lower standard deviation. This standard deviation is computed thanks to the 3 data split predefined by the authors of the dataset.

Flowers 102

Flower 102 database contains 8189 images divided into 102 flowers classes (cf. Method Result MKL [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF] 72.8 MKL [START_REF] Mikolajczyk | Augmented kernel matrix vs classifier fusion for object recognition[END_REF] 73. in 10 images per class (1030 images) while the test set has 6129 images with at least 20 images per class.

Like [START_REF] Nilsback | Automated flower classification over a large number of classes[END_REF] we use four different χ2 distance matrices 2 to describe different properties of the flowers: HSV histogram, SIFT inside the foreground region, SIFT on the foreground region boundary and Histogram of Oriented Gradients.

In Fig. 6., we compare our method with the methods from the literature and mainly to the reference method of the state of the art [START_REF] Mikolajczyk | Augmented kernel matrix vs classifier fusion for object recognition[END_REF]. It can be seen that our method provides a significant gain. Note that, since there is only one single data split in the original benchmark, no standard deviation can be computed. Changing the split process would bias the protocol which also explains why no standard deviation is reported in any other paper considering this benchmark.

Conclusion

This paper presents a new method to learn a kernel function for image categorization in large databases. This method has several advantages in this specific context, both during the training step, where the category models are learnt, and during the categorization step, where images are categorized.

Considering the training step, we follow a two-stage approach. We first learn a kernel function, and then use it to train a SVM classifier for each category. The kernel function is built using a Boosting approach, which allows a combination from a very large number of weak kernels, actually infinite thanks to well-chosen weak learners. Furthermore, we propose an algorithm to perform this learning with a computational complexity linear with the size of the training set. Note that we learn a single kernel function for all categories, using all the labels from the categories, thanks to novel learners target in the Boosting process. This property allows the method to take advantage of any kind of relationship between categories, for instance hierarchy. From the computational point of vue, this is also an interesting property for dealing with current datasets, which number of categories grows more and more.

Considering the categorization step, the method we proposed creates an embedding function that maps any image into a Hilbert space. The categorization of any image is then the evaluation of this single function, followed by the projection on the SVM hyperplanes (one for each category). Since the dimension of the Hilbert space where images are embedded is small, the computations for the projection on hyperplanes is negligible. Most of the computation is then the embedding, that depends on the choice of the weak learners and underlying visual features. However, since we expect from these learners to be weak, a relevant choice is to use simple projection models and low dimension features. For instance, in this paper, we used Least Mean Squares with features from 16 to 1024 dimensions, and only with 128 dimensions we are still close to the best results. As a result, the categorization step using our approach, with a relevant tuning, leads to a fast processing of large databases.

The method we proposed also offers a wide range of new techniques, especially if we consider the weak learners. In this paper, we used a very simple weak learner (LMS). However, many other choices can be done, such as linear learners or k-Nearest-Neighbors... We have evaluated our method on real data. The experiments show that the final centroids are representative of category clusters. We compare our method with recent State-of-the-Art methods considering different types of features. Our method outperforms all other reference methods, thereby showing the relevance of our approach.

We are currently working on a straight forward generalization of our method to collaborative learning. Indeed, the same algorithm can easily target a kernel matrix for collaborative learning context by considering several retrieval session result as initial annotations of the classes.

Algorithm 2 .

 2 Initialization of the proposed algorithm Input: Low-level feature spaces Xs, Orthogonal n × c label matrix Q For t=1,...,c: Compute f ⋆ t = Q(:, t) Foreach low-level feature space Xs

  (VOC) 2006 dataset. This database contains 5304 images provided by Microsoft Research Cambridge and Flickr. The VOC2006 database contains 10 categories, example images are shown in Figure 4.1. Each image can belong to several categories. There are two distinct sets, one for training (2618 images) and one for testing (2686 images) with 9507 annotations (4754 object in train and 4753 object in test).

Fig. 5 )Fig. 5

 55 Fig. 5 Examples of categories from the database Flowers 102

  Categories from PASCAL Visual Object Challenge (VOC) database, 2006. .4 24.6 16.0 9.4 11.2 9.0 8.0 27.2 10.9 14.0 lab32 10.7 8.1 45.7 27.1 34.2 15.9 10.0 9.1 27.0 25.6 22.8 lab6410.0 12.5 47.9 28.5 37.[START_REF] Cristianini | On kernel target alignement[END_REF] 19.1 9.9 16.4 31.7 50.3 26.3 lab128 18.7 24.7 46.6 28.8 34.1 20.0 16.0 16.5 33.2 50.0 28.7 qw16 14.0 46.8 55.5 15.1 7.5 14.6 8.3 21.0 25.6 11.2 22.0 qw32 38.5 52.2 60.2 22.2 7.7 15.9 8.9 36.0 36.9 25.6 30.4 qw64 43.0 53.1 63.4 22.0 14.2 18.8 13.2 43.3 37.5 36.2 34.4 qw128 47.9 57.4 65.6 25.8 14.8 20.3 21.6 45.5 33.2 48.6 37.6 Concatenation 52.1 58.2 72.2 37.4 38.5 27.1 26.7 44.4 39.5 56.1 45.

	1.Bus	2.Bicycle			3.Cat			4.Car			5.Cow
	6.Dog	7.Horse		8.Motobike			9.Person		10.Sheep
	Fig. 1 Feature	1	2	3	4	5	6	7	8	9	10	Mean
	lab16	12.4 9

3 Proposed 52.2 63.1 75.9 43.8 41.6 27.6 27.2 52.7 41.9 56.6 48.3

http://www.robots.ox.ac.uk/~vgg/data/flowers/17/index.html

http://www.robots.ox.ac.uk/~vgg/data/flowers/102/index.html