Chapter One

Octree Grid Topology-Preserving Geometric Deformable Model (OTGDM)

Ying Bai1, Xiao Han2, and Jerry L. Prince3 1HeartFlow Inc., Redwood City, CA, USA 2Electa Inc., Maryland Heights, MO, USA 3Johns Hopkins University, Baltimore, MD, USA

Abstract

Topology-preserving geometric deformable models (TGDMs) are used to segment objects that have a known topology. Their accuracy is inherently limited by the resolution of the underlying computational grid. Although this can be overcome by using fine-resolution grids, both the computational cost and the size of the resulting surface increase dramatically. In this article, we present a new octree grid topology-preserving deformable model (OTGDM). OTGDMs refine grid resolution locally, thus maintaining computational efficiency and keep the surface mesh size manageable. Topology preservation is achieved by adopting concepts from a digital topology framework on octree grids that we have proposed previously. Details of OTGDM implementation are discussed, including grid generation, model initialization, numerical schemes, and final surface model extraction. Experiments on both mathematical phantoms and real medical images are used to demonstrate the advantages of OTGDMs.

Keywords

Digital topology; adaptive grid; octree; deformable model; isosurface; image segmentation

1. Introduction

Front propagation using level set methods (Osher & Sethian, 1988) and their application in deformable models—geometric deformable models (GDMs; Caselles, Kimmel, and Sapiro, 1997; Malladi & Sethian 1995; Yezzi et al., 1997) are well established and extensively used in image segmentation. Topology-preserving geometric deformable models (TGDMs; Han, Xu, and Prince, 2003; Han et al., 2004; Sundaramoorthi & Yezzi 2005) were introduced to provide the ability to maintain the topology of segmented objects while preserving the other benefits of GDMs. For example, in medical imaging, many organs to be segmented have boundary topologies equivalent to that of a sphere. While many applications, such as visualization and quantification, may not require topologically correct segmentations, there are some applications—e.g., surface mapping and flattening and shape atlas generation—that cannot be achieved without having the correct topology of the segmented objects. Figure 1 shows examples of segmented geometric models with simple topologies, but convoluted shapes. In these cases, segmentation methods without topology modeling are likely to produce results with incorrect topologies. Figure 1 Geometric models with simple topologies. (See the color plate.) GDMs represent the evolving surface implicitly as a level set of a higher-dimensional function. The resolution of the implicit surface is therefore restricted by the resolution of the sampling grid that defines the level set function, as demonstrated in Figures 2(a-c). Accurate representation of shapes with fine anatomical details (e.g., the folded sulci and gyri on the cortex) requires the use of a fine resolution grid. This dramatically increases the computation time of GDMs and produces surface meshes with prohibitive size, especially on highly resolved 3D medical images. Adaptive grid techniques (Terzopoulos & Vasilescu, 1991; Milne, 1995; Sussman et al., 1999; Xu, Thompson, and Toga, 2004; Droske, 2001; Sochnikov & Efrima, 2003) address the resolution problem of GDMs by locally refining the sampling grid in order to resolve details and concentrate computational efforts where more accuracy is needed (as shown in Figure 2(d)). Figure 2 Implicit surface resolution: the blue contour is the truth contour, and the red contour is the implicit contour embedded in each sampling grid. (a) A coarse resolution grid cannot resolve contour details. (b) A refined grid represents the truth contour better. (c) A more refined grid provides a more accurate representation. (d) An adaptive grid with local refinement provides an accurate and efficient multiresolution shape representation. (See the color plate.) Extending TGDM to adaptive grids is not trivial. Besides numerical schemes to implement level set methods on adaptive grids, we also need to define digital connectivity rules for adaptive grids. Without such rules, it is difficult to guarantee homeomorphisms between the implicit surfaces and the corresponding boundaries of segmented objects on an adaptive grid. Digital connectivity rules for adaptive grids are also necessary to design a topology-preserving level set method on adaptive grids. On regular grids, TGDM maintains the topology of the implicit surface by controlling the topology of the corresponding binary object segmentation. This is achieved by applying the simple point criterion (Bertrand, 1994a,b) from the theory of digital topology (Kong & Rosenfeld, 1989), preventing the level set function from changing sign at nonsimple points. It means that we need to characterize what “simple points” on adaptive grids are. In our previous work (Bai, Han, and Prince, 2009), we defined and proved a digital topology framework on adaptive octree grids, which provides solutions to the above mentioned challenges. This chapter presents a topology-preserving level set method on the adaptive octree grids. In section 2, we first review the digital topology framework for octree grids that we proposed in Bai, Han, and Prince (2009). In section 3, we present an octree grid topology-preserving GDM (OTGDM). Several experiments are shown in section 4 to demonstrate the performance of OTGDMs on both computational phantoms and real medical images.

2. Digital Topology on Adaptive Octree Grids

In this section, we summarize the digital topology framework on adaptive octree grids. We start with basic notations and definitions of digital topology on octree grids and then we introduce the concept of valid octree grid (VOG), which resolves ambiguities in defining object topology on octree grids, Finally, we revisit the simple point characterization on a VOG.

2.1. Basic Concepts

An octree grid is a hierarchical cartesian grid. A cell is the basic unit of an octree grid; it is a cube with 6 faces, 12 edges, and 8 vertices. Each cell can be divided into eight child cells. The root cell represents the entire domain and is at level 0. The resolution level of a cell is defined by starting from the root cell and adding one for each refinement. A leaf cell is a cell that has no child cells. The domain of a digital image defined on an octree grid is the set Ω of all vertices of the octree leaf cells. The location of a point P ∈ Ω is given by an integer-valued triplet (x,y,z), which also represents its position on the underlying finest-resolution uniform grid. On uniform grids, the concept of neighborhood is defined using Euclidean distance. This is not applicable to octree grids, because leaf cells of octree grids have different sizes. Instead we use the following definitions. Three types of neighborhoods are defined for each point x ∈ Ω: • EDGE (E)-neighborhood of x: NE(x) = {x′ ∈ Ω: x and x′ are the two vertices of an edge of a leaf cell} • SQUARE (S)-neighborhood of x: Ns(x) = {x′ ∈ Ω: x and x′ are two of the four vertices of a square of a leaf cell} • CUBE (C)-neighborhood of x: NC(x) = {x′ ∈ Ω: x and x′ are two of the eight vertices of a cube of a leaf cell} We define the E-neighbors of x to be NE (x), the S-neighbors of x to be NS(x)\NE(x), and the C-neighbors of x to be NC(x)\NS(x). See Figure 3 for illustrations of these neighborhoods on both regular and octree grids. Figure 3 Three-dimensional (3D) neighborhoods on an octree grid. In each example, the gray circle is the root point; the black squares denote the E-neighbors; the white squares denote the S-neighbors; and the gray squares denote the C-neighbors. (a)-(c) are single-level neighborhoods; (d) is a multilevel neighborhood. Note that the E-connected,...