## Ooo

Figure 12.14: Computer graphic display of a sphere using different grids (reproduced from [19]). (a) Display based on a sc grid with voxels of the same volume as the display based on a fcc used for (b). The image (c) corresponds to a display based on a sc grid with voxels of volume equal to one eighth of the voxel volume in the other two images.

grid, grid points whose Voronoi neighborhoods share a face can be at one of two distances from each other, depending on the kind of face they share (see Fig. 12.13), a characteristic that may not be desirable. The Voronoi neighborhoods of an fcc grid Fs are rhombic dodecahedra (polyhedra with 12 identical rhombic faces), as can be seen in Fig. 12.13. We can define the adjacency relation P for the grid Fs by: for any pair (c, d) of grid points in Fs,

Each grid point c e Fs has 12 P -adjacent grid points in Fs .In fact, two grid points in Fs are adjacent if, and only if, the associated Voronoi neighborhood share one face. In practice these definitions give rise to a digital space (V, n) by using a V that is a finite subset of Fs and a n that is the P of Eq. (12.20) restricted to V. (Note that since Eq. (12.2) ignores distance, a similar approach applied to the bcc grid would have the undesirable consequence of having a fuzzy spel affinity that does not incorporate the difference in distances between adjacent spels.)

Experiments with segmentations using this approach on 3-D images were reported in [34]. Here we present two more recent experiments from [35] of multiple object fuzzy segmentation of 3-D images on the fcc grid.

The first experiment was performed on a computerized tomography (CT) reconstruction that assigned values to a total of (298 x 298 x 164)/2 = 7,281,928 (see Eq. 12.17)) fcc grid points. We selected seeds for four objects, the intestine (red object), other soft tissues (green object), the bones (blue object) and the

Figure 12.15: Two axial slices from a CT volume placed on the fcc grid and the corresponding 4-segmentations. (All four images were interpolated to the sc grid for display purposes.)

lungs/background (cyan object). Then, using a 1.7 GHz IntelĀ® Xeon personal computer, our program performed the 4-segmentation on this volume that is shown in Fig. 12.15.

The execution time of our program was 249 s, or approximately 34 ^s were needed per spel to perform the segmentation. Based on the execution timings for the previous experiments, one should expect a smaller execution time for this volume. There are three main reasons why the average number of spels segmented per second is not higher. First, since we have used the ^-adjacency, the number of neighboring spels was doubled or tripled when compared to the previous examples, where we used the edge-adjacency for the images on the hexagonal (six neighbors) and square (four neighbors) grids, respectively.

Second, the memory saving approach used in implementing the 3-D version of our algorithm slowed down the execution. (Since the goal was to segment volumes that could have as many as 512 x 512 x 512 spels, we chose to implement a "growing" heap, where a new level of the heap was added or an old one was removed as the program was executed depending on the number of spels currently in the heap, so that the memory usage was kept as low as possible. Note that, besides the heap, both the M-segmentation map and the original volume are accessed simultaneously by Algorithm 1). Finally, our program was developed with the goal of being able to segment images placed on the sc, fcc, and bcc grids, and this generality also contributed to the longer execution time of the algorithm; as opposed to the approach taken in the 2-D case, where we use two programs to produce the segmentations shown in subsection 12.3.3 (one for the images on the hexagonal grid and another for the images on the square grid).

In order to have a better idea of the quality of the segmentation produced by our algorithm on this volume, we created a 3-D model of the segmented intestines (the red object of Fig. 12.15) using the software OpenDX [36], which can be seen in Fig. 12.16. Since OpenDX can work with arbitrary grids, we used the fcc grid: the surface shown on Fig. 12.16 consists of faces of rhombic dodecahedra (fcc Voronoi neighborhoods).

Figure 12.16: A 3-D view of the segmented intestines shown in Fig. 12.15.

For a second experiment, we interpolated a clinically obtained CT dataset from the sc grid to the fcc grid. In this experiment, the aim is to segment the trachea and bronchial tubes so that they can be subsequently visualized in a virtual bronchoscopy (VB) animation [35]. (We refer to this dataset as the VB dataset.) This dataset is formed by 512 x 512 x 60/2 fcc grid points.

Figures 12.17 and 12.18 show two axial slices of the VB dataset and corresponding slices of a 4-segmentation of it. Our segmentation program produced this 4-segmentation of the VB dataset containing 7,864,320 fcc grid points in 263 s or approximately 33 ^s per spel.

One should observe that even though the attenuation coefficients of the reconstructed spels in the lung area are in the same range (for the current

Figure 12.17: An axial slice from the VB dataset volume placed on the fcc grid and three maps of a 4-segmentation of it. (All four images were interpolated to the sc grid for display purposes.)

Figure 12.18: An axial slice from the VB dataset volume placed on the fcc grid and three maps of a 4-segmentation of it. (All four images were interpolated to the sc grid for display purposes.)

Figure 12.18: An axial slice from the VB dataset volume placed on the fcc grid and three maps of a 4-segmentation of it. (All four images were interpolated to the sc grid for display purposes.)

display window settings) as those in the bronchi and trachea, the placement of seeds in the areas of the lung close to bronchial junctions stop the leakage of the trachea-bronchi object (top right) into the lung object (bottom right). Figure 12.19 shows a 3-D view of the segmented trachea and bronchial tubes.

0 0