Document Open Access Logo

A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition)

Authors Erin Chambers , Christopher Fillmore , Elizabeth Stephenson , Mathijs Wintraecken

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.66.pdf
  • Filesize: 16.76 MB
  • 9 pages

Document Identifiers

Author Details

Erin Chambers
  • Saint Louis University, MO, USA
Christopher Fillmore
  • IST Austria, Klosterneuburg, Austria
Elizabeth Stephenson
  • IST Austria, Klosterneuburg, Austria
Mathijs Wintraecken
  • IST Austria, Klosterneuburg, Austria

Funding

Partially supported by the DFG Collaborative Research Center TRR 109, "Discretization in Geometry and Dynamics" and the European Research Council (ERC), grant no. 788183, "Alpha Shape Theory Extended".
  • Chambers, Erin: Supported in part by the National Science Foundation through grants DBI-1759807, CCF-1907612, and CCF-2106672.
  • Wintraecken, Mathijs: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science fund (FWF) M-3073

Acknowledgements

We thank André Lieutier, David Letscher, Ellen Gasparovic, Kathryn Leonard, and Tao Ju for early discussions on this work. We also thank Lu Liu, Yajie Yan and Tao Ju for sharing code to generate the examples.

Cite As Get BibTex

Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, and Mathijs Wintraecken. A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.66

Abstract

The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Medial axis
  • Collapse
  • Pruning
  • Burning
  • Stability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry: Theory and Applications, 19(2-3):127-153, 2001. URL: https://doi.org/10.1016/S0925-7721(01)00017-7.
  2. Vladimir Arnol'd. Singularities of caustics and wave fronts, volume 62 of Mathematics and its Applications. Springer Science & Business Media, 2013. Google Scholar
  3. D. Attali, J.-D. Boissonnat, and H. Edelsbrunner. Stability and computation of medial axes - a state-of-the-art report. In Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, Mathematics and Visualization, pages 109-125. Springer Berlin Heidelberg, 2009. Google Scholar
  4. Dominique Attali and Annick Montanvert. Modeling noise for a better simplification of skeletons. In Proceedings of 3rd IEEE International Conference on Image Processing, volume 3, pages 13-16. IEEE, 1996. URL: https://doi.org/10.1109/ICIP.1996.560357.
  5. Gulce Bal, Julia Diebold, Erin Wolf Chambers, Ellen Gasparovic, Ruizhen Hu, Kathryn Leonard, Matineh Shaker, and Carola Wenk. Skeleton-based recognition of shapes in images via longest path matching. In Research in Shape Modeling, volume 1 of Association for Women in Mathematics Series, pages 81-99. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-16348-2_6.
  6. RH Bing. Some aspects of the topology of 3-manifolds related to the Poincaré conjecture. In T.L. Saaty, editor, Lectures on modern mathematics, volume II, pages 93-128. John Wiley and Sons, 1964. Google Scholar
  7. Thibault Blanc-Beyne, Géraldine Morin, Kathryn Leonard, Stefanie Hahmann, and Axel Carlier. A salience measure for 3D shape decomposition and sub-parts classification. Graphical Models, 99:22-30, 2018. URL: https://doi.org/10.1016/j.gmod.2018.07.003.
  8. Harry Blum. A Transformation for Extracting New Descriptors of Shape. In Weiant Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form, pages 362-380. MIT Press, Cambridge, 1967. Google Scholar
  9. Michael A. Buchner. The structure of the cut locus in dimension less than or equal to six. Compositio Mathematica, 37(1):103-119, 1978. URL: http://www.numdam.org/item/CM_1978__37_1_103_0/.
  10. Ming-Ching Chang and Benjamin B. Kimia. Measuring 3d shape similarity by graph-based matching of the medial scaffolds. Computer Vision and Image Understanding, 115(5):707-720, May 2011. URL: https://doi.org/10.1016/j.cviu.2010.10.013.
  11. F. Chazal and R. Soufflet. Stability and finiteness properties of medial axis and skeleton. Journal of Dynamical and Control Systems, 10(2):149-170, 2004. URL: https://doi.org/10.1023/B:JODS.0000024119.38784.ff.
  12. Frédéric Chazal and André Lieutier. The “λ-medial axis”. Graphical Models, 67(4):304-331, 2005. URL: https://doi.org/10.1016/j.gmod.2005.01.002.
  13. Blender Online Community. Blender - a 3D modelling and rendering package. Blender Foundation, Stichting Blender Foundation, Amsterdam, 2018. URL: http://www.blender.org.
  14. James Damon. Smoothness and geometry of boundaries associated to skeletal structures I: Sufficient conditions for smoothness. In Annales de l'institut Fourier, volume 53(6), pages 1941-1985, 2003. URL: https://doi.org/10.5802/aif.1997.
  15. James Damon. Smoothness and geometry of boundaries associated to skeletal structures, II: Geometry in the Blum case. Compositio Mathematica, 140(6):1657-1674, 2004. URL: https://doi.org/10.1112/S0010437X04000570.
  16. James Damon. Determining the geometry of boundaries of objects from medial data. International Journal of Computer Vision, 63(1):45-64, 2005. Google Scholar
  17. James Damon. The global medial structure of regions in ℝ³. Geometry & Topology, 10(4):2385-2429, 2006. URL: https://doi.org/10.2140/gt.2006.10.2385.
  18. James Damon. Global geometry of regions and boundaries via skeletal and medial integrals. Communications in Analysis and Geometry, 15(2):307-358, 2007. URL: https://doi.org/10.4310/CAG.2007.v15.n2.a5.
  19. Ilke Demir, Camilla Hahn, Kathryn Leonard, Geraldine Morin, Dana Rahbani, Athina Panotopoulou, Amelie Fondevilla, Elena Balashova, Bastien Durix, and Adam Kortylewski. SkelNetOn 2019: Dataset and challenge on deep learning for geometric shape understanding. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 1143-1151, 2019. URL: https://doi.org/10.1109/CVPRW.2019.00149.
  20. Tamal K. Dey and Jian Sun. Defining and computing curve-skeletons with medial geodesic function. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing, SGP '06, pages 143-152, Goslar, DEU, 2006. Eurographics Association. Google Scholar
  21. Tamal K Dey and Wulue Zhao. Approximating the medial axis from the Voronoi diagram with a convergence guarantee. Algorithmica, 38(1):179-200, 2004. URL: https://doi.org/10.1007/s00453-003-1049-y.
  22. H. Federer. Curvature measures. Transactions of the American Mathematical Society, 93:418-491, 1959. URL: https://doi.org/10.1090/S0002-9947-1959-0110078-1.
  23. Peter J Giblin, Benjamin B Kimia, and Anthony J Pollitt. Transitions of the 3D medial axis under a one-parameter family of deformations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(5):900-918, 2008. URL: https://doi.org/10.1109/TPAMI.2008.120.
  24. Joachim Giesen, Balint Miklos, Mark Pauly, and Camille Wormser. The scale axis transform. In Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pages 106-115, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1542362.1542388.
  25. Seng-Beng Ho and Charles R Dyer. Shape smoothing using medial axis properties. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8(4):512-520, 1986. URL: https://doi.org/10.1109/TPAMI.1986.4767815.
  26. André Lieutier. Any open bounded subset of ℝⁿ has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029-1046, 2004. Solid Modeling Theory and Applications. URL: https://doi.org/10.1016/j.cad.2004.01.011.
  27. Lu Liu, Erin W. Chambers, David Letscher, and Tao Ju. Extended grassfire transform on medial axes of 2d shapes. Computer-Aided Design, 43(11):1496-1505, 2011. Solid and Physical Modeling 2011. URL: https://doi.org/10.1016/j.cad.2011.09.002.
  28. Eduard Looijenga. Structural Stability of smooth families of C^∞-functions. PhD thesis, Universiteit van Amsterdam, 1974. Google Scholar
  29. John N Mather. Distance from a submanifold in Euclidean-space. In Proceedings of symposia in pure mathematics, volume 40, pages 199-216. American Mathematical Society, 1983. Google Scholar
  30. Punam K Saha, Gunilla Borgefors, and Gabriella Sanniti di Baja. A survey on skeletonization algorithms and their applications. Pattern recognition letters, 76:3-12, 2016. Google Scholar
  31. T.B. Sebastian, P.N. Klein, and B.B. Kimia. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(5):550-571, 2004. URL: https://doi.org/10.1109/TPAMI.2004.1273924.
  32. Doron Shaked and Alfred M. Bruckstein. Pruning medial axes. Computer Vision and Image Understanding, 69(2):156-169, 1998. URL: https://doi.org/10.1006/cviu.1997.0598.
  33. Andrea Tagliasacchi, Thomas Delame, Michela Spagnuolo, Nina Amenta, and Alexandru Telea. 3D skeletons: A state-of-the-art report. In Computer Graphics Forum, volume 35(2), pages 573-597. Wiley Online Library, 2016. URL: https://doi.org/10.1111/cgf.12865.
  34. R. Thom. Sur le cut-locus d'une variété plongée. Journal of Differential Geometry, 6(4):577-586, 1972. URL: https://doi.org/10.4310/jdg/1214430644.
  35. Martijn van Manen. Maxwell strata and caustics. In Singularities In Geometry And Topology, pages 787-824. World Scientific, 2007. Google Scholar
  36. Franz-Erich Wolter. Cut locus and medial axis in global shape interrogation and representation. In MIT Design Laboratory Memorandum 92-2 and MIT Sea Grant Report, 1992. Google Scholar
  37. Yajie Yan, Kyle Sykes, Erin Chambers, David Letscher, and Tao Ju. Erosion thickness on medial axes of 3d shapes. ACM Transactions on Graphics, 35(4):38:1-38:12, July 2016. URL: https://doi.org/10.1145/2897824.2925938.
  38. Yosef Yomdin. On the local structure of a generic central set. Compositio Mathematica, 43(2):225-238, 1981. URL: http://www.numdam.org/item/CM_1981__43_2_225_0/.
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 About DROPS Imprint Privacy Contact