Unsupervised image partitioning with semidefinite programming

We apply a novel optimization technique, semidefinite programming, to the unsupervised partitioning of images. Representing images by graphs which encode pairwise (dis)similarities of local image features, a partition of the image into coherent groups is computed by determining optimal balanced graph cuts. Unlike recent work in the literature, we do not make any assumption concerning the objective criterion like metric pairwise interactions, for example. Moreover, no tuning parameter is necessary to compute the solution. We prove that, from the optimization point of view, our approach cannot perform worse than spectral relaxation approaches which, conversely, may completely fail for the unsupervised choice of the eigenvector threshold.