## Experiments

Now we demonstrate the usage of Algorithm 1 on mathematically-defined as well as on real images. Similarly to the example shown in section 12.2, the appropriate fuzzy spel affinities were automatically defined by a computer program, based on some minimal information supplied by a user. However, this is not the only option: for example, if sufficient prior knowledge about the class of

Figure 12.3: A mathematically defined image (top left) including both background variation and noise, and the corresponding 3-segmentation (top right and bottom row).

segmentation problems to which the application at hand belongs is available, then the whole segmentation process can be automated by designing a program that automatically selects the seeds for the objects to be segmented, as it was done in [30] to segment macromolecules in electron microscopy volumes.

On the top-left of Figs. 12.3-12.7 and in the left column of Fig. 12.8 are images defined on a V consisting of regular hexagons that are inside a large hexagon (with 60 spels on each side, a total of 10,621 spels). In all these examples, M = 3. For these experiments we defined Vm (1 < m < 3) to be the set of spels indicated by the user plus their six neighbors. The fuzzy affinity functions fm (1 < m < 3) were computed according to Eqs. (12.2) and (12.3), with adjacency n between hexagons meaning that they share an edge.

The other three images of Figs. 12.3-12.7 represent the resulting om (obtained by Algorithm 1) with the brightness of each spel encoding its grade of membership in an object. (For Fig. 12.3 we selected the seed spels so that V1 = V2, for Fig. 12.4 we selected the seed spels so that V2 = V3, and for Figs. 12.5-12.7 the three sets of seed spels are pairwise disjoint, which happens to result, because of the large number of gray levels used in the images

Figure 12.4: A mathematically defined image (top left) including both background variation and noise, and the corresponding 3-segmentation (top right and bottom row).
Figure 12.5: A mathematically defined image (top left) including both background variation and noise, and the corresponding 3-segmentation (top right and bottom row).
Figure 12.6: A mathematically defined image (top left) including both background variation and noise, and the corresponding 3-segmentation (top right and bottom row).
Figure 12.7: A mathematically defined image (top left) including both background variation and noise, and the corresponding 3-segmentation (top right and bottom row).
Figure 12.8: Two images obtained using magnetic resonance imaging (MRI) of heads of patients (left) and the corresponding 3-segmentations (right). (Color slide.)

to be segmented, in the three objects being pairwise disjoint as well.) The right column of Fig. 12.8 shows the resulting maps of the am by assigning the color (r, g, b) = 255 x (af, a^, a£) to the spel c. Note that not only the hue, but also the brightness of the color is important: the less brightly red areas for the last two images correspond to the ventricular cavities in the brain, correctly reflecting a low grade of membership of these spels in the object that is defined by seed spels in brain tissue. The seed sets Vm consist of the brightest spels. The times taken to calculate these 3-segmentations using our algorithm on a 1.7 GHz Intel® Xeon personal computer were between 90 and 100 ms for each of the seven images (average = 95.71 ms). Since these images contain 10,621 spels, the execution time is less than 10 ^s per spel. The same was true for all the other 2-D image segmentations that we tried, some of which are reported in what follows.

To show the generality of our algorithm and to permit comparisons with other algorithms, we also applied it to a selection of real images that appeared in the recent image segmentation literature. Since in all these images V consist of squares inside a rectangular region, the n of Eq. (12.2) is selected to

Figure 12.9: An SAR image of trees and grass (left) and its 2-segmentation (center and right).

be the edge-adjacency (4-adjacency) on the square grid. We chose to include in the sets of seed spels not only the spels at which the user points but also their eight edge-or-vertex adjacent spels. Except for this adaptation, the previous specification is verbatim what we use for the experiments which we now describe.

In [31] the authors demonstrate their proposed technique by segmenting an SAR image of trees and grass (their Fig. 1, our Fig. 12.9 left). They point out that "the accurate segmentation of such imagery is quite challenging and in particular cannot be accomplished using standard edge detection algorithms." They validate this claim by demonstrating how the algorithm of [32] fails on this image. As illustrated on the middle and right images of Fig. 12.9, our technique produces a satisfactory segmentation. On this image, the computer time needed by our algorithm was 0.3 s (on the same 1.7 GHz Intel® Xeon personal computer that we use for all experiments presented in this section), while according to a personal communication from the first author of [31], its method "took about 50 seconds to reach the 2-region segmentation for this 201-by-201 image on Sparc 20, with the code written in C."

In Figs. 12.10-12.12 we report on the results of applying our approach to two physically obtained images from [6]: an aerial image of San Francisco (top-left image of Fig. 12.10) and an indoor image of a room (top-left image of Fig. 12.11). The middle and bottom images of the left column of Fig. 12.10 show a 2-segmentation of the San Francisco image into land and sea, while the right column shows how extra object definitions can be included in order to produce a more detailed labeling of a scene, with the 3-segmentation of the San Francisco image separating the Golden Gate Park from the rest of the land object. Figure 12.11 shows the original image (top-left) and a 5-segmentation of the

Figure 12.10: Aerial image of San Francisco (top left), a 2-segmentation into land and sea (middle and bottom images on the left column) and a 3-segmentation into built-up land, the Golden Gate Park, and sea (right column).

Figure 12.11: An indoor image of a living room (top left) and its 5-segmentation.

living room image. The 6-segmentation of the room shown in Fig. 12.12 includes a new object corresponding to the base and arm of one of the sofas.

It is stated in [6] that the times needed for the segmentations reported in

that paper "are in the range of less than five seconds" (on a Sun UltraSparc ). Our CPU time to obtain the segmentations shown in Figs. 12.10-12.12 is

Figure 12.12: A 6-segmentation of the indoor image of a living room shown in Fig. 12.11.

around 2 s. However, there is a basic difference in the resolutions of the segmentations. Since the segmentation method used in [6] is texture based, the original 512 x 512 images are subdivided into 64 x 64 "sites" using a square window of size 8 x 8 per site. In the final segmentations of [6] all pixels in a particular window are assigned to the same object. As opposed to this, in our segmentations any pixel can be assigned to any object. Another way of putting this is that we could also make our spels to be the 8 x 8 windows of [6] and thereby reduce the size of the V to be a 64th of what it is currently. This should result in a two order of magnitude speedup in the performance of our segmentation algorithm (at the cost of a loss of resolution in the segmentations to the level used in [6]).

0 0