Morphological Modeling of Terrains and Volume Data


Scalar fields are real-valued functions defined point-wise within a $d$-dimensional domain. They appear in many applications, including physics, chemistry, medicine, geography, etc., and represent real or simulated phenomena characterized by a spatial extension. The most common example are height fields which describe terrains and have been studied extensively in Geographic Information Systems (GISs) and scientific visualization. Scalar fields can also be defined on shapes (which describe the surface of an object in 3D) to represent some point-wise defined property on them (such as curvature). As $d$-dimensional domains are discretized (e.g., as d-dimensional images composed of voxels) and so are shapes (e.g., a surface tessellated as a mesh of triangles), scalar fields defined on them have a discrete representation: usually, field values are associated with the voxels of an image or with the vertices of a mesh. This provides a detailed representation of the scalar field. Thanks to hardware and software development, available data representing both the field and its domain are increasing in size and complexity. On the other hand, a detailed representation is verbose and not suitable to analysis tasks such as recognition and classification. Therefore, the issue arises to switch from representation to description of a scalar field. While a representation provides all details necessary to know the field point-wise, a description is more abstract and has the purpose of showing the main characteristics of the field, such as, for instance, its maxima/minima/saddles and their relative positions. This book focuses on morphological descriptions of scalar fields, mainly in 2D (height fields, or terrains) and 3D (volume data). Specifically, we consider morphological descriptions based on identifying maxima, minima and saddles, finding their influence zones, and encoding their mutual spatial relations. All this is formalized through Morse theory, Morse and Morse-Smale complexes. We provide the mathematical background, which has been formally defined for smooth functions and then transposed into a discrete setting in different ways. We introduce the main algorithmic approaches and their characteristics, and present algorithms for discrete scalar fields in two and three dimensions, and (where possible) in general dimensions. Although morphological descriptions based on Morse and Morse-Smale complexes represent scalar fields in a much more compact way than the initial geometric representation, simplification of these complexes is often necessary. Simplification allows disregarding less meaningful morphological features, or spurious features, due to noise in the data, as well as adapting the level of abstraction of the description to the current application task. Therefore, we present simplification operators which act on the morphological description of a scalar field. The issue of simplification comes along with that of multi-resolution, which requires being able to build a compact model encompassing different levels of detail (corresponding to different degrees of simplification), in such a way that the appropriate level of detail can be extracted on the fly according to user-defined criteria. This book is organized as follows. Chapter 1 contains the necessary mathematical background on Morse theory in the smooth and in the discrete case. Chapter 2 presents a classification of existing algorithms for morphological computation based on different and often orthogonal criteria, where the main criterion is the algorithmic approach they use. Such a criterion identifies boundary-based and region-growing methods (which essentially deal with 2D and 3D scalar fields), watershed-based and methods based on a discrete Morse theory due to Forman (which are dimension-independent). The next three chapters present a survey of algorithms belonging to the first two classes (Chap.3), of watershed-based algorithms (Chap.4) and of Forman-based algorithms (Chap.5). Chapter 6 considers the issues related to simplification and multi-resolution. Finally, Chap.7 presents experimental comparisons and draw concluding remarks.