We introduce an image segmentation algorithm GC^max_sum, which combines, in a 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 RFC with respect to the seed choice (thus, avoiding ``shrinking problem'' of GC), while keeping GC's bigger control over ``leaking though the weak boundary.'' The theoretical analysis of GC^max_sum is greatly facilitated by our recent theoretical results that RFC belongs to the Generalized GC (GGC) segmentation algorithms framework. In our implementation of GC^max_sum we use, as a subroutine, a version of RFC algorithm (based on Image Foresting 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.

ICIP Conference Proceedings reprint.

Full paper.

Last modified February 26, 2013.