DISCRIMINATIVE MOTION MODELING FOR HUMAN MOTION TRACKING

[0001] This application claims priority from U.S. provisional application No. 60/731,158 entitled “Discriminative Motion Modeling For Human Motion Tracking” which is incorporated by reference herein in its entirety.

[0002] The invention relates generally to computer vision, and more specifically, to tracking human motion.

[0003] Many applications in computer vision involve motion analysis and modeling, such as motion tracking and action recognition. Most conventional methods for motion modeling are largely limited to simple motions. A comprehensive analytical model for complex motions, such as biological motion or human motion, is a challenging problem. One of the difficulties in motion modeling stems from the high dimensionality of the complex motion, which demands great descriptive power from the model itself. Without any constraint, it is very difficult, if not impossible, to model arbitrary motions. Fortunately, in practice, the motions of interest are more or less constrained due to physical or biological reasons. Although these constraints can be highly nonlinear, they largely reduce the intrinsic complexity of the motion. For example, human motions cannot be arbitrary but must be confined by anthropologically feasible joint angles, e.g., the upper arm and the lower arm cannot move independently.

[0004] Thus, one issue in motion tracking is to characterize and take advantage of these constraints. Since it is generally difficult to explicitly describe motion constraints, a plausible alternative is to learn them from training data. Human motion, although complex, resides in a space whose dimensionality is significantly lower than its joint angle space. Thus, dimensionality reduction is a significant step of learning to help reduce the problem complexity and build a motion model.

[0005] Many conventional techniques are available for dimensionality reduction in human motion tracking. One conventional technique is to reduce the dimensionality using ISOMAPS and learn a Gaussian mixture model in the low-dimensional space as described in Tenenbaum, J. B., et al., A Global Geometric Framework For Nonlinear Dimensionality Reduction, Science, 2000, vol. 290 pp. 2319-2323 which is incorporated by reference herein in its entirety. Another conventional technique is to use Laplacian eigenmaps for dimensionality reduction, and employ continuity interpolation when modeling dynamics as described in Sminchisescu, C., and A. Jepson, Generative Modeling for Continuous Non-Linearity Embedded Visual Inference, ICML, 2004 which is incorporated by reference herein in its entirety. In yet another conventional technique, K-means clustering is used to partition the state space first, and then Principal Component Analysis (PCA) is used to reduce the dimensionality.

[0006] These conventional methods are suitable when the motion is short, uniform and continuous, but are inappropriate for recognizing and tracking different motion patterns. These techniques may introduce confusion among different motion classes due to the compactness in the low-dimensional space and prevent accurate tracking.

[0007] There have been several previous attempts to deal with training data comprising multiple classes of motion. For example, a transition probability matrix may be learned as described in Wang, Q., et al., Learning Object Intrinsic Structure for Robust Visual Tracking, Proc. IEEE Conference on Computer Vision and Pattern Recognition, 2003, pp. 227-233 and North, B., et al., Learning and Classification of Complex Dynamics, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, pp. 1016-1034 which are both incorporated by reference herein in their entirety. An alternative to the transition matrix is to apply the training algorithm repeatedly for each individual motion. A problem that confronts these two methods is that it is possible that the different motions to be tracked may have some similar human poses, and these poses may be even closer when the dimensionality of the data is reduced. When the tracker is approaching these confusion areas caused by these similar poses, the tracker can be distracted since there is no discriminance enforced among those possible motion patterns. When motion segments with different characteristics are intermingled together, the accuracy of motion modeling may deteriorate.

[0008] Due to the problems above, the preservation of differences between motion patterns in the training set is a significant property when tracking multiple classes of motion. Therefore, it is also preferable to maintain the discriminance between motions in the lower dimensional space. Traditional discriminative models such as Linear Discriminative Analysis (LDA) are inappropriate for this problem because the motions to be modeled are generally non-linear and non-Gaussian.

[0009] What is needed as a system for discriminative motion modeling that can recognize and track a variety of human motion patterns in a reduced dimensionality space.

[0010] A system and method is provided to efficiently recognize and track a set of stylized human motions. A representation of human motion is received having at least one motion from a motion class. A motion comprises a sequence of pose states residing in a high dimensional space. A discriminative model is received, for example, from an offline learning stage to project the sequences of pose states from the high dimensional space to a low dimensional space. The discriminative model enforces discriminance between the different classes of motion in the low dimensional space. The tracker can accurately and efficiently track motions from different motion classes based on the learned discriminative model. This framework is general and does not require restrictions on the selection of the stylized motions to be tracked.

[0011] In one embodiment, in order to preserve the discriminance in the low-dimensional space, the discriminative model projects data points that are near neighbors in the original space so that they are still the near neighbors in the low-dimensional space. Also, the neighbor data points in the original space from different motion classes are separated as far as possible in the low-dimensional space.

[0012] In on embodiment of the learning stage, the model of the human body is represented as a skeleton and body parts. A pose state vector represents the pose of the skeleton and each motion type is represented by a sequence of such vectors. Vectors in the high dimensional space are projected onto a low-dimensional space by a dimensionality reduction algorithm. A clustering algorithm is applied to the low-dimensional data to generate a set of motion segments, and an autoregressive process (ARP) is learned for each motion segment.

[0013] In one embodiment of the tracking stage, the initialized skeleton is projected onto the low-dimensional space. The nearest neighbor(s) of the current skeleton is then computed, and the corresponding possible motion type(s) of these neighbors are determined. The discriminative motion model helps the tracker to be selective with these nearest neighbors, especially when multiple motion classes are tracked. The learned dynamics are then used to predict the future skeleton pose in the low-dimensional space and can be reconstructed to the original space. Finally, the body parts hypotheses and the predicted skeleton determine the tracking result interactively.

[0014] FIG. 1 is a computer system in accordance with one embodiment of the present invention.

[0015] FIG. 2 is an input/output diagram in accordance with one embodiment of the present invention.

[0016] FIG. 3 is a flow diagram illustrating an offline learning stage in accordance with one embodiment of the present invention.

[0017] FIG. 4 is a human body model in accordance with one embodiment of the present invention.

[0018] FIG. 5 is a flow diagram illustrating a method for applying a discriminative model in accordance with one embodiment of the present invention.

[0019] FIG. 6 is a flow diagram illustrating a tracking stage in accordance with one embodiment of the present invention.

[0020] FIG. 7 is a flow diagram illustrating a method for generating pose predictions in accordance with one embodiment of the present invention.

[0021] 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.

[0022] 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.

[0023] 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.

[0024] 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.

[0025] 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.

[0026] 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.

[0027] 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.

[0028] 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.

[0029] 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 an image 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 an image 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.

[0030] FIG. 2 is an input/output diagram according to one embodiment of the present invention. In an offline learning stage 220 a discriminative model 230 is generated based on motion capture data 210. A tracking stage 250 receives the discriminative model 230 and human motion data 240 (such as a video) comprising at least one motion to be tracked. Based on the learned discriminative model 230, the tracking stage outputs tracking data 260.

[0031] The motion capture data 210 comprises data of at least one motion class. For example, a motion class may be walking, clapping, tossing, balancing, or swinging. Motion capture data 210 may be acquired by a variety of conventional techniques. In one embodiment, a subject wears a special suit with markers and performs motions captured by a video camera or similar device. Further, motion capture data 210 may be two dimensional or three dimensional. Motion capture data 210 may be acquired from multiple subjects performing the same classes of motions. This provides the statistical data used to generate the deterministic model 230.

[0032] In the learning stage, motion capture data 210 is received 302 by the computer system 100. In one embodiment, the motion capture data 210 may be received by a image capture unit 140 interfaced to an input device 102. In other embodiments, the motion capture data 210 may be received by the input device 102 from a database 130 or through a network 120.

[0033] Motion capture data is processed 304 to extract pose states. Processing may be performed by a processor 106, image processor 110, or other specialized processor. An example of the pose state representation is illustrated in FIG. 4. In this example embodiment, a human body 400 includes a pose state comprising skeleton joints 404. The pose state is represented by a vector, x. For example, x may represent the relative coordinates of skeleton joints 404. In another embodiment, the pose state vector, x, may instead represent other characteristics that describe the pose state. For example, the pose state vector, x, may represent angles, positions, velocities, or accelerations of joints, limbs, or other body parts or points of interest used to describe the pose state. A motion is composed of a time sequence of pose states, and is represented by a sequence of vectors X=[x₁ x₂ . . . x_m]. Each pose state vector, x_i, may be assigned a motion label y_i. The motion label y_i represents the class of motion to which the pose state vector, x_i, belongs.

[0034] The sequence of vectors, X, representing a motion resides in a high dimensional space, denoted by HεRⁿ where R is the space of real numbers and n is the dimensionality of the high dimensional space. For example, if 13 skeleton joints 404 are used to represent the pose (as in FIG. 4), each pose state vector, x, would have n=26 dimensions, representing the concatenated two dimensional image coordinates of the 13 skeleton joints 404. In another embodiment, the pose state vector, x, may comprise three dimensional image coordinates. Processing data in this high dimensional space is computationally expensive and inefficient, making real-time tracking difficult or impossible. Therefore, it is desirable to project the high-dimensional data to a low-dimensional space denoted by LεR^l where l is the dimensionality of the low dimensional space. This projection becomes possible given that human motion is naturally constrained due to physical or biological reasons. For example, the upper arm and lower arm cannot move independently and there are a limited number of anthropologically feasible joint angles.

[0035] Turning back to FIG. 3, a discriminative model is learned 306 to project the high-dimensional data, X, to a low dimensional space. The discriminative model obtains low-dimensional state vectors Z=[z₁ z₂ . . . z_m], where the dimensionality, l, of each z_i is less than the dimensionality, n, of each x_i. In reducing the dimensionality of the data, the discriminative model also enforces discriminance between different classes of motion. By enforcing discriminance, the model projects data such that samples which are near neighbors in the high dimensional space and of the same motion class remain near neighbors in the low-dimensional space. Samples which are near neighbors but from different motion classes are separated as far as possible in the low-dimensional space.

[0036] For example, a pose state vector x_a of the motion class “clap” may appear very similar to a pose state vector x_b of the motion class, “swing”. The discriminative model will project the data such that the low dimensional state vectors z_a and z_b are far apart in the low dimensional space. In contrast, if a pose state vectors x_a and x_c are both of the motion class “clap” and appear very similar in the high dimensional space, the discriminative model will project the data such that z_a and z_c remain similar in the low dimensional space. The discriminative model is thus configured to avoid confusion areas between different classes of motions and allows for accurate tracking of multiple motion classes.

[0037] The discriminance between the data from different motion classes is achieved by increasing the inter-class separability, which is the sum of the distances between each data point and their neighboring data points that are from different classes, and simultaneously reducing the intra-class variety, which is the sum of the distances between each point and their neighboring points that are in the same class. The advantage of contriving these two measurements is that in contrast to many conventional techniques, it does not rely on the assumption that the data follows Gaussian distribution.

[0038] In one embodiment, Local Discriminant Embedding (LDE) (or similar Marginal Fisher Analysis) provides the discriminative model 230 to project data from the high dimensional space to the low dimensional space. LDE and Marginal Fisher Analysis are described in more detail in Chen, H., et al., Local Discriminant Embedding and Its Variants, Proc. IEEE Conference on Computer Vision and Pattern Recognition, 2000, pp. 126-133; and Yan, et al., Graph Embedding: A General Framework for Dimensionality Reduction, Proc. IEEE Conference on Computer Vision and Pattern Recognition, 2005, pp. 830-837, which are both incorporated by reference herein in their entirety. Additional details may be found in He, X., Locality Preserving Projections, NIPS, 2003 which is incorporated by reference herein in its entirety.

[0039] FIG. 5 illustrates one embodiment of a method for learning 306 the discriminative model. For the motion data set X=[x₁ x₂ . . . x_m]εH, a projection matrix V generates the low dimensional data by Z=V^TX=[z₁ z₂ . . . z_m]εL. The class label for each x_i is y_i.

[0040] The intra-class variety is computed 510 as $\begin{array}{cc}\begin{array}{c}S=\sum _{i,j}^{}\sum _{\left(j\right)\mathrm{or}j\in N_{k_1}^{+}\left(t\right)}^{}{W_{x_i}-W_{x_j}}^2\text{?}\\ =2W^{T}X\left(D^w-W^w\right)X^{T}W\end{array}W=1\mathrm{if}j\in N_{k_1}^{+}\left(i\right)\mathrm{or}i\in N_{k_1}^{+}\left(j\right);0,\mathrm{else}\text{Text missing or illegible when filed}& \left(1\right)\end{array}$

[0041] where N_k1⁺(t) denotes the set of k₁ nearest neighbors of point x_i, which are in the same class of class y_i. D^w is a diagonal matrix with entries d_ij^w

[0042] The inter-class separability is computed 520 as $\begin{array}{cc}\begin{array}{c}S\text{?}=\sum _{i,j}^{}\sum _{i\in N_{k_2}^{-}\mathrm{or}j\in N_{k_2}^{-}\left(i\right)}^{}{W_{x_i}-W_{x_j}}^2\\ =2W^{T}X\left(D^b-W^b\right)X^{T}W\end{array}{W}_{i.j}^b=1\mathrm{if}j\in N_{k_2}^{-}\left(i\right)\mathrm{or}i\in N_{k_2}^{-}\left(j\right);0,\mathrm{else}\text{?}\text{indicates text missing or illegible when filed}& \left(2\right)\end{array}$

[0043] where N_k2⁻(t) denotes the set of k₂ nearest neighbors of point x_i, which are in classes other than y_i. D^b is a diagonal matrix with entries d_xi^b=Σ_iW_ij^b

[0044] Then, the projection matrix, V, can be obtained 530 by solving the following generalized eigenvector problem,
X(D^b−W^b)X^Tv=λX(D^w−W^w)X^Tv   (3)

[0045] Eigenvectors v₁, v₂, . . . , v_l are chosen corresponding to the l largest eigenvalues. The mapping from the high dimensional space to the low dimensional space can then be computed 540 by z_i=V^Tx_i, where V=[V₁, V₂, . . . , V_l].

[0046] A dynamic human motion model can further improve motion tracking. Motion can be practically modeled as an autoregressive process by recognizing that the movement in a short period tends to be continuous. This model is based in part on techniques described in Wang and North referenced previously; and Agarwal, A. and B. Triggs, Tracking Articulated Motion Using a Mixture of Autoregressive Models, ECCV, 2004; and Li, Y., et al., Motion Texture: A Two-Level Statistical Model for Character Motion Synthesis, SIGGRAPH, 2002 which are both incorporated by reference herein in their entirety.

[0047] A clustering algorithm is applied 308 to separate the data of each motion pattern in the low dimensional space into clusters. In one embodiment, a K-means algorithm provides the clustering algorithm. To ensure that each cluster is formed by contiguous sequences, the time stamp t_i of each sample point z_i is also considered. Thus, in one embodiment, similar low dimensional state vectors, z, that have very different time stamps, t, are clustered separately. For example, if low dimensional state vectors z_a and z_b are very similar and are very close together in time, it is highly likely the state vectors are part of the same motion segment and should be clustered together. However, if the similar state vectors are far apart in time, it is less likely they are part of the same motion segment and may instead represent similar poses from different motion segments. Thus, the clustering algorithm encourages temporally contiguous sample vectors to be clustered into one segment.

[0048] Motion dynamics are learned 310 for each motion segment to help guide the tracking. Motion dynamics may comprise two-dimensional or three dimensional motions. In one embodiment, an auto-regressive process (ARP) is applied to learn the motion patterns of each segment by $\begin{array}{cc}{z}_t=\sum _{k=1}^K{A}_k{z}_{t-k}+d+\mathrm{Bn},& \left(4\right)\end{array}$

[0049] where z_tεR^l is the state vector in the low-dimensional space, A_kεR^l×l; k=1, . . . , K is the state transition matrices for K clusters, d is the offset vector, BεR^l×l, u_t˜N(0, Q) is the noise vector. The parameters {A_k, k=1, . . . , K, d, B} can be learned by Maximum Likelihood Estimation (MLE) as described in North, et al., referenced above. Those motion segments, whose resulting prediction error by ARP is large, are considered to be erratic movements and are pruned away. The number of clusters in the clustering algorithm, K, is chosen as the one from a range, (for example, [1, 6]]) which can produce the minimum ARP prediction error of all clusters.

[0050] The tracking stage 250 is configured to track a set of stylized motion patterns based on the learned model. In tracking, the human body can be represented by a human body model, for example, as illustrated in FIG. 4. In one embodiment, the data comprising the human body model is a combination of two subsets of parameters: pose state (represented by, for example, skeleton joints 402) and body parts 404. This decomposable model helps to distribute the computation into two subsets, each with reduced dimensionality. These two subsets jointly and interactively determine the human configuration, i.e., the skeleton joints 402 represents the abstract “style” of motions, which accounts for the general and global movement of human. The body parts 404 are the “content” of the motion, which are different for different people wearing different clothes.

[0051] The body parts 404 are represented by a set of body part descriptors. In one embodiment, rectangles associated with limbs, torso, and head, for example, represent each body part. In another embodiment, different shapes are used to represent the body parts. Each body part 404 has the parameters of center point, height, width, scale and orientation. The body parts 404 may then be manipulated with operations such as translation, rotation, scaling, and so on.

[0052] In one embodiment, various types of histograms are used as the body part descriptors. For example a color histogram, a gradient orientation histogram, and a color distance histogram may be used. A color histogram is a conventional histogram that represents an image by counts of the colors of each pixel in the image. A gradient orientation histogram is a representation that provides edge information in an image. Both the orientation and the magnitude of the gradient are computed for each pixel within the body part. Then the orientations are quantized into a predetermined number of bins and the magnitude of each gradient is added into its corresponding bin.

[0053] A color distance histogram represents the spatial distribution of color pixels. The color distance histogram describes how the color pixels are distributed within the body part, which can alleviate confusion between candidates which have similar color histogram but very different spatial distribution of color pixels. In computing the color distance histogram, the intensity range of the pixels is quantized into a predetermined number of bins. For each pixel, the pixel distance to the center of the body part is computed and the distance is added to the bin corresponding to the intensity of that pixel. Thus, both the intensity and the spatial structure of the color pixels are considered.

[0054] In the tracking stage, 250, an image is received from the human motion data 240 (for example, a video) comprising the motion to be tracked. In one embodiment, no background subtracting is performed on the received image in contrast to many conventional techniques. The current skeleton vector, x_c, is projected 604 to the low dimensional space by z_c=V^Tx_c where V is the projection matrix generated in the learning stage 220. Pose predictions are then generated 608 to predict a future pose state of the skeleton. FIG. 7 illustrates one embodiment of a method for generating 608 pose predictions. The P nearest neighbors of z_c are determined 702 where each of the P nearest neighbors come from different motion segments. In one embodiment, P is a predetermined quantity. The motion type of each of the P nearest neighbors are then determined 704. The learned motion dynamics of the P different motion segments are applied 706 to form the pose predictions for each nearest neighbor. Thus, predictions are generated 608 based on learned motion dynamics for different motion segments. In one embodiment, pose predictions are generated using the auto-regressive process of Eq. 4 described previously.

[0055] Given the skeleton configuration in the low-dimensional space, L, the corresponding skeleton is reconstructed 610 in the original space, H for the predicted poses. Here, the basic assumption is that, the local geometry is consistent in both the original space and the low-dimensional space. Neighborhood reconstruction is applied to reconstruct a predicted pose, x_p, in the original space from the predicted pose, z_p, in the low dimensional space in a manner similar to that described in Roweis, S. and L. K. Saul, Nonlinear Dimensionality Reduction By Locally Linear Embedding, Science, 2000, vol. 290, pp. 2323-2326 which is incorporated be reference herein in its entirety.

[0056] In reconstructing x_p from z_p, the nearest neighbors of z_p are first determined. Next, the linear coefficients that best reconstruct z_p from the selected neighborhood are computed by a least square method. The neighborhood of z_p in L has known corresponding states in H. x_p is then reconstructed by linearly combining these states with the calculated coefficients.

[0057] In order to determine the optimal or near optimal combination of the body parts and the predicted skeleton, the body parts 404 must be fitted to the skeleton 402. Each of the body parts are fitted onto each of the possible predicted skeletons S_p, for p=1, . . . , P. One way to represent the topology of the body parts is by a graph G=(V, E), where the vertices V={v₁, . . . , v_Q} correspond to the Q body parts (in FIG. 4, for example, Q=10). An edge e(v_i, v_j) is assigned to each connected parts v_i and v_j such as the head and the torso, for example. The optimal fitting can be formulated as minimizing a cost function over the graph G, the parameters of which include the configuration of the skeleton S_p and the configurations of all the Q body parts B_i, i=1, . . . , Q.

[0058] For each body part B_i, the associated cost function m(Bi) can be written as follows,
m(B_i)=q(B_i,I)+d(B_i,S_p)   (5)

[0059] where, q(B_i, I) measures how well the body part matches the image I when positioned as B_i, and d(B_i, S_p) measures the extent to which the body part B_i deviates from the skeleton S_p. There is also a cost over each edge e(v_i, v_j)εE, which is the distance between those adjacent body parts, i.e., d(B_i, B_j). The optimal solution is computed by H*={S*, B_i*, i=1, . . . , Q}, such that $\begin{array}{cc}{H}^{*}=\arg \underset{B}{\min }\left(\text{?}d\left(B_i,B_j\right)+\text{?}\text{?}\left(B_i\right)\right)\text{?}\text{indicates text missing or illegible when filed}& \left(6\right)\end{array}$

[0060] Conventionally, solving the above optimization problem {S*, B_i*, i=1, . . . , Q}needs O(Qⁿ F) time, where Q is the number of the body parts, n is the possible configurations of each body part, and F is the number of all possible skeletons. If there are no constraints on the configurations of the skeleton then F=13^f, where 13 is the number of the skeleton points, f is the number of possible locations of each skeleton point. Solving these equations these equations using conventional techniques brings overwhelming computational cost.

[0061] In contrast to conventional methods, computation is significantly reduced by restricting the number of the possible skeletons to only P predictions based on nearest neighbors as described previously. The discriminative motion modeling is well adapted to make this local neighborhood search because the model reduces confusion areas caused by the multiple motion classes in the training data. Computation may be further reduced by employing dynamic programming to make the body part fitting polynomial rather than exponential in time. This technique is based in part on the techniques used in Felzenszwalb, P. F., Efficient Matching of Pictorial Structures, Proc. IEEE Conference on Computer Vision and Pattern Recognition, 2000, pp. 66-73 which is incorporated by reference herein in its entirety.

[0062] For any vertex v_j with no children (i.e., any leaf of the tree), its best configuration can be computed as a function of its parent v_i,
B_i*(B_i)=arg min(d(B_i, B_j)+m(B_j))   (7)

[0063] For any vertex v_j that has both parent v_i and children, the best location of all its children can be known given the configuration of B_j. Let C_Bj denote the best cost of all its children. Then the best configuration of v_j is,
B_j*(B_i)=arg min(d(B_i, B_j)+m(B_j)+C_Bj)   (8)

[0064] For the root vertex v_r, its best configuration is found as,
B_r*=arg min(m(B_r)+C_Br)   (9)

[0065] That is, fitting from the leaf parts can start, such as the lower arms and legs, then connects to their parents, i.e., the upper arms and legs, and finally reach to the root part, i.e., the head. Each non-leaf node records its best children given its own configuration. After that, the best configurations of each body part can be determined by tracing down from the root part to the leaf parts. The computation here is polynomial, O(Qn²).

[0066] 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.