David Antonio

Gómez Jáuregui

M Bill Triggs -Professeur

M Frédéric Lerasle -Maître

M Rachid Deriche

Mme Bernadette

M Patrick Horain -Ingénieur

Networked 3D virtual environments allow multiple users to interact with each other over the Internet.

Users can share some sense of telepresence by remotely animating an avatar that represents them.

However, avatar control may be tedious and still render user gestures poorly. This work aims at animating a user"s avatar from real time 3D motion capture by monoscopic computer vision, thus allowing virtual telepresence to anyone using a personal computer with a webcam.

The approach followed consists of registering a 3D articulated upper-body model to a video sequence. This involves searching iteratively for the best match between features extracted from the 3D model and from the image. A two-step registration process matches regions and then edges. The first

contribution of this thesis is a method of allocating computing iterations under real-time constrain that achieves optimal robustness and accuracy.

The major issue for robust 3D tracking from monocular images is the 3D/2D ambiguities that result from the lack of depth information. Particle filtering has become a popular framework for propagating multiple hypotheses between frames. As a second contribution, this thesis enhances particle filtering for 3D/2D registration under limited computation constrains with a number of heuristics, the contribution of which is demonstrated experimentally. A parameterization of the arm pose based on their end-effector is proposed to better model uncertainty in the depth direction. Finally, evaluation is accelerated by computation on GPU.

In conclusion, the proposed algorithm is demonstrated to provide robust real-time 3D body tracking from a single webcam for a large variety of gestures including partial occlusions and motion in the depth direction.

Résumé

Les environnements virtuels collaboratifs permettent à plusieurs utilisateurs d"interagir à distance par Internet. Ils peuvent partager une impression de téléprésence en animant à distance un avatar qui les représente. Toutefois, le contrôle de cet avatar peut être difficile et mal restituer les gestes de l"utilisateur. Ce travail vise à animer l"avatar à partir d"une acquisition 3D des gestes de l"utilisateur par vision monoculaire en temps réel, et à rendre la téléprésence virtuelle possible au moyen d"un PC grand public équipé d"une webcam.

L"approche suivie consiste à recaler un modèle 3D articulé de la partie supérieure du corps humain sur une séquence vidéo. Ceci est réalisé en cherchant itérativement la meilleure correspondance entre des primitives extraites du modèle 3D d"une part et de l"image d"autre part. Le recalage en deux étapes peut procéder sur les régions, puis sur les contours. La première contribution de cette thèse est une méthode de répartition des itérations de calcul qui optimise la robustesse et la précision sous la contrainte du temps-réel.

La difficulté majeure pour le suivi 3D à partir d"images monoculaires provient des ambiguïtés 3D/2D et de l"absence d"information de profondeur. Le filtrage particulaire est désormais une approche classique pour la propagation d"hypothèses multiples entre les images. La deuxième contribution de cette thèse est une amélioration du filtrage particulaire pour le recalage 3D/2D en un temps de calcul limité par des heuristiques, dont la contribution est démontée expérimentalement. Un paramétrage de l"attitude des bras par l"extrémité de leur chaîne cinématique est proposé qui permet de mieux modéliser l"incertitude sur la profondeur. Enfin, l"évaluation est accélérée par calcul sur GPU.

En conclusion, l"algorithme proposé permet un suivi 3D robuste en temps-réel à partir d"une webcam pour une grande variété des gestes impliquant des occlusions partielles et des mouvements dans la direction de la profondeur. [START_REF] Howe | Silhouette lookup for monocular 3d pose tracking[END_REF]. .. [START_REF] Mamania | Markerless motion capture from monocular videos[END_REF]. ................... [START_REF] Ju | Cardboard People: A Parameterized Model of Articulated Image Motion[END_REF]. ...................... [START_REF] Azad | A full body human motion capture system using particle filtering and on-the-fly edge detection[END_REF] ............................ [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] ...... (Sminchisescu, et al., 2002) [START_REF] Agarwal | 3D Human Pose from Silhouettes by Relevance Vector Regression[END_REF] 2-20: Evaluating the match between the regions. The non-overlapping ratio F(q) is obtained from the overlap between the segmented image and the model projection in a candidate 3D pose. .... The effect of increasing or reducing the initial size of the simplex in our registration process until convergence. The abscissa is the frame number in the video sequence. The black line is the residual error of the non-overlapping ratio using a relatively large size of simplex (factor = 3.0). The gray line gives the corresponding residual error using a relatively small simplex (factor = 0.5). Finally, the dash gray line use a medium-sized simplex (factor=1.5), which provides smaller residual errors in our registration process. In each row, the images are respectively: the captured image; the edges extracted from the image; the edge-based registration result when using a large fixed initial simplex; and the edge-based registration result when using the final simplex of the region-based step. ............ The effect of limiting thr number of iterations on the residual error (ordinates) of our region-based registration. The abscissa is the frame number in a video sequence. The black line is the non-overlapping ratio minimized to convergence by the region-based registration while the gray line is limited to 500 iterations, which is the maximum number of iterations permissible for real-time computation. We see that limiting the number of iterations usually degrades the pose estimates. ....... The effect of limiting the number of iterations on the residual error (ordinates) of our edge-based registration step. The abscissa is the frame number in the video sequence. The black line is the mean edge distance minimized to convergence by the edge-based registration while the gray line is limited to 500 iterations. The example images show that the occluding edges of the 3D model are matched when the optimizer is near to convergence. 3-16: The mean residual error of the non-overlapping ratio (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and of the edge-based registration (y-axis) on video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results. ............... The mean residual error of the mean edge distance (z-axis) with respect to the number of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis), on video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results. ......................... The number of mistrackings for the non-overlapping ratio (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis), on the video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results. .... The number of mistrackings for mean edge distance (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis), on the video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results. ............... 3-26: The mean residual 3D error in millimeters (z-axis) on the video sequence with respect to the numbers of iterations of the region-based registration (x-axis) and edge-based registration (y-axis). The surfaces correspond to the video sequences "raising arms gesture" (a), "joy gesture" (b), "exclaiming gesture" (c) and "asking gesture" (d). ............................................................................... Graphs of the mean residual 2D error in millimeters (z-axis) for each video sequence, with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis). The plots correspond to the video sequences "raising arms gesture" (a), "joy gesture" (b), "exclaiming gesture" (c) and "asking gesture" (d). The residual 2D error decreases with the number of iterations for each sequence. The abscissa axis corresponds to the particle space . The particles are represented as circles which size is the likelihood of [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF] [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Each circle represents a particle which size correspond to its weight. Particles are propagated in time by three steps: resampling, prediction and measurement. . [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF]. ....... In the video sequence 3 (third row), the actor is turning around himself. In the video sequence 4 (forth row), the actor is not facing directly the camera. In video sequence 5 (fifth row), the actor is moving in the scene while making fast and relative depth motions. The video sequence 6 (sixth row) includes gestures in which the actor is moving in the scene and not facing directly to the camera. The first three video sequence last around 2 or 3 minutes while the sequences 5 and 6 (video lectures) last around 5 minutes. ........

Table of contents

List of figures

List of tables

Chapter 1

Introduction

Human motion capture is the process of measuring and recording human body in a computerusable form. Interest in human motion analysis -often called "mocap"has been growing in recent years as many potential applications have emerged (human-computer interfaces, medical applications, animation, interaction with virtual environments, video surveillance, games, etc.). This work focuses on enhancing interaction in virtual environments by reproducing user gestures directly in a 3D avatar in real-time [START_REF] Horain | Virtually enhancing the perception of user actions[END_REF].

Traditional motion capture involves special sensors (e.g. data gloves, magnetic sensors and mechanical exoskeletons) or optical markers on the performer"s body and limbs. Motion data is derived from the positions or angles of markers relative to the sensors. However, the cost and complexity of this equipment (personnel required, physical environment, etc.) is prohibitive for the general public and for many target applications. Computer vision based techniques offer an interesting alternative because they only require images from one or more cameras. As special and expensive equipment is not required, motion capture by vision is potentially a practical and inexpensive solution. We are interested in estimating 3D human motion from monocular images; this enormously increases the range of possible applications as many personal computers include a webcam.

We address the problem of 3D human motion capture in real-time without markers from monocular images obtained from a webcam. We focus on capturing the motion of the upper part of the human body as our objective is to achieve more natural interactions between users and 3D virtual collaborative environments. A prototype for 3D motion capture by monoscopic vision and virtual rendering was previously proposed in the works of Horain [START_REF] Horain | 3D Model Based Gesture Acquisition Using a Single Camera[END_REF] and Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. This approach consists basically of registering a 3D human upper-body model to video sequences. However, because it is designed to work in real time on a personal computer, its robustness and accuracy are currently limited and need to be improved. 3D motion capture from monocular images remains challenging open problem as many difficulties are involved; for example, the ambiguities of monocular images, partial occlusions of human body parts (e.g. crossed arms), the large number of degrees of freedom of the human body, variations in body proportions and clothing, cluttered and complex environments, image noise, etc. Moreover, the computations needed to track the human motion in the images can be very expensive, making it difficult to achieve robust real-time performance.

In this thesis, new algorithms are proposed to improve the results of the motion capture methods of (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. In the following subsections, we describe our target application and some other potential applications of the work; then we discuss the main challenges and difficulties involved and present the contributions of this work.

Enhancing the perception of user actions in 3D collaborative virtual environments

A Collaborative Virtual Environment (CVE) is used for collaboration and interaction of participants that may be spread over large distances. The applications are usually based on networked virtual environments where the users interact through avatars. An avatar is a representation of a person in the virtual environment. Avatars can communicate with each other as well as doing activities that people do in their daily life. Nowadays, virtual environments like Second Life (SL) attract many people to experience 3D virtual life.

In Second Life, residents can explore, meet other residents, socialize, participate in individual and group activities, and create and trade virtual property and services with one another, or travel throughout the world. Virtual environments can be also used to increase interaction and immersion in e-learning systems (Li, et al., 2009) or teleconferencing (Figure 1-1). People can attend virtual meeting rooms (teleconferencing) or virtual classrooms (e-learning). They can discuss with other people (avatars) and interact through virtual resources (e.g. blackboards, shared tables, etc.).

Figure 1-1: Avatars meeting and interacting in a 3D virtual space (OpenSpace3D, 2010)

Avatars are animated by their human counterpart to provide a sense of telepresence. The animation of avatars allows users to express themselves in the virtual environment and helps to focus attention on objects of interest [START_REF] Horain | Virtually enhancing the perception of user actions[END_REF]. However controlling their behaviors is difficult. Selecting animation primitives from a menu or using icons is tedious. Moreover the avatar animation is not lively as it moves only on command. There are a number of efforts underway to make 3D animated human form more lifelike and to achieve more intuitive interaction (e.g. Avatar Puppeteering by Linden Lab [START_REF] Linden | Avatar Puppeteering: Direct Manipulation of Avatars for Expression and Animation Editing[END_REF], Hands Free 3D by Kapor Enterprises [START_REF] Kapor | Hands Free 3D Controlling Virtual Words Without a Mouse or Keyboard[END_REF]).

We propose to enhance the perception and immersion of users in 3D virtual environments through 3D motion capture by monocular vision. In this way, the avatar can mimic the gestures of the user in real-time. This increases the users" sense of presence in the 3D virtual space [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. In this type of immersion, users do not have to memorize a large number of commands to use any special capture device. Motion capture by monoscopic computer vision offers a flexible solution as only a single camera is required, thus allowing telepresence to anyone using a personal computer with a webcam.

In this work, monocular vision (from a webcam) is used since webcams are very low-cost and flexible consumer devices (commonly included in personal computers and netbooks), in contrast to recent consumer devices capable of providing 3D information (e.g. camera TOF, Kinect), which are generally more costly and less flexible.

We aim to allow the users to fully control and express themselves via their 3D avatars (Figure 1-2). 3D human motion is captured through a webcam using computer vision algorithms and rendered by his avatar in real-time. This kind of immersion allows new gesture-based communication channels to be opened in virtual inhabited 3D space [START_REF] Horain | Virtually enhancing the perception of user actions[END_REF].

Figure 1-2: Our target application: 3D motion capture for 3D collaborative virtual environments (MyBlog3D, 2010).

Other potential applications

Motion capture technology has a wide variety of highly demanding applications. At present, the film industry is the application where motion capture is most extensively used. Motion capture techniques allow large amounts of animation data to be produced; the movements of human subjects (athletes, dancers, actors) are captured and transferred directly or indirectly to computer-generated animation models. This gives animator the ability to produce more realistic movements. Movies use mocap to replace traditional animation by hand and also to produce computer-generated creatures that interact visually with real actors (e.g. the Gollum character from the Lord of the Rings film). Recently, several films and television series have been produced almost entirely using motion capture animation (e.g. The Polar Express, Avatar, etc.). Similar motion capture techniques are applied in videogame industry to allow more convincing and realistic character movements and expressions.

Gait analysis is the systematic study of the body"s motions in space (kinematics) and the forces producing them (kinetics). In clinical medicine, gait analysis is applied to humans in order to identify pathological disabilities (e.g. neuromuscular disorders, cerebral palsy). Since early 1970s, this analysis was done by careful frame by frame study of the videos provided by a camera system. More recently, motion capture technology has been applied to gait analysis in order to quantify the movements [START_REF] Cloete | Benchmarking of a full-body inertial motion capture system for clinical gait analysis[END_REF], [START_REF] Saboune | Markerless human motion capture for Gait analysis[END_REF]. This allows the joint angles to be compute more accurately and the contribution of each bone and muscle to be detected in the motion trajectory. Variations in gait style (walking speed, step length, cycle time) can be also used in biometric identification and in sports performance enhancement.

Recently, some entertainment applications have started using motion capture in order to provide more intuitive forms of interaction in human-machine or human-software interfaces.

In the videogames industry, the next step is to allow players to interact with games using only body motion or gestures (hands-free gaming) without holding any physical device (e.g. Kinect from Microsoft, EyeToy from Sony). Human-robot interaction is another example of a motion capture application. A major challenge in robotics is providing humanoid robots with embedded intelligence so they can autonomously interact with people by using natural nonverbal communication (human gestures). Embedding motion capture in a robotic system would provide two advantages: 1) understanding meaningful human gestures and movements in order to serve humans in their daily life [START_REF] Kanda | Body movement analysis of human-robot interaction[END_REF], 2) communicating effectively with humans by imitating as closely as possible their natural motions [START_REF] Kim | Stable Whole-body Motion Generation for Humanoid robots to Imitate Human Motions[END_REF], [START_REF] Nakaoka | Generating whole body motions for a biped humanoid robot from captured human dances[END_REF]. This would allow robots to participate in many human society activities.

Automated video surveillance is another demanding application for human motion capture.

Video surveillance can be used in geriatric-care, alarm security systems, home-nursing, etc. The goal of automated surveillance is to reduce the large number of human operators required to monitor many real time video feeds simultaneously by using software that can analyze video content automatically. Currently, automated video surveillance is an active research area in computer vision with many remaining technical challenges [START_REF] Dick | Issues in Automated Visual Surveillance[END_REF]. In order to develop automated surveillance system, motion capture could be used to detect, track, identify people, and generally, to analyze human behavior in real-time without the need to attach any joint markers. These systems must be able to operate in public spaces (unconstrained environments) where lighting variations, occlusions and changes reflectance represent a significant challenge for the computer vision analysis.

Main challenges

We focus on 3D motion capture by monocular vision in real-time without markers [START_REF] Horain | 3D Model Based Gesture Acquisition Using a Single Camera[END_REF]. This computer vision problem is inherently difficult for because of insufficient information from images, ambiguities in the projection of monocular images, the large number of human pose parameters to estimate and self-occlusion of body parts. In this section, we describe the main challenges addressed in this work.

Lack of depth information: inferring the 3D pose from images obtained with only one camera is an ill-posed problem. Forward and backward movements with respect to the camera"s viewpoint (depth direction) lead to more than one possible solution due to the ambiguities in monocular images. These ambiguities result in motion-mistracking.

High-dimensional search: in order to estimate the 3D human pose, several works (Sminchisescu, et al., 2002), [START_REF] Delamarre | 3D articulated models and multiview tracking with physical forces. s.l[END_REF] use a 3D human model to infer the correct joint angle values (degrees of freedom) of each body part (head, neck, arms, forearms, hands, legs, etc.). Some other works [START_REF] Ramanan | Finding and Tracking People From the Bottom Up[END_REF], [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF] try to infer the position of each body part separately before enforcing joint connectivity. In both cases, the number of parameters to be estimated is very high (between 20 and 60 dimensions); therefore, finding the optimal pose is a search problem in a high dimensional space. This requires intensive computation that is difficult to achieve real-time.

Occlusions of human body parts: tracking 3D human motion from monocular images can become a difficult task as there are poses where some body parts are occluded by others (e.g. walking, arms crossed). In order to cope with occlusions, several works (Ning, et al., 2004), [START_REF] Sidenbladh | Implicit probabilistic models of human motion for synthesis and tracking[END_REF] use a learned motion model or exploit a temporal coherence in order to track the pose through body parts occlusions.

Clothing variations: different clothing in humans can be a problem (e.g. clothing of different shapes, or with color, edges and complex textures) causing inaccurate observations leading to ambiguities and consequently, incorrect 3D pose estimates.

Variations in human body proportions: many 3D pose estimation techniques [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF], (Sminchisescu, et al., 2002) use a 3D computer model of the human that must be matched to the actor in the image. Such model usually has predefined body part sizes and shapes. Thus, if the human model has different proportions from the real subject, the matching between the model projections and the actor cannot be accurate and failures may occur. For example, if the arms of the model are larger than the arms of the subject, the model arms can intersect erroneously with other body parts.

General motions: several works on 3D motion capture [START_REF] Urtasun | 3D human body tracking using deterministic temporal motion models[END_REF] use learned motion models to track cyclic or repetitive motions (e.g. walking, running, golf swing) however, general motions are difficult to track as they are highly variable and unpredictable, making the learned model useless. Several works address the problem of tracking general motions by propagating multiple hypotheses at each time (e.g. particle filter approaches), this often provides robust and accurate results, however, computation times can be very high as a large number of hypotheses must be propagated.

Complex environments: lighting changes and cluttered or dynamic backgrounds (e.g. public spaces) from video sequences can be a problem as imprecise observations (e.g. clutter edges, segmentation failures) can make the pose estimation procedure fails. Lighting changes can cause misclassifications in color segmentation or the emergence of new segments in the scene. Shadows, textures and objects in cluttered backgrounds can produce distracting image measurements (e.g. color, edges, optical flow).

Thesis contributions

In this thesis, we extend the approach proposed in (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF] and we propose new methods to achieve real-time 3D motion capture by monocular vision. The work is organized as follows.

Chapter 2 is a detailed analysis of the state-of-the-art for 3D motion capture by computer vision. Recent works in this area are discussed, emphasizing their respective benefits and limitations. Finally, we describe our baseline approach for real-time 3D motion capture by monocular vision.

In chapter 3, new algorithms are proposed to enhance the tracking performance of our baseline approach. We describe a new method that combines a robust region-based registration step and a more accurate edge-based registration step. The respective limitations and benefits of these are compared experimentally. Finally, we derive an optimal trade-off curve between these steps that achieves the best accuracy possible given the real-time constraint.

In chapter 4, we address the limitations of local optimization algorithms for 3D motion capture by introducing an improved set of optimization heuristics for real-time particle filtering. We describe and experimentally evaluate a number of heuristics that we demonstrate to jointly improve both the robustness and the accuracy of real-time 3D motion capture by monocular vision. End-effector based pose parameterization is introduced to handle the intrinsic data uncertainties more robustly. Real-time computation with large number of particles is achieved using a parallel GPU-based implementation of the particle evaluation step. Finally, we experimentally compare the results of our proposed real-time particle filtering algorithm on several real video sequences.

In chapter 5, we summarize the contributions of the thesis and present our final conclusions.

Perspectives and further extensions are also discussed.

Chapter 2

State of the art

Introduction

The use of motion capture technology is relatively new; it began in the late 1970"s for military purposes (tracking movements of pilots) [START_REF] Maureen | Motion Capture: An Overview[END_REF]. Later, in 1980, Vicon Motion Systems created the first system for gait analysis, which the captured motion of children in order to detect disabilities [START_REF] Sutherland | The Development of Mature Walking[END_REF]. Since the 1990"s, advances in computer processing power and research in algorithms have made possible a wide variety of new applications (see section 1.2) including real-time motion capture computation [START_REF] Molet | A real time anatomical converter for human motion capture[END_REF].

Nowadays, motion capture is rapidly becoming cheaper and many more systems have emerged in the market. However, it still faces challenges, such as lack of precision of the motion data and complicated calibration procedures (e.g. special environments, uncomfortable user equipment). In the following sections, current technologies for motion capture are described (section 2.2). Section 2.3 summarizes existing techniques for motion capture by computer vision without markers. Finally, section 2.4 briefly describes our baseline approach for 3D motion capture by monocular vision.

Motion capture technologies

Mocap technologies generally include synchronized cameras and special suits with markers or sensors worn by the performers. Markers are set at body parts (or joints) and are tracked in order to identify the motion by their positions or angles. Only the motion of the actors, not their visual appearance, is recorded and this motion is the mapped to a 3D model by computer.

Motion capture techniques can be classified by their input methods, namely optical, mechanical, magnetic, acoustic and inertial. Each of these inputs (or a combination of them) is tracked, ideally at least twice the frequency of the desired motion.

Optical systems

In optical motion capture systems, data acquisition is implemented using special markers attached to the actor [START_REF] Optitrack | Optitrack optical motion capture solutions[END_REF]; this approach uses at least three synchronized cameras and proper lighting to estimate the performer's position in 3D space. These systems produce data with 3D locations for each marker (Figure 2-1). Two types of markers can be used: passive and active.

Passive markers: Passive optical system use markers coated with a retro-reflective material to reflect back light that is generated near the cameras lens. The operating principle is similar to radar: the cameras emit radiation (usually infrared), which is reflected by the markers and returned to the same camera. The cameras are sensitive to a narrow band of wavelengths and perceive the markers as bright spots. Such a system typically consists of 6 to 24 cameras. Passive systems do not require the user to wear wires or electronic equipment. The markers are usually attached directly to the skin, or to a full body lycra suit designed for motion capture [START_REF] Qualisys | Qualisys. Optical Motion Capture -Accurate tracking of any kind of motion[END_REF].

Active markers: Rather than reflecting back externally generated light, the markers themselves are powered to emit their own infrared light. Active optical systems triangulate positions by illuminating one LED at a time very quickly or multiple LEDs with software to identify them by their relative positions. Some systems can modulate the amplitude or pulse width in order to provide marker ID. This unique marker ID provides much cleaner data than passive marker systems (PhaseSpace, 2010).

Mechanical systems

Mechanical methods use an exoskeletona skeletal-mechanical structure attached to the performer"s body (Figure 2-2). The exoskeletons are rigid structures of metal or plastic rods that articulate at the joints of the body linked together with potentiometers. They directly track body joint angles by the sensors attached to the exoskeleton. They provide real occlusion free information, however, the exoskeleton suit can be heavy and cumbersome, limiting the user"s freedom of movement (Gypsy7, 2010).

Magnetic systems

Magnetic systems use sensors placed on the body to measure a low-frequency magnetic field generated by a transmitter source (Figure 2-3). The outputs of these sensors are 3D positions and rotational information. The number of sensors used is usually from 6 to 11. The sensors and source are attached to an electronic control unit that correlates their reported locations within the magnetic field (AMM, 2010). Inverse kinematics (IK) is then used to recover the angles for the different body joints. A big advantage of these systems is that useful real-time results can be obtained from only 6 sensors. However, the sensors are susceptible to magnetic and electrical interference from metal objects in the environment. In addition, the wiring from the sensors tends to limit the actor"s movements. Recently, the development of new wireless magnetic systems has been reported [START_REF] Kanetaka | Wireless magnetic motion capture system for medical use[END_REF].

Acoustic systems

Acoustic systems use three audio receivers and an array of audio transmitters on the performer"s body. The audio transmitters send clicking sounds and the receiver measures the travel times from each transmitter (Intersense, 2010). The calculated distance from the three receivers is triangulated to provide a point in 3D space. This position data is typically fed to an inverse kinematics system which in turn drives an animated skeleton. An advantage of this method is the relative absence of occlusions. Unfortunately, accuracy may be affected by sound reflections or audio interference.

Inertial systems

Inertial systems are based on miniature inertial sensors (gyroscopes and accelerometers) with sensor fusion algorithms to measure the rotational rates. Motion data is transmitted wirelessly to a virtual skeleton in software. Basically, these systems are similar to the Nintendo Wii controllers but are more sensitive and more accurate. Inertial systems are practical because they are portable and do not require large capture areas or complicated calibration (IGS-190-M, 2010). A disadvantage is that the positional drift that can compound in time if the setup is not correct due to poor calibration.

Computer vision based systems

Using computer vision techniques to acquires the human body motion is one of the most attractive and practical solutions as it does not require any expensive or invasive hardware or markers (only cameras are required) and it can work outdoors (in streets, offices, parks).

Algorithms have been proposed that capture human motion at near real-time frame rates; however, they mostly rely on multi camera systems under controlled conditions, which limit their applicability. Some monocular vision approaches [START_REF] Agarwal | Recovering 3D human pose from monocular images. s.l[END_REF], [START_REF] Urtasun | Motion Models for Robust 3D Human Body Tracking[END_REF] aim at capturing specific motions (walking, golf swinging, jumping, etc.) using some learning model or tracking motion for certain parts of the body. Some other systems can track unconstrained motion, but do not run in real-time (Sminchisescu, et al., 2003).

Recently, 3D image sensors have been used to capture the 3D body shape and disambiguate poses using depth measurements. Time-of-flight sensors [START_REF] Ganapathi | Real Time Motion Capture using a Single Time-Of-Flight Camera[END_REF], [START_REF] Kolb | Time-of-Flight Cameras in Computer Graphics[END_REF]) and active triangulation system (e.g. Microsoft Kinect (Kinect, 2010)) are such dedicated sensors.

Real-time markerless tracking of human pose by monocular computer vision remains a hard yet relevant problem.

Human motion capture by computer vision

Human pose estimation from images is an unsolved and currently active field of research with significant scientific and computational challenge [START_REF] Sminchisescu | 3D human Motion Reconstruction in Monocular Video: Techniques and Challenges[END_REF]. As this is the main topic of this work, we present a more detailed analysis of computer vision-based techniques. We consider both real-time and non-real-time systems, as well as single and multi-camera systems.

Systems for motion capture using computer vision are first discussed based on the image descriptor or features that they use (section 2.3.1). Human pose can then be estimated using a generative approach (section 2.3.2) or a discriminative approach (section 2.3.3) [START_REF] Sminchisescu | 3D human Motion Reconstruction in Monocular Video: Techniques and Challenges[END_REF]. Tracking the pose between consecutive frames of a video sequence can ensure the temporal coherence of the human motion (section 2.3.4). Finally learned motion models can be used to enhance the robustness of the motion tracking (section 2.3.5).

Image features for motion capture

In order to estimate the 3D pose, image features are extracted from input images. A feature or image descriptor can be defined as a piece of low-level visual information extracted from an image to solve a specified task. Image descriptors are generally extracted using probability distributions (e.g. color histograms), neighborhood operations (e.g. edges, optical flow) or thresholding the pixel values (e.g. foreground or color classification). The choice of features depends greatly on the problem to be solved. In human motion capture, the image descriptors are generally used as cues to find the position of each body part and thus to estimate the full 3D human pose. Image descriptors commonly used in the literature include color, silhouettes, edges and motion [START_REF] Poppe | Vision-based human motion analysis: An Overview[END_REF], (Moeslund, et al.).

Color

Skin color is a common cue for head and hand detection [START_REF] Vezhnevets | A Survey on Pixel-Based Skin Color Detection Techniques[END_REF]. [START_REF] Broekhuijsen | Estimating 2D Upper Body Poses from Monocular Images[END_REF] extract skin regions by converting images to the HSV color space, thresholding each channel empirically, and finally selecting the largest connected components, which are deemed to belong to the head and the hands. [START_REF] Bernier | Fast nonparametric belief propagation for real-time stereo articulated body tracking. s.l[END_REF] use an initial face detection algorithm to obtain a normalized skin color histogram in the UV chrominance space (from YUV color space). A skin color probability is estimated from the histogram and then used to detect the head and hands.

Some human motion capture works combine different color cues into a single probability; [START_REF] Fontmarty | Data fusion within a modified annealed particle filter dedicated to human motion capture[END_REF] define a color-based likelihood that combines clothing color and skin color. For clothing probability, a learned reference histogram of the clothing color is compared using a Bhattacharyya distance with a targeted ROI in the image. In addition, they calculate a homogenous distance by measuring the standard deviation of the color distribution in RGB space from uniformly sampled points inside the color region.

Unfortunately, color may lack robustness in cases where significant local changes in illumination can occur. In addition, cluttered scenes that contain colors similar to regions of interest (skin or clothing) can generate noise in color segmentation.

Silhouettes

When capturing images with a static camera, silhouettes can be obtained using background subtraction techniques (Figure 234). Silhouettes can encode useful information about the human pose. [START_REF] Shahrokni | Markov-based Silhouette Extraction for Three Dimensional Monocular Body Tracking in Presence of Cluttered Background[END_REF] extract the human silhouette by texture segmentation. [START_REF] Deutscher | Articulated Body Motion Capture by Stochastic Search. s.l[END_REF] extract the silhouette by a thresholded background subtraction algorithm. [START_REF] Agarwal | Recovering 3D human pose from monocular images. s.l[END_REF] encode the shape information of learned silhouettes by computing histograms of shape context descriptors [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] that can be compared using simple Euclidean distance.

Silhouettes output by background subtraction can be noisy due to illumination changes or shadows, which can affect their shape. Another limitation is the poor visibility of certain degrees of freedom (e.g. knees, elbow, hands), which causes a high degree of ambiguity and body part occlusions which make it difficult to recover the 3D human pose.

Figure 2-4 : Human silhouettes extracted using a background subtraction algorithm [START_REF] Howe | Silhouette lookup for monocular 3d pose tracking[END_REF].

Edges

In computer vision, an edge is a significant variation or discontinuity in the gray level of a digital image. Edges detector algorithms provide the set of connected curves that indicate the boundaries of objects of interest [START_REF] Ziou | Edge detection techniques-an overview. s.l[END_REF]. In human motion capture image edges are a useful cue for the boundaries of body limbs (e.g. hand, arm, head, forearm, etc.). Some works [START_REF] Fontmarty | Data fusion within a modified annealed particle filter dedicated to human motion capture[END_REF], [START_REF] Chen | Markerless monocular motion capture using image features and physical constraints[END_REF] compute a distance transform to measure the distance between edge points in the image and their nearest pixel on a candidate silhouette boundary. Other works [START_REF] Ramanan | Finding and Tracking People From the Bottom Up[END_REF] use edgeS as a cue to detect or track body parts (e.g. arms, forearms, hands). [START_REF] Broekhuijsen | Estimating 2D Upper Body Poses from Monocular Images[END_REF] estimate the hand position by computing the number of edge pixels along a skin region of the full arm. They also train edge response histograms of limb-like edges and background-edges. They compute the probability that an edge belongs to a body part according to the edge orientation. [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF] use the orientation of the edges to estimate the position and orientation of a limb.

Edges have the advantage that they are very robust to changes in lighting conditions and can be extracted at a very low computational cost. However, undesirable edges resulting from background clutter, clothing textures edges or noise may be a problem.

Motion

Motion capture may use optical flow [START_REF] Horn | Determining optical flow[END_REF], [START_REF] Lucas | An Iterative Image Registration Technique with an Application to Stereo Vision (DARPA)[END_REF] to directly estimate the motion of each human body part by assuming small motion and brightness constancy. [START_REF] Ju | Cardboard People: A Parameterized Model of Articulated Image Motion[END_REF] use a parameterized optical flow equation to recover the motion of each region belonging to the limb. [START_REF] Bregler | Twist based acquisition and tracking of animal and human kinematics[END_REF] write the analytical relationship between the vectors of apparent motion in the image and the angular change of each joint. In this technique, linear differential equations need to be solved in order to update the 3D pose parameters for each frame. [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] use an optical flow method that generates a flow field with an outlier map that provides information about the motion boundaries. [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF] detect motion by computing the difference between the pixels of consecutive frames. They calculate a motion energy score for each limb.

Motion cues are usually robust to extract and provide useful information about the direction of the movement of each body part; however one disadvantage is the assumption that the person is always moving in the scene. Moreover, optical flow assumes small motions between frames; this is not always the case for human motion (especially motions of the arms and legs). Additionally, the deformation of clothing as a person moves can make the motion estimation difficult.

Feature combinations

Some works integrate different cues to achieve more robustness in the 3D pose estimation.

Several methods have been used to combine the information from different descriptors. Chen et al. [START_REF] Chen | Markerless monocular motion capture using image features and physical constraints[END_REF] combine the silhouette information with edges extracted from the same silhouette. They extract edges from the foreground silhouette and compute a distance transform to the silhouette boundaries. [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] combine edge and motion information in a negative log-likelihood function. Edges are weighted according to their importance qualified by a motion boundary map extracted from an optical flow method. [START_REF] Fontmarty | Data fusion within a modified annealed particle filter dedicated to human motion capture[END_REF] combine edge distance, color, and 3D blob distance (acquired from two cameras) into a single observation function. They assume that all observations are mutually independent probabilities.

Combining image descriptors proves to be more robust as the advantages of each descriptor can be used in one or more likelihood functions. However, care must be taken because each descriptor can give incompatible likelihoods.

Generative approaches

These approaches estimate the human pose using a prior model of the human body, parameterized by the kinematic tree of the articulations and the body dimensions. The pose of the human body model is described by a vector of parameters.

Generative approaches differ essentially in the manner in which data is associated with the 3D model. In this case, we can identify two methods: reconstruction-based and appearance-based.

The first method (reconstruction-based) try to fit the 3D model to a 3D cloud obtained from multiple cameras [START_REF] Urtasun | 3D human body tracking using deterministic temporal motion models[END_REF], (Ziegler, et al.). In the appearance-based techniques, a human model with a defined pose is projected into the input image and several features (section 2.3.1) are extracted from the image [START_REF] Lee | Particle Filter with Analytical Inference for Human Body Tracking[END_REF], (Ramanan, et al.), (Sminchisescu, et al., 2003). In both techniques, the human pose is estimated by finding the vector of model parameters that best fits the input data.

Finding the pose that best matches the image features can be a very difficult task, because occlusions of body parts may occur and same image feature can match different 3D poses (ambiguities). Several works propose different human body models and methods to estimate and track the human pose over time. Some learning methods are also used to improve the motion capture results. These methods will be described below.

Human body models

Human models are basically represented with a kinematic tree that of rigid segments connected by articulated joints. Each segment represents a specific human body part and can be described by a 2D figure or a 3D volume. A joint may hold up to 3 degrees of freedom. A given pose of the model is described by a vector of parameters of joint angles. [START_REF] Morris | Singularity Analysis for Articulated Object Tracking[END_REF] proposed a simple 2D scaled prismatic model (SPM). In this model, each segment is represented as a line that contains two parameters: the angle rotation and its length. Each segment contains a translational degree of freedom that scales the link appearance in order to estimate 3D motions. This model does not require specification of link lengths and joint axes. The author argues that such 2D SPM"s avoid some of the singularity problems associated with 3D motion from monocular vision. Cham et al. [START_REF] Cham | Multiple hypothesis approach to figure tracking[END_REF] used the SPM"s in order to estimate 2D human motions from monocular sequences. A simpler 2D model is used by [START_REF] Mamania | Markerless motion capture from monocular videos[END_REF], this model is represented by a stick figure , where the articulations are represented as points and the body parts or segments as simple lines.

Figure 2-5 : A human body model represented by a stick figure [START_REF] Mamania | Markerless motion capture from monocular videos[END_REF]. [START_REF] Ju | Cardboard People: A Parameterized Model of Articulated Image Motion[END_REF] represent the human model as a set of connected 2D planar patches (Figure 23456). A kinematic tree is constructed from these patches. Each patch is represented by its four corners, which represent also the articulation points between two connected planar patches. A similar model is used by [START_REF] Para | 2D Articulated Body Tracking with Self-occultations Handling[END_REF], where each body part consists of 2D planar figures (circles and rectangles) that are linked with flexible joints. Each planar figure contains three degrees of freedom which include the 2D coordinates of its centre and the rotation angle around the axis perpendicular to the image plane.

Figure 2-6 : A human body model represented by 2D planar patches [START_REF] Ju | Cardboard People: A Parameterized Model of Articulated Image Motion[END_REF].

Because 2D models are not able to capture the 3D motion correctly, many works add 3D volumes around the segments of the kinematic tree to represent more accurately the 3D pose (Figure 2 [START_REF] Azad | A full body human motion capture system using particle filtering and on-the-fly edge detection[END_REF] To achieve a better approximation of the human shape, some 3D models are constructed by polygon meshes. [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] use a mesh model that consists in a kinematic structure covered by super quadrics ellipsoids (Figure 2345678). This model is described by 30 joint parameters, 8 internal proportion parameters encoding the position of the joints and 9 deformable shape parameters for each body part. The shape parameters are based on standard humanoid dimensions.

Pose estimation

Pose estimation refers to the process of searching for the set of model parameters that minimizes the similarity between features extracted from the model and the input image using local optimization. The model parameters can be the joint angles or the global positions of each body part. Due to the high-dimensionality of the model parameters (20 or more joint angles), the search method used must be very efficient. In the state of the art, many works take several minutes per frame and only few can achieve quasi-real-time results [START_REF] Hua | A decentralized probabilistic approach to articulated body tracking. s.l[END_REF], [START_REF] Fontmarty | Vision et filtrage particulaire pour le suivi tridimensionnel de mouvements humains: applications à la robotique[END_REF], [START_REF] Bernier | Fast nonparametric belief propagation for real-time stereo articulated body tracking. s.l[END_REF] In general, there are two techniques for generative pose estimates: top-down estimation and bottom-up estimation. Related work using these approaches will be described below.

Top-down estimation

Top-down approaches estimate the state vector describing the human pose at each frame by a local search that evaluates different candidate poses starting from the configuration found in the previous frame (Figure [2][3][4][5][6][7][8][9]. One drawback of this approach is the pose in the first frame must be specified manually by the user. In [START_REF] Bregler | Twist based acquisition and tracking of animal and human kinematics[END_REF], the user must click on the 2D joint locations in all camera views at the first time step. The correspondence between the 3D pose and the image projection is found by minimizing the sum of squared differences between the projected model joint locations and the user supplied model joint locations. The optimization is done over the poses, angles, and body dimensions. The global minimization over all parameters yields a tri-linear equation system whose solution is approximated with a Quasi-Newton method.

Finding the best match can be computationally expensive due to the high number of parameters (dimensions) to be estimated. Different search strategies have been proposed; [START_REF] Delamarre | 3D articulated models and multiview tracking with physical forces. s.l[END_REF] created forces from the extracted human silhouette to the projected model. These forces are inferred from a comparison between tangents to the contours of the tracked object and the model. The forces are applied to the 3D model in order to push it towards the silhouette in the images by solving dynamical equations iteratively until convergence. [START_REF] Grest | Single View Motion Tracking by Depth and Silhouette Information. s.l. : Image Analysis[END_REF] used the normal displacement between the contour points of the model projection and the silhouette to estimate a Jacobian Matrix, which allows analytical derivation of the optimization function. Although the use of analytic Jacobian allows the number of iterations for pose estimation to be reduced, spurious local minima persist because observation likelihoods are typically multi-modal (Sminchisescu, et al., 2002).

Instead of using non-linear optimization techniques, some authors try to simplify the problem by fitting the model directly to the observations. [START_REF] Niskanen | Articulated motion capture from 3-D points and normals[END_REF] use an articulated surface like a human model. They use a set of 2D silhouettes (from multiple views) that are combined together with multi-camera geometric constraints. The human surface model is fitted to the 3D observations by the minimization of an objective function that takes into account the location and orientations of these observations. [START_REF] Taylor | Reconstruction of Articulated Objects from Point Correspondences in a Single Uncalibrated Image[END_REF] proposes a method to estimate the 3D pose directly from 2D points. In his work, the correspondence between joints in the model and point features in the image is provided by the user. The relative length of the segments in the model is also known a priori and the depth ordering of the image points must be specified manually. The 3D pose is then deduced from foreshortening of the body segments of the model under a scaled orthographic projection. Thus, they directly recover the coordinates of the joints in the world coordinate system.

Bottom-up estimation

Bottom-up approaches detect each body part individually from image features and assemble the detected parts together into a human body pose using heuristics or constraints such as the proximity between linked body parts. These approaches have the advantage that they can automatically perform initialization and recover from tracking failures. Furthermore, highdimensional search is avoided by partitioning the joint pose space into separate sub spaces for (Sminchisescu, et al., 2002).

each body part. However, the main difficulty is that body parts are not easy to detect producing many false positives as there may be many limb-like regions in an image.

Various authors have proposed techniques to track body parts using image features and to infer the resulting full body configuration. Ramanan and Forsyth [START_REF] Ramanan | Finding and Tracking People From the Bottom Up[END_REF] proposed body part detectors based on appearance and parallel lines. They learn the appearance of body parts by modelling segments as cylinders. Then, they convolve each frame with a template that responds to parallel lines of contrast. A feature vector (a normalized histogram in Lab space) captures its appearance of each candidate segment. They cluster the body part appearances and connect up the kinematically valid clusters with a dynamic Bayesian net. [START_REF] Hua | A decentralized probabilistic approach to articulated body tracking. s.l[END_REF] use detected edges of the contour of each limb. Each individual limb is represented by its own motion parameters. An undirected graph represents the spatial coherence among different body parts. They reinforce the spatial coherence constraints between neighboring parts using a Markov network.

Several works use multiple cues to enhance the robustness of body part detection. [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF] use color information, contours, background subtraction and motion to detect upper-body parts. The head and hands are identified using color information; the torso is detected using a rectangular grid of points interacting with a foreground silhouette; the arms, forearms and shoulders are detected robustly by fusing contour based cue and motion energy.

Upper-body parts are represented by spheres, cylinders and 2D patches. The upper body is modeled as a factor graph with limbs represented by nodes and links corresponding to articulations and non collision constraints between limbs. The complete graph includes the previous states to take temporal coherence into account. [START_REF] Broekhuijsen | Estimating 2D Upper Body Poses from Monocular Images[END_REF] use specialized detectors for the different joint and end-effector locations. Each detector uses a set of image descriptors. Background subtraction is used to identify the regions of the human silhouette. A template containing an outline of the head and shoulder is fitted to the extracted silhouette in order to obtain the 2D locations of the shoulder, neck and head. Skin color features are used to find the regions that belong to the head and arms. Edge response distributions (histograms) of limb-like edges and background-edges are compared to find the width of the lower and upper arm in the images. The 2D locations of the elbows are estimated by intersecting the lines through the centers of the lower and upper arms. Although body part detectors based in multi-visual cues have proven to be more robust, unobserved body parts caused by self-occlusion may still give rise to motion mistracking.

Combining Top-down and Bottom-up estimation

Some authors combine Top-down and Bottom-up approaches to address the limitations of each. In other words, they use the detection of body parts to improve the robustness in the estimation of the human pose parameters (e.g. joint angles). [START_REF] Lee | Particle Filter with Analytical Inference for Human Body Tracking[END_REF] fit a body model projection to a human silhouette and identify the position of hands, head and torso from the silhouette boundaries. The hands are detected along the outlines of the silhouette by extracting peaks in the convex curvature. The head is detected using a reference template representation of a head-shoulder contour. The torso is found by extracting the medial axis from the 2D silhouette. They then infer the human pose analytically by estimating the joint angles using geometry and inverse kinematics. [START_REF] Fontmarty | Vision et filtrage particulaire pour le suivi tridimensionnel de mouvements humains: applications à la robotique[END_REF] estimate the 3D pose by matching the human model projection with the foreground silhouette.

In addition, they use skin color segmentation from two cameras to obtain 3D blobs that belong to the head and hands regions. 3D pose configurations are computed using 3D hand and head positions by an analytical Inverse-Kinematics (IK) algorithm. Analytical 3D pose configurations are used to initialize automatically, recover from tracking failures, and guide search in the high-dimensional state space. [START_REF] Sminchisescu | Learning joint top-down and bottom-up processes for 3D visual inference[END_REF] propose an algorithm for learning a bidirectional function model that combines Top-down and Bottom-up processing for monocular 3D human motion estimation. Both learning process are done in alternative steps of self-training that optimize the probability of the image evidence: the Bottom-up process is tuned using samples from the Top-down process and the Top-down process is optimized to produce inferences close to the ones predicted by the current Bottomup process. Both processes converge at equilibrium, generating a consistent bi-directional function. The framework provides a uniform treatment of human detection, 3D initialization and 3D recovery from tracking failures.

Discriminative approaches

Discriminative approaches do not use an explicit human body model based representation. Instead, they infer the human pose directly from the image observations or features, using training examples to establish a direct relationship (or mapping) between the image observations and human poses; this assumes that the set of typical human poses is far smaller than the set of kinematically possible ones. Therefore, the training data needs to generalize well to observed variations over body configuration, body dimensions, viewpoint and appearance. The mapping method must also account for the highly non-linearity of the mapping between the feature and the pose space

These approaches have the advantage of avoiding the need for explicit initialization and accurate 3D modeling and rendering. They can also be used to initialize generative approaches as in [START_REF] Fossati | Bridging the gap between detection and tracking for 3D monocular videobased motion capture[END_REF]. However, they require a sufficient number of training examples in order to infer human pose properly, and they tend to be more sensitive to background clutter than generative approaches because an explicit model is not available for background masking.

Pose estimation techniques using discriminative approaches can be divided into two classes: learning-based estimation and example-based estimation. Related work using these methods will be described below.

Learning-based estimation

In Learning-based estimation, a function that maps from image space to pose space is learned using training data (Figure 2-10). Learning a function that directly recovers pose estimates from low-level image features can be highly complex as the same image features can represent different body pose configurations and same body configurations can generate different image features due to ambiguity. One of the first contributions was proposed by [START_REF] Rosales | Inferring Body Pose Without Tracking Body Parts[END_REF], who clustered (with Expectation Maximation algorithm) the space of 2D body poses into approximately homogeneous configurations. Then, for each cluster, a function was estimated to build the mapping from human silhouettes to 2D pose. This mapping was modeled using a neural network. For each new image, the mapping of each cluster is performed to yield a set of possible poses or solutions. From this set, they select the most likely pose by finding the best match using the maximum likelihood criterion. [START_REF] Grauman | Inferring 3D structure with a statistical imagebased shape model[END_REF] used PCA to build a probability density of multi-view silhouette contours augmented with 3D structure parameters (the 3D locations of key points on each silhouette).

In this way, the mixture model represents a density for the image contours together with their associated 3D structure parameters. Then for a given multi-view input contour, they essentially treat the unknown 3D structure parameters as missing variables, and find the MAP estimate of the shape and structure parameters based on the input contour data. They resolved the ambiguities of image silhouettes using the multi-view contours from cameras at known locations. [START_REF] Elgammal | Inferring 3D body pose from silhouettes using activity manifold learning[END_REF] learned an explicit low-dimensional nonlinear representation of an activity manifold from visual inputs (human silhouettes). They also learned mapping functions between such representations and both the visual input space and the 3D body pose space. In order to recover the human body pose, they projected the visual input (silhouette) to the learned low-dimensional manifold and then found the point on these manifold corresponding to the visual input using an embedding space error metric. A similar idea was adopted by [START_REF] Guo | 3D Human Pose Tracking Using Manifold Learning[END_REF], who applied Gaussian Process Dynamical Models (GPDM) (Urtasun, et al., 2006) to obtain two low dimensional nonlinear manifolds: one corresponding to the local joint angles and the other manifold the space of silhouettes for different views.

Then the nonlinear mapping between these two low dimensional spaces is learned using a Sparse Relevance Vector Machine (RVM).

Agarwal and Triggs ( 2006), ( 2004) encoded the shape of the human silhouette using histograms of shape contexts, which provides a significant amount of pose information. They applied Relevance Vector Machine (RVM) to model the nonlinear relationship between the histograms of shape contexts and the 3D poses. In order to reconstruct 3D human pose from ambiguities in monocular images, they used a mixture of regressors scheme that give multiple possible poses (Figure 2-10). [START_REF] Sminchisescu | Discriminative density propagation for 3D human motion Estimation[END_REF] also used shape context to encode the appearance of human silhouettes. Their training data consisted of pairs of typical human configurations together with their realistically rendered 2D silhouettes. They learned the multi-valued nature of the mapping from observations to pose states with a Bayesian Mixture of expert model. Each expert transforms their inputs into an output prediction and these are combined in a probabilistic mixture model based on Gaussians centered on them. The result is a conditional mixture distribution with components and mixing probabilities that are inputdependent. In this way, the inference of 3D pose is straightforward as the most probable mode can be selected. The authors showed promising results comparing their Bayesian mixture of experts (BME) conditional models with other methods like weighted nearest neighbor (NN) or the relevance vector machine (RVM). BME presented smaller average pose estimations errors.

Figure 2-10: 3D human pose reconstructed directly from silhouettes using learned RVM model [START_REF] Agarwal | 3D Human Pose from Silhouettes by Relevance Vector Regression[END_REF].

Example-based estimation

Example-based estimation avoids an off-line learning process by storing a database of training examples whose 3D poses are known. Pose estimation is done by searching for training images similar to a given input image, and interpolating from their 3D poses. One drawback of these approaches is the large amount of space needed to store the database, as exemplars sets can grow exponentially with object complexity. Example-based estimation approaches have proposed different methods to overcome this problem. [START_REF] Sullivan | Recognizing and tracking human action[END_REF] stored a set of key frames representing a specific action (e.g. playing tennis). In each of these key frames the body locations are determined manually. Then for every input frame of a video sequence, they use a shape matching algorithm based on qualitative similarity that computes point to point correspondence between shapes. Thus if any frame in the actual sequence matches to at least one key frame, the corresponding body locations are transferred from the matched key frames to the input frame using a closed loop tracking algorithm incorporating prior constraints (color and space constraints). The author argues that the use of key frames allows error recovery at any instant. [START_REF] Mori | Estimating Human Body Configurations Using Shape Context Matching[END_REF] adopted a similar idea; their approach consisted of storing a number of exemplar 2D views of the human body in a variety of different configurations and viewpoints with respect to the camera. On each of these stored views, the locations of the body joints (left elbow, right knee etc) were manually marked and labeled. The input image was then matched to each stored view, using the technique of shape context matching in conjunction with a kinematic chainbased deformation model. The locations of the body joints were transferred from the exemplar view to the input shape. These key points were used to construct an estimate of the 3D body configuration in the test image using the method proposed in [START_REF] Taylor | Reconstruction of Articulated Objects from Point Correspondences in a Single Uncalibrated Image[END_REF].

Example-based estimation can also be embedded in learned probabilistic models. [START_REF] Toyama | Probabilistic Tracking with Exemplars in a Metric Space. s.l[END_REF] used training exemplars to represent probabilistic mixture distributions of object configurations. Exemples are based on contours from silhouettes. The authors proposed the Metric Mixtures (M 2 ) approach that combines a metric space with a probabilistic framework.

They applied the approach to track walking people using the chamfer distance algorithm on binary edge images. [START_REF] Stenger | Filtering Using a Tree-Based Estimator[END_REF] proposed a tree based representation in a Bayesian probabilistic framework. The leaves of the tree define a partition of the state space with piecewise constant density. The advantage of this representation is that regions with low probability mass can be rapidly discarded in a hierarchical search, thus a significant speed-up can be achieved. [START_REF] Shakhnarovich | Fast pose estimation with parameter-sensitive hashing[END_REF] indexed training examples by learning a set of hashing functions. They proposed Parameter-Sensitive Hashing (PSH) which finds approximate nearest neighbors in sublinear time. In their algorithm, the hashing functions are sensitive to the similarity in the parameter space. They learned a feature space based on multi-scale histograms of edge directions. The results of their pose estimation were compared with the K-Nearest Neighbor method (k-NN). [START_REF] Fossati | Bridging the gap between detection and tracking for 3D monocular videobased motion capture[END_REF] relied on detecting key postures in a walking cycle. They linked sparse detections into a complete trajectory using a Viterbi-style algorithm. These detections included not only an example location but also the orientation of the person. In this way, orientation was used with a dynamic programming algorithm which allows the selection of the poses that provide the most likely trajectories according to the probabilities.

Pose tracking

Pose tracking is the process of following and estimating the human pose from frame to frame in a video sequence. Tracking the human pose has several advantages: a) the difficult task of searching the high-dimensional pose space is alleviated as pose differences between frames are usually small, b) temporal coherence is ensured when dealing with image projection ambiguities, c) the complexity of the pose estimation is reduced as an initial pose estimate is provided at each frame.

Generally, there are two strategies for tracking the pose: those that maintain or predict only one hypothesis (pose configuration) at each frame (single hypothesis tracking) and, those that propagate several hypotheses (multiple hypothesis tracking) or solutions per frame. Both approaches are described below.

Single hypothesis tracking

A simple single hypothesis tracker simply updates the pose configuration changes over time.

In [START_REF] Bregler | Twist based acquisition and tracking of animal and human kinematics[END_REF], the pose and the joint angles are updated for each time frame using a local minimization criterion initialized from the pose in the previous frame. Ning et al. (2004) propose a tracking strategy that includes two stages: prediction and updating. In the prediction stage, the posture of the moving human in the current frame is roughly estimated from the motion in previous frames. Joint angles are predicted by calculating their rotational velocities in the previous frame and apply these to the kinematical equations. The subsequent stage, minimizes the matching error between the projection of the predicted posture and the edge image.

Some authors use more complex techniques such as recursive linear filters (e.g. Kalman filter [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF]) to predict the human pose in each image. In [START_REF] Rohr | Towards model-based recognition of human movements in image sequences[END_REF], the walking motion of pedestrians is tracked by assuming a linear relation between the model parameters and the measurement errors. The model parameters in the subsequent image are predicted by applying a linear Kalman filter [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF] with constant velocities for the model parameters. [START_REF] Delamarre | 3D articulated models and multiview tracking with physical forces. s.l[END_REF] predict the motion of each frame with a linear Kalman filter in order to accelerate the convergence of their pose estimation. They supposed that the time derivatives of the parameters of the 3D model are constant. In their experiments, more than half of the iterations were saved. However, the prediction failed in cases when the motion was large and the direction of variation of some parameters of the model suddenly changed, and also when occlusions of the 3D model lasted for too long.

Unfortunately, single hypothesis tracking cannot deal with ambiguities, such as self-occlusion or image observations from monocular images. Therefore, there is always the possibility of selecting the wrong pose causing mistracking that may subsequent make recovery of the pose difficult. [START_REF] Deutscher | Tracking through singularities and discontinuities by random sampling[END_REF] showed that using a Kalman filter to predict the motion of an articulated arm can lead to false results at kinematic singularities and at self-occlusions.

Multiple hypothesis tracking

In order to overcome the problem of ambiguities in image observations, multiple hypotheses can be maintained and propagated from frame to frame. This can be done by adopting Sampling-based approaches such as Particle Filtering, e.g. the CONDENSATION algorithm [START_REF] Gordon | Novel approach to nonlinear/nonGaussian Bayesian state estimation[END_REF], [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Particle Filters are sophisticated Monte Carlo methods that aim to estimate the sequence of hidden parameters (e.g. joint angles) based only on the observed data (e.g. image features). They approximate the posterior distribution by a weighted set of P particles or samples. Each particle represents a candidate human pose that can be compared to the extracted image features. Particle filter algorithms have the advantage that, with particles (and an accurate underlying model), they can cover the full posterior distribution in model space. Particle filters can also deal with nonlinear observation models, allowing the integration of multiple data sources into one observation model (data fusion) [START_REF] Menezes | Towards human motion capture from a camera mounted on a mobile robot[END_REF]. However, when number of particles is not sufficiently large, the probability density function (pdf) of the human motion may not be represented sufficiently completely causing "particle depletion" and consequently, tracking failures.

Furthermore, pose tracking the high-dimensionality of the pose space would requires the use of an impractically large number of particles for complete coverage. All the particles must be propagated and evaluated (weighted) according to a matching cost function. Therefore, large numbers of particles have a high computational cost. Recently, many works have proposed different schemes to guide the samples (particles) more effectively in the pose space and thus reduce the number of particles required. In one of the first such contributions, [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF] proposed to reduce the number of particles by using a multi-layered search to gradually migrate the particle set toward the global maximum, at the cost of multiple iterations of sampling per frame. [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] proposed an efficient search technique that inflates each sample posterior covariance along uncertainty directions (covariance sampling) and refine each sample using continuous optimization.

The image cost function is highly multi-modal in pose space, and guiding particles towards the wrong local minima may lead to mistracking. Some works use analytical inference to compute hypotheses from image observations or assumptions in order to guide particles directly towards "good" local minima. Sminchisescu et al. (2003) use simple kinematic principles to construct "kinematic interpretation trees" that contain the possible 3D body configurations associated with a given set of projected joint centres. The different 3D configurations are linked by "forwards/backwards flipping" moves, one for each kinematic link. [START_REF] Lee | Particle Filter with Analytical Inference for Human Body Tracking[END_REF] use analytical computation (inferred from the detection of body parts) to infer a subset of the state parameters, thus reducing the degree of dependence on the Monte Carlo simulation. They demonstrated a reduction in the required number of particles and the computational load. [START_REF] Fontmarty | Vision et filtrage particulaire pour le suivi tridimensionnel de mouvements humains: applications à la robotique[END_REF] computed 3D human pose configurations from possible 3D positions of THE head and hands using an analytical Inverse-Kinematics (IK) algorithm. Samples were produced using Quasi Monte Carlo sampling [START_REF] Guo | Quasi-Monte Carlo filtering in nonlinear dynamic systems[END_REF] along the directions of lowest observability. Some modified particle filtering approaches introduce deterministic distribution sampling in order to search more efficiently in an optimal deterministic way. [START_REF] Saboune | Markerless human motion capture for Gait analysis[END_REF], ( 2007) propose a modification named Interval Particle Filtering that reorganizes the set of N particles into M subsets each formed of I particles covering in a deterministic way the "neighbourhood" of the j heaviest particles (j=1...M) of the previous frame. In this way, a larger number of neighbours I provide more accurate results but greater computational cost. [START_REF] Rose | Reducing particle filtering complexity for 3D motion capture using dynamic Bayesian networks[END_REF] introduce a particle filtering algorithm based on the Dynamic Bayesian Network (DBN) formalism that takes advantage of a factored representation of the state space to weight and select the particles. The factored representation is based on the dynamics of the joint angles. They used the factorization of the process to hierarchically resample the components of the state vector.

Combining or fusing multiple cues or features can implicitly reduce the search space. Azad et al. [START_REF] Azad | Stereo-based Markerless Human Motion Capture for Humanoid Robot Systems[END_REF] fused edge cue from foreground segmentation and 3-D distance cues into one likelihood function. They used a standard particle filter approach to compare the properties of different cues. Fontmarty et al. [START_REF] Fontmarty | Data fusion within a modified annealed particle filter dedicated to human motion capture[END_REF] combined edge cues, color histograms, 3D blob distance and skin color into a global likelihood function assuming the mutual independence of each cue. Both authors proved to reduce the search space achieving quasi real-time results. However, multiple cues that are not well combined can drastically reduce the accuracy of the pose estimate.

The number of particles can also be reduced by partitioning the high-dimensional pose space into several subspaces that belongs to each body part. Gang [START_REF] Hua | A decentralized probabilistic approach to articulated body tracking. s.l[END_REF] represent each individual limb with its own motion and enforce their spatial coherence with a Markov network. Motion posteriors of each body part are approximated by Bayesian inference and a set of low dimensional particle filters for each body part interact and collaborate with each other. [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF] proposed independent particle filtering and likelihood evaluation for each limb, while taking into account interactions between limbs through belief propagation. They reported quasi real-time results (6 fps). Although these approaches provide reductions in the computational cost, self-occlusions may be a problem as unobserved body parts may give rise to motion mistrackings.

Multiple hypotheses can also be maintained in time using a multi-dimensional non-linear optimization method. [START_REF] John | Markerless human articulated tracking using hierarchical particle swarm optimisation[END_REF] implemented a hierarchical particle swarm optimization (PSO) method to iteratively explore the high-dimensional poses pace using a population of multiple candidate solutions, named particles. The basic idea of PSO consists of simulating the unpredictable choreography of a bird flock in their search for food. The main difference between PSO and particle filter approaches is the fact that PSO uses particles to explore the search space while particle filters use particles to estimate the posterior density. In particle swarm optimization, each particle has its own velocity and communicates with other particles in order to perform the search. The authors combined hierarchical sampling with PSO in order to split the search space into 12 subspaces according to the kinematic human tree. They presented comparative results with some particle filter approaches commonly used (Condensation [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF], Annealed particle filter [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF]), showing that the PSO paradigm outperforms particle filtering with small numbers of particles. They also noted that one of the main advantages of hierarchical PSO is the ability to initialize and recover efficiently from wrong pose estimates due to the effective communication between particles in the swarm search. However, the authors reported that hierarchical PSO paradigm only performs reasonably well using multiple cameras (4 to 8 cameras) while it fails in monocular video sequences, having problems with front-back ambiguities in which all body segments lie in the same plane.

Dynamic models

Dynamic models can be used to encode the expected dynamics of a human motion, e.g. periodic motions such as walking, running, swinging, etc. They are used as predictive priors for tracking, providing more stable tracking at reduced computational cost. They are often learned from training data (e.g. body pose parameters) acquired with a motion capture system (section 2.2).

Using such models, the robustness of tracking can be enhanced even with incomplete information or occlusions, because the prior motion model allows spurious and distracting information to be discarded. They can also recover from tracking failures by using the motion priors as new starting points. Nevertheless, dynamic models have the disadvantage of depending significantly on the scope of the available training data; the set of exemplars must be sufficiently large to account for any variation that may occur in the captured movement. Using a strong motion prior limits the tracking essentially to the set of actions learnt beforehand.

Dynamic models for motion capture can be divided into two classes: high-dimensional models that are learned directly from the original pose space and low-dimensional models that consist in a reduced latent space with lower dimension, in which tracking is performed. Several works using different motion models are discussed below.

High dimensional models

Learning high-dimensional models is challenging because of the nonlinearity of human dynamics and the high dimensionality of the pose space. Several methods to learn probabilistic prior models from available training data have been proposed, they aim to correctly capture the variability of human motion, the correlations among joint angles, and the correlations of the motion over time. [START_REF] Howe | Bayesian reconstruction of 3D human motion from single-camera video[END_REF] proposed one early contribution. They model human motion as a mixture of Gaussian probabilities in a high-dimensional space. To learn the motion, they assemble the data into short motion elements called snippets of 11 successive frames. They represente each snippet as a large column vector of the 3D positions of each tracked body point in each frame of the snippet. They used k-means clustering to divide the snippets into several groups, each of which modeled by a Gaussian probability cloud in a weighted mixture-of-Gaussian model. The prior probability of any snippet obtained from this mixture model. They reconstruct the 3D pose from 2D observations by using the EM algorithm to find the probabilities of each Gaussian in the mixture and the corresponding snippet that maximizes the probability given the 2D observations. A similar idea was used by [START_REF] Caillette | Real-time 3-D human body tracking using variable length markov models[END_REF]; they partitioned the parameter space into Gaussian clusters each representing an elementary motion from balletdancing training data. Clustering was done using a variant of the EM algorithm. The transitions between Gaussian clusters use the predictions of a Variable Length Markov Model (VLMM) which can explain high-level behaviors over a long history of motions. At each frame, the state transition is chosen according to the above probabilities for each neighboring cluster. This predictive model is used in Monte-Carlo sampling framework, where noise is introduced to model uncertainty in the prediction. Ning et al. (2004) learn motion models represented as Gaussian distributions for each joint angle at any phase t in a walking cycle obtained from training examples. They assume that the Gaussian distributions at different phases of the walking cycle model are independent. They also explore motion constraints by considering the dependencies between motion parameters and representing them as conditional distributions. These Gaussian distributions are integrated into a dynamic predictive model to achieve efficient of sampling within a CONDENSATION framework [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. [START_REF] Sidenbladh | Implicit probabilistic models of human motion for synthesis and tracking[END_REF] adopted a different approach; instead of learning transition probabilities between poses, they learn a probabilistic search in a large training set in order to predict the pose at each time instant of the tracking process. The database is structured into a binary tree using coefficients learned from PCA with the top node in the tree corresponding to the coefficient that captures the dimension of largest variance in the database. In this way, they retrieve motion samples similar to the motion being tracked in a Particle Filter approach.

Low dimensional models

Several works learn low-dimensional latent space models in order to cope with the complexity of high-dimensional data (Figure 2 -12). This permits a more efficient exploration of the human pose space, for a computational effort similar to that of a high-dimensional method. Tracking in a low-dimensional manifold requires basically three processes. First, a mapping must be learned from original pose space to the low-dimensional manifold. Second, an inverse mapping must be defined from the low-dimensional latent space to pose space. Third, a method of tracking within the low-dimensional space must be defined. [START_REF] Urtasun | 3D human body tracking using deterministic temporal motion models[END_REF], ( 2005) built a motion model by performing Principal Component Analysis on a set of angular motion vectors representing a specific motion activity (e.g. walking. running, swinging). They showed that each motion activity produced separate clusters in the PCA subspace . In order to reduce the dimensionality, they represented the motion as a weighted sum of the mean motion and the first few principal directions of the training set. They incorporated a learned motion model to track the 3D configuration of the full body from monocular sequences using a single-hypothesis hillclimbing approach. This resulted in much lower computational complexity than current multihypotheses techniques. [START_REF] Rius | Action-specific motion prior for efficient Bayesian 3D human body tracking[END_REF] also performed PCA over all the poses from an action in order to find a more compact representation. They learned an action-specific lowerdimensional model by projecting all training poses to the PCA found. Then, they computed the mean of all training postures and selected enough leading eigenvectors to capture more that 90% of the variance represented in the training data. The learnt low-dimensional model is used as a priori knowledge within the Particle Filter algorithm. Hence, particles are propagated taking into account their motion history, and previously learnt motion directions from real training data. The state space is also constrained by filtering out the body configurations that are unlikely according to the motion model. PCA-based motion models have proven to be effective in reducing the dimensionality of the pose space, however PCA is not optimal as human motions are generally multimodal and have nonlinear correlations. Therefore non-linear mappings between pose space and latent space are predefined. [START_REF] Urtasun | Priors for people tracking from small training sets[END_REF] used a Scaled Gaussian Process Latent Variable Model (SGPLVM) to learn prior non-linear models for 3D person tracking from monocular video sequences. SGPLVMs have the advantage that they can be learned from much smaller amounts of training data than other techniques. In SGPLVM, likelihoods of the training data points are modeled as Gaussian processes for which the corresponding latent positions are initially unknown. As a consequence, one must now both the unknown latent positions and the mapping from the latent space to the original pose space. A kernel function is introduced to allow for nonlinear mappings. Scaling of individual data dimensions is used to account for the different variances of the different dimensions of the data. 3D tracking is accomplished with simple MAP estimators with SGPLVM used to encourage poses to be close to the training data.

Later, [START_REF] Urtasun | 3D people tracking with gaussian process dynamical models[END_REF] proposed a more sophisticated latent variable model named the Gaussian Process Dynamical Model (GPDM). Specifically, a GPDM is a latent variable dynamical model, comprising a low-dimensional latent space, a probabilistic mapping from the latent space to the pose space, and a dynamical model in the latent space (Figure 23456789101112). It provides continuous density functions over poses and motions that are generally non-Gaussian and multimodal. Given training sequences, one simultaneously learns the latent embedding, the latent dynamics, and the pose reconstruction mapping. GPDM has the advantage over GPLVM that it usually produces much smoother latent trajectories. GPDMs were shown to be effective for tracking a range of human walking styles, despite weak and noisy image measurements and partial occlusions. [START_REF] Raskin | Dimensionality reduction for articulated body tracking. s.l[END_REF] combined GPDMs with the Annealed Particle Filter body tracker proposed by [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF]. They used GPDM to reduce the effective dimensionality of the pose vector (joint angles). The particles were drawn in the latent space and then a mapping to the pose space for evaluation. This reduction improved the performance of the particle filter, increasing its stability and its ability to recover from lost targets. The reason for this is that particles generated in the latent space represent genuinely valid poses from the training data. Furthermore, the low-dimensional latent space can be covered with relatively a small number of particles.

Figure 2-12: A golf swing motion represented in a 3D latent manifold [START_REF] Urtasun | Motion Models for Robust 3D Human Body Tracking[END_REF].

Recently, several nonlinear probabilistic motion models have been proposed to better encode the sophisticated dynamics and spatial information of human poses. [START_REF] Pang | Monocular Tracking 3D People By Gaussian Process Spatio-Temporal Variable Model[END_REF] introduced the Gaussian Process Spatio-Temporal Variable Model (GPSTVM); this model comprises a low dimensional latent space with associated spatio-temporal process. They argue that GPSTVM provides a more genuine embedding of the human poses from both spatial and temporal perspectives than GPDM. They showed that GPSTVM produces smoother configuration of latent positions. They track the 3D configuration from monocular video sequences by particle filter propagation over time in the latent space, avoiding the highdimensionality of the pose space. [START_REF] Lu | People Tracking with the Laplacian Eigenmaps Latent Variable Model[END_REF] proposed the Laplacian Eigenmap Latent Variable Model (LELVM) to build priors for motion tracking. LELVM combines the advantages of latent variable models (multimodal probability density, nonlinear mappings for reconstruction and dimensionality reduction) with those of spectral manifold learning methods (no local optima, unfolding highly nonlinear manifolds and scaling to latent spaces of high dimension). LELVM uses a different type of dimensionality reduction; it defines just a correspondence between points in latent space and pose space and not a nonlinear mapping as GPDM or SGPLVM. [START_REF] Lu | People Tracking with the Laplacian Eigenmaps Latent Variable Model[END_REF] compared the performance of LELVM with PCA and GPLVM in a Particle Filter framework, showing that LELVM is superior in terms of accuracy, robustness and computation time.

Low-dimensional motion models are becoming more and more accurate and robust in representing complex human motion; however they are currently restricted to specific activities like walking, running, dancing, etc. Further research is needed to deal with transitions between different specific motions and extending motion models to broader classes of human movements and general unconstrained motions.

Our baseline approach for 3D motion capture

In this section, we describe our baseline approach previously proposed in the works of (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. Basically, our approach for 3D motion capture from real-time monocular vision consists of registering a 3D articulated model of the upper human body to 2D video sequences. No learning is involved in this algorithm because we aim to capture general human gestures. Our baseline approach works with the following assumptions:

1. The user remains seated while making gestures in front of his computer.

2. The shirt of the user has short sleeves and a uniform color.

3. The background is static. 4. In the first image of a video sequence, the user will be assumed in a fronto-parallel pose with no body part occlusions.

As seen in Figure 2-13, we extract primitives from the input image and from our human model. The similarity between the image and model primitives is then evaluated using a matching cost function. Our registration process consists searches for the pose of the 3D body model that optimally matches the primitives extracted from the 2D image. Biomechanical constraints allow poses that physically cannot be reached by the human body to be invalidated (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. At each new frame of the video sequence, 3D/2D registration is done starting from the configuration resulting from the previous frame. The following sections explain our approach in detail.

Figure 2-13: The general strategy of our approach for 3D motion capture

Our 3D upper-body human model

Our human articulated model is a kinematic tree that consists of upper-body segments connected by articulated joints according to the hierarchy described in the H-ANIM VRML standard (H-ANIM 1.1). Each segment of the kinematic structure is covered by a polygon mesh. The body segments included in our 3D model are: chest, head, upperarms, forearms and hands. The joints included are: humanoid root, neck, shoulders, elbows and wrists. In addition, our model includes 3 global translation parameters for the position the model in the 3D world. Thus, the human pose is represented as a vector of 23 parameters. In Figure 2-14, we show the kinematic chain dependencies that exist between the body segments of our model. Each articulation is associated with a node and the kinematic dependencies between joints are represented by the arcs between the nodes. We define the biomechanical constraints of our model by specifying the range allowable of motion for each joint rotation (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. Thus, the search space of 3D poses is constrained to eliminate impossible 3D configurations as well as body parts collisions (e.g. arm inside the chest). The biomechanical constraints (Table 2-

Generating 3D human pose

Body poses described by vectors of joint angles are applied to our 3D articulated body model using the OpenGL API [START_REF] Wright | OpenGL SuperBible: Comprehensive Tutorial and Reference[END_REF]. For each body segment, a list of polygons mesh is stored in a buffer. Then every polygon belonging to the same body segment (e.g. upper arm) is rotated and translated with respect to the center of the joint (e.g. shoulder).

describes the relationship between the joint angles of our vector of parameters and the BAP parameters that are sent to an avatar: 2-2: The BAP parameters sent by our motion capture system to animate a 3D avatar.

In our implementation, BAP parameters are sent through a TCP/IP socket connection to a local or remote computer where the 3D collaborative virtual environment application is installed. In this way, two or more users can express themselves in their own 3D avatars using the same collaborative virtual environment (Figure 1-2).

Region-based registration

Our registration process iteratively optimizes the match between the primitives from the model and those from image with respect to the model parameters (Figure 2-13). In our region-based registration, the primitives extracted are the color regions from the image and the 3D model. Three classes of regions are considered: skin, head and clothes. The human model in a candidate 3D pose is projected onto the segmented image and a cost function is used to measure the match between corresponding regions. The matching cost function is minimized using an optimization algorithm that requires only function evaluations (not gradients). In the following subsections, we describe in detail the method implemented in our region-based registration process (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF].

Extracting regions from images

Color samples are extracted from the first image captured. Basically, samples are extracted automatically, in contrast with the approach previously proposed in (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF], where samples had to be extracted manually. In the current system, a skin color sample is taken in the face region found with Adaboost face detector [START_REF] Viola | Rapid Object Detection Using a Boosted Cascade of Simple Features[END_REF] and a clothes sample is taken in rectangle estimated under the face. Each extracted color sample is transformed from RGB to HSV color space. For robustness to illumination changes we drop the lightness V and keep only the chrominance HS [START_REF] Vezhnevets | A Survey on Pixel-Based Skin Color Detection Techniques[END_REF]. The skin and clothes color samples in HS are modeled through a single Gaussian models (SGM). Thus, the Gaussian joint probability for a chrominance vector v in HS space is expressed as:

(2.3) (2.4) where and are respectively the mean chrominance and covariance matrix estimated from the skin color sample. and are the Gaussian parameters obtained from the clothes color sample. and are the probabilities for chrominance v to be observed at skin pixels and clothes pixels respectively.

The input image is segmented into three classes: clothes, arms and head. For each pixel in the image, if or respectively are above some threshold then the pixel is classified as skin or clothes respectively. The skin pixels in the rectangle output by the face detector are approximated with an ellipse of inertia (computed with OpenCV). Those skin pixels inside the ellipse are classified as head, while other skin pixels are labeled as arms. Finally, noise in the segmented image is cleaned up by morphological opening and closing.

Extracting regions from 3D model

The body segments of the model are associated with different classes of colors, the vertices and polygons belonging to the arms (upper-arm, forearm, and hand), chest and head are respectively skin color, clothes color and head color classes.

The model pose is generated according to the pose described in the vector of joint angle parameters (section 2.4.2). Each polygon mesh of the 3D model is projected (using perspective projection) onto the 2D image plane by computing matrix multiplications in homogeneous coordinates [START_REF] Wright | OpenGL SuperBible: Comprehensive Tutorial and Reference[END_REF], and flat-rendered with its given color label (Figure 2-19).

Evaluating the match between model and image regions

The projected model (section 2.4.4.2) is overlapped onto the segmented image (section 2.4.4.1) and their match is measured using the non-overlapping area ratio [START_REF] Ouhaddi | Vers la modélisation du geste par la vision. s.l. : Traitement du signal[END_REF]: (2.5) where q is the vector of parameters describing the candidate 3D pose, m is the number of color classes, A c is the set of pixels with the c color class in the segmented image, B c (q) is the set of pixels with the c color in the projection of the 3D model and | X | represent the number of pixels in X.

Optimizing the match between regions

The non-overlapping ratio is then minimized with respect to the vector of joint angle parameters using a downhill simplex optimization algorithm [START_REF] Nelder | A simplex method for function minimization[END_REF] under biomechanical constraints (Table 2-1). The downhill simplex method is a nonlinear optimization technique that requires only function evaluation without calculation of derivatives. The method uses the concept of a simplex, which is basically a polyhedron of vertices within a N-dimensional space (in our case, 20 dimensions corresponding to the joint angles). From an initial 3D pose, we build an initial simplex by generating new test points (candidate 3D poses) that correspond to each vertex of the simplex. Each test point is evaluated by the objective function (non-overlapping ratio) and ordered to determine the highest , second highest and the lowest point in the simplex. After, the centroid of all the points except , is generated. From the initial simplex built, the method iteratively changes the shape of the simplex adapting to the nonlinearities of the objective function by four operations: reflection, expansion, one-dimensional contraction and multiple contractions (Figure 2-21). Algorithm details of these operations are provided in the following: Downhill Simplex algorithm 1) Order the points according to the values at the vertices: .

2) Compute the centroid of all points except .

3) Reflection: a reflected point, , is found by reflecting through with the following equation:

(2.6) If : then replace with and go to step 1.

4) Expansion: if then continue to step 5, else if then expand the simplex along the centroid direction with the hope that the new expansion point, , will be better that . The expansion is done by the following equation:

(2.7)

If

: then replace with and go to step 1. else replace with and go to step 1.

5) One dimensional contraction: now, it is certain that then the simplex contracts along the centroid direction with the hope that the contracted point will be better that the worst point . The contraction is determined with the equation:

(2.8)

If

: then replace with and go to step 1. else go to step 6. 6) Multiple contraction: contract the whole simplex around the lowest point , using the following equation: , ϵ (2.9) where α, γ, ρ and σ are the factors for reflection, expansion, contraction and multiple contraction respectively (α=1, γ=2, ρ=0.5 and σ=0.5 [START_REF] Nelder | A simplex method for function minimization[END_REF]).

These operations are applied iteratively in different cases in order to converge toward an optimal solution [START_REF] Press | Numerical Recipes in C: The Art of Scientific Computing[END_REF]. In our implementation, the convergence criterion is based on the fractional range between the highest value point and the lowest value point of the simplex generated at each step. For each frame, the registration is initialized using the registered pose from the previous frame. In this way, the registration process benefits from the temporal coherence of the motion. The biomechanical constraints (Table 2-1) define a convex domain in the pose space to which the simplex is constrained. This allows a reduction of the search space [START_REF] Ouhaddi | Vers la modélisation du geste par la vision. s.l. : Traitement du signal[END_REF].

It is important to note that the size of the initial simplex is critical for the registration process.

An over small initial simplex can lead to the method getting trapped in a local minimum, while a very large initial simplex may cause loss of temporal coherence and possibly a failure to track the 3D pose correctly (Figure 2-23). Indeed, the real-time constraint can only be met with sub-optimal rather than global optimization algorithms, so temporal coherence is a key feature for tracking in the high-dimensional pose space. The next figure shows the variation of the registration error with respect to the size of initial simplex. From these experiments, we found that a size ratio from 1.5 to 2.0 allows good tracking.

Figure 2-22: The effect of increasing or reducing the initial size of the simplex in our registration process until convergence. The abscissa is the frame number in the video sequence. The black line is the residual error of the non-overlapping ratio using a relatively large size of simplex (factor = 3.0). The gray line gives the corresponding residual error using a relatively small simplex (factor = 0.5). Finally, the dash gray line use a medium-sized simplex (factor=1.5), which provides smaller residual errors in our registration process.

Conclusions and Future Work

In this chapter, we have presented a brief summary of current technologies commonly used for human motion capture. We exposed the importance of using computer vision based techniques for motion capture. Then, we presented an exhaustive analysis of existing methods for 3D motion capture by computer vision. Real-time and non-real-time, as well as single and multi-cameras works are considered. Firstly, images features used for motion capture are presented, and then we categorized several methods used for human pose estimation and tracking from image features. Finally, several motion models used as priors are described.

The strengths and limitations of these methods are discussed.

We have presented our baseline approach that consists in registering a 3D articulated model of the upper human body on 2D video sequences (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. First, we described our upper-body model formed by polygon meshes and the vector of parameters used to represent the 3D model poses. We described the biomechanical constraints used to avoid impossible 3D pose configurations and the MPEG-4 BAP parameters used to animate a 3D avatar. After, we introduced our region-based registration that consists in matching color regions from the image and the 3D model projection. The downhill simplex algorithm used for the optimization process is described briefly. Finally, we show some experiments to show the importance of the size of the simplex in the pose tracking results.

In the next chapters, we present the methods proposed to attack the limitations and disadvantages found in our baseline approach. Basically, a first disadvantage in the prototype system previously developed (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF] is the absence of a background subtraction method that allows working only with the region of interest (actor) in the image.

A second disadvantage is the fact that the 3D model cannot adapt automatically to the morphology of the actor. These disadvantages limit the applicability of the system for several users and different environments. In a following step, we will propose new methods to achieve a more accurate and robust tracking under limited real-time computation. In this case, exhaustive experiments must be done on several video sequences in order to validate the accuracy and robustness achieved by our proposed algorithms.

Chapter 3

Region-based vs. edge-based registration for 3D motion capture by monocular vision

Introduction

In this chapter, we develop new algorithms to enhance the tracking performance of our baseline approach (section 2.4). First, we implement new modules to extract the silhouette of the user and automatically calibrate our 3D model. In order to improve the accuracy of the pose estimation, a new registration step that works by matching color then edges is proposed.

Combining these features allow us to achieve robustness and accuracy in 3D motion capture limited by real-time computation. Combining color and edges may be difficult as each descriptor provides different image information; moreover, edges are much more localized image features, giving improved accuracy but potentially causing mismatches and errors in the pose estimation process. The proposed algorithms typically require less computation than the existing approaches, making them suitable for real-time use in consumer computers. An careful experimental analysis validated the proposed approach with respect to these challenges.

First, we briefly describe the modules implemented for our system. Then, a robust background subtraction algorithm for the extraction of the human silhouette is proposed.

After this, we introduce our 2 step approach based on matching color regions and edges. The experimental performance of each step is studied and we discuss how a balance between the two steps that makes the best use of the limited computation resources.

Implementation of our approach

Our motion capture system is divided into two main stages: initialization and tracking. Initialization refers to the process of automatically learning the appearance of the background and the user, and the size of his body and limbs. During tracking, we extract image features from the input video sequence and estimate the 3D pose that best matches them in real-time [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. The pose data is used to animate a 3D avatar in a collaborative virtual environment.

The initialization modules depicted in Figure 3-1 are briefly summarized as follows:

 Background learning: images without the actor are collected to obtain a statistical model of the empty scene. This will be used during tracking as a reference to extract the human silhouette (section 3. The correspondence between the projected model and the segmented image is evaluated using a matching cost function. A 3D pose that minimizes this cost function is estimated using the down-hill simplex algorithm [START_REF] Nelder | A simplex method for function minimization[END_REF] under biomechanical constraints (section 2.4.4).  Edge-based registration. This module uses edge information to improve the accuracy of the pose estimated by the region-based registration step. The occluding edges of the 3D model are projected onto the distance map computed in the image processing thread. The total distance between the occluding edges from the 3D model and the edge from the image is then minimized using the simplex algorithm ( [START_REF] Nelder | A simplex method for function minimization[END_REF], [START_REF] Marquardt | An Algorithm for Least-Squares Estimation of Nonlinear Parameters[END_REF])) (section 3.5).  Send BAP parameters. The resulting 3D pose parameters are encoded as MPEG-4

BAPs (Body Animation Parameters) and sent through a socket connection to animate a 3D avatar in a virtual environment.

Figure 3-2: Real-time modules of our 3D motion capture system

Automatic model calibration and pose initialization

The body model is calibrated in order to make it similar to the actor captured in the video. This can be done by adjusting the shape parameters (length, height and width) of each body part of the 3D model. The vector of joint angles is also adjusted to make the pose of the model similar to the pose of the actor in the first input image. The mesh model is projected and overlapped to the actor in the first captured image of the video sequence. The shape of each body segment is then updated to maximize the overlap between each segment of the projected model and the human in the image (Figure 3-3). We use the region-based matching algorithm to automatically calibrate the 3D model and initialize the pose [START_REF] Chen | Markerless monocular motion capture using image features and physical constraints[END_REF]. We assume that the first frame of the video sequence contains the actor in a pose with no self-occlusions of body parts (Figure 3-3). The automatic model calibration consists of three steps: model translation, pose alignment and shape adjustment. We describe the proposed method below.

Model translation: let be an initial guess of the translation of our 3D model in world coordinates and let be the centroid of the actor"s head in the image. We compute the 3D world coordinates of the actor"s head using homogeneous coordinates. Then the 3D model is superposed on the actor by computing the displacement between the centroid of the body model"s head in world coordinates and the centroid of the actor"s head in world coordinates.

(3.1)

The model global translation is updated from the initial translation with respect to the displacement :

(3.2) Finally, we iteratively adjust the global translation that corresponds to the distance between the image plane and the 3D model. As the true depth of the actor is unknown, we use the nonoverlapping ratio (2.6) to find the global translation that best matches the segmented image. (3.3) where is the non-overlapping ratio measure for the projection of the 3D model in an initial pose , and are minimum and maximum distance between the image plane and the 3D model in world coordinates.

Pose alignment: we minimize the non-overlapping ratio (section 2.4.4.3) by optimizing the vector of joint angles until convergence.

Shape adjustment: Let the vector be the scale parameters that correspond to the shape of a body segment. The scale parameters (length), (height) and (width) are applied to each vertex of a polygon by the following transformation: (3.4) are the scaled coordinates of a vertex that belongs to the same body segment in our 3D model. Now consider the vector that contains the scale parameters of all eight body segments our 3D model. In total, we have a vector of 24 shape parameters. Again, we minimize the non-overlapping ratio by optimizing this 24-dimensional shape vector until convergence.

After finishing the three steps described above, we have a 3D model aligned and fitted to the segmented human silhouette. These steps are done only one time at the first frame of a video sequence, so they do not represent a limitation for real-time computation. In the Figure 34, we show the results of the three steps described for automatic calibration of our 3D model. We observe that although the initial translation of the 3D model is imprecise, the model is fitted correctly to the segmented silhouette and ready for motion tracking.

Background subtraction for extracting human silhouette

Extracting the human silhouette allows to be processed the motion capture only those regions of the image that contain the subject of interest or actor. This helps to ignore static objects in the background that are not of interest (walls, tables, windows, etc.).

Silhouettes can be extracted using a background subtraction algorithm [START_REF] Herrero | Background subtraction techniques: Systematic evaluation and comparative analysis[END_REF] provided that the appearance of the environment or background is different from that of the object of interest or foreground. The background usually consists of still objects while, when considering human pose estimation, the foreground is the person in the image. Background subtraction models the appearance of the empty scene (background) using pixel-wise image features and compares this background model with the features observed at the same pixel of the input image where the object of interest (e.g. human) may appear [START_REF] Li | Statistical modeling of complex backgrounds for foreground object detection. s.l[END_REF], [START_REF] Guha | A Multiscale Co-linearity Statistic Based Approach to Robust Background Modeling[END_REF]. Features that appear to have changed significantly are thresholded, with classical post-processing to output the human silhouette region.

The naive approach to background subtraction assumes the temporal constancy of each background pixel intensity (or RGB color), with very little variation caused by image noise. However, in most practical situations, temporal changes do occur due to variations in illumination (shadows, changing sunlight, etc.). Several works have experimented with different color spaces to handle illumination changes. Apart from using RGB intensity values [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF], researchers have experimented with normalized RGB [START_REF] Paragios | A mrf based approach for real-time subway monitoring[END_REF], HSV [START_REF] Mckenna | Tracking color objects using adaptive mixture models[END_REF], YCrCb [START_REF] El Baf | A Fuzzy Approach for Background Subtraction[END_REF], etc. Some works obtain performance improvements using image gradients [START_REF] Javed | A hierarchical approach to robust background subtraction using color and gradient information[END_REF] or optical flow [START_REF] Mittal | Motion-based background subtraction using adaptive kernel density estimation[END_REF] features. Some contributions also implement complex statistical modeling of feature distributions (mixture of Gaussians [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF], PCA [START_REF] Rymel | Adaptive Eigen-Backgrounds for Object Detection[END_REF], Hidden Markov Models [START_REF] Stenger | Topology free hidden markov models: Application to background modeling[END_REF]). To date, no algorithm or feature has proven to be robust to all changing environment conditions or complex backgrounds. Moreover, the computational cost of some background subtraction algorithms is quite high, making them inappropriate for real-time work.

In this section, we propose a relatively simple real-time algorithm for background subtraction in order to extract human silhouettes under common lighting variations. Two robust features are combined: color chrominance and gradient. Both features provide some robustness to variations in lighting conditions. We use the chrominance components of the YCrCb color space. The Y (luminance) component is ignored for better robustness to lighting variations. However chrominance remains somewhat sensitive to illumination changes [START_REF] Liévin | Nonlinear color space and spatiotemporal MRF for hierarchical segmentation of face features in video. s.l[END_REF]. In order to gain robustness, we also include gradient-based features, these features exploit differential relationship within the neighborhood of each pixel and therefore they are less sensitive to lighting changes (Bernier, 2006). Both features are modeled by Gaussian densities, which describe the background scene statistically taking into account the variations of the image features due to illumination changes. The final foreground region is extracted by applying probability thresholds and using morphological operators.

Learning the background model

The background model describes the variations in the appearance of background pixels that are due to changes in the lighting conditions. We model the pixel variations using a Gaussian law per feature at each pixel. For background images from a sequence of images indexed by time t, we extract gradient orientations and chrominance for each pixel s = . Let G = and C = be the gradient vector and chrominance vector at pixel s in the reference background image . The gradient vector G at each pixel is obtained using a Deriche filter (Deriche, 1990) on the gray level background images. From G we derive the gradient orientation .

(3.5)

C is the vector of chrominance components from the color space YCrCb. RGB conversion to YCrCb is achieved with the OpenCV library (OpenCV, 2010). From a sequence of background images, we extract the gradient orientation and chrominance vector C for each pixel s. Then we compute, for each pixel s, the mean and variance of the gradient orientations and the mean vector and covariance matrix of the chrominance vectors.

Extracting the foreground silhouette

Using the learned background model, we extract the foreground object (the human silhouette) from the scene by combining the gradient and chrominance features. The proposed algorithm consists of five steps: 1) feature extraction, 2) feature combination, 3) pixel classification and 4) foreground segmentation.  Extract features. For each input RGB image , we extract the oriented gradient features (equation 3.3) and the chrominance vector features (from color space YCrCb.  Combine features. We compute a background probability pixel map from the oriented gradients and a background probability pixel map from the chrominance vectors

. Then, we combine the background probabilities from both features into a mixed probability map by keeping the maximum probability as a simple way to combine these different features.

(3.12)  Pixel classification. A binary mask of the pixels classified as foreground is generated by thresholding  Foreground segmentation. At this step, the foreground pixels mask may contain noise and small regions other than the human silhouette. Therefore a post processing is applied to in order to clean up the mask. First, we apply a morphological opening to remove small regions or noise in the foreground mask, then a morphological closing to fill small holes in the foreground.

Background subtraction results

We have tested this background subtraction algorithm on indoor video sequences (office, home, laboratory, etc.) exhibiting representative illumination sources with typical variations (incandescent and fluorescent light bulbs, switching lights, natural sunlight variations, shadows, etc.).

We experimentally compared the performance of our algorithm with two other common background subtraction methods. The first is a naïve approach that computes absolute differences of RGB pixel values between the input image (with foreground) and a reference background image. The differences are thresholded and post-processed with morphological operators. The second method compared is an adaptive Gaussian mixture model (GMM) in RGB channels proposed in [START_REF] Zivkovic | Improved adaptive Gausian mixture model for background subtraction[END_REF] and [START_REF] Zivkovic | Efficient adaptive density estimation per image pixel for the task of background subtraction[END_REF]. This method automatically updates the parameters of the GMM model in order to improve robustness to shadows and illumination changes. In order to compare the three algorithms, the same post processing method (morphological opening and closing) is used for all of them. We also note that the silhouette extracted with the proposed algorithm is more accurate in the sense that it presents fewer holes inside the foreground region. However in terms of computation cost, our proposed algorithm is more expensive than the other two (Table 3-1).

This limitation can be overcome by using the GPU to process and classify each pixel in parallel.

Edge-based registration

Our region-based registration method requires only a partial overlap between colored regions in order to converge towards a 3D pose that is approximately correct. However, it is not very accurate because the boundaries of the segmented regions are often inaccurate.

An example of this limited accuracy is showed in the figure 34567, where the hands of the actor overlap while the hands of the 3D model projection remain separated after the completion of the region-based registration. The segmented regions do not provide enough information to improve the accuracy of the 3D pose as the limb borders are not visible in them. To improve the precision of registration, we propose a further edge-based registration step. This works by matching edges in the captured image to the occluding edges of the 3D model [START_REF] Lu | Model-based integration of visual cues for hand tracking[END_REF], (Sminchisescu, et al., 2003). Here, the initial 3D pose is the pose output by the region-based registration. For each image, we compute a map giving the distance between each pixel of the image and the nearest edge. The distance between the edges of the input image and the boundary of the projected 3D model is minimized using the downhill simplex method [START_REF] Nelder | A simplex method for function minimization[END_REF]. The details are presented in the following subsections.

Extracting edges from images

Edges are discontinuities in the captured image. In our case, they convey information about the boundaries of the human body and limbs. We extract image edges using a Deriche filter that can be implemented with a fast and recursive algorithm (Deriche, 1990). Edges are extracted only inside the foreground silhouette. From the extracted edges we compute a chamfer distance transform [START_REF] Borgefors | Distance transformations in digital images[END_REF], which supplies each pixel of the image with a value representing the distance to the nearest edge pixel of the captured image (figure 345678).

Extracting occluding edges from 3D model

The occluding edges of a 3D surface are the lines of the surface where the observation direction is tangent to the surface [START_REF] Franco | Une approche hybride pour calculer l'enveloppe visuelle d'objets complexes. s.l[END_REF]. Along these lines, the surface folds behind itself, resulting in a discontinuity of the visible surface.

On a 3D mesh, occluding edges can be found as the set of the visible edges that connect backfacing polygons to front-facing polygons [START_REF] Raskar | Hardware support for non-photorealistic rendering[END_REF]. They can be extracted easily and efficiently with the OpenGL API, by rendering with culling based on the normal orientation. In a first step, backwards triangles and their edges are rendered with some constant color (different from the canvas background color). In a second step, the inside of frontwards triangles is rendered with the background color while backwards triangles are ignored, so only the occluding edges remain highlighted in the projected image (Figure 3-9) [START_REF] Baroud | Acquisition du geste par vision artificielle en temps réel[END_REF].

Evaluating match between edges

For edge-based registration we calculate the mean distance between the projected occluding edges of the model and the edges in the input video image. The mean edge distance is computed by masking the above distance map with the projected binary image of the 3D model occluding edges (figure 3-10), and summing: (3.13) where is the mean edge distance, is the distance transform image, are the pixels in the projected occluding edges of the 3D model. This function is minimized with the downhill simplex algorithm [START_REF] Nelder | A simplex method for function minimization[END_REF] under biomechanical constraints as previously done for the region-based registration.

Optimizing the match between edges

Our registration process basically consists of minimizing, first non-overlapping ratio, then the mean edge distance. Edge-based registration improves the accuracy of the 3D pose by matching the 3D model limbs with the image edges (figure [3][4][5][6][7][8][9][10][11].

It is important to note that edge-based registration requires an initialization close to the optimum because edge clutter leads to many local minima (e.g. edges from clothing, textures, noise) that make it difficult to recover the correct 3D pose. Therefore, the region-based registration should output a 3D pose in which the body and limbs are projected close enough to the edges of the subject in the image. Because the edge-based distance has multiple local minima, we need carefully to constraint the search space to match only the body and limbs. Therefore, the initial simplex for the edgebased registration is usually the small simplex at final iteration of the region-based registration, so that the edge-based registration starts searching in a reduced space around the 3D pose estimated by region-based matching. However, if the region-based registration reaches convergence, the size of this simplex will tend to zero. In this case we use a small simplex size experimentally optimized for edge-based registration.

Performance experiments for registration process

Iterative optimization in high dimensional spaces usually requires a large and variable number of iterations to converge. Because we are interested in real-time motion tracking, we have to limit the computation time and thus, the number of iterations per image. Unfortunately, this will also increase the residual error in the registration process. In each image of the video sequence, the initial 3D pose is the final output (registration) of the previous image. Figure 3-13 and Figure 3-14 show limiting the number of iterations leads to degraded pose estimates in a video sequence.

Figure 3-13: The effect of limiting thr number of iterations on the residual error (ordinates) of our region-based registration. The abscissa is the frame number in a video sequence. The black line is the non-overlapping ratio minimized to convergence by the region-based registration while the gray line is limited to 500 iterations, which is the maximum number of iterations permissible for real-time computation. We see that limiting the number of iterations usually degrades the pose estimates. The computation time of our prototype for 3D motion capture varies with the number of iterations, the captured image size, the processor speed (CPU) and the graphic card (GPU). Table 3-2 shows the computation time on three hardware platforms 2 with varying numbers of iterations shared in our two-steps registration process. Table 3-3 presents a comparison of the computation time 3 of our prototype for higher resolution images.

For real time tracking, the available computation time for each captured frame must be shared between the two steps of the registration process. For this reason, we experimentally analyzed the performance (robustness and accuracy) of our registration process by varying the number of iterations of each registration step (region-based and edge-based), searching for an optimal balance between the overall performance and computation time of the combined method (region-based and edge-based). In the following subsections we present an experimental analysis of the registration performance (robustness and accuracy) vs. the computation time 2 Platform 1: CPU Intel Core 2 Extreme Q9300 2.53 GHz with a GPU NVIDIA Quadro FX 3700M.

Platform 2: CPU Intel Pentium 4 3.6 GHz with a GPU NVIDIA Quadro FX 1400. Platform 3: CPU Intel Pentium 4 3.0 GHz with a GPU NVIDIA GeForce 9600 GT. 3 CPU Intel Core 2 Extreme Q9300 2.53 GHz with a GPU NVIDIA Quadro FX 3700M.

and we discuss how a balance can be found between the two steps in the face of limited computational resources. 3-3: Mean computation time for higher resolution images. Image processing includes the background subtraction algorithm, color segmentation, edge detection and the chamfer distance transform. The computation time is similar for each registration step (nonoverlapping ratio and mean edge distance). The ratio indicates the relationship between the computation times of the mean edge distance and thenon-overlapping ratio.

Number of iterations

Robustness evaluation for real-time motion tracking

Our goal is to track general human gestures from monocular images. Unfortunately, the inherent difficulties of the problem (lack of depth information, body part occlusions, fast motions, and noisy observations) may affect the performance of our registration process and lead to tracking failures (mistrackings).

Robustness is an important performance metric for our motion capture system. Here, we define robustness as the ability of the system to provide accurate or approximate estimates given some degree of noise presented in the input data. In addition, a robust system has the ability to recover quickly from mistrackings and holds up well under exceptional circumstances or various attack strengths. We are interested in measuring the robustness of our two-step registration process under real-time computational constraints.

In order to quantify the robustness of our approach, tracked real video sequences of humans performing a large variety of gestures. For each video sequence, we computed the mean residual error of each evaluation function and also the number of mistracked frames with varying numbers of iterations in the registration process. We used 6 video sequences 4showing various gestures with occlusions (e.g. arms crossed), fast motions, including motion in the depth direction (Figure 3-15) and a person not exactly facing the camera.

Experimental results on robustness evaluation

We analyzed the performance from 1 to 500 iterations assuming the computation time below 100 milliseconds (see Table 3-2), thus allowing tracking at 10 Hz or more. In each experiment, we sampled the residual value of the non-overlapping ratio and mean edge distance. We compute the mean residual values of the non-overlapping ratio and the mean residual of the mean edge distance for the whole video sequence of frames:

(3.14) (3.15)

A way of measuring the robustness of each registration step is by counting the number of failures for each experiment. We consider as failures or poor registrations all residual values that are above a predefined threshold (a "peak") for the evaluation function. If the residual value is larger than this, we consider that the solution output by the optimization algorithm to be an "erroneous" registration. In the figures below (Figure 3-16, Figure 3-17, Figure 3-18 and Figure 3-19), we experimental results from video sequence 2 as it contains the most varied movements and gestures with depth ambiguities and partial body occlusions.

Experimental analysis on robustness in real-time

These experimental results (the 3D surfaces showed in the figures above), allow us to understand the performance and robustness of the region-based and edge-based registration steps. From figures 3-16 and 3-17, we see that the region-based registration step reaches convergence more quickly that the edge-based one. The figures 3-18 and 3-19 show the relative instability (significant number of "peaks" in residual error) of the edge-based registration step compared to the region-based one. So we need to combine the robustness and stability of the region-based registration with the accuracy of the edge-based one.

To achieve real-time results, we need to limit the number of iterations as a function of the computational power of the platform. We measured the maximum allowable number of iterations experimentally for each platform (Table 3-2). In order to achieve robustness in realtime, we must give priority to the stability of the registration when the number of iterations is below 200 (found experimentally from Figure 3-18). Thus, in this case, all the iterations are executed by the region based step. However, when the total number of iterations exceeds 200, the number of mistrackings in the region-based step registration becomes comparatively small (Figure 3-18), and we can increase the accuracy of the registration by allocating some iterations to the edge-based step. Note that, although the performance variation (figures 3-16, 3-17, 3-18 and 3-19) was similar for all the videos tested, the video sequence 6 (Figure 3-15) presented the largest number of failures (mistrackings) due to the ambiguities caused by the self-rotation motion of the subject.

Accuracy evaluation for real-time motion tracking

In the previous section, we analyzed the performance of our two-step registration process with respect to the residual 2D matching error and its numbers of mistrackings. In this section, we analyze the performance with respect to the accuracy of the 3D pose estimates achieved in real-time.

Quantitative evaluation of 3D accuracy requires video sequences with ground-truth motion data. Capturing real human motion would require complex and expensive equipment. Instead, we used a set of synthetic communicative gesture sequences (Li, et al., 2009) generated using the GRETA embodied conversational agent [START_REF] Hartmann | Implementing Expressive Gesture Synthesis for Embodied Conversational Agents[END_REF]. Each communicative gesture consists of a sequence of H-Anim (H-ANIM 1.1) skeleton joint angles standardized with MPEG-4 BAP [START_REF] Taubin | SNHC verification model 7.0. s.l[END_REF] animation parameters. In order to evaluate the accuracy of our approach, synthetic video sequences were generated by animating a 3D avatar using the motion data from the GRETA database. The following figures ( Fast movement is present between the second and fourth images.

Experimental results for accuracy evaluation

We tracked the motion in the synthetic video sequences using our method and compared, for each frame, the pose estimated by our approach with the true synthetic pose.

Note that the different joint angles do not all have the same importance for the resulting pose, so we do not consider an error measure based on angles. Instead, we compute the pose estimation error from the 3D distances between joints [START_REF] Balan | A Quantitative Evaluation of Video-based 3D Person Tracking[END_REF] as follows:

(3.16) where is the average distance (in millimeters) between their articulations of the estimated pose and those of the ground truth pose.

is the 3D coordinate of the articulation in the estimated pose and is the corresponding coordinate in the true pose.

As we are mainly interested in arm motion, we included only the 3D distances for the wrist and elbow joints, which allows a better analysis of the pose estimation errors than the distances for all the joints of the 3D model.

Using the above error measure, we performed an experimental analysis of accuracy on the GRETA sequences. Again, we varied the number of iterations from 1 to 500 for each registration step and we computed the mean pose estimation error for all frames of the video sequence:

(3.17) First, we evaluated the 3D accuracy provided by maintaining each registration step to convergence. Figure 3-24, illustrates that edge based registration is indeed more accurate than region-based registration when iterating to convergence. However, we also note that edgebased registration does not always achieve better accuracy e.g. in the case of the monocular ambiguities in frames 70 to 90. Such ambiguities will be addressed in the next chapter. Obviously, the registration accuracy will be reduced by limiting the number of iterations for real-time computation. However, comparatively accurate results can still be achieved with a limited number of iterations by allocating the iterations appropriately to the region-based and edge-based registration steps (Figure 3 -25). In this way, we benefit from the rapid convergence and robustness of region-based registration, and also from the better precision achieved by the final edge-based iterations. Given the results shown, we need to determine how the available computation time should best be divided between the region-based and the edge-based methods, in order to achieve the best overall accuracy.

To find the optimal number of iterations, we again generate graphs showing the residual accuracy of our registration process with respect to the number of iterations of each registration step (Figure 3-26). These surfaces clearly show that 3D pose accuracy is not systematically improved by adding more iterations. The reason is that the registration process may find solutions that match the 2D image observations without necessarily corresponding to the real 3D pose. It cannot fully remove the ambiguities caused by the lack of depth information in monocular images.

From Figure 3-26, we also note that the 3D residual error behaves differently for different video sequences. For example, the sequence "raising arms gesture" yields the lowest residual error values while the sequence "joy gesture" yields the highest error values. The reason is that the "raising arms gesture" (Figure 3-20) contains more fronto-parallel motion than indepth motion; hence there are fewer ambiguous local minima in the pose space. Based on this analysis, depth ambiguity appears to be the main source of residual 3D error.

Figure 3-26: The mean residual 3D error in millimeters (z-axis) on the video sequence with respect to the numbers of iterations of the region-based registration (x-axis) and edge-based registration (y-axis). The surfaces correspond to the video sequences "raising arms gesture" (a), "joy gesture" (b), "exclaiming gesture" (c) and "asking gesture" (d).

Instead of 3D joints positions, the 2D positions of their projections in the image plane allow accuracy to be evaluated independently of the ambiguities in the depth direction. The residual 2D error of the articulations can be obtained as follows: (3.18) where is the average distance (in millimeters) between the 2D projections of the articulations (wrists and elbows) of the estimated pose and these of the ground truth pose.

Here

is the 2D projected coordinate of articulation of the estimated pose and is that of the true pose.

In order to find the optimal number of iterations for the region and edge-based registrations, we plot the residual 2D error with respect to the number of iterations allocated to each registration step. These graphs are generated by computing (equation 3.18) on each sequence (Figure 3-27).

Figure 3-27: Graphs of the mean residual 2D error in millimeters (z-axis) for each video sequence, with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis). The plots correspond to the video sequences "raising arms gesture" (a), "joy gesture" (b), "exclaiming gesture" (c) and "asking gesture" (d). The residual 2D error decreases with the number of iterations for each sequence.

We note that the errors for the "rising arms gesture" decrease faster because less motion in depth is involved; however the errors for the "asking gesture" decrease slowly. Also the number of error peaks is related to the type of motion. Difficult motions (e.g. self-occlusions, fast motions, rotations) make the tracking more unstable because both registration steps may become stuck in incorrect local minima.

Experimental analysis for accuracy in real-time

In order to model the general behavior of the residual 2D error, we averaged the mean residual 2D errors over our set of 4 synthesized videos (each sequence containing 165 frames) (Figure 3 From Figure 3-28, we see once again that low errors can be achieved by successive regionbased and edge-based registration for large numbers of iterations. We need to respect the realtime constraint, which can be expressed as an inequality on the numbers of iterations per frame: (3.20) where and are respectively the time required for a single iteration on regions and on edges, and is the time available per frame. Obviously, using all of the available computation time will provide better results, so the minimal error will be achieved for iterations numbers that satisfy: (3.21) We search for the minimal error along this line.

Figure 3-29: Finding the optimal numbers of iterations for a constant computation time. The optimal number of iterations is the point of the residual error curve (blue curve) that is tangent to the straight line of constant computation time ρ with angle θ. This problem is now reformulated as follows:

Given some available computation time ρ, what is the couple of numbers of iterations that belongs to this group of points and that has the lowest residual error?

Figure 3-29 illustrates this problem, the angle is computed from the ratio between the computation time of the mean edge distance and the non-overlapping ratio functions (ratios for several image resolutions are shown in Table 3-3).

Thus given the polynomial model of residual 2D errors (Figure 3-28), we search for the number of iterations with lowest residual errors that has computation times ρ.

From equation (3.21), we define a new coordinate system ( by rotating the original coordinate system ( ) through the angle about the origin. This gives the optimal point on the residual error for a given computation time (ρ). Returning to the original coordinate system ( ) by rotating the coordinate system ( ) through the angle about the origin gives the optimal curve describing the number of iterations allocated to each registration step in order to obtain the best accuracy in real-time. This curve is shown in the following.

Figure 3-30: The optimal curve for the numbers of iterations allocated to each registration step for the best accuracy in real-time. The abscissa is the number of iterations for regionbased registration and the ordinate is the number for edge-based registration. The optimal curve (black line) is superposed on the mean residual 2D error surface computed from multiple video sequences.

The optimal curve shown in the Figure 3-30, shows that, when large numbers of iterations are permitted, the optimal pose estimation is achieved by combining region-based and edge-based registrations. However the accuracy given by edge-based registration is advantageous only after a certain number of iterations of region-based registration (150). In fact, the results obtained are similar to the conclusions obtained in the previous experimental analysis of robustness (section 3.6.1): in order to obtain the most accurate and robust results in real-time, we must give priority to the stability of tracking for the first iterations, only then we improve the estimation accuracy using edge-based iterations.

By measuring the and computation times for a single iteration and using the resulting optimal curve, we can adapt our motion capture prototype to any host hardware platform, finding the allocation of regions-based and edges-based iterations that will achieve the best results.

Conclusions and Future Work

We have presented a real-time 3D human motion capture algorithm for monocular, based on registering a 3D articulated model to color regions and then to image edges. The pose of our 3D human upper-body model is controlled by 3 global position parameters and 20 joint angles. Our registration method iteratively optimizing the match between primitives extracted from the model and the images by varying the model position and joint angles under biomechanical constraints.

Our method is divided in two main stages: initialization and real-time tracking. In the initialization step, a statistical model of the background, based on image gradients and chrominance values, is computed and color samples on the subject are obtained and modeled probabilistically. The 3D model is also calibrated automatically and the pose is initialized. In the real-time stage, image primitives (regions and edges) from the foreground (human silhouette) are extracted for each captured image and the 3D model is projected into the image by rendering color and edges primitives according to the pose described in the vector of parameters. Our registration process searches for the best matching correspondence between the model and image primitives using a region-based registration followed by an edge-based registration step. The 3D pose estimated for each frame is used to animate a 3D avatar by converting the vector of joint angles into MPEG-4 BAP parameters.

We discussed and compared the advantages and limitations of each registration step, combining them to achieve robust 3D motion tracking with a limited number of iterations. In particular, region-based registration provides high robustness but less accurate results, while edge-based registration is capable to improve accuracy of the region-based result. We experimentally studied the contribution of each registration step in order to find the best compromise between robustness and accuracy with respect to the number of iterations. The experiments were made on video sequences including body occlusions, motion in depth, fast motions and rotations. The experimental results demonstrate the efficiency of the combined registration process for robust and accurate real-time tracking. Finally, we proposed an experimental analysis to derive an optimal trade-off between the numbers of iterations allocated to each registration step for the best accuracy in real-time. The resulting curve is applicable to a large variety of motion gestures as it is based on the mean residual error over multiple video sequences.

Although our approach can provide robust 3D motion tracking for a large variety of gestures in real-time, it is limited by the ambiguities that are inherent to monocular images. The main problem is the fact that it allows only one solution (3D pose) to be propagated between frames. In monocular images, the problem is ambiguous because multiple solutions (3D pose projections) can match the same image primitives. Propagating an incorrect solution usually leads to motion mistracking. Temporal coherence and biomechanical constraints are not enough to disambiguate such poses, so a more sophisticated tracking approach must be adapted to address the ambiguities caused by the lack of depth information, while still maintaining at the same time, real-time motion tracking. Chapter 4 describes a real-time particle filter approach that does this, considerably improving the accuracy of real-time 3D pose estimation.

Chapter 4

Real-Time Particle Filtering with Heuristics for 3D Motion Capture by Monocular Vision

Introduction

As seen in the previous chapter, 3D motion capture by monocular vision can be achieved iteratively by local optimization (e.g. Downhill Simplex method [START_REF] Nelder | A simplex method for function minimization[END_REF]) under biomechanical constraints. However, the lack of depth information from monocular images makes 3D tracking difficult as forwards or backwards motion in the direction of the camera is difficult to recover.

Unfortunately, estimating only one solution (3D pose) at each frame often fails correctly to track the human pose from monocular video sequences. For instance, in cases where different 3D poses match the same image primitives (Figure 4 3D ambiguities in monoscopic images can be handled more effectively by propagating multiple hypotheses or candidate poses from frame to frame in the video sequence. The difficulty arises in finding, in the high-dimensional and multi-modal pose space, the correct set of hypotheses to be propagated given that the image observations are usually noisy or incomplete. As in many real-world signal processing problems, estimating human motion from image observations can be regarded as a problem of estimating the state of a nonlinear dynamical system over time. Sequential Monte Carlo methods (SMC), also known as particle filtering approaches, provide a flexible and potentially powerful framework to estimate the behavior of such nonlinear systems. Nowadays, particle filtering is well known as a robust approach for human motion tracking by vision, at the cost of heavy computation in the high dimensional pose space.

In this chapter, we propose an enhancement of the classical particle filter algorithm to achieve real-time 3D motion capture by monocular vision. The proposed algorithm allows the observation ambiguities of monocular images to be dealt with under real-time computation constraints. A number of heuristics for the particle filter approach are proposed to improve both the robustness and the accuracy of 3D motion capture using a limited number of Particle filtering methods, also known as Sequential Monte Carlo (SMC) provide a convenient and attractive approach to estimation in complex dynamical systems using Monte Carlo samples ("particles"). They aim to estimate the sequence of hidden parameters based only on the observed data sequence . They represent the posterior densities as clouds of samples and hence can deal with non-Gaussian noise. They are also flexible, parallelizable and easy to adapt to different domains (signal processing, telecommunications, economics, biology, chemistry, etc.). In the following subsections, we describe the fundamental concepts of particle filters and the steps necessary to implement the generic particle filtering approach.

Problem statement (Bayesian filtering)

Consider the problem of determining a sequence of states over time of a dynamical system given some noisy observations . Assuming that the dynamical system can be defined in a state space model by a Markov process, therefore the dynamics of the states can be described with the following equations: This problem, also known as the Bayesian filtering problem, can be solved by computing the probability density function of the current state given the sequence of all the measurements . In order to compute , we can use a recursive Bayesian solution that consists in two steps: prediction and update.

Assuming that the previous posterior is known, the prediction step can be computed as follows:

(4.3)
The update step is computed by the following equation: (4.4) Unfortunately, equations (4.3) and (4.4) cannot be computed in practice for nonlinear and non-Gaussian cases since they require the evaluation of complex high-dimensional integrals, which are impossible to solve analytically. Therefore, a method to approximate the recursive Bayesian solution is required.

Principles of particle filtering

From the late 1980s, the great increase in computational power made possible major advances to address the problem of Bayesian filtering [START_REF] Kitagawa | Non-Gaussian state-space modeling of nonstationary time series. s.l[END_REF], [START_REF] Geweke | Bayesian inference in econometric models using Monte Carlo integration[END_REF], [START_REF] Mueller | Monte Carlo integration in general dynamic models[END_REF]. One solution that has drawn recently attention is the use of Sequential Monte Carlo (SMC) methods or Particle filters. Basically, these methods work on the assumption that the posterior density of a dynamical system can be approximated using a large set of random samples, also named particles , with associated likelihood weights :

(4.5)

In the equation above, each particle represents a state of the dynamical system, and each weight is an associated normalized factor, which likelihood is computed from some measurement observation . The term describes the delta-Dirac mass located in .

Particle filtering involves importance sampling [START_REF] Geweke | Bayesian inference in econometric models using Monte Carlo integration[END_REF] where random samples are generated from a proposal distribution . Each sample is associated with a weight proportional to the value of the current observation density . The true posterior density is approximated with the weighted set of particles at each time step (Figure 4-3) in a sequential importance sampling (SIS) scheme.

Figure 4-3: A weighted set of particles representing the true posterior density. The abscissa axis corresponds to the particle space . The particles are represented as circles which size is the likelihood of [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF].

The degeneracy occurs when only one particle has non zero importance weight. Unfortunately, after few time steps, the particles will degenerate because the unconditional variance of the importance weights increases over time [START_REF] Ristic | Beyond the Kalman Filter. s.l[END_REF]. Consequently, particles fail to represent correctly the posterior density. This can be avoided by propagating the set of particles using a resampling step. The key idea of this step is to eliminate particles with low importance weights and multiply particles having high importance weights. The most popular resampling step was introduced in the bootstrap filter algorithm [START_REF] Gordon | Novel approach to nonlinear/nonGaussian Bayesian state estimation[END_REF]; it consists basically in resampling (with replacement) particles from a particle set according to the importance weights . The likelihood weights of the new set are updated to a uniform value . The new set is propagated to the next time step ( ) representing an improved approximation of the true posterior density .

In the next subsection, we describe the basic particle filtering algorithm based on the principles discussed here. More detailed theoretical concepts and variants of particle filtering can be found in [START_REF] Doucet | Sequential Monte Carlo Methods in Practice[END_REF].

CONDENSATION algorithm

Sequential Monte Carlo methods (SMC) have been applied to a wide range of complex applications since they do not require any assumptions about the probability distributions of the data. The CONDENSATION algorithm (Conditional Density Propagation) [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF], also known as sequential importance resampling, is a commonly used particle filtering algorithm. The sampling iterative strategy is based on the bootstrap filter [START_REF] Gordon | Novel approach to nonlinear/nonGaussian Bayesian state estimation[END_REF]. The CONDENSATION algorithm was originally applied to track the contour of objects moving in a cluttered environment. It is very flexible and can be easily improved. It consists of the following three steps:

 Resampling: resample (with replacement) a new particle set from the weighted set . The probability of selecting each particle is proportional to its weight .

 Prediction: generate from the particle set according to a stochastic diffusion model , where η is a vector of standard Gaussian random variables. In this way, the new set accounts for the uncertainty in the behavior of the tracked object.

 Measurement: evaluate the new particles based on observations . Then, normalize the weighted particle set so that and compute the cumulative probabilities. The resulted weighted particles represent the new posterior density of the system current state. Each time that samples have been obtained, the current state can be estimated by computing the mean state of or by selecting the particle with the highest weight. In the next figure, a diagram representation of the three steps is showed. [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Each circle represents a particle which size correspond to its weight. Particles are propagated in time by three steps: resampling, prediction and measurement.

The three steps of the CONDENSATION algorithm are applied to each time-step. The algorithm is designed to conserve the same number of particles, thus ensuring a constant computation time. Note that each sample-set of the current posterior density is derived from the sample set representation of the previous posterior , which is approximated by . In this way, particles can explore multimodal posterior distributions dealing with nonlinear dynamic behaviors.

One of the properties of CONDENSATION algorithm is its simplicity and generality. The three steps can be easily adapted and modified. Increasing the number of particles N allows to a more accurate representation of the posterior density .

Particle filtering for 3D motion capture

Particle filtering has been widely used in the computer vision community. These approaches usually provide very efficient results for real-time tracking in low-dimensional spaces (e.g. object tracking [START_REF] Yang | Fast multiple object tracking via a hierarchical particle filter[END_REF], contour tracking [START_REF] Li | Visual contour tracking based on particle filters[END_REF]). Unfortunately, particle filter algorithms become inefficient in high-dimensional spaces because the number of particles increases exponentially with the number of dimensions.

The problem for 3D motion capture is the high dimensionality of the configuration space of the 3D human poses (usually 20-60 degrees of freedom) as well as the increasing computational cost involved to evaluate all these particles (candidate poses). MacCormick and [START_REF] Maccormick | Partitioned Sampling, Articulated Objects, and Interface-Quality Hand Tracking[END_REF] proposed an interesting measure of the effective number of particles with respect to the number of dimensions that is given by the following expression:

(4.6)

In the equation above, represents the number of particles required, is the number of dimensions.

is a constant that represents the minimum acceptable survival diagnostic for successful tracking in a configuration space. is another constant representing the survival rate of a given particle set. More detailed explanation about these constants can be found in [START_REF] Maccormick | Partitioned Sampling, Articulated Objects, and Interface-Quality Hand Tracking[END_REF]. From this equation, it is clear that when is large, the number of particles and consequently the computational cost becomes intractable.

In a 3D pose configuration space, the likelihood function is usually multi-modal, illconditioned and highly nonlinear. Observation likelihoods based on visual primitives (e.g. color, edges, textures, etc.) do not provide enough information to find the global maximum of the likelihood function due to ambiguities of monocular images. In these cases, the vicinity of the global maximum is expected to give good pose estimations. In order to avoid mistrackings, the particles must be diffused by the dynamical noise (prediction step), thus producing samples that cover correctly, at each time-step, the principal modes or peaks of the likelihood function. However, particles tend to cluster themselves on a very small area (sample impoverishment) [START_REF] King | How does CONDENSATION behave with a finite number of samples? s[END_REF], mistrackings may occur as different modes can belong to 3D configurations that may be far away from the solutions given by the previous posterior. Moreover, new secondary modes can emerge at each time step, making it difficult to find them if the sampling was not dense enough. Other difficulties include the selfocclusions of body parts, and noisy observations which introduce uncertainty in the 3D pose estimation.

Despite the complexity of the problem of 3D motion capture, different strategies have been proposed to the particle filtering approach in order to face the high-dimensionality and the multi-modality of the pose space. The goal of these strategies is to sample the pose space more effectively by incorporating different elements and assumptions such as motion constraints, local optimization, hierarchy of body parts, analytical inference etc. In the following subsections, some of these strategies will be discussed.

Search space decomposition

This strategy consists in dividing the high dimensional space into several low-dimensional subspaces in order to reduce the number of particles required. Each subspace corresponds to a specific body part or limb that has an appropriate weighting function and isolated dynamics.

Partitioned sampling [START_REF] Maccormick | Partitioned Sampling, Articulated Objects, and Interface-Quality Hand Tracking[END_REF] is one of the first strategies proposed for tracking articulated body models, it is based on the assumption that the configuration space is partitioned as , the dynamics as and having weighting functions . In this way, each dynamic is a Gaussian diffusion acting on the appropriate partition and each is peaked in the same region as the posterior restricted to . Each partitioned configuration has an observation density . In this way, a CONDENSATION algorithm (Figure 4-4) is associated to each partition of the space with independent weighting functions . As a result, the required number of particles is reduced because of the state space decompositions.

Several works (Bernier, et al., 2006), [START_REF] Sigal | Tracking loose-limbed people. s.l[END_REF]) have adopted a partitioned sampling strategy but taking into account the true hierarchy of the human body in order to increase efficiency of the estimation of different body parts. One of the first contributions was proposed in [START_REF] Mitchelson | Simultaneous pose estimation of multiple people using multipleview cues with hierarchical sampling[END_REF], they proposed a hierarchical sampling scheme in which they divided the parameters into two layers: the layer A contained the location and orientation of the torso and the layer B comprises the orientation of left arm, right arm, left leg and right leg. In this way, layer A is first sampled independently and weighted to estimate the location and orientation of the body torso. Then, layer B is sampled using the estimation of layer A in order to refine the estimation of arms and legs.

In addition, the search space can be constrained more accurately by taking into account the proximity between limbs and the temporal coherence. In the works of [START_REF] Sigal | Tracking loose-limbed people. s.l[END_REF] and [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF], the articulated body model is represented as a factor graph with limbs represented by nodes and links corresponding to articulations. The marginal probabilities of the limbs states are obtained using belief propagation. Given a limb µ with a configuration state and image observations , the joint probability of the posterior density can be decomposed as a product of all probabilities , the time interaction factors , and the interaction factor for the set of links between limbs µ and υ: . The joint probability for all the limbs becomes:

(4.7)
The efficiency of partitioning strategies can be affected by self-occlusions of body parts that make independent limb location very difficult and consequently, weighting function inaccurate (Bernier, et al., 2006).

Annealed sampling

A modified particle filter algorithm, termed annealed particle filtering, was proposed by Deutscher et al. [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF]. It uses a principle based on a variant of simulated annealing [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] to gradually migrate the particles toward the global maxima of the posterior density. In this approach, a series of layers is employed, in each layer a modified weighting function is used to sharpen gradually the likelihood approximation. The weighting function is modified by the following equation:

(4.8)
for , the first layer is initialized with the minimum value and progressively increases until in the last layer. In this way, the function is designed to cover the overall modes of the search space while is highly sharpened, emphasizing likelihood observations. The set S of N weighted particles after each layer of an annealing run is represented by: [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF].

Annealed particle filtering (APF) achieves a reduction of the number of particles by over a factor of 10 compared to CONDENSATION algorithm. The main advantage of APF is its generality since it avoids strong assumptions on the search space or motion constraints. Annealed sampling has been the basis of various robust human body trackers in the literature [START_REF] Fontmarty | Data fusion within a modified annealed particle filter dedicated to human motion capture[END_REF], [START_REF] Raskin | Using Gaussian process annealing particle filter for 3D human tracking[END_REF].

A drawback of annealed sampling is the difficulty of tuning correctly the rate of annealing according to the number of layers. If the rate of annealing is too high the influence of local maxima will distort the estimation of the pose configuration. If the rate is too low, the estimation will not be determined with enough resolution. A method for tuning with respect to the survival rate after each annealing run is proposed in [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF].

Stochastic sampling with local optimization

Another strategy consists in guiding the particles toward the multiple modes of the posterior density by refining each particle using some local optimization method. The basic idea is to obtain the principal modes of the likelihood and thus, a more accurate representation of the posterior with less number of samples. One of the first contributions was proposed by [START_REF] Cham | Multiple hypothesis approach to figure tracking[END_REF]. They represented the probability density as a set of N modes modeling the neighborhood surrounding each mode with a Gaussian and a covariance. Given a set of N modes where the mode has a state , an estimated covariance and a probability . A configuration in the state-space of human poses is determined by the Gaussian component providing the largest contribution: (4.10) where is a normalization constant. At each time step , new hypotheses are sampled (with random Gaussian noise) from the posterior density of N modes . Then, each hypothesis is refined through differential local search in order to obtain the new modes of the current likelihood . In this way, the Gaussian covariances are obtained from the fitted optima and the search region is controlled by adding a large dynamical noise. [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] adopted a similar idea with a more sophisticated approach to deal with the uncertainties of unobservable 3D motion; the posterior distribution is represented as sets of separate modes with probability , mean and covariance . They separated each mode by running local continuous optimization to convergence. The modes are propagated at each time t and new samples are generated from each mode . Then, new samples are refined with local optimization to obtain for each new mode. Redundant samples converging to the same minimum are pruned. For each new mode found, the covariance is eigen-decomposed and inflated along highly uncertain directions that correspond to the unobservable motion in depth. In this way, the search space is more adapted to the cost function imperfections and 3D nonlinearities caused by monocular ambiguities.

The main advantage of these strategies is the fact that they allow to address the problem of multimodality directly, while the use of modes eliminates the need for a large number of particles required to sample densely the high dimensional space. In addition, inflating the covariances of the modes allows defining a well-controlled sampling. However, the computational cost required in the sample refinement process to find the modes can be prohibitive for real-time computation since local optimization is necessary for each sample (particle).

Analytical inference

Particle filter can be combined with analytical inference to reduce the degree of randomness of Monte-Carlo simulations. The main idea is to estimate analytically (e.g. using inverse kinematics) new vector parameters or new particles using some partial image observations and kinematic model assumptions. The analytical inference allows improving the state estimation using a smaller number of particles for high-dimensional search.

Several authors have adopted analytic strategies to compute new particles from image observations. Lee et al. [START_REF] Lee | Particle Filter with Analytical Inference for Human Body Tracking[END_REF] proposed a framework that consists in decomposing the pose configuration state in two parts . The state depends on the observation , while depends partially on the observation and the state . Assuming that can be computed analytically by a function , then the estimation of the posterior density becomes: (4.11) From the equation above, we can note that the simulation of is not required since can be computed analytically from . In this way, the Monte-Carlo sampling is only applied to the sub vector , reducing the number of particles required to estimate the full configuration state . Sminchisescu & Triggs. (2003) used kinematic principles to compute new 3D configurations that give the same projection in the image plane. The idea is to generate new particles to deal with unobservable forward / backward ambiguities in monocular images. In their probabilistic approach, a set of samples is generated from the posterior density , then they select a kinematic sub chain (e.g. left arm) based on local uncertainties of the posterior. For each sample , an interpretation tree is created, which contains the alternative ambiguous configurations corresponding to the sub chain . The list of angles of each alternative configuration is computed analytically and a new set of samples for each sub chain is added to the samples previously generated from the posterior. In this way, the new set of samples computed analytically allows to investigate efficiently alternative local minima in the posterior density.

Analytic inference is a very efficient technique to improve the search in high-dimensional spaces since it is possible to locate good local minima deterministically. In addition, the computational cost to compute new 3D poses with kinematic inverse is relatively low compared to sampling densely the posterior using Monte-Carlo simulation. However, analytic inference requires reliable image features and accurate body part detectors, which is not always possible in real video sequences.

Deterministic sampling

This strategy consists in exploring deterministically the posterior density by reconfiguring the particles search space in an optimal way. The aim is to control the search by explicitly defining the parameter space to sample, thus reducing the randomness of Monte-Carlo simulation. [START_REF] Saboune | Markerless human motion capture for Gait analysis[END_REF] proposed a prediction step in a particle filter framework that consists in combining stochastic with deterministic search. Sampling consists in decomposing the particle state in 2 vectors. The first vector L contains the n most interesting (difficult to track) dimensions while the second R cover the other dimensions. From vector L, a grid of sample poses I is generated by sampling deterministically the states space at regular intervals in the neighborhood of L. In this way, the vector L is replaced by a multidimensional grid of sample I vectors explicitly covering all the possible values of the n dimensions of L. As a result, each particle will be updated and replaced by I neighbor particles generated deterministically (Figure 456). The vector R is then updated by adding some dynamical noise. The number of particles increases by the number of sample poses I. All particles generated are evaluated according to observations and the heaviest particles are propagated. This simple technique allows creating a more reliable search space than using only stochastic sampling of the original CONDENSATION algorithm [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. However increasing in the number of particles results in a computational cost that is too heavy for realtime.

Our real-time particle filtering approach for 3D motion capture by monocular vision

In this section, we describe our particle filter approach for 3D motion capture by monocular vision in real-time. The main idea is heuristically guiding the particles (3D poses) toward local minimums of the posterior to achieve a more robust tracking with relatively small number particles. Basically, we implemented some modifications to the original CONDENSATION approach [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF] in order to search more efficiently in the high-dimensional pose space by combining several search strategies for 3D motion capture (section 4.3).

In our particle filter implementation, a robust likelihood function is built using our regionbased and edge-based registrations to evaluate particles efficiently combining different visual cues. A new state space based in end-effector position is proposed to deal with uncertain motion in depth.

The heuristics proposed allows dealing with the problem of ambiguities in monocular images while facing real-time computation. First, we deterministically resample the probability distribution for a more efficient selection of particles. Second, we use a deterministic particle prediction based on local optimization. Third, we search the high-dimensional space of 3D poses by generating new hypotheses (or particles) with equivalent 2D projection by kinematic flipping (Sminchisescu, et al., 2003). Finally, real-time computation with a high number of particles is achieved with a parallel implementation on GPU of the particle evaluation. This section is structured as follows. First, we describe the basic details of our particle filter implementation for 3D motion capture. Then, we introduce the proposed heuristics or modifications to the standard particle filter approach (CONDENSATION). Next, we address particle filter acceleration on GPU and finally, the steps of our real-time particle filter with heuristics will be described.

Basic details of our particle filter

We describe the basic details of our particle filter approach for 3D motion capture, reusing some concepts already described in previous chapter. In other words, we turn our proposed registration process (chapter 3) into a particle-filtering framework, so multiple hypotheses are kept from frame to frame. This section describes the basic details of implementing a particle filter (CONDENSATION) (Figure 4-4) for 3D motion capture. First, a particle state is defined, then we introduce the likelihood function used to evaluate the particles, finally we describe how particles are randomly diffused in the high dimensional space.

Definition of a particle state

A particle or sample at time t is a vector of 20 joint angle parameters that corresponds to the 20 degrees of freedom of our 3D upper-body model. In this way, each particle describes a candidate 3D pose of our model (Figure 4567).

Evaluation of particles

Particles are evaluated according to a matching measure between the features extracted from the captured image and from the 3D model. In the previous chapter, our experimental analysis showed that region-based registration provides robust tracking while edge-based registration provides more accurate pose estimation. Thus the weight of each particle is defined by combining region-based and edge-based measurements using the following likelihood function. (4.12) where is the non-overlapping ratio measure as described in equation ( 2.5), is the mean edge distance described in equation (3.13). The ranges and are the standard deviations that express the average variability of the non-overlapping ratio and the mean edge distance respectively on a full video sequence. The standard deviations ( and ) were obtained experimentally from several video sequences with various gestures. The observation measurements and are assumed to be mutually independent since the observation of the one does not affect the other. Thus particles best matched for both primitives (region and edges) will have the highest probability to survive. Figure 4-8: Particle evaluation according to regions and edges image observations. F(q) is the non-overlapping ratio and D C is the mean edge distance matching measure. Particles that are matched to both primitives will have highest probability weights.

Random diffusion of particles

Particles are scattered randomly over the 20-dimensional space by applying, to each particle , a scaled random Gaussian noise using the following equation:

(4.13)
where is the original particle state and is the new particle state after random diffusion. is a 20-dimensional vector of Gaussian random variables with variance according to the maximum variation from frame to frame of each joint angle . is a scale factor that controls the amount of diffusion applied to each particle . Thus a large scale factor allows sampling broadly in the state space while a small scale factor provides a narrow sampling. and are biomechanical constraints (Table 2-1) used to invalidate particles or 3D poses that are not kinematically feasible (biomechanical constraints described in section 2.4.1).

Figure 4-9: Random diffusion of particles (circles) controlled by a scale factor. A relatively small scale factor (left side) allows the particles to cover small regions of the posterior density (curve), while a relatively large scale factor (right side) allows a broader sampling in the posterior density.

Heuristics proposed and experimental analysis

In this section we describe the heuristics proposed for the particle filtering (CONDENSATION) (section 4.2.3). These heuristics aim at achieving robust and accurate tracking in monocular images while limiting computation for real-time. The main idea is to improve the efficiency of the search in the high dimensional space by propagating the most useful particles between frames while avoiding wasting particles. Our heuristics are based on prior assumptions and deterministic methods that allow guiding particles toward highly probable solutions (local minimums) of the posterior density.

In addition, the contribution of each heuristic proposed is analyzed experimentally using the synthesized video sequences from GRETA database (Figure 3-20 to that was introduced in the previous chapter. We recall that this set of gestures exhibit various types of motion in the depth direction. We track each video sequence by separately integrating each heuristic proposed into the particle filter algorithm (CONDENSATION) in order to analyze the specific contribution of each heuristic to the motion capture performance in terms of robustness and accuracy.

Our goal is to improve the accuracy of the 3D pose estimation as well as the robustness of tracking (less failures) using a small number of particles. For that, we analyzed the tracking performance for the set of video sequence while varying the number of particles (from 100 to 1000).For all the videos, we compute the mean residual 3D error and the number of failures (mistrackings).

Accuracy is estimated by computing the average residual 3D error (in millimeters) between some articulation joints (wrist and elbows) of the pose estimated and the joints from the ground truth pose (equation 3.16 from section 3.6.2.1). Robustness is evaluated as the number of failures with respect to both the non-overlapping ratio and mean edge distances. Just like in the previous chapter, we consider as failures or mistrackings the registered poses with residual values above a defined threshold (or a "peak") for each evaluation function. Those "peaks" represent an erroneous 2D matching which visually appears as a tracking failure (Figure 3-13 and Figure 34567891011121314).

In the following subsections, we describe and analyze experimentally the heuristics proposed to the particle filter algorithm in order to achieve a more efficient search in the highdimensional pose space with relative small number of particles.

Resampling (Weight-based heuristic)

In the standard algorithm (CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]) the probability of selecting a particle is proportional to its weight . This step would allow low-weight particles to be selected, although at a low probability. In order to focus computation on high weight particle rather than low probability particles, we heuristically enforce each parent particles to give birth to some number of children (resampled) particles proportional to their weights, based on a weight-based resampling heuristic. Namely, each parent gives rise to a number of children particles according to the following equation:

(4.14)
where is the preset total number of particles, is the weight of each particle. This way of resampling ensures that low weight particles have little or no children, while particles with heavy weight give birth to a family of particles. The weights of the new set of particles are updated to a uniform value as in the standard algorithm.

In addition, one child of the highest weight parent particle is kept unchanged, i.e. it is not randomly diffused at the prediction step; this aims at avoiding that children particles lose tracking because of loose sampling in the high dimensional space (sample depletion). A child of the highest weight parent particle will not be diffused randomly in the prediction step in order to avoid losing the currently best estimation in case of sample depletion.

Figure 4-11 shows how this heuristic enhances accuracy of 3D pose estimation in the particle filter approach. From the experimental results we note that our weight-based deterministic resampling (dashed gray line) reduces the 3D error for some video sequences (figures 4-11a, 4-11b and 4-11d ), but it exhibits a less stable residual 3D error than the CONDENSATION algorithm (black line). This means that removing random variability in the resampling step may reduces the efficiency of the particle filtering because low-weight particles that are discarded could otherwise turn into good solutions at some future time step. However, in Figure 4-12, we observe that reducing randomness with weight-based deterministic resampling can improve robustness (dashed gray line) even for motion in the depth direction (figures 4-12d). Thus, this heuristic keeps particles closer to local minimums, at the price of narrowing the search, which may result in lower accuracy of the 3D pose. Therefore, while the weight-based deterministic resampling may improve or degrade the 3D accuracy depending on the type of gesture, it generally enhances robustness.

Prediction

The heuristics described in this section are based on search strategies used in particle filtering for 3D motion capture (section 4.3). We propose three deterministic methods to generate highly probable hypotheses. In the first method, new particles are diffused according to a hierarchical partitioned motion-based sampling. In the second method, particles are heuristically guided towards optimums with limited local optimization. In the third method, we use kinematic jumps (Sminchisescu, et al., 2003) to analytically generate 3D poses with the same projected joint centers, so they are in alternative local minimums. These methods have low computational cost that is compatible with real-time.

state space in order to take into account the kinematic hierarchy between body limbs (Figure 2345). In the case where no motion has been detected

, the set of parameters will contain the same exact value as .

In Figure 4-13, we observe that hierarchical partitioned motion-based (HPM) sampling (dashed gray line) achieves a significant accuracy improvement for the video sequences that contain most fronto-parallel motions (figures 4-13a and 4-13b). However in case of motion in depth (figures 4-13c and 4-13d), state space decomposition fails to guide the particles and thus to accurately register the body poses. In the next figure, we observe that HPM sampling (dashed gray line) reduced significantly the number of mistrackings for almost all video sequences. As seen in the presented results, HPM sampling performs best on video sequences that contain most fronto-parallel motions (figure 4-14a). We also can observe that motion in depth does not decrease the robustness of the proposed heuristic (figure 4-14d).

Prediction with local optimization

In the prediction step of the CONDENSATION algorithm (section 4.2.3), stochastic random diffusion does not guide the particles toward the peaks of the posterior. We use local optimization in the particle filter prediction step to guide groups of particles toward local minimums (peaks of the posterior) of the matching cost (non-overlapping ratio from equation 3.15) in the state space. In the -dimensional pose space (20 parameters in our case), we consider groups of or more children particles issued from a same parent at the resampling step. We select of them and construct a simplex that is iteratively optimized following the downhill simplex algorithm [START_REF] Nelder | A simplex method for function minimization[END_REF].

Figure 4-15 shows how the large groups of children particles are used to create a N D -dimensional simplex around a peak (local minimum) of the posterior density. This simplex can be regarded as a deterministic sampling strategy since we are explicitly defining N D +1 neighbor particles (simplex vertices) in the state space. After the initial simplex is created, the remaining children particles are evaluated sequentially and optimized iteratively by the downhill simplex algorithm toward some minimum. Therefore, the number of iterations is limited to . In this case, we take advantage of the optimal curve found in section 3.6.2.2, in order to achieve an optimal balance between regionbased and edge-based registration of the limited number of iterations .

In our method, small groups of children particles (

) are not sufficiently numerous to initialize a simplex, however they still have a chance to explore the high-dimensional space using random sampling as in CONDENSATION algorithm (section 4.2.3). 4-17, this heuristic provides very stable and robust tracking (lower number of failures) for all the video sequences considered. This means that local optimization keeps particles near the minimums of the 2D residual error, so 2D mistrackings are kept low. However, as seen in Figure 4-16, accuracy of the 3D pose is degraded (higher residual 3D errors) mainly for the gestures with relative motion in depth (figures 4-16b, 4-16c and 4-16d). The reason is that local optimization may refrain particles in incorrect minimums of the 2D errors from escaping to other ambiguous minimums since the same 2D observation can have more than one 3D pose solution in monocular images. In this case, it is important to develop algorithms that allow particles jumping rapidly to ambiguous minimums. In the next subsection, this problem will be addressed.

Kinematic-flipping based sampling

Multiple 3D poses may give the same ambiguous 2D image projection by forward/backward flipping of articulation joints (Figure 4-1). Unfortunately, in monocular images, we do not have information to disambiguate such poses. Selecting a wrong pose in the registration process leads to mistrackings (Figure 4-2). We have implemented the approach proposed in (Sminchisescu, et al., 2003) to compute analytically new alternative poses that match the current image projection. This approach allows finding rapidly new minimums without searching exhaustively in the high-dimensional space. The following steps are necessary to compute analytically new kinematic-flipping samples. a) Building kinematic tree: We build kinematic trees for the kinematic sub-chains of the limb to be tracked (upper-limb in our case). An interpretation tree is generated by traversing each segment from the limb attachment to its end (e.g. from the shoulder joint to the wrist). For each upper-limb segment (arm and forearm), we construct an imaginary 3D sphere centered in the parent joint position (e.g. shoulder joint) with radius equal to the length of the segment limb. The ray going from the camera to the joint projection in the image plane intersects the 3D sphere at 2 points so giving rise to one alternative 3D joint position with same image projection (Figure 4-18). ) that gives the same projection (Ep). c) Building kinematic tree to find alternative joint configurations (K", K"", K""") that corresponds to the same set of projected joints in the 2D image plane.

b) Solving joint angles: Once the kinematic tree has been constructed, we calculate the joint angles that rotate each arm segment in order to reach each alternative 3D joint position computed in the last step. The arm kinematic sub-chains (Figure 4-18a) consists in the 3 DOF for the shoulder ( ) and 1 DOF for the elbow ( ). The joint angles are calculated analytically by representing each segment rotation by an axis-angle (or rotation vector) through the following equations: where and are the 3D position of the elbow and shoulder joint in the initial 3D model pose.

is the alternative 3D position of the elbow calculated in the previous step. is a vector describing the direction from to and is the direction from to . Thus we have an axis-angle representation by computing the angle between these two vectors and the unit perpendicular vector resulting from the cross product. From this representation we compute the Euler angles of the shoulder joint (through a rotation matrix) using the method proposed in [START_REF] Shoemake | Euler Angle Conversion. s.l[END_REF]. Now, we calculate the joint angle for the elbow ( ) with the following equation: (4.25) In equation (4.25), is the length of upper-arm segment, is the length of lowerarm segment and represents the distance from the shoulder joint to the alternative wrist joint

. After obtaining , it is necessary to adjust the shoulder rotation in order to reach . This is done by the following equations: where and are vectors projected in the plane . is the direction vector from to and is the direction vector from to . Through equation (4.28), we have the correct shoulder twist rotation to reach the wrist alternative 3D position .

c) Kinematic-flipping. We assign each arm kinematic sub-chain to a new different pose. Thus we generate 15 new hypotheses (particles ) for each set of projected joints. However, only some particles are acceptable due to the human body biomechanical constraints that are implemented . To analyze experimentally the contribution to performance of kinematic-flipping based sampling, we compute new alternative 3D poses for the best samples after the measurement step of CONDENSATION algorithm (Figure 4-4). Then the lowest weight particles are replaced by the new samples computed analytically. In the next figures (Figure 4-20 and Figure 4-21), we appreciate the accuracy and robustness contribution of kinematic-flipping sampling (dashed gray line) to the particle filter algorithm. As seen in the results shown above (Figure 4-20), kinematic-flipping (dashed gray line) does not significantly improve accuracy in the particle filter algorithm (black line). This is because in our experiments, we are replacing lowest-weight particles by alternative kinematic-flipping samples; consequently particles are less scattered in the high-dimensional space. In fact, kinematic-flipping contributes to obtain a more stable 3D tracking. In Figure 4-21, we can observe how the number of failures decreases smoothly as the number of particles increases. This means that kinematic-flipping avoids mistrackings more efficiently since particles can reach rapidly alternative local minimums that belong to ambiguous 3D pose configurations.

In the next figure, we can see how kinematic-flipping based sampling allows tracking to recover rapidly from a "wrong" 3D pose configuration (local minimum) to a right 3D pose configuration that gives approximately the same 2D projection. In this case, the right 3D pose configuration is conserved since its 2D projection matches better to the 2D image of the video sequence. Thus number of tracking failures (mistrackings) due to monocular ambiguities is reduced.

Tracking motion in depth using End-Effectors space

From those results, we note that, although the previous heuristics significantly reduce the number of failures (mistrackings), 3D errors do not decrease for some video sequences. Improving 3D accuracy from monocular video sequences is a challenge because of the lack of depth information.

In this section, we propose to describe body poses using end-effector positions, rather than joint angles, as an attempt to better model uncertainty of motion in the depth direction [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF]. Considering upper-body kinematics, our end-effectors parameters are the coordinates of the wrists in a camera-centered system.

Estimating 3D human pose in the end-effector space was investigated by [START_REF] Hauberg | Three Dimensional Monocular Human Motion Analysis in End-Effector Space[END_REF]. They argued that end-effectors makes real-time tracking of humans feasible at the cost of loss of accuracy due to the limitations of the inverse kinematic solvers, which may find 3D configurations that does not necessarily correspond to image observations. In our approach, we use end-effectors to gain explicit control over depth direction (z-axis). Our solution consists in replacing, for each kinematic arm sub-chains, the 3 DOF for the shoulder (

) and 1 DOF for the elbow ( ) by the 3D coordinates of the wrist position . Thus, instead of estimating the set of joint angles of a kinematic arm sub-chain , we estimate directly a desired end-effector wrist position according to image observations. In order to control the high-dimensional search, we define, for each wrist coordinate , a maximum variance according to the range of motion from frame to frame along each axis direction (-x. +x. -y. +y, -z, +z). In this way, the 3D pose space is explored by diffusing randomly new end-effector state particles around the sampled wrist positions. Particles are enforced to diffuse along uncertain depth direction by inflating the maximum variance along that direction (Figure 4-23). In our experiments, we use a maximum variance of 70 mm for x-direction and y-direction, and an inflated variance of 150 mm along zdirection. We also add end-effector constraints in order to invalidate particle end-effector states whose distance between shoulder and wrist is larger than the length of the full kinematic arm sub-chain. After estimating new end-effectors for each particle state, we use analytic inverse kinematics [START_REF] Tolani | Real-time inverse kinematics techniques for anthropomorphic limbs[END_REF] to compute the joint angles of the arm kinematic sub-chains . (4.29) In order to simplify inverse kinematics, we define the elbow position as a function of a swivel angle . In this case, as the swivel angle varies, the elbow traces an arc of a circle projected on a plane whose normal is parallel to the shoulder to wrist axis [START_REF] Tolani | Real-time inverse kinematics techniques for anthropomorphic limbs[END_REF]. The swivel angle is then considered as a new state parameter in order to define the elbow position of the arm sub-chain according to image observations.

GPU acceleration

Modern consumer personal computers contain powerful graphics processing units (GPUs) designed to perform operations in parallel on very large amounts of data. GPUs were originally meant for rendering graphics and they have now become programmable for general purpose computing.

In order to achieve real-time performance in particle filtering, some works have taken advantage of the growing computational power of GPUs. First, we give a short review on recent works that accelerate particle filtering with GPUs and then we propose a GPU implementation for particle filter.

Previous works on GPU particle filtering approaches

Several works have adopted strategies to benefit from the computation power of GPUs. However a major issue is that the algorithm is to be restructured in order to suit the GPU parallel architecture. Hendeby et al. [START_REF] Hendeby | A graphics processing unit implementation of the particle filter[END_REF] proposed the first complete parallel particle filter on a GPU. Every step of the algorithm (measurement, resample and time update) is implemented on GPU fragment shaders outperforming the computation speed of a CPU implementation when number of particles is large (above 103 particles). Lenz et al. [START_REF] Lenz | A gpu-accelerated particle filter with pixel-level likelihood[END_REF] proposed a GPU-accelerated particle filter algorithm to track skin-colored objects in real-time. They implemented only the high computation steps (segmentation, hypotheses computation and likelihood evaluation) on graphics hardware, through OpenGL shader language, while minimizing the data transfer between CPU and GPU. [START_REF] Montemayor | Bandwidthimproved gpu particle filter for visual tracking[END_REF] alleviated the computational cost of a 2D object tracking particle filter system by parallelizing the weight computation step. They exploited GPU higher memory bandwidth texture by creating a large square texture composed of a collection of small textured quads. Each quad contained a sub-image of a possible state of a system (particle) and is compared to the object model texture in parallel with the use of a fragment program. [START_REF] Lozano | Real-time visual tracker by stream processing[END_REF] also parallelized the weight computation step in particle filtering for face tracking; they took advantage of the CUDA multiprocessor architecture to achieve the whole weighting operation in a single kernel. The kernel is executed in M blocks, each with N threads. Each thread from each block computes the matching error of a particle and place the result in a different position of the blocks shared memory. Threads are synchronized and the particle weight is placed in global device memory.

Implementing our particle filtering on GPU

In our GPU implementation, we parallelize particle evaluation which is the main computational bottleneck in our algorithm. Particles evaluation can be implemented efficiently in a batch using the massively parallel architecture of GPUs. The evaluation of candidate poses (particles) involves projecting the 3D model on the image plane (Figure 4-8), which can be done efficiently using OpenGL flat rendering onto a Pixel Buffer Object (PBO). Using OpenGL again, the segmented input image is also blended into other bit-planes of this buffer. Then we derive the non-overlapping ratio (equation 2.5) from the histogram of the image thus formed, as described in section 2.4.4.3.

While efficient histogram calculation on GPU was a challenge with the earlier GPU architectures [START_REF] Scheuermann | Efficient histogram generation using scattering on GPUs[END_REF], current GPUs now offer two useful features that make it easier. Scatter allows a computation thread to write to any location in the output array, in parallel to the other threads. Atomic writes use locks to control the access while writing it [START_REF] Okun | Atomic writes for data integrity and consistency in shared storage devices for clusters[END_REF]. Furthermore, the recent OpenCL API can leverage the power of GPUs and multi-core CPUs and has complete access to the rendered pixel buffer (OpenCL, 2010).

GPUs are massively parallel devices that are the more efficient when the number of threads invoked is huge, so a single particle evaluation cannot take advantage of the GPU parallel architectures. Therefore, we concatenated all the image buffers formed by adding the rendered buffer and the segmented buffer to calculate the corresponding histograms in parallel. Our implementation involves two levels of parallelism, the one on the images associated with the particles, the other on the pixels of each of these images. The speed up achieved by using an Nvidia GPU of the Tesla generation is presented in Table 4-1 5 .

Number of particles

Implementing real-time particle filtering with heuristics

In this section, we describe how all the heuristics and strategies proposed in previous section (section 4.4.2) are integrated into our particle-filtering algorithm. In order to make the best from them all, to improve robustness and accuracy of the 3D tracking, each heuristic must cover the limitations of the others. For example, HPM sampling with end-effector space improves 3D accuracy while local optimization and kinematic-flipping reduce the number of failures and stabilize the 3D tracking. In this way, samples will be guided effectively toward several modes or peaks of the likelihood function even if samples are not dense.

Indeed, combining our heuristics into a particle filter algorithm is quite straightforward. First, groups of children particles are generated using weight-based resampling heuristics. Large group of children particles are guided using HPM sampling with local optimization. Small groups are randomly diffused with HPM sampling. All particles are guided using endeffectors space to improve accuracy in the depth direction. Then, kinematic-flipping is applied for the highest weight particles of each group in order to reach alternative "good" local minimums that possibly were missed by the weight-based resampling heuristic. Finally, evaluation of particles is accelerated on GPU. A new set of particles is propagated to the next time step. The steps of our particle filter algorithm proposed are described in the following.

Input: The set of particles (candidate poses) that approximates the previous posterior . 3) Measurement. Evaluate all particles according to color regions and edges image observations (section 4.4.1.2). Matching between regions is parallelized on GPU (subsection 4.4.3.2). Then assign the weights to the set of particles.

Particles are ordered by weight and lowest weight particles are discarded, where is the number of valid kinematic-flipping samples. Finally, normalize weights .

Output:

The set of particles represents the new posterior density .

The 3D pose is estimated by selecting the particle with the highest weight.

A diagram of our real-time particle filtering with heuristics algorithm is shown hereafter.

Figure 4-28: The steps of our real-time particle filtering with heuristics algorithm. Particles are guided toward the peaks of the posterior by combining the heuristics proposed. Evaluation of particles is parallelized on GPU according to color and edges observations.

In our particle filter algorithm, particles optimized with iterative local optimization must be evaluated sequentially at each optimization iteration. Thus, only particles obtained by random diffusion and kinematic flipping are grouped in batches and evaluated in parallel on GPU.. Although this increases the number of particles to be evaluated, little samples are generated because we apply kinematic-flipping only to the best particle of each group generated . After evaluating all particles, only the best N particles will be propagated to the next time step. In the next two figures, we present the results achieved by our real-time particle filter algorithm that combines all heuristic proposed. Figure 4-29 shows that the particle filter algorithm proposed (gray line) achieves significantly, improves 3D accuracy when compared to standard CONDENSATION algorithm for all video sequences, including those with motion in depth and partial occlusions (figure 4-30c and figure 4-30d). This means that the proposed algorithm is able to search more efficiently in the 3D pose space even if the sampling is not dense. We also appreciate that 3D accuracy error is similar for all video sequences, which means that estimation accuracy is not significantly affected by ambiguities from motion in depth in monocular images.

Based on these experimental results, a 3D accuracy residual error between 80 and 120 mm was achieved by our real-time particle filter with heuristics; these results outperform significantly the local optimization method previously described in chapter 3, as well as the results by [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF], where accuracy residual errors varies between 200 and 300 mm. Moreover, our accuracy results obtained in monocular sequences are similar to state-of-the-art stereovision approaches [START_REF] Bernier | Fast nonparametric belief propagation for real-time stereo articulated body tracking. s.l[END_REF] and [START_REF] Fontmarty | Vision et filtrage particulaire pour le suivi tridimensionnel de mouvements humains: applications à la robotique[END_REF] for realtime markerless 3D human motion capture, here authors reported accuracy residual errors that varies from 60 to 100 mm for less that 1000 particles. Figure 4-30 shows that our real-time particle filter algorithm (gray line) also significantly improves the robustness and stability of 3D tracking. In those results, no mistrackings were encountered when using more than 200 particles for all video sequences. Thus particles are guided more effectively toward the "peaks" of the posterior avoiding "bad" solutions and consequently, mistrackings. The Figure 4-31 shows how our proposed particle filtering method is able to track more efficiently the motion in depth that local optimization fails to track correctly in Figure 4-2.

Performance experiments on real video sequences

In this section we evaluate the tracking performance of the proposed particle filter algorithm in real video sequences with real-time limited computation. Namely, we measure the gain of robustness achieved by our proposed algorithm with respect to the standard CONDENSATION approach [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF] under real-world sequences. In addition, we include qualitatively results of our particle filter algorithm by animating a 3D avatar in realtime.

The selected video sequences involve a large variety of gestures including motion in the depth direction, fast motions, partial self-body occlusions, full-body rotations and translations. For each video sequence, we analyze experimentally the number of mistracked frames with varying number of particles limited to real-time computation. As previously, we consider as mistracked those frames with residual values above a defined threshold for both evaluation function (non-overlapping ratio and mean edge distance).

Conclusions

We have presented a real-time particle filter algorithm for 3D human motion capture by monocular vision. Our proposed algorithm allows dealing with depth ambiguities in monocular images using computation real-time.

Our method consists in a Particle Filter approach where particles (3D poses) are heuristically guided toward highly probable solutions (local minimums) of the posterior density. First, particles to be propagated in time are selected based on a weight-based deterministic resampling. Particles are efficiently diffused using a hierarchical partitioned sampling scheme with a fast local optimization algorithm. 3D ambiguities in monocular images are handled with kinematic flipping by adding particles later discriminated when tracking. Evaluation of particles is made with a function likelihood that consists in a region and edge matching between the model projection and captured image. In order to achieve real-time computation, evaluation of particles is accelerated by parallel GPU computing. In addition, end-effector pose parameterization is proposed to better cope with uncertain motion in depth. Our experiments on different video sequences showed that search in high-dimensional space was improved achieving a higher robustness and accuracy in monocular 3D motion tracking with relatively small number of particles.

We have proven that robustness and accuracy improvement for real-time monocular 3D motion capture can be achieved by combining different low-cost search strategies and heuristics into the particle filter framework. Moreover, our experimental analysis showed that problem of ambiguities from monocular images can be overcome by enforcing particles to search toward uncertain data observations. However, if sampling is not dense enough because of real-time limitations, some low-cost optimization method and deterministic heuristics must be implemented in order to guide particles rapidly toward high probable solutions. Finally, computational power of future graphic cards will allow us to increase the number of particles and thus, achieving higher robustness and accuracy in our proposed approach.

depth direction. This limitation can be addressed by propagating, at each time step, multiple hypotheses or particles (3D poses) using a particle filtering approach. Unfortunately particle filter approaches become very inefficient for 3D motion capture as the number of particles (3D poses) increases exponentially with the number of dimensions.

We have therefore developed a more sophisticated particle filter algorithm to reduce the number of particles required for monocular 3D motion capture. It integrates a number of heuristics and search strategies into the CONDENSATION approach to guide particles toward highly probable solutions. First, children particles are selected and grouped according to their parents" weights using a weight-based resampling heuristic. Then, large groups of particles are guided toward maximums of the posterior density using local optimization while small group of particles are diffused randomly in the pose space. Ambiguities from monocular images are handled by computing new samples by kinematic flipping. A hierarchical partitioned sampling is used to diffuse particles more efficiently based on motion observations. 3D poses are described using end-effector position to better model uncertainty in depth direction. Finally, evaluation of particles is accelerated by a parallelized GPU implementation.

Our real-time particle filter algorithm that combines all the previous heuristics did significantly improved the tracking robustness and accuracy using as little as 200 particles in 20 degrees of freedom state space. Particularly, we have demonstrated that depth ambiguities from monocular images can be handled in real-time by heuristically guiding particles toward several local minima while enforcing particles to search along uncertain depth direction.

Quantitative and qualitative results on real video sequences showed a significant improvement when tracking difficult gestures including motions in depth, self-occlusions, whole-body translations and rotations. Only motions with whole-body rotations are reported lower tracking improvement since turning direction cannot be detected from the image features we used so far.

Future perspectives

Future research will focus on incorporating more image features into particle filtering in order to improve 3D pose estimation. For example, motion features (e.g. optical flow) can be used to disambiguate motions with whole-body rotations by recovering the displacement direction of apparent motion of pixels in the human silhouette. Furthermore, body part detectors can be implemented to guide particles more efficiently in the high-dimensional space and also recovering easily from tracking failures.

Another research direction aims at reducing the high-dimensionality of the 3D pose space into a low-dimensional latent space. A very straightforward approach would be to combine Gaussian Process Dynamical Models (GPDM) with our real-time particle filtering with heuristics in order to guide efficiently particles in the latent space reducing even more the number of particles required.

In this work we have limited ourselves to estimate 3D human motion from monocular images. An interesting contribution would incorporate depth information from a time-of-flight (TOF) camera or Kinect sensor (Kinect, 2010) in order to increase the effectiveness of our proposed algorithms.

Finally, some other future applications could be proposed to our motion capture system, e.g. a gesture-based human-computer interaction for networked virtual environments, home video surveillance systems for fragile elder people, human-robot interaction, multimodal interfaces, etc.

Résumé de la thèse en français Chapitre 1 : Introduction

Cette thèse vise à améliorer les interactions dans les environnements virtuels collaboratifs à partir de la restitution des gestes de l"utilisateur directement dans un avatar 3D en temps réel [START_REF] Horain | Virtually enhancing the perception of user actions[END_REF]. Nous nous intéressons à l"acquisition 3D des gestes humains par la vision monoscopique en temps réel sans marqueurs. Un prototype antérieur [START_REF] Horain | 3D Model Based Gesture Acquisition Using a Single Camera[END_REF], [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF] procède en recalant un modèle 3D articulé de la moitie supérieur du corps humain sur des séquences vidéo. Cependant, la robustesse et la précision de l"acquisition 3D des gestes restaient insuffisantes. Ce travail propose de nouveaux algorithmes pour améliorer l"acquisition en temps réel du mouvement en fonction de la puissance de calcul disponible.

Amélioration de la perception des utilisateurs dans les environnements virtuels collaboratifs

Un environnement virtuel collaboratif (EVC) est utilisé pour l"interaction et la collaboration entre des utilisateurs distants. Un avatar est une représentation d"un utilisateur dans un environnement virtuel. Il est animé par celui-ci et permet de communiquer avec les autres utilisateurs pour donner un sentiment de présence à distance (téléprésence). Toutefois, la sélection d"animations prédéfinies à partir de menus ou d"icones est fastidieuse.

Nous proposons d"améliorer la perception mutuelle des utilisateurs par l"acquisition 3D et la restitution virtuelle des gestes par vision monoscopique. Les gestes humains sont capturés à partir d"une webcam en utilisant des algorithmes de vision par ordinateur et reproduits en temps réel par un avatar. Ce type d"immersion permet d"établir un canal de communication gestuelle et d"améliorer le sens de téléprésence dans un monde virtuel 3D [START_REF] Horain | Virtually enhancing the perception of user actions[END_REF]. L"acquisition des gestes par vision monoculaire ne nécessite qu"un ordinateur personnel avec une webcam.

Principaux défis

Nous nous intéressons à l"acquisition 3D des gestes par vision monoculaire en temps réel sans marqueurs [START_REF] Horain | 3D Model Based Gesture Acquisition Using a Single Camera[END_REF]. Ce problème de vision par ordinateur est très difficile à cause de l"absence d"information de profondeur dans des images monoculaires, le grand nombre de paramètres à estimer pour la pose humaine, l"imprévisibilité du mouvement humain, les occlusions des parties du corps, les variations des vêtements, les variations de la morphologie humaine et la complexité de l"environnement dans les images capturées.

Contribution de la thèse

Dans ce travail de thèse, nous partons des travaux antérieurs [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]

Technologies d'acquisition du mouvement

Les systèmes de « mocap » (motion capture) sont composés généralement par des caméras synchronisées et des marqueurs placés sur les membres (ou les articulations) des acteurs et en fournissant les positions ou les orientations. Le mouvement acquis est associé à un modèle 3D informatique.

L"acquisition du mouvement peut être optique [START_REF] Optitrack | Optitrack optical motion capture solutions[END_REF], mécanique (Gypsy7, 2010), magnétique (AMM, 2010), acoustique (Intersense, 2010) et inertielle (IGS-190-M, 2010). Toutefois, ces technologies nécessitent des matériels coûteux et invasifs et peuvent limiter la liberté de mouvement de l'acteur.

Acquisition de mouvement humain par la vision par ordinateur

L"acquisition des mouvements du corps humain par des techniques de vision par ordinateur ne nécessite ni matériel coûteux ou encombrant ni marqueurs (uniquement des caméras). Toutefois, les algorithmes proposés pour l"acquisition de mouvement humain à cadences vidéo quasi temps réel reposent principalement sur des systèmes de caméras multi-vues dans des conditions contrôlées qui limitent leur applicabilité.

L"estimation de l"attitude du corps humain par vision artificielle est un défi scientifique et informatique [START_REF] Sminchisescu | 3D human Motion Reconstruction in Monocular Video: Techniques and Challenges[END_REF]. Nous présentons une analyse détaillée des techniques existantes, en temps réel ou non, ainsi que des systèmes mono et multi-caméras [START_REF] Poppe | Vision-based human motion analysis: An Overview[END_REF], (Moeslund, et al.).

Primitives d'images pour l'acquisition des gestes

Pour estimer l"attitude du corps, des primitives d"images sont utilisées comme des indices pour trouver la position de chaque partie du corps et par la suite, l"estimation de la pose 3D complète. Des primitives d"images couramment utilisés dans la littérature sont notamment la couleur [START_REF] Broekhuijsen | Estimating 2D Upper Body Poses from Monocular Images[END_REF], les silhouettes [START_REF] Agarwal | Recovering 3D human pose from monocular images. s.l[END_REF], les contours [START_REF] Chen | Markerless monocular motion capture using image features and physical constraints[END_REF] et le mouvement [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF].

Approches génératives

Ces approches estiment l"attitude du corps humain en recalant sur les images un modèle 3D de ce corps, qui intègre la chaîne cinématique des articulations et les dimensions des parties du corps. Trouver l"attitude qui correspond le mieux aux primitives de l'image peut être très difficile en raison des éventuelles auto-occultations entre parties du corps et des ambiguïtés entre des attitudes 3D correspondant en projection aux mêmes primitives dans l"image. Plusieurs travaux proposent différents modèles de corps humain et des méthodes pour estimer et suivre la pose humaine sur séquence vidéo. Certaines méthodes d'apprentissage sont également utilisées pour améliorer les résultats d"acquisition de mouvement. Ces méthodes seront décrites ci-dessous.

Modèles du corps humain

Le corps humain est modélisé essentiellement par un arbre cinématique composé de segments rigides reliés par des articulations. Chaque segment représente une partie spécifique du corps humain. Le modèle peut être 2D [START_REF] Cham | Multiple hypothesis approach to figure tracking[END_REF], [START_REF] Morris | Singularity Analysis for Articulated Object Tracking[END_REF] ou 3D [START_REF] Deutscher | Articulated Body Motion Capture by Stochastic Search. s.l[END_REF], [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF]. Une articulation peut comporter jusqu'à 3 degrés de liberté. Chaque attitude du modèle est décrite par un vecteur de paramètres tels que les angles des articulations ou les positions dans l"espace des parties du corps.

Estimation de la pose humaine

L"estimation de l"attitude consiste à rechercher les paramètres du modèle qui maximisent la similitude entre les primitives extraites du modèle et de l"image. Les approches génératives peuvent procéder par estimation descendante (top-down) ou ascendante (bottom-up). Les approches descendantes [START_REF] Delamarre | 3D articulated models and multiview tracking with physical forces. s.l[END_REF], [START_REF] Grest | Single View Motion Tracking by Depth and Silhouette Information. s.l. : Image Analysis[END_REF], (Sminchisescu, et al., 2002) estiment le vecteur d'état complet qui décrit la pose humaine, où chaque paramètre d'état représente chaque degré de liberté du modèle du corps (par exemple un angle d'articulation). Un inconvénient de cette approche est que la pose initiale sur la première image doit être spécifiée manuellement par l'utilisateur. Les approches ascendantes [START_REF] Ramanan | Finding and Tracking People From the Bottom Up[END_REF], [START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF]

Approches discriminatives

Ces approches n"utilisent pas un modèle explicite du corps humain. Au lieu de cela, ils infèrent la pose directement à partir des primitives d"image. Les approches discriminatifs utilisent des exemples d"entrainement afin d"établir une relation directe (ou mappage) entre les primitives d"image et la pose humaine. Par conséquence, les données d"entrainement doivent généraliser les différentes variations sur la configuration de la pose, les dimensions du corps, point de vu et l"apparence. Les données d"entrainement doivent également considérer la non-linéarité de la correspondance entre l"image et l"espace de la pose. Les techniques d"estimation de la pose qui utilisent des approches discriminatives peuvent être divisées en deux classes : estimation basée sur l"apprentissage et l"estimation à partir des exemples.

Dans l"estimation basée sur l"apprentissage [START_REF] Rosales | Inferring Body Pose Without Tracking Body Parts[END_REF], [START_REF] Agarwal | Recovering 3D human pose from monocular images. s.l[END_REF], [START_REF] Elgammal | Inferring 3D body pose from silhouettes using activity manifold learning[END_REF], une fonction est apprisse pour associer les primitives d"image avec la pose 3D en utilisant des données d"entrainement. L"estimation à partir des exemples [START_REF] Sullivan | Recognizing and tracking human action[END_REF], [START_REF] Toyama | Probabilistic Tracking with Exemplars in a Metric Space. s.l[END_REF], [START_REF] Stenger | Topology free hidden markov models: Application to background modeling[END_REF] évite l"apprentissage en stockant une basse de données d"exemples d"entrainement dont les poses 3D sont connues. L"estimation de la pose est réalisée par la recherche d"exemples entrainés similaires à l"image d"entrée, et de l"interpolation de la pose 3D. Un inconvénient de ces approches est la grande quantité d'espace nécessaire pour stocker la base de données car le nombre d"exemplaires peut grandir de façon exponentielle par rapport à la complexité de l"objet.

Suivi de la pose

Le suivi de la pose est un processus pour estimer la pose humaine entre les trames successifs de la séquence vidéo. Généralement, il existe deux approches pour le suivi de la pose humaine : d"une part, ceux qui utilisent ou prédire une seule hypothèse (pose de configuration) à chaque image (suivi avec une seule hypothèse) et d'autre part, ceux qui propagent plusieurs hypothèses (suivi avec plusieurs hypothèses) ou des solutions par trame.

Un suivi simple d"une seule hypothèse consiste à la mise à jour de la configuration de la pose à chaque image. Certains auteurs utilisent des techniques plus complexes, tels que des filtres récursifs linéaires (par exemple le filtre de Kalman [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF]) afin de prédire la pose humaine dans l"image suivante. Malheureusement, le suivi avec une seule hypothèse ne peut pas traiter la pose avec les ambiguïtés des observations à partir d'images monoculaires. Afin de surmonter le problème des ambiguïtés dans les observations d'image, plusieurs hypothèses peuvent être reproduites dans chaque trame. Ceci est fait en adoptant des approches d'échantillonnage à base de particules, comme la filtration ou l'algorithme CONDENSATION [START_REF] Gordon | Novel approach to nonlinear/nonGaussian Bayesian state estimation[END_REF], [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. La grande dimensionnalité de l"espace des poses nécessite l'utilisation d'un grand nombre de particules. Toutes les particules doivent être propagées et évalués (pondéré) selon une fonction de coût correspondant. Par conséquent, l"augmentation du coût de calcul. Récemment, de nombreux travaux [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF], [START_REF] Saboune | Markerless human motion capture for Gait analysis[END_REF], [START_REF] Fontmarty | Data fusion within a modified annealed particle filter dedicated to human motion capture[END_REF] ont proposé de modifications sur l"algorithme de filtrage particulaire afin de guider les échantillons (particules) de manière efficace dans l'espace des poses et donc de réduire le nombre de particules nécessaires.

Modèles dynamiques

Les modèles dynamiques peuvent modéliser la dynamique d'un mouvement humain qui est généralement périodique (par exemple marcher, courir, le swing pour le golf, etc.) Ils sont utilisés comme aprioris en vue d"obtenir un suivi plus stable tout en réduisant le coût de calcul. En utilisant ces modèles, la robustesse du suivi peut être améliorée, même avec des informations incomplètes ou occlusions. Néanmoins, les modèles dynamiques ont l'inconvénient de dépendre de façon significative de la quantité de données d'apprentissage disponibles. Par conséquence, l'ensemble des exemplaires doit être suffisamment large et en plus, il considér les variations dans le mouvement acquis. Un autre inconvénient est le fait que l'utilisation d'un fort modèle dynamique peut limiter le suivi à l"ensemble des actions déjà apprises.

Les modèles dynamiques peuvent être divisés en deux catégories: les modèles de grande dimension [START_REF] Sidenbladh | Implicit probabilistic models of human motion for synthesis and tracking[END_REF], [START_REF] Caillette | Real-time 3-D human body tracking using variable length markov models[END_REF] qui sont apprises directement de l"espace des poses et des modèles de faible dimension [START_REF] Urtasun | 3D human body tracking using deterministic temporal motion models[END_REF] qui sont obtenues dans un espace latente avec dimension inférieure, où le suivi de la pose est effectué.

Notre approche de base pour l'acquisition 3D des gestes

Dans cette section, nous décrivons notre approche de base précédemment proposée dans les travaux de [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. Notre approche de base pour l"acquisition 3D des gestes par vision monoculaire en temps réel consiste à recaler un modèle 3D articulé de la partie supérieure du corps humain sur des séquences vidéo 2D.

En première étape, on extrait des primitives de l'image d'entrée et les primitives de notre modèle 3D du corps humain. Ensuite, la correspondance entre les primitives de l"image et du modèle 3D est évaluée en utilisant une fonction de coût d"association. Notre processus de recalage consiste à chercher la pose du modèle 3D qui mieux corresponde aux primitives extraites de l'image 2D, tout en respectant des contraintes biomécaniques (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF].

Notre modèle 3D de la moitié supérieur du corps humain

Notre modèle du corps humain est un arbre cinématique d"une chaine articulée qui est composée de segments du corps reliés par des articulations en fonction de la hiérarchie décrite dans le standard H-ANIM (H-ANIM 1.1). Chaque segment de la structure cinématique est couvert par des maillages. Les segments du corps inclus dans notre modèle 3D sont: le buste, la tête, les bras, les avant-bras et les mains. Les joints d"articulations inclus sont: la racine de l"humanoïde, le cou, les épaules, les coudes et les poignets.

Pour chaque image capturée, notre système d"acquisition des gestes trouve le vecteur des angles articulatoire qui décrit la pose estimée 3D. Ensuite, il est codé dans le format MPEG-4 spécifié dans la norme internationale ISO/IEC 14996-2 (2001). L"ensemble de paramètres BAP se compose de 186 angles articulatoires du corps qui comprennent la sacro-iliaque, la hanche, le genou, la cheville, les vertèbres, la clavicule, l"épaule, le coude, le poignet et les articulations des doigts. Ces articulations sont utilisées pour animer un avatar 3D dans un environnement virtuel.

Recalage sur les régions

Notre processus de recalage consiste à optimiser de manière itérative la correspondance entre les primitives du modèle 3D et de l"image d"entrée par rapport aux paramètres du modèle. Dans le recalage sur les régions, les primitives extraites sont les régions colorées de l"image et du modèle 3D. Trois classes de régions sont considérées : la peau, la tête et les vêtements. Le modèle 3D dans un pose candidate est projetée sur l"image segmentée et la correspondance entre les régions est mesurée en utilisant une fonction de taux de non recouvrement [START_REF] Ouhaddi | Vers la modélisation du geste par la vision. s.l. : Traitement du signal[END_REF] :

(2.10) où q représente le vecteur des paramètres qui décrivent la posture candidate, A c est l"ensemble des pixels dans la c ème classe de couleur dans l"image vidéo segmentée, B c (q) est l"ensemble des pixels dans la c ème classe de couleur dans la projection du modèle, m est le nombre de classes de couleur et | X | représente le nombre de pixels dans X. Cette fonction est ensuite itérativement minimisée par rapport à q en utilisant un algorithme de descente de simplex [START_REF] Nelder | A simplex method for function minimization[END_REF], tout en respectant des contraintes biomécaniques. Le recalage à chaque trame est initialisé avec la pose recalé à l"image précédente. De cette façon, le processus de recalage respecte la cohérence temporelle du mouvement humain. Les contraintes biomécaniques définissent un domaine convexe dans l"espace de poses dans lequel le simplex est limité.

Conclusions et travaux futurs

Dans ce chapitre, nous avons présenté un bref résumé des technologies actuelles couramment utilisés pour l"acquisition du mouvement humain. Nous avons exposé l'importance d'utiliser des techniques de vision par ordinateur pour l"acquisition des gestes. Ensuite, nous avons présenté une analyse exhaustive des méthodes existantes pour l"acquisition de mouvement humain par vision par ordinateur. Enfin, nous avons présenté notre approche de base qui consiste à recaler un modèle 3D articulé de la partie supérieure du corps humain sur des séquences vidéo 2D (Marques [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF].

Dans les prochains chapitres, nous présentons les méthodes proposées pour remédier aux limitations de notre approche de base. Nous allons proposer de nouvelles méthodes pour obtenir un suivi plus précis, robuste et un temps de calcul limité. Dans ce cas, des expériences exhaustives doivent être effectuées sur plusieurs séquences vidéo afin de valider la précision et les robustesses réalisées par nos algorithmes proposés.

Chapitre 3 : Recalage sur les régions et recalage sur les contours pour l'acquisition 3D des gestes par vision monoscopique

Introduction

Dans ce chapitre, nous développons des nouveaux algorithmes pour améliorer la performance de l"acquisition des gestes de notre approche de base (section 2.4). Tout d'abord, nous décrivons brièvement les modules mis en oeuvre pour notre système. Ensuite, un algorithme de soustraction d'arrière-plan pour extraire la silhouette humaine est proposé. Après, nous introduisons notre approche basée sur deux étapes de recalage entre les régions colorées et les contours. La performance expérimentale de chaque étape est comparée pour trouver un équilibre entre les deux étapes tout en faisant face aux ressources de calcul limitées.

Mise en oeuvre de notre approche

Notre système d"acquisition des gestes est divisé en deux grandes étapes: l'initialisation et le suivi. L'initialisation se réfère au processus d'apprentissage automatique de l'apparence de l'arrière-plan et l'utilisateur. Dans la deuxième étape, on extrait en temps réel les caractéristiques de l'image d"entrée de la séquence vidéo et nous estimons la pose 3D qui corresponde mieux aux caractéristiques de l'image 2D [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. Finalement, la pose 3D obtenue est utilisée pour animer un avatar 3D dans un environnement virtuel collaboratif.

Etalonnage automatique du modèle et initialisation de la pose

Le modèle du corps est étalonné de manière à le rendre semblable à l'acteur dans la vidéo capturée. Cela peut être fait en ajustant les paramètres de forme (longueur, largeur et hauteur) de chaque partie du corps du modèle 3D. Le vecteur des angles d"articulations est également ajusté pour que la pose du modèle 3D soit semblable à la pose de l'acteur dans l'image première entrée. Nous utilisons le recalage sur les régions pour étalonner automatiquement le modèle 3D et initialiser la pose 3D [START_REF] Chen | Markerless monocular motion capture using image features and physical constraints[END_REF]. Nous supposons que la première image de la séquence vidéo contient une pose de l'acteur sans autooccultations des parties du corps. L"étalonnage du modèle consiste en trois étapes: translation du modèle, ajustement de la pose 3D et adaptation de la forme. Ces étapes sont réalisées une seule fois sur la première image d'une séquence vidéo, donc il ne représente pas une limitation pour le calcul en temps réel.

Soustraction de l'arrière-plan pour l'extraction de la silhouette humaine

La soustraction de l"arrière-plan permet de traiter uniquement les régions de l'image qui contient l'objet d'un intérêt ou dans notre cas, l"acteur. Dans cette section, nous proposons un algorithme en temps réel pour la soustraction d'arrière-plan afin d'extraire la silhouette humaine en faisant face aux variations d'éclairage. Dans notre algorithme, deux primitives d"images sont combinés : la chrominance et les gradients. Pour la chrominance, nous utilisons les composantes de chrominance de l"espace de couleur YCrCb. La composante de luminance Y est ignorée pour une meilleure robustesse aux variations d"éclairage. Afin d"obtenir plus de robustesse, nous utilisons également les gradients, car ils exploitent la relation entre le voisinage de chaque pixel, et donc ils sont moins sensibles aux variations de la lumière (Bernier, 2006). Ces deux primitives sont modélisées par des fonctions gaussiennes. Les étapes de notre algorithme sont décrites ci-après.

 Extraction des primitives. Pour chaque image d'entrée RGB , on extrait les gradients orientés et le vecteur de chrominance à partir de l"espace de couleur YCrCb.  Combinaison des primitives. Nous calculons une carte de probabilité de l"arrièreplan à partir des gradients orientées et une carte de probabilité de l"arrière-plan à partir des vecteurs de chrominance . Ensuite, nous combinons les probabilités de l"arrière-plan dans une carte de probabilité combinée en prenant la probabilité maximal.

(3.25)

 Classification des pixels. Un masque binaire des pixels classés comme l"avantplan est générée par seuillage de la carte de probabilité combiné  Segmentation de l'avant-plan. Un post-traitement est appliqué à afin de nettoyer les masque. D"abord, nous appliquons une ouverture morphologique pour supprimer les petites régions de bruit dans le masque. Après une fermeture morphologique est appliquée pour remplir les petits trous dans l'avant-plan.

Recalage sur les contours

Le recalage sur les régions ne nécessite qu"un recouvrement partiel entre régions colorées pour converger vers une pose 3D approximativement correcte. Toutefois, elle n"est pas précise car les pixels de la frontière des régions sont peu nombreux par rapport aux pixels de l"intérieur de la région. Afin d"augmenter la précision, nous utilisons une étape de recalage sur les contours qui consiste à mettre en correspondance les contours de l"image avec les contours occultant du modèle 3D en minimisant la distance qui les sépare. L"état initial du modèle 3D pour cette étape est l"état final du recalage sur les régions. Les contours dans l"image d"entrée sont extraits par un filtre de Deriche (Deriche, 1990). Une carte de distance aux contours est ensuite calculée par un algorithme de chanfrein [START_REF] Borgefors | Distance transformations in digital images[END_REF]. Ensuite, on extrait les contours occultant du modèle 3D. La distance résiduelle entre les contours occultant du modèle projeté et les contours extraits de l"image vidéo est la moyenne de la carte de distance masquée par l"image binaire des contours occultant : (3.26) Où est la distance moyenne entre contours, est la carte de distance, sont les pixels de la projection des contours occultant du modèle 3D. Le recalage sur les contours consiste à minimiser cette distance entre contours par l"algorithme de descente de simplexe [START_REF] Nelder | A simplex method for function minimization[END_REF]) déjà utilisé précédemment.

Expériences de performance pour le processus de recalage

L"optimisation itérative dans un espace de grande dimension nécessite habituellement un grand nombre d'itérations pour converger. Parce que nous sommes intéressés par l"acquisition des gestes en temps réel, nous devons limiter le temps de calcul, par conséquence, le nombre d'itérations par image. Pour cette raison, nous avons analysé la performance (robustesse et précision) de notre approche en fonction du nombre d'itérations effectuées à chaque étape du recalage (recalage sur les régions et les contours), afin de trouver un équilibre optimal entre la performance et le temps de calcul dans les deux étapes de recalage.

Evaluation de la robustesse pour l'acquisition des gestes en temps-réel

Afin de mesurer la robustesse de notre approche, une analyse expérimentale a été effectuée avec des séquences vidéo réelles. Nous avons utilisé 6 séquences vidéo présentant des gestes avec occultations, des mouvements rapides, ainsi que des mouvements dans la direction de la profondeur et une personne légèrement de coté.

Nous avons calculé, pour chaque séquence vidéo, l'erreur moyenne résiduelle de chaque fonction d'évaluation et le nombre de décrochages en fonction du nombre d"itérations effectuées. À partir de ces expériences, nous constatons que le recalage sur les régions converge plus rapidement que le recalage sur les contours. Les résultats montrent que le recalage sur les contours est moins stable (grand nombre de pics) que le recalage sur les régions.

Pour avoir la meilleure performance, nous donnons la priorité à la stabilité du recalage lorsque le nombre d"itérations est inferieur à 200 (valeur choisie expérimentalement) en consacrant toutes les itérations au recalage sur les régions. Au-delà, le nombre de décrochage du recalage sur les régions devient relativement petit, ce qui permet d"améliorer la précision du recalage par des itérations supplémentaires de minimisation de la distance entre les contours.

Evaluation de la précision pour l'acquisition des gestes en temps-réel

Dans cette section, nous analysons la performance de notre approche à l'égard de la précision de l'estimation de la pose 3D en temps réel. L'évaluation quantitative de la précision de l"acquisition 3D des gestes nécessite des séquences vidéo avec la vérité-terrain. Nous avons utilisé un ensemble de gestes communicative synthétique (Li, et al., 2009). Dans ces séquences vidéo, différents types de gestes sont inclus: de mouvement dans la direction de la profondeur, gestes avec occultations et des mouvements rapides. Encore une fois, nous avons fait varier le nombre d'itérations (de 1 à 500 itérations) pour chaque étape de recalage (recalage sur les régions et les contours) et nous avons calculé, pour chaque séquence vidéo, la moyenne de l"erreur résiduelle de la pose 3D. L'erreur résiduelle est calculée à partir de la distance 2D entre les joints dans le plan de l'image afin d'évaluer la précision indépendamment des ambiguïtés des images monoculaires. De cette façon, une erreur résiduelle 2D entre les joints d'articulation peut être obtenue comme suit: Nous avons calculé la moyenne des erreurs résiduelles 2D pour toutes les séquences vidéo de synthèse et, nous avons modélisé l"erreur par un polynôme quadratique obtenu par régression [START_REF] Phillips | ZunZun.com Online Curve Fitting and Surface Fitting Web Site[END_REF]. A partir du polynôme quadratique, nous avons obtenu une courbe optimale décrivant le nombre d'itérations allouées à chaque étape de recalage afin d'obtenir la meilleure précision en temps réel. Grâce à la courbe optimale, nous vérifions que, nous pouvons profiter de la précision donnée par le recalage sur les contours après un certain nombre d'itérations de du recalage sur les régions (après 150 itérations). De cette façon, nous pouvons adapter notre prototype d"acquisition des gestes à la puissance de calcul de chaque plate-forme en d"allouant les itérations de recalage sur les régions et les contours qui permettront obtenir la meilleure performance en temps réel.

Conclusions et travaux futurs

Nous avons présenté un algorithme pour l"acquisition 3D des gestes par vision monoscopique en temps réel, basée sur le recalage d'un modèle 3D articulé sur des régions colorées, puis sur les contours. A partir des résultats expérimentaux, nous avons démontré l'efficacité de la combinaison des primitives pour arriver à un suivi plus robuste et précis en temps réel. Enfin, nous avons proposé une analyse expérimentale pour obtenir une courbe optimale qui décrit le nombre d'itérations allouées à chaque étape du recalage afin d"obtenir la meilleure précision en temps réel. Même si notre approche peut arriver à une acquisition des gestes très robuste pour une grande variété de gestes en temps réel, il est encore limité par des ambiguïtés qui sont inhérentes aux images monoculaires. Ainsi, une méthode plus sophistiqué doit être adopté afin de résoudre le problème des ambiguïtés causées par le manque d'informations de la profondeur tout en préservant le temps réel.

Chapitre 4 : Filtrage particulaire en temps réel avec heuristiques pour l'acquisition 3D des gestes par vision monoscopique

Introduction

Dans le chapitre précédent, nous avons montré que l"acquisition 3D des gestes par vision monoscopique peut être obtenue de façon itérative par une méthode d'optimisation locale [START_REF] Nelder | A simplex method for function minimization[END_REF]. Cependant, le manque d'information de la profondeur dans les images monoculaires rend l"acquisition 3D des gestes difficile à suivre car plusieurs solutions (poses 3D) peuvent recaler dans la même observation 2D. Les ambiguïtés 3D dans les images monoscopique peuvent être mieux gérées par propagation des plusieurs hypothèses ou poses candidates à chaque trame sur des séquences vidéo. Dans ce cas, les méthodes de Monte Carlo séquentielles (ou de filtrage particulaire), fournissent un modèle flexible et puissant pour estimer le comportement des systèmes non linéaires en utilisant plusieurs hypothèses à chaque instant. Dans ce chapitre, nous proposons un algorithme de filtrage particulaire en temps réel pour l"acquisition 3D des gestes par vision monoscopique. L'algorithme proposé permet de gérer les ambiguïtés des images monoculaires en conservant, au même temps, la contrainte de calcul en temps réel.

Approche de filtrage particulaire

Les filtrages particulaires ou méthodes de Monte Carlo séquentielles (SMC) fournissent une approche pratique pour estimer les systèmes dynamiques complexes en utilisant des échantillons ou des particules. Ces méthodes visent à estimer la séquence de paramètres cachés à partir des données observées . L"algorithme de CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF], également connu sous le nom de ré-échantillonnage d"importance séquentiel, est un algorithme de filtrage particulaire couramment utilisé. Les étapes de l"algorithme sont décrites ci-après.

 Ré-échantillonnage. Ré-échantillonner (avec remplacement) une nouvelle ensemble de particules de l"ensemble pondérée . La probabilité de sélectionner chaque particule est proportionnelle à son poids .

 Prédiction. Générer à partir de l"ensemble de particules selon un modèle de diffusion stochastique , où η est un bruit Gaussien. De cette façon, le nouvel ensemble de particules représente l'incertitude dans le comportement de l'objet d'un suivi.

 Mesurer. Evaluer les nouvelles particules par rapport aux observations . Puis, normaliser l"ensemble de particules pondérées de façon que et calculer les probabilités cumulés.

L"ensemble de particules pondérées représentent la nouvelle densité postérieure de l'état du système actuel.

Filtrage particulaire pour l'acquisition 3D des gestes

Le problème pour l"acquisition 3D des gestes est la grande dimensionnalité de l'espace de configuration des poses humaines ainsi que le coût de calcul nécessaire pour évaluer toutes ces particules (poses candidates). Les observations basées sur des primitives visuelles (par exemple la couleur, les contours, les textures, etc.) ne fournissent pas suffisamment d'informations pour trouver le maximum global de la fonction de vraisemblance à cause des ambiguïtés d'images monoculaire. Malgré la complexité du problème de l"acquisition 3D des gestes, différentes stratégies ont été proposées pour le filtrage particulaire afin de faire face à la grande dimension et la multi-modalité de l'espace des poses. L'objectif de ces stratégies est d'échantillonner les particules de manière plus efficace en intégrant différents méthodes tels que la décomposition de l"espace [START_REF] Maccormick | Partitioned Sampling, Articulated Objects, and Interface-Quality Hand Tracking[END_REF], échantillonnage avec recuit simulé [START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF], l'optimisation locale [START_REF] Cham | Multiple hypothesis approach to figure tracking[END_REF], l'inférence analytique [START_REF] Lee | Particle Filter with Analytical Inference for Human Body Tracking[END_REF] (Sminchisescu, et al., 2003), l'échantillonnage déterministe [START_REF] Saboune | Markerless human motion capture for Gait analysis[END_REF], etc.

Notre approche de filtrage particulaire pour l'acquisition 3D des gestes par vision monoscopique

Dans cette section, nous décrivons notre approche de filtrage particulaire pour l"acquisition 3D des gestes par vision monoscopique en temps réel. L'idée principale est l"intégration des heuristiques pour guider les particules vers les solutions plus probables de la fonction de densité de probabilité. Notamment, nous avons mis en oeuvre quelques modifications à l'approche originale CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF] afin de trouver plus efficacement les solutions plus probables dans l"espace des poses en combinant plusieurs stratégies pour l"acquisition 3D des gestes (section 4.3). Les heuristiques proposées permettent de gérer le problème des ambiguïtés dans les images monoculaire tout en respectant le calcul en temps réel.

Mis en oeuvre du filtrage particulaire

Une particule ou échantillon à l'instant t est un vecteur de 20 angles de l'articulation qui correspond aux 20 degrés de liberté de notre modèle 3D de la partie supérieur du corps. De cette façon, chaque particule décrit un possible pose candidat.

Le poids de chaque particule est défini en combinant les mesures basées sur la correspondance entre régions et les contours en utilisant la fonction de vraisemblance suivante. (4.31) où est la mesure de taux de non recouvrement décrit dans l'équation (2.1), est la distance résiduelle entre contours décrit dans l'équation (3.2). et sont les écarts-types qui expriment la variance moyenne des taux de non recouvrement et la distance résiduelle entre contours respectivement sur une séquence vidéo complète.

Heuristiques proposés et analyse expérimentale

Nos heuristiques reposent sur des méthodes déterministes qui permettent de guider les particules vers des solutions probables de la densité postérieure. En outre, la contribution de chaque heuristique proposée est analysée expérimentalement en utilisant les séquences vidéo de synthèse qui ont été introduites dans le chapitre précédent. Pour toutes les vidéos, nous calculons la moyenne des erreurs résiduelles 3D et le nombre de décrochages.

Ré-échantillonnage déterministe par poids

Cette heuristique consiste à propager les particules de poids importants plutôt que des particules de faible probabilité. Dans cette heuristique chaque particule parent va donner naissance à un certain nombre de particules enfants (ré-échantillonnées) dont le nombre d"enfants est proportionnelles au poids de la particule parent. D'après les résultats expérimentaux nous constatons que notre ré-échantillonnage déterministe par poids présente une erreur résiduelle 3D moins stable que celle de l'algorithme CONDENSATION. Cela signifie que la suppression de la variabilité aléatoire dans l'étape de ré-échantillonnage peut réduire l'efficacité du filtrage particulaire. Toutefois, nous observons que la réduction du caractère aléatoire peut améliorer la robustesse, même pour les gestes vers la direction de la profondeur. Ainsi, cette heuristique maintient les particules proche du minimum au prix de limiter la recherche de solutions dans l"espace des poses 3D.

Échantillonnage partitionné basée mouvement

Cette stratégie consiste à échantillonner (avec bruit aléatoire gaussien) seulement les parties du corps qui présentent un certain mouvement entre la trame antérieure et actuelle. Nous avons partitionné le vecteur de pose en quatre sous-ensemble de paramètres :

. , et sont respectivement les paramètres de la tête, le bras gauche et le bras droite. Les paramètres ont un effet sur la poitrine et toutes les parties du corps. Pour chaque sous-ensemble de paramètres, on va mesurer la présence de mouvement par rapport aux variations dans la correspondance des régions colorées entre la trame antérieure et actuelle.

Nous avons observé expérimentalement que l"échantillonnage partitionné basée mouvement permet d'obtenir une amélioration significative de précision pour les séquences vidéo qui contiennent des gestes dans la direction fronto-parallèle. Toutefois, en cas des gestes vers la direction de la profondeur, l"échantillonnage partitionné ne réussit pas à guider les particules correctement. Par rapport à la robustesse, l"échantillonnage partitionné basée mouvement permet d"obtenir une réduction significative du nombre de décrochages pour toutes les types des gestes.

Prédiction avec l'optimisation locale

Cette heuristique consiste à l"utilisation d"une optimisation locale pour guider les groupes de particules vers les minimums locaux de la fonction de coût dans l'espace des poses. Dans notre espace de dimensions (20 paramètres), nous considérons les groupes de particules de plus de enfants, et nous dérivons un simplex qui sera optimisé itérativement avec l"algorithme de descente de simplex [START_REF] Nelder | A simplex method for function minimization[END_REF]. Toutefois, si les petits groupes de particules enfants (

) ne sont pas suffisamment nombreux pour initialiser un simplex, ils ont encore une chance d'explorer l'espace de grande dimension en utilisant un échantillonnage aléatoire comme l'algorithme CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF].

Cette heuristique produit un suivi très robuste (faible nombre de décrochages) pour toutes les séquences vidéo considérées. Cela signifie que l'optimisation locale est capable de guider correctement les particules vers les minimums de l'erreur résiduelle 2D. Toutefois, la précision de la pose 3D est dégradée principalement pour les gestes vers la direction de la profondeur.

Echantillonnage par sauts-cinématiques

Nous avons mis en oeuvre l'approche proposée dans (Sminchisescu, et al., 2003) pour calculer analytiquement des nouvelles poses 3D alternatives qui correspondent à la projection 2D de l'image actuelle. Cette approche permet de trouver rapidement de nouveaux minimums sans la recherche exhaustive dans l'espace de grande dimensionnalité. Afin d"analyser expérimentalement la performance de l"échantillonnage par sautscinématique, nous avons calculé des nouvelles poses alternatives pour les meilleures échantillons après l'étape d"évaluation des particules de l'algorithme de CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Par rapport aux résultats, l"échantillonnage par sauts-cinématiques n"a pas améliorée significativement la précision 3D de la pose estimée. Cependant, il contribue à obtenir un suivi plus stable principalement avec les gestes vers la direction de la profondeur. Cela signifie que les particules peuvent arriver rapidement aux minimums locaux alternatifs qui appartiennent aux configurations 3D ambigües.

Changement de paramétrage (suivi avec le bout de la chaine cinématique)

Nous proposons un changement de paramétrage qui consiste en l"utilisation des positions du bout de la chaine cinématique, plutôt que les angles des articulations. Ce paramétrage nous permet de mieux modeler l'incertitude du mouvement dans la direction de la profondeur [START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF]. Considérant la cinématique de la partie supérieure du corps, les nouveaux paramètres sont les coordonnées 3D des poignets dans le repère de la caméra. De cette manière, au lieu d'estimer l'ensemble des angles des articulations des bras, nous estimons directement la position 3D des poignets par rapport aux observations des images. Afin de contrôler la recherche dans l"espace de solutions, nous définissons, pour chaque cordonnée du poignet , un écart maximal en fonction de l'amplitude du mouvement entre chaque trame (-x. +x. -y. +y, -z, +z). De cette façon, les particules sont forcées à chercher vers les directions de la profondeur en gonflant l'écart maximum dans la direction avec plus d"incertitude (-z, +z).

Dans notre analyse expérimentale, notre méthode a amélioré la précision 3D ainsi que la robustesse pour les séquences vidéo avec des gestes dans le sens de la profondeur. Cependant, la précision n'est pas améliorée significativement pour les séquences vidéo qui contiennent des mouvements fronto-parallèles

Accélération par GPU

Afin d'atteindre le temps réel dans le filtrage particulaire avec grand nombre de particules, certains travaux ont profité de la puissance de calcul des GPUs [START_REF] Hendeby | A graphics processing unit implementation of the particle filter[END_REF], [START_REF] Lenz | A gpu-accelerated particle filter with pixel-level likelihood[END_REF]. Dans notre implémentation GPU, nous avons parallélisé l'évaluation des particules qui est le principal goulot d'étranglement de calcul de notre algorithme. L'évaluation de la pose candidate consiste à projeter le modèle 3D sur le plan de l'image. Dans ce cas, nous avons mis en oeuvre le taux de non recouvrement à partir du calcul parallèle de l"histogramme. De cette façon, nous avons concaténé tous les images résultant de l"addition de la projection du modèle 3D avec l"image segmentée pour calculer les histogrammes correspondantes en parallèle. Notre mise en oeuvre comporte deux niveaux de parallélisme, l'une sur les images associées à des particules, l'autre sur les pixels de chacune de ces images.

Mise en oeuvre du filtrage particulaire en temps réel avec heuristiques

Dans cette section, nous décrivons l"intégration des heuristiques proposées dans l"algorithme de filtrage particulaire. Afin d"améliorer la robustesse et la précision de la pose estimée, nous avons combiné les avantages de chaque heuristique. Les étapes de notre algorithme de filtrage particulaire proposé sont décrites ci-dessous.

Données d'entrée :

L"ensemble de particules (poses candidates) qui représente la densité postérieure précédente. Dans les résultats expérimentaux, l'algorithme de filtrage particulaire a démontré une amélioration significative de la précision 3D et la robustesse par rapport à l'algorithme CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF], pour toutes les séquences vidéo, même pour les gestes avec des mouvements vers la profondeur. Dans ces résultats, aucun décrochage n"a été rencontré lors de l'utilisation de plus de 200 particules pour toutes les séquences vidéo.

Dans nos résultats, une erreur de précision 3D résiduelle entre 80 et 120 mm a été obtenue par notre algorithme de filtrage particulaire avec heuristiques. Ces résultats surpassent de façon significative la méthode d'optimisation locale précédemment décrit dans le chapitre 3, ainsi que les résultats [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF], où les erreurs de précision résiduelle varient entre 200 et 300 mm. En plus, la précision obtenue dans les séquences vidéo monoculaires est similaire à l'état de l"art des approches pour l"acquisition 3D des gestes en temps réel par stéréovision [START_REF] Bernier | Fast nonparametric belief propagation for real-time stereo articulated body tracking. s.l[END_REF] et [START_REF] Fontmarty | Vision et filtrage particulaire pour le suivi tridimensionnel de mouvements humains: applications à la robotique[END_REF], dans lesquelles les auteurs ont rapporté une erreur résiduelle qui varie de 60 à 100 mm pour moins de 1000 particules.

Conclusions

Nous avons présenté un algorithme en temps réel de filtrage particulaire pour l"acquisition 3D des gestes par vision monoscopique. Notre algorithme proposé permet de gérer les ambiguïtés de profondeur dans les images monoculaires en respectant la contrainte du temps réel. Nous avons prouvé que l"amélioration de la robustesse et la précision en temps réel peut être obtenue par l"intégration des différentes stratégies, des heuristiques à faible coût et des heuristiques dans le schème d"un filtrage particulaire. En outre, notre analyse expérimentale a montré que le problème des ambiguïtés des images monoculaires peut être surmonté par forcer les particules à chercher vers la direction incertaine de la profondeur. Toutefois, si l'échantillonnage n'est pas assez dense en raison des limitations en temps réel, une méthode d'optimisation locale et des heuristiques déterministes doivent être mises en oeuvre afin de guider les particules rapidement vers des solutions plus probables. Enfin, la puissance de calcul des futures cartes graphiques nous permettra d'augmenter le nombre de particules et donc, la robustesse et précision dans notre approche.

Chapitre 5 : Conclusions et perspectives

Dans ce travail, nous nous intéressons au problème de l"acquisition 3D des gestes en temps réel par vision monoscopique (avec une webcam). Notre approche consiste à recaler un modèle 3D articulé de la partie supérieure du corps de l'homme sur des séquences vidéo monoculaires. Nous avons proposé de nouvelles méthodes pour améliorer la robustesse et la précision de la pose 3D estimée en partant des travaux antérieurs [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF]. La pose 3D obtenue à chaque image est utilisée pour animer un avatar 3D dans un environnement virtuel collaboratif.

Contributions

Nous avons développé un prototype d"acquisition 3D des gestes par vision monoscopique en temps réel. Notre prototype est divisé en deux grandes étapes: l'initialisation et le suivi. Dans l'étape d'initialisation, de nouveaux algorithmes ont été proposés pour apprendre l'apparence de l'arrière-plan et l'utilisateur ainsi que la morphologie des parties du corps. Dans l'étape de suivi, des nouvelles méthodes sont proposées afin d'améliorer la robustesse et la précision de la pose 3D tout respectant le calcul en temps réel.

La précision est améliorée par un recalage sur les contours après un recalage sur les régions. Les avantages et les inconvénients de chaque étape du recalage sont discutés et comparées expérimentalement avec un nombre limité d'itérations. Dans cette analyse expérimentale, nous avons trouvé un compromis optimal entre la robustesse et la précision par rapport au nombre d'itérations.

Nous avons développé un algorithme de filtrage particulaire hybride qui combine plusieurs heuristiques afin de gérer les ambigüités 3D / 2D avec un nombre faible de particules. L"algorithme proposé intègre un certain nombre d'heuristiques dans l'approche de CONDENSATION [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF] afin de guider les particules vers des solutions plus probables. Nous avons démontré expérimentalement l"amélioration significative de la robustesse et la précision de la pose estimée en utilisant aussi moins que 200 particules dans l'espace de 20 degrés de liberté. Les résultats quantitatifs et qualitatifs sur des séquences vidéo réelles ont montré une amélioration significative pour l"acquisition des gestes complexes comprenant des gestes vers la profondeur, auto-occultations, déplacement de l"acteur et rotations complètes du corps.

Perspectives futures

Les travaux futurs porteront sur l'intégration des autres primitives d"image à notre algorithme de filtrage particulaire proposé afin d'améliorer l"estimation de la pose 3D (par exemple le flux optique, détecteurs des parties du corps). Un autre perspective reposerait sur la réduction de l'espace de grande dimensionnalité des poses 3D dans un espace latente de faible dimension afin d"utiliser moins de particules pour le suivi de la pose.

Une contribution intéressante sera incorporé l"information de profondeur à partir caméras temps de vol (Time of Flight) ou un capteur Kinect (Kinect, 2010) afin d"améliorer l'efficacité de nos algorithmes proposés.

Enfin, d'autres applications futures pourraient être envisagées à notre système d"acquisition des gestes, par exemple une interaction homme-machine basée sur les gestes, des systèmes de vidéo surveillance pour les personnes âgées, l'interaction homme-robot, des interfaces multimodales, etc.

Chapter 1 .

 1 .................................................................................................................................. Introduction ....................................................................................................................................... 1.1 Enhancing the perception of user actions in 3D collaborative virtual environments ................. 1.2 Other potential applications .......................................................................................................

Figure 1 - 1 :

 11 Figure 1-1: Avatars meeting and interacting in a 3D virtual space (OpenSpace3D, 2010) ..................

Figure 1 - 2 :

 12 Figure 1-2: Our target application: 3D motion capture for 3D collaborative virtual environments (MyBlog3D, 2010). ...............................................................................................................................

Figure 2 - 1 :

 21 Figure 2-1: Optical motion capture system. Actor wearing an optical motion capture suit with infrared markers (left). 3D human pose inferred from the relative positions of each marker (right) (PhaseSpace, 2010). ..............................................................................................................................

Figure 2 - 2 :

 22 Figure 2-2: A mechanical exoskeleton suit for motion capture (Gypsy7, 2010)...................................

Figure 2 - 3 :

 23 Figure 2-3 : A performer wearing a suit for magnetic motion capture (AMM, 2010) ..........................

Figure 2 - 4 :

 24  Human silhouettes extracted using a background subtraction algorithm[START_REF] Howe | Silhouette lookup for monocular 3d pose tracking[END_REF]. ..

Figure 2 - 5 :

 25 Figure 2-5 : A human body model represented by a stick figure[START_REF] Mamania | Markerless motion capture from monocular videos[END_REF]. ...................

Figure 2 -

 2 Figure 2-6 : A human body model represented by 2D planar patches[START_REF] Ju | Cardboard People: A Parameterized Model of Articulated Image Motion[END_REF]. ......................

Figure 2 -

 2 Figure 2-7 : A human body model represented by 3D volumes[START_REF] Azad | A full body human motion capture system using particle filtering and on-the-fly edge detection[END_REF] ............................

Figure 2 -

 2 Figure 2-8: A human model represented by super quadric ellipsoids[START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF] ......

Figure 2 -

 2 Figure 2-9: Generative Top Down estimation: 1) Input image, 2) Image feature, 3) Model projected in a candidate pose, 4) Estimation of model parameters by matching model projection and input image features(Sminchisescu, et al., 2002). ....................................................................................................

  Figure 2-9: Generative Top Down estimation: 1) Input image, 2) Image feature, 3) Model projected in a candidate pose, 4) Estimation of model parameters by matching model projection and input image features(Sminchisescu, et al., 2002). ....................................................................................................

Figure 2 -

 2 Figure2-10: 3D human pose reconstructed directly from silhouettes using learned RVM model[START_REF] Agarwal | 3D Human Pose from Silhouettes by Relevance Vector Regression[END_REF]. ..........................................................................................................................

  Figure2-10: 3D human pose reconstructed directly from silhouettes using learned RVM model[START_REF] Agarwal | 3D Human Pose from Silhouettes by Relevance Vector Regression[END_REF]. ..........................................................................................................................

Figure 2 -

 2  Separate clusters of motion activities projected to a PCA subspace[START_REF] Urtasun | Motion Models for Robust 3D Human Body Tracking[END_REF]. .....

Figure 2 -

 2 Figure 2-12: A golf swing motion represented in a 3D latent manifold (Urtasun, 2006). ....................

Figure 2 -

 2 Figure 2-13: The general strategy of our approach for 3D motion capture ...........................................

Figure 2 -

 2 Figure 2-14: The skeleton design of our 3D upper-body model based on the H-Anim 1.1 standard. ...

Figure 2 -

 2 Figure 2-15: Our 3D body model formed by polygon meshes showing the initial 3D pose. ................

Figure 2 -

 2 Figure 2-16: Our 3D upper-body model projected showing a 3D pose. ...............................................

Figure 2 -

 2 Figure 2-17: Obtaining color samples using the face detector in the first image captured. ..................

Figure 2 -

 2 Figure 2-18: Segmenting regions from input image. The images are respectively: the captured image and the image segmented in three regions (arms, clothes and head). ....................................................

Figure 2 -

 2 Figure 2-19: Rendering the 3D model: The left image is the generated 3D model pose and the right image is the model projection with the body segments flat-rendered according to their three color labels (arms, head and clothes). .............................................................................................................

Figure

   Evaluating the match between the regions. The non-overlapping ratio F(q) is obtained from the overlap between the segmented image and the model projection in a candidate 3D pose. ....

Figure 2 -

 2 Figure 2-21: Downhill simplex steps. (a) the simplex at the beginning of the step, (b) reflection, (c) expansion, (d) one dimensional contraction, (e) multiple contraction toward the lowest point. ...........

Figure 2 -

 2  The effect of increasing or reducing the initial size of the simplex in our registration process until convergence. The abscissa is the frame number in the video sequence. The black line is the residual error of the non-overlapping ratio using a relatively large size of simplex (factor = 3.0). The gray line gives the corresponding residual error using a relatively small simplex (factor = 0.5). Finally, the dash gray line use a medium-sized simplex (factor=1.5), which provides smaller residual errors in our registration process. ..........................................................................................................

   The effect of increasing or reducing the initial size of the simplex in our registration process until convergence. The abscissa is the frame number in the video sequence. The black line is the residual error of the non-overlapping ratio using a relatively large size of simplex (factor = 3.0). The gray line gives the corresponding residual error using a relatively small simplex (factor = 0.5). Finally, the dash gray line use a medium-sized simplex (factor=1.5), which provides smaller residual errors in our registration process. ..........................................................................................................

Figure 2 -

 2 Figure 2-23: Region-based registration until convergence, using different sizes of initial simplex. First row: the input images of a video sequence. Second row: segmented regions from input images. Third row: motion tracking results (projected model) using a small initial simplex (factor = 0.5). Fourth row: motion tracking with a large initial simplex (factor = 3.0). Fifth row: motion tracking using a medium size simplex (factor = 1.5). A medium size simplex provides better tracking results because the local search space respects more closely the temporal coherence of the motion. ..........................................

Figure 3 - 1 :

 31 Figure 3-1: Initialization modules of our 3D motion capture system ....................................................

Figure 3 - 2 :

 32 Figure 3-2: Real-time modules of our 3D motion capture system ........................................................

Figure 3 - 3 :

 33 Figure 3-3: Calibrating and initializing our 3D model with respect to the actor in the first input image. ...............................................................................................................................................................

Figure 3 - 4 :

 34 Figure 3-4: Automatic model calibration: (a) segmented silhouette, (b) initial model translation, c) model aligned with the head, d) model aligned in depth direction, e) pose alignment and f) shape adjustment. ............................................................................................................................................

Figure 3 - 5 :

 35 Figure 3-5: Diagram of the proposed background subtraction algorithm .............................................

Figure 3 - 6 :

 36  An example of background subtraction in the case of a sunlight variation. From left to right: the reference background image; the input image respectively before (upper row) and after the illumination change; the foreground extracted respectively before and after the illumination change using naïve direct RGB comparison, then the GMM-based approach and finally our algorithm. ........

Figure 3 -

 3  The limited accuracy of region-based registration. The images are respectively: the captured image, the segmented image and the projection of the registered 3D human body model after

Figure 3 - 8 :

 38 Figure 3-8: Computing a distance map from captured images: The images are respectively: the captured image, the foreground silhouette, the edges extracted inside the silhouette and the edge distance map. .........................................................................................................................................

Figure 3 - 9 :

 39 Figure 3-9: Extracting occluding edges. Left: the 3D model is rendered with some foreground color (first step). Right: the inside of frontwards triangles is rendered with the background color and with backwards culling (second step). ...........................................................................................................

Figure 3 -

 3 Figure 3-10: Evaluating the match between edges. The mean distance between edges (D C ) is obtained by masking the distance map from the image with the occluding edges of the 3D model in a candidate 3D pose. .................................................................................................................................................

Figure 3 -

 3 Figure 3-11: Improving the registration accuracy by edge-based registration. The images in each column are respectively: the input image, the 3D pose estimated by the region-based registration step, and the 3D pose estimation improved by the edge-based registration step. In the second and third columns, the occluding edges of the 3D model are superposed on the input image. In the last column we observe that the distances to the limb edges are reduced, providing more accurate pose estimation. ...............................................................................................................................................................

Figure 3 -

 3 Figure 3-12: Edge-based registration after reducing the search space to the simplex output by the region-based registration. In each row, the images are respectively: the captured image; the edges extracted from the image; the edge-based registration result when using a large fixed initial simplex; and the edge-based registration result when using the final simplex of the region-based step. ............

  Figure 3-14: The effect of limiting the number of iterations on the residual error (ordinates) of our edge-based registration step. The abscissa is the frame number in the video sequence. The black line is the mean edge distance minimized to convergence by the edge-based registration while the gray line is limited to 500 iterations. The example images show that the occluding edges of the 3D model are matched when the optimizer is near to convergence. ............................................................................

Figure 3 -

 3 Figure 3-15: The video sequences used in our experiments. The video sequences 1 (top left), 2 (top center), 3 (top right), 4 (bottom left), 5 (bottom center) and 6 (bottom right) contain respectively 290, 1497, 1412, 887, 1032 and 551 frames. The first three sequences include various types of gestures. Sequence 4 includes principally gestures when arms are crossing each other. In sequence 5, the person is not directly facing the camera. The sequence 6 includes movements in which the person is turning from side to side. ...................................................................................................................................

Figure

   The mean residual error of the non-overlapping ratio (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and of the edge-based registration (y-axis) on video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results. ...............

Figure 3 -

 3 Figure 3-20: Raising arms gesture. This gesture mostly involves fronto-parallel motions with no-self body occlusions. There is little relative motion in depth. Sample images from the video sequence are shown in the first row. The second row shows a top down view of the same 3D. ................................

Figure 3 -

 3  Joy gesture. This sequence contains relative motion in depth with some partial selfocclusions (second image). Relatively fast motion is present between the third and fourth images. ...

Figure 3 -

 3 Figure 3-22: Exclaiming gesture. More relative motion in depth is involved with upper-arm self occlusions (second image). Partial rotations of both arms are presented between the second and fourth images....................................................................................................................................................

Figure 3 -

 3 Figure 3-23: Asking gesture. Forward/backward motion in depth is significant in this gesture. Fast movement is present between the second and fourth images. ...............................................................

Figure 3 -

 3 Figure 3-24: The residual 3D error achieved by each registration step in joy gesture video sequence. The black line is the residual error (in mm) obtained by running region-based registration to convergence. The gray line is the residual error obtained by running edge-based registration to convergence. The abscissa is the frame number in the video sequence. Overall, edge-based registration is more accurate than region-based registration. The visual example shows how the 3D accuracy is limited by the depth ambiguity of monocular images. In this example, an incorrect 3D pose (lower row right side) gives a 2D projection (top row right side) that correspond approximately to the 3D pose of the synthesized video sequence (top row left side) without corresponding to the real 3D configuration (lower row left side) ..............................................................................................................................

Figure 3 -

 3 Figure 3-25: Comparative 3D accuracy for method limited to 500 iterations in total. The black line shows the residual error (mm) after 500 iterations of the region-based registration while the gray line shows the error after 500 iterations of the edge-based registration. The dashed line is the error obtained when the first 250 iterations are allocated to the region-based step and the remaining 250 iterations to edge-based registration. Sharing the number of iterations between the two registration steps provides more accurate pose estimates. ...............................................................................................................

Figure

   The mean residual 3D error in millimeters (z-axis) on the video sequence with respect to the numbers of iterations of the region-based registration (x-axis) and edge-based registration (y-axis). The surfaces correspond to the video sequences "raising arms gesture" (a), "joy gesture" (b), "exclaiming gesture" (c) and "asking gesture" (d). ...............................................................................

  Figure 3-27: Graphs of the mean residual 2D error in millimeters (z-axis) for each video sequence, with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis). The plots correspond to the video sequences "raising arms gesture" (a), "joy gesture" (b), "exclaiming gesture" (c) and "asking gesture" (d). The residual 2D error decreases with the number of iterations for each sequence. ..........................................................................................

Figure 3 -

 3 Figure 3-28: A quadratic polynomial fit to the mean residual 2D error (z-axis) with respect to the number of region-based (x-axis) and edge-based (y-axis) iterations. The left image shows the polynomial surface. The right image is the same surface from a top view. The highest residual 2D errors are in the red regions, the lowest ones in the blue regions. .........................................................

Figure 3 -

 3 Figure 3-29: Finding the optimal numbers of iterations for a constant computation time. The optimal number of iterations is the point of the residual error curve (blue curve) that is tangent to the straight line of constant computation time ρ with angle θ. ....................................................................

Figure 3 -

 3 Figure 3-30: The optimal curve for the numbers of iterations allocated to each registration step for the best accuracy in real-time. The abscissa is the number of iterations for region-based registration and the ordinate is the number for edge-based registration. The optimal curve (black line) is superposed on the mean residual 2D error surface computed from multiple video sequences. ....................................

Figure 4 - 1 :

 41 Figure 4-1: Monocular observation ambiguities: a) the input image, b) the segmented image, c) a model projection that matches the segmented image, (d) and (e) are different 3D poses that both match the segmented image as they give the same model projection in (c). ...................................................

Figure 4 - 2 :

 42 Figure 4-2: A video sequence showing motion in depth tracked with local optimization method. The images in each row are respectively: the input image, the segmented image, the projection of the 3D model after region-matching with local optimization (region-based registration), and a top-down view of the 3D model showing the incorrect 3D pose. Local optimization failed to correctly track motions in the depth direction. ................................................................................................................................

Figure 4 - 3 :

 43  A weighted set of particles representing the true posterior density. The abscissa axis corresponds to the particle space . The particles are represented as circles which size is the likelihood of[START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF].................................................................................................

   A weighted set of particles representing the true posterior density. The abscissa axis corresponds to the particle space . The particles are represented as circles which size is the likelihood of[START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF].................................................................................................

Figure 4 - 4 :

 44  One time-step of the CONDENSATION algorithm[START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Each circle represents a particle which size correspond to its weight. Particles are propagated in time by three steps: resampling, prediction and measurement. ...................................................................................

   One time-step of the CONDENSATION algorithm[START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Each circle represents a particle which size correspond to its weight. Particles are propagated in time by three steps: resampling, prediction and measurement. ...................................................................................

Figure 4 - 5 :

 45  Annealed particle filtering using 3 layers. Particles (circles) migrate gradually toward the global maximum by sharpening the posterior (curves) at each layer m[START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF]. .......

Figure 4 - 6 :Figure 4 Figure 4 - 8 :Figure 4 - 9 :Figure 4 -Figure 4 -Figure 4 -Figure 4 -Figure 4 -Figure 4 -Figure 4 -Figure 4 -

 464484944444444 Figure 4-6: Deterministic sampling. Particles are updated and replaced by neighbor particles that sample possible states in a neighborhood around the current particles . ............................................. 100

Figure 4 -

 4 Figure 4-18: Computing ambiguous 3D joint configurations. a) A general design of a kinematic arm sub chain of our 3D model. b) Imaginary 3D sphere centered in shoulder joint (Sw) traversed by the camera ray of sight to find a new alternative 3D point (Ew") that gives the same projection (Ep). c) Building kinematic tree to find alternative joint configurations (K", K"", K""") that corresponds to the same set of projected joints in the 2D image plane. ............................................................................

Figure 4 -

 4 Figure 4-19: Two 3D poses computed analytically that give the same model projection in the 2D image plane (first row) but which corresponds to different skeleton configurations (second row). Both 3D configurations are kinematically valid since they respect our biomechanical constraints. ...........

Figure 4 -

 4  showing the accuracy contribution of kinematic-flipping-based sampling (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence. Accuracy is not necessarily improved because lowest-weight particles are replaced by alternative kinematic-flipping samples. Therefore particles are less scattered in the pose space. ......

Figure 4 -

 4 Figure 4-21: Experimental results showing the robustness contribution of kinematic-flipping based sampling (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates is the number of mistrackings obtained for all frames of the video sequence. .............................................................................................................................................................

Figure 4 -

 4  Recovering from monocular 3D/2D ambiguities using kinematic-flipping based sampling. The first row contains sequential sample images from video sequence "joy gesture". The second row is the model projection of the 3D pose estimated (highest weight particle) using Condensation algorithm with kinematic-flipping. Third row shows a top-view of the images in first row. The last row is a top-view of the images in second row. The last row shows how kinematicflipping allows tracking recovers rapidly from a "wrong" 3D pose configuration to a "good" pose configuration. Note that all 3D pose configurations in the last row give similar 2D projections (second row). ....................................................................................................................................................

Figure 4 -

 4 Figure 4-23: End-effector used as state pose parameters to estimate motion in depth. End-effector positions are shown as red circles. Particles end-effector states are diffused randomly around each endeffector according to a variance explicitly defined (red dashed circle) to search along depth direction (z-axis). ................................................................................................................................................

Figure 4 -

 4 Figure 4-24: The elbow E K is on a circle orthogonal to the line from shoulder S K to wrist W K . Its position is defined by the swivel angle Φ around that line. ................................................................

Figure 4 -

 4 Figure 4-25: Experimental results showing the accuracy contribution of our solution based in endeffector space (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence. .............................................................................................................

Figure 4 -

 4 Figure 4-26: Experimental results showing the robustness contribution of our solution based in endeffector space (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates is the number of mistrackings obtained for all frames of the video sequence. .............................................................................................................................................

Figure 4 -

 4 Figure 4-27: Evaluation of particles is parallelized on GPU. Non-overlapping ratio F(q) is parallelized for many particles by computing the histogram of the image resulted by adding the segmented image buffer to the rendered buffer of the 3D model projections. Each model projection in the rendered buffer describes a different particle state . .................................................................................

Figure 4 -

 4 Figure 4-28: The steps of our real-time particle filtering with heuristics algorithm. Particles are guided toward the peaks of the posterior by combining the heuristics proposed. Evaluation of particles is parallelized on GPU according to color and edges observations. .......................................................

Figure 4 -

 4 Figure 4-29: Comparative results showing the residual 3D accuracy error achieved by our proposed particle filter algorithm that combines all heuristics (gray line) and the CONDENSATION algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.................................................................

Figure 4 -

 4 Figure 4-30: Comparative results showing the residual 3D accuracy error achieved by our proposed particle filter algorithm that combines all heuristics (gray line) and the CONDENSATION algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.................................................................

Figure 4 -

 4 Figure 4-31: Video sequence showing motion in depth tracked with our real-time particle filter with heuristics algorithm. The images in each row are respectively: the input image, the segmented image, the projection of the 3D pose described by the highest weight particle, and the top-view of the 3D model showing a coherent 3D pose. Our proposed algorithm is able to track motion in depth from 2D image observations more efficiently than local optimization in figure 4-2. ........................................

Figure 4 -

 4  Monocular video sequences tracked in our performance experiments. The video sequence 1 (first row) contains pointing gestures with relative motion in depth and fast motions. The video sequence 2 (second row) contains mostly gestures with partial body occlusions. In the video sequence 3 (third row), the actor is turning around himself. In the video sequence 4 (forth row), the actor is not facing directly the camera. In video sequence 5 (fifth row), the actor is moving in the scene while making fast and relative depth motions. The video sequence 6 (sixth row) includes gestures in which the actor is moving in the scene and not facing directly to the camera. The first three video sequence last around 2 or 3 minutes while the sequences 5 and 6 (video lectures) last around 5 minutes. ........

Figure 4 -

 4 Figure 4-33: Experimental results showing the gain of robustness for each video sequence obtained by our real-time particle filter with heuristics algorithm (dashed gray line) with respect to the Condensation algorithm (black line). The abscissas are the number of particles and ordinates are the number of mistrackings obtained for each sequence. ..........................................................................

Figure 4 -

 4 Figure 4-34: Qualitative visual results on video sequence 1. Gestures are acquired with our Real-Time Particle Filter with Heuristics method proposed (700 particles were used). Joint angle pose parameters (in MPEG-4 BAP format) are sent to the 3D avatar in real-time. .......................................................

Figure 4 -

 4 Figure 4-35: Qualitative visual results on video sequence 4. Gestures are acquired with our Real-Time Particle Filter with Heuristics method proposed (700 particles were used). Joint angle pose parameters (in MPEG-4 BAP format) are sent to the 3D avatar in real-time. .......................................................

Figure 4 -

 4 Figure 4-36: Qualitative visual results on video sequence 5. Gestures are acquired with our Real-Time Particle Filter with Heuristics method proposed (700 particles were used). Joint angle pose parameters (in MPEG-4 BAP format) are sent to the 3D avatar in real-time. .......................................................

Figure 2 - 1 :

 21 Figure 2-1: Optical motion capture system. Actor wearing an optical motion capture suit with infrared markers (left). 3D human pose inferred from the relative positions of each marker (right) (PhaseSpace, 2010).

Figure 2 - 2 :

 22 Figure 2-2: A mechanical exoskeleton suit for motion capture (Gypsy7, 2010).

Figure 2 - 3 :

 23 Figure 2-3 : A performer wearing a suit for magnetic motion capture (AMM, 2010)

  -7).[START_REF] Deutscher | Articulated Body Motion Capture by Stochastic Search. s.l[END_REF] use a full body model that consists of 17 segments and 29 degrees of freedom. Each segment is fleshed out by cones with elliptical cross-section. The author argues that such models have many advantages including computational simplicity and compact representation. Several works have adopted similar models.Saboune et al. (2007) use a model formed by 19 joints that represent key elements of the human body (head, elbows, knees, arms, etc.), each segment is fleshed out by adding cube volumes around it.[START_REF] Azad | A full body human motion capture system using particle filtering and on-the-fly edge detection[END_REF] use a model with 28 degrees of freedom, where each body part is modeled as a section of a cone. Each cone is described by two ellipses (base ellipse and upper ellipse) and the length between these ellipses.[START_REF] Noriega | Multicues 3D Monocular Upper Body Tracking using Constrained Belief Propagation[END_REF] combine 2D patches and 3D volumes to represent an upper body model. Arms and forearms are modeled as cylinders and the head as a sphere. The torso, hands and clavicles are represented by 2D planar patches. Limb interactions are described in terms of distances between the body parts.

Figure 2 -

 2 Figure 2-7 : A human body model represented by 3D volumes[START_REF] Azad | A full body human motion capture system using particle filtering and on-the-fly edge detection[END_REF]

Figure 2 -

 2 Figure 2-8: A human model represented by super quadric ellipsoids[START_REF] Sminchisescu | Covariance Scaled Sampling for Monocular 3D Body Tracking[END_REF]

Figure 2 -

 2 Figure 2-9: Generative Top Down estimation: 1) Input image, 2) Image feature, 3) Model projected in a candidate pose, 4) Estimation of model parameters by matching model projection and input image features(Sminchisescu, et al., 2002).

Figure 2 -

 2 Figure 2-11: Separate clusters of motion activities projected to a PCA subspace[START_REF] Urtasun | Motion Models for Robust 3D Human Body Tracking[END_REF].

Figure 2 -

 2 Figure 2-14 shows the kinematic tree of our model, which contains the 20 articulation angles belonging to the upper-body. In terms of Euler angles, these joint angles correspond to:  3 rotations for the humanoid root (torsion, roll, tilt).  3 rotations for the left wrist (flexion, pivot, twisting).  3 rotations for the right wrist (flexion, pivot, twisting).  1 rotation for the left elbow (flexion).  1 rotation for the right elbow (flexion).  3 rotations for the left shoulder (flexion, abduct, twisting).  3 rotations for the right shoulder (flexion, abduct, twisting).  3 rotations for the neck (roll, torsion, tilt).

Figure 2 -

 2 Figure 2-14: The skeleton design of our 3D upper-body model based on the H-Anim 1.1 standard.

  1) establish the maximum and minimum rotation angles permissible for each joint starting from the initial pose (Figure 2-15).

Figure 2 -

 2 Figure 2-15: Our 3D body model formed by polygon meshes showing the initial 3D pose.

Figure 2 -

 2 Figure 2-17: Obtaining color samples using the face detector in the first image captured.

Figure 2 -

 2 Figure 2-18: Segmenting regions from input image. The images are respectively: the captured image and the image segmented in three regions (arms, clothes and head).

Figure 2 -

 2 Figure 2-19: Rendering the 3D model: The left image is the generated 3D model pose and the right image is the model projection with the body segments flat-rendered according to their three color labels (arms, head and clothes).

Figure 2 -

 2  Evaluating the match between the regions. The non-overlapping ratio F(q) is obtained from the overlap between the segmented image and the model projection in a candidate 3D pose.

Figure 2 -

 2 Figure 2-21: Downhill simplex steps. (a) the simplex at the beginning of the step, (b) reflection, (c) expansion, (d) one dimensional contraction, (e) multiple contraction toward the lowest point.

Figure 2 -

 2 Figure 2-23: Region-based registration until convergence, using different sizes of initial simplex. First row: the input images of a video sequence. Second row: segmented regions from input images. Third row: motion tracking results (projected model) using a small initial simplex (factor = 0.5). Fourth row: motion tracking with a large initial simplex (factor = 3.0). Fifth row: motion tracking using a medium size simplex (factor = 1.5). A medium size simplex provides better tracking results because the local search space respects more closely the temporal coherence of the motion.

  4.1).  Skin and clothes color learning: skin and clothes colors samples from the human are captured from the image to generate a statistical Gaussian model for each color class (section 2.4.4.1).  3D human body model calibration: the sizes of the model limbs are adjusted to fit the human in the image (section 3.3).

Figure 3 - 1 :

 31 Figure 3-1: Initialization modules of our 3D motion capture system

Figure 3 - 3 :

 33 Figure 3-3: Calibrating and initializing our 3D model with respect to the actor in the first input image.

Figure 3 - 4 :

 34 Figure 3-4: Automatic model calibration: (a) segmented silhouette, (b) initial model translation, c) model aligned with the head, d) model aligned in depth direction, e) pose alignment and f) shape adjustment.

  to (3.7) we obtain the normal law describing the orientations of gradients and chrominance vectors C at each pixel s of the background model. Thus the probabilities that a pixel with gradient orientation and chrominance vector C belongs to the background model b are defined by the following Gaussian probability density functions:

Figure 3 - 5 :

 35 Figure 3-5: Diagram of the proposed background subtraction algorithm

Figure 3 - 1 :Figure 3 -

 313 Figure 3-6: An example of background subtraction in the case of a sunlight variation. From left to right: the reference background image; the input image respectively before (upper row) and after the illumination change; the foreground extracted respectively before and after the illumination change using naïve direct RGB comparison, then the GMM-based approach and finally our algorithm.

Figure 3 -

 3 Figure 3-7: The limited accuracy of region-based registration. The images are respectively: the captured image, the segmented image and the projection of the registered 3D human body model after optimization. The pose of the 3D model differs from the pose of the actor because the region-based registration is not accurate.

Figure 3 -

 3 Figure 3-8: Computing a distance map from captured images: The images are respectively: the captured image, the foreground silhouette, the edges extracted inside the silhouette and the edge distance map.

Figure 3 -

 3 Figure 3-9: Extracting occluding edges. Left: the 3D model is rendered with some foreground color (first step). Right: the inside of frontwards triangles is rendered with the background color and with backwards culling (second step).

Figure 3 -

 3 Figure 3-10: Evaluating the match between edges. The mean distance between edges (D C ) is obtained by masking the distance map from the image with the occluding edges of the 3D model in a candidate 3D pose.

Figure 3 -

 3 Figure 3-11: Improving the registration accuracy by edge-based registration. The images in each column are respectively: the input image, the 3D pose estimated by the region-based registration step, and the 3D pose estimation improved by the edge-based registration step. In the second and third columns, the occluding edges of the 3D model are superposed on the input image. In the last column we observe that the distances to the limb edges are reduced, providing more accurate pose estimation.

Figure 3 -

 3 12 shows the results. By examining the last column of this figure, we can see how the edge-based registration achieves more accurate 3D pose estimation by matching the correct edges of the body limbs.

Figure 3 -

 3 Figure 3-12: Edge-based registration after reducing the search space to the simplex output by the region-based registration. In each row, the images are respectively: the captured image; the edges extracted from the image; the edge-based registration result when using a large fixed initial simplex; and the edge-based registration result when using the final simplex of the region-based step.

Figure 3 -

 3  The effect of limiting the number of iterations on the residual error (ordinates) of our edge-based registration step. The abscissa is the frame number in the video sequence. The black line is the mean edge distance minimized to convergence by the edge-based registration while the gray line is limited to 500 iterations. The example images show that the occluding edges of the 3D model are matched when the optimizer is near to convergence.

Figure 3 -

 3 Figure 3-15: The video sequences used in our experiments. The video sequences 1 (top left), 2 (top center), 3 (top right), 4 (bottom left), 5 (bottom center) and 6 (bottom right) contain respectively 290, 1497, 1412, 887, 1032 and 551 frames. The first three sequences include various types of gestures. Sequence 4 includes principally gestures when arms are crossing each other. In sequence 5, the person is not directly facing the camera. The sequence 6 includes movements in which the person is turning from side to side.

Figure 3 -

 3 Figure 3-16: The mean residual error of the non-overlapping ratio (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and of the edge-based registration (y-axis) on video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results.

Figure 3 -

 3 Figure 3-17: The mean residual error of the mean edge distance (z-axis) with respect to the number of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis), on video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results.

Figure 3 -

 3  The number of mistrackings for the non-overlapping ratio (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis), on the video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results.

Figure 3 -

 3 Figure 3-19: The number of mistrackings for mean edge distance (z-axis) with respect to the numbers of iterations of the region-based registration (x-axis) and the edge-based registration (y-axis), on the video sequence 2. Experiments on video sequences 1, 3, 4, 5 and 6 showed similar results.

Figure 3 -

 3 20 to show the video sequences used in our experimental analysis. Each video sequence contains 165 frames. In each figure, the first row contains sample 2D images from the video sequence that is tracked by our proposed algorithms while the second row shows a top-down view to illustrate the degree of motion in depth present in the gesture.

Figure 3 -

 3 Figure 3-20: Raising arms gesture. This gesture mostly involves fronto-parallel motions with no-self body occlusions. There is little relative motion in depth. Sample images from the video sequence are shown in the first row. The second row shows a top down view of the same 3D.

Figure 3 -

 3 Figure 3-21: Joy gesture. This sequence contains relative motion in depth with some partial self-occlusions (second image). Relatively fast motion is present between the third and fourth images.

Figure 3 -

 3 Figure 3-22: Exclaiming gesture. More relative motion in depth is involved with upper-arm self occlusions (second image). Partial rotations of both arms are presented between the second and fourth images.

Figure 3 -

 3 Figure 3-23: Asking gesture. Forward/backward motion in depth is significant in this gesture.Fast movement is present between the second and fourth images.

Figure 3 -

 3 Figure 3-24: The residual 3D error achieved by each registration step in joy gesture video sequence. The black line is the residual error (in mm) obtained by running region-based registration to convergence. The gray line is the residual error obtained by running edge-based registration to convergence. The abscissa is the frame number in the video sequence. Overall, edge-based registration is more accurate than region-based registration. The visual example shows how the 3D accuracy is limited by the depth ambiguity of monocular images. In this example, an incorrect 3D pose (lower row right side) gives a 2D projection (top row right side) that correspond approximately to the 3D pose of the synthesized video sequence (top row left side) without corresponding to the real 3D configuration (lower row left side)

Figure 3 -

 3 Figure 3-25: Comparative 3D accuracy for method limited to 500 iterations in total. The black line shows the residual error (mm) after 500 iterations of the region-based registration while the gray line shows the error after 500 iterations of the edge-based registration. The dashed line is the error obtained when the first 250 iterations are allocated to the region-based step and the remaining 250 iterations to edge-based registration. Sharing the number of iterations between the two registration steps provides more accurate pose estimates.

  -20, and, fitted a quadratic polynomial by regression using least squares method[START_REF] Phillips | ZunZun.com Online Curve Fitting and Surface Fitting Web Site[END_REF]:(3.19) where A, B, C, D, F, and G are the regression coefficients of the polynomial function, and are the numbers of iterations respectively in region-based and edge-based registrations, and is the mean residual 2D error. In this way, we get a polynomial model that describes the average behavior of the 3D surfaces (Figure3-28).

Figure 3 -

 3 Figure 3-28: A quadratic polynomial fit to the mean residual 2D error (z-axis) with respect to the number of region-based (x-axis) and edge-based (y-axis) iterations. The left image shows the polynomial surface. The right image is the same surface from a top view. The highest residual 2D errors are in the red regions, the lowest ones in the blue regions.

  -1), choosing the wrong pose often traps the registration process in some incorrect local minimum (Figure4-2).

Figure 4 - 1 :

 41 Figure 4-1: Monocular observation ambiguities: a) the input image, b) the segmented image, c) a model projection that matches the segmented image, (d) and (e) are different 3D poses that both match the segmented image as they give the same model projection in (c).

  that describes the transition between sequential states with a noise term . At each time , the hidden state produces a new observation . is a possibly non-linear transition function with non-Gaussian noise .

Figure 4 - 4 :

 44 Figure 4-4: One time-step of the CONDENSATION algorithm[START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF]. Each circle represents a particle which size correspond to its weight. Particles are propagated in time by three steps: resampling, prediction and measurement.

  state and its associated weight at a time step t and layer m. For each particle , the weight is assigned with the observation likelihood . After the weights are computed in a layer m, particles are resampled from with replacement with a probability equal to their weight . Then, a new set is generated with random Gaussian noise with zero mean and a covariance decreasing at each time step t. The set is used to initialize layer . The process is repeated until arriving to the set where we can find the optimal configuration by computing the posterior mean. Finally, a new set is generated (using random Gaussian noise) from the final layer set . The new set is used to initialize layer M of the next time step . In the next figure, a diagram shows a set of particles migrating gradually toward the global maximum of the posterior in a multi-layered search.

Figure 4 - 5 :

 45 Figure 4-5: Annealed particle filtering using 3 layers. Particles (circles) migrate gradually toward the global maximum by sharpening the posterior (curves) at each layer m[START_REF] Deutscher | Articulated body motion capture by annealed particle filtering. s.l[END_REF].

Figure 4 -

 4 Figure 4-6: Deterministic sampling. Particles are updated and replaced by neighbor particles that sample possible states in a neighborhood around the current particles .

Figure 4 -

 4 Figure 4-7: A particle state represents a candidate 3D pose in our particle filter framework.

Figure 4 -

 4 Figure 4-10: Weight-based deterministic resampling. Parent particles (gray circles) give birth to a number of children particles (white circles) proportional to their weights (size of particle).A child of the highest weight parent particle will not be diffused randomly in the prediction step in order to avoid losing the currently best estimation in case of sample depletion.

Figure 4 -

 4 Figure 4-11: Experimental results showing the accuracy contribution of weight-based deterministic (WD) resampling (dashed gray line) w.r. to classical particle filtering (black line). The abscissas are the number of particles employed. Ordinates show the mean residual 3D error (in millimeters) on the video sequence.

Figure 4 -

 4 Figure 4-12: Experimental results showing the robustness contribution of weight-based deterministic (WD) resampling (dashed gray line) to the particle filtering algorithm (black line). The abscissas are the number of particles employed in each experiment. Ordinates show the number of mistrackings obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-13: Experimental results showing the accuracy contribution of Hierarchical Partitioned Motion-based (HPM) sampling (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-14: Experimental results showing the robustness contribution of Hierarchical Partitioned Motion-based sampling (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates is the number of mistrackings obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-15: A diagram showing our prediction with local optimization heuristic and random diffusion. Large group of particles (circles) are sent to the peaks of posterior density (curve) through downhill simplex optimization. Small group of particles are randomly diffused in the high-dimensional space.

Figure 4 -

 4 Figure 4-16: Experimental results showing the accuracy contribution of the proposed local optimization (dashed gray line) with respect to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.

Figure 4 -

 4  showing the robustness contribution of the proposed local optimization (dashed gray line) with respect to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates is the number of mistrackings obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-18: Computing ambiguous 3D joint configurations. a) A general design of a kinematic arm sub chain of our 3D model. b) Imaginary 3D sphere centered in shoulder joint (Sw) traversed by the camera ray of sight to find a new alternative 3D point (Ew") that gives the same projection (Ep). c) Building kinematic tree to find alternative joint configurations (K", K"", K""") that corresponds to the same set of projected joints in the 2D image plane.

Figure 4 -

 4 Figure 4-19: Two 3D poses computed analytically that give the same model projection in the 2D image plane (first row) but which corresponds to different skeleton configurations (second row). Both 3D configurations are kinematically valid since they respect our biomechanical constraints.

Figure 4 -

 4 Figure 4-20: Experimental results showing the accuracy contribution of kinematic-flippingbased sampling (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence. Accuracy is not necessarily improved because lowest-weight particles are replaced by alternative kinematic-flipping samples. Therefore particles are less scattered in the pose space.

Figure 4 -

 4 Figure 4-21: Experimental results showing the robustness contribution of kinematic-flipping based sampling (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates is the number of mistrackings obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-22: Recovering from monocular 3D/2D ambiguities using kinematic-flipping based sampling. The first row contains sequential sample images from video sequence "joy gesture". The second row is the model projection of the 3D pose estimated (highest weight particle) using Condensation algorithm with kinematic-flipping. Third row shows a top-view of the images in first row. The last row is a top-view of the images in second row. The last row shows how kinematic-flipping allows tracking recovers rapidly from a "wrong" 3D pose configuration to a "good" pose configuration. Note that all 3D pose configurations in the last row give similar 2D projections (second row).

Figure 4 -

 4 Figure 4-23: End-effector used as state pose parameters to estimate motion in depth. Endeffector positions are shown as red circles. Particles end-effector states are diffused randomly around each end-effector according to a variance explicitly defined (red dashed circle) to search along depth direction (z-axis).

Figure 4 -

 4 Figure 4-25: Experimental results showing the accuracy contribution of our solution based in end-effector space (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.

Figure 4 -

 4  showing the robustness contribution of our solution based in end-effector space (dashed gray line) to the particle filter algorithm (black line). The abscissas are the number of particles and ordinates is the number of mistrackings obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-27: Evaluation of particles is parallelized on GPU. Non-overlapping ratio F(q) is parallelized for many particles by computing the histogram of the image resulted by adding the segmented image buffer to the rendered buffer of the 3D model projections. Each model projection in the rendered buffer describes a different particle state .

Figure 4 -

 4 Figure 4-29: Comparative results showing the residual 3D accuracy error achieved by our proposed particle filter algorithm that combines all heuristics (gray line) and the CONDENSATION algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-30: Comparative results showing the residual 3D accuracy error achieved by our proposed particle filter algorithm that combines all heuristics (gray line) and the CONDENSATION algorithm (black line). The abscissas are the number of particles and ordinates are the mean residual 3D error (in millimeters) obtained for all frames of the video sequence.

Figure 4 -

 4 Figure 4-31: Video sequence showing motion in depth tracked with our real-time particle filter with heuristics algorithm. The images in each row are respectively: the input image, the segmented image, the projection of the 3D pose described by the highest weight particle, and the top-view of the 3D model showing a coherent 3D pose. Our proposed algorithm is able to track motion in depth from 2D image observations more efficiently than local optimization in figure 4-2.

Figure 4 -

 4 Figure 4-32 presents the video sequences we used for experiments. The first three video sequences (top three rows) are specific gestures and poses intentionally made by an actor to evaluate the tracking performance. The forth sequence (forth row) contains communicative gestures of a candidate person in a job interview and finally, the last two video sequences (five and six row) are gestures from video lectures from Institut Télécom/Télécom SudParis (SudParis, 2011).

Figure 4 -

 4 Figure 4-32: Monocular video sequences tracked in our performance experiments. The video sequence 1 (first row) contains pointing gestures with relative motion in depth and fast motions. The video sequence 2 (second row) contains mostly gestures with partial body occlusions.In the video sequence 3 (third row), the actor is turning around himself. In the video sequence 4 (forth row), the actor is not facing directly the camera. In video sequence 5 (fifth row), the actor is moving in the scene while making fast and relative depth motions. The video sequence 6 (sixth row) includes gestures in which the actor is moving in the scene and not facing directly to the camera. The first three video sequence last around 2 or 3 minutes while the sequences 5 and 6 (video lectures) last around 5 minutes.

Figure 4 -

 4 Figure 4-34: Qualitative visual results on video sequence 1. Gestures are acquired with our Real-Time Particle Filter with Heuristics method proposed (700 particles were used). Joint angle pose parameters (in MPEG-4 BAP format) are sent to the 3D avatar in real-time.

Figure 4 -

 4 Figure 4-35: Qualitative visual results on video sequence 4. Gestures are acquired with our Real-Time Particle Filter with Heuristics method proposed (700 particles were used). Joint angle pose parameters (in MPEG-4 BAP format) are sent to the 3D avatar in real-time.

Figure 4 -

 4 Figure 4-36: Qualitative visual results on video sequence 5. Gestures are acquired with our Real-Time Particle Filter with Heuristics method proposed (700 particles were used). Joint angle pose parameters (in MPEG-4 BAP format) are sent to the 3D avatar in real-time.

  moyenne (en millimètres) entre la projection 2D des joints d"articulations (les poignets et les coudes) de la pose estimée et les articulations projetées de vérité terrain.est la coordonnée 2D du joint d"articulation m de la pose estimée et est la coordonnée du joint d"articulation m de la vérité terrain.

Table 2 -

 2 1: The biomechanical constraints applied to each joint angle of our 3D model ......................

Table 2 -

 2 2:The BAP parameters sent by our motion capture system to animate a 3D avatar. ..............

Table 3 -

 3

1: The computation time of each background subtraction algorithm. Image size: 160x120 ...

Table 3 -

 3 2: Computation time in milliseconds (average and standard deviation) with respect to the number of iterations shared in our two-step registration process on three platforms. In these experiments, 50% of the total number of iterations is allocated to each step. .......................................

Table 3 -

 3 3: Mean computation time for higher resolution images. Image processing includes the background subtraction algorithm, color segmentation, edge detection and the chamfer distance

transform. The computation time is similar for each registration step (non-overlapping ratio and mean edge distance). The ratio indicates the relationship between the computation times of the mean edge distance and thenon-overlapping ratio. .................................................................................................

Table 4 -

 4

1: Computation time with respect to the number of particle evaluations (histogram computation). Image size: 160 x 120. .................................................................................................

Table 2 - 1 :

 21 The biomechanical constraints applied to each joint angle of our 3D model

	Parameter	Joint	Minimum	Maximum
			rotation	rotation
	1	Humanoid root torsion	-180°	180°
	2	Humanoid root roll	-45°	45°
	3	Humanoid root tilt	-45°	45°
	4	Neck toll	-10°	10°
	5	Neck torsion	-10°	10°
	6	Neck tilt	-10°	10°
	7	Left Shoulder flexion	-110°	25°
	8	Left Shoulder twisting	-60°	30°
	9	Left Shoulder abduct	-20°	100°
	10	Right Shoulder flexion	-110°	25°
	11	Right Shoulder twisting	-30°	60°
	12	Right Shoulder abduct	-100°	20°
	13	Left Elbow flexion	-150°	0°
	14	Right Elbow flexion	-150°	0°
	15	Left Wrist flexion	-20°	20°
	16	Left Wrist twisting	-100°	100°
	17	Left Wrist pivot	-37°	27°
	18	Right Wrist flexion	-20°	20°
	19	Right Wrist twisting	-100°	100°
	20	Right Wrist pivot	-37°	27°

Table 3 -

 3 2: Computation time in milliseconds (average and standard deviation) with respect to the number of iterations shared in our two-step registration process on three platforms. In these experiments, 50% of the total number of iterations is allocated to each step.

		Platform 1	Platform 2	Platform 3
	40	20 ± 3 ms			22 ± 7 ms	24 ± 6 ms
	100	31 ± 5 ms			36 ± 7 ms	37 ± 6 ms
	200	46 ± 6 ms			58 ± 7 ms	59 ± 7 ms
	300	62 ± 8 ms			79 ± 7 ms	79 ± 7 ms
	400	75 ± 9 ms			87 ± 7 ms	95 ± 9 ms
	500	93 ± 10 ms	101 ± 10 ms	114 ± 10 ms
	Image	Image	Non-		Mean edge	Ratio
	resolution	processing	overlapping	distance (MED)	(MED:NOR)
			ratio (NOR)
	160 x 120	66 ms	0.35 ms		0.37 ms	1.06 ms
	256 x 256	137 ms	0.68 ms		0.56 ms	0.82 ms
	320 x 240	149 ms	0.78 ms		0.69 ms	0.88 ms
	480 x 480	482 ms	1.95 ms		1.52 ms	0.80 ms
	512 x 512	560 ms	2.24 ms		1.75 ms	0.78 ms
	640 x 480	600 ms	2.58 ms		1.99 ms	0.77 ms
	Table

Table 4 - 1 :

 41 Computation time with respect to the number of particle evaluations (histogram computation). Image size: 160 x 120.

		CPU	CPU	GPU-1	GPU-2
		(Native	(OpenCL)	(OpenCL)	(OpenCL)
		C++)
	100	27.14 ms	12.24 ms	1.50 ms	1.37 ms
	300	40.31 ms	19.75 ms	2.73 ms	2.50 ms
	500	75.91 ms	28.32 ms	6.85 ms	6.53 ms
	700	110.34 ms	50.42 ms	20.84 ms	16.84 ms

  et nous proposons des nouvelles méthodes pour l"acquisition 3D des gestes par vision monoscopique. Nous décrivons les différentes approches dans l"état de l"art pour l"acquisition 3D des gestes par vision par ordinateur. Nous améliorons la robustesse et la précision des algorithmes et nous évaluons de manière expérimentale leur performance. Dans le chapitre 2 nous présentons une analyse détaillée de l'état de l'art pour l"acquisition 3D de mouvements par vision artificielle. Dans le chapitre 3, des nouveaux algorithmes basés sur le récalage d"un modèle 3D sont proposés pour améliorer la performance du suivi. Nous proposons de combiner une étape de recalage robuste entre régions et une étape plus précise de recalage sur les contours. Nous définissons une répartition optimale entre ces deux étapes pour atteindre la meilleure précision sous la contrainte du temps réel. Dans le chapitre 4, nous repoussons les limitations des algorithmes d"optimisation locale pour l"acquisition 3D des gestes en intégrant des heuristiques avec un filtrage particulaire en temps réel. Nous proposons et évaluons expérimentalement plusieurs heuristiques qui améliorent conjointement la robustesse, la précision et le traitement en temps réel. Le calcul en temps réel est obtenu avec un nombre élevé de particules grâce à une mise en oeuvre parallèle sur GPU de l"évaluation de ces dernières. Enfin, nous évaluons expérimentalement les résultats de notre algorithme de filtrage particulaire pour l"acquisition 3D des gestes par vision monoculaire en temps réel sur plusieurs séquences vidéo réelles. Dans le chapitre 5, nous résumons les contributions de cette thèse et nous présentons la conclusion finale. Les perspectives et les futurs travaux sont discutés.

	Chapitre 2 : Etat de l'art
	2.1 Introduction
	Les technologies d"acquisition du mouvement sont apparues à la fin des années 1970 (suivi
	des mouvements des pilotes) (Maureen, 2000). La section 2.2 de ce chapitre décrit les
	technologies d"acquisition de mouvement. La section 2.3 est une analyse des techniques
	actuelles d"acquisition du mouvement humain par vision artificielle sans marqueurs. Enfin,
	dans la section 2.3, nous décrivons brièvement notre approche pour l"acquisition 3D des
	gestes par vision monoculaire.

  essaient de détecter chaque partie du corps individuellement à partir des primitives d'image et d'assembler les parties du corps détectés dans une pose humaine en utilisant des heuristiques ou des contraintes (par exemple la proximité entre les parties du corps liées). Ces approches ont comme avantages qu"ils peuvent effectuer l"initialisation automatique de la pose ainsi que la récupération des erreurs de suivi. Cependant, le principal inconvénient est la difficulté pour détecter chaque partie du corps individuellement à cause des occlusions partielles ou des régions similaires aux parties du corps (faux positifs).

1) Ré-échantillonnage. Pour

  Pour chaque groupe de particules enfants a. Si : Construire un simplexe et itérer pour guider les particules vers les optimum locaux (section 4.4.2.3) en utilisant l"échantillonnage partitionné basée mouvement (section 4.4.2.2) dans l"espace du bout de la chaine cinématique (section 4.4.2.5). Un nouvel Si : Diffuser de manière aléatoire chaque enfant en utilisant l"échantillonnage partitionné basée mouvement (section 4.4.2.2) dans l"espace du bout de la chaine cinématique (section 4.4.2.4). Générer des nouveaux échantillons avec les sauts-cinématiques (section 4.4.2.4), pour les particules avec les poids le plus élevé dans les étapes a) ou b). Seuls les échantillons qui respectent les contraintes biomécaniques sont conservés et ajoutés au groupe. 3) Mesurer. Évaluer toutes les particules en fonction de la correspondance entre régions colorées et contours (section 4.4.1). L"évaluation des particules est parallélisé par GPU (section 4.4.3). Les particules pondérées sont classés par poids et les particules de poids plus faible sont éliminée, ou est le nombre d"échantillons valides calculés par sauts-cinématique. Finalement, les poids sont normalisés .

	chaque particule en utilisant un ré-échantillonnage déterministe par poids (section , générer particules enfants 2) Prédiction. ensemble de particules 4.4.2.1). est généré après avoir complété itérations, où . est généré après la diffusion aléatoire. c. Données de sortie : L"ensemble de particules qui représente la densité postérieure actuelle . La pose 3D est estimée en sélectionnant la particule avec le b. Un nouvel ensemble de particules poids le plus élevé.

Experiments were run on a CPU Intel Core

Extreme Q9300 @ 2.53 GHz (CPU-2)

These video sequences were captured using a Logitech QuickCam Pro

webcam at 160 x 120 pixel resolution.

Experiments were run on an Intel Core 2 Quad CPU Q9000 @ 2.0 Ghz, a GPU Nvidia GTX 280M with 240 CUDA cores @ 1296Mhz (GPU-1) and a GPU ATIRadeon HD 5870 with 800 Stream Processors @ 850Mhz (GPU-2)

Acknowledgments

Since this PhD adventure started, more than 3 years ago, I have been very fortunate to meet and work with many great people. Here, I would like to express my sincere gratitude to all of them who made the development of this thesis possible.

I would like to express my sincerest gratitude to my supervisor Patrick Horain for his patience with me and generous guidance during this process. Thanks for showing me the value of

For example the rotation of a 3D vertex of a polygon belonging to a forearm segment can be computed using the following equations in homogeneous coordinates:

(2.1) (2.2) Here, are the internal 3D coordinates of the 3D vertex in the forearm segment and the 3D coordinates of the rotated vertex are calculated by multiplying the transformation matrix , which is computed from the shoulder translation , the shoulder rotation matrix , the elbow translation matrix and the elbow rotation matrix . In this way, we rotate and translate all of the vertices of our 3D model according to the vector of joint angles. In Figure 2-16, we see a projection (using OpenGL) of our 3D upper-body model showing a 3D pose. Further implementation details can be found in [START_REF] Wright | OpenGL SuperBible: Comprehensive Tutorial and Reference[END_REF].

Animating 3D avatars using MPEG-4 BAP parameters

BAP (Body Animation Parameters) are a set of parameters that define the manipulation of independent degrees of freedom in body skeleton models. BAPs have the advantage of producing similar high-level animation results on different body models without the need to calibrate each model [START_REF] Capin | Controlling and Efficient Coding of MPEG-4 Compliant Avatars[END_REF].

For each captured image, our motion capture system outputs the vector of joint angles that describes the estimated 3D body pose. This is then encoded in the MPEG-4 BAP format specified in the International Standard ISO/IEC 14996-2 (2001). The full set of BAPs consists of 186 body joint angles, including sacroiliac, hip, knee, ankle, vertebra, clavicle, shoulder, elbow, wrist and the fingers joints, that can be used to animate a 3D avatar in a virtual environment.

The BAP encoding is particularly suited for low-bitrate transmission in dedicated interactive communications and broadcast environments [START_REF] Capin | Controlling and Efficient Coding of MPEG-4 Compliant Avatars[END_REF]. The encoding consists basically of a masking scheme providing selective transmission of the BAPs according to which body parts are active in each time step. In this way, we can animate 3D avatars by activating only the BAPs that correspond to our vector of 20 joint angles. The following table hypotheses or particles. The algorithm is accelerated by harnessing the computation power of recent graphic cards (GPU). The chapter is structured as follows. In the next section (4.2), we review some fundamental concepts of the particle filter approach. Then, in section 4.3, we discuss some improvements over the state-of-the-art for 3D motion capture. Section 4.4 describes in detail our proposed particle filtering approach with heuristics for 3D motion capture and our GPU implementation to accelerate the evaluation of particles. In section 4.4, we report comparative experimental results showing the contribution of each heuristic proposed to the overall particle filter. The gain of robustness and accuracy achieved by our proposed real-time heuristic particle filter is evaluated experimentally on several sequences of human gestures containing motion in depth, occlusions, fast motions and rotations. In section 4.5, the performance of the proposed algorithm is evaluated qualitatively and quantitatively on various real video sequences. Finally, our conclusions are discussed in section 4.6.

Particle filtering approach

Many real-world problems involve estimating unknown states or quantities of a dynamical system from data observations. When prior knowledge is available, the estimates can be inferred by computing a posterior probability over the unknown states. The posterior distribution is found using Bayes theorem to combine the prior probability with the likelihood of the particular state given data observation . Unfortunately, real data can be very complex, involving non-linear, non-Gaussian and high-dimensional elements, in which the estimates cannot be computed accurately in closed form.

Hierarchical Partitioned Motion-based (HPM) Sampling

This strategy aims at diffusing more efficiently the particles based on motion observation. It consists in applying random Gaussian noise only to those body limbs that have moved between the previous and current frames.

We partition the vector of pose parameters in four sets of parameters:

. The last 3 sets of parameters controls the pose of a limb of the 3D model: , and are the parameters for head, left arm and right arm respectively.

holds the remaining parameters that have an effect on the chest and all the limbs (see . A motion observation measurement is associated to each set of parameters:

. The motion measurements are variations in overlapping of color regions with respect to the previous limb projection: (4.15) where represents one of the body limbs considered (chest, head, left arm and right arm). and are the set of pixels with the k color class in the segmented images of the previous frame and the current frame respectively. Left arm and right arm are assigned to the same color class in the segmented image.

is the set of pixels with the k color in the projection of the 3D pose described in the particle sub state estimated in the previous frame . | X | represent the number of pixels in X.

Using the equation ( 4.15), we can identify which body limb has moved between the previous and current frames. Hence, we can apply random diffusion only to specific sub states using the following equations:

where is the scaled random Gaussian diffusion described in (4.13), is a measure describing the degree of motion of each body limb . The factor represents the maximum degree of motion between two frames (obtained experimentally).

, , are the sets of parameters output by resampling step and , , are the sets of parameters after random diffusion. In the equation (4.16), random diffusion is applied to the full configuration Figure 4-24: The elbow E K is on a circle orthogonal to the line from shoulder S K to wrist W K . Its position is defined by the swivel angle Φ around that line.

After estimating the end-effector and the elbow position based on the swivel angle , we solve the joint angles of each arm sub-chain using the analytic method proposed in section 4.4.2.2.3b.

The next two figures show the enhancement in accuracy and robustness resulting from particle filtering in the end-effectors space. As seen in Figure 4-25, our method did improve the 3D accuracy for the video sequences with motion in the depth direction. However accuracy is not significantly improved for the video sequence that contains mostly frontoparallel motion (figure 4-25a). This is because the particles are mainly scattered in the depth direction.

In Figure 4-26, we observe that particle filtering in the end-effectors space performs well in terms of robustness. Particularly, higher robustness (less mistrackings) was achieved on the video sequence "asking gesture" (figure 4-26d), which appears to be related with the many motion in depth direction that this video contains.

Quantitative results on real video sequences

The next figure shows the gain of robustness of our particle filter method with respect to the standard CONDENSATION algorithm. We see that our algorithm reduces significantly the number of mistrackings for all the video sequences, including those where the actor is moving in the scene (figures 4-33e and 4-33f) and turning around himself (figure 4-33c).

We note that CONDENSATION algorithm presented the highest number of failures in the video sequences where the actor is not facing to the camera (figures 4-33d and 4-33f). The reason is that depth ambiguities remain for almost all images of these video sequences even if the actor is not executing any motion. In these cases, the proposed algorithm achieved the highest gain of robustness (figures 4-33d and 4-33f).

We see also that our algorithm achieved the lowest gain of robustness for the video sequence in which the actor is turning around himself (figure 4-33c). This is because full body rotation motions are the most difficult motion to track since the turning direction can hardly be detected with the image feature we used (color region and edges). Some other features, possibly optical flow, would help here.

Qualitative results on real video sequences

In this section, qualitative visual results are presented by animating a 3D avatar (OpenSpace3D, 2010) in real-time from the tracked video sequences (Figure 4-32). Thus, we compared visually the estimated 3D pose reproduced by the avatar with the actual 3D pose of the input image.

When using particle filtering algorithm, the 3D pose estimated may changes abruptly to another different 3D pose between consecutive time steps. This causes a "jiggling" effect in the gesture rendered by the 3D avatar. In order to reduce "jiggling", we smooth the tracked motion using a recursive filter by the following equation:

Where is a joint angle parameter of a 3D pose estimated (highest weight particle) at the current time step . and are the smoothed joint angle values in the current and previous time steps respectively. is the smoothing coefficient. In our experiments, we have found that a coefficient value of produces visually good results without sacrificing significantly the accuracy of the 3D pose estimated.

In next figures, we show qualitative 3D pose estimation results achieved by the proposed particle filter with heuristics algorithm. Each pose estimated is rendered in a 3D avatar in realtime by converting the joint angles to MPEG-4 BAP parameters (Table 2-2). As we see in the next figures, the 3D pose results are, in most cases, qualitatively close to the pose of the input image sequence. The pose of the 3D avatar is showed from different perspectives in order to observe clearly the motion in depth estimated for each gesture.

Chapter 5

Conclusions and perspectives

In this work, we address the problem of real-time 3D human motion capture without markers from monocular images (obtained from a webcam). Our approach consists in registering a 3D articulated model of the upper human body on monocular video sequences. We extend a previous work by ( [START_REF] Soares | Acquisition 3D du geste par vision monoscopique en temps réel et téléprésence[END_REF] and we propose new methods to enhance the robustness and accuracy of the 3D pose tracking. The 3D pose data is used to animate a 3D avatar in a collaborative virtual environment. The performance of our approach is quantitatively evaluated on monocular video sequences containing gestures with fast motions, partial body occlusions, rotations and motion in depth. The proposed algorithms allow us to track robustly a large variety of human gestures dealing with depth ambiguities in monocular images while holding real-time processing. In the next sections, we summarize the contributions of the thesis and present some future perspectives.

Contributions

We have developed a system for robust real-time upper-body motion capture by monocular vision. The motion capture system is divided in two main steps: initialization and tracking. In the initialization step, new algorithms were proposed to learn the appearance of the background and the user as well as the size of body limbs. In the tracking step, new pose estimation techniques are proposed in order to improve robustness and accuracy of the 3D pose while facing real-time computation. In order to enhance robustness to clutter environments and lighting variations from the scene, we have implemented a background subtraction method that combines two robust features: color chrominance and gradients.

Accuracy is improved by edge-based registration as a further step after region-based registration. It works by minimizing the distance between edges in the input images and occluding edges of the 3D model projected in the image plane. In this step, the initial 3D pose is the pose output by region-based registration. The advantages and limitations of each registration step are discussed and compared experimentally with a limited number of iterations. We found that region-based registration provides high robustness but inaccurate pose estimation while edge-based registration allows achieving more accurate poses at the cost of unstable tracking. An experimental analysis was done on several video sequences containing various gestures with body occlusions, motion in depth, fast motions and rotations. From the experimental analysis, we define an optimal compromise between robustness and accuracy with respect to the number of iterations. From this compromise, we have demonstrated the efficiency of combining both registration steps to achieve more robust and accurate tracking in real-time.

Although, the accuracy of the 3D poses is still limited because of depth ambiguities in monocular images. The major limitation of the previous registration process is that it achieves 2D ambiguous registration while we are interested in 3D poses, which lack accuracy in the