Biomedical Engineering Reference
In-Depth Information
(a)
(b)
(c)
Figure 22.
(a) Simplicial approximation of contour model using a Freudenthal triangulation
[59]. (b) Cell classification. (c) Intersection of two snakes with “inside” grid cell vertices
marked. Snake nodes in triangles A and B are reconnected. Reprinted with permission
from [59]. Copyright c
1995, IEEE.
the creation of local polygonal approximations of a contour or surface model.
In an
n
-simplex, the negative vertices can always be separated from the positive
vertices by a single plane; thus, an unambiguous polygonalization of the simplex
always exists, and as long as neighboring cubes are decomposed so that they share
common edges (or faces in 3D) at their boundaries, a consistent polygonization
will result. The set of simplices (or triangles in 2D) of the grid that intersect the
surface or contour (the boundary triangles) form a two-dimensional combinatorial
manifold that has as its dual a one-dimensional manifold that approximates the
contour. The one-dimensional manifold is constructed from the intersection of
the true contour with the edges of each boundary triangle, resulting in one line
segment that approximates the contour inside this triangle (Figure 22a). The
contour intersects each triangle in two distinct points, each located on a different
edge. The set of all these line segments constitutes the combinatorial manifold
that approximates the true contour.
The cells of the triangulation can be classified in relation to the partitioning
of space by a closed contour model by testing the “sign” of the cell vertices during
each time step. If the signs are the same for all vertices, the cell must be totally
inside or outside the contour. If the signs are different, the cell must intersect the
contour (Figure 22b).
The simplicial decomposition of the image domain also provides a framework
for efficient boundary traversal or contour tracing. This property is useful when
models intersect and topological changes must take place. Each node stores the
edge and cell number it intersects, and, in a complementary fashion, each boundary
cell keeps track of the two nodes that form the line segment cutting the cell. Any
node of the model can be picked at random to determine its associated edge and
cell number. The model can then be traced by following the neighboring cells
indicated by the edge number of the connected nodes.
