Grundmann et al. extend the graph-based image segmentation algorithm proposed by Felzenswalb and Huttenlocher  to video and also provide an efficient implementation able to process arbitrarily long videos on GitHub. They also provide some video sequences without ground truth for qualitative evaluation, see here. The algorithm can also be used for annotation online at videosegmentation.com - the project is currently maintained by Daniel Castro.
Figure 1 shows a segmentation example on the Sintel dataset  generated using a custom implementation inspired by the original implementation by Felzenswalb and Huttenlocher .
The implementation is available on GitHub.
alley_1sequence of the Sintel dataset . Top: original sequence; middle: oversegmentation; bottom: hierarchical segmentation.
Another implementation is also available as part of the libsvx library .