Emmanuelle Chapoulie

Maud Marchal

Evanthia Dimara

Maria Roussou

Jean-Christophe Lombardo

George Drettakis
email: george.drettakis@inria.fr

J.-C Lombardo

Evaluation of Direct Manipulation using Finger Tracking for Complex Tasks in an Immersive Cube

Keywords: Virtual reality, Direct manipulation, Immersive cube, Finger tracking

A solution for interaction using finger tracking in a cubic immersive virtual reality system (or immersive cube) is presented. Rather than using a traditional wand device, users can manipulate objects with fingers of both hands in a closeto-natural manner for moderately complex, general purpose tasks. Our solution couples finger tracking with a real-time physics engine, combined with a heuristic approach for hand manipulation, which is robust to tracker noise and simulation instabilities. A first study has been performed to evaluate our interface, with tasks involving complex manipulations, such as balancing objects while walking in the cube. The users finger-tracked manipulation was compared to manipulation with a 6 degree-of-freedom wand (or flystick), as well as with carrying out the same task in the real world. Users were also asked to perform a free task, allowing us to observe their perceived level of presence in the scene. Our results show that our approach provides a feasible interface for immersive cube environments and is perceived by users as being closer to the real experience compared to the wand. However, the wand outperforms direct manipulation in terms of speed and precision. We conclude with a discussion of the results and implications for further research.

Introduction

Fig. 1 A user in the four-sided cube holding a tray with two hands.

Interaction in immersive virtual reality systems (e.g., CAVEs) has always been challenging, especially for novice users. In most systems, 6 degree-of-freedom (6DOF) devices such as wands or flysticks are used for navigation as well as selection and manipulation tasks. Such devices are well established and can be very powerful since they allow users to perform actions which cannot be performed naturally, such as picking objects from afar, or navigating while physically staying in the same place. However, one goal of fully immersive systems is to enhance presence and immersion [START_REF] Slater | Place illusion and plausibility can lead to realistic behaviour in immersive virtual environments[END_REF]]. In such a context, flysticks can potentially degrade the realism and naturalness of the virtual environment (VE). To avoid this shortcoming, the use of direct manipulation (DM) using finger tracking as close as possible to the manipulation used in the real world is investigated [START_REF] Moehring | Natural interaction metaphors for functional validations of virtual car models[END_REF]; [START_REF] Wexelblat | An approach to natural gesture in virtual environments[END_REF]; [START_REF] Jacobs | A generalized Godobject method for plausible finger-based interactions in virtual environments[END_REF]; [START_REF] Hilliges | HoloDesk : Direct 3D Interactions with a Situated See-Through Display[END_REF]].

With the advent of hand and finger tracking solutions, there has been recent interest in using DM and gestures in immersive systems to achieve specific tasks, such as automotive design [START_REF] Jacobs | A generalized Godobject method for plausible finger-based interactions in virtual environments[END_REF]; [START_REF] Moehring | Natural interaction metaphors for functional validations of virtual car models[END_REF]], focusing on carefully handling the physics of collisions between hands and virtual objects in specific tasks. However, little has been done to investigate the usability of DM in a fully immersive setting for relatively complex, general-purpose tasks. Moreover, the effect of DM on presence or the similarity with real-world manipulations has not been sufficiently researched.

A solution which incorporates DM for grasping and moving objects, using both one and two hands, based on finger tracking with a glove-like device is presented and evaluated. Our system operates in a four-sided immersive cube (IC), i.e., a room with three rear-projected walls and rear-projected floor, providing a high sense of presence. To provide the most immersive and plausible experience, our solution uses a real-time physics simulator in addition to finger tracking. A physics engine, or simulator, is a software library that approximates the physical behavior of virtual objects by computing collision detection, the effect of gravity, etc., and the corresponding object transformations. It allows close-to-natural manipulation of objects in the scene. An approach for DM which is robust to tracker noise and instabilities of the physics simulation is presented.

The goals of our study are to evaluate (a) whether DM is a feasible alternative to traditional IC interfaces such as a wand, (b) the effect of using DM on presence, and (c) the similarity to real-world manipulation.

To demonstrate feasibility, we purposely choose a task that involves quite complex translations and rotations, while the user walks in the cube, and at the same time balances objects on a tray. DM is compared to traditional wand-based interaction and, most importantly, compared to a real-world reproduction of the virtual task, through a study focused on the sense of immersion. We record both objective measurements (time to completion and errors) and subjective judgments through the use of a questionnaire.

In summary, our study shows that two-handed DM enhances the sense of presence for some tasks, and users consider it more natural and closer to reality than the wand, clearly demonstrating its utility. Our objective measurements show that the wand and DM are in most cases equivalent in terms of speed and precision, but are slower than doing the task in the real world. The unconstrained user experience also shows several informal effects of enhanced presence due to DM, such as reflex reactions of participants trying to grasp dropped objects, or using two hands to adjust the position of a plate on a table.

Previous work

Gesture-based interaction has received significant interest in virtual or augmented reality research [START_REF] Sturman | Hands-on interaction with virtual environments[END_REF]; O 'Hagan et al (2002); [START_REF] Buchmann | Fingartips: gesture based direct manipulation in augmented reality[END_REF]; [START_REF] Cabral | On the usability of gesture interfaces in virtual reality environments[END_REF]]. A thorough review of natural gestures for virtual reality (VR) [START_REF] Bowman | Questioning naturalism in 3d user interfaces[END_REF]] underlines the many positive features of natural, but also discusses the utility of hyper-natural interfaces. In a previous survey of 3D user interfaces (UI) [START_REF] Bowman | 3d user interfaces: New directions and perspectives[END_REF]], natural gestures are mentioned as one of the important future directions for 3D UIs. In many cases, gestures are used to define a vocabulary or language [START_REF] Buchmann | Fingartips: gesture based direct manipulation in augmented reality[END_REF]] even if the number of gestures is often limited [START_REF] Sturman | Hands-on interaction with virtual environments[END_REF]; O 'Hagan et al (2002); [START_REF] Cabral | On the usability of gesture interfaces in virtual reality environments[END_REF]]. The early work by [START_REF] Bolt | "put-that-there": Voice and gesture at the graphics interface[END_REF] already investigates the combined use of gestures and voice inputs through a set of commands to manipulate simple shapes. However, the use of a specific vocabulary can create an overhead for the user who must remember the meaning of each gesture. An early solution providing more natural interfaces involved the use of multimodal interactions, combining depictive gestures with speech [START_REF] Koons | Iconic: speech and depictive gestures at the human-machine interface[END_REF]; [START_REF] Latoschik | Utilize speech and gestures to realize natural interaction in a virtual environment[END_REF]; [START_REF] Latoschik | A gesture processing framework for multimodal interaction in virtual reality[END_REF]]. We are more interested in the case of DM, i.e., interacting with the environment in a natural manner with the users hands [START_REF] Moehring | Natural interaction metaphors for functional validations of virtual car models[END_REF]; [START_REF] Wexelblat | An approach to natural gesture in virtual environments[END_REF]; [START_REF] Jacobs | A generalized Godobject method for plausible finger-based interactions in virtual environments[END_REF]; [START_REF] Hilliges | HoloDesk : Direct 3D Interactions with a Situated See-Through Display[END_REF]].

Using the hand as an interaction metaphor results from an interest in applying the skills, dexterity and naturalness of the human hand directly to humancomputer interfaces. Such metaphors are typically achieved either by detecting the hand through computer vision-based algorithms or by wearing-specific devices such as gloves [START_REF] Sturman | A survey of glove-based input[END_REF]]. However, [START_REF] Wang | Real-time hand-tracking with a color glove[END_REF] recently proposed a solution combining both technologies to provide simple and accurate real-time hand tracking for desktop VR applications, using only one camera and a color glove with a specific pattern. They demonstrate the validity of their solution through typical applications such as virtual assembly or gesture recognition. We are interested in fully immersive setups, and thus will focus on finger tracking technologies with high-range detection. [START_REF] Sturman | A survey of glove-based input[END_REF] and [START_REF] Dipietro | A survey of glovebased systems and their applications[END_REF] provide thorough surveys of such devices and their applications in various fields, such as design for construction or 3D modeling, data visualization, robot control, entertainment and sign language interpretation, while the health sector shows an increasing interest in such interfaces for motor rehabilitation (hand functional assessment), ergonomics or training.

The addition of physics simulation to DM provides truly intuitive interaction with the objects in the scene. Such approaches for interface design have received much interest in recent years, often linked with tabletop systems [START_REF] Agarawala | Keepin' it real: pushing the desktop metaphor with physics, piles and the pen[END_REF]; [START_REF] Wilson | Bringing Physics to the Surface[END_REF]]. The use of physics simulation to provide natural feedback in the environment has also been of great interest in VR research. One remarkable early result was that of [START_REF] Fröhlich | Physically-Based Manipulation on the Responsive Workbench[END_REF], which demonstrated the use of a fast physics solver and handbased interaction, in the context of a workbench environment. The physics solver presented was one of the first providing sufficiently fast simulation to allow realistic interaction. A major difficulty is how to handle objects controlled by the users hands (often called God-objects, sometimes referred to as kinematic objects; they can apply forces to dynamic objects in the scene, but no object can affect them) with respect to the simulation of the rest of the environment, i.e., correctly providing external forces from the hands.

Over the last 10 years, both physics simulation solutions and gesture-based input hardware have progressed immensely, providing the ability for much more accurate simulation. Much previous work concentrates on the more technical aspects of gesture recognition and its integration with physics, and often includes the calculation of forces for haptic forcefeedback systems [START_REF] Ortega | A six degree-offreedom god-object method for haptic display of rigid bodies with surface properties[END_REF]]. Initial work, before physics simulation became widely available, focused on the definition of appropriate gestures for certain kinds of operations, and notably grasping [START_REF] Ullmann | Intuitive Virtual Grasping for non Haptic Environments[END_REF]].

Experiments with force-feedback systems allowed the simulation of several quite complex manipulations [START_REF] Hirota | Dexterous object manipulation based on collision response[END_REF]]. A spring model coupled with a commercially available physics simulator was used in [START_REF] Borst | Realistic virtual grasping[END_REF] to simulate various kinds of grasping operations with objects of varying complexity and to avoid hand-object interpenetrations. A simpler approach was proposed by [START_REF] Holz | Multi-Contact Grasp Interaction for Virtual Environments[END_REF], where grasping is simulated without complex physics. Grasping and interpenetration were also the focus of the work by [START_REF] Prachyabrued | Visual interpenetration tradeoffs in whole-hand virtual grasping[END_REF].

In [START_REF] Moehring | Natural interaction metaphors for functional validations of virtual car models[END_REF], DM was used based on grasping heuristics and constraint-based solutions for the specific case of a car interior. Their approach is based on an analysis of the types of objects, their constraints and the typical grasps to derive a set of pseudophysical interaction metaphors. A quantitative comparison to a real-world car interior (mirror, door, etc.) was performed. More recent work has concentrated on developing appropriate soft models [START_REF] Jacobs | A soft hand model for physically-based manipulation of virtual objects[END_REF]] and efficient solvers to avoid interpenetration of God-objects and other objects in the scene [START_REF] Jacobs | A generalized Godobject method for plausible finger-based interactions in virtual environments[END_REF]], mainly in the context of automotive project review. The latter uses a setup similar to ours, with the same finger tracking system; however, a three-sided display system is used, with the floor projection from above. Usability and presence were not studied in this work.

The use of consumer-level depth sensors also opens numerous possibilities for natural interaction with collocation of virtual hands and a virtual scene, albeit in a limited workspace subject to various system constraints, e.g., the need for a split screen setup and the limited range of the depth sensor [START_REF] Hilliges | HoloDesk : Direct 3D Interactions with a Situated See-Through Display[END_REF]]. Our 4-sided IC also allows hand collocation and interaction, but does involve a number of hard constraints related to the geometry of the IC and the design of the tracking system. In particular, the three surrounding walls restrict the possible positions for the trackers and result in relatively large regions of shadow for the tracking system.

Our focus will be on presence, usability and user satisfaction when using DM in fully immersive environments. Some recent work exists for example on the effect of using physics on task learning [START_REF] Aleotti | Physics-based virtual reality for task learning and intelligent disassembly planning[END_REF]] or the use of natural interaction for video games [START_REF] Mcmahan | Evaluating natural interaction techniques in video games[END_REF]]. [START_REF] Heumer | Grasp recognition with uncalibrated data gloves -a comparison of classification methods[END_REF] proposed to evaluate recognition methods through classification to avoid the calibration of gesture-based input devices. However, the study of usability for DM in general tasks and in a fully IC-like environment with walking users has not received much attention. Our goal is to compare DM to the use of a wand and to real-world manipulations, in the challenging context of full immersion, which allows a close-to-natural interaction with the environment.

A heuristic approach for direct manipulation with physics

There are several difficulties in developing a DM interface in an IC-like environment. In contrast to systems with a restricted workspace, in which the user is sitting [START_REF] Prachyabrued | Visual interpenetration tradeoffs in whole-hand virtual grasping[END_REF]; [START_REF] Hilliges | HoloDesk : Direct 3D Interactions with a Situated See-Through Display[END_REF]], a room-sized environment is targeted, and the user is allowed to walk around the scene while manipulating objects. There are three main difficulties discussed below: finger tracking, dynamic constraints between objects and the physics simulation.

First, finger tracking in the IC is challenging. Even though a high-end finger tracking system is used (Sect. 4.2), it is prone to noise and interruptions in the signal for the fingers. In addition, a freely walking and moving user can often be in, or close to, shadow regions of trackers where the signal is deteriorated. This is due to occlusion from the user himself, and tracking calibration which is also hindered by the enclosing walls and the user occlusion. Tracking shadow regions thus occur in the zone 1020 cm away from the screen. To overcome these issues, our tasks are designed to avoid activities where the users body blocks the tracking cameras or involves objects in the shadow regions. Our treatment of finger tracking and tracker signal filtering is detailed in Sect. 3.1.

Second, given our goal of assessing feasibility of DM, users are asked to perform relatively complex tasks: grasping and translating objects, including balancing objects one on top of the other while walking. In previous work, users often manipulate a single dynamic object per hand, with simple constraints, e.g., collision detection with static objects. In contrast, our tasks involve several dynamic objects and multiple indirect constraints from physics-based interactions between objects. This requires the robust tracking and grasping solutions developed.

Third, our tasks require the use of a fast physics engine; we use Bullet1 (see Sect. 3.4 for details), which is fast enough to handle quite complex scenes in real time (e.g., our user experience scene in Fig. 14. Due to the low light condition in the IC, photos were taken with a long exposure which results in some blur in the photographs). Bullet uses an impact-based simulation approach. As a result, objects tend to bounce between the fingers instead of being grasped, and the contacts are unstable. Many recent solutions improve physics simulation, most notably to avoid interpenetration of the hand and other objects in the scene [e.g., [START_REF] Jacobs | A generalized Godobject method for plausible finger-based interactions in virtual environments[END_REF]; [START_REF] Prachyabrued | Visual interpenetration tradeoffs in whole-hand virtual grasping[END_REF]], while other approaches [START_REF] Ullmann | Intuitive Virtual Grasping for non Haptic Environments[END_REF]; [START_REF] Holz | Multi-Contact Grasp Interaction for Virtual Environments[END_REF]] avoid the need for complexand often expensiveprecise simulation using specific algorithms . In contrast, a fast but simple physics simulation is used, combined with an approach for basic DM such as grasping and releasing, and a finite-state machine to handle sequences of manipulations (e.g., moving from one-hand to two-hand grasping, etc.). (Fig. 1).

In addition, the physics simulation requires careful synchronization with the displays. The simulation is run on one machine, the transformation information of all dynamic objects is propagated to all slaves at each frame. The solutions adopted to address these problems are next discussed.

Finger tracking and signal filtering

The user is presented with a representation of the palm, thumb, index and middle fingertips in the form of small white cubes, providing visual feedback of hand position and orientation (see Fig. 2,left). Cubes are used for efficiency; they are mostly hidden by physical fingers, and thus did not interfere with interaction. In the following, only the thumb and index of each hand are used; these are called active fingers; the middle finger is ignored in our current implementation. Two active fingers proved to be largely sufficient to provide a natural-feeling DM interface, as seen in the evaluation.

When grasping with one hand, the main contacts are the actual contacts of the thumb and index with the object. When grasping with two hands, there is one main contact per hand. This is the actual contact between the finger and the object if only one finger is applied, or a "mean contact" if two fingers are applied with this hand. The "mean contact" is set at the midpoint between the two actual finger contacts and is useful for the grasp/release finite-state machine described next.

The finger tracking signal in the IC lacks precision involving noise ("trembling") and loss of signal ("jumps"). A Kalman filter is applied to each finger in time and we track the variance of the signal over a sliding window. If variance is above a threshold, we test if there is a plateau in the signal, in which case we identify this as a loss of signal and do not apply the motion to the object.

Grasp/release heuristics

The physics engine is directly used to simulate the manipulations in the environment. Cubic objects are attached to the fingertips and the top of the palm. These are "kinematic objects" in Bullet terminology and can apply forces to the other dynamic objects being simulated. Kinematic objects are not affected by other objects. For each object, contact events with the fingers provided by the physics simulation are tracked. Once two kinematic contacts on a given object are identified, the object is marked as "grasped," until the contacts are released. Grasped objects are removed from the physics simulation, and the transformation and speed of the trackers are enforced so that the simulation of objects in contact with the object selected is still correct.

When grasping, specific data are stored (e.g., position and orientation of the selected object), called grasping data, which is reset each time the number of contacts on the object changes. These data are used to compute the transformations of the selected object, depending on the fingers movements.

If we simply use the information from the tracker and the physics engine, users "drop" objects very quickly, or objects may move in an unstable manner. The selection is made more robust by marking an object as "released" only when the distance between the contacts is >10% of the distance stored in the grasping data. It is important to understand that contacts are determined by the physics engine in a natural manner when treated with our approach; they are not "pinch"-like gestures as the selection is determined by the actual contacts and distance between contacts and not by the movements (see Fig. 4). If a hand participates in holding an object by applying a single finger, it releases as soon as the distance between the two main contacts is 10% longer than that stored in the grasping data. These thresholds have been chosen by pilot trial-and-error tests in several different settings. While releasing, the object being handled follows the translation of the midpoint between the two main contacts. Accurately placing objects thus requires a short learning period (see the video and Fig. 3 for an example). However, users did not complain about this limitation. The threshold for release is the main restriction of our approach in terms of "naturalness." If a user grasps a "thick" object with one hand, it is not possible for her to directly release it in the current implementation if she cannot open her hand by at least 10% of the current gap. To release the selected object, the user would need to switch from a onehanded grasp to a two-handed grasp to reset the grasping data and then release the object. This scenario did not occur in our tasks (Figs. 4,5).

As mentioned before, selected objects are not handled by the physics simulation. The translation applied is that of the midpoint between the main contacts, and the rotation applied is that of the vector defined by the main contacts. When released, the objects are reinserted into the physics simulation.

Finite-state machine for object manipulation

When performing complex tasks, users naturally grasp and release objects, and often mix one-and two-handed manipulations. To treat such transitions, a finite-state machine approach is designed. The different possible transitions for each manipulation are next described.

Grasp

An object is grasped when the user applies at least two fingers on it, with only one hand or both hands (see Fig. 6, left). The user can switch from a one-handed grasp to a two-handed grasp by touching the object with one or both active fingers of the second hand.

There is no alignment test on contacts, so users could lift an object with two contacts on the same side of a cube. However, this would be unnatural, and no user attempted this gesture in our tests.

Release

An object is released when there is at most one finger in contact with the object. For a grasping hand to release the object, the user simply has to open her fingers (see Fig. 6, right). If one or both hands are grasping just by applying one of their active fingers, the user simply has to remove these hand(s) from the object. If both hands are grasping, the user can switch to a one-handed grasp by opening one hand. Finally, to completely release an object grasped with two hands, the user must spread her arms to ensure that the fingers are no longer in contact with the object.

The full list of possible transitions is provided in Fig. 5.

Translate

The grasped object is translated when the fingers in contact translate.

2-handed grasp 4 contacts

No contact or 1 contact 2-handed grasp 3 contacts 2-handed grasp 2 contacts 1-handed grasp Fig. 5 Finite-state machine graph detailing transitions between grasping and releasing states. A representation of the hand is shown in green; dots represent fingers. When only one active finger is touching a dynamic object, the corresponding dot becomes plain green. When two active fingers the same hand are grasping an object, the corresponding dots turn blue. When the object is grasped with both hands, the dots in contact with the object become red.

Rotate

The grasped object is rotated as soon as the fingers in contact rotate. The rotation with two hands is currently limited to simplify the implementation, avoiding problems with the combined effect of tracker noise on each hand: the user can rotate one hand with respect to the other (e.g., tipping out balls from a tray).

The user can switch from a one-handed grasp to a twohanded grasp and vice versa; two one-handed grasps can be used at the same time to manipulate two distinct objects (Fig. 7, right).

Implementation

Color coding is applied to the representations of fingertips. By default, the cubes are white. When only one active finger is touching a dynamic object, the corresponding cube becomes green. When two active fingers of the same hand grasp an object, the corresponding cubes turn blue. When the object is grasped with both hands, the cubes in contact with the object become red. We use our in-house VR software system which is based on OpenSceneGraph. 2 The Bullet Physics open source physics engine has been adapted to communicate the data needed by our grasping/release approach and our finite-state machine through extra object properties, as the transformations of the handled objects are enforced coherently with those controlled by the physics simulation. The interocular distance is calibrated, as well as YZ positions of the eyes for each participant at the beginning of each experiment. This provides a much better immersive experience in the IC by improving the projection from the users point of view (Sect. 4.2). This is also more comfortable for the user as it is expected to reduce the risk of cybersickness.

User study

Our goal is to evaluate whether DM is a feasible alternative to traditional interaction interfaces such as wands, whether it affects presence, and how similar it is to real-world manipulations. To provide a meaningful evaluation of feasibility, a complex task has purposely been chosen, which involves quite complex translations and rotations, while walking and balancing objects on a tray (see Sect. 4.3 for details). By complex task, we mean a task requiring the users attention as it combines several aspects of everyday movements, such as accuracy and balance, such that the task is difficult to perform. We do this evaluation by comparing DM to a traditional wand-based interaction and by comparing both the wand and DM to a real-world task: the virtual world used is a replica of a real space in which the same tasks are performed (Fig. 12). Our hypotheses are as follows: 1) using the wand will be more precise and faster than finger tracking based manipulation and 2) using finger tracking based DM will be more natural and will provide a higher sense of presence.

Both objective measurements, namely time to complete a task and precision or errors, and subjective judgments based on a questionnaire are recorded.

Population

The experiment has been run with 18 participants, 10 men and 8 women aged between 24 and 59 years old, (mean age 32.5 years, standard deviation 10.7 years). Most had no experience with virtual reality (13 out of 18); 5 had experienced VR demonstrations before. Four participants had previously used a wand, including three who had previously manipulated virtual objects.

Experimental apparatus

A four-sided IC (the Barco iSpace3 is used, comprising three walls and a floor, which has four retro-projected "black" screens. The front and side screens are 3.2 m wide 2.4 m high, and the floor is 3.2 m wide 2.4 m long. Stereo is provided using Infitec technology, and for tracking, an ART4 infrared optical system is used, with eight cameras (see Fig. 8, left). The head is tracked with a frame mounted on glasses. The tracked devices provided are the wand and the finger tracking system of ART to track the palm, thumb, index and middle finger of each hand (see Fig. 8, right). The finger tracking system tracks the tips of the fingers giving the relative positions of these frames with respect to a 6DOF active tracker which is on the back of the hand. Normally, six cameras are sufficient for head tracking. However, to allow better quality finger tracking and reduce "shadow" regions, two additional cameras were added. As these cameras must be placed in the bottom front corners of the IC and the cables connecting them to the system are visible in certain areas of the side walls, this can affect the users immersive experience. Our scenarios were thus designed to avoid eye gaze on these areas as much as possible, and our models were also designed to hide the cables and the cameras by adding very dark baseboards to the room.

Wand interaction

For the wand, a standard virtual ray emanating from the wand is used. To grasp an object with the wand, the user points the wand toward it and presses a trigger button. Small blue spheres are displayed at contact points between the ray and the object when grasping (Fig. 2, right). The trigger is kept pressed during manipulation. To release an object with the wand, the user simply has to release the trigger.

The ray has been implemented to be thin to limit occlusion and to be long enough (1 m) to allow sufficient coverage of the 3.2 m 3.2 m 2.4 m IC.

Experimental procedures and environments

The experiment lasted 90 min on average. As every participant performed all the tasks, it is a within-subject design. The experiment consists of a calibration step, a training session, a usability test, a "free form" user experience and a questionnaire completion. The usability evaluation has three conditions: using the wand, DM, and the real-world condition. Hence, we had six groups of three participants to test all the possible orders of conditions, which were randomized. For DM and real, the users always performed the tasks first with two hands and then with only one hand. We decided not to vary this order within the conditions using hands to permit the user to learn progressively. Specifically, when handling larger objects such as a tray, using two hands provides better control and balance overall. In contrast, using one hand involves grasping the border of the virtual tray; slight motion of one finger with respect to the other can result in a large motion of the tray, making it harder to control. In the design of all tasks, we tried to minimize the cases of the hand incorrectly occluding virtual objects; evidently this is not always possible, but we did not receive any negative feedback about this from participants.

The training session and the free-form user experience session are not performed in the real condition, but the order of the other conditions is the same as in the usability task. Concerning the DM, training session and the usability task are performed with two hands and one hand separately, whereas in the user experience, the user can freely manipulate objects with one or both hands. The best way to appreciate these experimental procedures is to watch the accompanying video.

Calibration step

The finger tracking devices are calibrated for each user so that the signals are more reliable. Both devices are calibrated separately to avoid interference, using the procedure defined by the manufacturer. The position of the eyes is also calibrated. A pilot test has been performed where the interocular distance was simply measured and set: this proved to be insufficient since the environment still displayed a "swimming" effect. To overcome this, the other two coordinates of the eye positions are also adjusted (see Fig. 9). This is done using a simple scene, i.e., a floor and a stool (see Fig. 10,left). The experimenter progressively modifies the coordinates of the eye positions until the cubes representing the fingers are closer to the fingertips and the user feels comfortable with the projection. A subsequent step consists in modifying values to minimize perceived movement of static objects when moving in the IC.

Training session

The goal of the training session is to familiarize the participant with the interaction techniques. The experimenter first explains the color coding of the cubes and how to use the techniques to grasp, release and move the objects.

To maximize immersion, the virtual scene consists of a closed room exactly the size of the actual IC, with two tables, and three cardboard posts in between (see Fig. 10,right). On the left table, the user is provided with a colored cube and a tray containing two balls. There are red crosses marked on the tables: one under the cube on the left table, and two on the right table which serve as targets (see Fig. 11,left). The experimenter demonstrates the movements in the IC before the training session starts, explains that an alarm sounds when the tray or hands hit the posts, and asks the user to test this. The goal of keeping as many balls as possible on the tray is explained, and that the participant should avoid hitting the posts with the tray or hands. The participant starts the training by lifting the tray off the table. The tray must then be rotated by 90 • , passed between the two first posts, rotated again by 90 • and passed between the two second posts before being released on one of the tables (preferably the one on the right). The user can then repeat these steps and try other movements until she feels comfortable with manipulating the tray. Time and trials are not restricted during the training session.

Once this is done, the user ends the session by placing the colored cube onto the red crosses in a specific order. The experimenter explains that the sound heard when the cube touches the marks means that the subtask is validated, and that the same sound will be used when validating a subtask in the following session.

Once the session is complete, the scene is reset so that the user can train with the other technique (wand or DM), and when it is complete for the second time, the next session is automatically loaded.

The tray and the cube are manipulated with the wand and one hand; the tray is also manipulated with two hands.

Usability task

Usability is evaluated in a single task which tests all the manipulations.

The main evaluation scenario takes place in the same virtual room as in the training session; only this room contains a stool on the left, the same table on the right, the same three cardboard posts in between and a cupboard in the back. Again, the virtual scene has the exact size of our four-sided IC. A tray with nine balls is placed on the stool. There is also a bowl on the front half of the table (see Fig. 12,left).

This session is also performed in real conditions: the same scene has been built in the vicinity of the IC (see Fig. 12, right). The experimenter first explains the entire task to the user by mimicking the required operations at the beginning of each condition, insisting on the order of the steps. The beginning and end of each subtask is determined automatically by the system. The task is composed as follows (see Fig. 13): -Subtask 1: The user grasps the tray and passes between the two sets of posts after rotating the tray by 90 • each time, and then releases it on the table. The participant is instructed to avoid dropping balls as well as to avoid touching the posts with the tray or the hands (see Figs. 13 a,b,11,right). -Subtask 2: The user lifts the tray off the table and empties it into the bowl before releasing it on the table again. The user is instructed to keep as many balls as possible into the bowl (Fig. 13 c). If the tray is empty at the end of subtask 1, this subtask is skipped. -Subtask 3: The user picks up the empty tray again and places it inside the cupboard (Fig. 13 d).

This task is quite challenging, even in the real world. Notice that the first subtask corresponds to what the user already had to do in the training session, as this is the most challenging part of the task.

Making real and virtual equally difficult

To compare real and virtual tasks, we need to have approximately the same level of difficulty between the two. However, the physics simulator is only approximate in terms of material properties (friction, etc.) and handles dynamics with impulses which can sometimes be unrealistic. For a fair comparison, a pilot test with four participants who performed the task of balancing the tray avoiding the posts and minimizing the number of balls dropped has been carried out before the actual experiments, in both the real and virtual environments. Difficulty is measured by counting the number of balls dropped. The adjusted parameters are the height of the borders of the virtual tray and the type of the real balls.

Because of the impulses, virtual balls tend to bounce more on the tray in the VE than those in the real world. The borders of the virtual tray have thus been increased. In addition, the real balls had different friction so two ball types were mixed: ping-pong balls and foam balls. The pilot test showed that equivalent difficulty level between real and virtual tasks is obtained with a tray border raised to 3/4 the height of the balls, and mixing 3 foam balls and 6 ping-pong balls. This configuration has been used in all experiments.

User experience

The free-form user experience session corresponds to a qualitative observational evaluation, to see what the user will do with almost no instruction.

The scene is a dining room, with a cupboard, shelves and a table. The table is empty, and plates, glasses, forks and knives for six people are placed in the cupboard on the left and on the shelves in the back (see Fig. 14).

The user is introduced to the scene and receives no other instructions than "you have 4 min to set the table as best as you can." Our goal is to observe general behavior, i.e., whether participants use one or two hands, whether they Fig. 14 User experience scene: Left; at the outset, the table is clear. Right; at the end, the table is set with plates, cups and cutlery.

focus on completely setting the table or correctly placing objects, the order of setting the table, etc. We are interested in observing whether participants behave naturally, e.g., walk around the virtual table, catch falling objects, etc., as well as their degree of presence.

Measurements

In each session, head position and orientation of the users at each frame are recorded. The position and orientation of the fingers and palm, as well as the time to complete each task and subtask are also recorded. Every object collision and ball dropped are also recorded. The sessions were videotaped, and the completion times for the real environment were manually extracted.

Objective metrics

During the usability task, accuracy is measured by recording the following: (1) position of the tray with respect to the posts to make sure that the user does pass the tray between them; (2) number of times the tray touches the posts; (3) number of times the hands touch the posts; (4) number of balls remaining on the tray when releasing the tray onto the table ; (5) number of balls inside the bowl after emptying the tray.

Subjective measurements

At the end of the experiment, participants complete a questionnaire. For each technique in virtual conditions (wand, one hand and two hands), they are asked to rate various criteria on a Likert's scale between 1 and 7. We evaluate: ease of use, fatigue caused by using the technique, sensation of "being there," plausibility of the interaction with the environment and reaction of the environment to actions, similarity to the real condition (for one hand and two hands), precision, naturalness and cybersickness. Participants are also asked to rate the similarity of each virtual task to the real task. Then, they have to answer open questions related to their strategies for using the interfaces, and their opinion on advantages, drawbacks and difficulties of each interface. Finally, they are free to make additional comments. For further detail, please refer to the questionnaire in supplemental material.

Results

The statistical analysis of the results for both our objective measurements, i.e., speed and errors, and the responses to our subjective questionnaire is next presented. For the completion times, a Shapiro's test has been performed that rejected the normality hypothesis on the data distribution. Thus, a non-parametric Friedman's test for differences among the conditions has been used. Post hoc comparisons were performed using Wilcoxon's signed-rank tests with a threshold of 0.05 for significance.

Objective measurements

A Friedman's test has first been performed on the time performances between the 5 conditions, i.e., 1-and 2-handed real, 1-and 2-handed DM and the wand. The following abbreviations are used: R1H and R2H are real one and two-handed conditions respectively, and DM1H and DM2H are virtual DM one and two-handed conditions respectively. The reported p values were adjusted for multiple comparisons. A significant effect (χ 2 = 4.62, p < 0.001) of condition has been found. Post hoc analysis revealed that the time to complete the task was significantly lower for R1H with a median time to completion of 61.33 s compared to DM2H where time to completion was 113.8 s (p < 0.001). The time for R2H (median = 65.67 s) was significantly lower than DM1H (median = 86.95 s, p = 0.04), DM2H (p < 0.001) and wand (median = 88.86 s, p = 0.04). No significant effect was found between virtual conditions. Fig. 15 Significant "lower than" relationships between conditions for objective measurements.

Errors were measured in two manners: First, the number of balls lost throughout the task, and second, the number of times the tray or the hands hit the posts in the virtual tasks. Real and virtual conditions for both criteria are also compared.

A Friedman's test has been performed for the number of lost balls during the task. A significant effect of condition (χ 2 = 3.35, p = 0.007) has been found. The number of lost balls was significantly lower for wand compared to R1H and DM1H (p = 0.007 and p = 0.01, respectively), as revealed by post hoc analysis.

Finally, a Friedman's test has been performed for the number of hits during the task. The test revealed a significant effect of condition (χ 2 = 5.32, p < 0.001). The number of hits was significantly lower for R1H compared to all virtual conditions as shown by post hoc analysis (p < 0.001 for DM1H, p = 0.02 for DM2H and p < 0.001 for wand). The number of hits was also significantly lower for R2H compared to all virtual conditions (p < 0.001 for DM1H, p = 0.003 for DM2H and p < 0.001 for wand). No significant effect has been found between the virtual conditions.

Those results are summarized in Fig. 15 which shows "lower than" relationships between conditions for each parameter when it is significant.

Subjective questionnaire

For the responses to the subjective questionnaire, a Friedman's test has been performed for the different criteria between the three virtual conditions. No significant effect has been found for Plausibility for the usability task, Being there Fig. 16 Significant "lower than" relationships between conditions for subjective measurements.

for the user experience and Cybersickness. A significant effect has been found for 7 criteria: Ease of Use for the usability task (χ 2 = 4.95, p < 0.001), Being there for the user experience (χ 2 = 2.69, p = 0.02), Plausibility for the user experience (χ 2 = 2.54, p = 0.03), Fatigue (χ 2 = 4.27, p < 0.001), Similarity with real experience (χ 2 = 3.24, p=0.003), Precision (χ 2 = 4.35, p < 0.001) and Naturalness (χ 2 = 2.70, p = 0.02) (See Figs. 16,17). Post hoc analysis showed that wand was preferred to DM1H and DM2H for Ease of Use during the usability task (p < 0.001 and p = 0.003, respectively), Fatigue (p < 0.001 and p = 0.007, respectively) and Precision (p < 0.001 for both). In contrast, DM1H and DM2H conditions were significantly better rated than wand for Being there for the user experience (p = 0.04 and p = 0.02, respectively). The two hands condition was preferred to wand for Plausibility for the user experience (p = 0.03), Similarity with real experience (p = 0.003) and Naturalness (p = 0.02).

Those results are summarized in Fig. 16 which shows "lower than" relationships between conditions for each parameter when it is significant.

Discussion

Our goals were to evaluate the feasibility of DM in a fully immersive space, and its effect on presence as well as the similarity to real-world manipulation. We hypothesized that the wand would be more precise and efficient than DM, but we believed that DM would positively affect the sense of presence. The experimental results support these hypotheses.

Concerning the first hypothesis, the results show that all virtual tasks took longer than the real-world task and that the wand and DM are equivalent in terms of speed (even though the two-handed DM condition had a longer median completion time). We take this as an encouraging indication that DM does not penalize speed. However, as a general remark, it also indicates that for such complex tasks involving balance

Natural Interface

Fig. 17 Boxplots of the statistical results for some of the most interesting studied criteria. Each boxplot is delimited by the 25% quantile and 75% quantile of the distribution of the effect over the individuals. The median is also represented as a red line for each effect.

and rotations, we are still not at the point where virtual tasks can be performed at the same speed as their real equivalent.

In the real scene, the user is influenced by the kinesthetic perception (of touch, weight and muscle tension) which guides balance of the tray but increases fatigue. In contrast, this sense is missing in the virtual setting; note, however, that current solutions for haptics in ICs are unsatisfactory, and we thus chose not to opt for such a solution.

In terms of accuracy, users dropped fewer balls using the wand than with the one-handed virtual DM, as well as with the one-handed reallife condition. There was no significant difference with the two-handed DM, real or virtual. Evidently, the wand is a "hyper-natural" interface in the terminology of [START_REF] Bowman | Questioning naturalism in 3d user interfaces[END_REF], so it is unsurprising that it allows better performance than the real world in some cases. The fact that this occurred for the one-handed case rather than two hands is due to the inherent difficulty of the one-handed condition: the tray is a relatively long object, and a small movement of the fingers of the holding hand can result in a large movement of the tray, and thus, a loss of the balls. When using two hands, the tray is more stable. The above observations are true for the virtual setting, but also for the real tasks; several participants complained that the one-handed real task was hard and tiring.

The above two results for speed and accuracy indicate that the virtual DM is a feasible alternative for interaction. There is also an indication that DM could be considered better for applications such as training since performance is closer to the real world than the wand which augments interaction capabilities of the user.

The participants found the wand easier to use and less tiring. We also noticed that users subjectively considered the wand to be more precise than the DM even if the objective performance did not always confirm this, notably in terms of hitting the posts. Again, the "hyper-natural" aspect of the wand is a plausible explanation for this perception and this discrepancy.

For the user experience, participants rated the sense of being there to be higher for hands (both one and two-handed) compared to the wand. In informal interviews after completing the study, participants explained that in the usability task, they were so concentrated on completing the task that they did not pay much attention to the environment; this was not the case, however, for the user experience, where there were no constraints. Similarly, two hands were rated higher than the wand for the sense of plausibility, again in the user experience. We believe that this is not the case for the one-hand case because of the lack of precision when manipulating objects, as explained above.

The above results on the subjective ratings show that our DM interface does have an effect on the two components of presence, plausibility and being there [START_REF] Slater | Place illusion and plausibility can lead to realistic behaviour in immersive virtual environments[END_REF]]. In addition, for the two-handed case, participants perceived them as more natural and closer to the real experience than the wand. We believe that these are encouraging results, which support our hypothesis that DM can improve the sense of immersion in such VEs and provide an experience that is closer to reality than using more traditional device-based interfaces.

We also observed participants behavior informally, which revealed several interesting cases of their reactions to our VE. Some of these are illustrated in the sequences of the accompanying video. The IC offers a high level of immersion in and of itself; for example, participants attempted to place the wand on the virtual tables at the end of the different sessions. However, users tended to avoid walking through the virtual objects when they used their hands. In several cases, participants tried to catch the dropping objects as an automatic reaction when using DM. During the user experience, participants tended to place the objects in a specific order, as they do in real life: They begin with the plates, then the glasses, and they finish with the forks and the knives. Participants also tend to develop strategies to use the different techniques in the user experience. When using the wand, participants would stay in a convenient place to pick and place objects from a distance. However, they found it harder to rotate the objects, although different techniques for rotation could be implemented to alleviate this problem. When using DM, they used both hands to adjust the orientation of the plates; otherwise, they used both hands to pick two objects separately, and thus can set the table faster. These behaviors witness the immersion of our VE, as people behave as they do in real life.

Our results show that, even if the wand outperforms DM in terms of usability, our finger-based DM interface conveys a high sense of presence and naturalness. We also believe that improved tracking technology and possibly the use of five fingers will allow our approach to outperform the wand, while increasing difference in presence between the two.

Conclusions and future work

In this paper, a complete system has been presented which integrates DM with real-time physics in a fully immersive space, allowing close-to-natural manipulation of objects in a VE. Interaction is based on the physics engine, enhanced by a heuristic approach to manipulate objects. Users can thus perform moderately complex tasks, involving translations and rotations of objects and maintaining balance while walking.

A first user study has been performed, which included a usability task, and a free-form user experience task. Our DM has been compared to the traditional wand, and for the controlled setting, the virtual task has been replicated in the real world. Both the objective measures (speed, accuracy) and the responses to the subjective questionnaire indicated that DM is a feasible alternative to the more traditional wand interface. The results of our study also indicate that in several cases, especially when using two hands, the use of DM enhances the sense of presence in the VE and is perceived as being closer to reality.

In this study, feasibility of DM has been examined, leading us to test relatively complex tasks. Given that the feasibility of the interaction with DM is now quite clear, it will be interesting to examine the different parameters of our system in separate, more specific studies. An interesting direction to future work would also involve the use of a full hand model with complete tracking, similar to [START_REF] Hilliges | HoloDesk : Direct 3D Interactions with a Situated See-Through Display[END_REF], which, however, requires improvements in depth sensor technology before becoming realizable.

Fig. 2

 2 Fig. 2 Left visual representation of the palm and three fingertips in the VE (cubes are shown away from the fingers for clarity of illustration). Right wand selection used for comparison.

Fig. 3

 3 Fig. 3 Accurately placing a cube in a corner.

Fig. 4

 4 Fig. 4 User spreads her arms to release a large object without the need to further open her hands.

Fig. 6

 6 Fig. 6 Left two-handed grasp. Right two-handed release.

Fig. 7

 7 Fig. 7 Left one-handed grasp. Right two hands grasping two objects.

Fig. 8

 8 Fig. 8 Experimental setup. The four-sided IC is represented in a) with its eight infrared cameras. On the right are photos of the tracked input devices used: b) Infitec glasses with frame, c) ART flystick and d) ART finger-tracking gloves.

Fig. 9

 9 Fig.9Position of the user's eyes is calibrated in the three dimensions.

Fig. 10

 10 Fig. 10 Left calibration scene. Right training scene

Fig. 11

 11 Fig. 11 Left in the training session, target crosses are used to guide the participants. Right usability task scene contains posts: the user passes the tray through them.

Fig. 12

 12 Fig. 12 Left virtual usability environment. Right real usability space.

Fig. 13

 13 Fig. 13 Subtasks of the usability task (see text).

http://www.bulletphysics.org

http://www.openscenegraph.org/

http://www.barco.com/en/products-solutions/visual-displaysystems/3d-video-walls/multi-walled-stereoscopic-environment.aspx

4 http://www.ar-tracking.com

Acknowledgements

The authors wish to thank Rachid Guerchouche for his help in many aspects of the project, also Theophanis Tsandilas, Martin Hachet, Anatole Lecuyer, Peter Vangorp and Sylvain Duchêne for their help and their useful comments. We also thank all the participants of the study. This work was supported in part by the Regional Council of Provence Alpes-Côte dAzur and the EU project VERVE (http://www.verveconsortium.eu). The textures in the VEs come from the following websites: http://archivetextures.net, http://www.freestockphotos.biz, http://www.flickr.com, http://www.defcon-x.de, http://www.public-domain-image.com, http://images.meredith.com, http://onlyhdwallpapers.com, http://www.merveilles-russie.com and http://www.zastavki.com.


Alexandre Bilger

Éric Bardinet

Sara Fernandez-Vidal

Christian Duriez

Pierre Jannin

Stéphane Cotin

Intra-operative Registration for Deep Brain Stimulation Procedures based on a Full Physics Head Model

Brain deformation is a factor of inaccuracy during stereotactic neurosurgeries. If this phenomenon is not considered in the preoperative planning or intra-operatively, it could lead to surgical complications, side effects or ineffectiveness. In this paper, we present a patient-specific method to update the pre-operative planning based on a physical simulation of the brain shift. A minimization process estimates parameters of the simulation in order to compute the brain tissue deformation matching the partial data taken from intra-operative modalities. The simulation is based on a patient-specific biomechanical model of the brain and the cerebro-spinal fluid. We validate the method on a patient with a post-operative MRI.

Introduction

Targeting structures in sterotactic neurosurgery requires a high precision for the location and definition of the target. For instance, in deep brain stimulation (DBS), one of the main targets to stimulate is a 3 millimeters thick structure, the subthalamic nucleus. However, a combination of deformation and motion of the brain, known as brain shift, can occur during the procedure, depending on the surgical technique and the patient's brain anatomy and pathology. Because of this phenomenon, the target or other structures can be displaced, compared to the pre-operative location. Elias et al. [START_REF] Elias | Cortical and subcortical brain shift during stereotactic procedures[END_REF] reported an anterior commissure shift up to 5.67 mm with a mean of 0.98 mm, and higher shift values for the frontal pole.

Because brain shift is a major source of errors when applying the planned strategy intra-operatively, several groups have studied the problem of brain shift compensation using a deformable model, instead of using a fully intensity-based method. Skrinjar et al. [START_REF] Skrinjar | Model-driven brain shift compensation[END_REF] presented a method to deform pre-operative data according to a partial intra-operative brain surface, captured by a stereo camera, while Chen et al. [START_REF] Chen | Intraoperative brain shift compensation: accounting for dural septa[END_REF] and Audette et al. [START_REF] Audette | An integrated range-sensing, segmentation and registration framework for the characterization of intra-surgical brain deformations in image-guided surgery[END_REF] used a laser range scanner. However the equipment is not standard and requires a large working space without occlusion, which is not the case in DBS procedures. The work of Wittek et al. [START_REF] Wittek | Patient-specific model of brain deformation: application to medical image registration[END_REF] is very similar to [START_REF] Skrinjar | Model-driven brain shift compensation[END_REF] but they used intra-operative MRI to guide the deformable model and took extra care on the complex model of the brain tissue deformation. However [START_REF] Skrinjar | Model-driven brain shift compensation[END_REF] and [START_REF] Wittek | Patient-specific model of brain deformation: application to medical image registration[END_REF] do not model physically the brain shift phenomenon, because they include artificial forces by adding virtual springs or constraints between pre-and intra-operative control points. None of these methods accounts for the effects of gravity, interaction of cerbro-spinal fluid (CSF) and brain tissue and loss of CSF. On the contrary, Chen et al. [START_REF] Chen | Intraoperative brain shift compensation: accounting for dural septa[END_REF] used a computational model which accounts for CSF loss and gravity. They pre-operatively built a statistical atlas of deformation to solve the inverse problem intra-operatively.

We propose a new method to take into account brain shift during a stereotactic neurosurgical procedure. Because brain shift amount depends on many causes, such as the operating protocol or the mechanical parameters of the brain tissue, this variability leads us to deal with patient-specific data. It relies on high resolution pre-operative MR image and intra-operative image (CT scan) of the patient's brain, acquired once the brain has shifted, but the method could be extended to other modalities such as intra-operative MRI. The pre-operative data are deformed according to a physical model of brain shift, mainly based on a (CSF) interaction with the brain tissue, gravity and brain-skull interactions. The input parameters of the brain shift model are estimated intra-operatively with a measure of similarity between a series of pre-computed deformed configurations and the data from the intra-operative image. The deformed configuration that best fits the intra-operative data enables to compute the displacement and deformation of internal structures. With this information, the surgeon is able to update the pre-operative planning data (target coordinates, trajectory angles etc).

The following section describes the brain shift simulation and how we use it to solve the intra-operative registration based on a physical parameters estimation. Section 3 presents the results and the validation on a post-operative MR image of one patient. Section 4 concludes and addresses future steps for the method.

Materials & Methods

Data

Patient data consisted of pre-operative Gadolinium enhanced T1-weighted MRI acquired with a GER 1.5T scanner. Targeting of the basal ganglia follows a pipeline that is similar to the inclusion protocol described in [START_REF] D'albis | PyDBS : An automated image-processing workflow for planning and postoperative assessment of deep brain stimulation[END_REF]. In summary, preoperative 1.5T T1-weighted MRI data from a DBS-eligible patient goes through the following steps: first the AC-PC coordinates are interactively defined; then, the scalp, gray/white matter, and sulci are segmented from the T1-weighted MRI; finally, spatial normalization of the patient data in the atlas space is performed.

Presentation of the model

The patient data are used in a brain shift simulation, relying on a physics-based model of the brain tissue deformation, the contact response with the skull and the falx cerebri, and the interaction with the CSF. All these simulation components are linked together with a mechanism to propagate forces and displacements to the other models. The deformation model imposes its displacements to the others, and forces created with these models (contact for instance) are propagated back to the deformation model. The different models used in our simulation for the brain hemispheres are: deformation, collision, buoyancy, mass and visual.

The brain deformation is computed using a non-linear geometric finite element method, with a linear constitutive law. This allows for rotation in the model, while relying on a linear expression of the stress-strain relationship. Details of the computation method could be found in [START_REF] Felippa | A unified formulation of small-strain corotational finite elements: I. Theory[END_REF]. The viscous part of the brain behavior is omitted, because we focus on the static equilibrium after the brain has shifted. The equation relating the external forces f to node positions x can be written as f(x + dx) = f(x) + K(x)dx, with K the stiffness matrix depending on x. Both hemispheres are meshed independently with linear hexahedral elements for the FEM model. The forces produced by the mass model are computed on a volumic mesh made of linear tetrahedral elements, and propagated to the deformation model.

When the brain deforms, the simulation algorithm solves the contacts with the skull and the falx cerebri, considered as rigid. Unilateral interpenetration constraints are created when a collision is detected. The area near the brainsterm is assigned fixed Dirichlet boundary conditions to impose a null displacement constraint. The constraints are solved with Lagrangian multipliers. Figure 2 shows the boundary conditions and the different models.

The main cause of brain shift is a CSF loss [START_REF] Slotty | The impact of brain shift in deep brain stimulation surgery: observation and obviation[END_REF]. The resulting force of the surrounding fluid acting on the brain tissue acts against the weight, so that the Fig. 2: Schematic representation of the brain model and the set of constraints describing its interactions with the environment. The hexahedral FEM model for deformation is represented by the purple grid and the tetrahedral model for the mass by the pink triangles. In this pre-operative configuration, the patient is in the supine position (see the gravity vector direction g). The cerebro-spinal fluid surrounds the brain tissue and acts on it with pressure forces. The resultant force balances the weight (see the f CSF compared to the weight force mg). The brain is under a null displacement constraint near the brainstem area. The illustration also shows the contacts between the brain and the skull. brain is balanced. A CSF loss causes a fluid forces decrease, breaking the balance and leading to a brain shift. In order to cause a brain shift in our simulation, we include a model of CSF forces:

f CSF = S ρ g h(P ) dS
where ρ is the density of CSF (1000 kg/m 3 ), g is the norm of the gravity and h is the distance between a point P on the mesh and the fluid surface. The force f CSF is applied onto every immersed triangle S of the brain surface mesh. Asymmetric brain shift is observed on post-operative images (see Fig. 1). To handle this property, two independent models of fluid forces are present in the simulation, each acting independently on each hemispheres. With this model, the deformation depends also on the patient's head orientation compared to gravity direction, mechanical properties of the tissue and patient variability.

To recover the true rest configuration of the brain before applying gravity and external forces on the finite element model, we solve an inverse problem using an iterative geometric algorithm [START_REF] Sellier | An iterative method for the inverse elasto-static problem[END_REF]. The algorithm is used with a static solver. The iterations are smoothed to handle the geometrical non-linearities of the deformation model.

Non-rigid registration based on physical parameters estimation

Parameters to estimate As explained in section 2.2, the brain shift model depends on the following parameters: patient's head orientation compared to gravity direction, patient variability (geometry), mechanical properties of the tissue and the amount of CSF lost during the procedure. The two first parameters are known: we can measure the orientation of the patient's head and the geometry is acquired by the segmentation of patient images. The mechanical parameters of the brain tissue have been estimated by several groups using different techniques, but there is no consensus and there is no direct measurement technique personalized for a patient. Although it would be interesting to add the mechanical properties to the parameters to estimate, the deformation is also controlled by the CSF volume lost, meaning that these two parameters cannot be dissociated: the displacement of a material particle, as a function of the material properties and CSF volume lost, can have more than one fiber. We fix the mechanical properties to estimate a unique parameter type, the CSF volume lost. Moreover, the mechanical parameters are not the physical cause of the brain shift phenomenon. Finally, only the CSF volume lost is estimated. As we model both hemispheres independently, two quantities have to be estimated.

Error minimization In our algorithm, the only unknown input parameters are two volumes of CSF lost during the surgery. To estimate these parameters, we introduce a measure of similarity, to compare the final deformed geometry of the brain, obtained at equilibrium after applying a CSF loss in a simulation, and the visible surface of the brain, extracted from an intra-operative modality. The similarity between these two objects is defined with a least-squares approach:

d(S, M ) = x S ∈S x S -p(x S , M ) 2 (1)
with x S a point on the surface S of the intra-operative brain, p(x S , M ) is the projection of the point x S on the surface M of the simulated brain. To compute the projection of a point P on a triangular mesh, we first find the closest point of the surface. P is projected on every triangles around the closest point. We consider only the projections that are inside the corresponding triangle and take the one with minimal distance. If none of the projections are inside the corresponding triangle, we perform this same step on the edges around the closest point. If none of the projections are inside the corresponding edge, we consider the projection is the closest point. The measure is normalized by dividing by the number of points in S, and represents the average distance between both surfaces. The figure 3 shows a representation of such a projection in image space.

Our model is consistent with the correlation between the CSF loss and the amount of deformation, studied by [START_REF] Elias | Cortical and subcortical brain shift during stereotactic procedures[END_REF]. The displacement norm of a point in the brain is an increasing function of the CSF volume lost. This property guarantees the convexity of the error as a function of the two CSF volume losses: a local minimum is a global minimum.

Even an efficient optimization method for our problem would require at least several tens of iterations to converge to an estimation of the parameters. Each Fig. 3: Measure of similarity to be minimized: the triangular surface extracted intra-operatively, represented by a pink contour in this pre-operative axial MRI, is projected on the simulated brain surface (yellow contour). In this example, some points and their projection are depicted with an arrow. The measure is the average distance of projection. iteration requires to compute a direct simulation, which takes time (more than 5 minutes) and therefore is not compatible with an application during a neurosurgical procedure. To speed up the intra-operative computation, we pre-compute before the surgery a set of brain configurations, deformed by a simulated brain shift for a regular sampling of the parameters domain. Then, during the procedure, a mesh is extracted from an intra-operative image with a snake evolution based semi-automatic segmentation of the pneumocephalus, and compared to all the pre-computed deformed configurations. The configuration with the smallest error corresponds to the registered brain.

Finally, the displacement field enables to compute rapidly the displacement and deformation of other structures such as the ventricles, the target or the blood vessels. A summary of the whole process is available in the figure 4.

Results

In this section, we compare the result of our registration method to the preoperative configuration, through a comparison of the blood vessels network. However, the quality of an intra-operative image does not allow to extract a ground truth. To get around this issue, we consider using a post-operative image instead. In the days following the procedure, intracranial air is replaced by the CSF produced and brain tissue shift back to its original configuration. We can consider the displacement has not yet started just after the operation. For this reason, for the validation of our method, we chose to use a post-operative MR image of the patient, where we can segment the structures of interest and compare them with the registered structures. We assume the intra-operative Fig. 4: Steps of our method (read from left to right, then from top to bottom): the acquired pre-operative MRI enables to generate a simulation. A set of deformation is pre-computed. During the surgery, the pneumocephalus is extracted from the intra-operative CT, registered to the pre-operative data and compared to the set of pre-computed deformation. Finally, the displacement of the structures of interest is deduced. Among these steps, the most time consuming processes are done before the surgery. configuration to register and the post-operative configuration of the brain are equivalent. With this assumption, in this section, the intra-operative data of our method are taken from the post-operative image: we only extract air from the image, in the same way as in the intra-operative image. Our method, presented to be applied on CT scans, does not differ with an MRI because air appears as a volume with no intensity in both imaging modalities CT and MRI. In both cases, the pneumocephalus is segmented semi-automatically with an active contour model. Other details from the post-operative image, and not visible in the intra-operative image, are not taken into account in the registration process. However, some structures of interest are segmented in the post-operative image for a comparison purpose (not used during the registration process): the postoperative data follow the same preprocessing pipeline that the preoperative one and is registered on the pre-operative space by a rigid method (FLIRT 6 DoF).

The pre-operative segmented patient brain is used to generate several models for the simulation: the mechanical model is made of 7538 linear hexahedral elements, the model used for mass with 14671 linear tetrahedral elements, the collision model with 2940 triangles, and the model for buoyancy with 2772 triangles. In this study, the Young's modulus E is set to 6 kPa and Poisson's ratio to 0.45.

To estimate the CSF volumes parameters, a set of 169 brain configurations is pre-computed, with parameters varying from 0 cm 3 to 24 cm 3 . A higher number of configurations would result in more precision, but given the computation time, 169 configurations (on a laptop i7-4800MQ CPU) is a maximum for a global time compatible with a clinical use. We believe we can increase this number by optimizing our method. The different configurations are then compared to the intra-operative data, i.e. the brain surface in contact with intracranial air. A score of similarity is computed for each configuration according to the measure described in section 2.3. The minimum score corresponds to the parameters to estimate. The corresponding configuration is a registration of the whole brain. The comparison process on the complete set is almost instantaneous and does not requires any optimization.

The patient used for the validation of the method presents an asymmetric brain shift (See Fig. 1). We notice the right hemisphere has shifted more than the left. This phenomenon is found in the estimated parameters: we estimated that the right hemisphere needed a CSF loss of 18 cm 3 to deform and match the intra-operative data, whereas the left hemisphere needed 12 cm 3 . The average distance computed with these parameters is 2.5 mm for the right hemisphere and 1.8 mm for the left. The following results are based on these estimated parameters.

The displacement field and the shape functions of the FEM model is used to compute the displacement and deformation of internal brain structures. Most of the blood vessels are located in the sulci and if a blood vessel shifts on the trajectory of a stimulating electrode during a DBS procedure, it could lead to an hemorrhage. For this reason, we focus the tests of our method on the sulci.

To compare the different configurations, we use the following measure: A smaller distance indicates more similarity. The distance between sulci in preoperative configuration and post-operative configuration is 2.7 mm. The distance between sulci in the registered configuration and post-operative configuration is 1.3 mm. We conclude our registration method gives a better estimation of the sulci location than using the pre-operative data.

Conclusion

In this paper, we presented a method to register the pre-operative configuration of the brain onto the intra-operative state. The registration is entirely based on physics and handle patient-specific geometry, patient's head orientation and asymmetry in the deformation. The algorithm provides also the physical displacement and deformation of other structures such as the blood vessels or the target. We showed on one patient with an asymmetric brain shift that our method is more efficient that simply assuming the pre-operative location : we compared the registered sulci with their post-operative location.

The method is independent from the constitutive law of the brain, and could be improved using a more accurate law. We believe the method precision will strongly depend on the accuracy of the geometries and the models. The next step of this work is to strengthen the validation on a larger series of patients and perform tests on the basal ganglia.

Fig. 1 :

 1 Fig. 1: Pre-operative (left) MR image without brain shift, and post-operative (right) MRI showing asymmetric brain shift. The green and pink contours is a segmentation of the pneumocephalus (air inside skull). The pink line represents the surface of the brain in contact with air.

  meshes X and Y and d the euclidean distance between two vertices.

Acknowledgment

The authors would like to thank the French Research Agency (ANR) for funding this study through the ACouStiC project.


Cagdas Bilen

Srđan Kitić

Nancy Bertin

Rémi Gribonval

Çagdaş Bilen

Sr Dan Kitić

Sparse Acoustic Source Localization with Blind Calibration for Unknown Medium Characteristics

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Sparse recovery has become a popular research field especially after the emergence of compressed sensing theory [START_REF] Donoho | Compressed sensing[END_REF]. Consequently many natural signals have also been shown to be compressible or essentially low dimensional which enabled sparsity inducing methods to be used for the estimation of these signals in linear inverse problems.

Acoustic source localization can also be formulated as a sparse recovery problem [START_REF] Nam | Physics-driven structured cosparse modeling for source localization[END_REF][START_REF] Kitić | A review of cosparse signal recovery methods applied to sound source localization[END_REF]. In the continuous space and time, the acoustic pressure field in a 2-dimensional space, p( -→ s , t), induced by the pressure emitted by the sources, f ( -→ s , t), is known to obey the differential wave equation

∆p( - → s , t) - 1 c 2 ∂ 2 p( -→ s , t) ∂t 2 = 0, if no source at -→ s f ( -→ s , t), if source at -→ s (1)
at all non-boundary locations. The parameter c in (1) represents the speed of sound in the medium. For inhomogeneous mediums, this constant can be represented more generally as c( -→ s , t). In addition to the wave equation, the acoustic pressure field is also restricted by the boundary conditions. Both the wave equation and the boundary equations can be discretized straightforwardly into a set of linear differential equations represented as

(Ω 1 + αΩ 2 )x = z (2)
in which Ω 1 and Ω 2 represent the discretized differential operators in space and time respectively, α 1/c 2 is a function of speed of sound, x and z represent the discretized pressure field and the source signals in vector form respectively. The source localization problem can be described as the estimation of z (or equivalently x) from limited number of measurements recorded by a number of microphones, i.e. from

y = I s x (3)
where I s is a matrix formed by keeping some of the rows of the identity matrix corresponding to microphone locations. Considering the sparse nature of the sources, source localization can be posed as a sparse recovery problem which can be solved with convex optimization such as in

x = arg min x (Ω 1 + αΩ 2 )x * s.t. I s x = y (4)
where the * norm is often chosen as the ℓ 1 norm or the ℓ 1,2 norm [START_REF] Kitić | A review of cosparse signal recovery methods applied to sound source localization[END_REF]. In many such approaches, the medium is assumed to be homogeneous and the medium properties (c) are assumed to be known. However, in practice this assumption may not be always valid since the behavior of the medium may vary depending on the physical conditions such as temperature, ambient pressure, or unknown inhomogeneities in the medium. These incorrect assumptions on α (and hence the sparsifying operator Ω 1 + αΩ 2 ) may lead to significantly decreased sparsity or multiplicative perturbations that would highly reduce the recovery performance [START_REF] Candès | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] Herman | General deviants: An analysis of perturbations in compressed sensing[END_REF].

In this abstract, we investigate the source localization problem formulated in (4) but with an unknown speed of sound c (or equivalently α). In Section 2, we formulate the source localization problem for a spatially varying c, i.e. a time invariant but inhomogeneous medium and present an algorithm to estimate the medium properties along with the sources under spatial smoothness assumptions. Preliminary experimental results with the proposed algorithm are then presented in Section 3, which is followed by the concluding remarks in Section 4.

Source Localization with Unknown Medium Parameters

Let us first assume that the medium is inhomogeneous and unknown, i.e. α = α( -→ s , t) for the continuous domain. Consequently the discretized equation in (2) can be modified as

(Ω 1 + Diag(α)Ω 2 )x = z (5)
where Diag(α) indicates a diagonal matrix with the entries of the vector α along the diagonal. In this setting one can attempt to recover α and x by minimizing

x, α = arg min

x,α

(Ω 1 + Diag(α)Ω 2 )x 1,2 s.t. I s x = y (6)
where the ℓ 1,2 norm is defined as ℓ 1 norm along the spatial and ℓ 2 norm along the temporal dimension, assuming all the source locations are fixed along time. However the global minimum of the objective function in [START_REF] Herman | General deviants: An analysis of perturbations in compressed sensing[END_REF] often does not correspond to the actual x and α due to the high number of degrees of freedom introduced by the unknown α. The intrinsic degrees of freedom in the structure of a real world medium is often much smaller. In this work we will assume the medium does not change in time and exploit the fact that the spatial variation in a natural medium is often limited and assume nth order spatial difference of the field α along each spatial dimension is zero, i.e.

D n α = 0 (7) ⇒ α = A n p (8)
where A n is an orthogonal basis for the null space of D n . It can be observed that the degrees of freedom for α are reduced to n 2 (for 2-dimensional space) from the total size of the discretized points in space, which can be a significant reduction in practice. With the assumption of (8), the optimization in ( 6) can be modified as

x, p = arg min

x,p

(Ω 1 + Diag(A n p)Ω 2 )x 1,2 s.t. I s x = y (9)
Unlike the case with known α, (9) is not a linear optimization when jointly considering the variables x and α, hence the well developed convex optimization methods are not applicable. It is, however, linear in terms of each of the unknowns when the other is considered a constant. Therefore we propose a form of the alternating minimization approach which is often employed in such scenarios.

Experimental Results

In order to demonstrate the joint estimation performance of the proposed approach, a rectangular grid of 10 by 10 spatial dimensions is simulated with k randomly located stationary sources, k varying from 1 to 5. The sources emit random sinusoidals for a duration of 20 time instants. The pressure field is measured by m randomly located stationary microphones for 100 time instants, m varying from 2 to 10. The boundary conditions are modeled to be Neumann boundaries as in [START_REF] Nam | Physics-driven structured cosparse modeling for source localization[END_REF][START_REF] Kitić | A review of cosparse signal recovery methods applied to sound source localization[END_REF]. The field α is generated randomly to obey (8) with parameter n set as 1 and 2 and the field values to be between 0.1 and 0.6. The field parameters p and the acoustic pressure x are estimated from the microphone measurements y = I s x with an algorithm that minimizes (9) by alternating between unknowns applying the method of Alternating Direction Method of Multipliers (ADMM [START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF]). The details of the algorithm are not provided here due to space constraints. Each of the randomly generated experiments is repeated 20 times with the same parameters to empirically estimate the minimum sufficient number of microphones for successful source localization for each set of n, m, k. After each simulation, k points with highest energy are chosen as estimates of the source locations. The minimum number of microphones that succeeds in localization of the sources in 80% of the 20 experiments is set as the minimum sufficient number of microphones, m x,α (n). The minimum sufficient number of the microphones for the recovery of the acoustic field when the medium parameter, α, is known, m x , is also computed the same way for comparison. Figure 1a shows the change of m x.α (n) and m x (n) with respect to the number of sources. A sample reconstruction of source signals is shown in Figure 1b. The original and the estimated field α as well as the source and the microphone locations for the same sample reconstruction can also be seen in Figure 2.

The first thing to notice in the presented results in Figure 1a is that estimating the unknown α introduces almost no performance degradation with respect to perfectly knowing the medium parameters. This can be attributed to the very small degrees of freedom in α thanks to the smoothness constraints. Hence estimating α while localizing sources is possible whenever the sources can be localized with known α. In fact it is observed in the experiments that the estimation of α is still accurate for many cases when source localization is not successful. A second observation is that the sufficient number of microphones is not significantly affected when α is spatially varying (n = 2) compared to when it is spatially constant (n = 1). However the degrees of freedom within α increases with n 2 and therefore the sufficient number of microphones is expected to increase more rapidly with increasing n.

Conclusion

In this work, the acoustic source localization problem with additional variables due to unknown medium properties is described and a sparse recovery approach is presented for estimating both the sources and the medium structure. The presented approach utilizes the assumption that the spatial variation in the medium is limited and the acoustic sources are sparse. Preliminary results that demonstrate the performance of the proposed approach are presented. The talk will include further results, the details on the recovery algorithm and discussions on the extensions of the algorithm for more realistic scenarios.

Figure 1 :

 1 Figure 1: (a) The minimum sufficient number of the microphones, mx.α(n), with n = 1, 2 for successfully localizing different number of sources. The required number of microphones for the ideal case when the field α is known, mx(n), is also plotted for comparison. (b) The original and estimated signals emitted from the sources for a sample recovery.

Figure 2 :

 2 Figure 2: The original field α and the estimated field α on a 10 by 10 2dimensional grid for a sample experiment. The red, blue and black markers indicate the spatial positions of the original sources, estimated sources and the microphones respectively.

* This work was partly funded by the European Research Council, PLEASE project (ERC-StG-2011-277906).


Mauve: a Component-based Modeling Framework for Real-time Analysis of Robotic Applications

Charles Lesire and David Doose and Hugues Cassé

I. INTRODUCTION

Robots are more and more used in very diverse situations (services to persons, military missions, crisis management, . . . ) in which robots must give some guarantees of safety and reliability. To be really integrated in everyday life, robots must fulfil some requirements. Among these requirements, we focus on the nonfunctional requirements on embedded software [START_REF] Wiegers | The Essential Software Requirement[END_REF], and more specifically on real-time software requirements. These requirements are most of the time fulfilled by proving the schedulability of the embedded software.

Analysing and validating such properties on an existing hand-coded software requires some reverse modelling of the software, leading to approximations of its behaviour. These approximations may have certification authorities not be confident on the robot dependability.

This paper proposes an integrated development methodology that starts from software component modelling, and leads to both validation of the embedded software and generation of deployable embedded software.

II. MOTIVATIONS

Component-Based Software Engineering (CBSE) is an essential design paradigm for robotic software development [START_REF] Brugali | Component-Based Robotic Engineering (Part II)[END_REF], applied in many applications [START_REF] Basu | Incremental component-based construction and verification of a robotic system[END_REF], [START_REF] Steck | Towards quality of service and resource aware robotic systems through model-driven software development[END_REF], [START_REF] Schlegel | Design Abstraction and Processes in Robotics: From Code-Driven to Model-Driven Engineering[END_REF], [START_REF] Alonso | V3CMM: a 3-View Component Meta-Model for Model-Driven Robotic Software Development[END_REF]. Resulting components are reusable and composable, which ease their development, the architecture deployment, and its validation.

Recent practices in robotic software development intensively use middlewares (such as Orocos [START_REF] Soetens | Realtime hybrid task-based control for robots and machine tools[END_REF], Genom [START_REF] Mallet | GenoM3: Building middleware-independent robotic components[END_REF] or ROS [START_REF] Bradski | Tutorial on ROS[END_REF]) to help engineers to focus on the robotic aspects of development without having to manipulate low-level OS primitives for task management or communication policies. This paper presents a methodology for robotic application design that first requires a specification of the robotic software architecture inspired by both CBSE and separation of concerns [START_REF] Radestock | Coordination in evolving systems[END_REF]. Then, runtime execution is ensured by the generation of embedded code for the Orocos middleware, which is renowned for its real-time skills.

Although such model-driven engineering frameworks targeting Orocos already exist (BRIDE [START_REF] Bride | BRICS Integrated Development Environment[END_REF] -developed in the BRICS project [START_REF] Bischoff | BRICS -Best practice in robotics[END_REF] -, Proteus [START_REF] Proteus | Platform for RObotic modeling and Transformations for End-Users and Scientific communities[END_REF]), the methodology proposed in this paper focuses on realtime validation of the robotic application, by directly analysing the architecture specification, and limiting the middleware usage to its verifiable subset.

III. MAUVE

The Mauve (Modeling Autonomous Vehicles) methodology settles on a formal model, that clearly separates the component Computation (modelled as codels [START_REF] Mallet | GenoM3: Building middleware-independent robotic components[END_REF]), and the component and system Configuration, modelled through a validable formal language. Finally, the schedulable software architecture is deployed by targeting a subset of the Orocos middleware [START_REF] Soetens | Realtime hybrid task-based control for robots and machine tools[END_REF] that offers OS abstraction and portability of the application.

The Mauve implementation relies on a domain specific language (DSL, partially represented on Fig. 2(a)). The abstract syntax of the Mauve DSL is used by the real-time analysis. The Mauve framework also provide a concrete syntax of the Mauve DSL used by engineers to specify their architecture (Fig. 2(b)).

The complete process is shown on Fig. 1 and is detailed in this section.

A. Codels

Codels, that stand for "elementary codes", concern the computation of a component, i.e. data processing and algorithms. A codel is a function directly implemented in a programming language, without any dependence neither on the component specification, nor on the targeted middleware, OS or hardware architecture. This separation makes codels framework-independent, reusable, maintenable, and shareable [START_REF] Makarenko | On the Benefits of Making Robotic Software Frameworks Thin[END_REF].

B. Component model

Mauve allows to model libraries of reusable components. A component is described by several elements:

• Properties: each component has a set of properties that define the component parameters;

• Methods: each component can provide services to the other components or require specific services from other, unknown components;

• Ports: components can exchange data through ports; a component defines its input and output ports, with the type of the received or sent data; Mauve also contains a simple expression language with assignments, conditional instructions, method calls, codel execution, etc. This expression language is used to specify the behaviour of a component:

• the entry expression is executed at the step when a state is entered;

• the run expression is executed at each step when a state is active;

• the exit expression is executed at the step when a state is left.

This component description is consistent with a lot of component-based middlewares classically used in robotics [START_REF] Basu | Incremental component-based construction and verification of a robotic system[END_REF], [START_REF] Mallet | GenoM3: Building middleware-independent robotic components[END_REF], [START_REF] Soetens | Realtime hybrid task-based control for robots and machine tools[END_REF], [START_REF] Bradski | Tutorial on ROS[END_REF].

C. Architecture specification

The specification of the software architecture defines component instances and specifies interactions between those instances. For safety reasons engineers may need to duplicate or triplicate some components. This need is satisfied by the segregation of component models and component instances in the Mauve process.

The architecture specification consists in:

• creating and naming the components instances;

• linking each required method of the component instances to a provided method of another component instance (that satisfies signature consistency);

• connecting each input port of the component instances to an output port of another component (that satisfies data-type consistency); port connections are defined by connectors that specify the connection policy (buffered or not) and some parameters (size of the buffer, . . . )

D. Deployment specification

In the proposed process, the architecture specification and the deployment specification are strictly separated for different reasons:

• experiments may lead to deploy the same software architecture on different hardware architectures;

• real-time parameters of some components may be adapted to their environment (e.g. effective sensor rate);

• schedulability analysis depends on hardware specification and codel implementation. The deployment consists in specifying the worst case execution time (WCET) of each used codel and defining the real-time parameters of component instances (priority, period, deadline, . . . ). The WCET computation is accomplished using the Otawa framework [START_REF] Ballabriga | OTAWA: an Open Toolbox for Adaptive WCET Analysis[END_REF] which statically analyses the assembled code mapped to an hardware architecture specification.

E. Real-time analysis

Each component instance is mapped into a real-time task. The tasks are executed on a real-time operating system [START_REF] Gerum | Xenomai-Implementing a RTOS emulation framework on GNU/Linux[END_REF] with a fixed priority scheduler. The schedulability analysis consists in computing the worst case response time (WCRT: worst delay between the task release and the end of its execution) of each task (i.e. component instance). A component instance meets its deadline if its WCRT is lower or equal to its deadline. We have defined a new method to compute with precision the WCRT of component instances. This method extends the well known schedulability analyses [START_REF] Zhang | Schedulability analysis for real-time systems with EDF scheduling[END_REF] by taking into account the state-machine of the real-time tasks.

F. Runtime deployment

For runtime deployment and execution, the Mauve specifications have not be mapped to an OS. Mauve

IV. CONCLUSIONS

The design process based on the Mauve DSL provides best practices for robotic software development and deployment, by (1) clearly separating the computation (i.e. codels) from the architecture configuration (i.e. component models, architecture and deployment specifications), and (2) limiting the language to what can be analysed (e.g., some Orocos synchronization primitives 1are not available in the Mauve language because they may lead to unsafe real-time behaviours or pessimistic analysis).

Finally, we plan to extend the runtime deployment process, by supporting other robotic middlewares, such as ROS [START_REF] Bradski | Tutorial on ROS[END_REF], and investigating the generation of bare Xenomai tasks. These mappings will allow to further

Fig. 1 :

 1 Fig. 1: The Mauve process

Fig. 2 :

 2 Fig. 2: Mauve component model

namely Send/ClientThread for Orocos users evaluate the real-time behaviours of the different runtime.


come

Adaptive fuzzy controller for multivariable nonlinear state time-varying delay systems subject to input nonlinearities

Abdesselem Boulkroune, Mohammed M'Saad, Mondher