Topological Methods in Data Analysis and Visualization IV

This is a survey article on singularity theory of differentiable maps with applications to visualization of scientific data in mind. Special emphasis is put on Morse theory on manifolds with boundary, singular fibers of multi-fields, their Reeb spaces, and their topological transitions.

Many scientific applications deal with data from a multitude of different sources, e.g., measurements, imaging and simulations. Each source provides an additional perspective on the phenomenon of interest, but also comes with specific limitations, e.g. regarding accuracy, spatial and temporal availability. Effectively combining and analyzing such multimodal and partially incomplete data of limited accuracy in an integrated way is challenging. In this work, we outline an approach for an integrated analysis and visualization of the atmospheric impact of volcano eruptions. The data sets comprise observation and imaging data from satellites as well as results from numerical particle simulations. To analyze the clouds from the volcano eruption in the spatiotemporal domain we apply topological methods. We show that topology-related extremal structures of the data support clustering and comparison. We further discuss the robustness of those methods with respect to different properties of the data and different parameter setups. Finally we outline open challenges for the effective integrated visualization using topological methods.

For the scientific visualization and analysis of univariate (scalar) fields several topological approaches like contour trees and Reeb graphs were studied and compared to each other some time ago. In recent years, some of those approaches were generalized to multivariate fields. Among others, data structures like the joint contour net (JCN) and the Pareto set were introduced and improved in subsequent work. However, both methods utilized individual data sets as test cases for their proof-of-concept sections and partially lacked a complete comparison to other multivariate approaches. Hence, to better understand the relationship between those two data structures and to gain insights into general multivariate topology, we present a deeper comparison of JCNs and Pareto sets in which we integrate data sets applied in the original JCN and Pareto set papers.

Discrete combinatorial optimization problems such as the Traveling Salesman Problem have various applications in science and in everyday life. The complexity of the problem and the effectiveness of search algorithms depend not only on the problem itself but also on the search operator in use. Therefore, investigating search operators and the search landscapes they give rise to is an important field of research. However, a full topological analysis of the landscapes is impossible due to their exponentially growing size. We propose a visualization system that gives a visual intuition about topological properties of the search landscape. We obtain representative samples of the search landscape and its optima by random sampling and by computing the related optima using local search. The distribution and the correlation of this data within the search landscape is visualized with a combination of one and two dimensional visualizations. Using the TSP as an example we illustrate how the visualization supports the understanding and comparison of search landscapes and their complexity.

We introduce a new method that identifies and tracks features in arbitrary dimensions using the merge tree—a structure for identifying topological features based on thresholding in scalar fields. This method analyzes the evolution of features of the function by tracking changes in the merge tree and relates features by matching subtrees between consecutive time steps. Using the time-varying merge tree, we present a structural visualization of the changing function that illustrates both features and their temporal evolution. We demonstrate the utility of our approach by applying it to temporal cluster analysis of high-dimensional point clouds.

Similarity estimation in scalar fields using level set topology has attracted a lot of attention in the recent past. Most existing techniques match parts of contour or merge trees against each other by estimating a best overlap between them. Due to their combinatorial nature, these methods can be computationally expensive or prone to instabilities. In this paper, we use an inexpensive feature descriptor to compare subtrees of merge trees against each other. It is the data histogram of the voxels encompassed by a subtree. A small modification of the merge tree computation algorithm allows for obtaining these histograms very efficiently. Furthermore, the descriptor is robust against instabilities in the merge tree. The method is useful in an interactive environment, where a user can search for all structures similar to an interactively selected one. Our method is conservative in the sense that it finds all similar structures, with the rare occurrence of some false positives. We show with several examples the effectiveness, efficiency and accuracy of our method.

Ab initio molecular dynamics (AIMD) simulations are increasingly useful in modeling, optimizing and synthesizing materials in energy sciences. In solving Schrödinger’s equation, they generate the electronic structure of the simulated atoms as a scalar field. However, methods for analyzing these volume data are not yet common in molecular visualization. The Morse-Smale complex is a proven, versatile tool for topological analysis of scalar fields. In this paper, we apply the discrete Morse-Smale complex to analysis of first-principles battery materials simulations. We consider a carbon nanosphere structure used in battery materials research, and employ Morse-Smale decomposition to determine the possible lithium ion diffusion paths within that structure. Our approach is novel in that it uses the wavefunction itself as opposed distance fields, and that we analyze the 1-skeleton of the Morse-Smale complex to reconstruct our diffusion paths. Furthermore, it is the first application where specific motifs in the graph structure of the complete 1-skeleton define features, namely carbon rings with specific valence. We compare our analysis of DFT data with that of a distance field approximation, and discuss implications on larger classical molecular dynamics simulations.

Morse-Smale complexes have been proposed to visualize topological features of scalar fields defined on manifold domains. Herein, three main problems have been addressed in the past: (a) efficient computation of the initial combinatorial structure connecting the critical points; (b) simplification of these combinatorial structures; (c) reconstruction of a scalar field in accordance to the simplified Morse-Smale complex. The present paper faces the third problem by proposing a novel approach for computing a scalar field coherent with a given simplified MS complex that privileges the use of piecewise polynomial functions. Based on techniques borrowed from shape preserving design in Computer Aided Geometric Design, our method constructs the surface cell by cell using piecewise polynomial curves and surfaces. The benefit and limitations of using polynomials for reconstruction surfaces from topological data are presented in this paper.

An escape map is the partial mapping from seed points to exit points of streamlines in a bounded domain. The escape map is piecewise continuous, and a topological segmentation of the domain boundary yields the regions and curve segments on which it is continuous. Escape maps have recently been introduced in the context of studying the connectivity of coronal holes. Computation of escape maps faces the problem of exponentially diverging streamlines, where standard adaptive streamsurface methods can fail. As a tool to detect such places and to guide escape map computation, a technique based on isoclines has recently been proposed (Machado et al., IEEE Trans. Vis. Comput. Graph. 20(12):2604–2613, 2014). We show in this paper that, in the case of a divergence-free vector field, boundary switch connectors can be used as a purely topological alternative, which to the best of our knowledge is the first practical application of boundary switch connectors. We provide a systematic approach to the topological segmentation of 3D domain boundaries for divergence-free vector fields. Finally, we explore an alternative approach based on streamtubes and targeted at robustness in escape map computation. Simulation results as well as a synthetic vector field are used for validation.

This paper studies the discontinuity in the behavior of neighboring integral curves. The discontinuity is measured by a number of selected attributes of integral curves. A variety of attribute fields are defined. The attribute value at any given spatio-temporal point in these fields is assigned by the attribute of the integral curve that passes through this point. This encodes the global behavior of integral curves into a number of scalar fields in an Eulerian fashion, which differs from the previous pathline attribute approach that focuses on the discrete representation of individual pathlines. With this representation, the discontinuity of the integral curve behavior now corresponds to locations in the derived fields where the attribute values have sharp gradients. We show that based on the selected attributes, the extracted discontinuity from the corresponding attribute fields may relate to a number of flow features, such as LCS, vortices, and cusp-like seeding curves. In addition, we study the correlations among different attributes via their pairwise scatter plots. We also study the behavior of the combined attribute fields to understand the spatial correlation that cannot be revealed by the scatter plots. Finally, we integrate our attribute field computation and their discontinuity detection into an interactive system to guide the exploration of various 2D flows.

In our paper, we discuss generalized vector field decompositions that mainly have been derived from the classical Helmholtz-Hodge-decomposition. The ability to decompose a field into a kernel and a rest respectively to an arbitrary vector-valued linear differential operator allows us to construct decompositions of either toroidal flows or flows obeying differential equations of second (or even fractional) order and a rest. The algorithm is based on the fast Fourier transform and guarantees a rapid processing and an implementation that can be directly derived from the spectral simplifications concerning differentiation used in mathematics.

3D symmetric tensor fields have a wide range of applications in science and engineering. The topology of a symmetric tensor field, which consists of degenerate curves, can provide critical insights into the behaviors of the tensor fields. Existing methods to extract degenerate curves make some assumptions of the maximum number of degenerate curves in a cell without validating this bound. In this paper, we study the maximum number of degenerate curves in a linear tensor field to contribute to accurate and efficient extraction methods.

Lagrangian coherent structures provide insight into unsteady fluid flow, but their construction has posed many challenges. These structures can be characterized as ridges of a field, but their local definition utilizes an ambiguous eigenvector direction that can point in one of two directions, and its ambiguity can lead to noise and other problems. We overcome these issues with an application of a global ridge definition, applied using the hierarchical watershed transformation. We show results on a mathematical flow model and a simulated vascular flow dataset indicating the watershed method produces less noisy structures.

Vector Field Topology describes the asymptotic behavior of a flow in a vector field, i.e., the behavior for an integration time converging to infinity. For some applications, a segmentation of the flow in areas of similar behavior for a finite integration time is desired. We introduce an approach for a finite-time segmentation of a steady 2D vector field which avoids the systematic evaluation of the flow map in the whole flow domain. Instead, we consider the separatrices of the topological skeleton and provide them with additional information on how the separation evolves at each point with ongoing integration time. We analyze this behavior and its distribution along a separatrix, and we provide a visual encoding for it. The result is an augmented topological skeleton. We demonstrate the approach on several artificial and simulated vector fields.

Transfer operator-based approaches have been successfully applied to the extraction of coherent features in flows. Transfer operators describe the evolution of densities under the action of the flow. They can be efficiently approximated within a set-oriented numerical framework and spectral properties of the resulting stochastic matrices are used to extract finite-time coherent sets. Also finite-time entropy, a density-based stretching quantity similar to finite-time Lyapunov exponents, is conveniently approximated by means of the discretized transfer operator. Transfer operator-based computational methods are purely probabilistic and derivative-free. Therefore, they can also be applied in settings where derivatives of the flow map are hardly accessible. In this paper, we summarize the theory and numerics behind the transfer operator approach and then introduce a straightforward extension, which allows us to study coherent structures in complex flows on triangulated surfaces. We illustrate our general computational framework with the well-known periodically driven double-gyre flow. To demonstrate the applicability of the approach for complex flows, we consider an approximation of the surface ocean flow, obtained by a numerical solution of the incompressible surface Navier-Stokes equation in a complicated geometry on the sphere.

Threshold-based feature definitions remain one of the most widely used and most intuitive choice in a wide range of scientific areas. However, it is well known that in many applications selecting a single optimal threshold is difficult or even impossible. Common examples of this are quantities with locally exponential behavior like the scalar dissipation rate in turbulent combustion simulations or indicator functions, such as, vorticity or delta popular in defining vortices. In these cases, local thresholds defined, for example, using contour trees can provide significantly better results, but typically require a data analysis expert to create and use. We present the ADAPT framework a new open source code that transforms a given scalar field such that global thresholds in the resulting field correspond to a variety of local thresholds in the original data. Consequently, the resulting field can be easily processed using any of the existing tool chains and provides scientists easy access to a wide variety of more advanced feature definitions. Currently, the package provides two techniques to define local thresholds: The relevance transform originally developed for combustion analysis and a model based fit initially designed to extract eddies in global ocean simulations. Furthermore, it provides an extendable API to easily add other transforms.

The Morse-Smale complex is a topological data structure that represents the behavior of the gradient of an input scalar field. Recent years have witnessed a significant number of applications that use this data structure for visualization and analysis of data from various scientific domains. However, these applications have required significant expertise in the implementation of algorithms. This potentially makes such analysis inaccessible to a large audience. In this paper we present open source software modules for the computation, analysis, and visualization of scientific data using the Morse-Smale complex. The modules, named pymstri and pyms3d, are intended for domains represented using 2D triangle meshes and 3D structured grids respectively. The software is designed to significantly reduce the effort required to use Morse-Smale complex based analysis. Also, the software leverages modern multi-core CPU and GPU architectures for computational efficiency. We demonstrate the usefulness via a case study to visually analyze and interactively segment the eye of the Hurricane Isabel simulation dataset. In particular, we highlight the ability to couple the visual analysis and the computation with ParaView, a popular general purpose visualization tool. The code is available at the project website http://​vgl.​csa.​iisc.​ac.​in/​mscomplex.

Merge trees are topological structures that record changes in super-level set topology of a scalar function. They encapsulate a wide range of threshold based features which can be extracted for analysis and visualization. Several distributed and parallel algorithms for computing merge trees have been proposed in the past, but they are restricted to simplicial complexes or regular grids. In this paper, we present an algorithm for the distributed computation of merge trees on CW-complexes. The conditions on the CW-complex required for the computation of the merge tree are discussed alongside a proof of correctness.

We design a fast algorithm for computing the fundamental group of the complement to any knotted polygonal graph in 3-space. A polygonal graph consists of straight segments and is given by sequences of vertices along edge-paths. This polygonal model is motivated by protein backbones described in the Protein Data Bank by 3D positions of atoms. Our KGG algorithm simplifies a knotted graph and computes a short presentation of the Knotted Graph Group containing powerful invariants for classifying graphs up to isotopy. We use only a reduced plane diagram without building a large complex representing the complement of a graph in 3-space.