Stefan Bernögger

Lijun Yin

Anup Basu

Axel Pinz
email: pinzg@icg.tu-graz.ac.at

Eye Tracking and Animation for MPEG-4 Coding

Accurate localization and tracking of facial features are crucial for developing high quality model-based coding (MPEG-4) systems. For teleconferencing applications at very low bit rates, it is necessary to track eye and lip movements accurately over time. These movements can be coded and transmitted to a remote site, where animation techniques can be used to synthesize facial movements on a model of a face. In this paper we describe simple heuristics which are effective in improving the results of well-known facial feature detection and tracking algorithms. Animation models are also presented, along with experimental results to demonstrate the system being developed. We focus our discussion only on the detection, tracking and modeling of eye movements.

Introduction

From the image analysis point of view, images can be considered as having structural features or objects such as contours and regions. These image features or objects have been exploited to encode images at very low bit rates. Research on this approach, known as model-based coding, which is related to both image analysis and computer graphics, has recently intensified. Up to now, most of the contributions to 3D model-based coding have focused on human facial images. Although a number of schemes for modelbased coding have been proposed [START_REF] Choi | Analysis and Synthesis of Facial Image Sequences in Model-Based Image Coding[END_REF][START_REF] Pearson | Developments in Model-Based Video Coding[END_REF], automatic facial feature detection and tracking along with facial expression analysis and synthesis still poses a big challenge to the problem of finding accurate features and their motion.

A variety of approaches have been proposed for detection of facial features. These include deformable template Supported by a Kurt Gödel scholarship from the Austrian government Stefan Bernögger was on leave at the Department of Computing Science, University of Alberta, Edmonton, in 1997/98. matching [START_REF] Chow | Towards a System for Automatic Facial Feature Detection[END_REF][START_REF] Deng | Region-Based Template Deformation and Masking for Eye-Feature Extraction and Description[END_REF][START_REF] Yuille | Feature Extraction from Faces Using Deformable Templates[END_REF], Hough transforms, and color image processing [START_REF] Chang | Facial Feature Extraction from Color Images[END_REF][START_REF] Wu | Face and Facial Feature Extraction from Color Image[END_REF]. Matching deformable templates requires a fairly accurate initial localization of the template because the energy minimization process only finds a local minimum. Other problems are caused by using several energy terms and weighting factors during the different epochs of matching. Because of the definition of the energy terms in [START_REF] Yuille | Feature Extraction from Faces Using Deformable Templates[END_REF] the template also inclines to shrink. In this paper we overcome some of these difficulties by improving the initial localization process. We show that simple processing on color images coupled with Hough transform and deformable template matching can produce very accurate results.

Another important component in model-based coding is synthesizing facial movements and expression at a remote site, using the motion parameters detected on an actual face image and animation on a model of this face. To represent a facial expression, several approaches have been proposed relying on feature detection [START_REF] Brunelli | Face Recognition: Features versus Templates[END_REF][START_REF] Yuille | Feature Extraction from Faces Using Deformable Templates[END_REF], facial expression analysis [START_REF] Tang | Quantifying Facial Expressions: Smiles[END_REF][START_REF] Terzopoulos | Analysis and Synthesis of Facial Image Sequences Using Physical and Anatomical Models[END_REF], and facial expression synthesis [START_REF] Ekman | Facial Action Coding System[END_REF][START_REF] Platt | Animating Facial Expressions[END_REF]. However, little work has been done specifically on the eye expression synthesis. Because the eye is one of the most significant organs contributing to a vivid face expression, subtle changes of the eye movement can result in a different expression. Therefore accurate eye expression analysis and synthesis are necessary.

In this paper, we present an approach to synthesize the eye movement by using the extracted eye features to compute the deformation of the eyes of the 3D model. After creating an individualized 3D face model, we map this model to the first frame of the face sequence. Based on the extracted eye features we apply the deformation parameters to the 3D model to synthesize the eye movement in successive frames.

The remainder of this paper is organized as follows: In Section 2, we describe the approach proposed for accurate eye feature detection and tracking. In Section 3, animation techniques for presenting eye movement are described. Ex-perimental results are shown in Section 4. Finally, concluding remarks are given in Section 5.

Robust detection and tracking of eye features

Our approach to detecting the eyes is similar to [START_REF] Chow | Towards a System for Automatic Facial Feature Detection[END_REF] in that it uses Hough transform and deformable template matching, however, it also exploits color information to extract the eyes accurately. The algorithm can be outlined as follows:

Determine two coarse regions of interest for the eyes.

Search the iris of the eyes using a gradient based Hough transform.

Determine a fine region of interest for extracting the boundaries of the eyes.

Using color information to get an initial approximation for the eye lids.

Localize the eye lids using deformable templates.

After detecting the face region two coarse regions of interest in the upper left and upper right half of an image can be defined to detect the eyes. Also a coarse range for the size of the eyes can be derived.

Since the iris is the most significant feature of the eye and has a simple circular shape, it is detected first by using a gradient-based Hough transform for circles [START_REF] Davies | A Modified Hough Scheme for General Circle Location[END_REF][START_REF] Kierkegaard | A Method for Detection of Circular Arcs Based on the Hough Transform[END_REF]. The necessary information position, magnitude and direction of significant edges is extracted by convolving the intensity image with a Sobel kernel, and performing a non-maximum suppression by removing all edges with a magnitude lower than 30 of the maximum magnitude. Figure 1 shows the robustness of the Hough transform. In spite of the large amount of edgels which are not produced by the contour of the iris the Hough space shows a significant maximum at the exact position of the center of the iris.

After extracting the circles the deformable templates for the eye lids have to be initialized. The model, along with all the parameters used is shown in Figure 2; with the parameters being set as follows: a = 1 :5r iris c = 0 :5r iris b = 2 :2r iris [START_REF] Brunelli | Face Recognition: Features versus Templates[END_REF] where r iris is the radius of the extracted circle. The orientation is determined by the center points of the two circles. The initialized deformable template is also shown in For the matching of the deformable template two different types of image information are used to create potential fields, one in each epoch. The image information extracted from a typical eye is shown in Figure 3. The first step in localizing the eye lids is to approximate the position of the deformable template relative to the iris. This is done by minimizing the following energy (E sat ) which is similar to the valley energy in [START_REF] Yuille | Feature Extraction from Faces Using Deformable Templates[END_REF]:

E sat = , 1 jA w j Z Aw sat xdA (2)
A w is the area inside the parabolas but not inside the circle of the iris and sat x is the inverted saturation value of the color image. Since only the location (not the size) is changed this method does not have the shrinking effect.

The next step is to approximate the parameters h 1 and h 2 . Especially the parameter h 1 is important because of the larger movement of the upper eye lid. In order to estimate the parameters, two regions of interest on both sides of the iris are defined (see Figure 4). The parameters of these regions are set as follows: dx = 5 dy = 3 r iris k = r iris + 5 [START_REF] Choi | Analysis and Synthesis of Facial Image Sequences in Model-Based Image Coding[END_REF] Depending on the position of the iris inside the deformable template only the left or the right region of interest is used for the further computation.

By using the horizontal integral projection ( [START_REF] Brunelli | Face Recognition: Features versus Templates[END_REF]), and by detecting the two most significant opposite gradients in the projection, the position of a point on the upper and lower eye lid can be detected (see Figure 4). The parameters h 1 and h 2 of the template are updated as follows: The last step is to match the deformable template accurately to the eye lids by minimizing the following energy (E edge ):

E edge = , 1 jB w j Z Bw edge xds (5)
B w is the boundary of the parabolas and edge x is the edge magnitude. During this minimization every parameter of the deformable template (location, orientation, height, width) can be changed. The tracking of eye features is similar to detection of eye features with the following differences:

The region of interest as well as the possible size and therefore the Hough space for the extraction of the iris can be restricted by using the position and the size of the extracted eye in the previous frame.

Instead of using the deformable template shown in Figure 2, the matched template of the previous frame is used for the initialization of the new template.

Animation of eye movements

The eye detection and tracking algorithms extract the contours of the iris and eye lids in each frame of the image sequence. These eye features are used to synthesize the real motions of the eye on a 3D facial model. The main procedure is described as follows:

Based on the 3D eye model which is part of our existing 3D facial model, 11 feature vertices are defined for each eye as shown in Figure 5. Once the eye lid contour and the iris are detected in the image sequence, the corresponding feature points on the template can be also determined simply by computing the points on the boundary of the parabolas and by using the center of the circle. For iris animation: After the iris is detected in the image sequence, the center of the iris in the eye model can be matched with the iris center in the eye image. The size of the iris model can be adjusted to the circle of the iris template.

For eye lid animation: After the eye lids are detected in the image sequence, the feature vertices on the eye model can be fitted to the feature points on the eye image. The displacements of the feature vertices and feature points consist of a set of motion vectors (we call them feature motion vectors (FMV)). To deform and animate the eye movement, the set of motion vectors of non-feature vertices has to be found as well. They can be derived by interpolating the feature motion vectors which are around the non-feature vertices. Actually, in the interpolation procedure, the newly obtained motion vector of the non-feature vertex is also put into the set of FMV. Therefore the size of the FMV is increased dynamically. The motion vector of a non-feature vertex on the eye model (denoted as v) can be derived by the following equation:

v = N X n=1 wd n v n (6)
where d n is the distance between the non-feature vertex (v) and the feature vertex v n , n = 1 ; 2; : : : ; N ; (d 1 ; : : : ; d N ) are arranged in an increasing order, and wd n is a weight function which has a large output value for a small input of d n :

wd n = d n 0 P N n=1 d n where n 0 = N + 1 , n (7) Based on these vertices, a deformed eye model can be built for each frame. The resulting eye model will show us the synthesized eye movement (see also Figure 6).

Finally, the animated eye model can be texturemapped by the original image (i.e. first frame) to synthesize the real eye expression completely.

Experimental results

To evaluate the algorithms developed, experiments with various color images of different eyes and eye sequences were made. The preliminary experiments have shown that the Hough transform, which is the first and therefore one of the most important steps, is very robust against noise as well as edges which are not produced by the contour of the iris. The results on tracking and animating of the iris and the eye lids in one image sequence are shown in Figure 6. Eye movements are synthesized as follows: First, eye movements are modeled as deformations of the individualized wire frame model (see Figure 7)(top). Then, the wire frame models in the successive frames are texturemapped by using the first frame of the sequence (see Figure 7)(bottom). From the preliminary experimental results, we can see that the algorithms proposed here behaves well for synthesizing eye movements. For the experiments in this paper, a high resolution facial model with 3118 patches is used instead of the low resolution model used in [START_REF] Tang | Quantifying Facial Expressions: Smiles[END_REF]. However, the time complexity of modeling, analysis and synthesis increase significantly as a result.

Conclusion

In this paper we discussed robust methods for detecting and tracking eye movements, a strategy for eye movement animation, and resulting applications in model-based low bit-rate coding.

In future reports we will discuss extensions of the method to robust detection of lip movements and network strategies for real-time demonstration of the system.

Figure 1 .

 1 Figure 1. Extraction of circle (image and result, edge image, Hough space).

Figure 2 .

 2 Figure 2. Deformable Template (model, initialization).

Figure 3 .

 3 Figure 3. Image fields used for computing the potential energy (image, saturation, edge).

  and y low are the y-coordinates of the detected points inside the region of interest of the upper and lower eye lid.

h 1 and h 2 Figure 4 .

 24 Figure 4. Integral projections beside iris (model and example).

Figure 5 .

 5 Figure 5. Defined eye feature vertices.

Figure 6 .

 6 Figure 6. Sequence (Frame 1, 24, 68, 169) showing eye movement. Original images (top); extracted eye template (middle); matched and animated 3D model (bottom).

Figure 7 .

 7 Figure 7. Animated wire frame model (top) and texture-mapped model (bottom) for different eye expressions. From left to right: individual model and original image (first frame), deformed model and synthesized images looking left, right, and straight respectively.


Nathaniel Rossol
email: nrossol@ualberta.ca

Senior Member, IEEE Irene Cheng
email: locheng@ualberta.ca

Senior Member, IEEE Anup Basu
email: basu@ualberta.ca

A Multisensor Technique for Gesture Recognition Through Intelligent Skeletal Pose Analysis

Keywords: Depth sensors, gesture recognition, multisensor, occlusion, pose estimation, user evaluation

Recent advances in smart sensor technology and computer vision techniques have made the tracking of unmarked human hand and finger movements possible with high accuracy and at sampling rates of over 120 Hz. However, these new sensors also present challenges for real-time gesture recognition due to the frequent occlusion of fingers by other parts of the hand. We present a novel multisensor technique that improves the pose estimation accuracy during real-time computer vision gesture recognition. A classifier is trained offline, using a premeasured artificial hand, to learn which hand positions and orientations are likely to be associated with higher pose estimation error. During run-time, our algorithm uses the prebuilt classifier to select the best sensor-generated skeletal pose at each time step, which leads to a fused sequence of optimal poses over time. The artificial hand used to establish the ground truth is configured in a number of commonly used hand poses such as pinches and taps. Experimental results demonstrate that this new technique can reduce total pose estimation error by over 30% compared with using a single sensor, while still maintaining real-time performance. Our evaluations also demonstrate that our approach significantly outperforms many other alternative approaches such as weighted averaging of hand poses. An analysis of our classifier performance shows that the offline training time is insignificant, and our configuration achieves about 90.8% optimality for the dataset used. Our method effectively increases the robustness of touchless display interactions, especially in high-occlusion situations by analyzing skeletal poses from multiple views.

I. INTRODUCTION

I NTERACTING with computer interfaces through mid-air hand gestures is emerging as an intuitive and effective alternative to traditional touch-screen interfaces. For example, interacting with medical displays via touch screens or a traditional mouse and keyboard can present a major problem for medical professionals wishing to keep equipment sterile. Even in small clinical settings, examinations may often use fluids, such as ultrasound conductive gel, which users do not want to spread onto a physical interface through touch [START_REF] Rossol | Touchfree medical interfaces[END_REF].

Mid-air hand gestures allow individuals to interact freely with computer interfaces without keyboard, mouse, or screen contact. Instead, hand movements are tracked and interpreted through computer vision (CV) techniques [START_REF] Grange | M/ORIS: A medical/operating room interaction system[END_REF]- [START_REF] Wachs | A gesture-based tool for sterile browsing of radiology images[END_REF]. This paper is focused on the domain of markerless mid-air hand gestures (i.e., gestures that are tracked with CV techniques alone and do not require the placement of markers or tracking devices on the user's hands). Markerless approaches are much more desirable among users because they allow for immediate interaction with a computer interface. Time and resources are not wasted on additional setup or calibration steps [START_REF] Wachs | Vision-based hand-gesture applications[END_REF].

A. Problem

Previous work in markerless CV hand tracking has made use of color and/or depth cameras (such as the Microsoft Kinect [START_REF] Oikonomidis | Efficient model-based 3D tracking of hand articulations using kinect[END_REF]) in order to analyze either static or dynamic hand gestures in real time. Using raw depth/color data, features such as hand and finger positions/orientations can be extracted, from which an estimate of the hand's pose can be determined. The main drawback of these past approaches is a large amount of noise associated with the computed 3-D fingertip positions. In addition, low sampling rates make it difficult to track quick hand movements due to motion blur [START_REF] Hardenberg | Bare-hand human-computer interaction[END_REF]. With the recent hardware advances in new CV hand-tracking sensor systems (such as the Leap Motion Sensor), millimeter-level precision can be achieved for tracking a fully articulated hand skeleton at sampling rates of over 120 frames/s [START_REF] Weichert | Analysis of the accuracy and robustness of the leap motion controller[END_REF]. However, these latest sensors still have low pose estimation accuracy due to occlusion. These situations frequently occur when the palm is not directly facing the camera, or when performing certain gestures, such as pinches, where one finger can be blocked by another. These problems can disrupt accurate gesture interpretation and lead to unintended computer operations.

B. Proposed Solution

We introduce a novel technique to improve hand pose estimation accuracy when using smart depth sensor technology for tracking hand poses. In particular, our technique addresses the issue of occlusion by using pose estimations from multiple sensors placed at different viewing angles. One of the primary advantages of our approach is to avoid fusing sensor data at the 3-D depth-map level, which is not available from all modern sensors such as the Leap Motion Sensor. Instead, we achieve wider flexibility by intelligently analyzing each sensor system's independently derived skeletal pose estimations. A key challenge that makes skeletal pose fusion especially difficult is the tendency of the underlying pose estimation algorithms being trapped in local minimas that can be substantially different from each other. This explains why most classical sensor fusion techniques, such as the Kalman filter [START_REF] Sun | Multi-sensor optimal information fusion Kalman filter[END_REF], are ineffective in this problem domain, because there is no useful difference in the generated noise profiles to make a meaningful quality evaluation of the sensor data. To address this issue, we present a more robust strategy, which demonstrates that by selecting an appropriately designed subset of the skeletal pose estimation parameters, we can build an offline model. The offline model can then be used in real time to intelligently select pose estimations, while still running at over 120 frames/s. In our experimental prototype involving dual sensors (see Fig. 1), we analyze the pose estimation accuracy from different angles for a number of hand gestures typically used to control displays (e.g., pinch, tap, and open hand). In this context, we demonstrate that we are able to achieve a 31.5% reduction in pose estimation error compared with using only a single sensor. We are able to effectively eliminate the false hand poses that interfere with accurate gesture recognition.

Our contributions are summarized as follows. 1) We improve pose estimation accuracy of state-of-the-art hand-tracking systems through a novel technique for analyzing skeletal hand poses from multiple sensors. 2) We experimentally demonstrate how the improved pose estimations can have a meaningful improvement on recognizing gestures used for controlling display interfaces.

II. RELATED WORK

A. Real-Time Hand Pose Estimation

CV-based hand gesture recognition can be broken down into two main categories: 1) model-based approaches concerned with pose estimation; and 2) appearance-based approaches [START_REF] Pavlovic | Visual interpretation of hand gestures for human-computer interaction: A review[END_REF]. Model-based approaches involve determining and tracking the entire articulated pose of the hand as it moves, including the 3-D position and orientation of the wrist, and the deflection angles of every joint. On the other hand, appearance-based approaches use other characteristics in the captured images, such as the silhouette, contour, color, area, and pixel flow, to predict the intended hand gesture [START_REF] Zhu | A real-time approach to the spotting, representation, and recognition of hand gestures for humancomputer interaction[END_REF], [START_REF] Ren | Robust part-based hand gesture recognition using kinect sensor[END_REF]. Despite the benefit of knowing the full pose of a moving hand, most real-time systems make use of indirect cues from appearance-based approaches due to processing time constraints [START_REF] Erol | Visionbased hand pose estimation: A review[END_REF]. Early studies have shown that accurate CV model-based hand pose estimation algorithms are too computationally expensive to run in real time [START_REF] Oikonomidis | Efficient model-based 3D tracking of hand articulations using kinect[END_REF]. Fortunately, recent hardware advances have helped deliver low-cost commercial depth sensors, which support real-time and more precise hand pose estimation.

In 2011, Oikonomidis et al. [START_REF] Oikonomidis | Efficient model-based 3D tracking of hand articulations using kinect[END_REF] successfully developed an accurate model-based approach for tracking the 3-D position, orientation, and full articulation of a hand at 15 Hz on high-end hardware. Their approach used a combination of video and depth images from a Microsoft Kinect sensor as input, which were processed by a modified particle swarm optimization algorithm. Although still computationally intensive, the 15-Hz frame rate can be achieved using only a single computer, making use of a highly parallelized GPU implementation. The authors then expanded their approach to include interactions between two hands [START_REF] Oikonomidis | Tracking the articulated motion of two strongly interacting hands[END_REF].

In 2013, Keskin, et al. [START_REF] Keskin | Real time hand pose estimation using depth sensors[END_REF] proposed a novel approach for realtime hand pose recognition using random decision forests on a synthetically generated dataset of hand poses. Their approach is similar to the approach used by Microsoft Research on Kinect to create the real-time skeletal pose recognition system [START_REF] Shotton | Real-time human pose recognition in parts from single depth images[END_REF]. By applying their classifier to label each depth pixel, and then mean-shift to identify the position of each part of the hand, full pose estimation is achieved. The classifier is able to run at a rate of up to 30 Hz. Although the authors claimed that the technique should theoretically be able to classify arbitrary hand poses given enough training data, classification of only a few discrete poses (namely, hand poses related to American Sign Language) was presented. This limitation is also present in the real-time discrete hand pose system proposed by Romero et al. [START_REF] Romero | Monocular real-time 3D articulated hand pose estimation[END_REF]. In contrast, we are interested in the continuous space of all possible hand poses. Our goal is to maximize flexibility and future extensibility of our system.

A drawback of traditional approaches is that they are not able to robustly capture small precise gestures (like quick subtle finger taps), due to their low sampling rates. It is necessary to estimate human hand poses at high sampling rates because of the rapid motions of the hand. Previous work has reported that human hands can reach speeds of up to 5 m/s and the wrist can reach rotational speeds of up to 300 • /s during normal gestures [START_REF] Erol | Visionbased hand pose estimation: A review[END_REF]. Hand poses between successive frames become increasingly uncorrelated with each other as the hand moves faster [START_REF] Erol | Visionbased hand pose estimation: A review[END_REF]. The combination of high movement speeds and low sampling rates often leads to inaccurate gesture recognition. More accurate results can be obtained from advanced sensors with higher sampling rates. For this reason, we used the leap motion sensor [START_REF] Weichert | Analysis of the accuracy and robustness of the leap motion controller[END_REF] to test our method.

The leap motion sensor is an example of a new generation of CV-based sensors that provides real-time hand-tracking and pose estimation. Unlike past Infrared Red (IR) pattern light depth sensors (such as the first generation Microsoft Kinect), or time-of-flight sensors (such as the Soft Kinectic DepthSense Camera), the leap motion sensor is able to provide much higher 3-D positional accuracy for hands and fingertips (better than 1 mm of precision). Its sampling rate exceeds 120 frames/s [START_REF] Weichert | Analysis of the accuracy and robustness of the leap motion controller[END_REF]. However, the sensor is unable to provide a full high-resolution In the pair of images on the right, a pinch pose (f) is tested. The sensor on the left has a fairly good view (g) and gives an estimate of (i). However, this pose is mostly occluded and seen as (h) from the right side sensor, which leads to an estimate of (j). Note that the pinch pose has become an open hand, which disagrees with the left sensor.

depth map due to USB bandwidth limitations. In addition, its maximum effective tracking distance is only around 50 cm from the device.

B. Sensor Fusion

High-occlusion situations impose a major challenge for analyzing hand poses. As previously mentioned, many skeletal hand pose estimation techniques follow particle-filter approaches, which can trap pose estimation algorithms in a local minimum due to inadequate visible data to resolve ambiguity. The pose can be incorrectly interpreted for a considerable amount of time, or even indefinitely if the user's hand continues to stay in a static pose. Typical real-time sensor fusion techniques, such as the Kalman filter [START_REF] Sun | Multi-sensor optimal information fusion Kalman filter[END_REF], are unsuitable in this context. This is because the similar noise profiles of correct and incorrect hand poses will result in equal evaluation weighting, making it impossible to identify the correct pose [START_REF] Mitra | Gesture recognition: A survey[END_REF]. While using finger motion, such as the angular velocities of finger joints, to predict future positions may be helpful, this method is not feasible for many applications given rapid finger movements.

Regardless of the underlying hand pose recognition technique, or sensor used, occlusion is a major problem when using a single vision-based sensor. We propose fusing data from multiple sensors placed at different viewing angles, and analyzing the skeletal poses directly instead of examining the depth maps, because the latter may not always be available. This is the case with the leap motion sensor, which does not generate any depth maps or 3-D point clouds.

We tested a two-sensor setup capturing a pose from two different viewing angles. When there is a disagreement between the sensors at a particular time step due to possible occlusion blocking one of the views, our computation model evaluates the different estimates and chooses the one that best fits the continuous stream of skeleton poses. Fig. 2 shows examples of agreement and disagreement between the two sensors. Our technique is intended to generate a fused sequence of optimal poses over time, and we are able to demonstrate (in Section IV) that this approach is more accurate than the alternative of fusing the sensor images at each time-step.

C. Gesture-Controlled Displays

Over the past decades, there have been many studies on hand-tracking and touchless displays. Real-time hand tracking is important in many applications, including medical ones. A pri-mary motivation in healthcare is reducing spreading biological contamination by avoiding touching a device, and the resulting time/cost savings from reduced sterilization [START_REF] Grätzel | A non-contact mouse for surgeon-computer interaction[END_REF].

One of the earlier works in CV-based gesture control of medical displays was completed by Grange et al., in 2004 [2]. Their system-controlled computer mouse movements in an operating room display via hand gestures. Stereo color cameras and a combination of static background subtraction and pixel color thresholding were used to track the user's hand positions in a 3-D space. As the system did not track fingers, virtual mouse clicks were performed by either pushing the hand forward 20 cm, or holding it absolutely still for several seconds. Similarly, the Gestix's system developed in 2008 [START_REF] Wachs | A gesture-based tool for sterile browsing of radiology images[END_REF] used a nearly identical approach but did not control a virtual cursor. Instead, the authors used communicative gestures (such as hand swipes or circular motions) to perform various tasks. As is typical in appearance-based approaches that use color information to segment the user's hands, both of these approaches are vulnerable to segmentation errors caused by changes in illumination, shadows, or dynamic backgrounds.

In 2011, Gallo et al. [START_REF] Gallo | Controller-free exploration of medical image data: Experiencing the kinect[END_REF] proposed a Kinect-based interface for visualizing medical images in a sterile surgery room. The user was required to be standing and using both hands for interaction. The system tracked the 3-D position of both hands at 30 Hz and recognized the hand as either being in the open or closed state. As with the previous works, the inability to track the finger positions means that the gesture requires large hand movements for recognition purposes, which can cause the user physical fatigue over time [START_REF] Segen | Look ma, no mouse![END_REF]. Another limitation of the system is that their method requires two hands to be free for operation, which is not possible when one hand is used to hold clinical tools.

Our system can be used with either one or both hands and is designed for gestures that are commonly adopted by touchscreen interfaces.

III. IMPLEMENTATION

Our multisensor skeletal pose estimation approach is composed of the following steps.

1) First, we use a trained support vector machine (SVM) [START_REF] Platt | Fast training of support vector machines using sequential minimal optimization[END_REF] model to intelligently determine the optimal pose estimation from an array of sensors. We build this model offline (only once) with a training set, which uses a IEEE TRANSACTIONS ON HUMAN-MACHINE SYSTEMS Fig. 3. Overview of our real-time execution steps. feature vector composed of a subset of each sensor's output. 2) Next, we convert each sensor's pose output into a global coordinate system so that the poses of all of the fingers are represented in a single unified space. Likewise, we also keep the positions of all of the fingers in a local hand coordinate system, which provides key information for the pose estimation model. 3) Finally, the local hand pose information and the global hand pose information are input into our gesture recognition model so that dynamic and static hand gestures can be tracked. An overview of these steps is shown in Fig. 3.

A. Sensor Array Setup

The goal of our implementation is to demonstrate the feasibility of our algorithm. We tested our approach with a two-sensor setup. As shown in Figs. 1 and4, our setup involves two leap motion sensors aligned at a 45 • angle to the table surface they are placed on. This angle is chosen to make the sensor view angles orthogonal, to optimize the amount of unique informa-tion available to each sensor during situations of high occlusion. The point at which the center of the field of view of both sensors intersects was set at 20 cm for our experiment, following the default precalibrated interaction height for the leap motion sensor.

One consideration when using multiple leap motion sensors for our configuration is that the IR (infrared) projectors of one sensor can shine directly into the IR cameras of the other, which can generate noisy data. This can be solved by positioning the sensors outside the 150 • field of view of each other, or by placing a small nonreflective object in-between the sensors, to prevent a direct line of sight. We adopted the latter approach in our implementation. Based on our test results, even if a pair of leap motion sensors shine directly into one another, the additional noise in the pose estimation was insignificant provided the automatic infrared light compensation feature in the sensor configuration was disabled.

B. Selecting Optimal Pose Estimations

We define the amount of pose estimation error as the sum of the Euclidean distances (in millimeters) of each fingertip from its ground truth position. The positions are expressed locally relative to the reported palm position and normal of the hand (provided directly by the sensor data in our setup). That is, if f i is a 3-D vector representing the position of the fingertip of the ith finger on a hand, and g i is the actual ground truth position, we then define the error of a hand pose estimation as

E = 5 i=1 ||f i -g i || 5 . ( 1
)
Given a set of pose estimations from a sensor array (two sensors with two independent estimations in our prototype), the goal at each time step is to select the single pose estimation that has minimum error E. The main issue is that it is impossible to track the difference in noise levels between accurate and highly inaccurate pose estimations. As explained previously, stable inaccurate pose estimations are a common artefact of the traditional particle filter algorithms, which makes it difficult to decide which sensor's reading is more trustworthy.

The novelty of our approach lies in intelligently determining which sensor is likely reporting the most accurate pose estimation. Specifically, we observed that even in situations with high occlusion and pose estimation error, the tracking of the palm position and orientation often remained accurate. We exploit this observation and build an SVM model that learns which hand positions and orientations are likely to be associated with higher pose estimation error. At run-time, our algorithm computes a feature vector based on each sensor's reported hand position/orientation in the local sensor space. This feature vector is then run through the prebuilt classifier in order to predict which sensor is likely providing the best pose estimation. The selected pose is then passed along for subsequent processing and gesture recognition.

For our two-sensor setup, each sensor's feature vector is composed of the following 12 floating point values per pose estimation:

1) Three (X, Y, and Z) values of the palm position relative to the sensor. 2) Three (X, Y, and Z) values of the palm plane normal relative to the sensor. 3) Three (X, Y, and Z) values of the "forward" direction of the hand (i.e., the direction where the fingers point to when extended). 4) The local "Roll" rotation of the hand. 5) The dot product between the palm normal and the direction the sensor is facing. 6) Sensor confidence estimation. This value is a floating point between 0 and 1 that is generated by an internal proprietary part of the leap motion API. Its limitations when used on its own are shown in Section IV. SVM was chosen as the classifier because almost all of the features used have a geometric meaning. Thus, we expect that in the higher dimensional space of the palm position/orientation, it should be possible to find a relatively good hyperplane that separates the spatial regions in which each sensor would perform the best.

In order to build the training data for our model, we require a set of feature vectors that are already prelabeled to indicate which sensor performed best. Several strategies are possible for generating the training data. If the setup did not use IR sensors (such as the leap motion), it may be possible to use an IR-based motion capture rig such as OptiTrack1 with markers on the fingertips during the training process. Alternatively, data gloves with only minimal error levels can be used if they are not bulky enough to skew the results. In Section IV, we demonstrate our approach through a third option, where we use an articulated artificial hand model with a known pose to represent ground truth for the training and evaluation data.

As is typical of an SVM training approach, the time required for training the offline model depends on the number of training samples and number of features used. In our implemented prototype, the training time for 108 data points with 12 features each was less than 0.1 s when executing on a regular computer.

C. Reprojecting Into Global and Local Spaces

After a hand pose is selected from the sensor array, it must be converted into a unified global space to interpret meaningful gestures or interactions. The matrix used to determine the hand pose in the global space can be defined manually if the placement of sensors is known precisely enough, such as in our proposed two-sensor setup. In general, for an array of multiple sensors, the user can use several static finger positions visible from each sensor to build a set of 3-D point clouds, and then apply an iterative closest point algorithm [START_REF] Besl | Method for registration of 3-D shapes[END_REF] to compute the specific matrix required to project the points from each sensor's local coordinate system into the global coordinate system.

Similarly, we also compute a projection into a local hand coordinate space to help in gesture recognition. If we consider a hand with a normalized palm direction vector ĥN (i.e., normal to the plane of the palm and in the same direction as the palm), and a normalized orthogonal forward vector ĥF , we can compute an additional basis vector ĥC for the local hand coordinate system as the cross product of these two:

ĥC = ĥN × ĥF .
(

The main challenge in this step involves determining ĥF , the "forward" direction of a hand. Multiple definitions are possible, but given the sensor data available, we define the forward direction of the hand based on the mean direction of all tracked fingers. This means that for n tracked fingers with normalized direction vectors d1 , ..., dn , we compute the unnormalized mean forward direction d M as shown in

d M = n i=1 di n . ( 3
)
We then project this computed vector onto the palm normal plane (provided directly from the sensor data) and normalize the result as shown in

ĥF = d M -( ĥN • d M ) ĥN ||d M -( ĥN • d M ) ĥN || . ( 4
)
With the three basis vectors of the local hand coordinate system computed, and the known position of the hand palm (T ), we construct a matrix M that transforms fingertip positions and direction vectors from the global coordinate system into the local hand coordinate system

M = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ h Ĉ x -h N x -h Fx T x h Ĉ y -h N y -h Fy T y h Ĉ z -h N z -h Fz T z 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
.

-1 [START_REF] Wachs | Vision-based hand-gesture applications[END_REF] Note that the directions of the hand normal and forward vectors are inverted when used as basis vectors. This is because the coordinate system of the global sensor space defines the y-axis as pointing upward, and the z-vector as pointing toward the user, whereas the palm normal is defined as facing downward, and the fingers (used for the forward direction) normally pointing away from the user. The transformation is a 4 × 4 homogeneous matrix. This means that 3-D points are augmented with a "1" at the end before multiplication, and direction vectors are augmented with a "0."

D. Gesture Detection

Finally, after the hand pose is computed in the local and global spaces, we perform gesture recognition on the computed poses. We use gestures which are intuitive to the users. The interactions are based on a combination of three basic movements: air-taps, pinches, and dragging (or swiping). Finger air-taps are analogous to clicking mouse buttons or tapping a touch screen with the finger, but in mid-air. In our gesture interfaces, this is used to select items. The air-tap was chosen because it can be recognized robustly, and previous studies have demonstrated that most users find the gesture easy to learn and remember [START_REF] Vogel | Distant freehand pointing and clicking on very large, high resolution displays[END_REF], [START_REF] Fikkert | Gestures for large display control[END_REF]. Similarly, pinch gestures in the air are essentially the same as those used on touch screen for zooming. Dragging (or swiping) refers to moving the hand, while at least one of the fingers is in the tap-down state (i.e., performing the first half of an air-tap, but halting before raising the finger). This is analogous to dragging file icons on a computer interface while having a mouse button down, or dragging objects across a touch-screen display with a fingertip, or swiping between pages displayed on a tablet computer. Our framework also allows pinch-dragging.

In past studies, hidden Markov models have been effective for gesture recognition in appearance-based systems [START_REF] Wilson | Hidden Markov models for modeling and recognizing gesture under variation[END_REF]. In our case, however, because the actual finger positions are known with high accuracy, we use the current state of the fingers directly in a finite-state machine model, without the need for indirectly modeling hidden states. The result is a computationally inexpensive direct analysis of the finger states. Fig. 5 shows a graph summarizing the state transitions of our gesture interface design.

1) Tap and Pinch Recognition: Using our local coordinate system, it is easy to suggest that an air-tap is performed when a finger moves to a local y value exceeding a threshold value. However, observations show that false positives can occur when the user's hand is in a relaxed state, probably due to fatigue over time as shown in Fig. 6(c) and(d).

Thus, we adopt an adaptive approach, taking other fingers into consideration, to compute the threshold y value of the downward distance a finger must move in order to be classified as an air-tap. It is computed using the following equation:

T f = D T (1 + W T m T ) (6)
where T f is the threshold value in millimeters (in the ydirection), that the finger f must move downward in order to be recognized as an air-tap, D T is the default threshold value for an air-tap assuming all the other fingers are in the plane of the palm, and W T is a constant weighting factor. m T is the mean y position of all other fingers besides the finger f in our partial pose estimation model. Once a finger has been recognized as being in the tapped state, i.e., having passed below T f , we require that it returns to the palm plane through a different upper threshold value U f , in order to be recognized as the untapped motion, where Fig. 6 illustrates the tap recognition corresponding to the ideal and relaxed hand states. A similar concept is used for pinch recognition, except that the computational complexity of the palm plane and neighboring fingers is reduced. For pinch recognition, we define two thresholds: an enter threshold, and a larger release threshold. When the Euclidean distance between the index finger and thumb drops below the enter threshold (e.g., 15 mm), a pinch gesture will be recognized as "Started." When the distance between the two pinching fingers exceeds the exit threshold (e.g., 25 mm), the pinch is recognized as "Ended."

U f = c(T f ), 0 < c < 1. (7)
2) Drag or Swipe Recognition: Drag gestures are recognized as hand movements that occur when one or more fingers are in the down position of an air-tap, or a pinch. Unlike interaction on a touch screen, where the user drags virtual items according to the position of their finger tip, in our model, items are first selected by the user's fingers, but then dragged according to the hand position. This is due to the lack of haptic feedback in mid-air gestures, which makes it difficult to distinguish the movements of communicative tap gestures from the movements used to manipulate the position of a virtual object. Our recognition technique is similar to using mouse buttons for selections and hand palm movements (i.e., mouse movements) to move objects on a computer screen.

IV. EVALUATION WITH GROUND TRUTH

In our experiments, ground truth values for hand poses were determined by using an artificial hand model that was manually placed into fixed and known poses. Since there are a large number of usable hand poses that could be created, we focus on tracking three hand poses that can replace certain commands commonly used on touch-screen interfaces. These three hand poses are the following:

1) an open hand;

2) a pinch gesture; 3) a tap gesture. These gestures are shown in Fig. 7.

The articulated artificial hand model has dimensions similar to that of a male right hand. Fingers are approximately between 7.0 and 10.5 cm in length, and the entire length of the hand from the bottom of the palm to the tip of the middle finger is approximately 20.5 cm when fingers are fully extended. It was observed that the tracking accuracy of the artificial hand was roughly equivalent to that of a normal human hand.

In order to investigate the ability of our multisensor technique to track these hand poses when the hand is moving, we fixed the hand position in the middle of the field of view of both sensors (placed 20 cm away) and slowly rotated the artificial hand counterclockwise along the axis of the wrist as shown in Fig. 8. The rotation was paused every 10 • in order to record a measurement from each sensor. This resulted in 36 pairs of pose estimations per gesture and 108 pairs of pose estimations in total.

We then computed the pose estimation error of each sensor for all 108 cases. To train our computational model, we constructed all 108 feature vectors and labeled every case with the sensor that produced the lower pose estimation error. Note that the average pose estimation performance of both sensors were identical because both sensors eventually saw all the exact same hand poses from the same distance and rotation angle (but not at the same time). We evaluated the performance of our model using a tenfold cross validation across all 108 data points, which is a standard approach commonly used by classification techniques.

A. Performance Analysis

Overall, the experimental results indicated that our approach reduced the total pose estimation error by 31.5% compared with using only one sensor. We summarize the performance comparisons in Tables I andII. The average pose estimation error (in millimeters) is calculated from the sum of the Euclidean distances (in millimeters) of each fingertip from its ground truth position [see [START_REF] Rossol | Touchfree medical interfaces[END_REF]] divided by the number of fingers. Using this metric, the worst-case and best-case performances were found to be 21.45 and 9.5 mm, respectively (see Table II). The worst case represents the theoretical worst average pose estimation error that could result from our approach. For it to occur, our classifier would need to incorrectly choose the sensor with the worse pose estimation every time (i.e., have 0% accuracy). Similarly, the best case represents the result if our approach consistently chose the sensor with the smaller pose estimation error. In this context, our approach is able to achieve an optimal accuracy of 90.8% on the average.

B. Comparison with Alternative Approaches

The result obtained from a single sensor shown in Tables I and II represents the average amount of pose estimation error. Given our symmetric setup, it is also the amount of pose estimation error expected if we choose randomly between the two sensors. Although the mean sensor pose estimation error was approximately 15.48 mm, there was quite a large variation in estimation error across the dataset with a maximum recorded error of 114.24 mm, and the minimum recorded error of less than 0.07 mm. When the pose estimation error exceeded 30 mm, the sensor was producing a pose estimation that was substantially different from the ground truth. There were about 22 such cases in our dataset of 108. Thus, we conclude that occlusion can make the pose estimation performance of a single sensor unreliable.

We also analyzed the performance of using unweighted averaging to fuse pose estimations. That is, for each finger in the local hand coordinate space, the final pose is the midpoint between the two sensors' estimates. This technique generates results similar to those from a Kalman filter. Based on our experiments, the method can help reduce the errors from infrequent poor pose estimations. A drawback is that if the system enters a state where the user's hand pose is constantly at a poor viewing angle for one sensor, the averaging will increasingly reduce the overall pose estimation accuracy.

Another comparison was with using the leap motion sensor's self-reported confidence score. In this measurement, the sensor with the higher reading is selected based on their reported confidences using a scale of 0 to 1. This approach showed approximately 76% accuracy, suggesting the feasibility of including this parameter in the training model. However, it is ineffective by itself in comparison with our approach, which has better performance by taking the palm position and orientation into account. Furthermore, not all depth sensors provide self-reported confidence scores.

Our technique aims at generating a fused sequence of optimal poses over time. We also analyze the "Weighted Fusion" method, which fuses the sensor output at each time step. In this approach, we fit a logistic regression model to the SVM outputs in order to produce probability estimates indicating how confident the model was with each selection. We then used these values directly to compute a combined weighted average of the hand poses. The results showed that the weighted fusion method did not perform as well as our proposed approach. For example, in cases of high occlusion, the weighted fusion method can have hand pose estimations that are well over 10 cm away from the ground truth, while our proposed method has higher accuracy (see Tables I andII).

Our analysis using a paired one-tailed t-test showed that there was a significant difference (α = 0.05) in the scores for our approach (mean = 10.60, std. deviation = 7.65) compared with using a single sensor (mean = 15.48, std. deviation = 11.65); t = 5.15, p < 0.0001. Similarly, there was a significant difference in our approach compared with using unweighted averaging (mean = 13.10, std. deviation = 7.19); t = 3.93, p < 0.0001 and also between using our approach compared with using the sensor confidence (mean = 12.29, std. deviation = 8.82); t = 2.88, p = 0.0024.

Additionally, there was a significant difference between using our weighted fusion approach (mean = 11.66, std. deviation = 10.52) compared with using a single sensor; t = 3.94, p < 0.0001, and also between using our weighted fusion approach in comparison with using unweighted averaging; t = 2.15, p = 0.0171. However, the weighted fusion approach did not show a significant difference from the sensor confidence approach; t = 0.74, p = 0.231. In light of this, we recommend the use of our original approach for most applications.

C. Analysis of Classification Performance

A unique aspect of our system's performance is that while our approach was about 90.8% optimal in terms of reducing the mean pose estimation error, our classifier accuracy was only 76.9% (i.e., 83 correctly classified instances out of the total 108). Normally, one would expect that this would result in the final performance being similar to around the 76.9% value. In order to investigate this deviation, we compared the difference in pose estimation error between the correctly and incorrectly classified instances.

A large difference in the pose estimation error between the two sensors for a data point typically indicates that the sensors had a large disagreement between each other, and that likely one of them (but perhaps both) was producing a very low quality pose estimation. When the difference between the two sensors was low, it indicates that both sensors were likely producing very similar pose estimations, and thus, the choice of which sensor to use was less important. In our analysis, we computed the difference in sensor pose estimation errors for all our data points. The corresponding distributions are shown in Fig. 9. Note that 1) instances having a higher median (difference in pose estimation error) are correctly classified, and 2) cases with the worst outliers are also classified correctly. 9. This plot shows the distribution of the level of disagreement between the sensors for correctly and incorrectly classified instances. Note that when disagreement between the two sensors is high (probably due to occlusion), our approach was able to classify correctly (left half of plot). When the data point was incorrectly classified, the difference between the sensor measurements tended to be small (right half of plot), and thus, it did not add significant error by choosing one sensor or the other. This shows that our approach can achieve high overall accuracy.

Our analysis shows that for the correctly classified instances, the median difference between pose estimations was 11.44 mm. For the incorrectly classified instances, the median difference was only 4.47 mm. This verifies that in cases where there was a large disagreement between the two sensors, our approach often made the correct decision. The missed instances were cases where the sensors only had a small level of disagreement. This analysis shows that our approach successfully eliminates the worst pose estimations in most cases.

V. CONCLUSION

We have presented a novel technique for improving full hand pose recognition accuracy from multiple sensors at frame rates in excess of 120 pose estimations per second. Our technique achieves this through a computational model, which is built to intelligently select the more accurate pose estimation at each time step, based on a subset of the underlying pose estimation data from each sensor. Our technique is most useful for improving the quality of tracking accuracy for gesture-controlled display interfaces, including medical interfaces. Our experimental results show that we were able to reduce the overall pose estimation error by over 30% in a two-sensor setup relative to the single sensor approach.

Other techniques that attempt to evaluate high-resolution images at high sampling rates from a large number of sensors quickly run into hardware limitations, computational challenges, and bandwidth constraints. In comparison, our approach is able to scale better with a large number of sensors because the data processed (i.e., the pose estimations) are at the skeletal pose level and are much smaller. A key contribution of our work is that it demonstrates the viability of combining pose estimations from multiple sensor systems, even without the presence of the underlying image data.

Fig. 1 .

 1 Fig. 1. Example setup used in our lab to capture a single hand pose from two different viewing angles.

Fig. 2 .

 2 Fig. 2. Hand poses and sensors are labeled from (a) to (j). In the pair of images on the left, the open hand pose (a) is visible by both sensors as (b) and (c). The sensors give a similar pose estimation (d) and (e) in their local sensor coordinate spaces.In the pair of images on the right, a pinch pose (f) is tested. The sensor on the left has a fairly good view (g) and gives an estimate of (i). However, this pose is mostly occluded and seen as (h) from the right side sensor, which leads to an estimate of (j). Note that the pinch pose has become an open hand, which disagrees with the left sensor.

Fig. 4 .

 4 Fig. 4. Diagram of our two-sensor setup. A small nonreflecting object is placed between the sensors to prevent a direct line of sight.

Fig. 5 .

 5 Fig. 5. Overview of the state transitions of our gesture interface design.

Fig. 6 .

 6 Fig. 6. Overview of the tap recognition system, which illustrates the importance of defining dynamic thresholds. The dashed magenta line indicates the palm plane as reported by the sensor. The solid magenta line indicates the side view of the offset plane parallel to the palm plane, but offset according to the average displacement of the fingertips relative to the palm plane. The solid green line indicates the threshold that must be exceeded to enter the tap down state. The dashed green line indicates the threshold that the finger must be above to return to the Open state. (a) Ideal case where the user's fingertips are mostly lying in the palm plane. (b) Tap gesture is easy to recognize. (c) More realistic case where the user has taken a more relaxed hand posture over time. (d) Tap gesture is not easy to recognize (bottom right).

Fig. 7 .

 7 Fig. 7. Three ground-truth hand poses tracked by our system.

Fig. 8 .

 8 Fig. 8. Artificial hand model was mounted such that it was fixed in space relative to the sensors and rotated along the axis of the wrist.

Fig.

  Fig.9. This plot shows the distribution of the level of disagreement between the sensors for correctly and incorrectly classified instances. Note that when disagreement between the two sensors is high (probably due to occlusion), our approach was able to classify correctly (left half of plot). When the data point was incorrectly classified, the difference between the sensor measurements tended to be small (right half of plot), and thus, it did not add significant error by choosing one sensor or the other. This shows that our approach can achieve high overall accuracy.

TABLE I

 I

		EXPERIMENTAL RESULTS
	Technique	Finger	Estimation Err. (mm)	Std. Err
	Single Sensor	Thumb	14.20	1.22
		1st Finger	18.40	1.87
		2nd Finger	15.51	1.55
		3rd Finger	16.29	1.08
		4th Finger	12.98	1.06
		Mean	15.48	1.12
	Averaging	Thumb	11.39	0.78
		1st Finger	16.22	1.19
		2nd Finger	13.27	1.00
		3rd Finger	13.79	0.67
		4th Finger	10.83	0.67
		Mean	13.10	0.69
	Sensor Confidence	Thumb	11.23	0.86
		1st Finger	14.26	1.49
		2nd Finger	12.61	0.97
		3rd Finger	13.14	0.94
		4th Finger	10.24	0.83
		Mean	12.29	0.85
	Weighted Fusion	Thumb	9.56	1.00
		1st Finger	13.44	1.61
		2nd Finger	12.89	1.54
		3rd Finger	12.56	0.91
		4th Finger	9.88	0.78
		Mean	11.66	1.01
	Our Approach	Thumb	9.53	0.85
		1st Finger	10.09	0.97
		2nd Finger	10.74	0.77
		3rd Finger	12.49	0.88
		4th Finger	10.14	0.84
		Mean	10.60	0.74

ROSSOL et al.: MULTISENSOR TECHNIQUE FOR GESTURE RECOGNITION THROUGH INTELLIGENT SKELETAL POSE ANALYSIS

http://www.optitrack.com

ACKNOWLEDGMENT

The authors would like to thank S. Khan for his input and feedback.

by the Natural Sciences and Engineering Research Council of Canada and Alberta Innovates Technology Futures. This paper was recommended by Associate Editor J.


A Firouzmanesh

I Cheng

A Basu

Keywords: Motion Capture, Compression, Perception of Animation, Online 3D Environments. Perceptually Guided Fast Compression of 3D Motion Capture Data

A time efficient compression technique, incorporating attention stimulating factors, for motion capture data is proposed. Compression ratios of 25:1 to 30:1 can be achieved with very little noticeable degradation in perceptual quality of animation.

Experimental analysis shows that the proposed algorithm is much faster than comparable approaches using wavelets; thereby making our approach feasible for motion capture, transmission and real-time synthesis on mobile devices, where processing power and memory capacity are limited.

I. INTRODUCTION

SING motion capture data is an effective way to produce skeletal animations. In online applications, efficient compression of motion capture data can contribute to optimal use of available bandwidth while preserving the transmission of higher quality animation. In recent years, different approaches have been proposed to address the motion data compression problem. However, none of them directly discusses the possibility of achieving further reduction in data size with little noticeable perceptual degradation, considering the human visual system.

Even though perceptual factors in image and video have been widely studied [START_REF] Ramos | Perceptual quantization for waveletbased image coding[END_REF], there is no existing qualitative metric [START_REF] Pan | Quality metric for approximating subjective evaluation of 3D objects[END_REF] that considers different aspects of perception in animation. Thus, in this paper we propose a technique for perceptually guided compression of motion data, considering some of the most important factors, which can affect the perception of animation.

Motion capture refers to "the process of recording movement and translating that movement on to a digital model" [START_REF] Wikipedia | Motion capture[END_REF]. Motion can be recorded using optical, mechanical or magnetic devices by tracking the movements of key points (such as joints) on an object (Figure 1). Motion capture is useful in many applications including military, entertainment, sports, medicine, computer vision and robotics. In computer animation, motion capture data can be used to create realistic 2D and 3D animated characters.

Motion data are usually sampled at frequencies between 60 to 240 Hz. A hierarchical biped structure (skeleton) is typically used to coordinate the relative position and movement of each child key point with respect to its parent key point. The movement of a key point can be precisely described using 9 degrees of freedom (3 translations, 3 rotations, and 3 scaling factor) in the x-, y-and z-coordinates. We use the term channel to associate with one degree of freedom (DOF), tracing the trajectory of a key point during the entire motion sequence (animation). Given a defined number of key points, the size of each channel is dictated by the number of frames captured. Thus, if k markers are used to capture the movements of k key points in an n-frame sequence, the motion sequence can be encoded in 9k channels, with each channel recording n numbers defining the state of a key point at each of the n time slots. It is possible that the values of some channels remain zero during the entire animation. For body animation, very often movement of the whole object can be defined using at most 3 rotational DOF for each marker, plus 3 translational DOF for the whole object.

In online and interactive applications, motion capture data can consume a large amount of bandwidth especially when multiple dynamic characters are present in the scene. An important characteristic of realistic motion data is a considerable amount of spatial correlation between the different data channels and temporal correlation within each channel, which if processed and compressed effectively can reduce the data size considerably.

The primary motivation of this work is efficient data transmission for interactive online 3D environments (such as online games). To this end we propose a method which is capable of achieving an equivalent or better compression ratio compared to the state of art methods while consuming a much shorter compression and decompression time.

The rest of this paper is organized as follows. Section II introduces the basic concepts of motion capture in computer animation, reviews some of the important motion data compression approaches, and discusses their shortcomings for online transmission of interactive data. In the same section we also review the study results on human perception of animation. The proposed method is discussed in Section III followed by experimental results in Section IV. Finally concluding remarks and future work are outlined in Section V.

II. RELATED WORK

Current approaches to compression of motion data can achieve compression ratios of 25:1 to 35:1 without noticeable perceptual degradation [START_REF] Arikan | Compression of motion capture databases[END_REF], [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF]. However each approach has some deficiencies in addressing the requirements of online 3D applications as discussed below.

A. PCA Based Approach

Arikan [START_REF] Arikan | Compression of motion capture databases[END_REF] proposed a method that can compress large databases of motion capture data, using a ratio from 30:1 to 35:1, with minimum amount of degradation in perceptual quality (Fig. 2). The input database consists of a file describing the skeleton structure of the animated character, plus a (typically large) number of motion clips. In their experiments they used two databases. The first one contained 620K frames sampled at 120Hz (1:30 hours long). The second one was the Carnegie Mellon motion capture database containing 2.9M frames sampled at 120Hz (6:30 hours long).The underlying skeleton was composed of 20 bones, coordinated with 56 DOFs.

Instead of working with joint orientation data, the authors use joint position data to avoid the problem that may arise from nonlinearity and hierarchical representation of joint orientation data. For each bone "the global position of 3 different and known points" in the bone's local coordinate is calculated. These positions are called virtual markers.

A 3D cubic Bezier curve is then fit into the 3D trajectory of each virtual marker. The vectors containing Bezier curve parameter values generated from the virtual markers are clustered using Nystrom approximation. Principal Component Analysis (PCA) is performed on each cluster, and depending on the desired accuracy a number of larger rows of the resulting matrix are selected. The (x,y,z) positions of each virtual marker on the foot are considered as separate 1D signals and compressed using Discrete Cosine Transform (DCT). While this approach achieves high compression ratios, it may not be suitable for some applications. First, for game and simulation engines that use joint angles representation, the overhead of converting marker positions to joint angles might be significant [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF]. Second, PCA based approach achieves high compression ratios by exploiting correlation between DOFs in addition to temporal dependencies within each DOF. However, it might be desirable to achieve the same compression ratio while encoding each channel separately. For example, in some applications it is useful to combine different motion files to generate a new motion (e.g., combining upper body of one motion with lower body of another one). Finally, this approach achieves high compression ratios only when applied to a large motion database, but for individual motion files with relatively small number of frames the compression ratio can be significantly lower [START_REF] Arikan | Compression of motion capture databases[END_REF]. This is because high compression is achieved when PCA is applied on large clusters.

B. Wavelet Based Approach

Using wavelet to compress the motion files can solve most of the problems in the PCA based approach discussed above. High compression ratios with low perceptual degradation can be achieved without exploiting the correlation between DOFs and without the overhead of converting joint angles to marker positions and vice versa. In wavelet based methods one dimensional wavelet transform is applied to each channel of motion data (Fig. 3). Depending on the desired compression ratio a percentage of the wavelet coefficients are kept and others are set to zero. This process is followed by quantization, run length encoding and entropy coding to produce the compressed output stream. Baudin et al. [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF] proposed optimal wavelet coefficient selection for motion data compression. Their approach applies a distortion metric that takes into account the difference between the positions of each joint before and after compression, and gives higher weight to joints with more local influence (based on the length of the bone attached to the joint). Given a desired compression ratio, an optimal number of wavelet coefficients are selected for each channel, such that the distortion is minimized. Since the coefficient search space is very large, a discrete optimization algorithm is used to estimate the best solution. In order to reduce the artifacts related to foot skating, the difference between the actual position of a foot before and after coefficient selection is stored. For decompression, an inverse kinematic solver is used to correct the position of joints after moving a foot to its actual position. Their studies suggest that a compression ratio of 25:1 (for short motions) to 35:1(for longer motions) can be achieved without any noticeable visual degradation. While generating promising results, this approach has a number of shortcomings. First, the compression is very time consuming (133-327 ms per frame on a 2GHz AMD Athlon 64 bits) mainly because of the process of allocating an optimal number of coefficients to each channel. Also, the compression time per frame has a direct relation with the number of frames in the animation. Second, the error metric used for optimization is highly dependent on the joint hierarchy. In other words, giving more weight to the joints with high error rates does not necessarily yield good results.

C. MPEG-4 Bone-based Animation

In 2004 Bone-based Animation (BBA) was included in the MPEG-4 standard [START_REF]Animation Framework eXtension (AFX)[END_REF]. Motion is represented by variations in the DOF of joints in a skeleton (as described in Section I). For each frame, a binary string is used to record which DOF is modified, and only the values of the modified DOF are stored and transmitted.

Preda et al. [START_REF] Preda | Optimized MPEG-4 animation encoder for motion capture data[END_REF] proposed two different methods for encoding and transmitting BBA. The first method is based on predictive coding followed by quantization and entropy coding. The second one consists of applying one-dimensional Discrete Cosine Transform (DCT) on each DOF in the skeleton, followed by quantization and entropy coding. They also proposed a frame reduction technique to achieve higher compression. Compression rates of the input BVH files vary from 5:1 to 45:1 depending on the method (DCT resulting in higher compression) and parameters, e.g., quantization parameter, used.

D. Other Approaches

Onder et al. [START_REF] Onder | Keyframereduction techniques for motion capture data[END_REF] presented two methods to reduce the number of key frames in a motion capture file. The first method is fitting a Hermite curve to each channel of motion data (rotation angles) using a dynamic programming approach. A Hermite curve can be reconstructed by specifying control points and tangent vectors. In the second method they use a curve simplification algorithm to represent each channel of data by a few keyframes. They applied their proposed methods on a short (22 frames) and a relatively long (1409 frames) motion. Both methods were capable of reducing the number of keyframes by 75-80% without any noticeable perceptual degradation. While the compression ratio is not as high as other approaches, their methods may be useful in editing motion data and motion understanding.

Tournier et al. [START_REF] Tournier | Motion Compression using Principal Geodesics Analysis[END_REF] proposed a method based on Principal Geodesics Analysis (PGA) that exploits both temporal and spatial redundancy of motion data. PGA is an extension of PCA in non-Euclidian space (such as joint rotation angles). Joints in the skeleton are divided into three groups and each group is compressed in a different way. Root position and orientations are compressed using a lifting scheme. End-joints trajectory can be compressed using any standard linear compression methods, such as wavelets. PGA is performed on the rotation angles of inner joints. For decompression, a PGAbased inverse kinematics is applied that can recover the original position of inner joints using the root and outer joints positions. The authors reported a compression ratio of 18:1 to182:1 for different types of animation. While this method achieves high compression for some motion data, it has a few drawbacks. First, the decompression is very time consuming because of the inverse kinematics. Also, the average decompression time per frame is directly related to the number of frames. Finally, the compression ratio varies significantly for different types of motion which is not desirable in online applications.

E. Measuring Perceptual Quality of Motion

The research on measuring the perceptual quality of animation is still in its early stage. A closely related problem is determining whether a motion is perceived as natural by human subjects. Approaches to quantifying natural human motion can be divided into three categories [ category is defining some constraints on the movements of joints and looking for violation of these constraints. Two examples are conservation of angular momentum in flight, and "violation of the friction cone when the foot is in contact." Another category, which will be discussed more below, is to define some threshold on the percentage of error in different aspects of animation (such as change in lengths, horizontal and vertical velocities, etc.) that can be obscured. The third category is to train a classifier based on data labeled by humans as natural or unnatural motions.

Reitsma and Pollard [START_REF] Reitsma | Perceptual metrics for character animation: Sensitivity to errors in ballistic motion[END_REF] performed experiments to measure the sensitivity of human subjects to violation of some of the laws of physics as a result of changes to the motion data. They systematically added errors to human jumping motion and measured the ability of subjects to detect these errors. Results of their studies suggest that: (1) Added acceleration is easier to detect than added deceleration; (2) Detection of low gravity is easier than high gravity; (3) Errors in horizontal velocities are easier to detect than errors in vertical velocities. They also proposed a formula to estimate the level of acceptable error, but mentioned that the specific results depend on many other factors including complexity of the geometric model.

Pollick et al. [START_REF] Pollick | Visual perception of humanoid movement[END_REF] studied the factors affecting perception of human movements. Results of their study suggest that for fast movements the judgment is mostly based on the velocity, while for slower, movements velocity along with another factor (not precisely defined) is used to distinguish between similar looking motions. Harrison et al. [START_REF] Harrison | Obscuring length changes during animated motion[END_REF] performed a series of experiments to measure human sensitivity to changes in length in animation considering the effects of expectation, task interference, increase vs. decrease in length, duration of length change and division of attention. As a result of their studies, the authors suggest several guidelines for obscuring length changes in animation including: (1) A length change of up to 2.7% is almost unnoticeable by a human observer; [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF] The change in length should not exceed 20% under any condition;

(3) People are more sensitive to increase in length than to decrease; (4) Faster changes are more noticeable; (5) Sensitivity to length changes decreases during fast motions.

Ren et al. [START_REF] Ren | A Data-Driven Approach to Quantifying Natural Human Motion[END_REF] investigated the possibility of developing a measure for quantifying the naturalness of human motion by training different classifiers (including a mixture of Gaussians, hidden Markov models, and switching linear dynamics systems) with a large database of motions. None of the classifiers were able to classify the test data with very low error rates. Also, they mention that this approach suffers from a few shortcomings including: (1) The measures may not be valid for motions that are significantly different from the training data; (2) Some types of error may not be reliably detected (for example, error occurring within a very short duration of time).

III. PROPOSED METHOD

The aim of this work is to develop a technique for lossy compression of human motion capture data for online applications considering the following requirements: (1) Encoding and decoding should take a small portion of the processing resources (not just real time), since transmitting 3D animation online involves many other tasks with high resource demands besides the transmission of motion data; (2) It should be able to incorporate human perceptual factors of animation into the technique.

Among the different motion capture data compression methods discussed in the previous section, we find that wavelet coding provides the best technique considering the requirements mentioned above for several reasons. First, wavelet encoding proved to be one of the most efficient approaches for encoding multimedia data [START_REF] Gonzalez | Digital Image Processing[END_REF]. Second, even without considering spatial dependencies between motion channels, high compression ratios can be achieved. Finally, it is relatively straightforward to adjust the perceptual quality of motion. This is because each channel is encoded independently, and so if research studies show that one joint should be encoded more accurately, then the wavelet coefficients of the channels relating to that joint can be compressed with a lower ratio.

The basic idea is to select different numbers of coefficients for different channels of data based on the importance of each channel on the perceived quality of motion. Also, based on global properties of the object (such as distance from camera, number of objects present in the scene, degree of attention, etc.) the total number of coefficients to be transmitted could be multiplied by a factor (between 0 and 1). We did not use a global optimization method (such as that in [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF]) because: (1) Either the compression or decompression would require high processing resources, which is not suitable for the intended application; (2) As discussed in [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF], global optimization approaches might not provide good results when the distortion metric is not "dependent enough on the joint hierarchy." This would be the case if the distortion metric gives higher weights to the error of some joints (e.g., joints in contact with the environment).

In this work we try to optimize the coefficient selection algorithm considering two important factors. The first factor is the length of the bone connected to a joint. Larger bones have greater effect on the perceptual quality of an animation than smaller bones. It should be noted that we are considering the effect of a joint on the whole hierarchy because: (1) We are concerned with the perceptual quality of the coordinated animation, and not the individual position of each joint; (2) Finding the individual effect of each joint on its hierarchy is not straightforward and may become time consuming. For example, as mentioned in [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF] "In a boxing animation sequence where the actor holds his arms close to his body, a small rotation of the torso can have less influence on the positional distortion than a rotation at the elbow or the shoulder."

The evaluation of animation quality involves multiple factors, which include not only the movement itself but also other environmental factors such as the viewer's region of interest, texture masking and scene illumination. How environmental factors affect human perceptual quality is a large research topic worth separate discussion and is not in the scope of this manuscript. In our experiments, we apply regular lighting in an empty scene mapping simple plain colors on the animated character, and assume the viewer focuses on the animated character. This experimental setting provides a high likelihood for majority of the viewers to discover any artifact in the animation.

In order to locate the high attention regions, we apply the Interactivity-Stimulus-Attention Model (ISAM) [19], which explains how interactivity stimulates immersion of cognitive resources. ISAM was validated by involving 700 participants in their user studies. We hence assume that the amount of attention focused on a region is proportional to the amount of activity associated with that region. Similarly, in a motion sequence where the character moves its left hand more often but its right hand remains almost still, we assume the viewer pays more attention to the area around the left hand. In order to compare the amount of activity for each DOF, we measure the sum of its variation in a set of consecutive frames (see Step 4 of the proposed algorithm below).

The proposed method can be described by the following steps. Each channel of data (

N i c i ≤ ≤ 1 ,
) represents one DOF (usually rotational) of a joint of the skeleton. α is an input parameter to the algorithm indicating the percentage of the wavelet coefficients to be kept for the whole animation. The other inputs are QP (quantization parameter) in bits, and W (window size) which contains the number of frames that are compressed together in a single slice. The output of the algorithm is the compressed wavelet coefficients of the motion file. The processing steps are: 1. Divide the animation into M slices, having W frames in each slice (with the exception in the last slice, which can contain less than W frames).

For each slice

k m ( M k ≤ ≤ 1
) perform Steps 3 to 9:

3. Since the animated characters can be of different sizes, we use the normalized values (or relative measurement) to provide a comparable basis. Thus, for each channel we obtain the normalized bone length ( i l ) by dividing the bone length attached to the corresponding joint by the maximum bone length in the skeleton. 4. Find the variation of each channel ( i c ) using the following formula:

W c c v W W m W m p p i p i i i i ∑ - + = + - = 1 * * , 1 , (1)
5. Combine the effects of relative bone length and variation to obtain a weighted quantity ( i A )

representing the relative importance (perceptual impact) of each channel.

i i i v l A = (2) 6. For each channel compute ) , max( 1 C A NW A K N j j i i ∑ = = α
, the largest (in absolute value) wavelet coefficient, and set other coefficients to zero (where C is a constant representing the minimum number of wavelet coefficients kept for each channel). 7. Quantize the remaining wavelet coefficients linearly into QP bits. 8. Use run-length to encode the wavelet coefficients. 9. Use an entropy coding method to compress the data.

IV. EXPERIMENTAL RESULTS

We implemented our compression algorithm using the C programming language. Daubechies D4 wavelet was used for encoding data. We used the Carnegie Mellon University ASF/ASM viewer [START_REF]CMU Graphics Lab motion capture database[END_REF] in our user studies. LZW compression [START_REF] Li | Fundamental of Multimedia[END_REF] was used as the entropy coding method. The input data were in "asf" format, which described the skeleton structure; and in "amc" format, which defined the movements. In order to provide a format independent estimation of compression ratio, the motion data is converted into arrays with IEEE 32 bit (4 bytes) floats precision, where every 4 bytes represent one DOF in a frame. The skeleton hierarchy used was composed of 20 bones, controlled by a total of 56 DOFs (the number of DOFs does not change from frame to frame), and thus the input size was 56x4x(number of frames) bytes.

We performed a user study using two short motion sequences from the CMU [START_REF]CMU Graphics Lab motion capture database[END_REF] motion capture database. The first one labeled 2_2 is a simple walking motion and the second one labeled 49_14 is a dancing sequence. Both motions were captured at the rate of 120 frames per second. The motion sequences were compressed using three methods: 1-The proposed method with both bone lengths and variation in the degrees of freedom being taken into account; 2-The proposed method but only bone lengths being taken into account; 3-Standard wavelet compression (setting the same percentage of coefficients to zero for all the channels). For our method, motions were compressed using different parameters, e.g., quantization parameter (QP) and window size. A few sample videos of the original and compressed motion can be found at http://cs.ualberta.ca/~firouzma/mocap. Fifteen computer science students from the University of Alberta participated in this user study and were able to compare side by side the original and compressed motions. The latter were shuffled in random order before being presented to the users, who were asked to rank their quality from 1 to 5 in 0.5 steps, 5 being the best quality. Before starting the evaluation the users were introduced to the concept of quality degradation due to motion data compression. A total of 76 (38 for each motion) compressed motions were presented to the users in a random order. The compressed motions were generated by applying the two cases (with and without bone length) of our proposed method, and standard wavelet compression; using different compression ratios (1:10 to 1:70), different QPs (7 to 11) and different window sizes (64 to 256). Eight (four for each sequence) compressed motion files appeared twice in the test set. The users were allowed to see each motion as many times as they wanted but the total time of the test was limited to 40 minutes. Before starting the test a few compressed motions with a wide range of compression ratios (from 10:1 to 70:1) were shown to the users to help familiarize them with the difference in qualities.

Fig. 5 reports the user study results: The mean opinion score (MOS) for compression ratios from 20:1 to 40:1 for QP=9 and window size of 256 frames using the proposed method. The error bar represents confidence interval ( 05 . 0 = α ). Observe that for a compression ratio lower than 25:1 our method gets an average score of around 4.5 which indicates very little visible difference (and no difference to some viewers) between the perceptual qualities of the original and compressed motions. Also, for compression ratio 35:1 the average quality score is still close to 4.

Fig. 6 compares the quality scores of the proposed method with standard wavelet compression. For compression ratios over 30:1 our method shows a statistically significant improvement over the standard wavelet compression (the P-Value of one-tailed t-test comparing MOS of proposed method and standard wavelet compression with the same compression ratio was less than 0.05 for all the experiments).

In order to verify our choice of variation in rotation degrees as an attention factor we compare the quality of compressed motion using the proposed method (both bone lengths and variation in rotation) and the case where only bone lengths are considered (Fig. 7). Here again the results show a significant improvement when both factors are considered. The compression times of three motion files with different number of frames are shown in Table I. The compression times for shorter clips are not reported because animations in real time applications are much longer. Also, the imprecision in the timer can distort the results for short clips. The program was executed on a desktop computer with an Intel Core 2 Duo 2.66 GHz processor and 2 GB of memory. We can see that the average compression time per frame is about 25 µs for relatively long motion files, which demonstrates that the algorithm has very efficient processing time. It is reported by the adaptive wavelet compression method [START_REF] Beaudoin | Adapting wavelet compression to human motion capture clips[END_REF] that, for short sequences, a compression ratio of 25:1 is achieved without any noticeable degradation. This can be comparable to the average quality score of around 4.5 reported in Fig. 5 for the same compression ratio. The compression time reported in that paper is between 133 and 483 ms per frame on a 2 GHz AMD Athlon 64 bit which is approximately 10 4 times greater than our method. In Arikan's paper [START_REF] Arikan | Compression of motion capture databases[END_REF], a compression ratio of 30:1 is reported for compressing the whole CMU database, which contains 6:30 hours of animation at 120 frames per second (2.9M frames). However in this calculation the input files are not in 32 bit floats, but in a text based format which needs about twice as much storage. Based on the reported figures in that paper, the compression ratio is equivalent to less than 20:1 if the input is converted to 32 bit floats. Also, note that the statistics is based on compressing a very large motion database containing motion clips of various contents and lengths. It is not expected to obtain the same results when a single regular length motion clip is the target. In their case, a decompression time of 1.2 ms per frame is reported on a Pentium 4 @ 3.4 GHz which is 40 times greater than the decompression time of our algorithm.

V. CONCLUSION AND FUTURE WORK

We proposed a fast encoding and decoding technique for lossy compression of motion capture data, taking human perception into consideration. Experimental results show that our algorithm, in general, is much faster than other comparable methods. Initial studies suggest that compression ratios of at least 25:1 are achievable with little impact on perceptual quality. Since our method is faster while preserving an equivalent or better perceptual quality, the compressed motion data is more robust to constrained bandwidth, which is especially important in a mobile environment. In the current model, we introduce two attention factors: bone lengths and variation in rotation. However, there can be many other factors affecting the quality of animations, including the distance from camera, horizontal and vertical velocity of the object and the size of the limbs. Also, the efficiency of correcting contact positions using inverse kinematics [START_REF] Ikemoto | Knowing when to put your foot down[END_REF] could be further studied. We believe our work presented in this paper will inspire more interest in the research community, resulting in more attention factors to be discovered, and the mathematical model to be extended and refined.

Fig. 1 .

 1 Fig.1. An example of (left) a motion sequence captured using markers (black dots) on key points, (right) a file format of the captured data, and (bottom) a 3D trajectory generated by one key point during motion capture.

Fig. 2 .

 2 Fig. 2. PCA based approach.

Fig. 3 .

 3 Fig. 3. Wavelet Based Approach.

Fig. 4 .

 4 Fig. 4. Motion capture viewer environment.

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Results of user study on two of CMU database motion files