Spatio-temporal segmentation for video

1. A method for segmenting a video, comprising:

segmenting the video to produce video regions;

generating a region graph for the video having weighted edges incident to video regions, the weight of an edge based on properties of video regions incident to the edge;

determining if a weight of an edge incident to the first and second video regions is less than internal variations of the properties of the first and second video regions;

merging a first video region and a second video region to form a merged video region responsive to a determination that the weight of the edge incident to the first and second video regions is less than internal variations of the properties of the first and second video regions; and

storing descriptions of the region graph and the merged video region in a non-transitory computer-readable storage medium.

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

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.

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

defining a segmentation graph for the video, wherein the segmentation graph includes a node associated with a pixel in a video frame and nodes edges incident to the node and to surrounding nodes within the video frame, to associated nodes in a previous frame, and to associated nodes in a subsequent frame; and

segmenting the segmentation graph to produce the video regions.

4. The method of claim 1 , wherein a video region comprises a plurality of pixels and wherein the properties of the video region include properties of the plurality of pixels.

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

calculating the weight for the edge incident to the first video region and the second video region responsive to a comparison of properties of pixels within the first and second video regions.

6. The method of claim 1 , wherein merging a first video region and a second video region comprises:

determining a scalar value representing a granularity of the video regions;

determining a relaxed internal variation for the first video region and the second video region based on the internal variations of the properties of the first and second video regions and the determined scalar value; and

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 relaxed internal variation.

7. The method of claim 6 , wherein the video is segmented via an iterative process and wherein the scalar value increases with each iteration.

8. A system for segmenting a video, comprising:

a processor for executing computer program instructions;

a non-transitory computer-readable storage medium storing computer program instructions executable to:

segment the video to produce video regions;

generate a region graph for the video having weighted edges incident to video regions, the weight of an edge based on properties of video regions incident to the edge;

determine if a weight of an edge incident to the first and second video regions is less than internal variations of the properties of the first and second video regions;

merge a first video region and a second video region to form a merged video region responsive to a determination that the weight of the edge incident to the first and second video regions is less than internal variations of the properties of the first and second video regions; and

store descriptions of the region graph and the merged video region in a memory.

9. The system of claim 8 , wherein segmenting the video comprises:

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.

10. The system of claim 8 , wherein segmenting the video comprises:

defining a segmentation graph for the video, wherein the segmentation graph includes a node associated with a pixel in a video frame and nodes edges incident to the node and to surrounding nodes within the video frame, to associated nodes in a previous frame, and to associated nodes in a subsequent frame; and

segmenting the segmentation graph to produce the video regions.

11. The system of claim 8 , wherein a video region comprises a plurality of pixels and wherein the properties of the video region include properties of the plurality of pixels.

12. The system of claim 8 , wherein generating a region graph for the video comprises:

calculating the weight for the edge incident to the first video region and the second video region responsive to a comparison of properties of pixels within the first and second video regions.

13. The system of claim 8 , wherein merging a first video region and a second video region comprises:

determining a scalar value representing a granularity of the video regions;

determining a relaxed internal variation for the first video region and the second video region based on the internal variations of the properties of the first and second video regions and the determined scalar value; and

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 relaxed internal variation.

14. The system of claim 13 , wherein the video is segmented via an iterative process and wherein the scalar value increases with each iteration.

15. 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 video regions;

generating a region graph for the video having weighted edges incident to video regions, the weight of an edge based on properties of video regions incident to the edge;

determining if a weight of an edge incident to the first and second video regions is less than internal variations of the properties of the first and second video regions;

merging a first video region and a second video region to form a merged video region responsive to a determination that the weight of the edge incident to the first and second video regions is less than internal variations of the properties of the first and second video regions; and

storing descriptions of the region graph and the merged video region in a memory.

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

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.

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

defining a segmentation graph for the video, wherein the segmentation graph includes a node associated with a pixel in a video frame and nodes edges incident to the node and to surrounding nodes within the video frame, to associated nodes in a previous frame, and to associated nodes in a subsequent frame; and

segmenting the segmentation graph to produce the video regions.

18. The non-transitory computer-readable storage medium of claim 15 , wherein a video region comprises a plurality of pixels and wherein the properties of the video region include properties of the plurality of pixels.

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

calculating the weight for the edge incident to the first video region and the second video region responsive to a comparison of properties of pixels within the first and second video regions.

20. The non-transitory computer-readable storage medium of claim 15 , wherein merging a first video region and a second video region comprises:

determining a scalar value representing a granularity of the video regions;

determining a relaxed internal variation for the first video region and the second video region based on the internal variations of the properties of the first and second video regions and the determined scalar value; and

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 relaxed internal variation.