problems on graphs. This talk summarizes rigorous probabilistic
formulations of image segmentation (as a multicut problem) and object
tracking (as a selection and assignment problem). It shows
state-of-the-art results obtained from these models by exact
combinatorial optimization. Toward problems where a global optimum is
inaccessible, it presents the most efficient exhaustive search
algorithm. Finally, it portrays the vision of a unified model for
segmentation and tracking that incorporates so far unexploited image
evidence.