Joint graph cut and relative fuzzy connectedness image segmentation algorithm.

We introduce an image segmentation algorithm, called GC(sum)(max), 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(sum)(max) preserves robustness of 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(sum)(max) 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(sum)(max) 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(sum)(max) running in a time close to linear. Experimental comparison of GC(sum)(max) to GC, an iterative version of RFC (IRFC), and power watershed (PW), based on a variety medical and non-medical images, indicates superior accuracy performance of GC(sum)(max) over these other methods, resulting in a rank ordering of GC(sum)(max)>PW∼IRFC>GC.

A framework for comparing different image segmentation methods and its use in studying equivalences between level set and fuzzy connectedness frameworks.

In the current vast image segmentation literature, there seems to be considerable redundancy among algorithms, while there is a serious lack of methods that would allow their theoretical comparison to establish their similarity, equivalence, or distinctness. In this paper, we make an attempt to fill this gap. To accomplish this goal, we argue that: (1) every digital segmentation algorithm [Formula: see text] should have a well defined continuous counterpart [Formula: see text], referred to as its model, which constitutes an asymptotic of [Formula: see text] when image resolution goes to infinity; (2) the equality of two such models [Formula: see text] and [Formula: see text] establishes a theoretical (asymptotic) equivalence of their digital counterparts [Formula: see text] and [Formula: see text]. Such a comparison is of full theoretical value only when, for each involved algorithm [Formula: see text], its model [Formula: see text] is proved to be an asymptotic of [Formula: see text]. So far, such proofs do not appear anywhere in the literature, even in the case of algorithms introduced as digitizations of continuous models, like level set segmentation algorithms.The main goal of this article is to explore a line of investigation for formally pairing the digital segmentation algorithms with their asymptotic models, justifying such relations with mathematical proofs, and using the results to compare the segmentation algorithms in this general theoretical framework. As a first step towards this general goal, we prove here that the gradient based thresholding model [Formula: see text] is the asymptotic for the fuzzy connectedness Udupa and Samarasekera segmentation algorithm used with gradient based affinity [Formula: see text]. We also argue that, in a sense, [Formula: see text] is the asymptotic for the original front propagation level set algorithm of Malladi, Sethian, and Vemuri, thus establishing a theoretical equivalence between these two specific algorithms. Experimental evidence of this last equivalence is also provided.

Iterative Relative Fuzzy Connectedness for Multiple Objects with Multiple Seeds.

In this paper we present a new theory and an algorithm for image segmentation based on a strength of connectedness between every pair of image elements. The object definition used in the segmentation algorithm utilizes the notion of iterative relative fuzzy connectedness, IRFC. In previously published research, the IRFC theory was developed only for the case when the segmentation was involved with just two segments, an object and a background, and each of the segments was indicated by a single seed. (See Udupa, Saha, Lotufo [15] and Saha, Udupa [14].) Our theory, which solves a problem of Udupa and Saha from [13], allows simultaneous segmentation involving an arbitrary number of objects. Moreover, each segment can be indicated by more than one seed, which is often more natural and easier than a single seed object identification.The first iteration step of the IRFC algorithm gives a segmentation known as relative fuzzy connectedness, RFC, segmentation. Thus, the IRFC technique is an extension of the RFC method. Although the RFC theory, due to Saha and Udupa [19], is developed in the multi object/multi seed framework, the theoretical results presented here are considerably more delicate in nature and do not use the results from [19]. On the other hand, the theoretical results from [19] are immediate consequences of the results presented here. Moreover, the new framework not only subsumes previous fuzzy connectedness descriptions but also sheds new light on them. Thus, there are fundamental theoretical advances made in this paper.We present examples of segmentations obtained via our IRFC based algorithm in the multi object/multi seed environment, and compare it with the results obtained with the RFC based algorithm. Our results indicate that, in many situations, IRFC outperforms RFC, but there also exist instances where the gain in performance is negligible.