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}||_{1}, 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}||_{1}, when the original weight function w is replaced by w^{q}.
Thus, any algorithm GC_{sum} solving the ||F_{P}||_{1} 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.**