Fast Continuous Max-Flow Approach to Minimum Image Partition

Post date: Dec 12, 2010 5:48:2 AM

Minimum image partition, i.e. the Potts model, proposes to segment a image with the minimal total perimeter, which gives the most natural model of image segmentation of multiple regions in mathematics. In the recent years, it was realized that the minimum image partition problem can be formulated and approximated by the convex relaxation model, so-called the convex Potts model, with the total-variation function as the perimeter evaluation (see Chambolle et al). It boils down to a convex constrained nonsmooth optimization formulation, which proposes a challenging problem in computation. Some algorithms were investigated and proposed, e.g. Lellmann et al and Egil et al. 

In this project, we propose and study the equivalent dual model of the considered convex Potts model, which is called the continuous max-flow model. It provides a completely new perspective of the investigated convex Potts model. The close connections between flows and cuts are described in an elegant variational manner. Moreover, it also leads to a fast algorithm in the style of maximization of flows. The new algorithmic scheme can be easily parallelized and implemented in the advanced platform, e.g. GPU. Experiments show its great out-performance over the state of art approaches in terms of convergence rate.

Related works: