Keywords

1 Introduction

Image segmentation is an important and challenging task for which a multitude of different techniques have been developed; see, e.g., Sect. 1.6 of [19] and the survey articles in Part IV of that book. Our paper deals with the segmentation methodology known as fuzzy connectedness (or FC) segmentation, which has been used with considerable success—see, e.g., Fig. 1—on biomedical and many other kinds of images [1–11, 13–18, 21–23, 25–33]. One typical example is [1], in which FC segmentation is used to delineate nodules in computerized tomography (CT) images of the lungs of patients. In medical imaging, FC segmentation was first developed by Udupa and Samarasekera [32]. Earlier uses of FC segmentation in an entirely different context (geophysical data processing) are reported in [8–11].

Much of the theory of FC segmentation has developed along two different tracks. In one of the tracks [1, 2, 13–18, 21, 27, 28, 31, 33] two kinds of segmentation are used: relative fuzzy connectedness (RFC) segmentation and iterative relative fuzzy connectedness (IRFC) segmentation. The other track [3–7, 22, 25] uses a third kind of segmentation that is called multi object fuzzy segmentation (MOFS). In [12] we present a general theory of FC segmentation that encompasses both tracks and unifies them.

2 Basic Definitions

Let V be the set of all points of a digital image (so that V is finite and nonempty), let M be a positive integer, and let \(S_{1},\,\dots ,S_{M}\) be pairwise disjoint nonempty subsets of V. Then FC (short for fuzzy connectedness) segmentation can be understood as one method of identifying M subsets \(O_{1},\,\dots ,O_{M}\) of V such that \(S_{i}\subseteq O_{i}\subseteq S_{i}\cup (V\setminus \bigcup _{j}S_{j})\) for \(1\le i\le M\). Each of the sets \(O_{1},\,\dots ,O_{M}\) that is identified is called an object, and (for \(1\le i\le M\)) each point in the originally specified set \(S_{i}\) is called a seed point or simply a seed for the ith object \(O_{i}\). In many applications one of the M objects is called the background.

In a practical application, the sets \(S_{1},\,\dots ,S_{M}\) may be specified in any way appropriate for that application. For example, to specify the seed sets that resulted in the 4-object segmentation shown at the bottom of Fig. 1, the creator of that segmentation displayed on the computer screen the image shown at the top of Fig. 1 and, for \(1\le i\le 4\), used mouse clicks to indicate the locations of all the points in \(S_{i}\). But this is not the only way to select seed points; for example, [1] describes procedures for selecting seed points automatically in a manner that is different for the background object and the other objects (that are all nodules in [1]). Automatic seed selection has the potential of reducing the time that the user needs to spend on providing input to the segmentation process.

Fig. 1.
figure 1

Top: A slice of a patient’s head obtained by magnetic resonance imaging (MRI). Bottom: A 4-object MOFS of the same slice. The number 4 reflects the fact that this FC segmentation aims at dividing up the image according to four tissue types (shown in red, green, blue, and yellow. (Reproduced from [6]) (Color figure online)

Full size image

In addition to using the term FC segmentation to refer to the process by which the objects \(O_{1},\,\dots ,\,O_{M}\) are found, we will also call the sequence of objects \(O_{1},\,\dots ,\,O_{M}\) an FC segmentation or an M-object FC segmentation of the set V of image points.

An FC segmentation is not necessarily a segmentation in the most typical sense because it is not necessarily a partition of the set V of image points: It is not required that the \(O_{i}\) be pairwise disjoint nor that their union be the whole of V. However, FC segmentation is the only kind of segmentation we discuss here, and we will often refer to FC segmentations as “segmentations.”

The objects \(O_{i}\) that are found by FC segmentation depend on user-specified mappings called fuzzy affinities or just affinities. An affinity (on V) is a mapping \(\psi :V\times V\rightarrow [0,1]\) such that \(\psi (v,v)=1\) for all \(v\in V\). For all \(u,v\in V\), we call the value \(\psi (u,v)\in [0,1]\) the \(\psi \)-affinity   value of (u, v).

An affinity on V may be regarded as an edge-weight function of the complete digraph (with loops) on V. Affinity values are described in [32] and elsewhere as (user-specified) measures of the “hanging togetherness” of pairs of image points.

One of the ways that RFC segmentation and IRFC segmentation differ from MOFS is that, for any seed sets \(S_{1},\,\dots ,\,S_{M}\), the RFC and IRFC segmentations of V are determined by a single affinity \(\psi :V\times V\rightarrow [0,1]\), whereas the MOFS segmentation of V depends on M affinities \(\psi _{1},\,\dots ,\,\psi _{M}\) (i.e., one affinity for each of the M objects).

FC segmentation is unlikely to identify useful objects unless the affinity or affinities we use are appropriate for our application. The important problem of how to define appropriate affinities is discussed, e.g., in [3, 7, 14, 15, 24, 25]. In MOFS each affinity \(\psi _{i}\) is quite frequently defined based on some statistical analysis of the image values assigned to points in neighborhoods of the seed points in \(S_{i}\); see, for example, [5, 6, 25].

Given an affinity \(\psi :V\times V\rightarrow [0,1]\) on V and \(A,B,W\subseteq V\), a W-path from \(A\) to \(B\) of length l is any sequence \(p=\langle w_{0},\ldots ,w_{l}\rangle \) of points in W such that \(w_{0}\in A\) and \(w_{l}\in B\); the \(\psi \)-strength of \(p=\langle v_{0},\ldots ,v_{l}\rangle \), denoted by \(\psi (p)\), is defined by \(\psi (p)=\min _{1\le k\le l}\psi (v_{k-1},v_{k})\) if \(l>0\) and \(\psi (p)=1\) if \(l=0\); the \(\psi \) -strength of connectedness of \(A\ne \emptyset \) to \(B\ne \emptyset \) via W is defined as

$$\begin{aligned} \psi ^{W}(A,B)=\max \,\{\psi (p) \mid p\,{\,\text {is a}\,\,(W\cup A\cup B)\,\text {-}\, \text {path from} \,\,A\,\ \mathrm{{to}} \,\,B}\}. \end{aligned}$$
(1)

For \(a,b\in V\), a W-path from \(\{a\}\) to \(\{b\}\) will also be called a W-path from a to b. Similarly, we write \(\psi ^{X}(a,B)\), \(\psi ^{X}(A,b)\), and \(\psi ^{X}(a,b)\) for \(\psi ^{X}(\{a\},B)\), \(\psi ^{X}(A,\{b\})\), and \(\psi ^{X}(\{a\},\{b\})\), respectively. Note that \(\psi (a,b)=\psi ^{\emptyset }(a,b)\le \psi ^{X}(a,b)\le \psi ^{V}(a,b)\), that \(\psi ^{X}(A,B)=1\) if \(A\cap B\ne \emptyset \), and that \(\psi ^{\emptyset }(A,B)=\max \limits _{a\in A,b\in B}\psi (a,b)\).

We say that the seed sets \(S_{1},\,\dots ,\,S_{M}\) are consistent with the affinities \(\psi _{1},\,\dots ,\,\psi _{M}\) if \(\psi _{i}^{V}(S_{i},S_{j})<1\), for all distinct i and j in \(\{1,\,\dots ,\,M\}\). In other words, \(S_{1},\,\dots ,\,S_{M}\) are consistent with the affinities \(\psi _{1},\,\dots ,\,\psi _{M}\) if, and only if, for all distinct i and j in \(\{1,\,\dots ,\,M\}\) and for every V-path \(\langle v_{0},\ldots ,v_{l}\rangle \) from \(S_{i}\) to \(S_{j}\), there exists a k, \(1\le k\le l\), such that \(\psi _{i}(v_{k-1},v_{k})<1\).

3 A Simple Multi Object Fuzzy Segmentation (MOFS) Algorithm

The following algorithm for computing the M-object MOFS of the set V for pairwise disjoint nonempty seed sets \(S_{1},\,\ldots ,\,S_{M}\subset V\) and affinities \(\psi _{1},\,\ldots ,\,\psi _{M}\) on V is not intended to be efficient. Rather, it is intended to be simple and concise, so as to give readers who are new to the subject a quick (yet completely accurate) understanding of the nature of the objects that are found by MOFS. A much more efficient (but less easily understood) method for computing MOFS is Algorithm 5 of [12], which is akin to Dijkstra’s shortest-path algorithm [20], computes all of the objects simultaneously, and may be regarded as a simplified version of the MOFS algorithm of [6, Sect. 3].

figure a

Let \(\varPsi =\langle \psi _{1},\dots ,\psi _{M}\rangle \) be any sequence of affinities on V and let \(\mathcal {S}=\langle S_{1},\dots ,S_{M}\rangle \) be any sequence of M pairwise disjoint nonempty subsets of V. Then we denote the MOFS segmentation \(\langle O_{1}^{\mathrm {MOFS}},\,\dots ,\,O_{M}^{\mathrm {MOFS}}\rangle \) that is produced by Algorithm 1 for affinities \(\psi _{1},\dots ,\psi _{M}\) and seed sets \(S_{1},\dots ,S_{M}\) by \(\langle O_{1}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S}),\dots ,O_{M}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\rangle \). We now proceed to give an alternative, non-algorithmic, characterization of this segmentation (in statements 1(a) and 1(b) below) and to state some related facts about the segmentation and Algorithm 1.

Let \(A=\bigcup _{j}\psi _{j}[V\times V]\setminus \{0\}\) and let \(1=\alpha _{1}>\ \dots \ >\alpha _{|A|}\) be the sequence obtained by sorting A into decreasing order. For \(1\le i\le M\) and \(0\le n<|A|\), let \(T_{i}^{n}\) be the value of the variable \(T_{i}\) at the beginning of the \(n+1\)st iteration of the main loop when Algorithm 1 is executed, and let \(T_{i}^{|A|}\) be the value of \(T_{i}\) at the end of the |A|th iteration of the main loop (which is the value of \(T_{i}\) when Algorithm 1 terminates). Then

$$ S_{i}\subseteq O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\subseteq S_{i}\cup (V\setminus {\bigcup \nolimits _{j}}S_{j}) $$

for \(1\le i\le M\). Moreover:

  1. 1.

    For \(1\le i\le M\) we have that:

    1. (a)

      \(T_{i}^{0}=S_{i}\), and \(T_{i}^{n}=T_{i}^{n-1}\cup \{v\in V\setminus {\bigcup \nolimits _{j}}T_{j}^{n-1}\mid \psi _{i}^{T_{i}^{n-1}\cup (V\setminus \bigcup _{j}T_{j}^{n-1})}(S_{i},v)=\alpha _{n}\}\) for \(1\le n\le |A|\).

    2. (b)

      \(O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})=T_{i}^{|A|}\).

  2. 2.

    \(\{v\in V\setminus {\bigcup \nolimits _{j}}T_{j}^{n-1}\mid \psi _{i}^{T_{i}^{n-1}\cup (V\setminus \bigcup _{j}T_{j}^{n-1})}(S_{i},v)>\alpha _{n}\}=\emptyset \) for \(1\le i\le M\) and \(1\le n\le |A|\).

  3. 3.

    \(T_{i}^{n}=T_{i}^{n-1}\cup \{v\in V\setminus {\bigcup \nolimits _{j}}T_{j}^{n-1}\mid \psi _{i}^{T_{i}^{k}}(S_{i},v)=\alpha _{n}\}\) for \(1\le i\le M\) and \(1\le n\le k\le |A|\).

Now let us assume the seed sets \(\mathcal {S}=\langle S_{1},\dots ,S_{M}\rangle \) are consistent with the affinities \(\varPsi =\langle \psi _{1},\dots ,\psi _{M}\rangle \). Then there is an arguably even more easily comprehended characterization of the MOFS segmentation

$$\begin{aligned} \langle O_{1}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S}),\,\dots ,\,O_{M}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\rangle \end{aligned}$$

than the characterization that is given by statements 1(a) and 1(b) above: The segmentation is the unique sequence of sets \(\langle O_{1},\dots ,O_{M}\rangle \) such that

$$\begin{aligned} O_{i}=\{v\in V\mid \max \nolimits _{j\ne i}\psi _{j}^{O_{j}}(S_{j},v)\le \psi _{i}^{O_{i}}(S_{i},v)\ne 0\}\,\,\,{ \text {for } 1\le i\le M}. \end{aligned}$$
(2)

That this is the case is stated (and proved) as part of Theorem 3.10 in [12]. The proof makes use of the concept (introduced in [12]) of a recursively optimal path.

Let us expand this characterization. Suppose that a sequence of sets

$$\begin{aligned} \langle O_{1},\dots ,O_{M}\rangle \end{aligned}$$

satisfies (2). Then, for \(1\le i\le M\), \(S_{i}\subseteq O_{i}\) and, for any \(v\in V\), \(v\in O_{i}\) if, and only if:

  1. 1.

    There is an \((O_{i}\cup \{v\})\)-path \(\langle v_{0},\ldots ,v_{l}\rangle \) from \(S_{i}\) to v such that \(\psi _{i}(v_{k-1},v_{k})>0\) for \(1\le k\le l\). (This implies that \(\psi _{i}^{O_{i}}(S_{i},v)>0\).)

  2. 2.

    For \(1\le j\le M\), the \(\psi _{j}\)-strength of any \((O_{j}\cup \{v\})\)-path from \(S_{j}\) to v is not greater than \(\psi _{i}^{O_{i}}(S_{i},v)\).

Furthermore, since the characterization uniquely determines the sequence

$$\begin{aligned} \langle O_{1},\dots ,O_{M}\rangle \end{aligned}$$

it follows that the definition

$$\begin{aligned} \sigma (v)=\max _{1\le i\le M}\psi _{i}^{O_{i}}(S_{i},v) \end{aligned}$$
(3)

assigns a value from \(\left[ 0,1\right] \) to every \(v\in V\). If \(\sigma (v)=0\), then \(\psi _{i}^{O_{i}}(S_{i},v)=0\) and \(v\notin O_{i}\) for \(1\le i\le M\). On the other hand, if \(\sigma (v)\ne 0\), then there must be at least one i such that \(\max \nolimits _{j\ne i}\psi _{j}^{O_{j}}(S_{j},v)\le \psi _{i}^{O_{i}}(S_{i},v)=\sigma (v)\), and \(v\in O_{i}\) for all such i. (This is a good place to point out a second difference between MOFS and either RFC segmentation or IRFC segmentation: While in MOFS the \(O_{i}\) may overlap, objects in any RFC or IRFC segmentation are pairwise disjoint.) When representing the outcome of such a segmentation by a color image (as in the bottom image of Fig. 1), we can associate a different pure hue with each of the is (in the case of the bottom image of Fig. 1, there are four pure hues used: red, green, blue, and yellow): If \(v\in O_{i}\), then the hue associated with i is assigned to the pixel v. In the bottom image of Fig. 1, the brightness that is assigned to each \(v\in O_{i}\) is \(\sigma (v)\), which is often regarded (see, for example, [6]) as the grade of membership of v in \(O_{i}\).

4 Robustness of Fuzzy Connectedness Segmentations

In practice the seed points may be selected by the user clicking on images (as was done to produce the 4-object MOFS shown at the bottom of Fig. 1) or in some more automatic manner (as described, for instance, in [1]). In the first case, the choice of the seed points is likely to be different for different users and even for the same user at different times. Even in the second case, we have variability; the noise in the image of an object is not deterministic and an automated process for determining the location of the seeds may depend on the noise in the image (for example, if it involves finding local minima or maxima). It would make the practical usefulness of FC segmentation questionable if the outcome were highly dependent on the exact selections of the seed points. Fortunately, this has not been found to be the case: FC segmentations are generally robust with respect to small changes in seed sets.

When the affinities do not depend on the choice of seeds, we can establish mathematical results that explain this robustness. In the cases of RFC and IRFC segmentation, such results are given in [18, Sect. 2.4]. In this section we state one such result for MOFS, which shows that it is possible to introduce a large number of additional seed points without changing the resulting MOFS.

Let \(\varPsi =\langle \psi _{1},\dots ,\psi _{M}\rangle \) be any sequence of affinities on V and \(\mathcal {S}=\langle S_{1},\dots ,S_{M}\rangle \) any sequence of M pairwise disjoint nonempty subsets of V that are consistent with the affinities. Then, for \(1\le i\le M\), we define \(\mathcal {P}_{i}(\varPsi ,\mathcal {S})\) to be the collection of all subsets P of V that satisfy both of the following conditions:

  1. 1.

    \(P\,\,\subseteq \,\,O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\setminus \bigcup _{j\ne i}O_{j}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S}).\)

  2. 2.

    \(\psi _{i}^{O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})}(S_{i},v)\,\ge \,\psi _{i}^{\emptyset }(v,V\setminus P)\) for every \(v\in P\).

The core of \(O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\), denoted by \(\mathcal {P}i\), is defined as the union of all the sets in \(\mathcal {P}_{i}(\varPsi ,\mathcal {S})\). We observe that \(\mathcal {P}i\subseteq O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\setminus \bigcup _{j\ne i}O_{j}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\) for \(1\le i\le M\). This implies that the cores of distinct MOFS objects are always disjoint: \(\mathcal {P}i\cap \mathcal {P}j=\emptyset \) whenever \(i\ne j\).

Since \(S_{i}\subseteq O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\setminus \bigcup _{j\ne i}O_{j}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\) (which is clear when we recall from the previous section that \(S_{i}\subseteq O_{i}^{\mathrm {MOFS}}\subseteq S_{i}\cup (V\setminus \bigcup _{j}S_{j})\) for \(1\le i\le M\)), we see that \(S_{i}\in \mathcal {P}_{i}(\varPsi ,\mathcal {S})\) and therefore \(S_{i}\subseteq \mathcal {P}i\) for \(1\le i\le M\). A little reflection will show that it is quite possibly the case that \(\mathcal {P}i\) is a much larger set than \(S_{i}\). Nevertheless, as the following theorem states, using the \(\mathcal {P}i\)s instead of the \(S_{i}\)s as the seed sets for the objects does not change the resulting MOFS.

MOFS Robustness Theorem [12]: Let \(\varPsi =\langle \psi _{1},\dots ,\psi _{M}\rangle \) be a sequence of affinities on V and \(\mathcal {S}=\langle S_{1},\dots ,S_{M}\rangle \) a sequence of pairwise disjoint nonempty seed sets consistent with the affinities. Let \(\mathcal {R}=\langle R_{1},\dots ,R_{M}\rangle \) be such that \(S_{i}\subseteq R_{i}\subseteq \mathcal {P}i\) for \(1\le i\le M\). Then \(O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {R})=O_{i}^{\mathrm {MOFS}}(\varPsi ,\mathcal {S})\) for \(1\le i\le M\).

Other results regarding the robustness of MOFS with respect to changes in seed sets (e.g., [12, Corollary 5.6]) can be deduced from this theorem.

All mathematical results the authors are aware of regarding robustness of FC segmentations assume that affinities remain unchanged when seed sets change. For example, there appear to be no results in the literature regarding robustness of FC segmentations when affinities depend on statistical properties of the image values assigned to points in neighborhoods of the seeds.

5 Unified Theory of FC Segmentations

While we have repeatedly mentioned RFC and IRFC segmentations, until now we have discussed details only of MOFS. A unified theory that covers all three types of segmentations is offered in [12]: In that paper it is shown that a generally common mathematical approach is applicable in all three cases. Moreover, the methods and results stated for MOFS above (and some other methods and results for MOFS) have close analogs for RFC and IRFC segmentations.

One significant fact that emerges from the unified theory of [12] is that the IRFC segmentation for an affinity \(\psi \) and seed sets \(S_{1},\dots ,S_{M}\) consistent with \(\psi \) can be found by executing the very efficient Algorithm 5 of [12] for MOFS with \(\psi _{1}=\dots =\psi _{M}=\psi \): Each object \(O_{i}^{\mathrm {IRFC}}\) of the IRFC segmentation consists just of those points in the corresponding MOFS object \(O_{i}^{\mathrm {MOFS}}\) that do not lie in any of the other \(M-1\) MOFS objects:

$$\begin{aligned} O_{i}^{\mathrm {IRFC}}=O_{i}^{\mathrm {MOFS}}\setminus {\bigcup \nolimits _{j\ne i}}O_{j}^{\mathrm {MOFS}}. \end{aligned}$$
(4)

For segmentation into more than two objects, this approach (which allows the M IRFC objects to be computed simultaneously) can compute IRFC segmentations more quickly than commonly-used algorithms that compute these segmentations one object at a time.

6 Conclusion

Fuzzy connectedness (FC) image segmentation, which finds objects based on user-specified seed sets and fuzzy affinity functions, is one of the most computationally efficient segmentation methodologies and is commonly used in practical image segmentation tasks (especially in biomedical imaging). As can be seen from the references cited in this brief presentation, the methodology has a growing literature which covers mathematical properties of the segmentations as well as users’ practice and experience.