Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Image segmentation is a fundamental task in computer vision that, despite substantial progress over the years, is still far from solved. Typically, it is cast as a combinatorial optimization problem for which graph cuts have been popular tools. However, it is becoming increasingly evident that graph cuts and their associated random field models are limited and fail in commonly encountered challenging settings. We introduce a new high-order segmentation model that is based on graphs but is not restricted by any of the previously used computationally nice but limiting properties such as locality or regularity. Instead, we use "cooperative graph cuts" that allow the cut cost to be not merely a sum of edge weights but a submodular function of graph edges. The resulting coupling of edges captures global characteristics of the cut, and thereby significantly improves results for difficult segmentations. MAP inference in this model means finding a Minimum Cooperative Cut, a very hard problem in general. As empirical results stand in contrast to this general hardness, we demonstrate how lower bounds for cooperative cuts and recently studied related problems depend on properties of the cost function. Moreover, some models admit exact inference in practice. This is joint work with Jeff Bilmes, Rishabh Iyer, Pushmeet Kohli and Anton Osokin