System and method for human pose estimation in unconstrained video

Abstract

A system and method for estimating a sequence of human poses in an unconstrained video. In the present invention, a unified two stage, tree-based, optimization problem is solved for which an efficient and exact solution exists. While the proposed method finds an exact solution, it does not sacrifice the ability to model the spatial and temporal constraints between body parts in the video frames on the unconstrained video.

Claims

1. A method for estimating human poses in an unconstrained video, the method comprising: receiving, at a computing device comprising hardware components and software programs, an unconstrained video comprising a plurality of consecutive frames including at least one human pose; generating a plurality of best full body pose hypotheses for each of the plurality of consecutive frames; extracting a plurality of real body part nodes from each of the plurality of best full body pose hypotheses; extracting a plurality of real body part nodes from each of the plurality of best full body pose hypotheses in each of the plurality of consecutive frames of the unconstrained video; generating a real body part hypotheses for each of the plurality of real body part nodes extracted from the plurality of best full body pose hypotheses; combining one or more pairs of symmetric real body part nodes into a single abstract coupled body part node to generate a plurality of abstract coupled body part nodes for each of the plurality of consecutive frames of the unconstrained video, wherein each of the one or more pairs of symmetric real body part nodes includes a left real body part node of the at least one human pose and a corresponding symmetric right real body part node of the at least one human pose; generating a plurality of abstract body part hypotheses from the plurality of abstract coupled body part nodes and each of the real body part hypotheses; generating an optimal tracklet for each of the abstract body part hypotheses; and estimating a human pose in the unconstrained video based upon the abstract body part tracklets using tree-based optimization.

2. The method of claim 1, wherein generating a plurality of best full body pose hypotheses for each of the plurality of consecutive frames, further comprising generating a plurality of best full body pose hypotheses using an N-best inference algorithm.

3. The method of claim 1, wherein the real body part nodes are selected from head, neck, right elbow, left elbow, right wrist, left wrist, right hip, left hip, right knee, left knee, right foot and left foot.

4. The method of claim 1, wherein the abstract body part nodes include abstract single body part nodes.

5. The method of claim 4, wherein the abstract single body part nodes include, head top and head bottom.

6. The method of claim 1, wherein the abstract coupled body part nodes include one or more of, right shoulder combined with left shoulder, right elbow combined with left elbow, right wrist combined with left wrist, right hip combined with left hip, right knee combined with left knee and right ankle combined with left ankle.

7. The method of claim 1, wherein generating an optimal tracklet for each of the abstract body part hypotheses further comprises selecting the one tracklet for each of the abstract body parts that maximizes a combined detection score and compatible score weights.

8. A system for estimating human poses in an unconstrained video, the system comprising: at least one computing device comprising hardware components and software programs for; receiving an unconstrained video comprising a plurality of consecutive frames including at least one human pose; generating a plurality of best full body pose hypotheses for each of the plurality of consecutive frames; extracting a plurality of real body part nodes from each of the plurality of best full body pose hypotheses in each of the plurality of consecutive frames of the unconstrained video; generating a real body part hypotheses for each of the plurality of real body part nodes extracted from the plurality of best full body pose hypotheses; combining one or more pairs of symmetric real body part nodes into a single abstract coupled body part node to generate a plurality of abstract coupled body part nodes for each of the plurality of consecutive frames of the unconstrained video, wherein each of the one or more pairs of symmetric real body part nodes includes a left real body part node of the at least one human pose and a corresponding symmetric right real body part node of the at least one human pose; generating a plurality of abstract body part hypotheses from the plurality of abstract coupled body part nodes and each of the real body part hypotheses; generating an optimal tracklet for each of the abstract body part hypotheses; and estimating a human pose in the unconstrained video based upon the abstract body part tracklets using tree-based optimization.

9. The system of claim 8, wherein the system further includes software programs for generating a plurality of best full body pose hypotheses for each of the plurality of consecutive frames, further comprising generating a plurality of best full body pose hypotheses using an N-best inference algorithm.

10. The system of claim 8, wherein the real body part nodes are selected from head, neck, right elbow, left elbow, right wrist, left wrist, right hip, left hip, right knee, left knee, right foot and left foot.

11. The system of claim 8, wherein the abstract body part nodes include abstract single body part nodes.

12. The system of claim 11, wherein the abstract single body part nodes include, head top and head bottom.

13. The system of claim 8, wherein the abstract coupled body part nodes include one or more of, right shoulder combined with left shoulder, right elbow combined with left elbow, right wrist combined with left wrist, right hip combined with left hip, right knee combined with left knee and right ankle combined with left ankle.

14. The system of claim 1, wherein the system is integrated into a gaming system or a camera.

15. One or more non-transitory computer-readable media having computer-executable instructions for performing a method of running a software program on a computing device, the computing device operating under an operating system, the method including issuing instructions from the software program comprising: receiving an unconstrained video comprising a plurality of consecutive frames including at least one human pose; generating a plurality of best full body pose hypotheses for each of the plurality of consecutive frames; extracting a plurality of real body part nodes from each of the plurality of best full body pose hypotheses in each of the plurality of consecutive frames of the unconstrained video; generating a real body part hypotheses for each of the plurality of real body part nodes extracted from the plurality of best full body pose hypotheses; combining one or more pairs of symmetric real body part nodes into a single abstract coupled body part node to generate a plurality of abstract coupled body part nodes for each of the plurality of consecutive frames of the unconstrained video, wherein each of the one or more pairs of symmetric real body part nodes includes a left real body part node of the at least one human pose and a corresponding symmetric right real body part node of the at least one human pose; generating a plurality of abstract body part hypotheses from the plurality of abstract coupled body part nodes and each of the real body part hypotheses; generating an optimal tracklet for each of the abstract body part hypotheses; and estimating a human pose in the unconstrained video based upon the abstract body part tracklets using tree-based optimization.

16. The media of claim 15, wherein generating a plurality of best full body pose hypotheses for each of the plurality of consecutive frames, further comprising generating a plurality of best full body pose hypotheses using an N-best inference algorithm.

17. The media of claim 15, wherein the real body part nodes are selected from head, neck, right elbow, left elbow, right wrist, left wrist, right hip, left hip, right knee, left knee, right foot and left foot.

18. The media of claim 15, wherein the abstract body part nodes include abstract single body part nodes.

19. The media of claim 18, wherein the abstract single body part nodes include, head top and head bottom.

20. The media of claim 15, wherein the abstract coupled body part nodes include one or more of, right shoulder combined with left shoulder, right elbow combined with left elbow, right wrist combined with left wrist, right hip combined with left hip, right knee combined with left knee and right ankle combined with left ankle.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The patent or application file contains at least one drawing executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee.

(2) For a fuller understanding of the invention, reference should be made to the following detailed description, taken in connection with the accompanying drawings, in which:

(3) FIG. 1A is a diagram illustrating the video image frames used to execute the inventive concept of abstraction and association for human pose estimation, in accordance with an embodiment of the present invention.

(4) FIG. 1B is a diagram illustrating the body parts in each video image frame and associated edges used to execute the inventive concept of abstraction and association for human pose estimation, in accordance with an embodiment of the present invention.

(5) FIG. 1C is a diagram illustrating the concept of abstraction in human pose estimation in videos, in accordance with an embodiment of the present invention.

(6) FIG. 1D is a diagram illustrating the concept of association in in human pose estimation in videos, in accordance with an embodiment of the present invention.

(7) FIG. 2A is a diagram illustrating the real body parts used for human pose estimation is videos, in accordance with an embodiment of the present invention.

(8) FIG. 2B is a diagram illustrating the abstract body parts used for human pose estimation is videos, in accordance with an embodiment of the present invention

(9) FIG. 3A shows the original video frames for which human poses are to be estimated.

(10) FIG. 3B illustrates the N-Best method known in the art which is employed to generate a set of diverse poses for each single frame.

(11) FIG. 3C illustrates that, by using the results from FIG. 3B, real body part hypotheses are generated for each body part in each frame and propagated to the adjacent frames.

(12) FIG. 3D illustrates how real body parts are combined into abstract body parts and how the hypotheses are also combined, accordingly, in order to remove the intra-frame simple cycles (i.e. the simple cycles with blue and green edges in FIG. 1B).

(13) FIG. 3E illustrates the tracklets that are generated for the abstract body parts (including single body parts and coupled body parts) using the abstract body part hypotheses generated in FIG. 3D.

(14) FIG. 3F illustrates how the pose hypotheses graph is build, wherein each node is a tracklet corresponding to the abstract body part and the best post estimation is obtained by selecting the best hypotheses for the parts from the graph.

(15) FIG. 4A illustrates the relational graph for the abstract body part tracklet generation in accordance with an embodiment of the present invention.

(16) FIG. 4B illustrates the tracklet hypothesis graph for single body parts, in accordance with an embodiment of the present invention.

(17) FIG. 4C illustrates the tracklet hypothesis graph for coupled body parts, in accordance with an embodiment of the present invention.

(18) FIG. 5A illustrates the pose relational graph, in accordance with an embodiment of the present invention.

(19) FIG. 5B illustrates the pose hypothesis graph, in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

(20) The present invention provides a method to estimate a sequence of human poses in an unconstrained video. In contrast with the commonly employed graph optimization framework, which is NP-hard (nondeterministic polynomial time-hard) and necessitates approximate solutions, in the present invention, this problem is formulated into a unified two stage, tree-based, optimization problem for which an efficient and exact solution exists. Although the proposed method finds an exact solution, it does not sacrifice the ability to model the spatial and temporal constraints between body parts in the video frames; indeed it even models the symmetric parts better than the existing methods currently known in the art.

(21) One commonly employed methodology for human pose estimation in videos is the graph optimization formulation. There are two types of such formulation. The first type of this formulation is to generate several human pose hypotheses in each frame and select one best hypothesis from each frame, while making sure they are consistent throughout the video. The inference in this approach is very efficient, however, due to the large variations of pose configurations, it is very difficult to get good poses with all body parts correctly estimated. Therefore, a second type of such formulation was introduced to handle each body part separately. In this formulation, hypotheses are generated for each body part in every frame. Following the spatial constraints between body parts in each frame and using temporal consistency of appearances and locations between adjacent frames, the goal is to optimally select the best hypotheses for each body part from all the frames together. This formulation is desirable, since it is able to expand sufficient diverse human pose configurations and it is able to effectively model spatiotemporal constraints between body parts. Despite all the benefits of this formulation, it is an NP-hard problem due to the underlying loopy graph structure (i.e. there are many simple cycles in the graph; e.g. the simple cycles in FIG. 1B induced by the green, blue and red edges). Several methods have been proposed to attack this NP-hard problem in different ways to reduce the complexity induced by inter-frame simple cycles. However, none of the proposed methods simultaneously exploited the important constraints between body parts (e.g. symmetry of parts) and none of the proposed methods provide an efficient exact solution.

(22) FIG. 1A-FIG. 1D provides an abstract high-level illustration of the proposed method of the present invention which is focused on removing simple cycles from the commonly employed graph optimization framework for video based human pose estimation problems. The video based human poses are illustrated the video frames of FIG. JA. FIG. 1B illustrates a relational graph commonly known in the art in which each body part in each frame is represented by a node. Green and blue edges represent relationships between the different body parts in the same frame. Green edges are commonly used edges in the literature, blue edges are important edges for symmetric parts and red edges represent the consistency constraints for the same body part in adjacent frames. Note that FIG. 1B is for illustrative purposes and not all edges are shown. FIG. 1C illustrates the abstraction stage of the present invention, wherein symmetric parts are combined together and the simple cycles within each single frame are removed. FIG. 1D illustrates the association stages of the present invention, wherein the simple cycles between adjacent frames are removed.

(23) In various embodiments, the present invention solves the problem of exploiting the spatial constraints between the body parts in each frame and temporal consistency throughout the frames, to the greatest possible extent, while also providing an efficient exact solution. Since it is known that the inference of a tree-based optimization problem has a polynomial time solution, the main issue solved by the present invention becomes is how to formulate the problem in order to model the useful spatial and temporal constraints between body parts among the frames without inducing simple cycles.

(24) To solve the problems known in the art, the present invention approximates the original fully connected model into a simplified tree-based model. In contrast with the standard tree representation of body parts, the present invention introduces a new concept, related to the use of abstract body parts and referred to as abstraction, to conceptually combine the symmetric body parts. FIG. 2A and FIG. 2B illustrates the concept of real body parts vs. abstract body parts. FIG. 2A shows the commonly used body part definitions in the literature, in which these body parts, or nodes, represent real body parts (i.e. head, elbow, hip, etc.). The associated real body part relational graph is also illustrated in FIG. 2A. FIG. 2B shown the proposed new definition of body parts in accordance with the present invention, in which a pair of symmetric body parts are combined into one body part. These combined body parts (nodes) are referred to as abstract body parts, since the parts are some abstract concepts of parts, but not real body parts. The associated abstract body part graph is also illustrated in FIG. 2B. As such, the present invention takes advantage of the symmetric nature of the human body parts without inducing simple cycles into the formulation. In addition to the concept of abstraction, the present invention also introduces the concept of association, in which optimal tracklets are generated for each abstract body part to ensure the temporal consistency. Since each abstract body part is processed separately, it does not induce any temporal simple cycles into the graph. In view of these novel concepts, the present invention ensures both spatial and temporal constraints without inducing any simple cycles into the formulation and an exact solution can be efficiently found by dynamic programming.

(25) FIG. 3A-FIG. 3F provides an outline of the proposed method of the present invention for estimation human poses in unconstrained video. FIG. 3A show the original video frames. FIG. 3B illustrates the N-Best method known in the art which is employed to generate a set of diverse poses for each single frame. FIG. 3C illustrates that, by using the results from FIG. 3B, real body part hypotheses are generated for each body part in each frame and propagated to the adjacent frames. FIG. 3D illustrates how real body parts are combined into abstract body parts and how the hypotheses are also combined, accordingly, in order to remove the intra-frame simple cycles (i.e. the simple cycles with blue and green edges in FIG. 1B). FIG. 3E illustrates the tracklets that are generated for the abstract body parts (including single body parts and coupled body parts) using the abstract body part hypotheses generated in FIG. 3D. FIG. 3F illustrates how the pose hypotheses graph is build, wherein each node is a tracklet corresponding to the abstract body part and the best post estimation is obtained by selecting the best hypotheses for the parts from the graph.

(26) In computer vision, and several other disciplines, many problems can be abstracted as follows. Assume there is a set of entities ={e.sup.i|.sub.i=1.sup.N}, where each entity can only

(27) be in one of the many states S={s.sup.k|.sub.k=1.sup.M}, with the unary scoring functions {(e.sup.i, s.sup.k|e.sup.i , s.sup.k S}, which gives the likelihood that an entity e.sup.i is in state s.sup.k. And there is a binary compatibility function for each pair of entities {(e.sup.i, e.sup.j, s.sup.k, s.sup.l)|e.sup.i, e.sup.j , s.sup.k, s.sup.lS} which represents the compatibility of entity e.sup.i in state s.sup.k and entity e.sup.j in state s.sup.l. The goal then is to determine the best states for each entity such that all of them have high unary scores and they are also compatible with each other. This problem can be modeled as a graph optimization problem formulated by relational and hypothesis graphs, which is described below.

(28) A relational graph, G.sub.r=(V.sub.r, E.sub.r), represents the relationship of a set of entities which are represented by entity nodes {v.sub.r.sup.i|.sub.i=1.sup.|V.sup.r.sup.|v)}, and the relationships between pairs of entities are represented by edges E.sub.r. Examples of relational graphs are shown in FIG. 1A, FIG. 4A and FIG. 5A. More specifically, FIG. 5A is the pose relational graph, wherein each node represents one abstract body part and edges represent the relationship between the connected body parts. Corresponding to a relational graph G.sub.r, a hypothesis graph G.sub.h=(V.sub.h, E.sub.h), can be built. For an entity node v.sub.r.sup.i in V.sub.r, a group of hypothesis nodes V.sub.h(i)={v.sub.h(i).sup.k|.sub.k=1.sup.|V.sup.h(i).sup.|} are generated to form the hypothesis graph, so V.sub.h=U.sub.i=1.sup.|V.sup.r.sup.|V.sub.h(i). The hypothesis nodes represent the possible states of each entity, and in the current context, they represent possible locations of body parts. Hypothesis edges, E.sub.h={(v.sub.h(i).sup.k, v.sub.h(j).sup.l)|v.sub.h(i).sup.kV.sub.h(i), v.sub.h(j).sup.lV.sub.h(j), v.sub.r.sup.i, v.sub.r.sup.j)E.sub.r}, are built between each pair of hypothesis nodes from different groups following the structure of G.sub.r. An unary weight, , can be assigned to each hypothesis node, which measures the likelihood of the corresponding entity to be in the state of this hypothesis node, and a binary weight, , can be assigned to each hypothesis edge, which measures the compatibility of the pair of hypothesis nodes connected by the edge. Examples of hypothesis graphs are shown in FIG. 4B, FIG. 4C and FIG. 5B. More specifically, FIG. 5B is the pose hypothesis graph, wherein each node is a tracklet for the part and edges represent the spatial compatibility of connected nodes. The methodology is to select one hypothesis node for each entity, in order to maximize the combined unary and binary weights. This is a graph optimization problem and the general form is NP-hard; however, if the relational graph is a tree (including the degenerate case of a single branch), the problem is not longer NP-hard and efficient dynamic programming based polynomial time solutions exist.

(29) For a tree-based relational graph, G.sub.r, and the corresponding hypothesis graph, G.sub.h, the objective function for a set of arbitrary selected nodes s={s.sup.i|.sub.i=1.sup.|V.sup.r.sup.|, s.sup.iV.sub.h} is:
(s)=.sub.s.sub.i.sub.V.sub.h(s.sup.i)+.Math..sub.(s.sub.i.sub.,s.sub.j.sub.)E.sub.h(s.sup.i, s.sup.j),(1)
in which is the parameter for adjusting the binary and unary weights and the goal is to maximize (s):s*=argmax.sub.s((s)). Letting the algorithm process from the leaf nodes to the root, and letting
(i,k)=(v.sub.h(i).sup.k)+.sub.v.sub.r.sub.j.sub.kids(v.sub.r.sub.i.sub.).sup.max.sub.l(.Math.(v.sub.h(i).sup.k, v.sub.h(j).sup.l)+(j,l)).(2)

(30) Based on this recursive function, the problem can be solved efficiently by dynamic programming with a computation complexity of (|V.sub.r|.Math.N), in which N is the max number of hypotheses for each node in V.sub.r.

(31) In the present invention, the term real body parts is used to represent body parts which are commonly used in the literature. The term abstract body parts is a new concept introduced by the present invention to facilitate the formulation of the proposed method, as illustrated in FIG. 2B. In contrast to the real body part definitions, there are two types of abstract body parts introduced by the present invention, which include single part and coupled part. Single parts include HeadTop and HeadBotom. Coupled parts include Shoulder, Elbow, Hand, Hip, Knee and Ankle. Note that, for coupled parts, one part is used to represent two symmetric real body parts. For instance, Ankle is employed to represent the abstract part which is actually the combination of the left and right ankles. The motivation of abstract body parts is to remove simple cycles in the body part relational graph while at the same time maintaining the ability of modeling the symmetric body parts. For example, as shown in FIG. 1B, in each frame, the green and blue edges are used to model the body part relationships and at the same time there are many simple cycles in a give frame. After introducing the abstract body parts, as shown in FIG. 1C, the symmetric parts are combined, and as a result, none of the frames contain simple cycles. However, there are still simple cycles between frames, which will be handled by the abstract body part tracklets discussed below.

(32) A known human pose estimation approach can be applied to each video frame to generate N best full body pose hypotheses. N is usually a large number (normally N>300) and for each real body part, the body part hypotheses are body part locations extracted from the-best poses. The body part hypotheses are sampled by an iterative, non-maximum suppression (NMS) scheme based on the detection score map. Detection score is a combination of max-marginal and foreground score,
.sub.s(p)=.sub.M(p)+(1).sub.F(p),(3)
in which .sub.s is the detection score, .sub.M is the max-marginal, .sub.F is the foreground score obtained by the background subtraction, and p is the location of the body part.

(33) The abstract body part hypotheses for a single part are the same as its corresponding real body part hypotheses and the abstract body part hypotheses for a coupled part are the permutation of its corresponding left and right body part hypotheses.

(34) Based on the abstract body part hypotheses described above, the goal is to obtain several best single part and coupled part tracklets through the video frames. The problem is now to select one hypothesis from each frame, ensuring that they have high detection scores and are consistent throughout the frames. Following the definitions previously discussed, the relational graph for this problem is shown in FIG. 4A and the hypothesis graphs for single parts and coupled parts are shown in FIG. 4B and FIG. 4C, respectively. FIG. 4A shows the relational graph for the abstract body part tracklet generation. FIG. 4B shows the tracklet hypothesis graph for single body parts, wherein each node represents on hypothesis location of the body part in a specific frame and edges shown the similarity between the connect body part hypotheses in adjacent frames. FIG. 4C shows the tracklet hypothesis graph for coupled parts, wherein each node represents a coupled body part hypothesis, which is the combination of the corresponding symmetric body parts, which are represented by each node being colored into two halves. The edges represent the similarities between connected coupled body parts in adjacent frames. Note that FIG. 4B and FIG. 4C are only illustrations, and for simplicity, not all edges are shown.

(35) Based on the single part hypotheses, a single part tracklet hypothesis graph is built, as shown in FIG. 4B, for each single part (HeadTop and HeadBottom). In this graph, each node represents a single part hypothesis and the detection score .sub.s(p) is used to assign the node a unary weight. Edges are added between every pair of nodes from the adjacent frames. Binary weights are assigned to the edges which represent similarities between hypotheses in adjacent frames. The binary weight is defined as a combination of optical flow predicted location distance and the Chi-square distance of HOG (histogram of oriented gradients) features as follows:

(36) $\begin{array}{cc}{}_s\left(p^f,p^{f+1}\right)=\exp \left(-\frac{X^2\left(\left(p^f\right),\left(p^{f+1}\right).Math..Math.{\hat{p}}^f-p^{f+1}.Math.\frac{2}{2}\right)}{{}^2}\right)& \left(4\right)\end{array}$
where p.sup.f and p.sup.f+1 are two arbitrary hypotheses from frames f and f+1, (p) is the optical flow predicted location p, {circumflex over (p)}.sup.f is the optical flow predicted location for p.sup.f and f+1, and is a parameter. The goal is to select one node from each frame to maximize the overall combined unary and binary weights. Given an arbitrary selection of nodes from the graph s.sub.s={s.sub.s.sup.i|.sub.i=1.sup.F}, wherein F is the number of frames, the objective function is given by:
.sub.s(s.sub.s)=.sub.i=1.sup.F.sub.s(s.sub.s.sup.i)+.sub.s.Math..sub.i=1.sup.F.sub.s(s.sub.s.sup.i, s.sub.s.sup.i+1),(5)
where .sub.s is the parameter for adjusting the binary and unary weights and s.sub.s*=argmax.sub.s.sub.s(.sub.s(s.sub.s)) gives the optimal solution. It is clear that the relational graph of this problem is a degenerate tree (i.e. single branch tree), as shown in FIG. 4A. As such, the problem can be solved using dynamic programming efficiently. After the optimal solution is obtained, the selected nodes are removed from the graph and the next optimal solution can be obtained. This process can be iterated over multiple times in order to get several tracklets from the graph.

(37) The relational graph for the coupled part tracklets generation is the same as for the single part; however, the nodes and edges are defined differently. In this case, each hypothesis node is composed of the locations of a pair of symmetric parts (e.g. left and right ankles). FIG. 4C shows an illustration of the relational graph for the coupled parts. Such a design aims to model the symmetric relationship between coupled parts, including mutual location exclusions and appearance similarity in order to reduce double counting. As discovered in previous research, double counting is a key issue which severely hinders the pose estimation. Theoretically, tree based models lack the ability to model spatial relationship of the coupled parts (e.g. left and right ankles). Furthermore, as previously discussed, attempting to model such spatial relationships would inevitably induce simple cycles in the graph, which would severely increase the computational complexity. The present invention introduces the idea of coupled parts to effectively address this issue. In the coupled part tracklet hypothesis graph, each node r=(p, q) represents a composition of a pair of symmetric parts p and q. Unary weights are assigned to the nodes which represent the detection confidence and the compatibility between the two symmetric parts, and the weight is defined as:

(38) $\begin{array}{cc}{}_c\left(r\right)=\frac{\left({}_s\left(r.p\right)+{}_s\left(r.q\right)\right).Math.\left({\left(r.p\right)}^T.Math.\left(r.q\right)\right)}{1+e^{.Math.r.p-r.q.Math./}},& \left(6\right)\end{array}$
where .sub.s is from Eq. 3, and wherein, r.p and r.q respectively represent the left and right components of the coupled part r, (p) is the normalized color histogram of a local patch around p, the denominator is the inverse sigmoid function which penalizes the overlap of the symmetric parts, and is the parameter that controls the penalty. The binary weights of the edges are computed as:
.sub.c(r.sup.f, r.sup.f+1)=.sub.s(r.p.sup.f, r.p.sup.f+1)+.sub.s(r.q.sup.f, r.q.sup.f+1),(7)
where .sub.s is from Eq. 4.

(39) Similarly, the goal is to select one node (which is a composition of a pair of symmetric parts) from each frame to maximize the overall combined unary and binary weights. Given an arbitrary selection of nodes from the graph s.sub.c={s.sub.c.sup.i|.sub.i=1.sup.F} (where F is the number of frames), the objective function is:
.sub.c(s.sub.c)=.sub.i=1.sup.F.sub.c(s.sub.c.sup.i)+.sub.c.Math..sub.i=1.sup.F.sub.c(s.sub.c.sup.i, s.sub.c.sup.i+1),(8)
where .sub.c is the parameter to adjust the binary and unary weights and s.sub.c*=argmax.sub.s.sub.c(.sub.c(s.sub.c)) gives the optimal solution. As previously discussed, the problem can also be solved by dynamic programming efficiently and iterated for multiple times to generate several tracklets.

(40) After the best tracklets for each of the abstract body parts are obtained by the methods previously described, the next step is to select the best tracklets that are compatible. The relational graph G.sub.T=(V.sub.T, E.sub.T), for this final tracklet based optimal pose estimation, is shown in FIG. 5A, wherein each node represents an abstract body part and the edges model the spatial relationship between them. Following the definitions of the abstract body parts and using the part tracklets generated for these abstract body parts, a pose hypothesis graph can be build to get the optimal pose, as shown in FIG. 5B. In the hypothesis graph of FIG. 5B, each node represents an abstract body part tracklet and edges represent the spatial constraints. For each hypothesis tracklet node, s, depending on it if corresponds to a single part of a coupled part E.sub.s(s) from Eq. 5 or E.sub.c(s) from Eq. 8 is used as its unary weight .sub.T(S). Let .sub.d(p.sub.i, q.sub.j)=w.sub.i,j.Math.(p.sub.iq.sub.j) be the relative location score (w.sub.i,j and are defined in the current state of the art), the binary weight between a pair of adjacent single part tracklet nodes s.sub.s={s.sub.s.sup.i|.sub.i=1.sup.F}and t.sub.s={t.sub.s.sup.i|.sub.i=1.sup.F} is:
.sub.T(s.sub.s, t.sub.s)=.sub.i=1.sup.F.sub.d(s.sub.s.sup.i, t.sub.s.sup.i)(9)
the binary weight between a single part tracklet node s.sub.s={s.sub.s.sup.i|.sub.i=1.sup.F} and an adjacent coupled part tracklet node t.sub.c={t.sub.c.sup.i|.sub.i=1.sup.F} is:
.sub.T(s.sub.s, t.sub.c)=.sub.i=1.sup.F(.sub.d(s.sub.s.sup.i, t.sub.c.sup.i.Math.p)+.sub.d(s.sub.s.sup.i, t.sub.c.sup.i.Math.q))(10)
and the binary weight between a pair of adjacent coupled tracklet nodes s.sub.c={s.sub.c.sup.i|.sub.i=1.sup.F} and t.sub.c={t.sub.c.sup.i|.sub.i=1.sup.F} is:
.sub.T(s.sub.c, t.sub.c)=.sub.i=1.sup.F(.sub.d(s.sub.c.sup.i.Math.p, t.sub.c.sup.i.Math.p)+.sub.d(s.sub.c.sup.i.Math.q, t.sub.c.sup.i.Math.q)).(11)

(41) Now, the goal is to select only one tracklet for each abstract body part in order to maximize the combined unary (detection score) and binary (compatible score) weights. Given an arbitrary tree selected from the hypothesis graph s.sub.T={s.sub.T.sup.i|.sub.i=1.sup.|V.sup.T.sup.|}, the objective function is given by:
.sub.T(s.sub.T)=.sub.v.sub.T.sub.i.sub.V.sub.T.sub.T(s.sub.T.sup.i)+.sub.T.Math..sub.(v.sub.T.sub.i.sub.,v.sub.T.sub.j.sub.)E.sub.T.sub.T(s.sub.T.sup.i, s.sub.T.sup.j),(12)
where .sub.T is a parameter for adjusting the binary and unary weights and the optimal solution, s.sub.T*=argmax.sub.s.sub.T(.sub.T(s.sub.T)), can also be obtained by the dynamic programming algorithm efficiently. The body part locations in each frame are extracted from this final optimal solution.

(42) In one embodiment, the system of the present invention may include various software programs and associated hardware components, such as a central processing unit (CPU) and associated memory. In an exemplary embodiment of the present invention, 15 consecutive video frames were analyzed each time. For Eq. 5 and Eq. 5, the unary and binary weights were normalized for each from between 0 and 1. In Eq. 3, =0.5 and .sub.c=.sub.s=.sub.T=1 for Eq. 5, Eq. 8 and Eq. 12. For Eq. 5 and in Eq. 6, 10% of the median height (normally 15-30 pixels) of N-Best poses was used. For each real body part, 20 hypotheses were generated and for each abstract body part, the top 10 tracklets were selected.

(43) In the present invention, a tree-based optimization method for human pose estimation in videos is provided. The main contribution of the invention is focused on reformulating the problem to remove the simple cycles from the relational graph, while at the same time maintaining the useful connections to the greatest possible extent, in order to transform the original NP-hard problem into a simpler tree-based optimization problem, for which an exact solution exists and which can be solved efficiently. The method of the present invention is general and has potential to be employed in solving other problems in computer vision.

(44) The present invention has improved performance over current human pose estimation methods in videos currently known in the art. The method and associated software-executed algorithm of the present invention has lower computational complexity. As compared to the depth sensor based systems of the prior art, the present invention has broader application in the field of video estimation as a result of the ability to utilize a regular video camera, thereby eliminating the depth sensor requirement. In addition, the present invention also reduces the required equipment cost since video cameras are much cheaper than video systems incorporating depth sensor technology.

(45) The present invention has tremendous commercial value in the computer/digital gaming industry and also in the public surveillance industry. For the gaming companies, they can directly integrate the present inventive method into their new games and attract new customers by this improved user experience. Additionally, video camera producers can incorporate the inventive technology directly into the cameras, thereby creating a competitive advantage over other camera producers.

(46) The present invention may be embodied on various computing platforms that perform actions responsive to software-based instructions. The following provides an antecedent basis for the information technology that may be utilized to enable the invention.

(47) The computer readable medium described in the claims below may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any non-transitory, tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

(48) A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. However, as indicated above, due to circuit statutory subject matter restrictions, claims to this invention as a software product are those embodied in a non-transitory software medium such as a computer hard drive, flash-RAM, optical disk or the like.

(49) Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wire-line, optical fiber cable, radio frequency, etc., or any suitable combination of the foregoing. Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, C#, C++, Visual Basic or the like and conventional procedural programming languages, such as the C programming language or similar programming languages.

(50) Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

(51) These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

(52) The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

(53) It should be noted that when referenced, an end-user is an operator of the software as opposed to a developer or author who modifies the underlying source code of the software. For security purposes, authentication means identifying the particular user while authorization defines what procedures and functions that user is permitted to execute.

(54) It will be seen that the advantages set forth above, and those made apparent from the foregoing description, are efficiently attained and since certain changes may be made in the above construction without departing from the scope of the invention, it is intended that all matters contained in the foregoing description or shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

(55) It is also to be understood that the following claims are intended to cover all of the generic and specific features of the invention herein described, and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween.