PROPAGATION

INVENTORS: MING-HSUAN YANG, GANG HUA

CROSS REFERENCE TO RELATED APPLICATIONS

[0001] This application claims benefit under 35 USC § 1 19(e) to U.S. Provisional

Patent Application No. 60/625,437, titled "Human Pose Estimation by Data Driven Belief Propagation," filed November 5, 2004, and U.S. Utility Patent Application No. (Not Yet Known), titled "Human Pose Estimation with Data Driven Belief Propagation," filed November 3, 2005, which are incorporated by reference herein in their entirety.

FIELD OF THE INVENTION

[0002] The present invention generally relates to the field of computer vision, and more specifically, to estimating two-dimensional human pose from single images.

BACKGROUND OF THE INVENTION

[0003] Inferring human pose from a single image is an aspect of applications such as motion analysis and visual tracking, and is arguably one of the most difficult problems in computer vision. Recent approaches have yielded some favorable results. A description of this can be found in Efficient Matching of Pictorial Structures, P. Felzenszwalb and D. Huttenlocher, IEEE Conf. on Computer Vision and Pattern Recognition, volume 2, pages 2066-2073, 2000, and also in Proposal Maps Driven MCMC for Estimating Human Body Pose in Static Images, M. W. Lee and I. Cohen, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, volume 2, pages 334-341, 2004, and also in Recovering Human Body Configurations: Combining Segmentation and Recognition, G. Mori, X. Ren, A. Efros, and J. Malik, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, volume 2, pages 326- 333, 2004, all of which are incorporated by reference herein in their entirety. [0004] For convenience, these approaches may be categorized as deterministic and statistical. Deterministic methods apply deterministic optimization, and the objective function is the matching error between the model and the image data or between the image data and the exemplar set. Descriptions of these concepts can be found in Felzenszwalb and

Huttenlocher, which was referenced above, and in Estimating Anthropometry and Pose From a Single Uncalibrated Image, C. Barrn and I. Kakadiaris, Computer Vision and Image Understanding, 81(3):269-284, 3 2001, and also in Fast Pose Estimation with Parameter- Sensitive Hashing, G. Shakhnarovich, P. Viola, and T. Darrell, Proc. IEEE International Conference on Computer Vision, volume 2, pages 750-757, 2003, both of which are incorporated by reference herein in their entirety. An alternative statistical approach builds detectors for different body parts and ranks the assembled configuration based on human- coded criteria. A description of this can be found in G. Mori, et al., which was referenced above.

[0005] Despite some success, many challenging issues remain in achieving robust and efficient pose estimation. First, an optimization problem of high dimensionality must be solved, and, consequently, the computation is intractable unless certain assumptions are explicitly made. Such assumptions may regard the background, characteristics of the human subjects, clothing, distance, etc., in order to make the application domain manageable by the proposed algorithms. Accordingly, the application domains have generally been limited to uncluttered backgrounds or to the human body with fixed scale. Descriptions of these concepts can be found in Barrn and Kakadiaris, Felzenszwalb and Huttenlocher, and Mori, et al., which were referenced above. Second, the set of exemplars must be sufficiently large to cover the parameter space necessary to achieve satisfactory estimation results. However, this also results in high computational complexity, as described in Shakhnarovich, which was referenced above. Third, it is difficult to build robust body part detectors except those for faces due to the large appearance variation caused by clothing. A description of this can be found in Rapid Object Detection Using a Boosted Cascade of Simple Features, P. Viola and M. Jones, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, volume 1, pages 511-518, 2001, which is incorporated by reference herein in its entirety, and in Mori, et al., which was referenced above.

[0006] A merit of the statistical formulation for posture estimation is that prior knowledge of human body parts (e.g., appearance, shape, edge and color) can be exploited and integrated into a rigorous probabilistic framework for efficient inference. Ioffe and Forsyth proposed an algorithm that sequentially draws samples of body parts and makes the best prediction by matching the assembled configurations with image observations. A description of this can be found in Finding People by Sampling, Proc. IEEE International

Conference on Computer Vision, pages 1092-1097, 1999, which in incorporated herein by reference in its entirety. However, this approach is best applied to estimating human pose in images without clothing or cluttered background, since the method relies solely on edge cues. Sigal et al. applied a non-parametric belief propagation algorithm for inferring the 3-D human pose as the first step of a human tracking algorithm. Background subtraction and images from multiple views facilitated human pose estimation and tracking. Descriptions of these concepts can be found in Attractive People: Assembling Loose-Limbed Models Using Nonparametric Belief Propagation, L. Sigal, M. Isard, B. Sigelman, and M. Black, Advances in Neural Information Processing System 16, MIT Press, 2004, and in PAMPAS: Real- Valued Graphical Models for Computer Vision, M. Isard, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pages 613-620, 2003, which are incorporated by reference herein in their entirety.

[0007] Lee and Cohen applied the Data Driven Markov Chain Monte Carlo

(DDMCMC) algorithm to estimate 3-D human pose from single images, wherein the MCMC algorithm traversed the pose parameter space. However, it is unclear how the detailed balance condition and convergence within the Markov chain were ensured. Most importantly, the problem of inferring 3-D body pose from single two-dimensional (2 -D) images is intrinsically ill-posed as a consequence of depth ambiguity. Descriptions of these concepts can be found in Lee and Cohen, which was referenced above, and in Image Segmentation by Data-Driven Markov Chain Monte Carlo, Z. Tu and S. -C. Zhu, IEEE Transaction on Pattern Analysis and Machine Intelligence, 24(5):657-673, 2002, which is incorporated by reference herein in its entirety.

[0008] Based on the above, there is a need for an improved system and method for inferring human pose from single images that manages complexity and eliminates the need for inordinate assumptions, and that provide reliable results.

SUMMARY OF THE INVENTION

[0009] A method of 2-D human pose estimation employs a probabilistic framework and an inference algorithm within a rigorous statistical framework. A human body pose is modeled by a Markov network, wherein the nodes denote body parts and the edges encode constraints among them. Each body part is represented within the Markov network by a state variable describing its shape and location. An efficient data-driven belief propagation Monte

Carlo algorithm infers the 2-D human pose within a single target image. This algorithm incorporates importance sampling functions and is built from low-level visual cues. [0010] From a set of labeled training images, a principal component analysis learns the

2-D shape models of each body part. These models provide prior knowledge for automatic prediction of body parts within a subsequently received target image. Data-driven importance sampling for the head pose is built using a computationally efficient AdaBoost-based face detector. A description of this can be found in Viola and Jones, which was referenced above. [0011] Constrained by the head location determined from face detection, a probabilistic

Hough transform extracts salient line segments in the image, which are assembled to form good candidates for constructing an importance sampling function for the human torso. A description of this can be found in A Probabilistic Hough Transform, N. Kiryati, Y. Eldar, and A. M. Bruckstein, Pattern Recognition, 24(4):303-316, 1991, which is incorporated by reference herein in its entirety. A skin color model pertaining to the subject in the image is built based on the face detection result. This model is then utilized in sampling functions that predict candidate body parts such as arms and legs within the target image. The data driven importance functions for the body parts are incorporated in the belief propagation Monte Carlo framework for efficient Bayesian inference of the human pose. The observation models are built based on the steered edge response of the predicted body parts. [0012] Diametric to the sequential DDMCMC algorithm, the method of the invention integrates reasoning mechanisms with visual cues. The method can also execute the inference tasks in parallel, and does so within a sound statistical framework. Furthermore, the shape models of body parts are explicitly learned using quadrangles rather than rectangular templates. This facilitates inference of pose parameters. A description of this can be found in Felzenszwalb and Huttenlocher, Ioffe and Forsyth, and in Mori, et al., which were referenced above.

[0013] Experimental results demonstrate the effectiveness of the method of the invention in estimating the pose of soccer players in single images with cluttered backgrounds.

[0014] 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

[0015] The invention has other advantages and features which will be more readily apparent from the following detailed description of the invention and the appended claims, when taken in conjunction with the accompanying drawings, in which:

[0016] Figure 1 illustrates a system according to one embodiment of the present invention.

[0017] Figure 2 illustrates a Markov network according to one embodiment of the present invention.

[0018] Figure 3 illustrates a method of estimating human pose according to one embodiment of the present invention.

[0019] Figure 4 illustrates several manually-labeled images according to one embodiment of the present invention.

[0020] Figure 5 illustrates normalization of a labeled shape according to one embodiment of the present invention.

[0021] Figure 6 illustrates original shapes, normalized shapes and reconstructed shapes of the upper right arm according to one embodiment of the present invention.

[0022] Figure 7 illustrates link point pairs according to one embodiment of the present invention.

[0023] Figure 8 illustrates a belief propagation Monte Carlo algorithm according to one embodiment of the present invention.

[0024] Figure 9(a) illustrates a face detected by an AdaBoost face detector according to one embodiment of the present invention.

[0025] Figure 9(b) illustrates image-specific skin color segmentation according to one embodiment of the present invention.

[0026] Figure 9(c) illustrates fitted lower-arm and upper-leg hypotheses according to one embodiment of the present invention.

[0027] Figure 9(d) illustrates upper-arm and lower-leg hypotheses according to one embodiment of the present invention.

[0028] Figure 10(a) illustrates an original image.

[0029] Figure 10(b) illustrates line segments extracted according to one embodiment of the present invention.

[0030] Figure 10(c) illustrates torso hypotheses assembled from the line segments of

Figure 10(b) according to one embodiment of the present invention.

[0031] Figure 1 l(a) illustrates horizontal translation of the lower-left leg with respect to the correct location according to one embodiment of the present invention.

[0032] Figure 1 l(b) illustrates likelihoods of translated lower-left leg hypotheses from the correct location according to one embodiment of the present invention.

[0033] Figure 12 illustrates experimental results of human pose estimation based on one embodiment of the present invention.

[0034] Figure 13 illustrates the overall root-mean-square error associated with each of a set of test images according to one embodiment of the present invention.

[0035] Figure 14 illustrates overall root mean square error associated with each of a set of test images.

DETAILED DESCRIPTION

[0036] Reference will now be made in detail to several embodiments of the present invention, examples of which are illustrated in the accompanying figures. It is noted that wherever practicable similar or like reference numbers may be used in the figures and may indicate similar or like functionality. The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein. ARCHITECTURAL OVERVIEW

[0037] Figure 1 shows a system 100 according to one embodiment of the present invention. Computer system 110 comprises an input module 112, a memory device 114, a storage device 118, a processor 122, and an output module 124. In an alternative embodiment, an image processor 120 can be part of the main processor 122 or a dedicated device to perceive situations as digital images captured in a preferred image format. Similarly, memory device 114 may be a standalone memory device, (e.g., a random access memory (RAM) chip, flash memory, or the like), or a memory on-chip with processor 122 (e.g., cache memory). Storage device 118 may be any bulk storage device such as a hard disk, DVD-R/RW, CD-R/RW or RAM. Likewise, computer system 110 can be a stand-alone system, such as, a server, a personal computer, or the like. Alternatively, computer system 110 can be part of a larger system, for example, a robot having a vision system. [0038] According to this embodiment, input module 112 receives digital images from a database 140. Input module 112 may also receive digital images directly from an imaging device 130, for example, a digital camera 130a (e.g., robotic eyes), a video system 130b (e.g., closed circuit television), an image scanner, or the like. Alternatively, input module 112 may be an interface to receive information from a network system, for example, another database, another vision system, Internet servers, or the like. The network interface may be a wired interface, such as, a USB, RS-232 serial port, Ethernet card, or the like, or may be a wireless interface module, such as, a wireless device configured to communicate using a wireless protocol, e.g., Bluetooth, WiFi, IEEE 802.11, or the like. Image processor 120 could be used to pre-process the digital images received through the input module 112 to convert the digital images to the preferred format on which the processor 122 operates.

[0039] Information is stored in the memory device 114 to be processed by processor

122. Processor 122 applies a set of instructions that when executed perform one or more of the methods according to the present invention, e.g., implementing a data-driven belief propagation Monte Carlo algorithm. Memory device 114 may, e.g., include a module of instructions 116 for implementing such a method.

[0040] Processor 122 may output information through the output module 124 to an external device 150, e.g., a network element or server 150a, a display device 150b, a database 150c or the like. As with input module 112, output module 124 can be wired or wireless. Output module 124 may be a storage drive interface, (e.g., hard-drive or optical drive driver), a network interface device (e.g., an Ethernet interface card, wireless network card, or the like), or a display driver (e.g., a graphics card, or the like), or any other such device for outputting the information determined. In addition, output module 124 may interface appropriately with the systems of an autonomous machine such as a humanoid robot. BA YESiAN FORMULATION AND MARKOV NETWORK

[0041] According to one embodiment, a human body configuration is represented by a

Markov network as shown in Figure 2. Each random variable x, represents the pose parameter (i.e., hidden state) of body part i, e.g., x _/ , describes the pose of head, x, describes the pose of torso, and \ _ru ι describes the pose of the upper-right leg. Each undirected link models the constraints between adjacent body parts by a potential function ψ _y (x _b X ₇ ). Each directed link depicts the image observation z, of body part i with an observation likelihood function #>,(z,|x,). The set of pose parameters X = {x _; , i e S) and the set of observations Z = {z,, i e S), respectively, where S is the set of all subscripts. The joint posterior distribution of this Markov network is

where E is the set of all undirected links and v is the set of all directed links. A description of this can be found in Jordan and Weiss, which was referenced above. Consequently, the pose estimation problem is formulated as a Bayesian inference problem of estimating the marginal posterior distribution P(x,|Z).

[0042] Direct computation of equation (1) is intractable, since doing so involves numerous integrations of real-valued random variables in every P(x,|Z). As an alternative, belief propagation algorithms offer an efficient solution to such inference problems.

According to one embodiment, a Monte Carlo approach for belief propagation that is facilitated by local message passing (e.g., local computation) is applied. A description of this can be found in Multi-scale Visual Tracking by Sequential Belief Propagation, G. Hua and Y. Wu, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pages 826-833, 2004. POSE PARAMETERIZATION

[0043] Referring now to Figure 3, a method 300 is shown for estimating human pose according to one embodiment of the present invention. One or more training images of human subjects are received, and the body parts are labeled 308. The images may be received, for example, by input device 112 from camera system 130 or database 140. The training images may be labeled manually or via automatic means. Multiple training images may be used, which may be unrelated, and may even portray different subjects. Each body part is labeled with a quadrangular shape in a manner similar to that used by Felzenszwalb and Huttenlocher, and by Mori, et al., which were referenced above. However, according to this embodiment, the body parts are not necessarily modeled by rectangles or trapezoids, since the body contours usually do not form parallel lines in the received images. Some example manually-labeled images are illustrated in Figure 4.

[0044] The 2-D shape models of the body parts are next created 309. For each manually-labeled quadrangle, the lines along the body outer contour are defined as the left and the right lines, and the other two lines are defined as the top and the bottom lines. The local coordinate system of each body part is defined by choosing the centroid of the quadrangular shape as its origin. The Y-axis is oriented from the middle point of the top line to the middle point of the bottom line, and the X-axis is oriented perpendicular to the Y-axis, such that this local coordinate system represents a rotation and translation of the coordinate system of the overall image. Each labeled shape is then rotated with respect to a reference frame and then normalized in both the X and Y directions. For example, the width along the X axis between the left and the right lines is normalized to 40 pixels, and the height along the Y axis between the top and the bottom lines is normalized to 50 pixels, as depicted in Figure 5. Each normalized shape is then represented by an 8-dimensional vector, by clockwise enumerating the coordinates of the four vertices. The normalized shapes may be stored in storage device 118 or database 150c.

[0045] A probabilistic principle component analysis (PCA) is next applied 310 to each set of the 8-dimensional normalized body part shapes for dimensionality reduction. A

description of this can be found in Probabilistic Principle Component Analysis, M. E. Tipping and C. M. Bishop, Journal of Royal Statistical Society, Series B, 61(3):611-622, 1999. The discussion below will describe how the learned shape model with probabilistic PCA is used to construct importance sampling functions for body parts. It has been experimentally found that 99% of the shape variation can be retained with the top 3 principal components. The shape representation with reduced dimensionality for each body part / e S is denoted as ps,. Consequently, the 2-D pose of body part i can be represented by the rotation θ, scaling S _x , s _y , and translation t _x , t _y , in both X and Y directions of ps,, e.g.,

X ₁ = {pS,, S _x , Sy, θ, t _x , ty} (2) wherein ps, is referred to as the intrinsic pose parameter, and the other parameters are referred to as the extrinsic pose parameters. By learning a low-dimensional shape representation, the original 13 -dimensional state space is reduced to 8 dimensions, thus facilitating efficient sampling. The low-dimensionality normalized shapes may also be stored 312 in storage device 118 or database 150c. Figure 6 shows some example original labeled shapes for the upper-right-arm, the corresponding normalized shapes, as well as the corresponding reconstructed shapes from the probabilistic PCA. The reconstructed shapes clearly match the original labeled shapes well. POTENTIAL FUNCTION AND LIKELIHOOD MODEL

[0046] A target image is next received 313 for pose estimation. A potential function ψ _y next models 314 the pose constraints between adjacent body parts. For pose estimation, the natural constraints entailing adjacent body parts should be of a loosely-connected nature. A description of this can be found in Sigal et al., which was referenced above. Accordingly, a Gaussian distribution models the Euclidean distance between the link points of adjacent body parts, e.g.,

where || ■ || is the Euclidean distance, σ ² _l} is the variance learned from the labeled images, Pt _{1 }}

is the link point of the i ^th toj" ¹ body part, and Pt ₇ , is the link point of the f ^h to i' ^h body part. Figure 7 shows all the link points of the body parts, wherein each pair of circle points represents the link point pair. According to this embodiment, the link points are either corner points or middle points of either the bottom or top line of the shape. For example, the link

point of the left-upper-arm to the torso is defined as the corner point of the left line and the bottom line of the left-upper arm shape, and the link point of the torso to the left-upper arm is also defined as the corner point of the left-bottom corner of the torso shape. The link point of the upper-left arm to the lower-left arm is delineated by the middle point of the top line of the upper-left arm shape, and the link point of the left-lower-arm to the left-upper-arm is defined as the middle point of the bottom line of the left-lower-arm shape. [0047] Although object appearance or texture has been successfully utilized in tasks such as face detection, body contour information may be the only salient cue available for pose estimation, as clothing causes large visual variation. According to this embodiment, the likelihood function φ, is constructed based on the average steered edge response along the boundaries of the pose hypothesis of a body part. A description of this can be found in Learning the Statistics of People in Image and Video, H. Sidenbladh and M. Black, International Journal of Computer Vision, 54(1 -3): 183-209, 2003, which is incorporated by reference herein in its entirety. For example, if the rotation angle of one line segment / is a and the total number of points on the line is Ni, then the average steered edge response is

£ _/ . _α = -rr _j r- γ i) sm a - ε _y {y. _τ , where ε _x and ε _y are the steered edge responses in the X and Y directions, and ε _m is the maximum value of the steered edge response. Unlike in Sidenbladh, the steered edge response is not computed according to different scales, because the average steered edge responses across scales may make the steered edge response less discriminant. Instead, the steered edge response is computed in each of the color component channels, e.g., red-green-blue (RGB). Thus, the edge responses in red, green and blue color channels for each hypothesized body part x, are ε _a ^{R) (x, ) , ε^ (JC, ) and ε _a ^(B) (x, ) , respectively. For head and torso, the average steered edge response is computed using all four line segments of the shape pose hypothesis, whereas the average steered edge response is only calculated on the left and right line segments for the other body parts. Since all the steered edge responses have been normalized between 0 and 1, the likelihood function is derived 315 based on the maximum steered edge response, e.g., φfaM = ^roa x(4">(xO, 4 ^G)( x.-).4 ^fl> (*)) (5)

This embodiment uses the maximum steered edge response from different color channels

based on the results of empirical studies. The studies revealed that more effective discrimination could be realized using the maximum rather than average edge response. A proposed Gibbs likelihood model was tried, but the performance was less satisfactory. A possible explanation is that background subtraction is utilized so that the body contours can be better extracted before learning a Gibbs model for likelihood estimation. A description of this can be found in Gibbs Likelihoods for Bayesian Tracking, S. Roth, L. Sigal, and M. Black, Proc. of IEEE Conference on Computer Vision and Pattern Recognition, volume 1, pages 886-893, 2004. Nevertheless, background subtraction is inapplicable in this embodiment, since human pose is to be estimated from single images. DATA-DRIVEN BELIEF PROPAGATION

[0048] According to one embodiment, a data-driven belief propagation Monte Carlo algorithm (DDBPMC) performs Bayesian inferencing according to a real-valued graphical model. Belief propagation is an efficient algorithm to compute the marginal posterior distribution P(X ₁ IZ), through a local message passing process, whereby the message from X ₇ to X; is computed by:

fteVCxjUi (6) where s the set of neighboring nodes of X ₇ except X ₁ -. A description of this can be found in Graphical models: Probabilistic Inference, M. Jordan and Y. Weiss, The Handbook of Brain Theory and Neural Network, pages 243-266. MIT Press, second edition, 2002, and in Learning Low-level Vision, W. T. Freeman and E. C. Pasztor, Proc. IEEE International Conference on Computer Vision, pages 1182-1189, 1999, both of which are incorporated by reference herein in their entirety.

[0049] According to one embodiment, the belief propagation algorithm iteratively updates the messages passed among the connected nodes until it converges, and the marginal posterior distribution P(XzIZ) on node x, can be efficiently computed by

When both the potential function ψ _y {Xi, X ₇ ) and the observation likelihood #>,(z,|x,) are Gaussian distributions, equation (6) can be evaluated analytically and thus equation (7) can be analytically computed. However, situations arise where the observation likelihood functions

φ,(z,\x,) can only be modeled with non-Gaussian distributions. In such cases, the messages HIy(X ₁ ) are also non-Gaussians, thereby making the computation intractable. [0050] According to one embodiment, to resolve this problem and improve flexibility, a

Monte Carlo approximation may be applied within the belief propagation formulation, resulting in a belief propagation Monte Carlo (BPMC) algorithm. Both the message m _y (x,) and the marginal posterior distribution -P(x,|Z) may be represented as weighted sample sets by

IXIy- (X ₄ ) ~ {5S ⁿ⁾ _{) W} ? ⁱⁿ⁾ }!L _l .j e ^(x,) ₍₈₎

In these equations, s and π respectively denote the samples drawn and the associated weights. That is, these samples are used to approximate the distribution P(X ₁ ]Z). The iterative computation for the belief propagation may be implemented based on these weighted sample sets as summarized in Figure 8.

[0051] In both the non-parametric belief propagation and PAMPAS algorithms, the messages as well as the marginal distributions are modeled with Gaussian mixtures, and the message passing process is carried out by a Markov chain Monte Carlo (MCMC) algorithm. Descriptions of these concepts can be found in Nonparametric Belief Propagation, E. Sudderth, A. Ihler, W. Freeman, and A. Willsky, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pages 605-612, 2003, and in PAMPAS: Real- Valued Graphical Models for Computer Vision, M. Isard, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pages 613-620, 2003, both of which are incorporated by reference herein in their entirety. In contrast, the BPMC algorithm models both the messages and marginal distributions with weighted samples, and the message passing process may be computed efficiently based on the samples drawn from an importance sampling. In the BPMC algorithm, good importance functions lead to efficient computation and better inference results. It will be shown below how good importance functions for drawing samples of body parts using visual cues are constructed. These concepts will be illustrated by application to estimating the pose of soccer players in images, wherein certain image cues can be exploited for computational efficiency. IMPORTANCE FUNCTION FOR HEAD POSE

[0052] The AdaBoost-based face detector has demonstrated success in efficiently detecting faces in images of humans. A description of this can be found in Viola and Jones,

which was referenced above. However, this view-based detector performs best in detecting faces in upright frontal views, although this limitation can be alleviated by utilizing a multi- view extension. Figure 9(a) shows an example face detected by the AdaBoost-based detector. [0053] A common problem with this face detector is that the raw detection results are not very accurate. For example, the bounding rectangles often enclose background pixels and do not enclose the faces with the correct pose. Since skin color pixels occupy the majority of a rectangular area enclosing a face, according to one embodiment, a &-means algorithm (k = 2) is applied to group the pixels within the rectangle into skin and non-skin clusters. The center of the face rectangle is then repositioned to the centroid of the cluster of skin color pixels. The rectangular shape is then projected onto the learned PCA subspace of the head shape, thereby obtaining its intrinsic pose parameters as defined in equation (2). An approximated head pose Ix/, is obtained, along with the extrinsic rotation, scaling and translation parameters extracted from the face rectangle. Thereby, the importance sampling function for the head pose is obtained 316: Iz ₁ (X/,) ~ JV(Xj ₁ IlXz ₁ , Ε _h ) ₍₁₀ ) where Ix _h is the identity matrix of xj, and Σ _/ , is a diagonal covariance matrix. IMPORTANCE FUNCTIONS FOR ARM AND LEG POSE

[0054] Soccer players often wear short sleeve shirts and short trunks, and consequently skin color is a salient cue for locating lower-arm and upper-leg regions. According to one embodiment, a skin color model is next constructed 320 from the pixels of the skin color cluster obtained as discussed above. A 2-D color histogram is computed from the normalized RGB pixel values of the skin color cluster. Although it is difficult and time consuming to develop a generic skin color model to account for all variations (e.g., resulting from lighting and race factors), it is relatively easy and effective to construct a skin color model specific to a human subject considered for pose estimation, and consequently skin color regions can be extracted effectively with thresholds. Figure 9(b) shows some segmentation results using the learned skin color histogram, and Figure 9(c) shows the resulting best-fit quadrangles after discarding small "blobs." It should be noted that the number of skin tone blobs do not necessarily match the number of body parts.

[0055] Geometric cues such as shape, size, position, and orientation with respect to the head position of a human can be exploited to generate good pose hypotheses for the lower- arm and upper-leg body parts from these best-fit rectangles. The hypotheses for the upper-arm

and the lower-leg are then generated by first rotating the shape with respect to the link point of the corresponding lower-arm and the upper-leg hypotheses, respectively. The image likelihoods are then evaluated based on edge response using equations (4) and (5) for each rotation angle. The hypotheses with maximum likelihoods for upper-arm and lower-leg parts are selected for importance functions. Figure 9(d) shows one hypothesis for each of the upper- arm and lower-leg. The importance sampling function for the arm and leg pose is modeled 324 by a Gaussian mixture of these hypotheses. That is, after obtaining K good pose hypothesis Ix, , n = 1, . . ., K for body part i, samples are drawn from the importance function

K.

Mx.) ~ ∑ ^V-(X ₅ IIXJ" ⁾ , ∑0, i E S \ {h, t]

«=! *- (11) where Σ, is a diagonal covariance matrix. Note that a small number of K good hypotheses facilitate efficient sampling and inference processes, although there may be adverse effects if the number is too small. The optimum value of K depends on the application. According to one embodiment, a value of K of 8 is used. IMPORTANCE FUNCTIONS FOR TORSO POSE

[0056] Locating the torso region may be the most important task in human pose estimation, since it connects to most other body parts. However, detecting a torso is difficult, as it is usually clothed, and therefore exhibits a large variation in appearance. Also, the torso usually lacks salient image cues, e.g., color and texture, to facilitate the detection process. According to one embodiment, line segments are extracted 328 from a probabilistic Hough transform and used to assemble good shape hypotheses for the torso. A description of this can be found in Kiryati and Eldar, which was referenced above.

[0057] A Canny edge detector is first applied to build an edge map, and then a probabilistic Hough transform is performed to detect the substantially horizontal and substantially vertical line segments. For each combination of a pair of vertical line segments, hi, Ui, and a pair of horizontal line segments, /^ ₁ , hi, let the corner points of the assembled shape be /? _V I,AI _> Pvi,h2 _> Pvi,h\, and/> _V 2,Λ2 respectively. Torso hypotheses are obtained by solving an optimization problem with an objective function specified by the following criteria:

1. The normalized shape of a good torso hypothesis should be reconstructed by the learned PCA subspace of the torso with minimum error,

2. A good hypothesized torso should be as close to the detected face as possible, and

3. The two vertical lines, / _vl , / _v2 should be as symmetric as possible in the assembled shape, subject to the constraints that/? _v i,Λi _> /M,*2, _. Pv2,/ιb and/» _v2 ,Λ2 are within the range of image. [0058] For each of the M torso hypotheses Ix/ ^M) obtained by solving the above- mentioned optimization problem, with n = 1, . . . , M and usually M < 10, the response of edges extracted by the Canny detector with likelihood /?/ ⁿ⁾ is computed using functions similar to equations (4) and (5). The importance sampling function for the torso pose is specified 332 by a Gaussian mixture, e.g.,

where Σ, is the diagonal covariance matrix. Figure 10(a) repeats the soccer player of Figure 9(a). Figure 10(b) shows one example of the detected substantially horizontal and substantially vertical line segments from the probabilistic Hough transform, and Figure 10(c) shows the corresponding torso hypotheses. Although the number of combinations using horizontal and vertical lines is large, solving the above-mentioned optimization problem significantly prunes the number of torso hypotheses, e.g., M < 10, thereby facilitating efficient and effective inference.

[0059] According to one embodiment, the data-driven importance functions for the body parts are next incorporated into the belief propagation Monte Carlo framework of Figure 1, as described above. Equation (1) is solved by performing 336 belief propagation, e.g., local message passing, as summarized by Figure 8. This may be accomplished via local computation, for example, using processor 122 and program 116.

[0060] Persons skilled in the art will appreciate that while a particular embodiment of the method of the invention has been described, other embodiments are possible. For example, data-driven importance sampling for the head pose, arm and leg pose, and torso (steps 316, 324 and 332 respectively) may be performed in parallel, rather than sequentially as described.

EXPERIMENTAL RESULTS

[0061] The method of the invention was applied to estimate pose in images of soccer players. Persons skilled in the art will appreciate that the method can be extended to estimate human pose in other image domains as well. To demonstrate the effectiveness of the likelihood function discussed above, a number of lower-left leg hypotheses were generated by

translating the correctly labeled body part horizontally, as shown in Figure 1 l(a). The corresponding likelihoods are shown in Figure 1 l(b), wherein it is shown that the maximum likelihood occurs at the correct labeled location, i.e., 0 horizontal translation. The two next- smaller peaks correspond to the cases when one of the left and right lines of the shape pose is aligned with the boundary of the left-lower-leg in the image. The likelihood plots for the other body parts are similar to Figure 1 l(b), except that the likelihood model for the torso may not peak at the correct labeled location and may have more local peaks (due to noisy edge response). This reflects the difficulty of constructing a likelihood model of the torso using only edge cues.

[0062] To learn the PCA subspace for each body part, a set of 50 training images of soccer players was collected, and the quadrangular shapes and poses of human body parts were manually labeled. For pose estimation experimentation, another set of 30 target images of soccer players was collected, and the body parts were first manually located to establish the "ground truth." These images represented humans with large variation in pose and background, as well as occlusions either due to clothing or view angles. The values of the diagonal covariance matrices in the importance functions of equations (10)-(12) were empirically learned from the training image set.

[0063] Empirical results of estimating pose in single target images according to one embodiment are illustrated in Figure 12, wherein the best estimated shapes and locations of body parts are indicated by quadrangles. This embodiment draws 500 samples for each of the body parts, and the message passing process of the DDBPMC algorithm is iterated 6 times. The results show that the method of the invention is able to locate the body parts and estimate their pose well, even though they appear in the contexts of different posture, background, view angles and lighting conditions. The method is further able to infer poses which are heavily occluded, e.g., in Figure 12(e)-(f), through the benefit of data driven importance sampling from visual cues. For example, the left lower leg of the player in Figure 12(e) is located as a result of the best pose estimation, using image likelihoods and the importance function of equation (11). Similarly, the occluded body parts and their poses in Figures 12(g)- (h) are inferred using the proposed DDBPMC algorithm.

[0064] The accuracy of pose estimation was evaluated by computing the root mean square errors (RMSE) between the estimated body pose enclosed by quadrangles and the ground truth based on the corner points of the pair of corresponding quadrangles. The average

root of mean-square errors (RMSE) of each body part as well as that of the overall full body pose estimation over the 30 test images are presented in Figure 13. For each test image, the RMSE was computed for all of the body parts. The RMSE of the body parts comprising all of the test images was then computed. Upon first comparison, it may seem that the RMSE of the method of the invention is larger than the result of 20 test images reported in Lee and Cohen, which was referenced above, even though the test sets are different. However, the present evaluation computes the accuracy of four points for each body part, while Lee and Cohen only evaluated the accuracy of the joint locations, and thus a direct RMSE comparison is not justified. Furthermore, the number of points in the points set of the present evaluation is greater than that in used by Lee and Cohen. Another complicating factor is the difficulty of determining what the "ground truth" of body pose is, as a result of covered clothing and subjective variation in labeling body parts and pose. Finally, the average RMSE of each image is presented in Figure 14 to show the distribution of the overall RMSE among the 30 test images.

[0065] Advantages of the present invention include a system and method for estimating

2-D human pose from single target images. A Markov network and a data-driven Monte Carlo algorithm utilizing importance sampling functions provide efficient probabilistic inference. The method of the invention integrates reasoning mechanisms based on both overall body structure and on detailed characteristics of body parts. The algorithm can carry out inference tasks in parallel. Experimental results demonstrate the effectiveness of the method of the invention.

[0066] Persons skilled in the art will appreciate additional alternative designs for a system and method for estimating 2-D human pose from single images. Thus, 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 which will be apparent to those skilled in the art may be made in the arrangement, operation and details of the method and apparatus of the present invention disclosed herein without departing from the spirit and scope of the invention as defined in the appended claims.