Search Results

Documents authored by Wagner, Hubert

Document
DOI: 10.4230/LIPIcs.SoCG.2023.60
Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data

Authors: Hubert Wagner

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We focus on efficient computations of topological descriptors for voxel data. This type of data includes 2D greyscale images, 3D medical scans, but also higher-dimensional scalar fields arising from physical simulations. In recent years we have seen an increase in applications of topological methods for such data. However, computational issues remain an obstacle. We therefore propose a streaming scheme which simplifies large 3-dimensional voxel data - while provably retaining its persistent homology. We combine this scheme with an efficient boundary matrix reduction implementation, obtaining an end-to-end tool for persistent homology of large data. Computational experiments show its state-of-the-art performance. In particular, we are now able to robustly handle complex datasets with several billions voxels on a regular laptop. A software implementation called Cubicle is available as open-source: https://bitbucket.org/hubwag/cubicle.
Cite as

Hubert Wagner. Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wagner:LIPIcs.SoCG.2023.60,
  author =	{Wagner, Hubert},
  title =	{{Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{60:1--60:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.60},
  URN =		{urn:nbn:de:0030-drops-179107},
  doi =		{10.4230/LIPIcs.SoCG.2023.60},
  annote =	{Keywords: Computational topology, topological data analysis, topological image analysis, persistent homology, persistence diagram, discrete Morse theory, algorithm engineering, implementation, voxel data, volume data, image data}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.64
GPU Computation of the Euler Characteristic Curve for Imaging Data

Authors: Fan Wang, Hubert Wagner, and Chao Chen

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Persistent homology is perhaps the most popular and useful tool offered by topological data analysis - with point-cloud data being the most common setup. Its older cousin, the Euler characteristic curve (ECC) is less expressive - but far easier to compute. It is particularly suitable for analyzing imaging data, and is commonly used in fields ranging from astrophysics to biomedical image analysis. These fields are embracing GPU computations to handle increasingly large datasets. We therefore propose an optimized GPU implementation of ECC computation for 2D and 3D grayscale images. The goal of this paper is twofold. First, we offer a practical tool, illustrating its performance with thorough experimentation - but also explain its inherent shortcomings. Second, this simple algorithm serves as a perfect backdrop for highlighting basic GPU programming techniques that make our implementation so efficient - and some common pitfalls we avoided. This is intended as a step towards a wider usage of GPU programming in computational geometry and topology software. We find this is particularly important as geometric and topological tools are used in conjunction with modern, GPU-accelerated machine learning frameworks.
Cite as

Fan Wang, Hubert Wagner, and Chao Chen. GPU Computation of the Euler Characteristic Curve for Imaging Data. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SoCG.2022.64,
  author =	{Wang, Fan and Wagner, Hubert and Chen, Chao},
  title =	{{GPU Computation of the Euler Characteristic Curve for Imaging Data}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.64},
  URN =		{urn:nbn:de:0030-drops-160724},
  doi =		{10.4230/LIPIcs.SoCG.2022.64},
  annote =	{Keywords: topological data analysis, Euler characteristic, Euler characteristic curve, Betti curve, persistent homology, algorithms, parallel programming, algorithm engineering, GPU programming, imaging data}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.31
Topological Data Analysis in Information Space

Authors: Herbert Edelsbrunner, Žiga Virk, and Hubert Wagner

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.
Cite as

Herbert Edelsbrunner, Žiga Virk, and Hubert Wagner. Topological Data Analysis in Information Space. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2019.31,
  author =	{Edelsbrunner, Herbert and Virk, \v{Z}iga and Wagner, Hubert},
  title =	{{Topological Data Analysis in Information Space}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.31},
  URN =		{urn:nbn:de:0030-drops-104357},
  doi =		{10.4230/LIPIcs.SoCG.2019.31},
  annote =	{Keywords: Computational topology, persistent homology, information theory, entropy}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.35
Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry

Authors: Herbert Edelsbrunner, Ziga Virk, and Hubert Wagner

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.
Cite as

Herbert Edelsbrunner, Ziga Virk, and Hubert Wagner. Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2018.35,
  author =	{Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert},
  title =	{{Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.35},
  URN =		{urn:nbn:de:0030-drops-87487},
  doi =		{10.4230/LIPIcs.SoCG.2018.35},
  annote =	{Keywords: Bregman divergence, smallest enclosing spheres, Chernoff points, convexity, barycenter polytopes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.39
Topological Data Analysis with Bregman Divergences

Authors: Herbert Edelsbrunner and Hubert Wagner

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback-Leibler divergence, which is commonly used for comparing text and images, and the Itakura-Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized Cech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized Cech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory.
Cite as

Herbert Edelsbrunner and Hubert Wagner. Topological Data Analysis with Bregman Divergences. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2017.39,
  author =	{Edelsbrunner, Herbert and Wagner, Hubert},
  title =	{{Topological Data Analysis with Bregman Divergences}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.39},
  URN =		{urn:nbn:de:0030-drops-71985},
  doi =		{10.4230/LIPIcs.SoCG.2017.39},
  annote =	{Keywords: Topological data analysis, Bregman divergences, persistent homology, proximity complexes, algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact