We introduce an image segmentation algorithm, called GC^max_sum, which combines, in novel manner, the strengths of two popular algorithms: Relative Fuzzy Connectedness (RFC) and (standard) Graph Cut (GC). We show, both theoretically and experimentally, that GC^max_sum preserves robustness of sum RFC with respect to the seed choice (thus, avoiding "shrinking problem" of GC), while keeping GC's stronger control over the problem of "leaking though poorly defined boundary segments." The analysis of GC^max_sum is greatly facilitated by our recent theoretical results that RFC can be described within the framework of Generalized GC (GGC) segmentation algorithms. In our implementation of GC^max_sum we use, as a subroutine, a version of RFC algorithm (based on Image Forest Transform) that runs (provably) in linear time with respect to the image size. This results in GC^max_sum running in a time close to linear. Experimental comparison of GC^max_sum to GC, an iterative version of RFC (IRFC), and power watershed (PW), based on a variety medical and non-medical images has revealed a consistently superior accuracy performance of GC^max_sum over these other methods, resulting in a rank ordering of sum GC^max_sum > PW ~ IRFC > GC.

Full text on line in pdf format.

ICIP Conference Proc. version.

Last modified July 20, 2013.