Automatic video object extraction

• US 6,785,329 B1
• Filed: 12/21/1999
• Issued: 08/31/2004
• Est. Priority Date: 12/21/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation), Webassured.Com, Co.
• Original Assignee: Microsoft Corporation
• Inventors: Li, Shipeng, Zhang, Ya-Qin, Pan, Jinhui
• Primary Examiner(s): Vo, Tung T.
• Application Number:
  US09/468,985
• Time in Patent Office: 1,715 Days
• Field of Search: H04/N.732, H04/B.166, 375/240.01, 375/240.24, 375/240.25, 375/240.26, 375/240.27, 375/240.29, 382/103, 382/233, 382/164, 348/413.1, 348/416.1, 348/414.1, 348/699, 345/419
• US Class Current: 375/240.08
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30224 Ball; Puck
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: G06T 7/90 Determination of colour characteristics
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

Automatic video object extraction that defines substantially precise objects is disclosed. In one embodiment, color segmentation and motion segmentation are performed on a source video. The color segmentation segments the video by substantially uniform color regions thereof. The motion segmentation segments the video by moving regions thereof. The color regions and the moving regions are then combined to define the video objects. In varying embodiments, pre-processing and post-processing is performed to further clean the source video and the video objects defined, respectively.

Claims

1. A computer implemented method for extracting objects from a source video comprising:

performing color segmentation on a frame of the source video to segment the video to a first precision by substantially uniform color regions thereof;

performing motion segmentation on a plurality of frames of the source video to segment the video to a second precision by moving regions thereof; and

,

combining at least the moving regions resulting from the motion segmentation and the substantially uniform color regions resulting from the color segmentation to define the objects of the source video to a third precision;

wherein the third precision is greater than the first precision, and the first precision is greater than the second precision.

2. The method of claim 1, further comprising pre processing the frame of the source video to remove noise prior to performing color segmentation.

3. The method of claim 2, wherein pre processing the frame comprises applying a median filter on each of a plurality of color channels of the frame.

4. The method of claim 1, further comprising, prior to combining at least the moving regions and the substantially uniform color regions, generating a frame difference mask from two frames of the source video.

5. The method of claim 1, wherein the performing motion segmentation comprises performing motion segmentation on the at least three frames of the plurality of frames of the source video to produce at least two motion segmentation masks that are used to segment the video by moving regions thereof.

6. The method of claim 1, further comprising post processing the objects of the source video to remove noise from the objects.

7. The method of claim 6, wherein post processing the objects comprises removing small holes from the objects to generate integrated objects.

8. The method of claim 6, wherein post processing the objects comprises removing small regions from background areas of the source video to generate cleaner objects.

9. The method of claim 1, wherein performing color segmentation defines substantially precise boundaries of the objects extracted from the source video.

10. The method of claim 1, wherein performing color segmentation comprises growing the substantially uniform color regions by growing each of a plurality of seed pixels of the frame.

11. The method of claim 10, wherein performing color segmentation comprises merging smaller of the substantially uniform color regions with larger of the substantially uniform color regions.

12. The method of claim 1, wherein performing motion segmentation defines approximate boundaries of the objects extracted from the source video.

13. At least one machine readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

performing color segmentation on at least one frame of a plurality of frames of video to segment the video to a first precision by substantially uniform color regions;

performing motion segmentation on at least two frames of the plurality of frames of the video to segment the video to a second precision by moving regions; and

,

combining the substantially uniform color regions resulting from the color segmentation and the moving regions resulting from the motion segmentation to define objects of the video to a third precision;

wherein the third precision is greater than the first precision, and the first precision is greater than the second precision.

14. The at least one machine readable medium of claim 13, wherein the performing color segmentation comprises at least one of edge detection, a region technique, a Maximum A posteriori Probability (MAP) technique, and pixel growth.

15. The at least one machine readable medium of claim 13, wherein the performing color segmentation comprises obtaining a seed pixel and using the seed pixel to grow a neighborhood of pixels.

16. The at least one machine readable medium of claim 13, wherein the performing color segmentation comprises generating substantially homogenous color regions responsive to maximum and minimum values for the regions.

17. The at least one machine readable medium of claim 13, wherein the performing color segmentation comprises generating substantially homogenous color regions responsive to maximum and minimum values for the regions and at least one predetermined threshold.

18. The at least one machine readable medium of claim 13, wherein the performing color segmentation comprises merging relatively smaller color regions by integrating the relatively smaller color regions into relatively larger color regions.

19. The at least one machine readable medium of claims 13, wherein the performing motion segmentation comprises at least one of an optical flow technique, a block-based matching technique, a Maximum A posteriori Probability (MAP) technique, a simultaneous motion estimation and segmentation technique, and a region-based motion vector approach.

20. The at least one machine readable medium of claim 13, wherein the performing motion segmentation comprises determining motion vectors for a plurality of regions with respect to a first frame and a subsequent frame of the plurality of frames of the video.

21. The at least one machine readable medium of claim 20, wherein the motion vectors are determined with regard to the substantially uniform color regions resulting from the color segmentation or to a precursor of the substantially uniform color regions.

22. The at least one machine readable medium of claim 13, wherein the performing motion segmentation comprises (i) determining motion vectors for a plurality of regions using a matching error minimization technique and (ii) determining a motion mask using the motion vectors and at least one threshold.

23. The at least one machine readable medium of claim 13, wherein the performing color segmentation comprises determining at least one color segmentation mask and the performing motion segmentation comprises determining at least one motion segmentation mask.

24. The at least one machine readable medium of claim 13, wherein the combining the substantially uniform color regions and the moving regions comprises performing a mapping operation using the substantially uniform color regions and the moving regions.

25. The at least one machine readable medium of claim 24, wherein the performing the mapping operation comprises mapping an entirety of a particular substantially uniform color region to a particular moving region if a percentage of the particular substantially uniform color region that is assignable to the particular moving region exceeds a predetermined threshold.

26. The at least one machine readable medium of claim 13, wherein the method further comprises performing a frame difference operation to produce a frame difference mask that reflects an amount of difference between a first frame and a subsequent frame of the plurality of frames of the video.

27. The at least one machine readable medium of claim 26, wherein the combining the substantially uniform color regions and the moving regions comprises combining the substantially uniform color regions, the moving regions, and the frame difference mask to define the objects of the video.

28. The at least one machine readable medium of claim 13, wherein the combining the substantially uniform color regions and the moving regions comprises combining (i) the substantially uniform color regions, (ii) the moving regions, and (iii) one or more of a frame difference mask, a depth mask, and a texture mask to define the objects of the video.

29. The at least one machine readable medium of claim 13, wherein the method further comprises:

pre-processing the video prior to the performing color segmentation; and

post-processing the objects of the video.

30. At least one machine readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

generating a color segmentation mask that defines contours of objects of a video to a first precision based on colors of the video;

generating a motion segmentation mask that defines the contours of the objects of the video to a second precision based on motions of the video;

generating a frame difference mask that reflects differences in the video between a first frame and a second frame of the video; and

combining the color segmentation mask, the motion segmentation mask, and the frame difference mask to define the objects of the video;

wherein the combining defines the objects of the video to a third precision; and

wherein the third precision is greater than the first precision, and the first precision is greater than the second precision.

31. At least one machine readable medium comprising:

means for performing color segmentation on at least one frame of a plurality of frames of video to segment the video by substantially uniform color regions to a middle precision;

means for performing motion segmentation on at least two frames of the plurality of frames of the video to segment the video by moving regions to a precision that is lower than the middle precision; and

,

means for combining the substantially uniform color regions produced by the means for performing color segmentation and the moving regions produced by the means for performing motion segmentation to define objects of the video to another precision that is greater than the middle precision.