Image extraction from complex scenes in digital video

• US 7,729,422 B2
• Filed: 01/12/2006
• Issued: 06/01/2010
• Est. Priority Date: 12/21/2000
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Wilensky, Gregg D.
• Primary Examiner(s): VO, TUNG T
• Application Number:
  US11/331,498
• Publication Number:
  US 20060126719A1
• Time in Patent Office: 1,601 Days
• Field of Search: 348/239, 348/446, 382/164, 382/283, 382/254, 382/236, 382/232, 345/591, 375/240.01
• US Class Current: 375/240.01
• 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

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 video. An input defining an initial border region is received, which includes a border between a foreground portion and a background portion of an initial digital image in a digital video. A border region for another digital image in the digital video is generated. The initial and automatically generated 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 from a background portion of a digital video, the method comprising:

receiving an input defining an initial border region that includes a border between a foreground portion and a background portion of an initial digital image, the initial digital image being one of a sequence of digital images that define a digital video, the initial border region further including only a part of the foreground portion and only a part of the background portion, the border consisting of pixels that include contributions from the foreground portion and the background portion, the input including an inside path and an outside path;

automatically generating, based on the initial border region, a border region for another digital image of the sequence of digital images, the automatically generated border region including the border in the other digital image, only a part of the foreground portion, and only a part of the background portion, wherein automatically generating a border region for another digital image comprises;

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

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

determining an edge path transformation between the initial digital image and the other 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 other digital image, and wherein generating a border region is performed by one or more processors; and

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

2. The method of claim 1, wherein identifying the edge path for the other automatically generated border region comprises:

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

3. The method of claim 1, wherein identifying an edge path for the initial border region comprises:

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

4. The method of claim 3, further comprising:

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

5. The method of claim 1, wherein identifying an edge path for 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.

6. The method of claim 1, 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.

7. The method of claim 6, wherein determining a set of local edge path transformations comprises:

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

8. The method of claim 6, 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.

9. The method of claim 1, 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.

10. A computer program product, tangibly stored on a computer-readable storage medium, for masking a foreground portion from a background portion of a digital video, the product comprising computer program instructions operable to cause a processor to perform operations comprising:

receiving an input defining an initial border region that includes a border between a foreground portion and a background portion of an initial digital image, the initial digital image being one of a sequence of digital images that define a digital video, the initial border region further including only a part of the foreground portion and only a part of the background portion, the border consisting of pixels that include contributions from the foreground portion and the background portion, the input including an inside path and an outside path;

automatically generating, based on the initial border region, a border region for another digital image of the sequence of digital images, the automatically generated border region including the border in the other digital image, only a part of the foreground portion, and only a part of the background portion, wherein automatically generating a border region for another digital image comprises;

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

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

determining an edge path transformation between the initial digital image and the other 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 other digital image; and

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

11. The program product of claim 10, wherein identifying the edge path for the other automatically generated border region comprises:

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

12. The program product of claim 10, wherein identifying an edge path for the initial border region comprises:

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

13. The program product of claim 12, where the operations further comprise:

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

14. The program product of claim 10, wherein identifying an edge path for 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.

15. The program product of claim 10, 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.

16. The program product of claim 15, wherein determining a set of local edge path transformations comprises:

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

17. The program product of claim 15, 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.

18. The program product of claim 10, 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.

19. A system comprising:

a computer-readable medium comprising instructions;

one or more processors configured to execute the instructions to perform operations comprising;

receiving an input defining an initial border region that includes a border between a foreground portion and a background portion of an initial digital image, the initial digital image being one of a sequence of digital images that define a digital video, the initial border region further including only a part of the foreground portion and only a part of the background portion, the border consisting of pixels that include contributions from the foreground portion and the background portion, the input including an inside path and an outside path;

automatically generating, based on the initial border region, a border region for another digital image of the sequence of digital images, the automatically generated border region including the border in the other digital image, only a part of the foreground portion, and only a part of the background portion, wherein automatically generating a border region for another digital image comprises;

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

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

determining an edge path transformation between the initial digital image and the other 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 other digital image; and

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

20. The system of claim 19, wherein identifying the edge path for the other automatically generated border region comprises:

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

21. The system of claim 19, wherein identifying an edge path for the initial border region comprises:

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

22. The system of claim 21, further comprising operations including:

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

23. The system of claim 19, wherein identifying an edge path for 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.

24. The system of claim 19, 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.

25. The system of claim 24, wherein determining a set of local edge path transformations comprises:

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

26. The system of claim 24, 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.

27. The system of claim 19, 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.