Biomedical Engineering Reference
In-Depth Information
branch-on-need (T-BON) octree
) minimizes the impact of the I /O bottleneck by
reading from disk only those portions of the search structure and data necessary
to construct the current isosurface. The method works as follows.
A preprocessing step builds a BONO for each time step and properly stores
it to disk. To avoid I/O performance problems at run-time, the algorithm packs
nodes into disk blocks in order to read a number of nodes at once.
At run-time, the tree infrastructure is read from disk and recreated in mem-
ory. Isovalues queries are then accepted in the form
(timestep,isovalue)
. The
algorithm initially fetches the root node of the octree corresponding to
timestep
from disk. If the extreme values are stored in the root node span
isovalue
, the
algorithm next fetches all children of the root node from disk. This process re-
peats recursively until reaching the leaf nodes. Then, the algorithm computes
disk blocks containing data points needed by that leaf and inserts those blocks
into a list. Once all nodes required to construct the current isosurface have
been brought into memory, the algorithm traverses the block list and reads the
required data blocks sequentially from disk.
The meta-cell technique proposed by Chiang
et al.
[16] works through a
similar philosophy. Given an
isovalue
, the query pipeline follows the next steps:
(1) query the interval tree to find all meta-cells whose meta-intervals contain
the
isovalue
(
active meta-cells
); ( b) sort the reported meta-cell IDs properly
to allow sequential disk reads; and (c) for active meta-cell, read it from disk to
main memory and compute the corresponding isosurface patches.
An important difference between the meta-cell technique and T-BON is that,
unlike T-BON, meta-cell uses two distinct structures: one for the scalar field in-
formation (interval tree) and another for the space partition. The link between
these structures is given by the interval tree leaves information (meta-intervals
and pointers to corresponding meta-cells). Such split in the way meta-cell tech-
nique deals with domain partition and the scalar field gives more flexibility to
meta-cell if compared with T-BON.
For instance, the query “given a point (
x
,
y
,
z
), find its image intensity,” useful
when segmenting with deformable models, is implemented more easily through
meta-cell (see expression (7.28)) than with BONO. Besides, image data sets are
represented on regular grids which means that we do not need hierarchical
structures to take account for regions with higher density of points. These are
the reasons why meta-cell is more suitable for out-of-core image segmentation
than BONO. Next, we will explore this fact.
