29 research outputs found
Building Morphological Representations for 2D and 3D Scalar Fields
No full textAscending and descending Morse complexes, defined by the critical points and integral lines of a scalar field f defined on a manifold domain D, induce a subdivision of D into regions of uniform gradient flow, and thus provide a compact description of the morphology of f on D. We propose a dimension-independent representation for the ascending and descending Morse complexes, and we describe a data structure which assumes a discrete representation of the field as a simplicial mesh, that we call the incidence-based data structure. We present algorithms for building such data structure for 2D and 3D scalar fields, which make use of a watershed approach to compute the cells of the Morse decompositions
Dimension-Independent Simplification and Multi-Resolution Representation of Morse Complexes
No full text
Disambiguating flat spots in discrete scalar fields
No full textWe consider 2D scalar fields sampled on a regular grid. When the gradient is low relative to the resolution of the dataset’s range, the signal may contain flat spots: connected areas where all points share the same value. Flat spots hinder certain analyses, such as topological characterization or drainage network computations. We present an algorithm to determine a symbolic slope inside flat spots and consistently place a minimal set of critical points, in a way that is less biased than state-of-the-art methods. We present experimental results on both synthetic and real data, demonstrating how our method provides a more plausible positioning of critical points and a better recovery of the Morse–Smale complex
Topologically-consistent simplification of discrete Morse complex
No full textWe address the problem of simplifying Morse–Smale complexes computed on volume datasets based on discrete Morse theory. Two approaches have been proposed in the literature based on a graph representation of the Morse–Smale complex (explicit approach) and on the encoding of the discrete Morse gradient (implicit approach). It has been shown that this latter can generate topologically-inconsistent representations of the Morse–Smale complex with respect to those computed through the explicit approach. We propose a new simplification algorithm that creates topologically-consistent Morse–Smale complexes and works both with the explicit and the implicit representations. We prove the correctness of our simplification approach, implement it on volume data sets described as unstructured tetrahedral meshes and evaluate its simplification power with respect to the usual Morse simplification algorithm
Efficient computation of simplicial homology through acyclic matching
No full textWe consider the problem of efficiently computing homology with Z coefficients as well as homology generators for simplicial complexes of arbitrary dimension. We analyze, compare and discuss the equivalence of different methods based on combining reductions, co reductions and discrete Morse theory. We show that the combination of these methods produces theoretically sound approaches which are mutually equivalent. One of these methods has been implemented for simplicial complexes by using a compact data structure for representing the complex and a compact encoding of the discrete Morse gradient. We present experimental results and discuss further developments
Computing discrete Morse complexes from simplicial complexes
No full textWe consider the problem of efficiently computing a discrete Morse complex on simplicial complexes of arbitrary dimension and very large size. Based on a common graph-based formalism, we analyze existing data structures for simplicial complexes, and we define an efficient encoding for the discrete Morse gradient on the most compact of such representations. We theoretically compare methods based on reductions and coreductions for computing a discrete Morse gradient, proving that the combination of reductions and coreductions produces new mutually equivalent approaches. We design and implement a new algorithm for computing a discrete Morse complex on simplicial complexes. We show that our approach scales very well with the size and the dimension of the simplicial complex also through comparisons with the only existing public-domain algorithm for discrete Morse complex computation. We discuss applications to the computation of multi-parameter persistent homology and of extremum graphs for visualization of time-varying 3D scalar fields
A discrete Morse-based approach to multivariate data analysis
No full textMultivariate data are becoming more and more popular in several
applications, including physics, chemistry, medicine, geography,
etc. A multivariate dataset is represented by a cell complex and a
vector-valued function defined on the complex vertices. The major
challenge arising when dealing with multivariate data is to obtain
concise and effective visualizations. The usability of common visual
elements (e.g., color, shape, size) deteriorates when the number
of variables increases. Here, we consider Discrete Morse Theory
(DMT) [Forman 1998] for computing a discrete gradient field on a
multivariate dataset. We propose a new algorithm, well suited for
parallel and distribute implementations. We discuss the importance
of obtaining the discrete gradient as a compact representation of the
original complex to be involved in the computation of multidimensional
persistent homology. Moreover, the discrete gradient field
that we obtain is at the basis of a visualization tool for capturing the
mutual relationships among the different functions of the dataset
Topological modifications and hierarchical representation of cell complexes in arbitrary dimensions
No full textWe propose a set of atomic modeling operators for simplifying and refining cell complexes in arbitrarydimensions. Such operators either preserve the homology of the cell complex, or they modify it in a con-trolled way. We show that such operators form a minimally complete basis for updating cell complexes,and we compare them with various operators previously proposed in the literature. Based on the newoperators, we define a hierarchical model for cell complexes, that we call aHierarchical Cell Complex(HCC), and we discuss its properties. AnHCCimplicitly encodes a virtually continuous set of complexesobtained from the original complex through the application of our operators. Then, we describe theimplementation of a version of theHCCbased on the subset of the proposed modeling operators whichpreserve homology. We apply the homology-preservingHCCto enhance the efficiency in extractinghomology generators at different resolutions. To this aim, we propose an algorithm which computeshomology generators on the coarsest representation of the original complex, and uses the hierarchicalmodel to propagate them to complexes at any intermediate resolution, and we prove its correctness.Finally, we present experimental results showing the efficiency and effectiveness of the proposedapproac
