Fuzzy Connectedness image segmentation in Graph Cut formulation: A linear-time algorithm and a comparative analysis


Krzysztof Chris Ciesielski, J.K. Udupa, A.X. Falcao, and P.A.V. Miranda

Journal of Mathematical Imaging and Vision 44(3) (2012), 375-398.

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, GCmax. The output of GCmax coincides with a version of a segmentation algorithm known as Iterative Relative Fuzzy Connectedness, IRFC. However, GCmax is considerably faster than the classic IRFC algorithm, which we prove theoretically and show experimentally.

From the theoretical point of view, we show that GCmax output constitutes a solution of a graph cut energy minimization problem, in which the energy is defined as the \ell\infty norm ||FP||\infty of the map FP 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 ||FP||q for q in [1,\infty]. Of these, the best known minimization problem is for the energy ||FP||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 ||FP||q, q in [1,\infty], is identical to that for ||FP||1, when the original weight function w is replaced by wq. Thus, any algorithm GCsum solving the ||FP||1 minimization problem, solves also one for ||FP||q with q in [1,\infty), so just two algorithms, GCsum and GCmax, are enough to solve all ||FP||q-minimization problems. We also show that, for any fixed weight assignment, the solutions of the ||FP||q-minimization problems converge to a solution of the ||FP||\infty-minimization problem.

An experimental comparison of the performance of GCmax and GCsum 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.