Foreground and Background Image Segmentation

• US 20110293180A1
• Filed: 05/28/2010
• Published: 12/01/2011
• Est. Priority Date: 05/28/2010
• Status: Active Grant

• 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, Sharp, Toby, Fitzgibbon, Andrew, Cook, Matthew Darius
• Granted Patent: US 8,625,897 B2
• Time in Patent Office: Days
• 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 having a plurality of image elements, each image element having an associated value, the method comprising:

selecting a seed region in the foreground portion of the image;

calculating, using a processor, a geodesic distance from each image element to the seed region using the associated values;

determining a subset of the image elements having a geodesic distance less than a predefined threshold; and

labeling the subset of the image elements as foreground image elements.

2. A method according to claim 1, wherein the step of selecting a seed region comprises:

comparing the image to a previously stored image on a storage device to detect at least one changed region; and

selecting the changed region to be the seed region.

3. A method according to claim 2, wherein the at least one changed region is caused by movement of at least one object in the image relative to the previously stored image.

4. A method according to claim 1, further comprising the steps of, prior to determining the subset:

generating a background seed using the geodesic distance from each image element to the seed region;

calculating, using the processor, a geodesic distance from each image element to the background seed using the associated values; and

calculating an overall geodesic distance for each image element by combining;

i) the geodesic distance from each image element to the seed region; and

ii) the geodesic distance from each image element to the background seed.

5. A method according to claim 4, wherein the step of combining comprises subtracting:

i) the geodesic distance from each image element to the seed region, from;

ii) the geodesic distance from each image element to the background seed.

6. A method according to claim 4, wherein the step of generating the background seed comprises selecting a predefined shape for the background seed such that regions of shortest geodesic distance to the seed region are at least partially surrounded by the background seed.

7. A method according to claim 1, wherein the image is received from a depth camera, and the associated values represent a detected distance from the depth camera.

8. A method according to claim 1, wherein the image is received from an RGB camera, and the associated values represent a color value.

9. A method according to claim 1, further comprising the step of subsequently analyzing each foreground image element using a machine learning classifier to classify each foreground image element as belonging to one of:

a user, a foreground object;

or background.

10. 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; and

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.

11. A method according to claim 10, 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.

12. A method according to claim 10, 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.

13. A method according to claim 10, 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.

14. A method according to claim 10, further comprising the steps of, 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.

15. A method according to claim 14, 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.

16. A method according to claim 15, 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.

17. A method according to claim 10, 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.

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

19. A device for automatically segmenting a foreground portion from a background portion of an image, wherein the image comprises a plurality of image elements, each having an associated value, and the image represents a user, at least one foreground object in proximity to the user, and a background, the device comprising:

an input interface arranged to receive the image from a capture device;

at least one processor; and

a memory arranged to store a decision forest comprising a plurality of distinct trained decision trees, and arranged to store executable instructions configured to cause the processor to;

select a seed region in the foreground portion of the image;

calculate a geodesic distance from each image element to the seed region using the associated values;

determine a subset of the image elements having a geodesic distance within a predefined threshold distance of the seed region;

select an image element from the subset;

apply the subset image element to each of the trained decision trees to obtain a plurality of probabilities of the subset image element representing the user, the foreground object or the background;

aggregate the probabilities from each of the trained decision trees and assign a classification of user, foreground object or background to the subset image element in dependence thereon;

repeat the steps of selecting, applying and aggregating for each image element in the subset; and

output the subset image elements having the classification of user as the foreground portion.

20. A device according to claim 19, wherein the device is one of:

a video game system or a depth camera.