Many interactive image segmentation approaches use an
objective function which includes appearance models as an
unknown variable. Since the resulting optimization problem
is NP-hard the segmentation and appearance are typically
optimized separately, in an EM-style fashion. One
contribution of this paper is to express the objective function
purely in terms of the unknown segmentation, using
higher-order cliques. This formulation reveals an interesting
bias of the model towards balanced segmentations.
Furthermore, it enables us to develop a new dual decomposition
optimization procedure, which provides additionally
a lower bound. Hence, we are able to improve on existing
optimizers, and verify that for a considerable number of real
world examples we even achieve global optimality. This is
important since we are able, for the first time, to analyze the
deficiencies of the model. Another contribution is to establish
a property of a particular dual decomposition approach
which involves convex functions depending on foreground
area. As a consequence, we show that the optimal decomposition
for our problem can be computed efficiently via a
parametric maxflow algorithm.