Image foreground extraction using a presentation application

• US 8,559,732 B2
• Filed: 08/06/2008
• Issued: 10/15/2013
• Est. Priority Date: 08/06/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Rayner, Tyler Christian
• Primary Examiner(s): Alavi, Amir
• Assistant Examiner(s): CESE, KENNY A
• Application Number:
  US12/187,263
• Publication Number:
  US 20090060334A1
• Time in Patent Office: 1,896 Days
• Field of Search: None
• US Class Current: 382/224
• CPC Class Codes: G06F 16/4393 Multimedia presentations, e.g. slide shows, multimedia albums
• CPC Class Codes: G06F 3/04845 for image manipulation, e.g. dragging, rotation, expansion or change of colour
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• 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/194 involving foreground-background segmentation
• CPC Class Codes: G11B 27/034 on discs G11B27/036, G11B27/038 take precedence
• CPC Class Codes: G11B 27/10 Indexing; Addressing; Timing or synchronising; Measuring tape travel
• CPC Class Codes: G11B 27/34 Indicating arrangements indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D

Abstract

A presentation application is provided that allows a user to extract a portion of the foreground or background from an image. The user can define a polygon outlining a portion of the image, and can adjust the shape and width of the polygon. The presentation application may use the user-defined polygon to identify a background region associated with pixels lying entirely outside the polygon, a foreground region associated with pixels enclosed by the polygon, and a set of pixels that are initially unknown within the width of the polygon. The presentation application then determines whether each unknown pixel is part of the background, foreground, or part of both. Based on the classification, the presentation application can extract the foreground of the image and mask the remaining portions of the image.

Claims

1. A method of extracting a portion of an image, wherein the image is formed by a plurality of pixels, the method comprising:

displaying the image;

generating a polygon in response to receiving one or more user inputs;

displaying the polygon as an overlay on the displayed image;

categorizing each pixel of the plurality of pixels of the image as part of a foreground of the image or as part of a background of the image, wherein the categorizing comprises;

classifying each pixel of the plurality of pixels that is enclosed by an inner boundary of the polygon as part of the foreground;

classifying each pixel of the plurality of pixels that is not enclosed by an outer boundary of the polygon as part of the background;

determining whether each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon is one of the background, the foreground, or both the background and the foreground by;

scanning concentric circles around that pixel to locate a closest pixel of the plurality of pixels that has been classified as part of the background and a closest pixel of the plurality of pixels that has been classified as part of the foreground,

generating a first pixel path to the closest pixel that has been classified as part of the background, the first pixel path including a first plurality of pixels; and

generating a second pixel path to the closest pixel that has been classified as part of the foreground, the second pixel path including second plurality of pixels; and

classifying each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon as part of one of the background and the foreground based at least in part on a first accumulated sum of color resistance of the first plurality of pixels and a second accumulated sum of color resistance of the second plurality of pixels; and

extracting one of;

the foreground of the image by removing each pixel of the plurality of pixels that has been categorized as part of the foreground from the image; and

the background of the image by removing each pixel of the plurality of pixels that has been categorized as part of the background from the image.

2. The method of claim 1, wherein generating a polygon comprises receiving a plurality of user selections from the one or more user inputs to form vertices of the polygon.

3. The method of claim 1, wherein one of the one or more user inputs is a user request to close the polygon.

4. The method of claim 1, further comprising:

receiving a user indication to change a width of the polygon;

displaying the polygon with the changed width based on the user indication; and

categorizing each pixel of the plurality of pixels of the image according to the changed width of the polygon.

5. The method of claim 1, wherein categorizing each pixel of the plurality of pixels occurs in response to receiving a user indication to extract the portion of the image, the method further comprising re-displaying after the extracting one of the foreground of the image and the background of the image, wherein the pixels categorized as part of the other one of the foreground of the image and the background of the image are re-displayed in an altered form.

31. The method of claim 1 further comprising, in response to determining that a first boundary pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon is part of both the background and the foreground, computing a degree of association of the first boundary pixel with at least one of the foreground and the background.

32. The method of claim 1, wherein the scanning of concentric circles around each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon comprises scanning concentric circles of increasing radii around that pixel.

33. The method of claim 32, wherein the classifying each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon as part of one of the background and the foreground based on the determining comprises using a pixel walker algorithm on that pixel.

34. The method of claim 33, wherein the pixel walker algorithm ends at a foreground pixel.

35. The method of claim 33, wherein the pixel walker algorithm ends at a background pixel.

6. A method of extracting a portion of an image, wherein the image is formed by a plurality of pixels, the method comprising:

displaying the image;

generating a polygon in response to receiving one or more user inputs;

displaying the polygon as an overlay on the displayed image;

categorizing each pixel of the plurality of pixels of the image as part of a foreground of the image or as part of a background of the image, wherein the categorizing comprises;

classifying each pixel of the plurality of pixels that is enclosed by an inner boundary of the polygon as part of the foreground;

classifying each pixel of the plurality of pixels that is not enclosed by an outer boundary of the polygon as part of the background;

determining whether each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon is part of the background, the foreground, or both the background and the foreground by;

computing a plurality of color resistances between that pixel and each neighboring pixel,

comparing, based on the computed color resistances, one or more neighboring pixels with a guidance vector pointing towards one of a closest background pixel and a closest foreground pixel to identify pixel path, the pixel path including a plurality of pixels, and

computing a sum of color resistances of the plurality of pixels in the identified pixel path; and

classifying each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon as part of one of the background and the foreground based at least in part on the computed sum of the color resistances of the plurality of pixels in the identified pixel path; and

extracting one of;

the foreground of the image by removing each pixel of the plurality of pixels that has been categorized as part of the foreground from the image; and

the background of the image by removing each pixel of the plurality of pixels that has been categorized as part of the background from the image.

7. A method of analyzing a plurality of pixels of an image, the method comprising:

receiving a user input that classifies a first portion of the plurality of pixels as a first part of a foreground of the image and that classifies a second portion of the plurality of pixels as a first part of a background of the image; and

categorizing a first pixel of the plurality of pixels, wherein the first pixel is one of a plurality of contiguous pixels of the plurality of pixels, wherein each pixel of the plurality of contiguous pixels is not of the first portion and is not of the second portion, and wherein the categorizing comprises;

identifying a first pixel path leading away from the first pixel and directed towards the foreground of the image, the first pixel path including a first set of pixels;

identifying a second pixel path leading away from the first pixel and directed towards the background of the image, the second pixel path including a second set of pixels; and

classifying the first pixel as part of the foreground of the image or part of the background of the image based at least in part on a first total of color resistance accumulated from traversing the first set of pixels in the identified first pixel path and on a second total of color resistance accumulated from traversing the second set of pixels in of the identified second pixel path.

8. The method of claim 7, wherein at least one of the identifying the first pixel path and the identifying the second pixel path comprises determining a first color resistance between a first pair of a plurality of pairs of neighboring pixels of the plurality of contiguous pixels, and wherein each pair of the plurality of pairs of neighboring pixels comprises the first pixel.

9. The method of claim 8, wherein the first pair of the plurality of pairs of neighboring pixels is in a first direction, the method further comprising determining a respective color resistance between three other pairs of the plurality of pairs of neighboring pixels, wherein each pair of the three other pairs is in a respective direction that is different from the first direction.

10. The method of claim 9, wherein the first direction and the respective directions comprise directions up, up-right, right, and down-right.

11. The method of claim 7, wherein classifying the first pixel is further based on a first type of a pixel ending the first pixel path and a second type of a pixel ending the second pixel path.

12. The method of claim 7, further comprising identifying, for each pixel of the plurality of contiguous pixels, a first guidance vector pointing towards a closest foreground pixel.

13. The method of claim 12, wherein identifying the first pixel path comprises directing the first pixel path towards the closest foreground pixel based on the vector.

14. The method of claim 7, further comprising identifying, for each pixel of the plurality of contiguous pixels, a second guidance vector pointing towards a closest background pixel.

15. The method of claim 14, wherein identifying the second pixel path comprises directing the second pixel path towards the closest background pixel based on the second guidance vector.

16. An electronic device for performing an extraction of a portion of an image formed by a plurality of pixels, the electronic device comprising a display, an input device, and a processor, the processor operative to:

display the image on the display;

generate a polygon in response to receiving one or more user inputs from the input device;

display the polygon on the display as an overlay on the displayed image;

categorize each pixel of the plurality of pixels of the image as part of a foreground of the image or as part of a background of the image by;

classifying each pixel of the plurality of pixels that is enclosed by an inner boundary of the polygon as part of the foreground;

classifying each pixel of the plurality of pixels that is not enclosed by an outer boundary of the polygon as part of the background;

determining whether each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon is one of the background, the foreground, or both the background and the foreground by;

scanning concentric circles around that pixel to locate a closest pixel of the plurality of pixels that has been classified as part of the background and a closest pixel of the plurality of pixels that has been classified as part of the foreground,

generating a first pixel path to the closest pixel that has been classified as part of the background, the first pixel path including a first plurality of pixels; and

generating a second pixel path to the closest pixel that has been classified as part of the foreground, the second pixel path including second plurality of pixels; and

classifying each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon as part of one of the background and the foreground based at least in part on a first accumulated sum of color resistance of the first plurality of pixels and a second accumulated sum of color resistance of the second plurality of pixels; and

extract one of;

the foreground of the image by removing each pixel of the plurality of pixels that has been categorized as part of the foreground from the image; and

the background of the image by removing each pixel of the plurality of pixels that has been categorized as part of the background from the image.

17. The electronic device of claim 16, wherein the processor is further operative to receive a plurality of user selections from the one or more user inputs to form vertices of the polygon.

18. The electronic device of claim 16, wherein one of the one or more user inputs is a user request to close the polygon.

19. The electronic device of claim 16, wherein the processor is further operative to:

receive a user indication to change a width of the polygon;

display, on the display, the polygon with the changed width based on the user indication; and

categorize each pixel of the plurality of pixels of the image according to the changed width of the polygon.

20. The electronic device of claim 16, wherein the processor categorizes each pixel of the plurality of pixels in response to receiving a user indication to extract the portion of the image, and wherein the processor is further operative to re-display after the extracting one of the foreground of the image and the background of the image, wherein the pixels categorized as part of the other one of the foreground of the image and the background of the image are re-displayed in an altered form.

21. An electronic device for performing an extraction of a portion of an image formed by a plurality of pixels, the electronic device comprising a display, an input device, and a processor, the processor operative to:

display the image on the display;

generate a polygon in response to receiving one or more user inputs from the input device;

display the polygon on the display as an overlay on the displayed image;

categorize each pixel of the plurality of pixels of the image as part of a foreground of the image or as part of a background of the image by;

classifying each pixel of the plurality of pixels that is enclosed by an inner boundary of the polygon as part of the foreground;

classifying each pixel of the plurality of pixels that is not enclosed by an outer boundary of the polygon as part of the background;

determining whether each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon is part of the background, the foreground, or both the background and the foreground by;

computing a plurality of color resistances between that pixel and each neighboring pixel,

comparing, based on the computed color resistances, one or more neighboring pixels with a guidance vector pointing towards one of a closest background pixel and a closest foreground pixel to identify a pixel path, the pixel path including a plurality of pixels, and

computing a sum of color resistances of the plurality of pixels in the identified pixel path; and

classifying each pixel of the plurality of pixels that is situated between the inner boundary and the outer boundary of the polygon as part of one of the background and the foreground based at least in part on the computed sum of the color resistances of the plurality of pixels in the identified pixel path; and

extract one of;

the foreground of the image by removing each pixel of the plurality of pixels that has been categorized as part of the foreground from the image; and

the background of the image by removing each pixel of the plurality of pixels that has been categorized as part of the background from the image.

22. An electronic device for analyzing a plurality of pixels of an image, the electronic device comprising an input unit and a processor configured to:

receive a user input from the input unit that classifies a first portion of the plurality of pixels as a first part of a foreground of the image and that classifies a second portion of the plurality of pixels as a first part of a background of the image; and

categorize a first pixel of the plurality of pixels, wherein the first pixel is one of a plurality of contiguous pixels of the plurality of pixels, wherein each pixel of the plurality of contiguous pixels is not of the first portion and is not of the second portion, and wherein the processor is configured to categorize the first pixel by;

identifying a first pixel path leading away from the first pixel and directed towards the foreground of the image, the first pixel path including a first set of pixels;

identifying a second pixel path leading away from the first pixel and directed towards the background of the image, the second pixel path including a second set of pixels; and

classifying the first pixel as part of-the foreground of the image or part of the background of the image based at least in part on a first total of color resistance accumulated from traversing the first set of pixels in the identified first pixel path and on a second total of color resistance accumulated from traversing the second set of pixels in the identified second pixel path.

23. The electronic device of claim 22, wherein at least one of the identifying the first pixel path and the identifying the second pixel path comprises determining a first a color resistance between a first pair of a plurality of pairs of neighboring pixels of the plurality of contiguous pixels, and wherein each pair of the plurality of pairs of neighboring pixels comprises the first pixel.

24. The electronic device of claim 23, wherein the first pair of the plurality of pairs of neighboring pixels is in a first direction, wherein the processor is further configured to determine a respective color resistance between three other pairs of the plurality of pairs of neighboring pixels, and wherein each pair of the three other pairs is in a respective direction that is different from the first direction.

25. The electronic device of claim 24, wherein the first direction and the respective directions comprise directions up, up-right, right, and downright.

26. The electronic device of claim 22, wherein classifying the first pixel is further based on a first type of a pixel ending the first pixel path and a second type of a pixel ending the second pixel path.

27. The electronic device of claim 22, wherein the processor is further configured to identify, for each pixel of the plurality of contiguous pixels, a first guidance vector pointing towards a closest foreground pixel.

28. The electronic device of claim 27, wherein the processor is further configured to direct the first pixel path towards the closest foreground pixel based on the vector.

29. The electronic device of claim 22, wherein the processor is further configured to identify, for each pixel of the plurality of contiguous pixels, a second guidance vector pointing towards a closest background pixel.

30. The electronic device of claim 29, wherein the processor is further configured to direct the second pixel path towards the closest background pixel based on the second guidance vector.