Biomedical Engineering Reference
In-Depth Information
7.7 Out-of-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,
C
2
/
3
active cells (or voxels). Therefore, we
read
C
1
/
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 ex-
pect to read
C
1
/
3
·
(
K
/
B
) disk blocks to complete the isosurface. Henceforth,
we can increase meta-cells sizes while keeping the effect of the factor
C
1
/
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:
I
0
=
[0
,
0];
I
1
=
[2
,
2];
...
;
I
127
=
[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 2
9
×
2
9
×
2
9
data set, if we take meta-cells with 2
4
×
2
4
×
2
4
data points, we find 2
15
=
32 kB meta-cells. Thus, we will need an amount of 2
×
128
×
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
