Up-sampling binary images for segmentation

• US 8,411,948 B2
• Filed: 03/05/2010
• Issued: 04/02/2013
• 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:
  US12/718,232
• Publication Number:
  US 20110216975A1
• Time in Patent Office: 1,124 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/273, 348/247, 348/449, 348/419, 348/51, 348/589
• 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 method comprising:

receiving, by a computer, an image;

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

segmenting 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-scaling and smoothing 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, creating 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 method according to claim 1, wherein the up-scaling and smoothing is performed without using the received image.

3. A method according to claim 1, wherein up-scaling and smoothing the initial binary solution to create an interim solution comprises:

interpolating 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 method according to claim 3, wherein the smoothing kernel comprises a Gaussian kernel.

5. A method 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 method 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 method according to claim 1, wherein segmenting at least a part of the modified image into a background portion and a foreground portion to create an initial binary solution comprises:

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

determining properties corresponding to the foreground and background portions;

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

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

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

displaying, 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 method according to claim 1, implemented in an image editing tool in a software application.

10. A method 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 method according to claim 1, wherein the step of generating a modified image from the image is performed in response to receiving at least one user input.

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

accessing an image; and

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

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

segmenting 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-scaling and smoothing 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

generating 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. One or more tangible device-readable media according to claim 12, wherein the up-scaling and smoothing is performed without using the accessed image.

14. One or more tangible device-readable media according to claim 12, further comprising device-executable instructions that, when executed by a computing system, direct the computing system to perform a step comprising:

displaying at least one background or foreground portion of the image.

15. One or more tangible device-readable media 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. One or more tangible device-readable media according to claim 12, wherein up-scaling and smoothing the initial binary solution to form an interim solution comprises:

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

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

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

17. One or more tangible device-readable media according to claim 16, wherein the sampling and convolving is 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 computer-implemented method of segmenting an image into a foreground portion and a background portion comprising:

accessing the image;

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

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

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

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

19. A computer-implemented method according to claim 18, wherein segmenting the modified of the image comprises:

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

determining properties corresponding to the foreground and background portions;

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

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

20. A computer-implemented method 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.