Efficient convex optimization for minimal partition problems with volume constraints

Minimal partition problems describe the task of partitioning a domain into a set of meaningful regions. Two important examples are image segmentation and 3D reconstruction. They can both be formulated as energy minimization problems requiring minimum boundary length or surface area of the regions. This common prior often leads to the removal of thin or elongated structures. Volume constraints impose an additional prior which can help preserve such structures. There exist a multitude of algorithms to minimize such convex functionals under convex constraints. We systematically compare the recent Primal Dual (PD) algorithm [1] to the Alternating Direction Method of Multipliers (ADMM) [2] on volume-constrained minimal partition problems. Our experiments indicate that the ADMM approach provides comparable and often better performance.