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\), 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).

1. A simpler FC segmentation method, called absolute fuzzy connectedness (AFC) segmentation, predates (I)RFC and MOFS segmentation. In AFC segmentations each object consists of those points that are connected to the object’s seed set by a path whose strength is no less than a user-specified threshold. An important motivation for the development of (I)RFC and MOFS segmentation was to eliminate the need for users to specify such thresholds.

2. IRFC segmentation is closely related to one version of the watershed transform. Specifically, in the case where each seed set \(S_{i}\) consists of just one seed point, Audigier and Lotufo observed in [2] that the objects of an IRFC segmentation are the catchment basins of the tie-zone IFT watershed transform generated by the same seeds and a path cost function that is a strictly decreasing function of the path’s strength (with respect to the affinity used to create the segmentation). The set of points that do not lie in any of the IRFC objects is the tie-zone of the same watershed transform. Tie-zone IFT watershed transforms are discussed in [1–4], though the path cost function used in [1] and [4] is not directly relevant to IRFC segmentation.

3. This can be done by replacing each of our crisp objects \(O_{i}\) with the fuzzy set whose membership value at each point \(v\in O_{i}\) is the strength of the strongest \(O_{i}\)-path from \(O_{i}\)’s seed set \(S_{i}\) to v, and whose membership value at each point \(v\in V{\setminus } O_{i}\) is 0. This definition of the membership value at each point v is quite simple, but other definitions (e.g., definitions which depend directly on the image intensity value at v) may give membership values that are more useful in some applications. One reason to define objects as crisp sets rather than fuzzy sets is that there is no standard way to define the membership value at a point.

4. Affinities whose values need not be numbers (e.g., affinities whose values are n-tuples of real numbers) are considered in [17, 18, 31]. In particular, in [31] affinity values may be elements of any partially ordered set and the strength of connectedness of one point to another is an element of a free distributive lattice over the partially ordered set.

5. The single affinity used for (I)RFC segmentation is often created from M distinct components, each specific to one object.

6. To see the “only if” part, consider the final iteration of Algorithm 3’s main loop in the case \(\psi _{1}=\dots =\psi _{M}=\psi \) and then observe that \(\psi (u,v)=0\) whenever u lies in an MOFS object but v lies in no MOFS object.

7. The condition that \(\psi _{i}(u,v)<1\) (\(1\le i\le M)\) whenever \(u\ne v\) is needed only because we do not want any perturbed affinity value to exceed 1. From a mathematical perspective there is no real loss of generality when we assume this condition. Indeed, if the condition is not satisfied we can define affinities \(\psi _{i}^{*}(u,v)\) such that \(\psi _{i}^{*}(u,v)=\psi _{i}(u,v)/2\) whenever \(u\ne v\), and then use the \(\psi ^{*}\)s in place of the \(\psi \)s: The \(\psi ^{*}\)s evidently satisfy the condition, and it is not hard to see from Algorithm 3 that using the \(\psi ^{*}\)s in place of the \(\psi \)s will not change the segmentations that are produced, because for all V-paths p and q of nonzero length and all \(i,j\in \{1,\dots ,M\}\) we have that \(\psi _{i}^{*}(p)<\psi _{j}^{*}(q)\) if and only if \(\psi _{i}(p)<\psi _{j}(q)\). (See [17, Prop. 1] for more examples of different affinities that are equivalent for FC segmentation purposes.) From a computational perspective, we mention that many MOFS segmentation algorithms, including our Algorithm 5 below, can be easily modified to produce correct segmentations even if some affinity values exceed 1. If we use a modified algorithm of this kind, then the perturbation described here can be applied even if the condition is not satisfied.

8. Indeed, suppose not: Suppose \(v\in O_{i}^{\mathrm {MOFS}}\cap O_{j}^{\mathrm {MOFS}}\) where \(\langle O_{1}^{\mathrm {MOFS}},\dots ,O_{M}^{\mathrm {MOFS}}\rangle \) is the MOFS segmentation derived from \(\psi _{1}',\dots ,\psi _{M}'\) and pairwise disjoint seed sets \(S_{1},\dots ,S_{M}\), and \(i\ne j\). Then we see from the main loop of Algorithm 3 that v must be incorporated into \(T_{i}\) and \(T_{j}\) at the same iteration of that loop. Assuming v is incorporated into \(T_{i}\) and \(T_{j}\) at the nth iteration of the loop, and using the notation of Theorem 2.6, we have that \(v\in T_{i}^{n}{\setminus } T_{i}^{n-1}\) and \(v\in T_{j}^{n}{\setminus } T_{j}^{n-1}\), whence we see from Theorem 2.6 that there is a V-path from \(S_{i}\) to v of \(\psi _{i}'\)-strength \(\alpha _{n}\) and there is also a V-path from \(S_{j}\) to v of \(\psi _{j}'\)-strength \(\alpha _{n}\). But this would imply \(\alpha _{n}\in \{\psi _{i}'(u,v)\mid u,v\in V\,\,\text{ and }\,\, u\ne v\}\cap \{\psi _{j}'(u,v)\mid u,v\in V\,\,\text{ and }\,\, u\ne v\}\), which contradicts (2.1).

9. Note that this cannot be shown by considering affinity perturbations of the kind we have discussed in the above paragraphs, because IRFC segmentation uses just a single affinity.

10. Note that an \(O_{m}^{\Psi ,\mathcal {S}}\)-path to v that is \((\psi _{m}|_{O_{m}^{\Psi ,\mathcal {S}}\times O_{m}^{\Psi ,\mathcal {S}}},S_{m})\)-optimal need not be a V-path to v that is \((\psi _{m},S_{m})\)-optimal: It may have lower \(\psi _{m}\)-strength than a V-path from \(S_{m}\) to v that is not an \(O_{m}^{\Psi ,\mathcal {S}}\)-path.

11. It is enough to verify that \(O_{i}^{\mathrm {IRFC}}\) is the same set as the ith IRFC object according to [20]. To see this, let \(X_{i}=\bigcup _{j\ne i}S_{j}\) (\(1\le i\le M\)) and let \(f:\mathcal {P}(V{\setminus } X_{i})\rightarrow \mathcal {P}(V{\setminus } X_{i})\) be the set function defined by \(f(O)=\{v\in V\mid \psi ^{V{\setminus } O}(X_{i},v)<\psi ^{V}(S_{i},v)\}\) for all \(O\subseteq V{\setminus } X_{i}\). Consider the sequence \(O_{i}^{0},O_{i}^{1},O_{i}^{2},\dots \) where \(O_{i}^{0}=\emptyset \) and \(O_{i}^{k+1}=f(O_{i}^{k})\) for \(0\le k<\infty \). Since f is monotonic (i.e., \(f(O)\subseteq f(O')\) whenever \(O\subseteq O'\)) and \(\emptyset =O_{i}^{0}\subseteq O_{i}^{1}\), we see that \(O_{i}^{k}=f(O_{i}^{k-1})\subseteq f(O_{i}^{k})=O_{i}^{k+1}\) for \(k=1,2,3,\dots \). Writing \(O_{i}^{\infty }\) to denote the union (i.e., the largest set) of the chain \(\emptyset =O_{i}^{0}\subseteq O_{i}^{1}\subseteq O_{i}^{2}\subseteq \dots \) of subsets of the finite set \(V{\setminus } X_{i}\), we have that \(O_{i}^{\infty }=f(O_{i}^{\infty })\). Equivalently, \(O_{i}^{\infty }=\{v\in V\mid \psi ^{V{\setminus } O_{i}^{\infty }}(X_{i},v)<\psi ^{V}(S_{i},v)\}=\{v\in V\mid \max _{j\ne i}\psi ^{V{\setminus } O_{i}^{\infty }}(S_{j},v)<\psi ^{V}(S_{i},v)\}\) and so by statement 3 of Theorem 3.8 we have that \(O_{i}^{\mathrm {IRFC}}=O_{i}^{\infty }\). But since the ascending chain \(\emptyset =O_{i}^{0}\subseteq O_{i}^{1}\subseteq O_{i}^{2}\subseteq \dots \) satisfies \(O_{i}^{k+1}=O_{i}^{k}\cup O_{i}^{k+1}=O_{i}^{k}\cup f(O_{i}^{k})=O_{i}^{k}\cup \{v\in V{\setminus } O_{i}^{k}\mid \psi ^{V{\setminus } O_{i}^{k}}(X_{i},v)<\psi ^{V}(S_{i},v)\}\) for \(0\le k<\infty \), this chain satisfies the inductive definition of the chain \(\emptyset =P_{S_{i},T_{i}}^{0}\subseteq P_{S_{i},T_{i}}^{1}\subseteq P_{S_{i},T_{i}}^{2}\subseteq \dots \) that is given by equation (12) of [20] in the case where the affinity is \(\psi \) and C, m, and \(T_{i}\) are respectively equal to our V, M, and \(X_{i}\). So in this case the set \(P_{S_{i},T_{i}}^{k}\) of [20] is equal to \(O_{i}^{k}\) for \(0\le k<\infty \), whence the set \(\bigcup \nolimits _{k}P_{S_{i},T_{i}}^{k}\), which is the ith IRFC object according to [20, Sect. 4.3], is \(\bigcup \nolimits _{k}O_{i}^{k}=O_{i}^{\infty }=O_{i}^{\mathrm {IRFC}}\).

12. Indeed, let \(\mathrm {OBJ}_{i}\) denote the ith object (in the sense of this paper) of the segmentation produced by the MOFS algorithm of [10] for our affinities \(\psi _{1},\dots ,\psi _{M}\) and seed sets \(S_{1},\dots ,S_{M}\). Then what we want to verify is that \(\mathrm {OBJ}_{i}=O_{i}^{\mathrm {MOFS}}\) for \(1\le i\le M\). In the notation of [10], \(\mathrm {OBJ}_{i}=\{c\in V\mid \sigma _{i}^{c}\ne 0\}\). Theorem 1 of [10] uses the notation \(V_{i}\) to denote the seed set we refer to as \(S_{i}\) and uses \(s_{i}^{c}\) to denote the value \(\psi _{i}^{\mathrm {OBJ}_{i}}(S_{i},c)\). For \(1\le i\le M\) and all \(c\in V\), statement (i) of that theorem implies that \(\sigma _{i}^{c}\ne 0\) just if \(\max _{j\ne i}s_{j}^{c}\le s_{i}^{c}\ne 0\). Equivalently, for \(1\le i\le M\) we have that \(c\in \mathrm {OBJ}_{i}\) just if \(\max _{j\ne i}\psi _{j}^{\mathrm {OBJ}_{j}}(S_{j},c)\le \psi _{i}^{\mathrm {OBJ}_{i}}(S_{i},c)\ne 0\), whence we see from statement 3 of Theorem 3.10 that \(\mathrm {OBJ}_{i}=O_{i}^{\mathrm {MOFS}}\), as required.

13. This follows from observations (iv), (vi), and (vii) in Sect. 6.8, statement 2 of Proposition 6.12, and Theorem 3.10.

14. Given an affinity on V and pairwise disjoint nonempty seed sets \(S_{1},\,\dots ,\, S_{M}\subset V\), we can compute the IRFC object \(O_{i}^{\mathrm {IRFC}}\) associated with the seed set \(S_{i}\) by executing the \(\mathrm {GC}_{\max }\) algorithm of [20, p. 386] with \(W=\bigcup _{j}S_{j}\) and a priority map \(\lambda \) such that \(\lambda (c)=0\) if \(c\in S_{i}\) and \(\lambda (c)=1\) if \(c\in \bigcup _{j\ne i}S_{j}\). This will compute a forest in which the nodes of the trees rooted at points in \(S_{i}\) are exactly the points of \(O_{i}^{\mathrm {IRFC}}\). To compute the entire IRFC segmentation \(\langle O_{1}^{\mathrm {IRFC}},\,\dots ,\, O_{M}^{\mathrm {IRFC}}\rangle \) we do this M times, with \(i=1,\dots ,M\). A modified version of \(\mathrm {GC}_{\max }\), which uses a priority map \(\lambda \) that satisfies \(\lambda (c)=j-1\) for all \(c\in S_{j}\) (\(1\le j\le M\)), will compute a forest such that, for \(1\le j\le M\), the nodes of the trees rooted at points in \(S_{j}\) include all points of \(O_{j}^{\mathrm {IRFC}}\) but possibly also some points of the tie-zone if \(j\ne 1\). When the tie-zone is very small, a good approximation to the entire IRFC segmentation \(\langle O_{1}^{\mathrm {IRFC}},\,\dots ,\, O_{M}^{\mathrm {IRFC}}\rangle \) can be obtained by executing such a modified version of \(\mathrm {GC}_{\max }\) just once.

15. We are grateful to a referee for bringing this method to our attention. We think the method is sound and quite clever, but it seems to us that the corresponding pseudocode [2, Pseudocode 1] does not anticipate every situation that might arise in an image and may in certain cases fail to identify some tie-zone points, though we think it would not be difficult to modify the pseudocode to correctly handle such cases.

16. Indeed, suppose \(M=1,\) \(\psi _{1}=\psi \), and \(S_{1}=S\) in Algorithm 5. As \(M=1\), the effect of line 16 of Algorithm 5 is undone by line 17, so we can omit line 16. Also, each \(\mathsf {i}\) on lines 13–19 can be replaced by 1. Moreover, for each point \(v\in V\) the value of \(\sigma [v]\) can become nonzero only if line 6 or line 15 is executed when \(\mathsf {s}\) or \(\mathsf {x}\) is the point v, and when that happens \(\chi ^{1}[v]\) will be set to \(\mathbf {true}\) by line 7 or line 17. So line 12 can be omitted; this allows execution of lines 13 – 20 even if \(\chi ^{1}[\mathsf {w}]=\mathbf {false}\), but in that case execution of those lines would have no significant effect—for if \(\chi ^{1}[\mathsf {w}]=\mathbf {false}\) we see from the previous sentence that \(\sigma [\mathsf {w}]\) is zero, so execution of line 13 would set \(\sigma '\) to zero and then the conditions on lines 14 and 18 would not be satisfied. In fact the condition on line 18 is never satisfied since \(\chi ^{1}[\mathsf {x}]=\mathbf {true}\) if \(\sigma [\mathsf {x}]\) is nonzero, and so lines 18 – 20 can be omitted too. After these simplifications there are no statements whose execution is conditional on the contents of the array \(\chi ^{1}[\,]\), and if we ignore the lines that only involve \(\chi ^{1}[\,]\) then the algorithm is equivalent to Algorithm 4.

Authors and Affiliations

1. Department of Mathematics, West Virginia University, Morgantown, WV, 26506, USA

   Krzysztof Chris Ciesielski

2. Computer Science PhD Program, Graduate Center, City University of New York, New York, NY, 10016, USA

   Gabor T. Herman

3. Department of Computer Science, Queens College, City University of New York, Flushing, NY, 11367, USA

   T. Yung Kong

4. Department of Radiology, MIPG, University of Pennsylvania, Philadelphia, PA, 19104-6021, USA

   Krzysztof Chris Ciesielski

Corresponding author

Correspondence to Krzysztof Chris Ciesielski.

Conflict of Interest

The authors declare that they have no conflict of interest.

Research involving Human Participants and/or Animals

The authors declare that research leading to this paper involved neither human nor animal participation.

Reprints and permissions