Updating image segmentation following user input

• US 8,655,069 B2
• Filed: 03/05/2010
• Issued: 02/18/2014
• Est. Priority Date: 03/05/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rother, Carsten Curt Eckard, Sharp, Toby, Blake, Andrew, Kolmogorov, Vladimir
• Primary Examiner(s): BEKELE, MEKONEN T
• Application Number:
  US12/718,343
• Publication Number:
  US 20110216976A1
• Time in Patent Office: 1,446 Days
• Field of Search: 382/173, 382/159, 382/165, 382/181, 382/124, 382/106, 345/180, 345/179, 345/157
• 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 the 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;

wherein,

the properties associated with the first portion of the image comprise a Gaussian mixture model and 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;

or

the method further comprises;

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.

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 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.

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

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

16. A system for updating a segmented image based on at least one user input, the segmented image comprising a foreground portion and a background portion and the system comprising:

one or more processors configured to;

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

receive 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;

update 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;

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

compute 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 update 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

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

17. A system according to claim 16, the one or more processors being further configured to, prior to updating the foreground and background portions of the segmented image based on the updated properties:

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

update 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.

18. A system according to claim 16, the one or more processors being further configured to provide an image editing tool in a software application.

19. A system according to claim 16, wherein the at least one user input includes a user-defined brush stroke.

20. A System according to claim 16, the one or more processors being further configured to repeat the further update on receipt of one or more additional further user inputs.