Learning Must-Link Constraints for Video Segmentation

Anna Khoreva, Fabio Galasso,

Matthias Hein and Bernt Schiele


In recent years it has been shown that clustering and segmentation methods can greatly benefit from the integration of prior information in terms of must-link constraints. Very recently the use of such constraints has been integrated in a rigorous manner also in graph-based methods such as normalized cut. On the other hand spectral clustering as relaxation of the normalized cut has been shown to be among the best methods for video segmentation. We merge these two developments and propose to learn must-link constraints for video segmentation with spectral clustering. We show that the integration of learned must-link constraints not only improves the segmentation result but also significantly reduces the required runtime, making the use of costly spectral methods possible for today's high quality video.

Supplementary video

A visual excerpt of the work including video results can be downloaded from this link.

Other materials


BMDS - extra annotated frames

Evaluation files


[Khoreva et al., 2014] , A. Khoreva, F. Galasso, M. Hein and B. Schiele, Learning Must-Link Constraints for Video Segmentation based on Spectral Clustering, German Conference on Pattern Recognition (GCPR), September, (2014)


title={Learning Must-Link Constraints for Video Segmentation based on Spectral Clustering},
author={A. Khoreva and F. Galasso and M. Hein and B. Schiele},
booktitle={German Conference on Pattern Recognition (GCPR)},