Advances in Imaging and Electron Physics

1. Auflage 2014
ISBN: 978-0-12-800319-0
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, Band Volume 181, 240 Seiten

Reihe: Advances in Imaging and Electron Physics

Advances in Imaging and Electron Physics merges two long-running serials--Advances in Electronics and Electron Physics and Advances in Optical and Electron Microscopy. This series features extended articles on the physics of electron devices (especially semiconductor devices), particle optics at high and low energies, microlithography, image science and digital image processing, electromagnetic wave propagation, electron microscopy, and the computing methods used in all these domains. - Contributions from leading authorities - Informs and updates on all the latest developments in the field

Autoren/Hrsg.

Leseproben

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 O of all vertices of the octree leaf cells. The location of a point P ? O 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 ? O:

• EDGE (E)-neighborhood of x: NE(x) = {x' ? O: x and x' are the two vertices of an edge of a leaf cell}

• SQUARE (S)-neighborhood of x: Ns(x) = {x' ? O: x and x' are two of the four vertices of a square of a leaf cell}

• CUBE (C)-neighborhood of x: NC(x) = {x' ? O: 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,...