We introduce an image segmentation algorithm, called GCmaxsum, 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 GCmaxsum 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 GCmaxsum 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 GCmaxsum 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 GCmaxsum running in a time close to linear. Experimental comparison of GCmaxsum 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 GCmaxsum over these other methods, resulting in a rank ordering of sum GCmaxsum > PW ~ IRFC > GC.
Full text on line in pdf format.
ICIP Conference Proc. version.
Last modified July 20, 2013.