All the methods described in Section 7.3 suffer from a common limitation: Self-intersections may happen during the evolution of the initial curve/surface.

Traditional deformable models [6, 19, 42], including the one defined by Eq. (7.9), cannot efficiently deal with self-intersections. It is due to the nonlocal testes dependency, which requires O (N2) in the worst case, where N is the number of mesh nodes (or snaxels, for 2D).

Recently, in [63] we have shown that such limitation can be addressed by using the T-snakes model because the reparameterization process of this model can naturally deal with self-intersections. It can also be addressed for 3D by using the T-surfaces.

Firstly, let us make some considerations about the T-snakes/T-surfaces.

The threshold T used in the normal force definition (7.12) plays an important role in the T-surfaces model [47,49]. If not chosen properly, the T-surfaces can be frozen in a region far from the target(s) [33,63].

The choice of T is more critical when two objects to be segmented are too close, as shown in Fig. 7.7. In this example, the marked grid nodes are those whose image intensity falls bellow the threshold T.

For T-snakes model to accurately segment the pictured objects, it has to burn the marked grid nodes. However, the normal force given by expression (7.12) changes its signal if the T-snakes gets closer. So, the force parameters

I |
\ \ |
\ | ||

SecSe^ | ||||

\ | ||||

o |

Figure 7.7: T-snake and grid nodes marked.

in expressions (7.11) and (7.12) have to be properly chosen to guarantee the advance over narrow regions. However, parameters choice remains an open problem in snake models [31]. This problem can be addressed by increasing the grid resolution as it controls the flexibility of T-surfaces. However, this increases the computational cost of the method.

To address the trade-off between model flexibility and the computational cost, in [22,29] we propose to get a rough approximation of the target surfaces by isosurfaces generation methods. Then T-surfaces model is applied.

The topological capabilities of T-surfaces enable one to efficiently evolve the isosurfaces extracted. Thus, we combine the advantages of a closer initialization, through isosurfaces, and the advantages of using a topologically adaptable deformable model. These are the key ideas of our previous works [22,29]. We give some details of them.

At first, a local scale property for the targets was supposed: Given an object O and a point p e O, let rp be the radius of a hyperball Bp which contains p and lies entirely inside the object. We assume that rp > 1 for all p e O. Hence, the minimum of these radii (rmjn) is selected.

Thus, we can use rmjn to reduce the resolution of the image without losing the objects of interest. This idea is pictured in Fig. 7.8. In this simple example, we have a threshold which identifies the object (T < 150), and a CF triangulation whose grid resolution is 10 x 10.

Now, we can define a simple function, called an object characteristic function, as follows:

X (p) = 0, otherwise, where p is a node of the triangulation (marked grid nodes on Fig. 7.8(a)).

Figure 7.8: (a) Original image and characteristic function. (b) Boundary approximation.

Figure 7.8: (a) Original image and characteristic function. (b) Boundary approximation.

We can do a step further, shown in Fig. 7.8(b), where we present a curve which belongs to the transverse triangles. Observe that this curve approximates the boundary we seek. This curve (or surface for 3D) can be obtained by isosurface extraction methods and can be used to efficiently initialize the T-surfaces model, as we already pointed out before.

If we take a grid resolution coarser than rmin, the isosurface method might split the objects. Also, in [22,29] it is supposed that the object boundaries are closed and connected. These topological restrictions imply that we do not need to search inside a generated connected component.

In [63] we discard the mentioned scale and topological constraints. As a consequence, the target topology may be corrupted. So, a careful approach will be required to deal with topological defects. An important point is the choice of the method to be used for isosurfaces generation. In [22,63] we consider two kinds of isosurface generation methods: the marching ones and continuation ones.

In marching cubes, each surface-finding phase visits all cells of the volume, normally by varying coordinate values in a triple "for" loop [45]. As each cell that intersects the isosurface is found, the necessary polygon(s) to represent the portion of the isosurface within the cell is generated. There is no attempt to trace the surface into neighboring cells. Space subdivision schemes (such as Octree and k-d-tree) have been used to avoid the computational cost of visiting cells that the surface does not cut [17,64].

Once the T-surfaces grid is a CF one, the tetra-cubes is especially interesting for this discussion [10]. As in the marching cubes, its search is linear: Each cell of the volume is visited and its simplices (tetrahedrons) are searched to find surfaces patches. Following marching cubes implementations, tetra-cubes uses auxiliary structures based on the fact that the topology of the intersections between a plane and a tetrahedron can be reduced to three basic configurations pictured in Fig. 7.1 (Section 7.2.3).

Unlike tetra-cubes, continuation algorithms attempt to trace the surface into neighboring simplices [1]. Thus, given a transverse simplex, the algorithm searches its neighbors to continue the surface reconstruction. The key idea is to generate the combinatorial manifold (set of transverse simplices) that holds the isosurface.

The following definition will be useful. Let us suppose two simplices a0, a1, which have a common face and the vertices v e a0 and v' e a1 both opposite the common face. The process of obtaining v' from v is called pivoting. Let us present the basic continuation algorithm [1].

PL generation algorithm:

Find a transverse triangle a0; J2 = {0}; V (a0) = set of vertices of a0; while V (a) = 0 for some a e . get a such that V (a) = 0; . get v e V (a);

. obtain a' from a by pivoting v into v' . if a' is not transverse . then drop v from V (a);

Differently from tetra-cubes, once the generation of a component is started, the algorithm runs until it is completed. However, the algorithm needs a set of seed simplices to be able to generate all the components of an isosurface. This is an important point when comparing continuation and marching methods.

If we do not have guesses about seeds, every simplex should be visited. Thus, the computational complexity of both methods is the same (O (N) where N is the number of simplices).

However, if we know in advance that the target boundary is connected, we do not need to search inside a connected component. Consequently, the computational cost is reduced if continuation methods are applied.

Based on this discussion about marching cubes and PL generation, we can conclude that, if we do not have the topological and scale restrictions given in Section 7.4, tetra-cubes is more appropriate to initialize the T-surfaces. In this case, it is not worthwhile to attempt to reconstruct the surface into neighboring simplices because all simplices should be visited to find surface patches.

However, for the T-surfaces reparameterization (steps (1)-(4) in Section 7.2.3), the situation is different. Now, each connected component is evolved at a time. Thus a method which generates only the connected component being evolvedâ€”that is, the PL generation algorithmâ€”is interesting.

Was this article helpful?

## Post a comment