From IACL
Jump to: navigation, search

Topology Preserving Geometric Deformable Models

Xiao Han, Chenyang Xu and Jerry L. Prince



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 models (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.