Fast Continuous Max-Flow Approach to Continuous Min-Cut

Post date: Dec 03, 2010 10:1:31 PM

Many problems of image processing and computer vision can be reformulated by graph-cuts, e.g. image segmentation, image denoising, image alignment and stitch, depth stereo etc. Computing the formulated minimum-cut is of utmost importance in many real applications. In the numerical respect, its dual model, i.e. the max-flow formulation, is often applied to build up the efficient algorithm to min-cut. In fact, most fast computation ways of min-cut rely on its max-flow scheme, e.g. push-relabel, pseudoflow-relabel (see wiki for more information).

It was observed by Nikolova, Chan and Esedoglu that the two-phase image segmentation problem in the spatially continuous setting can be solved globally and exactly by convex optimization, where the edge smoothness is encoded by the total-variation function, the so-called continuous min-cut model: 

where d(x) = C_t(x) - C_s(x).

Fast numerical approaches were further developed through alternating optimization by Bresson et al, Bregman-Splitting by Goldstein et al and Primal-Dual method by Pock et al. In this study, we propose the dual formulation of the continuous min-cut problem, so-called the continuous max-flow model:

We show its great adavantages in three folds:

• • The continuous max-flow model provides a new variational perspective on the continuous min-cut in terms of the flow maximization over flow capacities and conservation. It gives the most elegant way to study min-cuts and shows the close connections between cuts and flows, which is analogue to the dualities of max-flow and min-cut over graphs.

  • The continuous max-flow model directly results in a very fast max-flow algorithm, which regards the labeling function as the multiplier: for a cut of the 400 x 400 image, the continuous max-flow method converges within 10 iterations (about 100 miliseconds), error below 10^-4.

  • Comparing to graph-based methods, the continuous max-flow and min-cut properly avoids metric effects or grid bias. In addition, as its mathematical theories, it often gives a series of global and exact optimums, not just one.