General Theory of Fuzzy Connectedness Segmentations

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 tie-zone (i.e., the set of points that do not lie in just one object) is 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 generalize the concepts of RFC and IRFC segmentation to the case where the affinity is not necessarily symmetric, explain just how the three different segmentation methods relate to each other, and give very concise mathematical (i.e., nonalgorithmic) 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. The fast MOFS algorithm in this paper (our Algorithm 5), which is reminiscent of Dijkstra's shortest path algorithm for weighted digraphs, is one of the most computationally efficient segmentation algorithms. It can be used to efficiently compute IRFC segmentations as well as MOFS segmentations: This is because it emerges quickly from our work that if a single affinity is used then IRFC objects are just MOFS objects from which all tie-zone points have been removed. When $$M > 2$$M>2, this fast MOFS algorithm is likely to compute an M-object IRFC segmentation more quickly than commonly used IRFC segmentation algorithms that compute IRFC objects one at a time (except possibly when the tie-zone of the segmentation is very large, in which case we show that the IRFC segmentation must be unstable).