System and method for visually tracking occluded objects in real time

• US 6,674,877 B1
• Filed: 02/03/2000
• Issued: 01/06/2004
• Est. Priority Date: 02/03/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jojic, Nebojsa, Turk, Matthew A.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Choobin, Barry
• Application Number:
  US09/496,996
• Time in Patent Office: 1,433 Days
• Field of Search: 382/103, 382/285, 382/154, 382/173, 382/107, 382/104, 382/106, 382/118, 348/43, 348/48, 348/169, 348/208.14, 706/52, 345/848, 345/419, 342/90
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/251 involving models
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition

Abstract

The present invention is embodied in a system and method for digitally tracking objects in real time. The present invention visually tracks three-dimensional (3-D) objects in dense disparity maps in real time. Tracking of the human body is achieved by digitally segmenting and modeling different body parts using statistical models defined by multiple size parameters, position and orientation. In addition, the present invention is embodied in a system and method for recognizing mutual occlusions of body parts and filling in data for the occluded parts while tracking a human body. The body parts are preferably tracked from frame to frame in image sequences as an articulated structure in which the body parts are connected at the joints instead of as individual objects moving and changing shape and orientation freely.

Claims

1. A method for tracking an object having plural parts, wherein the object is tracked as an articulated structure, the method comprising:

obtaining digital representations of the object from multiple viewpoints;

generating disparity maps between the digital representations; and

digitally segmenting the disparity maps and modeling selected parts of the object using a predefined 3-D Gaussian statistical model of the object with fixed eigenvalues.

2. The method of claim 1, wherein the predefined statistical model is comprised of sub-models of the parts each defined by multiple parameters including size parameters comprised of at least one of position and orientation.

3. The method of claim 1, further comprising using the statistical model to recognize mutual object part occlusions.

4. The method of claim 3, further comprising filling in data for the occluded object parts with the statistically recognized mutual occlusions.

5. The method of claim 1, wherein the digital representation of the object is comprised of plural digital images sequentially ordered so that movement of the object is capable of being tracked.

6. The method of claim 5, further comprising correlating pixels of the multiple images to one another to determine the disparity map at each pixel of the images.

7. The method of claim 5, further comprising determining two dimensional coordinate points of the pixels and transforming each pixel into appropriate three dimensional points using its disparity map and the coordinate points.

8. The method of claim 7, further comprising using the three dimensional pixel points to compute a likelihood estimate of a posture of the articulated structure for each object part.

9. The method of claim 8, further comprising associating the pixel points with an object part having the highest likelihood estimate to define a segmentation map of the pixel points.

10. The method of claim 9, further comprising re-estimating pixel point associations by recomputing statistical parameters of the Gaussian models for selected object parts.

11. The method of claim 2, wherein the object is a human body and the parts of the object are human body parts.

12. The method of claim 11, wherein the statistical model is comprised of a human body represented by a human torso body connected to segmented upper and lower human body part limbs.

13. A method for tracking a human body having multiple body parts comprising:

obtaining a digital representation of the human body;

predefining generative statistical models of image formation for each body part and using the statistical models to recognize mutual body part occlusions;

filling in data for the occluded body parts with the statistically recognized mutual occlusions.

14. The method of claim 13, wherein the body parts are tracked from frame to frame in image sequences as an articulated structure in which the body parts are connected at associated joints.

15. The method of claim 14, wherein the predefined statistical models are Gaussian models defined by multiple parameters including size parameters comprised of at least one of position and orientation.

16. The method of claim 15, wherein the image sequences are ordered sequentially to simulate motion and further comprising correlating pixels of the multiple images to one another to determine a disparity map at each pixel of the images.

17. The method of claim 16, further comprising determining two dimensional coordinate points of the pixels and transforming each pixel into appropriate three dimensional points using its disparity map and the coordinate points.

18. The method of claim 17, further comprising using the three dimensional pixel points to compute a likelihood estimate of a posture of the articulated structure for each body part.

19. The method of claim 18, further comprising associating the pixel points with a body part having the highest likelihood estimate to define a segmentation map of the pixel points.

20. The method of claim 19, further comprising re-estimating pixel point associations by recomputing statistical parameters of the Gaussian models for selected body parts.

21. The method of claim 13, wherein the body parts are capable of moving and changing shape and orientation freely.

22. The method of claim 13, wherein the statistical models are graphical Bayesian networks that formalize generative processes to allow probabilistic inference.

23. The method of claim 14, further comprising determining a maximum likelihood estimate of a posture of the body parts of the articulated structure.

24. The method of claim 16, further comprising segmenting the disparity map into different body parts of the articulated structure using estimated states of Gaussian mixtures.

25. The method of claim 24, further comprising re-estimating statistical properties of the body parts.

26. The method of claim 25, further comprising enforcing articulation constraints to improve tracking performance by modeling the dynamics of the tracked object.

27. The method of claim 26, wherein the articulation constraints are enforced with an extended Kalman Filter.

28. An object tracking system for dynamically tracking articulated structures within a sequence of images, wherein the structures are made of segmented parts, comprising:

a predefined statistical model of each articulated structure;

a depth map processor that computes range image data and segments a disparity map into different parts of the structure;

a pixel classification processor that classifies pixels of each image within defined part segments; and

an occlusion detector and handler that estimates missing data and resolves the missing data as occluded parts.

29. The object tracking system of claim 28, further comprising a re-estimation processor that re-computes statistical parameters of the statistical models for different parts.

30. The object tracking system of claim 29, further comprising an enhancing filter that enhances the re-computations and a blob computation processor that computes individual model parameters.

31. The object tracking system of claim 28, wherein the statistical model is a multi-dimensional Gaussian model parametrically defined with part segments.

32. The object tracking system of claim 31, wherein the Gaussian model includes a mean value parameter and a covariance matrix parameter.

33. The object tracking system of claim 32, wherein the likelihood of a particular measurement depends on the distance from the mean value.

34. The object tracking system of claim 32, wherein the covariance matrix allows additional variability in one direction than in another.

35. The object tracking system of claim 32, wherein the covariance matrix is related to an ellipsoid describing an amount of variation in different directions of the parts.

36. The object tracking system of claim 35, wherein the covariance matrix has eigenvalues that are fixed allowing changes in position and orientation in space of the ellipsoid without changing the shape of the ellipsoid.

37. The object tracking system of claim 36, wherein the eigenvalues of the Gaussian model are fixed and used as a model of a human body part.

38. The object tracking system of claim 31, wherein the pixel classification processor determines coordinates of each pixel and uses the coordinate determinations with the disparity map to transform each pixel into an appropriate multi-dimensional point.

39. The object tracking system of claim 38, wherein the Gaussian model uses the multi-dimensional points for each pixel to compute a likelihood estimate of a posture of the articulated structure.

40. The object tracking system of claim 39, wherein the part of the Gaussian model with the best likelihood estimate of a particular pixel is considered as having been generated by that part.

41. The object tracking system of claim 39, wherein the part of the Gaussian model with the best likelihood estimate of the particular pixel is labeled and stored having a quantified probability that it was generated by that part.

42. The object tracking system of claim 38, wherein the pixel classification processor produces results comprised of a segmentation map that labels different pixels as belonging to different parts.

43. The object tracking system of claim 42, wherein the occlusion detector and handler uses the segmentation map, the Gaussian parameters and the range image data of the depth map to produce a set of additional multi-dimensional points at the occluded parts.

44. The object tracking system of claim 42, wherein the occlusion detector and handler produces a probability of occlusion for each pixel and a best estimate of occluded values.

45. The object tracking system of claim 43, wherein the occlusion detector and handler computes for each pixel an optimum depth value expected to be formed by a particular part of the statistical model and determines if an optimum value according to the particular part is significantly larger than a measured value and if the segmentation map has another part identified as having been generated by the particular part for assuming whether occlusion of the particular part occurs.

46. The object tracking system of claim 45, wherein if occlusion is assumed, the optimum measurement is added as the measurement for the particular part in order to fill in the occluded missing data.

47. The object tracking system of claim 43, wherein probabilities of different parts for each pixel exists and the missing data is added in probabilistic form, wherein with each added point a weight is added to control affects of re-estimation of Gaussian model statistics.

48. The object tracking system of claim 38, further comprising a re-estimation processor that re-computes means and covariance matrices as statistical parameters of the statistical models for different parts.

49. The object tracking system of claim 48, wherein recomputation of means and covariance matrices includes estimating mean values for each part by averaging all the multi-dimensional points corresponding to the pixels associated with that part in the segmentation map and the estimated missing data.

50. The object tracking system of claim 49, wherein the covariance matrices are computed using the segmentation map and the estimated missing data.

51. The object tracking system of claim 50, wherein the estimated means and covariance matrices and estimated speed and acceleration parameters of all parts are used to produce expected parameters of the articulated structure.

52. The object tracking system of claim 51, wherein an Extended Kalman Filter based on the articulation model is used to produce the expected parameters.

53. The object tracking system of claim 51, wherein nonlinear equations are related to the state of the articulated model with means and covariance matrices that include assumptions of constant size of a part and kinematic chain equations describing connection of the parts in the structure.

54. The object tracking system of claim 53, wherein dynamics of the articulated model are captured by a transition matrix and wherein the nonlinear equations are linearized with the Extended Kalman Filters and a state is found that best fits the dynamics and the measurements of the model.

55. The object tracking system of claim 46, wherein additional data defined by at least one of acquired data and given data, is used to fill in the parts that are missing due to occlusions.