  Segmenting an image into multiple components is a central task in computer
vision. In many practical scenarios, prior knowledge about plausible components
is available. Incorporating such prior knowledge into models and algorithms for
image segmentation is highly desirable, yet can be non-trivial. In this work,
we introduce a new approach that allows, for the first time, to constrain some
or all components of a segmentation to have convex shapes. Specifically, we
extend the Minimum Cost Multicut Problem by a class of constraints that enforce
convexity. To solve instances of this APX-hard integer linear program to
optimality, we separate the proposed constraints in the branch-and-cut loop of
a state-of-the-art ILP solver. Results on natural and biological images
demonstrate the effectiveness of the approach as well as its advantage over the
state-of-the-art heuristic.
