Edit Distance between Merge Trees

Abstract

Topological structures such as the merge tree provide an abstract and succinct representation of scalar fields. They facilitate effective visualization and interactive exploration of feature-rich data. A merge tree captures the topology of sub-level and super-level sets in a scalar field. Estimating the similarity between merge trees is an important problem with applications to feature-directed visualization of time-varying data. We present an approach based on tree edit distance to compare merge trees. The comparison measure satisfies metric properties, it can be computed efficiently, and the cost model for the edit operations is both intuitive and captures well-known properties of merge trees. Experimental results on time-varying scalar fields, 3D cryo electron microscopy data, shape data, and various synthetic datasets show the utility of the edit distance towards a feature-driven analysis of scalar fields.

Cited by in corpus (13)

• Scalar Field Comparison with Topological Descriptors: Properties and Applications for Scientific Visualization
• Branch Decomposition-Independent Edit Distances for Merge Trees
• Comparative Analysis of Merge Trees using Local Tree Edit Distance
• A Deformation-based Edit Distance for Merge Trees
• Computing a Stable Distance on Merge Trees
• Fast Comparative Analysis of Merge Trees Using Locality Sensitive Hashing
• Taming Horizontal Instability in Merge Trees: On the Computation of a Comprehensive Deformation-based Edit Distance
• Topological Feature Search in Time-Varying Multifield Data
• A family of metrics from the truncated smoothing of Reeb graphs
• Merge Tree Geodesics and Barycenters with Path Mappings
• Sketching Merge Trees for Scientific Data Visualization
• Comparing Embedded Graphs Using Average Branching Distance
• Reeb Graph Metrics from the Ground Up