Image segmentation using reduced foreground training data

• US 8,787,658 B2
• Filed: 03/19/2013
• Issued: 07/22/2014
• 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:
  US13/847,455
• Publication Number:
  US 20130216127A1
• Time in Patent Office: 490 Days
• Field of Search: 382/159, 382/162, 382/166, 382/167, 382/199, 382/190, 382/173, 358/453, 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
• CPC Class Codes: G06V 10/235 based on user input or interaction

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 system comprising:

one or more processors configured to;

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

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

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

the first energy function comprising a function of the foreground and background properties, and

the one or more processors configured to determine the foreground training region and the background training region of the image being further configured to;

receive a user input defining a region of the image;

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

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

optimize 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

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

2. A system according to claim 1, wherein the one or more processors being configured to select one of the plurality of optimization results to provide the foreground and background training regions comprises:

the one or more processors being configured to select 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 system according to claim 2, wherein the defined threshold is defined with reference to at least one dimension of the user-defined region.

4. A system according to claim 2, wherein the one or more processors being configured to optimize the second energy function using a plurality of different values of the scalar value to produce a plurality of optimization results comprises:

the one or more processors being configured to iteratively optimize the second energy function using increasing values of the scalar value until the optimization result produced satisfies the selection condition.

5. A system according to claim 1, wherein the one or more processors being configured to optimize the second energy function using a plurality of different values of the scalar value to produce a plurality of optimization results comprises the one or more processors being configured to:

determine initial background properties based on said second portion;

set initial foreground properties to a uniform distribution; and

optimize 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 system according to claim 1, wherein the one or more processors being configured to compute foreground and background portions of the image by optimizing a first energy function includes the one or more processors being configured to use an iterative optimization process.

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

8. A system according to claim 1, the one or more processors being further configured to:

display at least one of the foreground and background portions of the image.

9. A system according to claim 1, wherein the one or more processors being configured to determine a foreground training region and a background training region of the image further comprises the one or more processors being configured to:

assign 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, assign 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 one or more processors being configured to select one of the plurality of optimization results to provide the foreground and background training regions comprises the one or more processors being configured to;

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

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

assign 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 system according to claim 1, wherein the one or more processors being configured to segment 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 the one or more processors being configured to, if the user-defined region comprises substantially all of the image:

define 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 system according to claim 1, the one or more processors being configured to provide at least a portion of an image editing tool in a software application.

12. A system 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 system comprising:

one or more processors configured to;

determine a foreground training region and a background training region of an image;

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

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

the first energy function comprising a function of the foreground and background properties, and

the one or more processors being configured to determine a foreground training region and a background training region of the image comprising the one or more processors being configured to;

receive a user input defining a region of the image;

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

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

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

14. A system according to claim 13, wherein the one or more processors being configured to assign 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 the one or more processors being configured to:

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

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

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

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

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

15. A system according to claim 13, the one or more processors being further configured to:

display at least one of the foreground and background portions of the image.

16. A system according to claim 13, the one or more processors being configured to provide at least a portion of an image editing tool in a software application.

17. A system comprising:

one or more processors being configured to;

display an image to a user;

receive a user input defining a region of the image;

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

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

compute foreground and background portions of the image by iteratively optimizing a first energy function, the first energy function comprising a function of the foreground and background properties; and

display at least one of the foreground and background portions of the image,

the one or more processors being configured to determine a foreground training region and a background training region of the image comprising the one or more processors being configured to;

on the basis of the user input, segment 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;

define 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 optimize 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; and

use the optimization result to provide the foreground and background training regions.

18. A system according to claim 17, wherein the second energy function is

19. A system according to claim 17, wherein the one or more processors being configured to use the optimization result to provide the foreground and background training regions includes the one or more processors being configured to:

assign 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, assign 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

define 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

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

20. A system according to claim 17, the one or more processors being configured to segment 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 includes the one or more processors being configured to, if the user-defined region comprises substantially all of the image:

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