## Outof Core Segmentation Approach

In this section we present the out-of-core version of the segmentation framework described in Section 7.5.

That algorithm is interesting for this work because of two aspects. First, it uses the T-surfaces model which uses auxiliary and very memory consuming data structures (hash table to keep transverse simplices, T-surfaces mesh, etc.). Thus, a suitable out-of-core implementation would improve algorithm performance as well as make it possible to segment the data sets which would not fit in memory. Second, it needs both the queries found in segmentation algorithms: (a) Given a reference value q, find all image points p such that I(p) = q and (b) given a point p, find the image intensity I( p).

The meta-cell technique used has the following elements.

Meta-cell partition: The meta-cell size is application dependent. Basically, it depends on the data set size, disk block size, and the amount of memory available. For isosurface extraction, we can obtain a quantitative bound by following [16] and taking the dimensional argument that an active meta-cell with C cells has, most of times, C2/3 active cells (or voxels). Therefore, we read C1/3 layers of cells for each layer of isosurface. Thus, if the isosurface cuts K cells and if B is the number of cells fitting in one disk block, we expect to read C1/3 ■ (K/B) disk blocks to complete the isosurface. Henceforth, we can increase meta-cells sizes while keeping the effect of the factor C1/3 negligible.

Interval tree: Volumetric images have some particular features that must be considered. Intensity values range from 0 to 255 and the data set is represented by a regular grid. This information can be used to find an upper bound for the interval tree size. Let us consider the worst case, for which the meta intervals are of the form: I0 = [0, 0]; I1 = [2, 2];...; I127 = [254, 254]. Thus, in the worst case, we have 128 meta-intervals for each meta-cell. Each meta-interval uses two bytes in memory. For a 29 x 29 x 29 data set, if we take meta-cells with 24 x 24 x 24 data points, we find 215 = 32 kB meta-cells. Thus, we will need an amount of 2 x 128 x 32 kB = 8.0 MB, which is not restrictive for usual workstations. Besides, in general, interval tree sizes are much smaller than this bound (see Section 7.9). Thus, we do not pack tree nodes as in [16].

Data cache: To avoid memory swap, we must control the memory allocation at run-time. This can be done through a data cache, which can store a predefined number M of meta-cells. When the cache fills, the least recently used (LRU) meta-cell will be replaced [64].

Query algorithm: (a) Given an isovalue q, find all meta-intervals (and the corresponding meta-cell IDs) containing q, by querying the I/O interval tree defined in Section 7.6. (b) Given a point q = (q1, q2, q3), find the corresponding meta-cell ID through the expression (7.28).

Besides, we need some auxiliary structures. The characteristic function (x) is a zero field at the beginning. There is a processing list which is dynamically constructed through a procedure called insert neighbors:

insert neighbors (p): For each neighbor q of a node element p, verify if q has not been evolved by Eq. (7.14) and if q £ processing list. In this case, insert q in processing list.

The key idea behind the processing list construction is to update node elements according to a breadth-first-search (BFS) algorithm; that is, we consider neighbors of a node as predecessors in the search. With such a procedure, we can minimize I/O operations due to the following property: starting at a seed, the algorithm visits all the neighbors; then it visits all the neighbors of neighbors, etc. until it runs out of neighbors to visit (see Fig. 7.12).

Thus, the least recently used meta-cell must be replaced when data cache fills because most probably the portion of T-surfaces that intersects that meta-cell has been completely updated. Certainly, we can generate the isosurfaces in step (2) according to a breadth-first-search continuation algorithm. However, we chose to incorporate this procedure in the T-surfaces method to get more generality for the out-of-core segmentation method.

Next, we outline the algorithm. We call seed a node element for which neighbors belong to the same meta-cell. Also, we suppose that the object of interest has intensity pattern inside the range [ I1, I2].

Figure 7.12: (a) Example of BFS algorithm in graphs. (b) Possible order of visiting nodes after BFS with seed S.

Figure 7.12: (a) Example of BFS algorithm in graphs. (b) Possible order of visiting nodes after BFS with seed S.

Out-of-Core Segmentation Algorithm:

(1) Compute Object_Characteristic_Function

.Traverse interval tree to find the list L of active meta-cells; .While L is not NULL

. Read M active meta-cells to main memory. . Take a metacell. Given a grid node p e metacell: if I (p) e [ h, I2] then x (p) = 1

(2) Extract isosurfaces.

(3) If needed, increase grid resolution. Go to step (1)

(4) Find a seed and insert it into processing list

(5) Begin T-Surfaces model;

.While the processing list is not empty: . Pop a point p from processing list . Find the corresponding meta-cell(p) . If meta-cell(p) is not in memory, read it . Find I (p) and VI ( p) . Update p according to Eq. (7.14) . Call insert ^neighbors ( p) .Update function x

.Reparameterization of T-Surfaces (Section 7.2.3) .If the termination condition is not reached, go to (4).

We shall observe that when the grid resolution of T-surfaces is (locally) increased in step (3), the list L of active meta-cells remains unchanged and the procedure to define the Object_Characteristic_Function does not change. Also, we must observe that the isosurfaces are taken over the object characteristic function field. Thus, there are no I/O operations in step (2).