Date Added: Jul 2009
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 one to develop a new dual decomposition optimization procedure, which provides additionally a lower bound. Hence, one is able to improve on existing optimizers, and verify that for a considerable number of real world examples one even achieves global optimality.