Solving graph-cut based optimization problems by a smoothing technique with applications in multi-phase segmentation

    Multi-labeling problems, such as multi-phase segmentation on images, can be proposed as a graph-cut based optimization problem through modification of Pott’s model. Solving the original Pott’s model is known as a combinatorial optimization, which poses difficulty in reducing computational complexity.  The continuous max-flow approach proposed by Yuan, Tai, et al has been demonstrated to be efficient in semi-supervised multi-phase segmentation. It is formulated as a convex, yet non-smooth optimization problem. Several algorithms have been proposed, such as solving the dual problem by proximal gradient, primal-dual hybrid gradient, augmented Lagrangian method, and more recent Bregman-proximal augmented Lagrangian method. In this talk, we are going to review these algorithms and propose a new one, based on a smoothing technique for the dual problem, which has several advantages such as theoretical guarantee of convergence with proved speed and error estimate for early termination. Some numerical examples in multi-phase segmentation are shown to demonstrate its effectiveness.