Foreground and background image segmentation

• US 8,625,897 B2
• Filed: 05/28/2010
• Issued: 01/07/2014
• Est. Priority Date: 05/28/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation), Taiwan Hopax Chems. Mfg. Co., Ltd.
• Original Assignee: Microsoft Corporation
• Inventors: Criminisi, Antonio, Shotton, Jamie Daniel Joseph, Fitzgibbon, Andrew, Sharp, Toby, Cook, Matthew Darius
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US12/790,026
• Publication Number:
  US 20110293180A1
• Time in Patent Office: 1,320 Days
• Field of Search: 382/173
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20048 Transform domain processing
• CPC Class Codes: G06T 2207/20156 Automatic seed setting
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/168 involving transform domain methods
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: H04N 13/239 using two 2D image sensors having a relative position equal to or related to the interocular distance H04N13/243 takes precedence

Abstract

Foreground and background image segmentation is described. In an example, a seed region is selected in a foreground portion of an image, and a geodesic distance is calculated from each image element to the seed region. A subset of the image elements having a geodesic distance less than a threshold is determined, and this subset of image elements are labeled as foreground. In another example, an image element from an image showing at least a user, a foreground object in proximity to the user, and a background is applied to trained decision trees to obtain probabilities of the image element representing one of these items, and a corresponding classification assigned to the image element. This is repeated for each image element. Image elements classified as belonging to the user are labeled as foreground, and image elements classified as foreground objects or background are labeled as background.

Claims

1. A computer-implemented method of segmenting a foreground portion from a background portion of an image, comprising:

receiving the image at a processor, wherein the image comprises a plurality of image elements, and the image represents at least one user, at least one foreground object in proximity to the at least one user, and a background;

accessing at least one trained decision tree stored on a memory;

selecting an image element from the image;

applying the image element to the or each trained decision tree to obtain one or more probabilities of the image element representing part of a user, a foreground object or background;

assigning a classification of user, foreground object or background to the image element in dependence on the one or more probabilities;

repeating the steps of selecting, applying and assigning for each image element in the image;

labeling the image elements having the classification of user as the foreground portion, and the image elements having the classification of foreground object and background as the background portion; and

subsequent to labeling the image elements;

selecting a first image element located at one side of the foreground portion and a second image element located at an opposing side of the foreground portion;

calculating a first set comprising a geodesic distance from each image element in the foreground portion to the first image element;

calculating a second set comprising a geodesic distance from each image element in the foreground portion to the second image element;

aggregating the geodesic distances in the first set over an axis of the image to form a first graph;

aggregating the geodesic distances in the second set over the axis of the image to form a second graph;

calculating an intersection area between the first graph and second graph; and

determining that two users are present in the image the intersection area is less than a predefined threshold.

2. A method according to claim 1, wherein the image is a depth image and each image element represents a distance from the at least one user, the at least one foreground object, or the background to a capture device.

3. A method according to claim 1, further comprising the step of, prior to accessing the at least one decision tree:

partially segmenting the image using a geodesic distance transform to remove at least a portion of the background image elements.

4. A method according to claim 1, wherein the at least one foreground object comprises at least one of:

a sofa;

a couch;

a chair;

a coffee table;

furniture;

a floor; and

a wall.

5. A method according to claim 1, further comprising, in case that two users are present in the image:

overlaying the first graph and second graph;

labeling image elements to one side of a cross-over point of the first and second graph as representing a first user; and

labeling image elements to an opposing side of the cross-over point of the first and second graph as representing a second user.

6. A method according to claim 5, wherein, in the case that the first and second user overlap in the image, labeling image elements in the cross-over point region with a probabilistic value of belonging to one of the first and second user.

7. A method according to claim 1, further comprising the step of training the at least one decision tree prior to receiving the image, wherein the step of training comprises:

receiving a plurality of training images, each comprising a plurality of image elements, wherein each image element has a classification representing one of a user, at least one foreground object in proximity to the user, or background;

selecting a decision tree from a random decision forest;

generating a random set of test parameters to apply at a node of the decision tree;

applying the set of test parameters to at least a portion of the image elements of the training images at the node;

selecting a subset of test parameters providing discrimination between the image element classifications and storing the subset in association with the node; and

repeating the steps of generating, applying, selecting and storing for each node in the or each decision tree.

8. A method according to claim 7, wherein the training images are computer-generated depth images each comprising at least one artificially synthesized user and foreground object.