The snake, a one-dimensional curve that encloses a two-dimensional image feature, was discussed in the previous sections. The governing equations can easily be extended to three dimensions. For example, the balance of forces described in Equation (6.7) would be discretized through finite differences in the x, y, and z directions. The external force (image force) would be represented by a gradient in three directions, broadened by three-dimensional Gaussian blur or three-dimensional gradient vector flow. The vertices (which now are allowed to move in three spatial directions toward their energy minimum) constitute a closed surface that surrounds a three-dimensional image feature, much like a balloon that contracts and shrink-wraps the object. An example of this process is shown in Figure 6.13, where a balloonlike active surface is dragged toward the edge of the object and shrink-wraps around it, closely following the brain gyri and sulci in the last iteration.
Specialized formulations, such as greedy formulation, ballooning forces, and gradient vector flow, can also readily be adapted for three dimensions. However, the added dimension drastically increases computation time. In addition, interactive initial placement of the shape becomes more difficult. One alternative is the placement of a series of snakes, slice by slice, around the object. The individual snakes can then be joined to form a closed surface and be subjected to the iterative minimization of the snake energy.
A detailed formulation of a three-dimensional active surface, termed a three-dimensional active net, was provided by Takanashi et al.30 A mesh, initially rectangular, is discretized into vertices v(p,q) = (x(p,q), y(p,q), z(p,q)). Here p and q are parameters of the surface with 0 < p < 1 and 0 < q < 1. Index variables i and j can be used to enumerate the vertices. For a mesh with (n + 1) m vertices, we can therefore write
FIGURE 6.13 Surface rendering of a human brain from MR data (A) after segmentation of the brain and deepening of the sulci by thresholding. A balloon-line active surface is shown step by step to shrink around the segmented brain and follow the gradient forces into the sulci (B-F). Particularly in image F, the active surface can be seen to take some "shortcuts" to minimize its bending energy.
Each vertex with the exception of the boundary vertices is connected with four neighboring vertices. To enclose a convex, three-dimensional shape, the mesh is now deformed into an ellipsoid in two steps. First, a tube surface is created when matching vertices along the left and right borders are connected with the boundary condition v(n, jl) = v(0, jl). Additional mesh connections are created between diagonally opposing vertices by duplicating the mesh outside the range 0 < i < n and with the additional boundary condition a, (3, and 7 are user-selectable weight factors with a function analogous to the snake [Equation (6.23)]. Equation (6.38) can readily be discretized with finite
where n is required to be an even number. In the second step, the cylinder is distorted to form an ellipsoid, and the vertices of the upper and lower end rings of the tube collapse into a single vertex. The resulting mesh is a three-dimensional network rather than a balloon. Energy minimization takes place analogously to the snake through
Eint is the sum of the stretching energy (computed through the first derivative toward the two index variables) and the bending energy (computed through the second derivative toward the two index variables). Econst is the energy contribution from constraints such as attractors and repulsors. Since this energy depends strongly on the user interface, Econst = 0 can be assumed in most cases. The image energy, Eimage, is the absolute image intensity in this formulation as opposed to the gradient magnitude in the snake formulations. In the numerical implementation, the minimization of Enet gives rise to three independent Euler-Lagrange differential equations that cover the partial derivatives of all three spatial components:
differences. For the x component of Equation (6.38), the following finite differences can be applied:
Equation (6.39) lists one spatial component only; the partial derivatives of the y and z components can be obtained in an analogous manner. For the gradient of the image energies, the finite difference scheme
or a Sobel-like difference operator may be used. Again, the image derivatives toward the spatial directions y and z are similar. The vertex coordinates (x,y,z) are not necessarily integer coordinates, so it will generally be required to perform some form of interpolation to obtain the image values I. By substituting Equations (6.39) and (6.40) into Equation (6.38) and moving the image energy term to the right-hand side, the system of Equations (6.38) for each vertex can be written in matrix form, analogous to Equation (6.25) and its discretization. The matrix system assumes the form
A contains the discretization elements and the weight factors a and (3, b contains the image energy terms, and x contains the vector of vertices. A can be decomposed into the diagonal elements D, the lower left triangle matrix E, and the upper right triangle matrix F. With this decomposition, an iterative time-stepping scheme becomes possible:
Application of Equation (6.42) advances the position vector x from time step T to time step T + 1. The additional parameter k improves convergence behavior through under relaxation and should be chosen to be k < 1. Like snakes, the active net tends to lock onto local minima, so the final convergence result will depend on the initial placement of the ellipse and on the choice of the weight parameters a, p, and 7.
Because of the high computational complexity, several modified approaches have been introduced. For example, Cohen and Cohen8 suggested the use of finite-element modeling to reach the energy minimum in shorter time. Bro-Nielsen proposed a model of active cubes.4 The term active cubes points at the fundamental difference between a three-dimensional active surface and the active cubes model: The active cube model simulates a filled solid. Active cubes combine ideas from snakes and active nets. Energy minimization is performed, where the total energy consists of the internal energy (bending and stretching energy) and the external energy. Contrary to the principle used in snakes, but similar to the active nets,30 direct image intensity data are used for the external forces instead of a gradient, and the cubes deform toward highest image intensities. Active cubes are well suited to simulate and parametrize elastic deformation (e.g., knee bending or jaw movement).
