## Segmentation

As showed before, the multiseeded segmentation algorithm is general enough to be applied to images defined on various grids. One has several options for representing a 3D image; in this section, when performing segmentation on 3D images, we choose to represent them on the face-centered cubic (fcc) grid, for reasons that are presented later.

Using Z for the set of all integers and 8 for a positive real number, we can define the simple cubic (sc) grid (Ss), the face-centered cubic (fcc) grid (Fs) and the body-centered cubic (bcc) grid (Bs) as

Fs = {(8ci, Sc2, 8cb) | ci, c2, cb e Z and ci + c2 + c3 = 0 (mod 2)}, (12.17) Bs = {(8c1; Sc2, 8cb) | c1; c2, cb e Z and c1 = c2 = c3 (mod 2)}, (12.18)

where 8 denotes the grid spacing. From the definitions above, the fcc and bcc grids can be seen either as one sc grid without some of its grid points or as a union of shifted sc grids, four in the case of the fcc and two in the case of the bcc.

We now generalize the notion of a voxel to an arbitrary grid. Let G be any set of points in R3, then the Voronoi neighborhood of an element g of G is Figure 12.13: Three grids with the Voronoi neighborhood of one of their grid points. From left to right: the simple cubic (sc) grid, the face-centered cubic (fcc) grid, and the body-centered cubic (bcc) grid.

defined as

Ng(g) = { e R3 | for all h e G, - g|| < - h\\}. (12.19)

In Fig. 12.13, we can see the sc, the fcc and the bcc grids and the Voronoi neighborhoods of the front-lower-left grid points.

Why should one choose grids other than the ubiquitous simple cubic grid? The fcc and bcc grids are superior to the sc grid because they sample the 3-D space more efficiently, with the bcc being the most efficient of the three. This means that both the bcc and the fcc grid can represent a 3-D image with the same accuracy as that of the sc grid but using fewer grid points .

We decided to use the fcc grid for 3-D images instead of the bcc grid for reasons that will become clear in a moment; now we discuss one additional advantage of using the fcc grid over the sc grid. If we have an object that is a union of Voronoi neighborhoods of the fcc grid, then for any two faces on the boundary between this object and the background that share an edge, the normals of these faces make an angle of 60° with each other. This results in a less blocky image than if we used a surface based on the cubic grid with voxels of the same size. This can be seen in Fig. 12.14, where we display approximations to a sphere based on different grids. Note that the display based on the fcc grid (center) has a better representation than the one based on the sc grid with the same voxel volume (left) and is comparable with the representation based on cubic grid with voxel volume equal to one eighth of the fcc voxel volume (right).

The main advantage of the bcc grid over the fcc grid is that it needs fewer grid points to represent an image with the same accuracy. However, in the bcc

0 0