**Overview:** Active
contour and surface models, also known as deformable models, are powerful
image segmentation techniques. Geometric deformable models implemented
using level set methods have advantages over parametric models due to
their intrinsic behavior, parameterization independence, and ease of implementation.
However, a long claimed advantage of geometric deformable models --- the
ability to automatically handle topology changes --- turns out to be a
liability in applications where the object to be segmented has a known
topology that must be preserved. In this project, we develop a new class
of geometric deformable models designed using a novel topology-preserving
level set method, which achieves topology preservation by applying the
simple point concept from digital topology. These new models maintain
the other advantages of standard geometric deformable models including
sub-pixel accuracy and production of non-intersecting curves or surfaces.
Moreover, since the topology-preserving constraint is enforced efficiently
through local computations, the resulting algorithm incurs only nominal
computational overhead over standard geometric deformable models.

**Introduction: **Active
contour and surface models, also called deformable models, have become
one of the most widely used tools in image segmentation, shape modeling
and visual tracking. Deformable models are broadly classified as either
*parametric deformable models* (PDMs) or *geometric deformable
models* (GDMs) according to their representation and implementation.
In particular, PDM contours are represented explicitly as parameterized
curves or surfaces that evolve in a Lagrangian fashion. GDM contours,
on the other hand, are embeded implicitly as level sets of higher-dimensional
level set functions, and evolve according to an Eulerian formulation.

GDMs have several advantages over PDMs,
which include computational stability (e.g, not suffering from the self-intersection
problem), independence of contour parameterization, straightforward application
in higher dimensions, and topological flexibility. However, the topological
flexibility of GDMs can turn into a liability in applications where the
topology of the sought object is known and the resulting deformable model
should conform to this topology constraint. One such application that
motivated this work is the human brain mapping. The human cortex is known
to have a spherical topology, thus any *correct* cortical surface
reconstruction algorithm should produce cortical surfaces with this spherical
topology. The topology constraint prevents traditional GDMs from being
used in such applications, and PDMs are often applied. However, PDMs suffer
from the self-intersection problem, the detection and prevention of which
is also computationally demanding.

Clearly there is a need for geometric
deformable mdoels that enforce a topological constraint. In this project,
we develop such a topology preserving mechanism for GDMs, which we call
the *topology preserving level set method*. The resulting *topology-preserving
geometric deformable model*s (TGDMs) guarantee that the final contour
has exactly the same topology as the initialization, while keeping all
the other useful features of GDMs like subpixel accuracy, free of self-intersection,
and easy of implementation.

**Method: **The
design of the topology preservation mechanism is based on the observation
that implicit contour (zero level set of the level set function) is homeomorphic
to the boundary of the digital object delineated by the level set function
on the computational lattice. As shown in Fig. 1(a), the digital object
simply consists of all grid nodes (*black points*) with a non-positive
level set function value. As a result, the topology change of the implicit
contour is directly correlated to the sign change of the level set function
at a grid point. However, not every sign change of the level set function
would lead to topology change of its zero level set. Based on some digital
topology theory, we conclude that the zero level set changes topology
if and only if the level set function changes sign at a what-so-called
*non-simple* point. As an example, the gray point in Fig. 1(c) is
a non-simple point, and the sign change at this point leads to splitting
of the original contour. The gray point in Fig. 1(b) is a simple point,
and the implicit contour maintains the original topology when passing
over this point. Thus, to maintain the topology of the zero level set
(the implicit contour), we prevent the level set function from changing
sign at non-simple points during its evolution. We call the topology-constrained
level set implementation the topology-preserving level set method (TLSM).
Any standard geometric deformable model (SGDM) can then be converted to
a topology-preserving one (TGDM) when implemented using TLSM.

The implementation of TLSM follows the traditional narrow-band implementation of level set method. The only modification is the extra simple point criterion check whenever the level set function is going to change sign. The simple point check requires the storage of a binary-values indicator function defined on the computational grid to keep track of the dynamically changing digital object. Whether a point is simple or not depends only on the configuration of its 8-neighbors in 2D and 26-neighbors in 3D. Thus, the simple point criterion check can be implemented by look-up table, which incurs little extra computational cost.

The design and implementation of TLSM simulates the gradient-descent-with-bending algorithm in optimization theory, and guanrantees its convergence to a constrained (local) optimum.

After the level set evolution converges,
or at any intermediate step, the implicit contour can be extracted from
the level set function using a *connectivity-consistent* Marching
Cubes (or Marching Squares in 2D) isocontour algorithm.

**Results: **
Several experimental results are presented
here to demonstrate the success of TGDMs and illustrate their potential
applications.

The first experiment compares a standard geometric deformable model (SGDM), a topology-preserving geometric deformable model (TGDM), and a parametric deformable model (PDM) using a simple object and identical initialization. It is shown that SGDM changes topology twice and TGDM does not change its topology while both converge to the desired object. PDM, on the other hand, is beset early on with self intersections and will not converge to the correct object.

The second experiment compares SGDM and TGDM on a simple object with a more complicated initialization. It demonstrates that TGDM does not get stuck in an undesirable configuration while maintaining the correct topology.

This experiment demonstrates the behavior of SGDM and TGDM on a cartoon picture of a human hand. In this case, SGDM splits because of a touching boundary between two fingers, creating the wrong topology for the boundary of a hand. TGDM, however, maintains the topology of the initial curve and provides a better segmentation.

We also applied TGDM for the reconstruction of cortical surfaces from MRI brain images, and compared the result with both PDM and SGDM. All three deformable models produced the same accuracy. However, the PDM causes self-intersection of the surface mesh (a 2D slice is shown in the middle figure below). The SGDM results always has many handles. TGDM automatically prevents the self-intersection (shown in the right figure below), and produces surface meshes topologically equivalent to the surface of a sphere. Hence, TGDM is the only model that produced both accurate and legal cortical surface reconstructions.

**Conclusion:** We
have developed a novel topology-preserving level set method and from which
we derived a new class of geometric deformable models where the topology
of the implicit curves or surfaces is preserved throughout the deformation.
The topology enforcement and automatic production of non-self-intersecting
contours makes TGDM a valuable tool for many segmentation problems, a
successful example of which being the cortical surface reconstruction
from MRI brain images.

**Acknowledgment: **This
work is supported in part by NSF/ERC Grant CISST9731748 and in part by
NIH/NINDS Grant R01NS37747.

**Publications: **

X. Han, C. Xu, and J. L. Prince,
"A topology preserving deformable model using level set," in *Proc.
IEEE Conf. CVPR 2001*, vol. II, pages 765--770, Kauai, HI, Dec 2001.

X. Han, C. Xu, D. Tosun, and J. L.
Prince, "Cortical surface reconstruction using a topology preserving geometric
deformable model," in *Proc. 5th IEEE Workshop MMBIA 2001*, pages
213--220, Kauai, HI, Dec 2001.

X. Han, C. Xu, and J.L. Prince, "A
topology preserving geometric deformable model and its application in
brain cortical surface reconstruction," in* Geometric Level Set
Methods in Imaging, Vision, and Graphics*, S. Osher and N. Paragios,
Eds. Springer Verlag, 2003.

X. Han, C. Xu, and J.L. Prince, "A
topology preserving level set method for geometric deformable models,"
*IEEE Trans. PAMI*, 25(6):755-768, 2003.