We introduce an image segmentation algorithm GCmaxsum, 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 GCmaxsum 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 GCmaxsum is greatly facilitated by our recent theoretical results that RFC belongs to the Generalized GC (GGC) segmentation algorithms framework. In our implementation of GCmaxsum 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 GCmaxsum running in a time close to linear.
ICIP Conference Proceedings reprint. Full paper.
Last modified February 26, 2013.