Image segmentation by combining the strengths of Relative Fuzzy Connectedness and Graph Cut

We introduce an image segmentation algorithm GC_sum^max, 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_sum^max 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_sum^max is greatly facilitated by our recent theoretical results that RFC belongs to the Generalized GC (GGC) segmentation algorithms framework. In our implementation of GC_sum^max 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_sum^max running in a time close to linear.