Sequential convex programming for computing information-theoretic minimal partitions: Nonconvex nonsmooth optimization

We consider an unsupervised image segmentation problem—from figure-ground separation to multiregion partitioning—that consists of maximal distribution separation (in terms of mutual information) with spatial regularity (total variation regularization), which is what we call information- theoretic minimal partitioning. Adopting the bounded variation framework, we provide an in-depth analysis of the problem which establishes theoretical foundations and investigates the structure of the associated energy from a variational perspective. In doing so, we show that the objective exhibits a form of difference of convex functionals, which leads us to a class of large-scale nonconvex optimization problems where convex optimization techniques can be successfully applied. In this regard, we propose sequential convex programming based on the philosophy of stochastic optimization and the Chambolle–Pock primal-dual algorithm. The key idea behind it is to construct a stochastic family of convex approximations of the original nonconvex function and sequentially minimize the associated subproblems. Indeed, its stochastic nature makes it possible to often escape from bad local minima toward near-optimal solutions, where such optimality can be justified in terms of the recent findings in statistical physics regarding a striking characteristic of the high-dimensional landscapes. We experimentally demonstrate such a favorable ability of the proposed algorithm as well as show the capacity of our approach in numerous experiments. The preliminary conference paper can be found in [Y. Kee, M. Souiai, D. Cremers, and J. Kim, Proceedings of the IEEE Conference on Computer Vision and Pattern, Recognition, 2014].