Comparative Analysis of Topological Structures

Abstract

Measuring scientific processes result in a set of scalar functions (scalar fields) which may be related temporally, be part of an ensemble, or unrelated. Overall understanding and visualization of scientific processes require the study of individual fields and, more importantly, the development of methods to compare them meaningfully. In this thesis, we focus on the problem of designing meaningful measures to compare scalar fields by comparing their abstract representations called topological structures. We emphasize on intuitive and practical measures with useful properties and applications.

The first part of the thesis deals with comparing a topological structure called the merge tree. We propose two global comparison measures, both based on tree edit distances. The first measure OTED is based on the assumption that merge trees are ordered rooted trees. Upon finding that there is no meaningful way of imposing such an order, we propose a second measure called MTED for comparing unordered rooted trees. We propose intuitive cost models and prove that MTED is a metric. We also provide various applications such as shape comparison, periodicity detection, symmetry detection, temporal summarization, and an analysis of the effects of sub-sampling /smoothing on the topology of the scalar field.

The second part deals with a local comparison measure LMTED for merge trees that supports the comparison of substructures of scalar fields, thus facilitating hierarchical or multi-scale analysis and alleviating some drawbacks of MTED. We propose a dynamic programming algorithm, prove that LMTED is a metric and also provide applications such as symmetry detection in multiple scales, a finer level analysis of sub-sampling effects, an analysis of the effects of topological compression, and feature tracking in time-varying fields.

The third part of the thesis deals with comparison of a topological structure called the extremum graph. We provide two comparison measures for extremum graphs based on persistence distortion (PDEG) and Gromov-Wasserstein distance (GWEG). Both persistence distortion and Wasserstein distance are known metrics. We analyze how the underlying metric affects these comparison measures and present various applications such as periodicity detection to facilitate scientific data analysis and visualization.

The final part of the thesis introduces a time-varying version of extremum graphs (TVEG) with a simple comparison criterion to identify correspondences between features in successive time steps. We provide applications to tracking features in time-varying scalar fields from computational fluid dynamics.