Biomedical Engineering Reference
In-Depth Information
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
=
(
q
1
,
q
2
,
q
3
), find the corresponding
meta-cell ID through the expression (7.28).
Besides, we need some auxiliary structures. The characteristic function (
χ
)
is a zero field at the beginning. There is a
processing list
which is dynamically
constructed through a procedure called
insert neighbor s
:
insert neighbor s
(
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 ele-
ments 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 neigh-
bors belong to the same meta-cell. Also, we suppose that the object of interest
has intensity pattern inside the range [
I
1
,
I
2
].
Figure 7.12: (a) Example of BFS algorithm in graphs. ( b) Possible order of
visiting nodes after BFS with seed
S
.