Methods and systems for determining and tracking extremities of a target

• US 8,963,829 B2
• Filed: 11/11/2009
• Issued: 02/24/2015
• Est. Priority Date: 10/07/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lee, Johnny Chung, Stachniak, Simon Piotr, Liu, Shao, Leyand, Tommer, Peeper, Craig
• Primary Examiner(s): SHENG, TOM V
• Application Number:
  US12/616,471
• Publication Number:
  US 20110080475A1
• Time in Patent Office: 1,931 Days
• Field of Search: 345/156, 382/103, 715/700, 715863-866
• US Class Current: 345/156
• CPC Class Codes: G06F 3/011 Arrangements for interaction with the human body, e.g. for user immersion in virtual reality blind teaching G09B21/00
• CPC Class Codes: G06F 3/012 Head tracking input arrangements
• CPC Class Codes: G06F 3/017 Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2219/2004 Aligning objects, relative positioning of parts
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 40/28 Recognition of hand or arm movements, e.g. recognition of deaf sign language static hand signs G06V40/113

Abstract

An image such as a depth image of a scene may be received, observed, or captured by a device. A grid of voxels may then be generated based on the depth image such that the depth image may be downsampled. A background included in the grid of voxels may also be removed to isolate one or more voxels associated with a foreground object such as a human target. A location or position of one or more extremities of the isolated human target may then be determined.

Claims

1. A method for determining extremities of a user, the method comprising:

receiving a depth image;

generating a grid of voxels based on the depth image;

removing a background included in the grid of voxels to isolate one or more voxels associated with a human target; and

determining a location or position of one or more extremities of the isolated human target by performing acts comprising;

determining a candidate for the one or more extremities;

generating a candidate cylinder based on the grid of voxels;

calculating a score for the candidate based on the candidate cylinder;

determining whether the score of the candidate exceeds an extremity threshold score; and

assigning a value of a voxel in the grid associated with the candidate to the location or position of the one or more extremities when the score exceeds the extremity threshold score.

2. The method of claim 1, wherein the one or more extremities comprises at least one of the following:

a head, a centroid, a shoulder, a hip, a leg, an arm, a hand, an elbow, a knee, and a foot.

3. The method of claim 1, wherein the acts further comprise estimating a center of the isolated human target, wherein estimating the center of the human target comprises calculating an average position of the voxels in the grid associated with the isolated human target.

4. The method of claim 1, wherein the acts further comprise determining a core volume of the isolated human target.

5. The method of claim 1, wherein the acts further comprise:

assigning a previous location of an extremity to the location or position of the one or more extremities when the score does not exceed the extremity threshold score.

6. The method of claim 1, wherein the acts further comprise:

sampling depth values of voxels in the grid indicative of defining an extremity shape;

determining whether the sampled depth values of the voxels deviate from one or more expected depth values of a two-dimensional pattern associated with the extremity shape; and

reducing a score associated with a voxel when the sampled depth value deviates from the expected depth values;

determining whether the score associated with the voxel has a highest value; and

assigning a value of the voxel having the highest value to the location or position of the one or more extremities.

7. The method of claim 1, wherein the acts further comprise:

defining a head-to-center vector based on locations or positions of a head and a center of the isolated human target;

creating an extremity volume box based on a displacement along head-to center vector; and

determining an orientation of the one or more extremities based on a line fit of depth values within the extremity volume box, wherein determining the orientation of the one or more extremities comprises calculating an extremity slope of an extremity vector associated with the one or more extremities based on the line fit of depth values.

8. The method of claim 1, wherein the acts further comprise:

creating a torso volume;

identifying voxels outside of the torso volume; and

labeling voxels outside the torso volume as being associated with the one or more extremities.

9. The method of claim 1, wherein the acts further comprise:

determining an anchor point and a limb average location;

generating a vector between the anchor point and the limb average location, wherein the vector defines a search direction;

determining a last valid voxel along the vector by searching from the anchor point in the search direction; and

associating a location or a position of the one or more extremities with the last valid voxel.

10. The method of claim 1, further comprising refining the location or position of the one or more extremities based on pixels associated with the one or more extremities in the depth image.

11. The method of claim 1, further comprising processing the one or more extremities.

12. A computer-readable storage device having stored thereon computer executable instructions for determining extremities of a user in a scene, the computer executable instructions comprising instructions for:

receiving a depth image comprising pixels;

downsampling the pixels in the received depth image to generate one or more voxels;

isolating one or more voxels associated with a human target; and

determining a location or position of a head of the isolated human target by performing acts comprising;

determining a candidate for the head;

generating a candidate cylinder based on the grid of voxels;

calculating a score for the candidate based on the candidate cylinder;

determining whether the score of the candidate exceeds a head threshold score; and

assigning a value of a voxel in the grid associated with the candidate to the location or position of the head when the score exceeds the head threshold score.

13. The computer-readable storage device of claim 12, wherein the acts further comprise:

assigning a previous location of the head to the location or position of the head when the score does not exceed the head threshold score.

14. The computer-readable storage device of claim 12, wherein the acts further comprise:

sampling depth values of voxels in the grid indicative of defining a head shape;

determining whether the sampled depth values of the voxels deviate from one or more expected depth values of a two-dimensional pattern associated with the head shape; and

reducing a score associated with a voxel when the sampled depth value deviates from the expected depth values;

determining whether the score associated with the voxel has a highest value; and

assigning a value of the voxel having the highest value to the location or position of the head.

15. The computer-readable storage medium of claim 12, further comprising instructions for refining the location or position of the head based on pixels associated with the head in the depth image.

16. The computer-readable storage medium of claim 15, wherein the instructions for refining the location or position of the head based on the pixels associated with the head in the depth image further comprises instructions for:

determining an averaging volume associated with the head based on a comparison of a running average and the location or position of the head;

scanning the pixels in the depth image associated with the averaging volume;

calculating a refined location or position of the head by averaging one or more values of one or more pixels in the averaging volume; and

refining the location or position of the head based on the refined location or position.

17. A system for determining extremities of a user, the system comprising:

a capture device, wherein the capture device comprises a camera component to receive a depth image of a scene; and

a computing device in operative communication with the capture device, wherein the computing device comprises a processor that generates a downsampled depth image based on one or more pixels in the depth image received from the capture device;

removes a background of the downsampled depth image to isolate a human target; and

determines a location or position of one or more extremities of the isolated human target by performing acts comprising;

determining a candidate for the one or more extremities;

generating a candidate cylinder based on a grid of voxels;

calculating a score for the candidate based on the candidate cylinder;

determining whether the score of the candidate exceeds an extremity threshold score; and

assigning a value of a voxel in the grid associated with the candidate to the location or position of the one or more extremities when the score exceeds the extremity threshold score,

wherein the one or more extremities comprises at least one of a head, a centroid, a shoulder, a hip, a leg, an arm, a hand, or a foot.

18. The system of claim 17, wherein the acts further comprise:

assigning a previous location of an extremity to the location or position of the one or more extremities when the score does not exceed the extremity threshold score.

19. The system of claim 17, wherein the acts further comprise:

defining a head-to-center vector based on locations or positions of a head and a center of the isolated human target;

creating an extremity volume box on a displacement along the head-to center vector; and

determining an orientation of the one or more extremities based on a line fit of depth values within the extremity volume box, wherein determining the orientation of the extremity comprises calculating an extremity slope of an extremity vector associated with the one or more extremities based on the line fit of depth values.

20. The system of claim 17, wherein the acts further comprise:

determining an anchor point and a limb average location;

generating a vector between the anchor point and the limb average location, wherein the vector defines a search direction;

determining a last valid voxel along the vector by searching from the anchor point in the search direction; and

associating a location or a position of the one or more extremities with the last valid voxel.