Convex relaxations for binary image partitioning and perceptual grouping

We consider approaches to computer vision problems which require the minimization of a global energy functional over binary variables and take into account both local similarity and spatial context. The combinatorial nature of such problems has lead to the design of various approximation algorithms in the past which often involve tuning parameters and tend to get trapped in local minima. In this context, we present a novel approach to the field of computer vision that amounts to solving a convex relaxation of the original problem without introducing any additional parameters. Numerical ground truth experiments reveal a relative error of the convex minimizer with respect to the global optimum of below 2% on the average. We apply our approach by discussing two specific problem instances related to image partitioning and perceptual grouping. Numerical experiments illustrate the quality of the approach which, in the partitioning case, compares favorably with established approaches like the ICM-algorithm.