Updating Image Segmentation Following User Input

• US 20110216976A1
• Filed: 03/05/2010
• Published: 09/08/2011
• Est. Priority Date: 03/05/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sharp, Toby, Kolmogorov, Vladimir, Rother, Carsten Curt Eckard, Blake, Andrew
• Granted Patent: US 8,655,069 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20096 Interactive definition of curve of interest
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/20104 Interactive definition of region of interest [ROI]
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06V 10/26 Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion

Abstract

Methods of updating image segmentation following user input are described. In an embodiment, the properties used in computing the different portions of the image are updated as a result of one or more user inputs. Image elements which have been identified by a user input are given more weight when updating the properties than other image elements which have already been assigned to a particular portion of the image. In another embodiment, an updated segmentation is post-processed such that only regions which are connected to an appropriate user input are updated.

Claims

1. A method comprising:

receiving, by a computer, at least one user input identifying a plurality of image elements in a segmented image as belonging to a first portion of the image, the segmented image comprising a first portion comprising image elements having a first label and a second portion comprising image elements having a second label;

updating properties associated with the first portion of the image giving more weight to the identified plurality of image elements than to other image elements in the first portion; and

updating the first and second portions of the segmented image based on the updated properties.

2. A method according to claim 1, wherein updating properties associated with the first portion of the image giving more weight to the identified plurality of image elements than to other image elements in the first portion comprises:

defining a first set of image elements comprising the identified plurality of image elements;

defining a second set of image elements comprising image elements having the first label excluding any elements in the identified plurality of image elements; and

updating properties associated with the first portion of the image based on a weighted combination of properties of image elements in the first portion, using a first weight in relation to the first set of image elements and a second weight in relation to the second set of image elements and wherein the first weight is larger than the second weight.

3. A method according to claim 1, wherein the properties associated with the first portion of the image comprises a Gaussian mixture model and wherein updating properties associated with the first portion of the image giving more weight to the identified plurality of image elements than to other image elements in the first portion comprises:

updating parameters of the Gaussian mixture model using a weighted average of a Gaussian mixture model component for each image element in the plurality of image elements and for each of the other image elements in the first portion, wherein a first weight is applied to the component for each image element in the plurality of image elements, a second weight is applied to the component for each of the other image elements in the first portion and the first weight is larger than the second weight.

4. A method according to claim 1, further comprising, prior to updating the first and second portions of the segmented image:

receiving, by the computer, at least one user input identifying a second plurality of image elements in the segmented image as belonging to the second portion of the image; and

updating properties associated with the second portion of the image giving more weight to the second identified plurality of image elements than to other image elements in the second portion.

5. A method according to claim 1, further comprising:

receiving, by a computer, a further user input identifying a further plurality of image elements in a segmented image as belonging to one of the portions of the segmented image;

further updating properties associated with said one of the portions of the segmented image giving more weight to the identified further plurality of image elements than to other image elements in said one of the portions; and

further updating the first and second portions of the segmented image based on the further updated properties.

6. A method according to claim 5, further comprising repeating the further updating steps on receipt of each additional further user input.

7. A method according to claim 1, wherein receiving at least one user input comprises receiving a plurality of user inputs and wherein the method further comprises:

dividing the plurality of user inputs into groups of user inputs, wherein each group of user inputs identifies a plurality of image elements in the segmented image as belonging to a first portion of the image,

and wherein the updating steps are performed separately for each group of user inputs.

8. A method according to claim 1, wherein the first portion comprises a foreground portion and the second portion comprises a background portion.

9. A method according to claim 1, wherein the updating of the first and second portions of the segmented image are performed by optimization of an energy function.

10. A method according to claim 1, wherein the user input comprises a user-defined brush stroke.

11. A method according to claim 1, further comprising:

displaying, on a display device, at least one of the updated first and second portions of the segmented image.

12. A method according to claim 1, further comprising:

computing a plurality of regions in the image, each region comprising connected image elements having the second label before updating the first and second portions and having the first label after updating the first and second portions; and

further updating the first and second portions of the segmented image by determining if a region comprises one of the plurality of identified image elements and if the region does not comprise one of the plurality of identified image elements, changing the label of each image element in the region from the first label to the second label.

13. A method comprising:

accessing, by a computer, first segmentation data for an image, the first segmentation data labeling image elements in the image as part of a first portion or a second portion of the image;

accessing user input data identifying a plurality of image elements as belonging to the first portion of the image;

accessing updated segmentation data computed from the first segmentation data based on said user input data;

computing a plurality of regions in the image, each region comprising connected image elements labeled as part of the second portion in the first segmentation data and labeled as part of the first portion in the updated segmentation data; and

generating output segmentation data from the updated segmentation data by labeling each image element in a region as part of the second portion if the region does not comprise one of the plurality of identified image elements.

14. A method according to claim 13, wherein the user input data further identifies a second plurality of image elements as belonging to the second portion of the image, the method further comprising:

computing a second plurality of regions in the image, each region in the second plurality of regions comprising connected image elements labeled as part of the first portion in the first segmentation data and labeled as part of the second portion in the updated segmentation data;

and wherein generating output segmentation data further comprises;

labeling each image element in one of the second plurality of regions as part of the first portion if the region does not comprise one of the second plurality of identified image elements.

15. A method according to claim 13, wherein the user input data comprises data relating to a plurality of user inputs received in response to displaying a segmented image according to the first segmentation data to a user.

16. A method according to claim 13, wherein the first portion and the second portion are each selected from a group comprising a background portion and a foreground portion.

17. A method according to claim 13, further comprising:

displaying, on a display device, at least one of the first and second portions of the image based on the output segmentation data.

18. A computer-implemented method of updating a segmented image based on at least one user input, the segmented image comprising a foreground portion and a background portion and the method comprising:

displaying at least the foreground portion of the segmented image to a user;

receiving at least one user input identifying a plurality of image elements in the segmented image as assigned to a first portion selected from the background and foreground portions of the segmented image;

updating properties of said first portion using a weighted combination of properties of each image element in the first portion, wherein a first weight is used for properties of the identified plurality of image elements and a second weight is used for properties of other image elements in said first portion and wherein the first weight is bigger than the second weight;

updating the foreground and background portions of the segmented image based on the updated properties;

computing a plurality of regions in the image, each region comprising connected image elements assigned to said first portion after updating and assigned to a second portion before updating, wherein the second portion is also selected from the background and foreground portions and is not the same as the first portion;

further updating the foreground and background portions of the segmented image by, for each of the plurality of regions in the image, assigning each image element in the region to the second portion if the region does not comprise one of the plurality of identified image elements; and

displaying at least the further updated foreground portion of the segmented image to the user.

19. A method according to claim 18, further comprising, prior to updating the foreground and background portions of the segmented image based on the updated properties:

receiving at least one user input identifying a second plurality of image elements in the segmented image as assigned to the second portion;

updating properties of said second portion using a weighted combination of properties of each image element in the second portion, wherein the first weight is used for properties of the identified second plurality of image elements and the second weight is used for properties of other image elements in said second portion.

20. A method according to claim 18, implemented in an image editing tool in a software application.