  Multicuts enable to conveniently represent discrete graphical models for
unsupervised and supervised image segmentation, in the case of local energy
functions that exhibit symmetries. The basic Potts model and natural extensions
thereof to higher-order models provide a prominent class of such objectives,
that cover a broad range of segmentation problems relevant to image analysis
and computer vision. We exhibit a way to systematically take into account such
higher-order terms for computational inference. Furthermore, we present results
of a comprehensive and competitive numerical evaluation of a variety of
dedicated cutting-plane algorithms. Our approach enables the globally optimal
evaluation of a significant subset of these models, without compromising
runtime. Polynomially solvable relaxations are studied as well, along with
advanced rounding schemes for post-processing.
