Spatio-temporal segmentation for video

• US 8,620,077 B1
• Filed: 07/01/2009
• Issued: 12/31/2013
• Est. Priority Date: 01/26/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Grundmann, Matthias, Kwatra, Vivek, Han, Mei
• Primary Examiner(s): Motsinger, Sean
• Application Number:
  US12/496,599
• Time in Patent Office: 1,644 Days
• Field of Search: None
• US Class Current: 382/173
• CPC Class Codes: G06V 20/49 Segmenting video sequences, i.e. computational techniques such as parsing or cutting the sequence, low-level clustering or determining units such as shots or scenes
• CPC Class Codes: H04N 5/91 Television signal processing therefor

Abstract

A video is segmented to produce volumetric video regions. Descriptors are created for the video regions. A region graph is created for the video, where the region graph has weighted edges incident to video regions and the weight of an edge is calculated responsive to the descriptors of the video regions incident to the edge. The region graph is segmented responsive to the weights of the edges incident to the video regions to produce a new region graph having new volumetric video regions comprised of merged video regions of the first region graph. The descriptions of the region graphs are stored in a data storage.

Claims

1. A method of using a computer to segment a video, comprising:

segmenting the video to produce volumetric video regions;

creating descriptors for the video regions;

generating a first region graph for the video, the first region graph having weighted edges incident to video regions, the weight of an edge calculated responsive to the descriptors of the video regions incident to the edge;

determining an internal variation of a first video region;

determining an internal variation of a second video region;

determining a weight of an edge incident to the first and second video regions;

merging the first and second video regions responsive to a determination that the weight of the edge incident to the first and second video regions is less than the internal variations of the first and second video regions to produce a second region graph comprising at least the merged first and second video region; and

storing descriptions of the first and second region graphs in a data storage.

2. The method of claim 1, further comprising:

analyzing the video to identify a plurality of scenes contained within the video; and

identifying a scene of the plurality of scenes for which segmentation is to be performed;

wherein the portion of the video forming the identified scene is segmented to produce the volumetric video regions.

3. The method of claim 1, wherein segmenting the video comprises:

defining a spatio-temporal segmentation graph for the video, wherein a node of the graph is associated with a pixel in the video and has 26 edges incident to other nodes within the video; and

segmenting the segmentation graph to produce the volumetric video regions.

4. The method of claim 1, wherein a video region comprises a plurality of pixels and wherein the descriptor for the video region describes an intensity of the plurality of pixels within the video region.

5. The method of claim 1, wherein creating descriptors for the video regions comprises:

creating histograms describing intensities of pixels within the video regions.

6. The method of claim 5, wherein generating a first region graph for the video comprises:

calculating a weight for an edge incident to a first video region and a second video region responsive to a comparison of first and second histograms respectively describing intensities of pixels within the first and second video regions.

7. The method of claim 1, further comprising:

determining a relaxed internal variation value;

wherein merging the first and second video regions is further responsive to a determination that the weight of the edge incident to the first and second video regions is less than the internal variation of the first video region summed with the relaxed internal variation value and less than the internal variation of the second video region summed with the relaxed internal variation value.

8. The method of claim 7, wherein the video is segmented via an iterative process and wherein the relaxed internal variation value is increased by a scale factor with each iteration.

9. A computer for segmenting a video, the computer comprising:

a computer-readable storage medium storing executable computer program instructions comprising instructions for;

segmenting the video to produce volumetric video regions;

creating descriptors for the video regions;

generating a first region graph for the video, the first region graph having weighted edges incident to video regions, the weight of an edge calculated responsive to the descriptors of the video regions incident to the edge;

determining an internal variation of a first video region;

determining an internal variation of a second video region;

determining a weight of an edge incident to the first and second video regions;

merging the first and second video regions responsive to a determination that the weight of the edge incident to the first and second video regions is less than the internal variations of the first and second video regions to produce a second region graph comprising at least the merged first and second video region; and

storing descriptions of the first and second region graphs in a data storage; and

a processor configured to execute the computer program instructions stored on the computer-readable storage medium.

10. The computer of claim 9, further comprising instructions for:

analyzing the video to identify a plurality of scenes contained within the video; and

identifying a scene of the plurality of scenes for which segmentation is to be performed;

wherein the portion of the video forming the identified scene is segmented to produce the volumetric video regions.

11. The computer of claim 9, wherein segmenting the video comprises:

defining a spatio-temporal segmentation graph for the video, wherein a node of the graph is associated with a pixel in the video and has 26 edges incident to other nodes within the video; and

segmenting the segmentation graph to produce the volumetric video regions.

12. The computer of claim 9, wherein a video region comprises a plurality of pixels and wherein the descriptor for the video region describes an intensity of the plurality of pixels within the video region.

13. The computer of claim 9, wherein creating descriptors for the video regions comprises:

creating histograms describing intensities of pixels within the video regions.

14. The computer of claim 13, wherein generating a first region graph for the video comprises:

calculating a weight for an edge incident to a first video region and a second video region responsive to a comparison of first and second histograms respectively describing intensities of pixels within the first and second video regions.

15. The computer of claim 9, further comprising instructions for:

determining a relaxed internal variation value;

wherein merging the first and second video regions is further responsive to a determination that the weight of the edge incident to the first and second video regions is less than the internal variation of the first video region summed with the relaxed internal variation value and less than the internal variation of the second video region summed with the relaxed internal variation value.

16. The computer of claim 15, wherein the video is segmented via an iterative process and wherein the relaxed internal variation value is increased by a scale factor with each iteration.

17. A non-transitory computer-readable storage medium storing executable computer program instructions for segmenting a video, the instructions comprising instructions for:

segmenting the video to produce volumetric video regions;

creating descriptors for the video regions;

generating a first region graph for the video, the first region graph having weighted edges incident to video regions, the weight of an edge calculated responsive to the descriptors of the video regions incident to the edge;

determining an internal variation of a first video region;

determining an internal variation of a second video region;

determining a weight of an edge incident to the first and second video regions;

merging the first and second video regions responsive to a determination that the weight of the edge incident to the first and second video regions is less than the internal variations of the first and second video regions to produce a second region graph comprising at least the merged first and second video region; and

storing descriptions of the first and second region graphs in a data storage.

18. The non-transitory computer-readable storage medium of claim 17, further comprising instructions for:

analyzing the video to identify a plurality of scenes contained within the video; and

identifying a scene of the plurality of scenes for which segmentation is to be performed;

wherein the portion of the video forming the identified scene is segmented to produce the volumetric video regions.

19. The non-transitory computer-readable storage medium of claim 17, wherein segmenting the video comprises:

defining a spatio-temporal segmentation graph for the video, wherein a node of the graph is associated with a pixel in the video and has 26 edges incident to other nodes within the video; and

segmenting the segmentation graph to produce the volumetric video regions.

20. The non-transitory computer-readable storage medium of claim 17, wherein a video region comprises a plurality of pixels and wherein the descriptor for the video region describes an intensity of the plurality of pixels within the video region.

21. The non-transitory computer-readable storage medium of claim 17, wherein creating descriptors for the video regions comprises:

creating histograms describing intensities of pixels within the video regions.

22. The non-transitory computer-readable storage medium of claim 21, wherein generating a first region graph for the video comprises:

calculating a weight for an edge incident to a first video region and a second video region responsive to a comparison of first and second histograms respectively describing intensities of pixels within the first and second video regions.

23. The non-transitory computer-readable storage medium of claim 17, further comprising instructions for:

determining a relaxed internal variation value;

wherein merging the first and second video regions is further responsive to a determination that the weight of the edge incident to the first and second video regions is less than the internal variation of the first video region summed with the relaxed internal variation value and less than the internal variation of the second video region summed with the relaxed internal variation value.

24. The non-transitory computer-readable storage medium of claim 23, wherein the video is segmented via an iterative process and wherein the relaxed internal variation value is increased by a scale factor with each iteration.