TY - JOUR

T1 - Sequential convex programming for computing information-theoretic minimal partitions

T2 - Nonconvex nonsmooth optimization

AU - Kee, Youngwook

AU - Lee, Yegang

AU - Souiai, Mohamed

AU - Cremers, Daniel

AU - Kim, Junmo

N1 - Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.

PY - 2017

Y1 - 2017

N2 - 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].

AB - 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].

KW - Difference of convex functions

KW - Image partitioning

KW - Information theory

KW - Stochastic optimization

KW - Total variation regularization

UR - http://www.scopus.com/inward/record.url?scp=85039754661&partnerID=8YFLogxK

U2 - 10.1137/16M1078653

DO - 10.1137/16M1078653

M3 - Article

AN - SCOPUS:85039754661

SN - 1936-4954

VL - 10

SP - 1845

EP - 1877

JO - SIAM Journal on Imaging Sciences

JF - SIAM Journal on Imaging Sciences

IS - 4

ER -