Image extraction from complex scenes in digital video

• US 20020118875A1
• Filed: 12/21/2000
• Published: 08/29/2002
• Est. Priority Date: 12/21/2000
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Wilensky, Gregg D.
• Granted Patent: US 7,003,061 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20041 Distance transform
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

The invention provides methods and apparatus, including computer program products, implementing and using techniques for masking and extracting a foreground portion from a background portion of a digital image. In the method, a first input defining a first border region is received, which includes at least a part of the foreground portion and at least a part of the background portion in a first digital image. A second input defining a second border region is received, which includes at least a part of the foreground portion and at least a part of the background portion in a second digital image. An intermediary border region is interpolated for an image intermediary in time to the first and second digital images and the first, second, and intermediary border regions are used for masking the foreground portion from the background portion in the digital video.

Claims

1. A method for masking a foreground portion of a digital image from a background portion of a digital image, the digital image being part of a video comprising a time sequence of digital images, each image being defined by a plurality of pixels, the method comprising:

receiving a first input defining a first border region, the first border region including at least a part of the foreground portion and at least a part of the background portion in a first digital image;

receiving a second input defining a second border region, the second border region including at least a part of the foreground portion and at least a part of the background portion in a second digital image;

interpolating an intermediary border region for an image intermediary in time to the first and second digital images; and

using the first, second, and intermediary border regions for masking the foreground portion from the background portion in the digital video.

2. The method of claim 1 wherein receiving a first and a second input comprise:

receiving user inputs defining the border regions; and

where interpolating an intermediary border region comprises;

interpolating an intermediary border region automatically without user input.

3. The method of claim 1 wherein using the first, second, and intermediary border regions for masking the foreground portion from the background portion comprises:

determining for a pixel in a border region whether it includes data that is associated with the foreground portion; and

using the result of the determining step to mask the foreground portion from the background portion in the digital video.

4. The method of claim 1, further comprising the steps of:

estimating an intrinsic color value for a pixel in the first, second, and intermediary border regions; and

using the estimated intrinsic color value for extracting the foreground portion from the background portion.

5. The method of claim 1 wherein receiving inputs indicating the border regions comprises:

generating an inside path located inside a foreground portion; and

generating an outside path located outside the foreground portion and enclosing the inside path,

wherein pixels between the inside and outside paths belong to a border region.

6. The method of claim 5 wherein generating an inside path and an outside path comprise:

generating a vector-based inside path and a vector-based outside path.

7. The method of claim 2 wherein receiving inputs indicating the border regions comprises:

generating a single path having a width encompassing that of the border region.

8. The method of claim 7 wherein generating a single path comprises:

generating a vector-based single path.

9. The method of claim 7 wherein generating a single path comprises:

generating a single path having variable thickness throughout its length.

10. The method of claim 1 wherein using the first, second, and intermediary border regions for masking the foreground portion from the background portion comprises:

masking the foreground portion and a portion of the border region; and

applying Gaussian blur to the portion of the border region.

11. The method of claim 10, further comprising displaying the masked foreground portion and the portion of the border region.

12. The method of claim 1 wherein using the first, second, and intermediary border regions for masking the foreground portion from the background portion comprises:

masking the foreground portion and a portion of the border region;

determining the opacities of the pixels in the portion of the border region that is displayed with the foreground portion; and

changing the opacities for pixels having opacities greater than a threshold value.

13. The method of claim 12, further comprising displaying the masked foreground portion and the portion of the border region.

14. The method of claim 1 further comprising:

receiving an input defining a border region for a second foreground portion in the first digital image, the border region including at least a part of a second foreground portion and at least a part of the background portion;

receiving an input defining a border region for the second foreground portion in the second digital image, the border region including at least a part of the second foreground portion and at least a part of the background portion; and

interpolating an intermediary border region for the second foreground portion for an image intermediary to the first and second digital images.

15. The method of claim 1 further comprising:

receiving an input defming a first internal border region, the first internal border region being enclosed by the first border region, in a first digital image;

receiving an input defining a second internal border region, the second internal border region being enclosed by the second border region, in a second digital image;

interpolating an intermediary internal border region for an image intermediary in time to the first and second digital images; and

using the first, second, and intermediary border regions, and the first internal, second internal, and intermediary internal border regions for masking the foreground portion from the background portion in the digital video.

16. The method of claim 15, wherein the first internal border region, the second internal border region, and the intermediary internal border region comprise at least a part of the foreground portion.

17. The method of claim 15, wherein the first internal border region, the second internal border region, and the intermediary internal border region comprise at least a part of the background portion.

18. The method of claim 15, wherein the first internal border region, the second internal border region, and the intermediary internal border region comprise at least a part of the foreground portion and at least a part of the background portion.

19. The method of claim 1, wherein the foreground portion is an object.

20. A method for masking a foreground portion of a digital image from a background portion of a digital image, the digital image being part of a video comprising a time sequence of digital images, each image being defined by a plurality of pixels, the method comprising:

receiving an input defining an initial border region, the initial border region including at least a part of the foreground portion and at least a part of the background portion in an initial digital image;

automatically generating a border region for another digital image in the time sequence based on the initial border region; and

using the initial and automatically generated border regions for masking the foreground portion from the background portion in the digital video.

21. The method of claim 20 wherein receiving an input comprises:

receiving a user input defining the border region.

22. The method of claim 20 wherein using the initial and automatically determined border regions for masking the foreground portion from the background portion comprises:

determining for a pixel in a border region whether it comprises data that is associated with the foreground portion; and

using the result of the determining step to mask the foreground portion from the background portion in the digital video.

23. The method of claim 20 further comprising:

estimating an intrinsic color value for a pixel in the first, second, and intermediary border regions; and

using the estimated intrinsic color value for extracting the foreground portion from the background portion.

24. The method of claim 21 wherein receiving a user input indicating the border regions comprises:

generating an inside path located inside the foreground portion; and

generating an outside path located outside the foreground portion and enclosing the inside path, wherein pixels between the inside and outside paths belong to a border region.

25. The method of claim 24 wherein generating an inside path and an outside path comprise:

generating a vector-based inside path and a vector-based outside path.

26. The method of claim 21 wherein receiving a user input indicating the border region comprises:

generating a single path having a width encompassing the border region.

27. The method of claim 26 wherein generating a single path comprises:

generating a vector-based single path.

28. The method of claim 26 wherein generating a single path comprises:

generating a single path having a variable thickness throughout its length.

29. The method of claim 20 wherein using the initial and the automatically generated border regions for masking the foreground portion from the background portion comprises:

masking the foreground portion and a portion of the border region; and

applying Gaussian blur to the portion of the border region.

30. The method of claim 29 further comprising displaying the masked foreground portion and the portion of the border region.

31. The method of claim 20 wherein using the initial and the automatically generated border regions for masking the foreground portion from the background portion comprises:

masking the foreground portion and a portion of the border region;

determining the opacities of the pixels in the portion of the border region that is displayed with the foreground portion; and

changing the opacities for pixels having opacities greater than a threshold value.

32. The method of claim 31, further comprising displaying the masked foreground portion and the portion of the border region.

33. The method of claim 20 further comprising:

receiving an input defining an initial border region for a second foreground portion, the border region including at least a part of a second foreground portion and at least a part of the background portion in the digital image with the first foreground portion;

automatically generating a border region for the second foreground portion in another image in the time sequence based on the initial border region for the second foreground portion; and

using the initial and automatically generated border regions for masking the second foreground portion from the background portion in the digital video.

34. The method of claim 20 further comprising:

receiving an input defining an initial internal border region, the initial internal border region being enclosed by the initial border region, in a first digital image;

automatically generating an internal border region for another image in the time sequence based on the initial internal border region; and

using the initial internal and the automatically generated internal border regions for masking the foreground portion from the background portion in the digital video.

35. The method of claim 34, wherein the initial internal border region and the automatically generated internal border region comprise at least a part of the foreground portion.

36. The method of claim 34, wherein the initial internal border region and the automatically generated internal border region comprise at least a part of the background portion.

37. The method of claim 34, wherein the initial internal border region and the automatically generated internal border region comprise at least a part of the foreground portion and at least a part of the background portion.

38. The method of claim 20, wherein the foreground portion is an object.

39. The method of claim 20 wherein automatically generating a border region for another digital image comprises:

identifying an edge path in the initial border region, the edge path indicating edges of the foreground portion in the initial digital image;

identifying an edge path in an automatically generated border region, the edge path indicating edges of the foreground portion in the another digital image;

determining an edge path transformation between the initial digital image and the another digital image; and

applying the edge path transformation to the inside path and the outside path in the initial digital image in order to generate a border region in the another digital image.

40. The method of claim 39 wherein identifying the edge path in the another automatically generated border region comprises:

identifying the edge path using a snake algorithm operating on a previously identified edge path.

41. The method of claim 39 wherein identifying an edge path in the initial border region comprises:

finding points in the border region that have image gradient values exceeding a threshold value.

42. The method of claim 41 further comprising the step:

calculating an image gradient value for each color channel in the initial border region.

43. The method of claim 39 wherein identifying an edge path in the initial border region comprises:

copying the inside path and the outside path;

moving the copies of the inside path and the outside path towards each other and towards edges of the foreground portion using a snake algorithm; and

identifying the edge path as the path where copy of the inside path and the copy of the outside path converge into one path.

44. The method of claim 39 wherein determining an edge path transformation comprises:

determining a set of local edge path transformations, the set of local edge path transformations together forming the edge path transformation.

45. The method of claim 44 wherein determining a set of local edge path transformations comprises:

determining a local edge path transformation for each point in the edge path.

46. The method of claim 44 wherein determining a set of local edge path transformations comprises:

determining a translation, a rotation, and a scaling for each local edge path transformation in the set of local edge path transformations.

47. The method of claim 39 wherein applying the edge path transformation to the inside and outside path comprises:

applying a set of local transformations to each point in the inside path and to each point in the outside path, the set of local transformations forming the edge path transformation.

48. The method of claim 47 wherein applying a set of local transformations comprises:

applying a translation, a rotation, and a scaling as each local transformation of the inside path and the outside path.

49. A method for masking an object from a background in a digital video, the digital video comprising a time sequence of digital images, each image being defined by a plurality of pixels, the method comprising:

receiving a first user input defining a first border region, the first border region including at least a part of the object and at least a part of the background in a first digital image;

receiving a second user input defining a second border region, the second border region including at least a part of the object and at least a part of the background portion in a second digital image;

interpolating an intermediary border region for an image intermediary in time to the first and second digital images;

using the first, second, and intermediary border regions for masking the object from the background in the digital video;

using the first, second, and intermediary border regions for extracting the object from the background in the digital video; and

placing the masked and extracted object against a new background in another digital video.

50. Computer software, tangibly embodied in a computer-readable medium or a propagated carrier signal for masking a foreground portion of a digital image from a background portion of a digital image, the digital image being part of a video comprising a time sequence of digital images, each image being defined by a plurality of pixels, the software comprising instructions to perform the following operations:

receive a first input defining a first border region, the first border region including at least a part of the foreground portion and at least a part of the background portion in a first digital image;

receive a second input defining a second border region, the second border region including at least a part of the foreground portion and at least a part of the background portion in a second digital image;

interpolate an intermediary border region for an image intermediary in time to the first and second digital images; and

use the first, second, and intermediary border regions for masking the foreground portion from the background portion in the digital video.

51. Computer software, tangibly embodied in a computer-readable medium or a propagated carrier signal for masking a foreground portion of a digital image from a background portion of a digital image, the digital image being part of a video comprising a time sequence of digital images, each image being defined by a plurality of pixels, the software comprising instructions to perform the following operations:

receive an input defining an initial border region, the initial border region including at least a part of the foreground portion and at least a part of the background portion in an initial digital image;

automatically generate a border region for another digital image in the time sequence based on the initial border region; and

use the initial and automatically generated border regions for masking the foreground portion from the background portion in the digital video.