Up-sampling binary images for segmentation

• US 8,644,609 B2
• Filed: 03/19/2013
• Issued: 02/04/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
• Primary Examiner(s): Allison, Andrae S
• Application Number:
  US13/847,436
• Publication Number:
  US 20130208983A1
• Time in Patent Office: 322 Days
• Field of Search: 382/132, 382/168, 382/173, 382/190, 382/192, 382/197, 382/199, 382/203, 382/209, 382/242, 382/128, 382/133, 382/134, 382/171, 382/172, 382/224, 348/218.1, 348/231.99, 348/239, 348/586, 348/587
• US Class Current: 382/173
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• 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

A method of up-sampling binary images for segmentation is described. In an embodiment, digital images are down-sampled before segmentation. The resulting initial binary segmentation, which has a lower resolution than the original image, is then up-sampled and smoothed to generate an interim non-binary solution which has a higher resolution than the initial binary segmentation. The final binary segmentation for the image is then computed from the interim non-binary solution based on a threshold. This method does not use the original image data in inferring the final binary segmentation solution from the initial binary segmentation. In an embodiment, the method may be applied to all images and in another embodiment, the method may be used for images which comprise a large number of pixels in total or in single dimension and smaller images may not be down-sampled before segmentation.

Claims

1. A system comprising:

one or more processors configured to;

receive an image;

generate a modified image from the image, the modified image having a lower image resolution than the image;

segment at least a part of the modified image into a background portion and a foreground portion to create an initial binary solution, the initial binary solution comprising data labeling a plurality of image elements in the modified image as either background or foreground;

up-scale and smooth the initial binary solution to create an interim solution having a higher resolution than the initial binary solution and comprising a non-binary segmentation parameter associated with each of a plurality of image elements in the interim solution; and

based on a threshold, create a final binary segmentation solution from the interim solution, the final binary segmentation solution having substantially the same resolution as the interim solution and comprising data labeling a plurality of image elements in the received image as either background or foreground.

2. A system according to claim 1, wherein the one or more processors are configured to up-scale and smooth without using the received image.

3. A system according to claim 1, wherein the one or more processors being configured to up-scale and smooth includes the one or more processors being configured to interpolate the initial binary solution by convolution with a smoothing kernel to compute a non-binary segmentation parameter for each of a plurality of image elements in the interim solution.

4. A system according to claim 3, wherein the smoothing kernel comprises a Gaussian kernel.

5. A system according to claim 4, wherein the Gaussian kernel comprises a one-dimensional Gaussian kernel and wherein interpolating the initial binary solution by convolution with a smoothing kernel comprises processing rows and columns of the initial binary solution in two separate passes.

6. A system according to claim 5, wherein a standard deviation of the one-dimensional Gaussian kernel is substantially equal to 0.74 times the size of an image element in the initial binary solution.

7. A system according to claim 1, wherein the one or more processors being configured to segment the at least part of the modified image into the background portion and the foreground portion to create the initial binary solution includes the one or more processors being configured to:

segment the modified image into a foreground portion and a background portion;

determine properties corresponding to the foreground and background portions;

update the background and foreground properties based on the portions; and

update the foreground and background portions based on the updated background and foreground properties.

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

display, on a display device, at least one of a background and a foreground portion of the image, the background and foreground portions being determined using the final binary segmentation solution.

9. A system according to claim 1, the one or more processors being configured to implement an image editing tool in a software application.

10. A system according to claim 9, 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.

11. A system according to claim 1, wherein the one or more processors being configured to generate the modified image from the image includes the one or more processors being configured to generate the modified image from the image in response to receiving at least one user input.

12. A system comprising:

one or more processors configured to;

access an image; and

if a size parameter associated with the image is not less than a predefined threshold;

down-scale the image to create a modified image from the image, the modified image having a lower image resolution than the image;

segment the modified image to create an initial binary solution comprising a binary parameter associated with each of a plurality of image elements in the modified image, the binary parameter assigning an image element to a background or a foreground portion;

up-scale and smooth the initial binary solution to form an interim solution, the interim solution having a higher resolution than the initial binary solution and comprising a non-binary parameter associated with each of a plurality of image elements in the interim solution; and

generate a final binary segmentation solution based on a threshold value of the non-binary parameter, the final binary segmentation solution having a higher resolution than the initial binary solution and comprising data assigning a plurality of image elements in the accessed image to either a background or a foreground portion.

13. A system according to claim 12, wherein the one or more processors being configured to up-scale and smooth includes the one or more processors being configured to up-scale and smooth without using the accessed image.

14. A system according to claim 12, the one or more processors being further configured to display at least one background or foreground portion of the image.

15. A system according to claim 12, wherein the size parameter comprises one of a number of image elements in the image and a longest image dimension.

16. A system according to claim 12, wherein the one or more processors being configured to up-scale and smooth includes the one or more processors being configured to:

sample a smoothing kernel at an image element center in the interim solution;

convolve the smoothing kernel with the initial binary solution to compute a non-binary parameter for the image element; and

repeat the sampling and convolving steps for each of the plurality of image elements in the interim solution.

17. A system according to claim 16, wherein the sample and convolve are performed in two passes, one pass using a 1×

N Gaussian kernel and one pass using a N×

1 Gaussian kernel, where N is an integer.

18. A system comprising:

one or more processors configured to;

access an image;

down-scale the image to create a modified version of the image having a lower image resolution than the image;

segment the modified version of the image to generate an initial binary segmentation, the initial binary segmentation comprising data labeling a plurality of image elements in the modified version of the image as part of a background portion or a foreground portion;

generate an interim solution having a higher resolution than the initial binary segmentation by, for each of a plurality of image elements in the interim solution, computing a non-binary value by convolving an interpolation kernel centered on the image element with the initial binary segmentation;

based on a threshold, generate a final binary segmentation solution having substantially the same resolution as the interim solution and comprising data labeling a plurality of image elements in said image as part of a background portion or a foreground portion; and

display at least one background or foreground portion of said image.

19. A system according to claim 18, wherein the one or more processors being configured to segment the modified of the image includes the one or more processors being configured to:

segment the modified version of the image into a foreground portion and a background portion;

determine properties corresponding to the foreground and background portions;

update the background and foreground properties based on the portions; and

update the foreground and background portions based on the updated background and foreground properties.

20. A system according to claim 18, wherein computing a non-binary value by convolving an interpolation kernel centered on the image element with the initial binary segmentation uses a one-dimension Gaussian kernel and is performed in two passes, one operating on rows of image elements and one operating on columns of image elements.