Analysis and comparison of vector fields can be done via a segmentation of the flow field into regions of similar behavior and a subsequent extraction of the topological skeleton. Our goals are a numerically stable computation of the topological skeleton including the extraction and classification of all closed streamlines, and a simple but consistent simplification of the topological skeleton to allow for a multi-scale vector field analysis. To achieve these goals we are investigating the applicability of a combinatorial approach to vector field topology.
Overview
In this project we develop discrete algorithms for the computation of vector field topology. Robin Forman has described a discrete Morse theory for general vector fields, our theoretical foundation. Standard algorithms for the extraction of the topological skeleton of a vector field involve many numerical challenges: finding all zeros of a vector field, integrating streamlines and streamsurfaces, the intersection of those, and the extraction of periodic orbits. While there are stable numerical algorithms to do this, the overall resulting framework has many parameters that may strongly influence the result.
Our approach to computational vector field topology avoids this problem by first computing a discrete representative of the vector field and then extracting the topological skeleton in this combinatorial setting. The main advantages of this approach are:
- Consistency: The extracted skeleton is always consistent, i.e. it respects the topology of the domain. A vector field on a sphere always contains at least one critical point, a vector field on a torus with no critical points contains at least two periodic orbits. We know that these kind of topological constraints are always respected by our algorithm due to the solid theoretical foundation provided by Robin Forman.
- Robustness: Our algorithm directly computes a natural hierarchy of topological skeletons that that enables a multi-scale interpretation of the input data. If there is noise in the data the resulting topological structure can be easily filtered using this hierarchy.
- Simplicity: The algorithm that computes the multi-scale hierarchy of discrete vector fields consists of a single graph theoretic algorithm related to the maximum weight matching problem. Given a discrete vector field, its topology can easily be extracted using Depth First Search. The overall framework for this discrete multi-scale vector field topology is therefore rather easy to implement compared to the classic continuous approach. Also, there are no parameters, which simplifies the application to real word data sets.
Publications
- Computational Discrete Morse Theory for Divergence-Free 2D Vector Fields [pdf]
J. Reininghaus, I. Hotz, Topological Methods in Data Analysis and Visualization II, Springer, to appear - Efficient Computation of a Hierarchy of Discrete 3D Gradient Vector Fields [pdf]
D. Günther, J. Reininghaus, S. Prohaska, T. Weinkauf, H.-C. Hege, Topological Methods in Data Analysis and Visualization II, Springer, to appear - TADD: A Computational Framework for Data Analysis Using Discrete Morse Theory [pdf]
J. Reininghaus, D. Günther, I. Hotz, S. Prohaska, H.-C. Hege, Mathematical Software - ICMS 2010, 198-208 - Fast Combinatorial Vector Field Topology [pdf]
J. Reininghaus, C. Loewen, I. Hotz, IEEE Transactions on Computer Graphics and Visualization, 2010, in press - Combinatorial 2D Vector Field Topology Extraction and Simplification [pdf]
J. Reininghaus, I. Hotz. Best Paper at TopoInVis 2009, Topological Methods in Data Analysis and Visualization. Theory, Algorithms, and Applications., Mathematics and Visualization, al., V. Pascucci et (Ed.), pp. 115 - 126, Springer, Berlin, 2011