Levinkov, EvgenyTompkin, JamesBonneel, NicolasKirchhoff, SteffenAndres, BjoernPfister, HanspeterEitan Grinspun and Bernd Bickel and Yoshinori Dobashi2016-10-112016-10-112016978-3-03868-024-6-https://doi.org/10.2312/pg.20161332https://diglib.eg.org:443/handle/10.2312/pg20161332Video segmentation requires separating foreground from background, but the general problem extends to more complicated scene segmentations of different objects and their multiple parts. We develop a new approach to interactive multi-label video segmentation where many objects are segmented simultaneously with consistent spatio-temporal boundaries, based on intuitive multi-colored brush scribbles. From these scribbles, we derive constraints to define a combinatorial problem known as the multicut-a problem notoriously difficult and slow to solve. We describe a solution using efficient heuristics to make multi-label video segmentation interactive. As our solution generalizes typical binary segmentation tasks, while also improving efficiency in multi-label tasks, our work shows the promise of multicuts for interactive video segmentation.I.4.6 [Computer Graphics]Image Processing and Computer VisionSegmentationRelaxation G.2.2 [Computer Graphics]Discrete MathematicsGraph TheoryGraph labeling10.2312/pg.2016133233-38