  We address the challenging task of foreground object discovery and
segmentation in video. We introduce an efficient solution, suitable for both
unsupervised and supervised scenarios, based on a spacetime graph
representation of the video sequence. We ensure a fine grained representation
with one-to-one correspondences between graph nodes and video pixels. We
formulate the task as a spectral clustering problem by exploiting the
spatio-temporal consistency between the scene elements in terms of motion and
appearance. Graph nodes that belong to the main object of interest should form
a strong cluster, as they are linked through long range optical flow chains and
have similar motion and appearance features along those chains. On one hand,
the optimization problem aims to maximize the segmentation clustering score
based on the motion structure through space and time. On the other hand, the
segmentation should be consistent with respect to node features. Our approach
leads to a graph formulation in which the segmentation solution becomes the
principal eigenvector of a novel Feature-Motion matrix. While the actual matrix
is not computed explicitly, the proposed algorithm efficiently computes, in a
few iteration steps, the principal eigenvector that captures the segmentation
of the main object in the video. The proposed algorithm, GO-VOS, produces a
global optimum solution and, consequently, it does not depend on
initialization. In practice, GO-VOS achieves state of the art results on three
challenging datasets used in current literature: DAVIS, SegTrack and
YouTube-Objects.
