Merge Tree Geodesics and Barycenters with Path Mappings
Pages 1095 - 1105
Abstract
Comparative visualization of scalar fields is often facilitated using similarity measures such as edit distances. In this paper, we describe a novel approach for similarity analysis of scalar fields that combines two recently introduced techniques: Wasserstein geodesics/barycenters as well as path mappings, a branch decomposition-independent edit distance. Effectively, we are able to leverage the reduced susceptibility of path mappings to small perturbations in the data when compared with the original Wasserstein distance. Our approach therefore exhibits superior performance and quality in typical tasks such as ensemble summarization, ensemble clustering, and temporal reduction of time series, while retaining practically feasible runtimes. Beyond studying theoretical properties of our approach and discussing implementation aspects, we describe a number of case studies that provide empirical insights into its utility for comparative visualization, and demonstrate the advantages of our method in both synthetic and real-world scenarios. We supply a C++ implementation that can be used to reproduce our results.
References
[1]
J. P. Ahrens, B. Geveci, and C. C. Law. “Paraview: An end-user tool for large-data visualization”. In C. D. Hansen and C. R. Johnson, eds., The Visualization Handbook, pp. 717–731. Elsevier: Academic Press, 2005. 5.
[2]
U. Bauer, B. D. Fabio, and C. Landi. An edit distance for reeb graphs. In A. Ferreira, A. Giachetti, and D. Giorgi, eds., 9th Eurographics Workshop on 3D Object Retrieval, 3DOR@Eurographics 2016, Lisbon, Portugal, May 8,2016. Eurographics Association, 2016. 2.
[3]
U. Bauer, X. Ge, and Y. Wang. Measuring distance between reeb graphs. In S. Cheng and O. Devillers, eds., 30th Annual Symposium on Computational Geometry, SoCG'14, Kyoto, Japan, June 08–11,2014, pp. 464–473. ACM. 2014. 2.
[4]
K. Beketayev, D. Yeliussizov, D. Morozov, G. H. Weber, and B. Hamann. “Measuring the distance between merge trees”. In P. Bremer, I. Hotz, V. Pascucci, and R. Peikert, eds., Topological Methods in Data Analysis and Visualization III, Theory, Algorithms, and Applications, pp. 151–165. Springer, 2014. 1,2.
[5]
B. Bollen, P. Tennakoon, and J. A. Levine. Computing a stable distance on merge trees. IEEE Trans. Vis. Comput. Graph., 29 (1): pp. 1168–1177, 2023. 2.
[6]
P. Bremer, G. H. Weber, V. Pascucci, M. S. Day, and J. B. Bell. Analyzing and tracking burning structures in lean premixed hydrogen flames. IEEE Trans. Vis. Comput. Graph., 16 (2): pp. 248–260, 2010. 2.
[7]
P. Bremer, G. H. Weber, J. Tierny, V. Pascucci, M. S. Day, and J. B. Bell. Interactive exploration and analysis of large-scale simulations using topology-based data segmentation. IEEE Trans. Vis. Comput. Graph., 17 (9): pp. 1307–1324, 2011. 2.
[8]
A. M. Bronstein, M. M. Bronstein, and R. Kimmel. “Numerical Geometry of Non-Rigid Shapes”. Monographs in Computer Science. Springer, 2009. 6.
[9]
H. A. Carr and J. Snoeyink. Path seeds and flexible isosurfaces - using topology for exploratory visualization. In 5th Joint Eurographics - IEEE TCVG Symposium on Visualization, VisSym 2003, Grenoble, France, May 26–28, 2003, pp. 49–58. Eurographics Association, 2003. 2.
[10]
M. E. Celebi, H. A. Kingravi, and P. A. Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Syst. Appl., 40 (1): pp. 200–210, 2013., 5.
[11]
F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, and S. Oudot. Proximity of persistence modules and their diagrams. In J. Hershberger and E. Fogel, eds., Proceedings of the 25thACM Symposium on Computational Geometry, Aarhus, Denmark, June 8–10, 2009, pp. 237–246. ACM, 2009. 2.
[12]
D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discret. Comput. Geom., 37 (1): pp. 103–120, 2007. 2.
[13]
D. Cohen-Steiner, H. Edelsbrunner, J. Harer, and Y. Mileyko. Lipschitz functions have Lp-stable persistence. Found. Comput. Math., 10 (2): pp. 127–139. 2010. 2.
[14]
H. Edelsbrunner and J. Harer. Computational Topology - an Introduction. American Mathematical Society, 2010. 2,3.
[15]
H. Edelsbrunner, J. Harer, A. Mascarenhas, and V. Pascucci. Time-varying reeb graphs for continuous space-time data. In J. Snoeyink and J. Boissonnat, eds., Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8–11,2004, pp. 366–372. ACM, 2004. 2.
[16]
H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. In 41 st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12–14 November 2000, Redondo Beach, California, USA, pp. 454–463. IEEE Computer Society, 2000. 2.
[17]
C. Elkan. Using the triangle inequality to accelerate k-means. In T. Fawcett and N. Mishra, eds., Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21–24, 2003, Washington, DC, USA, pp. 147–153. AAAI Press, 2003. 1,5.
[18]
M. Evers, M. Herick, V. Molchanov, and L. Linsen. Coherent topological landscapes for simulation ensembles. In K. Bouatouch, A. A. de Sousa, M. Chessa, A. Paljic, A. Kerren, C. Hurter, G. M. Farinella, P. Radeva, and J. Braz, eds., Computer Vision, Imaging and Computer Graphics Theory and Applications - 15th International Joint Conference, VISIGRAPP 2020 Valletta, Malta, February 27–29, 2020, Revised Selected Papers, vol. 1474 of Communications in Computer and Information Science, pp. 223–237. Springer, 2020. 2.
[19]
B. D. Fabio and C. Landi. The edit distance for reeb graphs of surfaces. Discret. Comput. Geom., 55 (2): pp. 423–461, 2016. 2.
[20]
G. Favelier, N. Faraj, B. Summa, and J. Tierny. Persistence atlas for critical point variability in ensembles. IEEE Trans. Vis. Comput. Graph., 25 (1): pp. 1152–1162, 2019. 6.
[21]
E. Gasparovic, E. Munch, S. Oudot, K. Turner, B. Wang, and Y. Wang. Intrinsic interleaving distance for merge trees. CoRR, 1908.00063, 2019. 2.
[22]
D. Günther, J. Salmon, and J. Tierny. Mandatory critical points of 2d uncertain scalar fields. Comput. Graph. Forum, 33 (3): pp. 31–40, 2014. 2.
[23]
C. Heine, H. Leitte, M. Hlawitschka, F. Iuricich, L. D. Floriani, G. Scheuermann, H. Hagen, and C. Garth. A survey of topology-based methods in visualization. Comput. Graph. Forum, 35 (3): pp. 643–667, 2016. 2.
[24]
M. Hilaga, Y. Shinagawa, T. Komura, and T. L. Kunii. Topology matching for fully automatic similarity estimation of 3d shapes. In L. Pocock, ed., Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2001, Los Angeles, California, USA, August 12–17, 2001, pp. 203–212. ACM, 2001. 6.
[25]
L. Hubert and P. Arabie. Comparing partitions. Journal of classification, 2: pp. 193–218, 1985. 5.
[26]
W. Köpp and T. Weinkauf. Temporal merge tree maps: A topology-based static visualization for temporal scalar data. IEEE Trans. Vis. Comput. Graph., 29 (1): pp. 1157–1167, 2023. 2.
[27]
M. Kraus. Visualization of uncertain contour trees. In P. Richard and J. Braz, eds., IMAGAPP 2010 - Proceedings of the International Conference on Imaging Theory and Applications and IVAPP 2010 - Proceedings of the International Conference on Information Visualization Theory and Applications, Angers, France, May 17–21, 2010, pp. 132–139. INSTICC Press. 2010. 2.
[28]
S. P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28 (2): pp. 129–136, 1982. 3.
[29]
A. P. Lohfink, F. Gartzky, F. Wetzels, L. Vollmer, and C. Garth. Time-varying fuzzy contour trees. In 2021 IEEE Visualization Conference, IEEE VIS 2021 - Short Papers, New Orleans, LA, USA, October 24–29, 2021, pp. 86–90. IEEE, 2021. 2.
[30]
A. P. Lohfink, F. Wetzels, J. Lukasczyk, G. H. Weber, and C. Garth. Fuzzy contour trees: Alignment and joint layout of multiple contour trees. Comput. Graph. Forum, 39 (3): pp. 343–355, 2020. 2, 8.
[31]
A. P. Lohfink, F. Wetzels, J. Lukasczyk, G. H. Weber, and C. Garth. Source Code for Fuzzy Contour Trees: Alignment and Joint Layout of Multiple Contour Trees. [Online]. Available: https://github.com/scivislab/Fuzzy-Contour-Trees, 2021. 8.
[32]
J. Lukasczyk, G. Aldrich, M. Steptoe, G. Favelier, C. Gueunet, J. Tierny, R. Maciejewski, B. Hamann, and H. Leitte. “Viscous fingering: A topological visual analytic approach”. In Physical Modeling for Virtual Manufacturing Systems and Processes, vol. 869 of Applied Mechanics and Materials, pp. 9–19. Trans Tech Publications Ltd, 9 2017. 2.
[33]
J. Lukasczyk, C. Garth, G. H. Weber, T. Biedert, R. Maciejewski, and H. Leitte. Dynamic nested tracking graphs. IEEE Trans. Vis. Comput. Graph., 26 (1): pp. 249–258, 2020. 2.
[34]
J. Lukasczyk, G. H. Weber, R. Maciejewski, C. Garth, and H. Leitte. Nested tracking graphs. Comput. Graph. Forum, 36 (3): pp. 12–22, 2017. 2.
[35]
D. Morozov, K. Beketayev, and G. H. Weber. Interleaving distance between merge trees. In TopoInVis. 2014. 1.
[36]
D. Morozov and G. H. Weber. Distributed merge trees. In A. Nicolau, X. Shen, S. P. Amarasinghe, and R. W. Vuduc, eds., ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '13, Shenzhen, China, February 23–27, 2013, pp. 93–102. ACM, 2013. 2.
[37]
D. Morozov and G. H. Weber. “Distributed contour trees”. In P. Bremer, I. Hotz, V. Pascucci, and R. Peikert, eds., Topological Methods in Data Analysis and Visualization III, Theory, Algorithms, and Applications, pp. 89–102. Springer, 2014. 2.
[38]
V. Narayanan, D. M. Thomas, and V. Natarajan. Distance between extremum graphs. In S. Liu, G. Scheuermann, and S. Takahashi, eds., 2015 IEEE Pacific Visualization Symposium, PacificVis 2015, Hangzhou, China, April 14–17, 2015, pp. 263–270. IEEE Computer Society, 2015. 2.
[39]
E. Nilsson, J. Lukasczyk, W. Engelke, T. B. Masood, G. Svensson, R. Caballero, C. Garth, and I. Hotz. Exploring cyclone evolution with hierarchical features. In 2022 Topological Data Analysis and Visualization (TopoInVis), pp. 92–102, 2022. 2.
[40]
P. Oesterling, C. Heine, G. H. Weber, D. Morozov, and G. Scheuermann. “Computing and visualizing time-varying merge trees for high-dimensional data”. In H. Carr, C. Garth, and T. Weinkauf, eds., Topological Methods in Data Analysis and Visualization IV, pp. 87–101. Springer International Publishing, 2017. 2.
[41]
V. Pascucci, K. Cole-McLaughlin, and G. Scorzelli. Multi-resolution computation and presentation of contour trees. In IASTED, 2004. 2.
[42]
J. Patchett and G. R. Gisler. The IEEE SciVis Contest. [Online]. Available: http://sciviscontest.ieeevis.org/2018/, 2018. 8.
[43]
M. Pont, J. Vidal, J. Delon, and J. Tierny. Wasserstein distances, geodesics and barycenters of merge trees. IEEE Trans. Vis. Comput. Graph., 28 (1): pp. 291–301, 2022. 1, 2, 3, 4, 5,6.
[44]
M. Pont, J. Vidal, and J. Tierny. Principal geodesic analysis of merge trees (and persistence diagrams). IEEE Trans. Vis. Comput. Graph., 29 (2): pp. 1573–1589, 2023. 2.
[45]
S. Popinet. Free computational fluid dynamics. ClusterWorld, 2 (6), 2004. 6, 8.
[46]
H. Saikia, H. Seidel, and T. Weinkauf. Extended branch decomposition graphs: Structural comparison of scalar data. Comput. Graph. Forum, 33 (3): pp. 41–50, 2014. 1,2.
[47]
H. Saikia and T. Weinkauf. Global feature tracking and similarity estimation in time-dependent scalar fields. Comput. Graph. Forum, 36 (3): pp. 1–11, 2017. 2.
[48]
A. Schnorr, D. N. Helmrich, D. Denker, T. W. Kuhlen, and B. Hentschel. Feature tracking by two-step optimization. IEEE Trans. Vis. Comput. Graph., 26 (6): pp. 2219–2233, 2020. 2.
[49]
Q. Shu, H. Guo, J. Liang, L. Che, J. Liu, and X. Yuan. Ensemblegraph: Interactive visual analysis of spatiotemporal behaviors in ensemble simulation data. In C. Hansen, I. Viola, and X. Yuan, eds., 2016 IEEE Pacific Visualization Symposium, PacificVis 2016, Taipei, Taiwan, April 19–22, 2016, pp. 56–63. IEEE Computer Society, 2016. 2.
[50]
R. Sridharamurthy, T. B. Masood, A. Kamakshidasan, and V. Natarajan. Edit distance between merge trees. IEEE Trans. Vis. Comput. Graph., 26 (3): pp. 1518–1531, 2020. 1,2,6,8.
[51]
R. Sridharamurthy and V. Natarajan. Comparative analysis of merge trees using local tree edit distance. IEEE Trans. Vis. Comput. Graph., 29 (2): pp. 1518–1530, 2023. 2.
[52]
S. Takahashi, Y. Takeshima, and I. Fujishiro. Topological volume skeletonization and its application to transfer function design. Graphical Models, 66 (1): pp. 24–49, 2004. 2.
[53]
R. Taylor, A. Chourasia, D. Whalen, and M. L. Norman. The IEEE SciVis Contest. [Online]. Available: http://sciviscontest.ieeevis.org/2008/, 2008. 7.
[54]
D. M. Thomas and V. Natarajan. Symmetry in scalar field topology. IEEE Trans. Vis. Comput. Graph., 17 (12): pp. 2035–2044, 2011. 2.
[55]
D. M. Thomas and V. Natarajan. Detecting symmetry in scalar fields using augmented extremum graphs. IEEE Trans. Vis. Comput. Graph., 19 (12): pp. 2663–2672, 2013. 2.
[56]
J. Tierny, G. Favelier, J. A. Levine, C. Gueunet, and M. Michaux. The topology toolkit. IEEE Trans. Vis. Comput. Graph., 24 (1): pp. 832–842, 2018. 2,5,8.
[57]
K. Turner, Y. Mileyko, S. Mukherjee, and J. Harer. Fréchet means for distributions of persistence diagrams. Discret. Comput. Geom., 52 (1): pp. 44–70, 2014. 2.
[58]
J. Vidal, J. Budin, and J. Tierny. Progressive wasserstein barycenters of persistence diagrams. IEEE Trans. Vis. Comput. Graph., 26 (1): pp. 151–161, 2020. 2,6.
[59]
G. H. Weber, P. Bremer, and V. Pascucci. Topological landscapes: A terrain metaphor for scientific data. IEEE Trans. Vis. Comput. Graph., 13 (6): pp. 1416–1423, 2007. 2.
[60]
T. Weinkauf and H. Theisel. Streak lines as tangent curves of a derived vector field. IEEE Trans. Vis. Comput. Graph., 16 (6): pp. 1225–1234, 2010. 8.
[61]
F. Wetzels and C. Garth. A deformation-based edit distance for merge trees. In 2022 Topological Data Analysis and Visualization (TopoInVis), pp. 29–38, 2022. 1,2,3,8.
[62]
F. Wetzels, H. Leitte, and C. Garth. Branch decomposition-independent edit distances for merge trees. Comput. Graph. Forum, 41 (3): pp. 367–378, 2022. 1, 2, 5, 7, 8.
[63]
F. Wetzels, M. Pont, J. Tierny, and C. Garth. Merge tree geodesics and barycenters with path mappings (supplementary source code). [Online]. Available: https://doi.org/10.5281/zenodo.8160990, 2023. 10.
[64]
W. Widanagamaachchi, C. Christensen, P. Bremer, and V. Pascucci. Interactive exploration of large-scale time-varying data using dynamic tracking graphs. In R. S. Barga, H. Pfister, and D. H. Rogers, eds., IEEE Symposium on Large Data Analysis and Visualization, LDAV 2012, Seattle, Washington, USA, 14–15 October, 2012, pp. 9–17. IEEE Computer Society, 2012. 2.
[65]
K. Wu and S. Zhang. A contour tree based visualization for exploring data with uncertainty. International Journal for Uncertainty Quantification, 3: pp. 203–223, 2013. 2.
[66]
L. Yan, T. Bin Masood, F. Rasheed, I. Hotz, and B. Wang. Geometry aware merge tree comparisons for time-varying data with interleaving distances. IEEE Transactions on Visualization and Computer Graphics, pp. 1–1, 2022. 2.
[67]
L. Yan, T. B. Masood, R. Sridharamurthy, F. Rasheed, V. Natarajan, I. Hotz, and B. Wang. Scalar field comparison with topological descriptors: Properties and applications for scientific visualization. Comput. Graph. Forum, 40 (3): pp. 599–633, 2021. 2.
[68]
L. Yan, Y. Wang, E. Munch, E. Gasparovic, and B. Wang. A structural average of labeled merge trees for uncertainty visualization. IEEE Trans. Vis. Comput. Graph., 26 (1): pp. 832–842, 2020. 2.
Index Terms
- Merge Tree Geodesics and Barycenters with Path Mappings
Index terms have been assigned to the content through auto-classification.
Recommendations
Wasserstein Distances, Geodesics and Barycenters of Merge Trees
This paper presents a unified computational framework for the estimation of distances, geodesics and barycenters of merge trees. We extend recent work on the edit distance [104] and introduce a new metric, called the Wasserstein distance between merge ...
Barycenters in the Hellinger–Kantorovich Space
AbstractRecently, Liero, Mielke and Savaré introduced the Hellinger–Kantorovich distance on the space of nonnegative Radon measures of a metric space X. We prove that Hellinger–Kantorovich barycenters always exist for a class of metric spaces containing ...
Fast computation of wasserstein barycenters
ICML'14: Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32We present new algorithms to compute the mean of a set of empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter, is the measure that minimizes the sum of its Wasserstein distances to each ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2023 The Authors. This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 25 October 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in