Abstract:
Disclosed is a method and system for efficiently and accurately tracking three-dimensional (3D) human motion from a two-dimensional (2D) video sequence, even when self-occlusion, motion blur and large limb movements occur. In an offline learning stage, 3D motion capture data is acquired and a prediction model is generated based on the learned motions. A mixture of factor analyzers acts as local dimensionality reducers. Clusters of factor analyzers formed within a globally coordinated low-dimensional space makes it possible to perform multiple hypothesis tracking based on the distribution modes. In the online tracking stage, 3D tracking is performed without requiring any special equipment, clothing, or markers. Instead, motion is tracked in the dimensionality reduced state based on a monocular video sequence.

Description:
RELATED APPLICATIONS  
       [0001]     This application claims priority from U.S. provisional application No. 60/731,399 entitled “Monocular Tracking of 3D Human Motion With a Coordinated Mixture of Factor Analyzers” which is incorporated by reference herein in their entirety. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The invention relates to tracking 3D human motion. More particularly, the invention relates to a system and method for tracking 3D articulated human motion in a dimensionality-reduced space given monocular video sequences.  
       BACKGROUND OF THE INVENTION  
       [0003]     Tracking articulated human motion is of interest in numerous applications including video surveillance, gesture analysis, human computer interface, and computer animation. For example, in creating a sports video game it may be desirable to track the three-dimensional (3D) motions of an athlete in order to realistically animate the game&#39;s characters. In biomedical applications, 3D motion tracking is important in analyzing and solving problems relating to the movement of human joints. In traditional 3D motion tracking, subjects wear suits with special markers and perform motions recorded by complex 3D capture systems. However, such motion capture systems are expensive due to the required special equipment and significant studio time. Further, conventional 3D motion capture systems require considerable post-processing work which adds to the time and cost associated with traditional 3D tracking methods.  
         [0004]     Various tracking algorithms have been proposed that require neither special clothing nor markers. A number of algorithms track body motion in the two-dimensional (2D) image plane, thereby avoiding the need for complex 3D models or camera calibration information. However, many conventional methods are only able to infer 2D joint locations and angles. As a result, many traditional 2D methods have difficulty in handling occlusions and are inutile for applications where accurate 3D information is required.  
         [0005]     3D tracking algorithms based on 2D image sequences have been proposed but depend on detailed 3D articulated models requiring significantly more degrees of freedom. Particularly, particle filtering methods have been applied widely in tracking applications. However, these algorithms have conventionally been inefficient due to the high dimensionality of the pose state space. The number of particles needed to sufficiently approximate the state posterior distribution means that significant memory and processing power is required for implementation.  
         [0006]     Several attempts have previously been made to develop particle filtering techniques in a reduced state space to ease memory and processing requirements. These efforts have largely failed to result in accurate tracking methods. Specifically, the proposed algorithms tend to fail when large limb movements occur over time.  
         [0007]     What is needed is an efficient and accurate algorithm for tracking 3D articulated human motion given monocular video sequences.  
       SUMMARY OF THE INVENTION  
       [0008]     The present invention provides a method for efficiently and accurately tracking 3D human motion from a 2D video sequence, even when self-occlusion, motion blur and large limb movements occur. In an offline learning stage, 3D motion capture data is acquired using conventional techniques. A prediction model is then generated based on the learned motions. In the online stage, 3D tracking is performed without requiring any special equipment, clothing, or markers. Instead, 3D motion can be tracked from a monocular video sequence based on the prediction model generated in the offline stage.  
         [0009]     In order to overcome the problem of high dimensionality associated with traditional particle filtering, the motion is tracked in a dimensionality-reduced state. Human motion is limited by many physical constraints resulting from the limited angles and positions of joints. By exploiting these physical constraints, a low-dimensional latent model can be derived from the high-dimensional motion capture data. A probabilistic algorithm performs non-linear dimensionality reduction to reduce the size of the original pose state space. During off-line training, a mixture of factor analyzers is learned. Each factor analyzer can be thought of as a local dimensionality reducer that locally approximates the pose state. Global coordination between local factor analyzers is achieved by learning a set of linear mixture functions that enforces agreement between local factor analyzers. The formulation allows easy bidirectional mapping between the original body pose space and the low-dimensional space.  
         [0010]     The projected data forms clusters within the globally coordinated low-dimensional space. This makes it possible to derive a multiple hypothesis tracking algorithm based on the distribution modes. By tracking in the low-dimensional space, particle filtering is faster because significantly fewer particles are required to adequately approximate the state space posterior distribution. Given clusters formed in the latent space, temporal smoothness is only enforced within each cluster. Thus, the system can accurately track large movements of the human limbs in adjacent time steps by propagating each cluster&#39;s information over time.  
         [0011]     The features and advantages described in the specification are not all inclusive and, in particular, many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]      FIG. 1  is an example computer system for executing the methods of the present invention.  
         [0013]      FIG. 2  is a block diagram illustrating one embodiment of the present invention.  
         [0014]      FIG. 3   a  is an offline learning algorithm for generating a prediction model used in 3D motion tracking.  
         [0015]      FIG. 3   b  is an online tracking algorithm for tracking 3D human motion given a monocular video sequence and the prediction model generated in the offline learning stage.  
         [0016]      FIG. 4  is a dimensionality reduction algorithm according to one embodiment of the present invention.  
         [0017]      FIG. 5  is a block diagram illustrating a learning process for a dimensionality reduction model.  
         [0018]      FIG. 6  illustrates clustering in a low dimensional space as a result of the dimensionality reduction algorithm.  
         [0019]      FIG. 7  is a flow diagram illustrating the computation performed during online tracking according to one embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]     A preferred embodiment of the present invention is now described with reference to the figures where like reference numbers indicate identical or functionally similar elements. Also in the figures, the left most digit of each reference number corresponds to the figure in which the reference number is first used.  
         [0021]     Reference in the specification to “one embodiment” or to “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.  
         [0022]     Some portions of the detailed description that follows are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self- consistent sequence of steps (instructions) leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical, magnetic or optical signals capable of being stored, transferred, combined, compared and otherwise manipulated. It is convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. Furthermore, it is also convenient at times, to refer to certain arrangements of steps requiring physical manipulations of physical quantities as modules or code devices, without loss of generality.  
         [0023]     However, all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or “determining” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices.  
         [0024]     Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by a variety of operating systems.  
         [0025]     The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.  
         [0026]     The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description below. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references below to specific languages are provided for disclosure of enablement and best mode of the present invention.  
         [0027]     In addition, the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the claims.  
         [0028]      FIG. 1  is a computer system according to one embodiment of the present invention. The computer system  100  comprises an input device  102 , a memory  104 , a processor  106 , an output device  108 , and an image processor  110 . The input device  102  is coupled to a network  120 , a database  130 , and a video capture unit  140 . The output device  108  is coupled to a database  150 , a network  160 , and a display  170 . In other embodiments, the input device is connected to only one or two of a network  120 , a database  130 , and a video capture unit  140 . In yet another embodiment, the input device may be connected to any device configured to input data to the computer system. Similarly, in some embodiments, the output device may be connected to one or more of a database  150 , network  160 , display  170  or any other device cable of receiving outputted data. In another embodiment, the computer system comprises one or more of a processor  106 , an image processor  110 , or other specialized processor.  
         [0029]      FIG. 2  is a block diagram illustrating one embodiment of the present invention. The embodiment comprises an offline learning algorithm  210  and an online tracking algorithm  220 . The offline learning algorithm  210  uses 3D motion capture data  212  to produce a prediction model  215  utilized by the online tracking algorithm  220 . The online tracking algorithm  220  uses a 2D image sequence  222  and the prediction model  215  to generate the 3D tracking data  224 .  
         [0030]     3D motion capture data  212  may be acquired by a variety of conventional techniques during the offline stage. In one embodiment, a subject wears a special suit with trackable markers and performs motions captured by video cameras. The subject may perform a series of different motions which are captured and processed. In addition, 3D motion capture data may be acquired from multiple subjects performing similar sets of motions. This provides statistical data from which the prediction model  215  can be derived.  
         [0031]      FIG. 3   a  summarizes one embodiment of the offline learning algorithm  210 . A computer system  100  receives  302  3D motion capture data  212 . The pose state is then extracted  304  from the 3D motion capture data. The unfiltered pose state resides in a high dimensional state space and it is desirable to reduce the dimensionality of the state space to decrease memory requirements and increase processing efficiency. A dimensionality reduction model is learned  306  to reduce the dimensionality of the pose state from a high dimensional space to a low dimensional space. Optionally, a dynamic model is learned  308 . The dynamic model, if learned, may optimize the prediction model  215  for more efficient tracking. The prediction model  215  is formed by generating  310  hypotheses based on the dimensionality reduction model and in some embodiments, the learned dynamic model.  
         [0032]     The motion capture data  212  may be received from a video capture unit  140  interfaced to an input device  102  of a computer system  100 . In other embodiments, the 3D motion capture data  212  may be received by the input device  102  from a database  130  or through a network  120 . The 3D motion capture data  212  is processed by the computer system  100  to extract  304  the pose states. The pose states comprise data which completely represent the positions of the subject throughout a motion. In one preferred embodiment of the present invention, the extracted pose state comprises a vector of joint angles. However, the pose state may comprise any set of data that completely describes the pose. This may include angles, positions, velocities, or accelerations of joints, limbs, or other body parts or points of interest. Any number of conventional techniques may be used to extract  304  the pose states from the raw motion capture data  212 .  
         [0033]     The 3D motion capture data  212  may be processed by a standard computer processor  106  or by a specialized image processor  110 , for example. In addition, the pose state may be stored in memory  104  or outputted by an output device  108 . The output device  108  interfaces to an external database  150  for storage or sends the data to a network  160  or a display  170 .  
         [0034]     A dimensionality reduction model is learned  306  based on the extracted pose states. The dimensionality reduction model takes advantage of the physical constraints of human motion to generate a low-dimensional latent model from high-dimensional motion capture data. Many algorithms for dimensionality reduction are known including Principal Component Analysis (PCA), Locally Linear Embedding (LLE) described in Roweis, et al.,  Nonlinear Dimensionality Reduction by Locally Linear Embedding,  Science 290, 2000, 2323-2326; Isomap described in Tenenbaum, et al.,  A Global Geometric Framework for Nonlinear Dimensionality Reduction,  Science 290, 2000, 2319-2323; and Laplacian Eigenmaps described in Belkin, et al.,  Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering,  Advances in Neural Information Processing Systems (NIPS), 2001, 585-591 all of which are incorporated by reference herein in their entirety. These conventional techniques are capable of handling non-linear behavior inherent to 3D human motion, but are typically not invertible. In one embodiment, regression methods (such as Radial Bases Function, for example) are used to learn the mapping back from the low dimensional space to the high dimensional space.  
         [0035]     In a preferred embodiment, an invertible dimensionality reduction method is used. Inverse mapping of particles back to the original human pose space allows for re-weighting of the particles given the image measurements during online tracking without using a regression method. Examples of dimensionality reduction techniques that provide inverse mapping include Charting described in Brand,  Charting a Manifold,  NIPS, 2001, 961-968; Locally Linear Coordination (LLC) described in Teh, et al.,  Automatic Alignment of Local Representations,  NIPS, 2002, 841-848; and Gaussian Process Latent Variable Model (GPLVM) described in Lawrence,  Gaussian Process Models for Visualization of High Dimensional Data,  NIPS, 2003 all of which are incorporated by reference herein in their entirety.  
         [0036]     In one embodiment, the dimensionality reduction model is based on an LLC algorithm. In this embodiment, a probabilistic algorithm is employed to perform non-linear dimensionality reduction and clustering concurrently within a global coordinate system. The projected data forms clusters within the globally coordinated low-dimensional space. A mixture of factor analyzers is learned with each factor analyzer acting as a local dimensionality reducer. In an alternate embodiment, a GPLVM algorithm or other dimensionality reduction algorithm is used.  
         [0037]     A model which performs a global coordination of local coordinate systems in a mixture of factor analyzers (MFA) is known is the art, for example, in Roweis, et al.  Global Coordination of Local Linear Models,  NIPS, 2001, 889-896 which is incorporated by reference herein in its entirety. Each factor analyzer (FA) can be regarded as a local dimensionality reducer. Both the high-dimensional data y and its global coordinate g are generated from the same set of latent variables s and z s , where each discrete hidden variable s refers to the s-th FA and each continuous hidden variable z s  represents the low-dimensional local coordinates in the s-th FA. In the MFA model, data generated from s-th FA with prior probability P(s), and the distribution of z s  are Gaussian: z s |s˜N(0,I) where I is the identity matrix. Given s and z s , y and the global coordinate g are generated by the following linear equations 
 
 y=T   L     s     z   s +μ s   +u   g , 
 
 g=T   G     s     z   g +κ g   +v   g ,   (1) 
 
         [0038]     where T Ls  and T Gs  are the transformation matrices, μ s  and κ s  are uniform translations between the coordinate systems, u s ˜N(0,          Δ u     s   ) and v s ˜N(0,          Δ v     s   ) are independent zero mean Gaussian noise terms. The following probability distributions can be derived from Eq. 1: 
 
 y|s, z   s   ˜N ( T   L     s     z   s +μ g ,          Δ u     s   ) 
 
 g|s, z   g   ˜N ( T   G     s     z   g +κ g ,          Δ v     s   ).   (2) 
 
         [0039]     With z s  being integrated out, the equation is 
 
 y|s˜N (μ s ,          Δ u     s     +T   L     s     T   L     s     T ) 
 
 g|s˜N (κ g ,          Δ v     s     +T   G     s     T   G     s     T ).   (3) 
 
         [0040]     The inference of global coordinate g conditioned on a data point y n  can be rewritten as  
                 p   ⁡     (     g   |     y   n       )       =       ∑   s     ⁢       p   ⁡     (       g   |     y   n       ,   s     )       ⁢     p   ⁡     (     s   |     y   n       )             ,           (   4   )             
 
         [0041]     where 
 
 p ( g|y   n   , s )=∫ p ( g|s, z   s ) p ( z   s   |s, y   n ) dz   s .   (5) 
 
         [0042]     Given Eq. 1, both p(g|s, z s ) and p(z s |s, y n ) are Gaussian distributions, p(g|y n ,s) also follows a Gaussian distribution. Since p(s|y n )∝p(y n |s)p(s) can be computed and viewed as a weight, p(g|y n ) is essentially a mixture of Gaussians.  
         [0043]     In one embodiment, an efficient two stage learning algorithm leverages on the mixture of local models to collapse large groups of points together as described by Teh, et al. referenced above. This algorithm works with the groups rather than individual data points in the global coordination. A graphical representation of the two stage dimensionality reduction model is depicted in  FIG. 4 . A data point in the original space, y n    402  is characterized by S factor analyzers. First the MFA between y  402  and (s, z s )  406  is learned using the method set forth in Ghahramani, et al.,  The EM Algorithm for Mixtures of Factor Analyzers,  Technical Report CRG-TR-96-1, University of Toronto, 1996 which is incorporated by reference herein in its entirety. Given the learned MFA model, z ns    406  is the expected local coordinate in the s-th FA for each data point y n . r ns    404  denotes the likelihood, p(y n |s). The set of z n    406  acts as a local dimensionality reducer while the set of r n    404  gives the responsibilities of each local dimensionality reducer. The weighted combination, u n    408  is formed from r n  and z n  as 
 
u n   T =[r n     1   z n     1     T , r n     1   , r n     2    z n     2     T , r n     2   , . . . , r n     g   , z n     s     T , r n     s   ], 
 
 Then from Eqs. 1 and 2, g n    412 , the expected global coordinate of y n    402  is defined as:  
               g   n     =         ∑   g     ⁢       r     n   s       ⁡     (         T     G   s       ⁢     z     n   s         +     κ   s       )         =       Lu   n     .               (   6   )             
 
 where 
 
L=[T G     1   , κ 1 , T G     2   , κ 2  . . . , T G     s   , κ S ]
 
         [0044]     The alignment parameters L  410  provide the mapping from the weighted combination, u n    408  to the global coordinates, g n ,  412  in the global coordinated latent space from Eq. 6. Let G=[g 1 , g 2 , . . . , g N ] T  be the global coordinates of the whole data set (the rows of G corresponding to the coordinated data points) and U=[u 1 , u 2 , . . . , u N ] T . This yields a compact representation G=UL. To determine L, a cost function must be minimized that incorporates the topological constraints that govern g n . In one embodiment, the cost function is based on LLE as described by Roweis in  Nonlinear Dimensionality Reduction by Locally Linear Embedding  referenced above.  
         [0045]      FIG. 5  represents an embodiment of a method for learning  306  a dimensionality reduction model which computes the alignment parameters, L, and the global coordinates, G. Local linear construction weights are first computed  502 . Next, a mixture of factor analyzers are trained  504  as local dimensionality reducers. The local linear construction weights are combined to form  506  the weighted combination matrix. Optimal alignment parameters are determined  508  to map the weighted combination matrix to the global coordinate system. The global coordinates are determined  510  from the weighted combination matrix and alignment parameters.  
         [0046]     The local linear reconstruction weights are computed  502  using equation 7 and as described below. For each data point y n , its nearest neighbors are denoted as y m  (m ε N n ) and following is minimized:  
                     ξ   ⁡     (     Y   ,   W     )       =       ∑   n     ⁢              y   n     -       ∑     m   ∈     N   n         ⁢       w   nm     ⁢     y   m                2                     =     Tr   ⁡     (         Y   T     ⁡     (     I   -     W   T       )       ⁢     (     I   -   W     )     ⁢   Y     )         ,                 (   7   )             
 
         [0047]     with respect to W and subject to the constraint ΣmεN n  w nm =1. Here the set of training data points is Y=[y 1 , y 2 , . . . , y N ] T  where each row of Y corresponds to a training data point. The weights w nm  are unique and can be obtained via constrained least squares. These weights represent the locally linear relationships between y n  and its neighbors.  
         [0048]     The matrix U is formed  506  by a mixture of factor analyzers as described above and the matrices A and B are computed from Eq. 8-10 set forth below.  
         [0049]     For this calculation, the following cost function is defined:  
                     ξ   ⁡     (     G   ,   W     )       =       ∑   n     ⁢              g   n     -       ∑     m   ∈     N   n         ⁢     g   m              2                   =     Tr   ⁡     (         G   T     ⁡     (     I   -     W   T       )       ⁢     (     I   -   W     )     ⁢   G     )                     =     Tr   ⁡     (       L   T     ⁢   AL     )         ,                 (   8   )             
 
         [0050]     where A=U(I−W T )(I−W)U T . To ensure G is invariant to translations, rotations and scaling, the following constraints are defined,  
                 1   N     ⁢       ∑   n     ⁢     g   n         =   0           (   9   )             and                               1   N     ⁢       ∑   n     ⁢       g   n     ⁢     g   n   T           =         1   N     ⁢     G   T     ⁢   G     =         L   T     ⁢   BL     =   I         ,           (   10   )             
 
         [0051]     where I is the identity matrix and B=1/NU T U. Both the cost function (Eq. 8) and the constraints (Eq. 10) are quadratic and the optimal alignment parameters, L, is determined  408  by solving a generalized eigenvalue problem. Let d&lt;&lt;D be the dimensionality of the underlying manifold that y is generated from. In one example embodiment, D may typically be around 50 and d may typically have a value around 3. However, these values may vary depending on the specific problem of interest. The 2 nd  to (d+1) th  smallest generalized vectors solved from Av=λBv form the columns of L. The global coordinates are then determined  510  from G=UL.  
         [0052]     Through the two stage learning process described above, clusters are obtained in the globally coordinated latent space  600  as illustrated in  FIG. 6 . Each cluster is modeled as a Gaussian distribution in the latent space with its own mean vector and covariance matrix. Each ellipsoid  602  represents a cluster in the latent space  600 , where the mean of the cluster is the centroid  604  and the covariances are the axes of the ellipsoids  602 . This cluster-based representation leads to a straightforward algorithm for multiple hypothesis tracking.  
         [0053]     Referring back to  FIG. 3 , a dynamic model is optionally learned  308  for specific motions to be tracked. The dynamic model predicts how individual particles move over time. In one embodiment, a different dynamic model may be learned for each motion. Learning the dynamic model  308  optimizes the prediction model and allows for more accurate tracking and reduced computation for a specific motion of interest. However, successful tracking is also possible without learning the dynamic model. Thus, in some embodiments, this step is skipped. In one embodiment, a random walk model is used in place of a learned dynamic model. This model is more generic and can be applied to track arbitrary motions.  
         [0054]     The online tracking algorithm  220  tracks a pose state in 3D by utilizing a modified multiple hypothesis tracking algorithm. Examples of such techniques are set forth in Isard, et al.,  CONDENSATION: Conditional Density Propagation for Visual Tracking,  International Journal of Computer Vision (IJCV) 29, 1998, 5-28; Cham, et al.,  A Multiple Hypothesis Approach to Figure Tracking,  Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 1999, 239-245; Toyama, et al.,  Probabilistic Tracking in a Metric Space,  Proc. IEEE International Conf. on Computer Vision (ICCV), 2001, 5057; Sidenbladh, et al.,  Stochastic Tracking of  3 D Human Figures Using  2 D Image Motion,  Proc. European Conf. on Computer Vision (ECCV), 2000, 702-718; Siedenbladh, et al.,  Learning Image Statistics for Bayesian Tracking,  Proc. ICCV, 2001, 709-716; Elgammal, et al.,  Inferring  3 D Body Pose From Silhouettes Using Activity Manifold Learning,  CVPR, 2004, 681-688; Grochow, et al.,  Style - based Inverse Kinematics,  ACM Computer Graphics (SIGGRAPH), 2004, 522-531; Safonova, et al.,  Synthesized Physically Realistic Human Motion in Low Dimensional Behavior Specific Spaces,  SIGGRAPH, 2004, 514-521; Sminchisescu, et al.,  Generative Modeling for Continuous Non - linearly Embedded Visual Inference,  Proc. IEEE International Conf. on Machine Learning, 2004,140-147; Tian, et al.,  Tracking Human Body Pose on a Learned Smooth Space,  Technical Report 2005-029, Boston University, 2005; and Urtasun, et al. Priors  for People Tracking from Small Training Sets,  Proc. IEEE International Conf. on Computer Vision, 2005, 403-410 which are all incorporated by reference herein in their entirety.  
         [0055]     The modes of this multiple hypothesis tracker are propagated over time in the embedded space. In the application to 3D articulated human tracking, at each time instance, the tracker state vector is represented by X t =(P t , g t ). P t  is the 3D location of the pelvis (which is the root of the kinematic chain of the 3D human model) and g t  is the point in latent space. Once the tracker state has been initialized, a filtering based tracking algorithm maintains a time-evolving probability distribution over the tracker state. Let Z t  denote the aggregation of past image observations (i.e. Z t ={z 1 , z 2 , . . , z t }). Assuming z t  is independent of Z t−1  given X t , the following standard equation applies: 
 
p(X t |Z t )∝p(z t |X t )p(X t |Z t−1 )   (11) 
 
         [0056]     A multiple hypothesis tracker (MHT) together with the learned LLC model provides the 3D motion tracker. As LLC provides clusters in the latent space as a step in the global coordination, it is natural to make use the centers of the clusters as the initial modes in the MHT (p(g|z s , s) follows a Gaussian distribution). Given that in each cluster, the points in the latent space represent the poses that are similar to each other in the original space, a simple dynamic model may be applied in the prediction step of the filtering algorithm. In one embodiment, the modes are passed through a simple constant velocity predictor in the latent space. In another embodiment, the dynamic model is not used.  
         [0057]      FIG. 3   b  summarizes one embodiment of the online tracking method  220 . The pose state at the next time frame is predicted  322  based on the prediction model  215 . In one embodiment, this prediction generates several of the most likely pose states based on the prediction model. The 2D image corresponding to the predicted time frame is then received  324  from a video sequence. The predicted pose state is then updated  326  based on the 2D image information. In one embodiment, this update comprises selecting the pose state of the several predicted possible pose states that best matches the data in the 2D image. The time frame advances  328  and the process repeats for each frame of 2D video.  
         [0058]      FIG. 7  summarizes the computations performed in the online tracking stage  220 . A prior probability density function is computed  702 . This function is based on the prediction model  215  and all past image observations. In one embodiment, the modes of the prior probability density function are passed through a simple constant velocity predictor to predict  322  the pose state at the next time frame. In equation 11, the prior probability density function is represented by p(X t |Z t−1 ).  
         [0059]     The likelihood function is computed  704  based on receiving the 2D image from the 2D image sequence  324 . In order to compute the likelihood for the current prediction and the input video frame, the silhouette of the current video frame is extracted through background subtraction. The predicted model is then projected onto the image and the chamfer matching cost between the projected model and the image silhouettes is considered to be proportional to the negative log-likelihood. In one embodiment, the projected model consists of a group of cylinders as described by Sigal, et al.,  Tracking Loose - limbed People.,  CVPR, 2004, 421-428. By computing the matching cost of the samples and measuring the local statistics associated with each likelihood mode, the predicted pose state is updated  326 . In equation 11, the likelihood function is represented by p(z t |X t ).  
         [0060]     The posterior probability density function is computed  706  through equation 11, where the posterior probability density function is represented by p(X t |Z t ). The time frame advances  708  and the calculation is repeated for each time frame of video.  
         [0061]     The MHT algorithm proposed here differs from conventional techniques in a variety of ways. For example, the present invention uses the latent space to generate proposals in a principled way. This is in contrast with conventional techniques, where the modes are selected empirically and the distributions are assumed to be piecewise Gaussian. While in the proposed algorithm, the output from the off-line learning algorithm (LLC) forms clusters (each cluster is described by a Gaussian distribution in latent space), the samples generated from the latent space are indeed drawn from a piecewise Gaussian distribution. The choice of modes to propagate over time becomes straightforward given the statistics of the clusters in the latent space.  
         [0062]     While particular embodiments and applications of the present invention have been illustrated and described herein, it is to be understood that the invention is not limited to the precise construction and components disclosed herein and that various modifications, changes, and variations may be made in the arrangement, operation, and details of the methods and apparatuses of the present invention without departing from the spirit and scope of the invention as it is defined in the appended claims.