A deep theoretical analysis of the graph cut image segmentation framework is presented in this paper which simultaneously translates into important contributions in several directions.

The most important practical contribution of this work is a full theoretical description, and implementation, of a novel powerful linear time segmentation algorithm, GC_max. The output of GC_max coincides with a version of a segmentation algorithm known as Iterative Relative Fuzzy Connectedness, IRFC. However, GC_max is considerably faster than the classic IRFC algorithm, which we prove theoretically and show experimentally.

From the theoretical point of view, we show that GC_max output constitutes a solution of a graph cut energy minimization problem, in which the energy is defined as the \ell_\infty norm ||F_P||_\infty of the map F_P that associates, with every element e from the boundary of an object P, its weight w(e). This formulation brings IRFC algorithms to the realm of the graph cut energy minimizers, with energy functions ||F_P||_q for q in [1,\infty]. Of these, the best known minimization problem is for the energy ||F_P||₁, which is solved by the classic min-cut/max-flow algorithm, referred to often as the Graph Cut algorithm.

We notice that a minimization problem for ||F_P||_q, q in [1,\infty], is identical to that for ||F_P||₁, when the original weight function w is replaced by w^q. Thus, any algorithm GC_sum solving the ||F_P||₁ minimization problem, solves also one for ||F_P||_q with q in [1,\infty), so just two algorithms, GC_sum and GC_max, are enough to solve all ||F_P||_q-minimization problems. We also show that, for any fixed weight assignment, the solutions of the ||F_P||_q-minimization problems converge to a solution of the ||F_P||_\infty-minimization problem.

An experimental comparison of the performance of GC_max and GC_sum algorithms is included. This concentrates on comparing the actual (as opposed to provable worst scenario) algorithms' running time, as well as the influence of the choice of the seeds on the output.

Full text on line in pdf format.

SPIE Conference Proc. version.

SPIE Conference Proc. version, second part.

Last modified August 23, 2012.