For any positive integer M, M-object fuzzy connectedness (FC) segmentation is a methodology for finding M objects in a digital image based on user-specified seed points and user-specified functions, called (fuzzy) affinities, which map each pair of image points to a value in the real interval [0,1].

The theory of FC segmentation has proceeded along two tracks. One track, developed by researchers including the first author, has used two kinds of FC segmentations: RFC segmentation and IRFC segmentation. The other track, developed by researchers including the second and third authors, has used another kind of FC segmentation called MOFS segmentation. In RFC and IRFC segmentation the M delineated objects are pairwise disjoint. In contrast, the M objects delineated by MOFS segmentation may overlap (though, in many practical applications, the overlap areas are extremely small). Another difference between (I)RFC and MOFS segmentation is that the former types of segmentation are defined in terms of just one affinity (regardless of the value of M), whereas MOFS segmentation is defined in terms of M different affinities with each of the M objects having its own affinity. Moreover, the affinity used in (I)RFC segmentation has almost always been assumed in the (I)RFC-track literature to be a symmetric function, but the affinities used in MOFS segmentation need not be symmetric.

This paper presents the first unified mathematical study of FC segmentation that encompasses both (I)RFC and MOFS segmentation. We explain just how the different segmentation methods relate to each other, and give very concise mathematical (i.e., non-algorithmic) path-based characterizations of the objects delineated by (I)RFC and MOFS segmentation. Our primary path-based characterization of MOFS objects depends on the concept of a recursively optimal path, which we introduce in this paper. Using another new concept---the core of an MOFS object---we prove results which show that MOFS segmentation is robust with respect to seed choice even when different affinities are used for different objects and the affinities are not necessarily symmetric. Two of these results substantially generalize known (I)RFC-track robustness results that previously had no MOFS-track counterpart.

MOFS segmentation may be preferable to (I)RFC segmentation in certain contexts where it is natural to use different affinities for different objects (e.g., by utilizing so-called object-based affinities). However, there is an entirely different reason why MOFS segmentation algorithms may be useful: It will be seen that they can also be used to compute IRFC segmentations. Indeed, for segmentation into more than two objects a fast MOFS segmentation algorithm (such as Algorithm 5 in this paper) can compute IRFC segmentations more quickly than commonly-used IRFC segmentation algorithms.

Full text on line in pdf format.

IWCIA Conference Proc. version.

Last modified April 25, 2016.