Efficient Hierarchical Graph-Based Video Segmentation

Top: Ice-skater Yu-Na Kim, 2009 World Championships, © 2009 NBC Olympics.
Middle: Segmentation result computed in 20 min. Our algorithm is able to segment video of non-trivial length into perceptually distinct spatio-temporal regions. We maintain region identity and clear boundaries over all frames, despite significant motion, camera movement and zoom.
Bottom: User-selected regions, Ice-skater (green) selected by a single mouse click in one frame, Olympus sign (magenta) selected by two clicks.


You can try out our video segmentation here.

Our source code is available here.

Authors

Matthias Grundmann
Vivek Kwatra
Mei Han
Irfan Essa

Abstract
We present an efficient and scalable technique for spatio- temporal segmentation of long video sequences using a hierarchical graph-based algorithm.
We begin by over- segmenting a volumetric video graph into space-time regions grouped by appearance. We then construct a "region graph” over the obtained segmentation and iteratively repeat this process over multiple levels to create a tree of spatio-temporal segmentations. This hierarchical approach generates high quality segmentations, which are temporally coherent with stable region boundaries, and allows subse- quent applications to choose from varying levels of granularity. We further improve segmentation quality by using dense optical flow to guide temporal connections in the initial graph.
We also propose two novel approaches to improve the scalability of our technique:
(a) a parallel out- of-core algorithm that can process volumes much larger than an in-core algorithm, and
(b) a clip-based process- ing algorithm that divides the video into overlapping clips in time, and segments them successively while enforcing consistency.
We demonstrate hierarchical segmentations on video shots as long as 40 seconds, and even support a streaming mode for arbitrarily long videos, albeit without the ability to process them hierarchically.
Paper

Download PDF
Slides

Download slides (keynote, ~100 MB)
Note: This file is password protected (under OSX use unzip command to extract).
Please request password by via e-mail.
Web-Service

You can try out our video segmentation here.
Just upload a video and obtain the segmentation results (videos and the actual segmentation).

Video
Citation 
@article{GrundmannKwatra2010,
   author = {Matthias Grundmann and Vivek Kwatra and Mei Han and Irfan Essa},
   title = {Efficient Hierarchical Graph Based Video Segmentation},
   journal = {IEEE CVPR},
   year = {2010},
 }
Dataset
You can download the original videos used in our video and in paper.
video_segmentation.zip (194 MB)
As most example videos are used under the fair-use clause for academic purposes, you need to aquire the password for the zip file by sending an e-mail.
Funding
This research is supported by:
  • NSF Grant
  • Google Grant
Copyright

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without explicit permission of the copyright holder.