Multiple centroid condensation of probability distribution clouds

• US 8,379,919 B2
• Filed: 04/29/2010
• Issued: 02/19/2013
• Est. Priority Date: 04/29/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bronder, Matthew, Williams, Oliver, Geiss, Ryan, Fitzgibbon, Andrew, Shotton, Jamie
• Primary Examiner(s): DRENNAN, BARRY T
• Application Number:
  US12/770,394
• Publication Number:
  US 20110268316A1
• Time in Patent Office: 1,027 Days
• Field of Search: None
• US Class Current: 382/103
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• 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: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 40/107 Static hand or arm
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements

Abstract

Systems and methods are disclosed for identifying objects captured by a depth camera by condensing classified image data into centroids of probability that captured objects are correctly identified entities. Output exemplars are processed to detect spatially localized clusters of non-zero probability pixels. For each cluster, a centroid is generated, generally resulting in multiple centroids for each differentiated object. Each centroid may be assigned a confidence value, indicating the likelihood that it corresponds to a true object, based on the size and shape of the cluster, as well as the probabilities of its constituent pixels.

Claims

1. A method of condensing centroids from a probability distribution cloud representing a plurality of parts of an object, comprising:

a) exemplar processing of a data sample set to assign a plurality of probabilities to each of the samples of said set, each assigned probability relating to the probability that one of said samples belongs to a respective one of said parts of the object;

b) combining the samples'"'"' positions with the assigned probabilities to produce a probability distribution cloud;

c) clustering one or more subgroups of the samples together to form one or more candidate centroids for the parts of the object, the clustering of one or more subgroups in said step c) depending on a proximity between the samples and the assigned probabilities.

2. The method of claim 1, further comprising the step of assigning a confidence value to the one or more candidate centroids, the confidence value for a centroid indicating the likelihood that the centroid corresponds to a correct part of the object.

3. The method of claim 2, said step of assigning a confidence value to the one or more candidate centroids comprising the step of assigning a confidence value based on a size and shape of a subgroup and the probabilities of its constituent samples.

4. The method of claim 1, said step c) of clustering one or more subgroups of the samples together to form one or more candidate centroids comprising the step of merging a pair of samples in a subgroup if they are close enough in space relative to their probabilities of being correctly classified.

5. The method of claim 1, said step c) of clustering one or more subgroups of the samples together to form one or more candidate centroids comprising the steps of:

d) squaring a distance between spatial positions of two candidate samples;

e) determining a normalized confidence of the two candidate samples; and

f) merging the two samples if the distance calculated in said step d) is less than the normalized confidence of the first candidate determined in said step e) multiplied by the normalized confidence of the second candidate determined in said step e) multiplied by a constant merge threshold value.

6. The method of claim 5, further comprising the step g) of sorting the two candidate samples by their respective normalized confidences if the two candidate samples are not merged in said step f).

7. The method of claim 6, said steps d) through g) comprising a step h) of performing steps d) through g) on pairs of adjacent samples in a subgroup of samples.

8. The method of claim 7, further comprising the steps of repeating said steps d) through g) on merged and/or sorted samples remaining after said step h).

9. The method of claim 5, further comprising the step of attenuating or amplifying the confidence of a sample based on the number of samples merged to form the sample and the size of the spatial region the sample represents in comparison to other samples which have been merged per step f).

10. In a system comprising a computing environment coupled to a capture device for capturing depth images of a body, a method of identifying real world objects, comprising:

a) determining depth information for a group of pixels captured by the capture device;

b) receiving exemplar classification results assigning a plurality of probabilities to said group of captured pixels, wherein each of said probabilities indicates that a group of captured pixels belongs to a respective one of said real world objects;

c) assigning each of a plurality of confidence scores to each of a plurality of candidates, the candidates being pixels in the group of captured pixels or centroids formed from pixels in the group of captured pixels, the confidence scores based in part on the exemplar classification in said step b); and

d) iteratively evaluating arrays of the candidates for merging together to form a next candidate set based on the candidates'"'"' proximity to each other in space and their confidence scores determined in said step c).

11. The method of claim 10, said step c) comprising the step of assigning a confidence value based on a size and shape of the group of pixels and the probabilities of its constituent pixels assigned in said step b).

12. The method of claim 10, further comprising the step f) of normalizing the confidence scores assigned in said step c).

13. The method of claim 10, said step d) comprising the step of iteratively evaluating two by two arrays of candidates.

14. The method of claim 10, said step d) comprising the steps of:

g) squaring a distance between spatial positions of two of said candidates;

h) determining a normalized confidence of the two candidates; and

j) merging the two candidates if the distance calculated in said step g) is less that the normalized confidence of the first of the two candidates determined in said step h) multiplied by the normalized confidence of the second of the two candidates determined in said step h) multiplied by a constant merge threshold value.

15. The method of claim 14, further comprising the step k) of sorting the two candidates by their respective normalized confidences if the two candidates are not merged in said step j).

16. The method of claim 10, said step d) comprising the step of iteratively evaluating a plurality of said arrays by parallel processing.

17. The method of claim 10, further comprising the step of repeating the iterative process of said step d) to produce a pyramid of centroids sorted regionally by normalized confidence and forming a quad tree in structure.

18. In a system comprising a computing environment coupled to a capture device for capturing depth images of a body, a method of identifying real world objects, comprising:

a) determining a plurality of depth patches by segmenting the depth image into regions of approximately constant depth;

b) assigning to each patch a list of the patches adjacent to said each patch to define a neighborhood graph;

c) processing exemplars by computing an average probability score assigned by an exemplar process to pixels in each of said patches;

d) identifying seed clusters as the set of said patches that have a higher score than all of their neighbors; and

e) growing clusters outward from the seed clusters.

19. The method of claim 18, said step e) comprising the steps of:

i) adding a neighbor cluster to a current seed cluster being grown if the neighbor is not assigned to any cluster,

ii) adding a neighbor cluster to a current seed cluster being grown if the neighbor is assigned to another cluster, but the current seed cluster has a higher confidence value, where the confidence value is based at least in part on the exemplars processed in said step c); and

iii) adding a neighbor cluster to a current seed cluster being grown if the total area dedicated to the current seed cluster does not exceed a predefined maximum value.

20. The method of claim 19, further comprising the step of updating the average probability scores after a neighbor has been added to the current seed cluster.