Image segmentation using reduced foreground training data

• US 8,422,769 B2
• Filed: 03/05/2010
• Issued: 04/16/2013
• Est. Priority Date: 03/05/2010
• Status: Expired due to Fees

• 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): Bayat, Ali
• Application Number:
  US12/718,321
• Publication Number:
  US 20110216965A1
• Time in Patent Office: 1,138 Days
• Field of Search: 382/159, 382/173, 382/162, 382/166, 382/167, 382/190, 382/199, 358/453, 358/538, 358/1.15, 358/1.16, 348/43, 348/169
• US Class Current: 382/159
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

Methods of image segmentation using reduced foreground training data are described. In an embodiment, the foreground and background training data for use in segmentation of an image is determined by optimization of a modified energy function. The modified energy function is the energy function used in image segmentation with an additional term comprising a scalar value. The optimization is performed for different values of the scalar to produce multiple initial segmentations and one of these segmentations is selected based on pre-defined criteria. The training data is then used in segmenting the image. In other embodiments further methods are described: one places an ellipse inside the user-defined bounding box to define the background training data and another uses a comparison of properties of neighboring image elements, where one is outside the user-defined bounding box, to reduce the foreground training data.

Claims

1. A computer-implemented method of segmenting an image into foreground and background portions, the method comprising:

determining a foreground training region and a background training region of the image;

determining foreground and background properties based on said foreground and background training regions; and

computing foreground and background portions of the image by optimizing a first energy function,

wherein the first energy function comprises a function of the foreground and background properties, and

wherein the step of determining a foreground training region and a background training region of the image comprises;

receiving, at a computer, a user input defining a region of the image;

on the basis of the user input, segmenting the image into a first portion comprising image elements having a foreground label and a second portion of image elements having a background label, wherein the foreground label comprises a segmentation parameter which has a first value and the background label comprises a segmentation parameter which has a second value;

defining a second energy function comprising a combination of the first energy function and an additional term, the additional term comprising a combination of a scalar value and the segmentation parameter for an image element, summed over a plurality of image elements;

optimizing the second energy function using a plurality of different values of the scalar value to produce a plurality of optimization results, each optimization result defining a candidate foreground training region and a candidate background training region; and

selecting one of the plurality of optimization results to provide the foreground and background training regions.

2. A method according to claim 1, wherein selecting one of the plurality of optimization results to provide the foreground and background training regions comprises:

selecting an optimization result with the smallest candidate foreground region which satisfies a condition that a distance of a largest connected component within the candidate foreground region to each side of the user-defined region is smaller than a defined threshold.

3. A method according to claim 2, wherein the defined threshold is defined with reference to at least one dimension of the user-defined region.

4. A method according to claim 2, wherein optimizing the second energy function using a plurality of different values of the scalar value to produce a plurality of optimization results comprises:

iteratively optimizing the second energy function using increasing values of the scalar value until the optimization result produced satisfies the selection condition.

5. A method according to claim 1, wherein optimizing the second energy function using a plurality of different values of the scalar value to produce a plurality of optimization results comprises:

determining initial background properties based on said second portion;

setting initial foreground properties to a uniform distribution; and

optimizing the second energy function using the initial background properties, the initial foreground properties and a plurality of different values of the scalar value.

6. A method according to claim 1, wherein computing foreground and background portions of the image by optimizing a first energy function uses an iterative optimization process.

7. A method according to claim 1, wherein the second energy function is

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

displaying, on a display device, at least one of the foreground and background portions of the image.

9. A method according to claim 1, wherein the step of determining a foreground training region and a background training region of the image further comprises:

assigning a background label to at least a subset of image elements outside the user-defined region;

for an image element in the user-defined region which has a neighbor image element assigned a background label, assigning a background label to the image element if a difference in properties associated with the image element and the neighbor image element is less than a threshold;

and wherein the step of selecting one of the plurality of optimization results to provide the foreground and background training regions comprises;

selecting one of the plurality of optimization results comprising a candidate foreground training region and a candidate background training region; and

identifying image elements in the candidate foreground training region assigned a background label; and

assigning the identified image elements to the candidate background training region instead of the candidate foreground training region to provide the foreground and background training regions.

10. A method according to claim 1, wherein the step of segmenting the image into a first portion comprising image elements having a foreground label and a second portion of image elements having a background label on the basis of the user input comprises, if the user-defined region comprises substantially all of the image:

defining an elliptical region inside the user-defined region, the elliptical region substantially touching each side of the user-defined region, wherein the first portion comprises image elements inside the elliptical region and the second portion comprises image elements outside the elliptical region.

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

12. A method according to claim 1, wherein the software application comprises one of a word processing application, a spreadsheet application, a slide presentation application, a database application and an email application.

13. A computer-implemented method of segmenting an image into foreground and background portions, the method comprising:

determining a foreground training region and a background training region of the image;

determining foreground and background properties based on said foreground and background training regions; and

computing foreground and background portions of the image by optimizing a first energy function,

wherein the first energy function comprises a function of the foreground and background properties, and

wherein the step of determining a foreground training region and a background training region of the image comprises;

receiving, at a computer, a user input defining a region of the image;

assigning a background label to at least a subset of image elements outside the user-defined region;

assigning a background label to an image element in the user-defined region which has a neighbor image element assigned a background label if a difference in properties associated with the image element and the neighbor image element is less than a defined threshold;

defining the background training region as those image elements assigned a background label and defining the foreground training region as other image elements within the user-defined region.

14. A method according to claim 13, wherein assigning a background label to an image element in the user-defined region which has a neighbor image element assigned a background label if a difference in properties associated with the image element and the neighbor image element is less than a defined threshold comprises:

defining a set of image elements comprising image elements in the user-defined region and image elements outside the user-defined region having a neighbor image element inside the user-defined region;

building a graph between neighboring pairs of image elements within the defined set of image elements;

assigning a label to each edge in the graph dependent upon whether a difference in properties associated with image elements connected by the edge is less than a defined threshold;

analyzing the graph and the labeled edges to compute a connected component which touches each side of the user-defined region; and

assigning a background label to image elements within the connected component.

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

displaying, on a display device, at least one of the foreground and background portions of the image.

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

17. One or more tangible device-readable storage media with device-executable instructions that, when executed by a computing system, direct the computing system to perform steps comprising:

displaying, on a display device, an image to a user;

receiving a user input defining a region of the image;

on the basis of the user input, determining a foreground training region and a background training region of the image;

determining foreground and background properties based on said foreground and background training regions;

computing foreground and background portions of the image by iteratively optimizing a first energy function, wherein the first energy function comprises a function of the foreground and background properties; and

displaying, on a display device, at least one of the foreground and background portions of the image,

wherein the step of determining a foreground training region and a background training region of the image comprises;

on the basis of the user input, segmenting the image into a first portion comprising image elements having a first opacity value and a second portion of image elements having a second opacity value;

defining a second energy function comprising the first energy function and an additional term, the additional term comprising a product of a scalar and an opacity value for an image element, summed over all image elements;

iteratively optimizing the second energy function using increasing values of the scalar to produce an optimization result defining a candidate foreground training region and a candidate background training region which satisfy predefined criteria;

using said optimization result to provide the foreground and background training regions.

18. One or more tangible device-readable storage media according to claim 17, wherein the second energy function is

19. One or more tangible device-readable storage media according to claim 17, wherein using said optimization result to provide the foreground and background training regions comprises:

assigning a background label to at least a subset of image elements outside the user-defined region;

for each image element in the user-defined region which has a neighbor image element assigned a background label, assigning a background label to the image element if a difference in properties associated with the image element and the neighbor image element is less than a threshold; and

defining a background training region comprising image elements in the candidate background training region and image elements in the candidate foreground training region assigned a background label; and

defining a foreground training region comprising image elements in the candidate foreground region not assigned a background label.

20. One or more tangible device-readable storage media according to claim 17, wherein the step of segmenting the image into a first portion comprising image elements having a first opacity value and a second portion of image elements having a second opacity value, if the user-defined region comprises substantially all of the image:

defining an elliptical region inside the user-defined region, the elliptical region substantially touching each side of the user-defined region, wherein the first portion comprises image elements inside the elliptical region and the second portion comprises image elements outside the elliptical region.