Morphological Modeling of Terrains and Volume Data | springerprofessional.de

Springer Professional

nach oben

2014 | Buch

Kapitel lesen Erstes Kapitel lesen

Morphological Modeling of Terrains and Volume Data

verfasst von: Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Verlag: Springer New York

Buchreihe : SpringerBriefs in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book describes the mathematical background behind discrete approaches to morphological analysis of scalar fields, with a focus on Morse theory and on the discrete theories due to Banchoff and Forman. The algorithms and data structures presented are used for terrain modeling and analysis, molecular shape analysis, and for analysis or visualization of sensor and simulation 3D data sets. It covers a variety of application domains including geography, geology, environmental sciences, medicine and biology. The authors classify the different approaches to morphological analysis which are all based on the construction of Morse or Morse-Smale decompositions. They describe algorithms for computing such decompositions for both 2D and 3D scalar fields, including those based on the discrete watershed transform. Also addressed are recent developments in the research on morphological shape analysis, such as simplification operators for Morse and Morse-Smale complexes and their multi-resolution representation. Designed for professionals and researchers involved with modeling and algorithm analysis, Morphological Modeling of Terrains and Volume Data is a valuable resource. Advanced-level students of computer science, mathematics and geography will also find the content very helpful.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Background

Abstract

In this chapter, we introduce the mathematical structures used to represent scalar fields and their morphology in the smooth and in the discrete cases. We provide the basic mathematical concepts, such as manifold, cell complex, regular grid, and simplicial complex (Sect. 1.1). We introduce discrete models for scalar fields defined at finite sets of points, such as regular models and simplicial models (Sect. 1.2). We present the basic notions of Morse theory, which provides a description of the morphology of functions in the smooth case (Sect. 1.3), and the watershed transform in the smooth case, which is an alternative framework to Morse theory (Sect. 1.4). We discuss the two existing approaches for extending the results of Morse theory to the discrete case: Banchoff’s piecewise-linear Morse theory (Sect. 1.5) and Forman’s discrete Morse theory (Sect. 1.6).

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Chapter 2. Morphology Computation Algorithms: Generalities

Abstract

We propose different criteria for classifying algorithms for morphology computation (Sect. 2.1). Such criteria are based on the dimension of the input scalar field (2D, 3D, or dimension-independent), on the input format (simplicial models, regular grids), on the output information (ascending or descending Morse complex, Morse-Smale complex), on the format of the output information, and on the algorithmic approach applied. This last criterion leads to a classification into boundary-based and region-growing algorithms (coming from Banchoff’s piecewise linear Morse theory), algorithms based on the watershed transform, and based on Forman’s discrete Morse theory. We will use this classification to organize the survey provided in the remainder of the book. We discuss methods to compute the critical points of the scalar field, which is a basic subcomponent of most morphology computation algorithms (Sect. 2.2), and solutions for dealing with the domain boundary (Sect. 2.3), and with plateaus (Sect. 2.4), which are common issues when applying such algorithms to real-world data.

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Chapter 3. Boundary-Based and Region-Growing Algorithms

Abstract

This chapter describes two approaches to morphology computation, which are dimension-specific: the boundary-based and the region-growing approach. Such approaches have been developed in the context of Geographic Information Systems (GISs), initially for terrains, and later for three-dimensional scalar fields for applications to volume data visualization. First, we review boundary-based methods, which are based on the idea of building the boundary lines (in 2D) or boundary surfaces (in 3D) of the Morse cells (Sect. 3.1); Then, we review region-growing algorithms, which are based on the idea of growing a cell of the descending or ascending Morse complex associated with a minimum or maximum by starting from such a point as a seed (Sect. 3.2).

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Chapter 4. Watershed Algorithms

Abstract

The watershed approach has been developed in image processing for segmenting grey-level images, i.e., two-dimensional scalar fields modeled as regular grids. It directly extends to higher dimensions. Few watershed algorithms are defined for simplicial models. In general, the input for a watershed algorithm is a graph describing the connectivity structure of either the input mesh (i.e., nodes correspond to vertices), or of its dual mesh (i.e., nodes correspond to cells of maximum dimension), with field values associated with its nodes. The output is a classification of the graph nodes as belonging to the catchment basin (ascending cell) of a certain minimum, or as belonging to the boundary between catchment basins. In this chapter, we present the main approaches to watershed computation, namely, by simulated immersion (Sect. 4.1), by topographic distance (Sect. 4.2), and by rain falling (Sect. 4.3), as well as a comparison among the different approaches (Sect. 4.4).

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Chapter 5. A Combinatorial Approach Based on Forman Theory

Abstract

In this chapter, we review algorithms based on Forman theory. These algorithms are combinatorial in nature and, thus, dimension-independent. Forman-based algorithms start from a Forman gradient vector field computed as a preliminary step. We discuss how to encode a Forman gradient over irregular simplicial complexes, by taking into account the relation between the input simplicial complex and its dual, and between the descending and ascending Morse complexes (Sect. 5.1). We describe the main algorithms for computing a Forman gradient on 2D and 3D scalar fields (Sect. 5.3). Finally we present algorithms which, given a Forman gradient, extract the collection of cells of the ascending and descending Morse complexes, the Morse-Smale cells, or the vertices and edges of the Morse-Smale complex (Sect. 5.4).

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Chapter 6. Simplification and Multi-Resolution Representations

Abstract

Simplification of Morse and Morse-Smale complexes is an important issue to eliminate noise and reduce over-segmentation. Moreover, different users may have different requirements in terms of degree of simplification, which usually vary over time and location within the field domain. Thus, a multi-resolution representation of morphology is critical for interactive analysis and exploration of data. In this chapter, we first describe and compare simplification operators on Morse functions and Morse and Morse-Smale complexes (Sect. 6.1). We then present multi-resolution models for the morphology of scalar fields (Sect. 6.2), and we specify two models in more detail: the first one providing a multi-resolution description of the combinatorial structure of Morse and Morse Smale complexes in arbitrary dimensions, and the second one addressing the problem of coupling a multi-resolution representation of geometry and of morphology in 2D.

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Chapter 7. Experimental Analysis and Comparisons

Abstract

This chapter presents experimental comparisons of different approaches for morphology computation, and illustrates the use of morphological descriptions in applications. We analyze the different output formats and their mutual relations (Sect. 7.1). After presenting metrics for comparing the results of different algorithms (Sect. 7.2), we compare watershed and Forman-based approaches, i.e., the two dimension-independent methods, by presenting results in the 2D and 3D cases, on data in general position (Sect. 7.3). We compare all approaches in the 2D case with respect to their feasibility and sensitivity to the presence of flat edges (Sect. 7.4). Finally, we present an overview on the use of morphological representations in the applications (Sect. 7.5).

Lidija Čomić, Leila De Floriani, Paola Magillo, Federico Iuricich

Titel: Morphological Modeling of Terrains and Volume Data
verfasst von: Lidija Čomić
Leila De Floriani
Paola Magillo
Federico Iuricich
Copyright-Jahr: 2014
Verlag: Springer New York
Electronic ISBN: 978-1-4939-2149-2
Print ISBN: 978-1-4939-2148-5
DOI: https://doi.org/10.1007/978-1-4939-2149-2

Premium Partner