Characterizing Player's Experience From Physiological Signals Using Fuzzy Decision Trees

Florent Levillain, Joseph Onderi Orero, Maria Rifqi and Bernadette Bouchon-Meunier

Abstract-In the recent years video games have enjoyed a dramatic increase in popularity, the growing market being echoed by a genuine interest in the academic field. With this flourishing technological and theoretical efforts, there is need to develop new evaluative methodologies for acknowledging the various aspects of the player's subjective experience, and especially the emotional aspect. In this study, we addressed the possibility of developing a model for assessing the player's enjoyment (amusement) with respect to challenge in an action game. Our aim was to explore the viability of a generic model for assessing emotional experience during gameplay from physiological signals. In particular, we propose an approach to characterize the player's subjective experience in different psychological levels of enjoyment from physiological signals using fuzzy decision trees.

I. INTRODUCTION

Fun is a crucial component of video games. Video games are purposely designed to elicit positive experiences, where every obstacle standing on the player's path should be an excuse for entertainment. Yet, when it comes to defining the factors determining such an experience, quantifying fun remains a complex task. In the domain of game design, empirical methods still rule the process of making a game enjoyable, and objective and systematic methods are still lagging behind the sheer interest for theoretical approaches in game design. In the recent past, research has focused on machine learning approaches, with the goal of modeling emotional experiences related to gameplay. In this direction, considerable progress has been made in using physiological signals as a source of input [START_REF] Rani | Anxiety-based affective communication for implicit human machine interaction[END_REF], [START_REF] Mandryk | A fuzzy physiological approach for continuously modeling emotion during interaction with play technologies[END_REF], [START_REF] Chanel | Boredom, engagement and anxiety as indicators for adaptation to difficulty in games[END_REF], [START_REF] Yannakakis | Real-time game adaptation for optimizing player satisfaction[END_REF].

However, despite these promising scientific advances, physiological computing still face a number of obstacles [START_REF] Fairclough | Fundamentals of physiological computing[END_REF]. Fundamental issues such as the generality and standardization of the methodologies developed [START_REF] Arroyo-Palacios | Towards a standardization in the use of physiological signals for affective recognition systems[END_REF], are yet to be fully addressed. The approaches tend to be too specific and dependent on the laboratory experiments, making it difficult to compare results and validate their applicability in real-time applications. Indeed, in order to realize the full potential of affective computing, more emphasis should be put in developing generic user models that represent the players [START_REF] Hudlicka | Affective game engines: Motivation and requirements[END_REF]. The aim of this work was to address some of these fundamental challenges.

Florent Levillain is with the Laboratoire Cognitions Humaine et Artificielle (CHART), Université Paris 8, France (email: flevillain@mac.com).

Joseph Onderi Orero, Maria Rifqi and Bernadette Bouchon-Meunier are with the Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie, France (email:{joseph.orero,maria.rifqi, bernadette.bouchon-meunier}@lip6.fr).

First, it is necessary to express in fuzzy terms the mapping of affective markers from physiological data. It can be argued that, changes from one emotional state to the next is gradual rather than abrupt and that we need to take into account the overlapping of class boundaries [START_REF] Goulev | An Investigation into the Use of AffectiveWare in Interactive Computer Applications[END_REF]. Moreover, the physiological data from sensors is itself imperfect, such that it is difficult to express the results in crisp terms [START_REF] Bouchon-Meunier | Aggregation and Fusion of Imperfect Information[END_REF]. Fuzzy set theory based models seem more applicable to represent these continuous transitions, uncertainties and imperfections. As a result, fuzzy set theory based approaches have been proposed with promising prospects to assess player's satisfaction [START_REF] Mandryk | A fuzzy physiological approach for continuously modeling emotion during interaction with play technologies[END_REF], [START_REF] Rani | Anxiety-based affective communication for implicit human machine interaction[END_REF], [START_REF] Yannakakis | Modeling and augmenting game entertainment through challenge and curiosity[END_REF]. Nevertheless there is need to advance further in this direction, especially by exploring methods able to extract relations that define the optimal combination of measures. Despite their many advantages in real-time applications, physiological measurements do not provide a lateral, isomorphic representation of the emotion or intention [START_REF] Fairclough | Fundamentals of physiological computing[END_REF]. Consequently, in this work, we employ fuzzy decision trees to extract psychophysiological relations.

Secondly, to guarantee the viability of the developed models in real-time application, the experimental setup should be as close to normal human situations as possible. In order to ensure a natural sense of immersion in the players, we put some efforts in creating an adequate experimental situation. We recruited our participants with no other incentive than to have fun playing the game. To respect their spontaneous pace, we placed no constraints on the way the game has to be played. We chose a popular game, well known for its smooth control system and its sense of balance and immersion but selected episodes in the game with a clear contrast in terms of difficulty, although each of them was worth playing. Finally, to gather different layers of players'satisfaction, we used two types of questionnaires: one immediately after each sequence, to probe the most recent memories of the feelings elicited by the game; another one, more retrospective, at the end of the session, to promote a comparison between the different sequences.

Overall, our main goal was to distinguish typical physiological signatures associated with various gaming experiences. In order to correlate these physiological measures with subjective evaluations in different psychological levels of enjoyment, we recorded physiological signals with the hope of finding features able to distinguish between the levels of engagement elicited by these sequences.

The rest of the paper is organized as follows: in Section II we outline how to assess player's experiences. In Section III we give justification of machine learning approaches. We then describe the experimental setup in Section IV before 978-1-4244-6297-1/10/$26.00 c 2010 IEEE giving our results in Section V. Finally, we give conclusions and future perspectives in Section VI.

II. HOW TO ASSESS PLAYER EXPERIENCES

A. Objective Measures

Until now, modeling of the player's emotional experience during gameplay has mainly relied on traditional methods through subjective self-reports such as questionnaires, interviews and focus groups. Although these subjective selfreport methods are used virtually in all fields to give a global view of the user experiences on specific aspects of interest, they have limitations. One of them being that they only generate data at the moment the question is asked, and not through a continuous process. Secondly, it is difficult for participants to self report their behaviors during game situations [START_REF] Pagulayan | Usercentered design in games[END_REF]. Since the main goal of video games is to entertain through a continuous renewal of the user's interest, controlling the emergence of certain affective states is crucial in achieving a truly immersive experience. Therefore, in evaluating video games, it would be more appropriate to use more objective measures that can assess continuously the emotional responses in relation to variations of scenarios and tasks at hand in the game. Among a vast range of possible ways to continuously assess a user's emotional responses such as facial gesture or voice recognition through video and audio recording, physiological measures stand out. Although physiological recordings have problems of their own (they produce noisy data, they are not yet fully wearable and require a certain immobility from the user), they grant an access to non conscious and non reportable processes [START_REF] Cacioppo | Psychophysiological science: Interdisciplinary approaches to classic questions about the mind[END_REF] and may to a certain extent be unobtrusively monitored [START_REF] Scheirer | Frustrating the user on purpose: A step toward building an affective computer[END_REF]. Since video games tend to promote a natural sense of immersion, physiological recordings seem appropriate when it comes to measuring how much cognitive effort, or active coping is involved in a particular task. Thus in this work, we focused on the use physiological signals as a more objective measure to continuously assess the players' emotional experience.

B. Modeling the Player's Experience

There is much debate concerning how to conceptualize emotions, whether they must be considered as static, biologically-rooted states [START_REF] Ekman | Autonomic nervous system activity distinguishes among emotions[END_REF] or as dynamical, boundariesfree states [START_REF] Ortony | Whats basic about basic emotions?[END_REF]. The dimensional theory of emotions holds that all emotions can be resumed as coordinates of valence and arousal [START_REF] Lang | The emotion probe studies of motivation and attention[END_REF], [START_REF] Russell | Affect-grid: A singleitem scale of pleasure and arousal[END_REF]. For instance, in the domain of game studies ( [START_REF] Mandryk | A fuzzy physiological approach for continuously modeling emotion during interaction with play technologies[END_REF], [START_REF] Chanel | Valence-arousal evaluation using physiological signals in an emotion recall paradigm[END_REF] and many others), the player's experience is defined as a compound of a certain amount of arousal and a certain degree on a valence scale.

But when trying to model the player's subjective experience, an approach based only on valence and arousal might come short. Specifically, this approach does not take into account the possibility that the player's satisfaction comes from two different sources: (i) the (meta)cognitive assessment of the challenge at stake, reflecting the recognition of the game designer's intentions to manipulate the affective/immersive component of the game, (ii) the affective evaluation of the pleasure gained from experiencing a certain amount of challenge. In other words, a player may recognize the intention of the game to vary the level of excitement, although he may not enjoy such a variation. This is coherent with a dualsystem of evaluation based on distinct anatomical pathways, a cognitive pathway and an emotional pathway [START_REF] Ledoux | The Emotional Brain: The Emotional Underpinnings of Emotional Life[END_REF].

In this respect, considering the player's appraisal of the challenge at stake might be a more promising approach. In this domain, one key approach concerns the theory of flow [START_REF] Csikszentmihalyi | Harper and Row Flow: The psychology of optimal experience[END_REF]. This theory states that in order to elicit positive emotions in the player, one should be certain that the player is maintained in a narrow channel (the flow channel) where he/she is not overcome by difficulty, although at the same time challenge should not fail to engage the player. The limits of the state of flow are thus boredom in the one hand, when the player feels insufficiently engaged, anxiety in the other hand, when challenge exceeds the player's skills. To put it in simple words, a game should be neither too hard nor too easy [START_REF] Fullerton | Game Design Workshop: Designing, Prototyping, and Playtesting Games[END_REF], which is represented by a recent tendency in game design to address several levels of skills by promoting multilayered games. In order to satisfy the player, therefore to maintain a state of flow as frequently as possible, it is thus extremely important to learn to recognize, with the help of objective indicators, what is a state of optimal satisfaction in his/her experience.

C. Application of Gameplay Experience Modeling

The approach of modeling player's experience with respect to appraisal of challenge, has been widely explored, especially in the recent past ( [START_REF] Chanel | Boredom, engagement and anxiety as indicators for adaptation to difficulty in games[END_REF], [START_REF] Yannakakis | Entertainment modeling through physiology in physical play[END_REF], [START_REF] Rani | Anxiety-based affective communication for implicit human machine interaction[END_REF] among others). Although the methodologies may seem similar, there seems to be two research concerns in this direction. One approach concerns the qualitative evaluation of the game to ensure that the final product gives the desired experience. In this case, the interest is more on determining the nature of combination of factors that make a computer game fun [START_REF] Malone | What makes things fun to learn? heuristics for designing instructional computer games[END_REF]. A game should be designed to combine these aspects such that it leads to the best experience. For instance, Yannakakis and his team [START_REF] Yannakakis | Modeling and augmenting game entertainment through challenge and curiosity[END_REF], [START_REF] Yannakakis | Entertainment modeling through physiology in physical play[END_REF], [START_REF] Yannakakis | Real-time game adaptation for optimizing player satisfaction[END_REF] have carried out extensive work developing models able to recognize games designed to give more fun with respect to Malone's factors [START_REF] Malone | What makes things fun to learn? heuristics for designing instructional computer games[END_REF].

On the contrary, a second approach seeks to hold certain factors constant, while varying certain aspects of interest. Unlike the former approach, this approach is more concerned by the implicit manipulation of the player's experience during interaction. When it comes to the evaluation of challenge, triggering an optimal experience implies the player's ability to handle the task at hand while being actively engaged.

The assumption is that for well-designed game sequences, the appreciation will vary depending on the mastery of the skills required. For instance, Rani et. al. [START_REF] Rani | Maintaining optimal challenge in computer games through real-time physiological feedback[END_REF], [START_REF] Rani | Anxiety-based affective communication for implicit human machine interaction[END_REF] induced different levels of anxiety by varying the challenge. In a similar way, Chanel et. al. [START_REF] Chanel | Boredom, engagement and anxiety as indicators for adaptation to difficulty in games[END_REF] tested the hypothesis that the experience in a game level depends on the player's mastering of the skills required in that specific level. In this direction, a major concern is to enable the possibility for games to adjust online the level of difficulty based on the player's skills.

Although the two approaches are closely interrelated, our focus in this work was more on the second approach. We propose to advance further in this direction by proposing a machine learning approach that could be more applicable in real-time applications. The aim was to extract information for developing a generic emotionally adaptive control [START_REF] Hudlicka | Affective game engines: Motivation and requirements[END_REF], that induces a given experience on the player through challenge variation. As outlined by Fairclough's [START_REF] Fairclough | Fundamentals of physiological computing[END_REF] four zones of distress and engagement, the game should maintain a continuous loop between the stretch zone (when engagement and distress are both high) and comfort zone (when the user is comfortable with the level of demand yet remains motivated by the task at hand). The corrective mechanisms of the emotionally adaptive control will depend on whether the player is experiencing: i) Low Distress -Game Engagement (Comfort zone) -Game Disengagement * ii) High Distress -Game Engagement (stretch zone) -Game Disengagement * Therefore, our experimental setup was geared towards extracting the characteristics of the physiological features that can be used to discriminate these experiences for an adaptive control to provide appropriate corrective mechanism.

III. MACHINE LEARNING

A. Classification Methods

A wide range of methods have been proposed for emotion recognition from physiological signals such as linear discriminant analysis, k-nearest-neighbor (KNN), neural network and decision trees [START_REF] Picard | Toward machine emotional intelligence: Analysis of affective physiological state[END_REF], [START_REF] Nasoz | Emotion recognition from physiological signals for presence technologies[END_REF], [START_REF] Wagner | From physiological signals to emotions: Implementing and comparing selected methods for feature extraction and classification[END_REF], [START_REF] Rani | Anxiety-based affective communication for implicit human machine interaction[END_REF], [START_REF] Kim | Emotion recognition based on physiological changes in music listening[END_REF]. Although the results from these methods seems comparable (see in [START_REF] Wagner | From physiological signals to emotions: Implementing and comparing selected methods for feature extraction and classification[END_REF]), decision trees appear to be better suited for this kind of problem. A major advantage of decision trees lies in the fact that they induce explicitly defined rules used in classification. Our interest is not only to achieve high rates of classification but also to determine the relationship between the physiological signals attributes and the emotional states. The success of affective computing [START_REF] Picard | Affective Computing[END_REF] depends on establishing the optimal combination measures and features to discriminate emotional categories. Unlike other classifiers, decision trees not only perform classification but also evaluate attributes by selecting the best attribute that discriminate the classes in each node of the tree. Indeed, with a reasonable tree pruning and sample size, decision trees give characterization of the training set indicating how attribute values differ between different classes.

B. Fuzzy Decision Trees

As we have already pointed out, it is preferable to use an approach based on fuzzy sets theory. In fuzzy sets theory [START_REF] Zadeh | Fuzzy sets[END_REF], a fuzzy set is represented by a membership function, µ A : A → [0, 1], indicating the degree to which an element belongs to a given set A. This is a contrast to {0, 1} in a crisp set, in which an element can only belong to a given set A (membership value of 1) or not (membership value of 0). It is interesting for this kind of recognition to express our output in a gradual scale [0, 1] especially in order to continuously assess the emotional change during gameplay. In this respect, fuzzy expert systems designed with rules based on psychophysiological literature [START_REF] Mandryk | A fuzzy physiological approach for continuously modeling emotion during interaction with play technologies[END_REF], [START_REF] Rani | Anxiety-based affective communication for implicit human machine interaction[END_REF] and learning from fuzzy neural networks [START_REF] Yannakakis | Modeling and augmenting game entertainment through challenge and curiosity[END_REF], have been explored.

In this work, we consider a machine learning by means of fuzzy decision trees. Fuzzy decision trees automatically construct from the data a set of fuzzy rules which is knowledge base for a fuzzy expert system. This approach is an automatic method to build fuzzy partitions from attributes to avoid prior definition of fuzzy values and enables us to test and compare them in the process of classification. In addition, like classical decision trees, they represent induced knowledge in a very expressive way in which the path of a decision tree is equivalent to an IF . . . THEN . . . rule. This is a contrast to black box methods such as neural networks in which the model is represented by values of a network weights. Moreover, in fuzzy decision trees, as changes from one rule to another is gradual with fuzzy values [0, 1] instead of crisp values{0, 1} in classical trees, they have proved to provide better classification rate [START_REF] Marsala | Fuzzy decision trees to help flexible querying[END_REF].

The objective of this work was to explore automatic generation of psychophysiological relations based on the players' physiological data. We used Marsala's Salammbô Fuzzy Decision Tree [START_REF] Marsala | Fuzzy decision trees to help flexible querying[END_REF] and compared our results with Quilan's C4.5 decision trees [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] and KNN [START_REF] Cover | Nearest neighbor pattern classficiation[END_REF].

IV. THE EXPERIMENTAL SETUP AND SETTING

A. Participants and Setting

The experiment was conducted at the LUTIN (Laboratoire des Usages en Technologies d'Information Numérique), Paris, France. Participants in the experiment were recruited from visitors of the nearby museum, Cité des Sciences et de l'Industrie. They were all aged between 15 to 39 and no specific expertise in the field of video games was required, although we selected participants able to manipulate a gamepad and to orient themselves in a virtual environment. We tested a total of 39 participants. However, due to failures in the physiological recording, we kept data from 25 participants for whom all the sensors worked.

We tested a game belonging to a popular genre in the game industry, Halo3, which is a First-Person Shooter (FPS). This game is one of the best genre that promotes a sense of immersion in that it propels the player at the heart of action through a first-person perspective. Halo3 T M was played on a Microsoft Xbox 360 T M on a 32-inch LCD television. A camera captured the TV screen. Participants were seated at approximatively one meter from the screen, they were explicitly told not to move and keep the game pad onto their laps in order to avoid any muscular artefact in the physiological recording.

B. Physiological Signals and Features

In order to discriminate emotions from physiological signals, a wide range of measures have been proposed such as electromyography measuring facial muscle tension, the blood volume pulse, the skin conductance, respiration rate and measures related to the brain activity. In this work, based on the previous literature, we identified a subset of these measures that can be used almost non-intrusively while yielding optimal results. We chose to collect galvanic skin response (GSR), heart rate (HR) and respiration rate (RR) data during gameplay. GSR which is a measure of the conductivity of the skin is considered as an effective correlate to arousal [START_REF] Lang | The emotion probe studies of motivation and attention[END_REF], [START_REF] Bradley | Affective picture processing[END_REF], [START_REF] Detenber | Roll' em! the effects of picture motion on emotional responses[END_REF] and has been extensively used in the domain of affective computing [START_REF] Scheirer | Frustrating the user on purpose: A step toward building an affective computer[END_REF], [START_REF] Ward | Physiological responses to different web page designs[END_REF], [START_REF] Mandryk | A fuzzy physiological approach for continuously modeling emotion during interaction with play technologies[END_REF]. On the other hand, heart rate (HR) and blood pressure may also give an indication about stress-related activities with heart rate accelerations mediated by the sympathetic nervous system [START_REF] Llabre | The reliability and specificity of delta versus residualized change as measures of cardiovascular reactivity to behavioral challenges[END_REF], [START_REF] Murphy | Gender and ethnicity in childrens cardiovascular reactivity : 7 years of study[END_REF]. But as a result of a dual innervation of the heart by both the sympathetic and the parasympathetic nervous systems, HR could also index moments of attentional surge. For instance, increased cardiac parasympathetic activity causes HR to decelerate when attention is paid to an external (e.g., media) stimulus [START_REF] Lacey | Some autonomic-central nervous system interrelationships[END_REF] [START_REF] Turpin | Effects of stimulus intensity on automatic responding: The problem of differentiating orienting and defense reflexes[END_REF].

To collect the physiological measures we used the Biopac M P 35 acquisition unit and the software BSLPro to visualize the data. We collected heart rate (HR) through a measure of cardiovascular activity by measuring the electrocardiography (ECG) through a Einthoven derivation II placing pregelled surface electrodes on the ankles and on the wrist. We recorded GSR using surface electrodes attached with Velcro T M Straps that were placed on two fingers of the left hand. The fingers wearing the electrodes remained wedged under the gamepad. We recorded the respiration rate (RR) with a stretch sensor positioned around the thorax. ECG, GSR and RR data were collected at 200Hz. As noisy ECG data may produce failures in computing the HR, we inspected the HR data and corrected manually every erroneous samples. The same method was applied to the RR.

In respect to physiological feature extraction, for each signal, we chose to calculate the features shown in Table I that we belief are very relevant based on results from past research and our earlier preliminary work [START_REF] Orero | Assessing gameplay emotions from physiological signals : A fuzzy decision trees based model[END_REF].

C. Game Sequences

As a baseline, we used a resting period during which participants watched the introductory screen from the game. This screen is appropriate to elicit a relaxing state in that it depicts a contemplative scene with slowly moving objects accompanied by a soft soundtrack. Participants played successively to four short sequences, each of them followed immediately by a questionnaire and a two-minutes resting period. The game sequences were as follows:

i) Sequence 1: The game session always started with an introductory sequence corresponding to the first minutes of the game. In this sequence, the transition from exploration to combat is smooth, and specifically designed not the challenge excessively the player enjoying the game for the first time. After having played Sequence 1, participants were asked to complete the three following sequences. The order of presentation of these sequences was counterbalanced. ii) Sequence 2: the player is driving a powerful tank, he is heavily protected and benefits from a highly effective arsenal; iii) Sequence 3: the player is equipped with a sniping riffle, and is allowed to shoot enemies at a distance. The player is in a tactical advantage, as he stands in a upper position; iv) Sequence 4: the player is confronted to the highest difficulty level of the game. The player is equipped with a very basic arsenal, whereas ennemies are well armed, ferocious and very resistant.

D. Self-Assessment Reports

At the end of each game episode, we asked the participant to rate both her evaluation of the level of certain psychological parameters, as well as the pleasure gained from these parameters on a six-point ranking scale such as: i) How much concentration is required in this sequence? ii) Did you enjoy that the sequence requires this particular amount of concentration? iii) How arousing is this sequence? iv) Did you enjoy that the sequence elicits this particular amount of arousal? . . . . Then, at the end of the experiment (after the participant had completed the four sequences), we asked him to answer four questions where a comparison between the four sequences was proposed: i) Which sequence is the most amusing? ii) Which sequence is the least amusing? iii) Which sequence is the most challenging? iv) Which sequence is the least challenging?

V. RESULTS

A. Learning Set Construction

To have a more objective correlation of the subjective experiences and the physiological measures during classification, we used the evaluation at the end of the experiment. As shown in Figure 1 and Figure 2, we found that the sequences considered as the most/the least challenging were not the ones considered as the most amusing. Specifically, we can see that the Sequence 4, which were clearly used as a representative of a very difficult game episode, was chosen by almost every participant as the one considered the most challenging. On the other hand, few participants considered this sequence as the most amusing. This probably reflects the fact that participants felt their skills exceeded in this episode, with a feeling of frustration as a consequence. On the opposite side, the Sequence 1, which was the introduction of the game, was clearly picked up as the least challenging sequence, no participant chose it as the most amusing. In this case, the lack of challenge is certainly the factor determining a weak sense of fun. These two results confirm the fact that in order to optimize the sense of fun, the player must be maintained in a state of flow, between boredom and anxiety, with the Sequence 2 and Sequence 3 standing here in the closest position to this state of flow. First, since there was a variation of the length of the episodes from participant to participant and to minimize the effect of the transition periods, we used only the physiological recordings of the last two minutes of the game sequence. Then we subdivided the signals into 10 seconds (2000 data points) segments. As attributes for the classifiers, we calculated the features explained in Section IV. Secondly, to account for variations between participants, we calculated each participant's attribute normalized value, nA i , from the row value, A i , using the attribute's standard deviation, A sdv , and its mean, A mean as shown in Equation 1. The output from the classifiers was in linguistic variables for each of the dimensions. The output from the fuzzy decision tree was in continuous values [0, 1] indicating the membership grades of a given sample to a particular linguistic variable. Figure 3 shows an example of fuzzy decision tree output from one of the participants. Samples 1 to 12 were samples from the sequence evaluated as the least amusing sequence while the rest were from the sequence evaluated as the most amusing. As it can be seen, although some samples from the least challenging sequence were classified as high and vise versa, we have more information as regards to the gradual change from one point in time to the next. This kind of information is critical towards building expert systems. We defuzzified the output into values {0, 1} and compared the results with other classifiers.

nA i = A i -A mean A sdv (1)

B. Results of Classification

Our main objective was to extract physiological features that characterize player's level of enjoyment (amusement). In order to have two clearly distinct categories of game sequences, we contrasted between the game sequence identified as the most amusing against the one identified by the player as the least amusing. We obtained the results shown in Table II. Figure 4 shows a sample of decision tree for discriminating most and least amusing game sequences. In particular, when GSR mean was greater than 0.22, the majority of the sequences are of low amusement.

Alternatively, as already discussed we can consider the amusement with respect to challenge. As we already noted, we can distinguish two possible undesirable player Secondly, in order to ascertain the physiological features that characterize moments when the player feels overloaded by the task (overload disengagement), we contrasted the sequences judged as the most challenging with the one identified as the most amusing. As shown in Figure 1, Sequence 4 is clearly judged as the most challenging, but 22 participants out of 25 did not find it the most amusing. Using data from these 22 participants, we contrasted between sequences identified by the player as most amusing against Sequence 4 (the most challenging sequence). We obtained the results shown in Table IV. Globally, the generated decision trees revealed that, the GSR (min), HR (min amplitude value, maximum value of the first derivative) and RR (maximum value of the first derivative and power spectrum density), were the most relevant features.

VI. CONCLUSIONS AND FUTURE PERSPECTIVES

In this study, we set up an experiment to enable us model the player's experiences. We used fuzzy decision trees to automatically characterize the behavior of physiological signals with respect to players' evaluation of challenge in a game episode. We managed to identify with considerable success amusement level in respect to variation of challenge at stake. Our results thus show that it is possible to gain information from physiological signals considering the optimal state of satisfaction of a player. Flow, in terms of physiological activity, is reflected by variations in GSR and other range of physiological activations that may be considered as the sign of a deeper immersion in the game.

Eliciting a state of higher arousal by increasing the challenge faced by the player is one of the component necessary to get a positive reaction. However, this component, when not coupled to a possible immersion component, may impede the sense of positive involvement in the game. In our experiment, this seems to happen especially when players face the highest level of difficulty of the game. Therefore, flow might be characterized as a sense of high physiological arousal coupled with a (possibly more cognitive) feeling of adequation between the level of difficulty and the skills at hand.

However, much is still to be done before getting access to the structure of the player's emotional processes. Our results further confirm the difficulty in performing machine learning due to inter individual variations of physiological signals. Physiological signals seem to vary considerably from participant to participant. Indeed, although we attempted to minimize these variations by normalizing the features for each participant, it may not have been successful due to enormous variations between individuals' physiological data. We thus need to consider better algorithms to tackle this problem.

Altogether, the road map for the forthcoming investigation of affective states in video game will get through a clear definition of the most relevant dimensions to account for the emotional response we target, as well as a thorough examination of other machine learning approaches. In this work, we introduced the aspect of correlating objective with subjective measures. Some more work is needed to understand how to combine subjective measures with multiple objective measures. This way, we hope for a truly systematic affective recognition procedure to be incorporated to the games evaluation routines.

Fig. 2 .

 2 Fig. 1. Most Amusing vs Challenge

Fig. 3 .

 3 Fig. 3. Example of Output from Fuzzy Decision Tree

RR min <= 16.44860: Low Amusement (4) | | | RR min > 16.44860: High Amusement (17): Low Amusement (2) | HR min > 67.90785: High Amusement (89): Low Amusement (20) GSR mean > 0.22266 | GSR min <= 6.33326: Low Amusement (78): High Amusement (12) | GSR min > 6.33326 | | GSR min <= 8.76122: High Amusement (14) | | GSR min > 8.76122: Low Amusement (19): 1.00 (6)

	TABLE II MOST/LEAST AMUSING GAME SEQUENCES CLASSIFICATION RESULTS	GSRmin<= -0.33239 : T ooLowDistress(104) : M ostAmusement(19)
	Least Amusing	Salammbô FDT 80.40%	Quilan C4.5 DT KNN(k=10) 78.80% 77.50%	GSRmin> -0.33239 : M ostAmusement(125) : T ooLowDistress(40)
	Most Amusing Overall	71.30% 75.85%	70.00% 74.40%	76.30% 76.90%	The GSR signal can thus be successfully used to detect periods when the player is insufficiently challenged (too low
					distress disengagement).
		Low/High Amusement Decision Tree
	GSR mean <= 0.22266
	| HR min <= 67.90785
	| | RR derivative<= 3.02265:Low Amusement (21):High Amusement (6)
	| | RR derivative > 3.02265
	| | | Fig. 4. Sample Extract of High/Low Amusement Decision Tree
	experiences (a) moments disengagement due to low distress
	, when the player is likely to feel insufficiently challenged
	by the task (too low distress disengagement) and (b) those
	moments when the player is overstretched beyond his/her
	ability leading to anxiety (high distress disengagement).
	As our interest is in developing emotionally adaptive
	system, it is important to identify the physiological features
	that characterize them as they require different adaptive
	mechanisms. First, as shown from Figure 1, Sequence 1
	which was the least challenging game sequence, was not
	identified by any participant as the most amusing. Therefore,
	to extract physiological features that characterize a game
	sequence of low distress disengagement (low challenge), we
	contrasted Sequence 1 and the sequence identified by the
	participant as the most amusing and found the results shown
	in Table III. We pruned a sample decision tree to produce
	the following two rules:

IEEE Conference on Computational Intelligence and Games (CIG'10)

IEEE Conference on Computational Intelligence and Games (CIG'10)


Yutaka Takeuchi

Patrick Gros

Martial Hebert
email: hebert@cs.cmu.edu

Katsushi Ikeuchi

Visual Learning for Landmark Recognition

Recognizing landmark is a critical task for mobile robots. Landmarks are used for robot positioning, and for building maps of unknown environments. In this context, the traditional recognition techniques based on strong geometric models cannot be used. Rather, models of landmarks must be built from observations using image-based visual learning techniques. Beyond its application to mobile robot navigation, this approach addresses the more general problem of identifying groups of images with common attributes in sequences of images. We show that, with the appropriate domain constraints and image descriptions, this can be done using efficient algorithms as follows: Starting with a "training" sequence of images, we identify groups of images corresponding to distinctive landmarks. Each group is described by a set of feature distributions. At run-time, the observed images are compared with the sets of models in order to recognize the landmarks in the input stream.

Introduction

Recognizing landmarks in sequences of images is a challenging problem for a number of reasons. First of all, the appearance of any given landmark varies substantially from on observation to the next. In addition to variation due to different aspects, illu-mination change, external clutter, and changing geometry of the imaging devices are other factors affecting the variability of the observed landmarks. Finally, it is typically difficult to use accurate 3D information in landmark recognition applications. For those reasons, it is not possible to use many of the object recognition techniques based on strong geometric models.

The alternative is to use image-based techniques in which landmarks are represented by collection of images which are supposed to capture the "typical" appearance of the object. The information most relevant to recognition is extracted from the collection of raw images and used as the model for recognition. This process is often referred to as "visual learning".

Progress has been made recently in developing such approaches. For example, in object modeling [Gros et al.], 2D or 3D model of objects are built for recognition applications. An object model is built by extracting features from a collection of observations. The most significant features are extracted for the entire set and are used in the model representation. Extension to generic object recognition were presented recently [Carlsson, 1996].

Other recent approaches use the images directly to extract a small set of characteristic images of the objects which are compared with observed views at recognition time. For example, the eigen-images techniques are based on this idea.

Those approaches are typically used for building models of single object observed in isolation. In the case of landmark recognition for navigation, there is no practical way to isolate the object in order to build models. Worse, it is often not known in advance which of the objects observed in the environment would constitute good landmarks.

A similar problem, although in a different context, is encountered in image indexing, where the main problem is to store and organize images to facilitate their retrieval [START_REF] Lamiroy | [END_REF]] [Schmid et al., 1996]. The emphasis in this case is the kind of features used and the type of requests that can be made by the user.

Our approach tries to combine these two categories of systems. In a training stage, the system is given a set of images in sequence. The aim of the training is to organize these images into groups based on similarity of feature distributions between images. The size of the groups obtained may be defined by the user, or by the system itself. In the latter case, the system tries to finds the most relevant groups, taking the global distribution of the images into account. In a second step, the system is given new images, which it tries to classify as one of the learned groups, or in the category of unrecognized images.

The basic representation is based on distributions of different feature characteristics. All these different kinds of histograms are computed for the whole image and for a set of sub-images. Tests are used to compare these histograms and define a distance between images. This distance is then used to cluster the images into groups. Each group is then characterized by a set of feature histograms. When new images are given to the system, the algorithm evaluates a distance between these images and the groups. The system determines to which group this image is the closest, and a set of thresholds is used to decide if the image belongs to this group.

The main goal of the work presented here was to explore the use of tools and methods in the field of image retrieval to the problem of landmark recognition. It is clear that the global architecture of the system is close to that of object recognition systems [Gros et al.]: a training stage in which 3D shape, 2D aspects, or groups, are characterized is followed by a recognition stage in which this information is used to recognize the models, objects or groups in new images. The difference comes from the wide diversity of the images and from the groups which are not reduced to a single aspect of an object. The two challenging tasks which we concentrate on in the remainder of the paper are to define these groups more precisely as sets of images, and to build automatically a characterization for each group.

The first section of the paper deals with the feature distributions, their computation and their comparison. The second section addresses the computation and the characterization of groups. The third section concerns the classification of new images according to the groups previously defined. Experimental data and results are presented in the fourth section.

Representing Images

In this section, we give a brief overview of the features used for representing images. Since an individual feature can be characteristic of an aspect of an object, but probably fails to characterize well a set of aspects, we use a statistical description of a large number of features as our basic representation Representing Feature Distributions Five basic features are currently used: distributions of normalized color and intensity, edges, segments, and parallel segments. Additional features can be added as needed. The basic image representation is a set of feature distributions. Edges are computed using Deriche's edge detector [Deriche, 1987]. Segments are computed as a polygonal approximation of the edges [START_REF] Horaud | [END_REF]. Among the characteristics computed from these five features are: color and grey levels; edge density, orientation, length and position; segment density, orientation, length, and position; parallel segment density, orientation, length, and position, and, finally, the angles between adjacent segments.

Feature densities are computed in two ways: first as the ratio of the number of features (edges, segments and parallel segments, respectively) to the area of the image or sub-image concerned; second as the ratio of the sum of all the feature lengths to the area of the image or sub-image. All the other measurements are computed and the results stored in histograms. Each bucket of the length histograms indicates how many features a length has in a given interval.

The position of a particular object in an image may vary substantially between observations. Therefore, it is important to build the representation in a way that allows for different placements of the object with similar resulting feature distributions. This is done by subdividing the image into smaller chunks, in which the feature distributions are computed. All these histograms and densities, except those relative to feature position, are computed for the whole image and for the sub-images obtained by dividing the image by 4, then 9, and then 16. The position histograms are computed only for the global image, i.e., 90 densities and 333 histograms are computed to characterize each image.

Comparing Feature Distributions

The feature distributions from two images are compared using a distance similar to the chi-square distance. This distance, in its simplest form, evaluates the probability that two sets of data, here the histograms or the densities, are derived from the same theoretical distribution. If the distributions are h = (h i ) and l = (l i ), their difference is computed as [START_REF] Press | [END_REF]

: d(h, l) = Σ i (h i -l i ) 2 /(h i + l i ).
The main problem is to derive a global distance between two images from the individual distances computed for each type of density and histogram. The distance d ij between two images i and j is defined as the linear combination of the distances between individual feature distributions:

d ij = Σ k λ k d(h, l)
, where the sum is taken over all the feature distributions used for representing the images.

When nothing is known about the distributions and their range of variation, all the weights can be taken equal to one. This simple approach gives good results in practice, but a better approach is to compute the weights based on the relative scales of the feature distributions. For each kind of density or histogram, the distance between every pair of images is computed, and the variance σ 2 k of these distances is derived. The coefficient relative to this particular distribution can be chosen as λ k = 1/σ 2 k . This choice of weights has the effect of normalizing the distributions and of assigning the same relative importance to all the partial distances used.

From Images to Landmarks

Given a sequence of images, we now want distinctive landmarks, that is, we want to split the sequence into groups of images, and find a characterization of each of these groups which allows further classification. This step is difficult to do fully automatically in general. The main reason is that there is not a taskindependent definition of the type of image groups that are needed. Our approach is to use task constraints to guide the grouping process. Specifically, given an initial grouping of images, we select groups based on three constraints. First, only the groups that contain a large enough number of images from different aspects are retained. Second, groups that do not provide significant discrimination are discarded. This is important to ensure that, at recognition time, only the groups that can be easily distinguished are used as models. Finally, the recorded sensor position for each training image is used for ensuring that the groups are spatially coherent.

Computing Initial Image Groups

Once the distance matrix is computed, a simple agglomerative method is used to split the image set into initial groups. First each image is put in a different group. Then the two closest groups are grouped and the distance matrix is updated. Finally, the algorithm iterates the previous step until an ending condition is verified.

Let |L| denote the number of elements of the image group L. The update of the matrix consists of suppressing the two lines and two columns i and j corresponding to the groups I and J which are grouped, and then adding a new line and column for the new group formed. The diagonal term of the new line added is:

(1)

The non diagonal term corresponding to the new group and a group k is:

(2) These formulas show that, at each iteration, the only information needed is the distance matrix and the number of elements in each group. Each term of the matrix is thus the mean distance between the images of two groups, or the mean distance of the images of a same group.

Controlling the Grouping Algorithm

The grouping algorithm described above is general. In particular, it does not incorporate a control structure that stops the grouping process when groups of images corresponding to recognizable landmark are formed. An automatic method was developed for controlling image grouping.

Given a set of image groups, let us denote the distance matrix by (d ij ) and the number of images of the group i by n i . If the images used to learn the groups form a representative sample, and if they are spread nearly uniformly in representation space, the probability that an unknown image will be classified in the group i (p i ) or in no group at all (p 0 ) can be evaluated. If n denotes the number of groups:

(3) These formulas state that the probability p i that a new image belongs to a group is proportional to the size d ii of this group, and that the probability p 0 of being in no group is proportional to the distances d jk between the groups. The factor 2/(n-1) is used to compensate the number of non-diagonal terms of the distance matrix with respect to the number of diagonal terms.

In the case where the images are known not to have a uniform distribution in a region of their representation space, this can be taken into account by using these other formulas:

(4)

In these new formulas, not only the size of the groups is taken into account but also their density, which is proportional to n i . The probability p 0 is also a function of the size of the groups: for the same distances between the groups, the smaller the groups, the bigger their density, and the smaller is the probability of having a new image between them.

The evaluation function is the entropy associated with this set of probabilities S= -Σ i p i ln p i , and the process is stopped when this entropy is maximal. This maximizes the information provided to the user by each classification request. -------------------------------------------------------------------------------------------------- In general, given an image, it would be necessary to consider other images for grouping in a radius around the corresponding vehicle position. In practice, images in the training sequence are digitized at approximately equal intervals. As a result, it sufficient to consider for grouping with image i only images j such that |i -j| < r, where r is the maximum extent of observability of any given landmark. This constraint reduces the computational complexity of the grouping algorithm, and it guarantees that the image groups correspond to spatially coherent landmarks.

I I 1 - ( )d ii J J 1 - ( )d jj 2 I J d ij + + I I 1 - ( ) J J 1 - ( ) 2 I J + + -
I I J ∪ ---------------d ik J I J ∪ ---------------d jk + p i d ii d jj j ∑ 2 n 1 - ------------ d jk j k ≠ ∑ + ------------------------------------------------- = p 0 2 n 1 - ------------ d jk j k ≠ ∑ d jj j ∑ 2 n 1 - ------------ d jk j k ≠ ∑ + ------------------------------------------------- = p i n i d ii n j 1 + ( )d jj j ∑ 2 n 1 - ------------ d jk j k ≠ ∑ + --------------------------------------------------------------------- = p 0 2 n 1 - ------------ d jk j k ≠ ∑ n j 1 + ( )d jj j ∑ 2 n 1 - ------------ d jk j k ≠ ∑ + --------------------------------------------------------------------- =

Recognition

Given set of image groups C i , characterized by their mean vector v i , their eigenvalues λ i1 ...λ il , and their eigenvectors v i 1 ... v i l , the problem is to compare these groups to a new image whose characteristic vector is v. The eigenvalues are positive, and the eigenvectors of a group are a family of orthonormal vectors, and v -v i may be decomposed with respect to this family: v -v i = Σ j a j v i j + r. The distance between v and the group C i is derived as:

(5) This formula allows us to find which is the closest group to an image. The problem is then to decide if the image really belongs to this group. We again use the task constraints. Intuitively, consecutive images should be classified in a consistent manner. Since we know the spatial extent from which a particular group of images is visible in the training sequence, we can eliminate the inconsistent classification results as unreliable.

Examples

The recognition algorithm was tested using several sequences taken from a moving vehicle. Figure 4 shows sample images from a test sequence taken over the same course as the training sequence of Figure 1. A total of 68 images were digitized from the test sequence at regular intervals. The test set of images was segmented manually into subsets corresponding to the landmarks identified in the training sequence. This provided the "ground truth" for evaluating the performance of the algorithm. Vehicle position was recorded using the INS system onboard a HMMWV used in a separate Unmanned Ground Vehicle (UGV) project [Hebert et al., 1996].

Using the algorithm outlined above, all the images in the test sequence were compared with the landmarks found in the training sequence. The images corresponding to a distinct distance minimum are labeled with the corresponding landmark number. Images that do not correspond to a distance minimum for any landmark are left unclassified. As we noted earlier, our goal is not to label every image but rather to correctly recognize the ones corresponding to the most salient landmarks.

Figure 5 illustrates the classification algorithm for three different landmarks. The graphs show that, for those three landmarks, the distance minimum is attained at the correct images in the test sequence. Figure 7 shows a view of all the landmarks recognized in the path travelled in the test sequence. Four landmarks are recognized in this example.

d C i v , ( ) a j 2 λ i j 1 + ---------------- j ∑ r 2 + =
Figure 7 also illustrates the potential use of landmark recognition for position estimation.

Two types of errors may occur during recognition. First, images that should match a landmark are matched to a different landmark. We call those images misclassified images. Second, images that should match a given landmark are not matched with any landmark. We call this second class of images unclassified images. To reduce the error rate, we use the sequential constraint earlier. This constraint is quite effective in practice.

Figure 6 shows the error statistics for the recognition algorithm with and without sequential constraint.

All the examples given so far involve images taken in urban environments. We have also conducted experiments in natural environments by collecting training sequences, extracting groups of distinctive images, and recognizing them in test sequences. Figure 8 shows two example groups computed from a typical training sequence. The error rate, is comparable to the one obtained in urban scenarios.

Conclusion

Results on image sequences in real environment show that visual learning techniques can be used for building image-based models suitable for recognition of landmarks in complex scenes. The approach performs well, even in the presence of significant photometric and geometric variations, provided that the appropriate domain constraints are used. In the case of mobile robot navigation, domain constraints include the sequential nature of the images, and the discriminability of landmarks.

Our goal is to demonstrate the use of landmark recognition for navigation. Specifically, we will show that rough position estimation and navigation based on the relative positions of landmarks can be achieved using image-based landmark recognition. Several limitations of the approach need to be addressed. First of all, rejection of unreliable groups need to be improved. In particular, the selection of the parameters controlling the grouping need to be implemented in a principled manner. Second, images that do not contribute information should be filtered out of the training sequences.

Figure 1 :

 1 Figure 1: Sample set of images from a typical training sequence. The complete training sequence contains 176 images taken over approximately 800 meters.

Figure 2 :

 2 Figure 2: Three of the groups extracted from the training sequence of Figure 1. Only three images are shown for each group.

  An important constraint in the context of landmark recognition is that the images are ordered in the training sequence. In fact, the position of the vehicle is recorded for each image. Using this information, grouping is limited to images for which the vehicle positions were close to each other, thus ensuring spatial consistency.

Figure 3 :

 3 Figure 3: Comparison of two new images (top) with the groups shown in Figure 2. The distance graph of the left image is shown as a solid line. The images are correctly classified in group 7.

Figure 4 :Figure 5 :

 45 Figure 4: Sample images from a test sequence. The complete sequence is 68 images over a course similar to the one used in Figure 1 for the training sequence. The orientation of the camera, and the illumination characteristics are substantially different from those of the training sequence.

Figure 7 :

 7 Figure 7: Overhead view of the path followed while collecting the images of the test sequence of Figure 4 (distances are indicated in meters.) Four landmarks are correctly identified. Example images from the test sequence are shown for each landmark.

Figure 8 :

 8 Figure 8: Images of one of the landmarks found in a sequence of images in a natural environment.

  Performance of the recognition algorithm on the two example sequences. Images are labeled as "misclassified" if they are matched to the wrong group; they are labeled as unclassified if they belong to a group but are not matched.

	Landmark 6		Landmark 7
	Urban Environment:
		distance only	with sequential constraint
	correct	72%	93%
	misclassified	19%	0%
	unclassified	9%	7%
	Natural Environment:
		distance only	with sequential constraint
	correct	84%	97%
	misclassified	6%	0%
	unclassified	10%	3%
	Figure 6:

1. This research was sponsored in part by Office of Naval Research (ONR) under Contract N00014-95-1-0591 and, in part, by DARPA under contract DAAE07-96-C-X075 monitored by TACOM. Patrick Gros was supported by a NATO fellowship. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of ONR, DARPA or the U.S. Government.


Julien Duboisset

Fabiana Munhoz

Zohra Fatma

Philippe Bioud

Sophie Réfrégier

Hervé Brasselet

Rigneault

Fatma

MOLECULAR ODER SYMMETRIES INVESTIGATED BY RESONANT (CARS, SRS) AND NON RESONANT (FWM, SHG) NONLINEAR POLARIZATION MICROSCOPY

published or not. The documents may come

MOLECULAR ODER SYMMETRIES INVESTIGATED BY RESONANT (CARS, SRS) AND NON RESONANT (FWM, SHG) NONLINEAR POLARIZATION MICROSCOPY

In the last few years non linear microscopy techniques have strongly evolved to become powerful imaging and spectroscopy tools that are nowadays ready to investigate the biological world. Indeed non linear microscopy allows spectroscopy and imaging of specific objects without the need of labeling or staining. This is the case of coherent Raman contrasts [START_REF]such as coherent anti-Stokes Raman scattering (CARS) and stimulated Raman scattering[END_REF] that are resonant with a molecular vibrational level. In this case, the interaction of the incident fields with the sample induces a third-order nonlinear polarization, whose properties depend both on the vector nature and frequencies of the incident electromagnetic fields and the structure of the medium. We have recently used polarization resolved CARS to decipher the orientation of specific molecular bond in a crystal [START_REF] Munhoz | [END_REF]. Indeed this study was possible because of the known structure of the targeted molecular bond. On the contrary, in bio-imaging, one deals with targeted molecular bond whose orientation and/or microscopic structure are unknown. In this framework it is very important to develop a general methodology to analyze polarization resolved signal in nonlinear microscopy.

In this work we investigate the potential of spherical basis to describe both the optical field and the induced nonlinear polarization. Theoretical investigations from the 70's [3] show that the complete accessible molecular function distribution can be recovered using polarization resolved methods and a complete spherical harmonic description of the susceptibility tensor, the electric fields and the molecular distribution function. We find that this model can be generalized for every n-wave mixing resonant and non-resonant processes. In this framework, this is our goal to investigate the impact of molecular symmetries on the recovered nonlinear polarization signals using non resonant (SHG, FWM) and resonant (CARS, SRS) contrast as generated in our microscope. We will discuss these concepts and give experimental illustrations in order to probe specific molecular organization in biological assemblies.

Duboisset, Fabiana Munhoz, Fatma Zohra Bioud, Philippe Réfrégier, Sophie Brasselet and Hervé Rigneault Institut Fresnel, MOSAIC CNRS UMR 6133, Universités Aix-Marseille III, Ecole Centrale Marseille Domaine Universitaire de Saint Jérôme 13013 Marseille, France Email :julien.duboisset@fresnel.fr

	KEY WORDS : Nonlinear microscopy, molecular orientation, Coherent Anti-Stokes Raman
	Scattering (CARS), Second harmonic generation (SHG), Stimulate Raman scattering (SRS),
	polarization analysis.