Joint Optimization of Segmentation and Appearance Models
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.