## Fuzzy Segmentation

If what distinguishes objects in an image are not the exact values assigned to the pixels but rather some textural property (as it is the case for images containing random noise and/or shading), then fuzzy connectedness can be usefully employed to achieve segmentation (see [12-17] and their references). Fuzzy connectedness was explicitly introduced by Rosenfeld , but it had been foreshadowed earlier (for example by the "Minimum Method" in ). Our approach is based on that advocated in , but is generalized to arbitrary digital spaces .

A digital space is a pair (V, n), where V is a set and n is a symmetric binary relation on V such that V is connected under n. Apicture over this digital space is a triple (V, n, f), where f maps V into the real numbers. Because of the nature of the applications that we have in mind, we refer to elements of V as spels, which is short for spatial elements . In this paper we assume that n is antireflexive (i.e., that, for all c e V, (c, c) \$ n) and we use N(c) to denote the neighborhood of c that consists of c itself and all d e V, such that (c, d) e n. If (c, d) e n, we say that c and d are adjacent. The spels can be pixels of an image (as in [11,12,14,16-18,20]), but they can also be dots in the plane (as in [21,22]), or any variety of other things. The theory and algorithm presented here will be independent of the specifics of the application area. They are in particular applicable to data clustering  in general, and so their range of usefulness goes far beyond just image segmentation and includes such distant areas of endeavor as psychology  and statistics .

The basic concept that we are generalizing here is that of fuzzy connectedness: to every ordered pair (c, d) of spels, it assigns a real number not less than 0 and not greater than 1. This indeed is an example of a fuzzy set (as it is normally defined in the literature ): the fuzzy set in question is "the set of connected pairs" and the grade of membership of (c, d) in this set is the fuzzy connectedness of c to d. In the approach used below, fuzzy connectedness is defined in the following general manner.

We call a sequence of distinct spels a chain; its links are the ordered pairs of consecutive spels in the sequence. We define the f-strength of a link to be the appropriate value of a fuzzy spel affinity function f : V2 ^ [0, 1], i.e., afunction that assigns a value between 0 and 1 to every pair of spels in V. For example, if the set of spels V is a finite set of dots in the plane, we may define the strength of the link from one dot to another as the reciprocal of the distance between them (we need to make the unit of distance such that all distinct dots are at least one unit from each other). A chain is formed by one or more links and the f-strength of a chain is the f -strength of its weakest link; the f -strength of a chain with only one spel in it is 1 by definition. A set U(c V) is said to be f-connected if, for every pair of spels in U, there is a chain in U of positive f-strength from the first to the second spel of the pair. As we will see later, for the purpose of fuzzy segmentation of images, the strength of any link of one pixel to another can often be automatically defined based on statistical properties of the links within regions identified by the user as belonging to the object of interest.

We associate with the fuzzy spel affinity function f a fuzzy connectedness function /f : V2 ^ [0,1] defined by

c(°)=c, c(K) =d and ci=cj,if i=j i.e., the f -strength of the strongest chain from c to d. We then define the f -connectedness map f of a set V for a seed spel o by the fuzzy connectedness val-uesof o to c (f (c) = /Xf (o, c)),forall c e V .Ahard object C is then defined based on the f -connectedness map by selecting a threshold t and associating with C all spels c for which f (c) is above the threshold, i.e., C = {c | c e V, f (c) > t}.

The algorithm proposed in  for obtaining a fuzzy connectedness map uses the concept of dynamic programming and has the characteristic that a single spel can be put into a spel queue O (that holds the spels waiting to be considered in the search for optimal chains) many times. This seemed to us an unnecessary inefficiency. In  we investigated the use of so-called greedy algorithms  for computing the fuzzy connectedness map. We observed that if we treat the set V as a connected graph and we consider the cost ofthearc(c, d)tobe1 — f (c, d), some of the graph algorithms for finding shortest paths could be applied to this problem. We showed that both Dijkstra's and Prim's algorithms can be used for computing the fuzzy connectedness map of an image faster than the previously used dynamic programming algorithm. In the experiments reported in  we achieved an average speedup of 8.2 times (over the algorithm of ) when using Dijkstra's or Prim's Algorithms for computing the connectedness maps for a set of images with the same size as the image shown in Fig. 12.1 (| V | = 10,621).

To obtain a version of Dijkstra's algorithm for computing the fuzzy connectedness map we only have to make two changes to the algorithm of . First, we make O a set instead of a queue, and second, when we remove a spel from O, we remove the spel d for which f (d) is maximal (greedy step). If a spel c is already in O it is not reinserted since O is now a set. This is the reason why this greedy algorithm is more efficient than the dynamic programming algorithm, in which a spel may be inserted into O many times. In order to implement efficiently the removal of d with the maximal f (d), we make use of a priority queue, in our case a binary heap, that maintains a partial ordering of the elements in O .

In order to apply the algorithms mentioned above to image segmentation, we have to define the fuzzy spel affinity f. Usually this is done by a computer program, based on some minimal information supplied by a user [11,12,19]. The underlying idea is that, even though the user most likely will not be able to define mathematically the characteristics of the object of interest, it is quite easy for him/her to select a spel belonging to it. The program will then compute some statistics based on the neighborhood of the selected spel and use these statistics to compute the fuzzy spel affinity f. We now make a sample methodology we have been using to achieve this.

For a picture (V, n, I) and selected spel o, we define f by i [g1(I(c)+I(d))+g2(|I(c)-I(d)|)] if (c d) _ f (C,d) = 2 ii(c 'd),6 n ' (12.2)

The values for m and oi are computed using the spels in the neighborhood of o: m1 and o1 are defined as the mean and standard deviation, respectively, of I(c) + I(d) over all adjacent spels c and d in N(o) and m2 and o2 are defined to be the mean and standard deviation, respectively, of 11(c) — I(d)| over all adjacent Figure 12.1: A mathematically defined image (top-left) on a hexagonal grid was segmented using thresholding (top-right) and fuzzy segmentation (bottom row).

spels c and d in N(o). This means that for any pair (c, d) of adjacent spels, their fuzzy spel affinity will be large if both I(c) + I(d) and 11(c) — I(d)| have values similar to those in the neighborhood of the selected spel. This definition reflects the fact that in many applications both the values assigned by I to spels and the differences between the values assigned to neighboring spels are important for distinguishing objects in an image.

As an example, the top-left image in Fig. 12.1 was mathematically defined on the hexagonal grid (each element of V is a hexagon and all of them are arranged on an enclosing hexagon with | V| = 10,621), and the user was asked to select a spel that is located inside the object to be segmented. The object in question is the rectangular region in the upper half of the image with slowly increasing brightness from left to right. In this example, two hexagons are considered to be adjacent if, and only if, they share an edge (thus the neighborhood of any interior hexagon consists of seven hexagons), and I(c) is the gray value assigned to the hexagon c.

The image on the top-right of Fig. 12.1 is the result of thresholding the original image at some level. Note that because of the brightness variation inside the object that we wish to segment (the horizontal stripe near the top of the image) there is no threshold level that can successfully segment it from the background. When using the fuzzy segmentation algorithm, the user chose a point belonging to the object (the brightest point in the lower-left image) that is used to identify the neighborhood over which information is collected regarding the characteristics of the object, to be used in Eqs. (12.2) and (12.3). The resulting fuzzy spel affinity ^ is then used to produce the connectedness map f shown in the lower-left image (note that (V, n, f) is also a picture over the digital space (V, n)), which is then thresholded to produce the successful final segmentation shown in the lower-right image (the hexagons belonging to the resulting hard object are shown white).

0 0