Skip to main content
main-content
Top

About this book

This book presents contributions on topics ranging from novel applications of topological analysis for particular problems, through studies of the effectiveness of modern topological methods, algorithmic improvements on existing methods, and parallel computation of topological structures, all the way to mathematical topologies not previously applied to data analysis.

Topological methods are broadly recognized as valuable tools for analyzing the ever-increasing flood of data generated by simulation or acquisition. This is particularly the case in scientific visualization, where the data sets have long since surpassed the ability of the human mind to absorb every single byte of data.

The biannual TopoInVis workshop has supported researchers in this area for a decade, and continues to serve as a vital forum for the presentation and discussion of novel results in applications in the area, creating a platform to disseminate knowledge about such implementations throughout and beyond the community.

The present volume, resulting from the 2015 TopoInVis workshop held in Annweiler, Germany, will appeal to researchers in the fields of scientific visualization and mathematics, domain scientists with an interest in advanced visualization methods, and developers of visualization software systems.

Table of Contents

Frontmatter

Topology-Based Analysis of Multi-Variate Data Sets

Frontmatter

Theory of Singular Fibers and Reeb Spaces for Visualization

Abstract
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.
Osamu Saeki

Topology-Based Analysis for Multimodal Atmospheric Data of Volcano Eruptions

Abstract
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.
Alexander Kuhn, Wito Engelke, Markus Flatken, Hans-Christian Hege, Ingrid Hotz

A Comparison of Joint Contour Nets and Pareto Sets

Abstract
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.
Lars Huettenberger, Christian Heine, Christoph Garth

Topological Techniques for High-Dimensional Data

Frontmatter

Visualizing Topological Properties of the Search Landscape of Combinatorial Optimization Problems

Abstract
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.
Sebastian Volke, Dirk Zeckzer, Martin Middendorf, Gerik Scheuermann

Computing and Visualizing Time-Varying Merge Trees for High-Dimensional Data

Abstract
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.
Patrick Oesterling, Christian Heine, Gunther H. Weber, Dmitriy Morozov, Gerik Scheuermann

Agreement Analysis of Quality Measures for Dimensionality Reduction

Abstract
High-dimensional data sets commonly occur in various application domains. They are often analysed using dimensionality reduction methods, such as principal component analysis or multidimensional scaling. To determine the reliability of a particular embedding of a data set, users need to analyse its quality. For this purpose, the literature knows numerous quality measures. Most of these measures concentrate on a single aspect, such as the preservation of relative distances, while others aim to balance multiple aspects, such as intrusions and extrusions in k-neighbourhoods. Faced with multiple quality measures with different ranges and different value distributions, it is challenging to decide which aspects of a data set are preserved best by an embedding. We propose an algorithm based on persistent homology that permits the comparative analysis of different quality measures on a given embedding, regardless of their ranges. Our method ranks quality measures and provides local feedback about which aspects of a data set are preserved by an embedding in certain areas. We demonstrate the use of our technique by analysing quality measures on different embeddings of synthetic and real-world data sets.
Bastian Rieck, Heike Leitte

Scalar Field Topology

Frontmatter

Fast Similarity Search in Scalar Fields using Merging Histograms

Abstract
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.
Himangshu Saikia, Hans-Peter Seidel, Tino Weinkauf

Morse-Smale Analysis of Ion Diffusion in Ab Initio Battery Materials Simulations

Abstract
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.
Attila Gyulassy, Aaron Knoll, Kah Chun Lau, Bei Wang, Peer-Timo Bremer, Michael E. Papka, Larry A. Curtiss, Valerio Pascucci

Piecewise Polynomial Reconstruction of Scalar Fields from Simplified Morse-Smale Complexes

Abstract
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.
Léo Allemand-Giorgis, Georges-Pierre Bonneau, Stefanie Hahmann

Vector and Tensor Field Topology

Frontmatter

Topological Extraction of Escape Maps in Divergence-Free Vector Fields

Abstract
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.
Ronald Peikert, Gustavo Machado, Filip Sadlo

Compute and Visualize Discontinuity Among Neighboring Integral Curves of 2D Vector Fields

Abstract
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.
Lei Zhang, Robert S. Laramee, David Thompson, Adrian Sescu, Guoning Chen

Decomposition of Vector Fields Beyond Problems of First Order and Their Applications

Abstract
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.
Wieland Reich, Mario Hlawitschka, Gerik Scheuermann

Maximum Number of Degenerate Curves in 3D Linear Tensor Fields

Abstract
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.
Yue Zhang, Yu-Jong Tzeng, Eugene Zhang

Coherent Structures

Frontmatter

Hierarchical Watershed Ridges for Visualizing Lagrangian Coherent Structures

Abstract
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.
Mingcheng Chen, John C. Hart, Shawn C. Shadden

Finite Time Steady 2D Vector Field Topology

Abstract
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.
Anke Friederici, Christian Rössl, Holger Theisel

Comparing Finite-Time Lyapunov Exponents in Approximated Vector Fields

Abstract
In the context of fluid mechanics, larger and larger flow fields arise. The analysis of such fields on current work stations is heavily restricted by memory. Approximation limits this problem. In this paper, we discuss the impact of vector field approximation on visualization techniques on the example of Finite-Time Lyapunov Exponent (FTLE) computations. Thereby, we consider the results of three different vector field compression approaches and analyze the reliability of integration results as well as their impact on two different FTLE variants.
Stefan Koch, Sebastian Volke, Gerik Scheuermann, Hans Hagen, Mario Hlawitschka

Transfer Operator-Based Extraction of Coherent Features on Surfaces

Abstract
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.
Kathrin Padberg-Gehle, Sebastian Reuther, Simon Praetorius, Axel Voigt

Software and Algorithms

Frontmatter

ADAPT: Adaptive Thresholds for Feature Extraction

Abstract
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.
Peer-Timo Bremer

Efficient Software for Programmable Visual Analysis Using Morse-Smale Complexes

Abstract
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.
Nithin Shivashankar, Vijay Natarajan

Notes on the Distributed Computation of Merge Trees on CW-Complexes

Abstract
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.
Aaditya G. Landge, Peer-Timo Bremer, Attila Gyulassy, Valerio Pascucci

Computing Invariants of Knotted Graphs Given by Sequences of Points in 3-Dimensional Space

Abstract
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.
Vitaliy Kurlin
Additional information

Premium Partner

    Image Credits