Document Open Access Logo

The Discrete Morse Complex of Images: Algorithms, Modeling and Applications

Authors Ricardo Dutra da Silva , Helio Pedrini , Bernd Hamann

PDF

File

Thumbnail PDF
PDF
OASIcs.iPMVM.2020.18.pdf
  • Filesize: 2.46 MB
  • 19 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computing methodologies → Image processing
Keywords
  • Discrete Morse Complex
  • Image Topology
  • Cell Complexes

Metrics

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

Abstract

The Morse complex can be used for studying the topology of a function, e.g., an image or terrain height field when understood as bivariate functions. We present an algorithm for the computation of the discrete Morse complex of two-dimensional images using an edge-based data structure. By using this data structure, it is possible to perform local operations efficiently, which is important to construct the complex and make the structure useful for areas like visualization, persistent homology computation, or construction of a topological hierarchy. We present theoretical and applied results to demonstrate benefits and use of our method.

Cite As Get BibTex

Ricardo Dutra da Silva, Helio Pedrini, and Bernd Hamann. The Discrete Morse Complex of Images: Algorithms, Modeling and Applications. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.iPMVM.2020.18

Author Details

Ricardo Dutra da Silva
  • Department of Informatics, Federal University of Technology, Curitiba, PR, Brazil
Helio Pedrini
  • Institute of Computing, University of Campinas, SP, Brazil
Bernd Hamann
  • Department of Computer Science, University of California, Davis, CA 95616, USA

References

  1. Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence, 33(5):898-916, May 2011. Google Scholar
  2. ATTLC. The Database of Faces, 2019. URL: http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html.
  3. Utkarsh Ayachit. The ParaView Guide: A Parallel Visualization Application. Kitware, Inc., Clifton Park, NY, USA, 2015. Google Scholar
  4. Tathagata Basak. Combinatorial Cell Complexes and Poincaré Duality. Geometriae Dedicata, 147(1):357-387, 2010. Google Scholar
  5. Bruce G. Baumgart. A Polyhedron Representation for Computer Vision. In National Computer Conference and Exposition, pages 589-596, Anaheim, CA, USA, 1975. ACM. Google Scholar
  6. K. Beketayev, G.H. Weber, M. Haranczyk, P.-T. Bremer, M. Hlawitschka, and B. Hamann. Topology-based Visualization of Transformation Pathways in Complex Chemical Systems. Computer Graphics Forum, 30(3):663-672, 2011. Google Scholar
  7. Talha Bin Masood, Joseph Budin, Martin Falk, Guillaume Favelier, Christoph Garth, Charles Gueunet, Pierre Guillou, Lutz Hofmann, Petar Hristov, Adhitya Kamakshidasan, Christopher Kappe, Pavol Klacansky, Patrick Laurin, Joshua Levine, Jonas Lukasczyk, Daisuke Sakurai, Maxime Soler, Peter Steneteg, Julien Tierny, Will Usher, Jules Vidal, and Michal Wozniak. An Overview of the Topology ToolKit. In TopoInVis, 2019. Google Scholar
  8. P. T. Bremer, E. M. Bringa, M. A. Duchaineau, A. G. Gyulassy, D. Laney, A. Mascarenhas, and V. Pascucci. Topological Feature Extraction and Tracking. Journal of Physics: Conference Series, 78(1):1-5, 2007. Google Scholar
  9. P.-T. Bremer, H. Edelsbrunner, B. Hamann, and V. Pascucci. A Multi-Resolution Data Structure for Two-Dimensional Morse-Smale Functions. In IEEE Visualization, pages 139-146, Washington, DC, USA, 2003. Google Scholar
  10. Gunnar Carlsson, Gurjeet Singh, and Afra Zomorodian. Computing Multidimensional Persistence. In Yingfei Dong, Ding-Zhu Du, and Oscar Ibarra, editors, Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 730-739. Springer Berlin Heidelberg, 2009. Google Scholar
  11. Gunnar Carlsson, Afra Zomorodian, Anne Collins, and Leonidas Guibas. Persistence Barcodes for Shapes. In Eurographics Symposium on Geometry Processing, pages 124-135, New York, NY, USA, 2004. Google Scholar
  12. Chao Chen and Michael Kerber. Persistent Homology Computation with a Twist. In 27th European Workshop on Computational Geometry, pages 197-200, Morschach, Switzerland, 2011. Google Scholar
  13. Moo K. Chung, Peter Bubenik, and Peter T. Kim. Persistence Diagrams of Cortical Surface Data. In Conference on Information Processing in Medical Imaging, pages 386-397, Williamsburg, VA, USA, 2009. Google Scholar
  14. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of Persistence Diagrams. Discrete & Computational Geometry, 37(1):103-120, 2007. Google Scholar
  15. Anne Collins, Afra Zomorodian, Gunnar Carlsson, and Leonidas J. Guibas. A Barcode Shape Descriptor for Curve Point Cloud Data. Computers and Graphics, 28(6):881-894, 2004. Google Scholar
  16. Leila De Floriani and Annie Hui. Data Structures for Simplicial Complexes: An Analysis and a Comparison. In Third Eurographics Symposium on Geometry Processing, Vienna, Austria, 2005. Eurographics Association. Google Scholar
  17. O. Delgado-Friedrichs, V. Robins, and A. Sheppard. Skeletonization and partitioning of digital images using discrete morse theory. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(3):654-666, 2015. Google Scholar
  18. Herbert Edelsbrunner, John Harer, and Afra Zomorodian. Hierarchical Morse Complexes for Piecewise Linear 2-Manifolds. In Symposium on Computational Geometry, pages 70-79, Medford, MA, USA, 2001. Google Scholar
  19. Barbara Di Fabio and Claudia Landi. Persistent Homology and Partial Similarity of Shapes. Pattern Recognition Letters, 33(11):1445-1450, 2012. Google Scholar
  20. Riccardo Fellegara, Leila De Floriani, and Kenneth Weiss. Efficient Computation and Simplification of Discrete Morse Decompositions on Triangulated Terrains. In ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 223-232, Dallas, TX, USA, 2014. ACM. Google Scholar
  21. R. Forman. Morse Theory for Cell Complexes. Advances in Mathematics, 134(1):90-145, 1998. Google Scholar
  22. R. Forman. Morse Theory and Evasiveness. Combinatorica, 20(4):489-504, 2000. Google Scholar
  23. Jennifer Gamble and Giseon Heo. Exploring Uses of Persistent Homology for Statistical Analysis of Landmark-Based Shape Data. Journal of Multivariate Analysis, 101(9):2184-2199, 2010. Google Scholar
  24. Leo Grady and Jonathan R. Polimeni. Discrete Calculus - Applied Analysis on Graphs for Computational Science. Springer, 2010. Google Scholar
  25. Leonidas Guibas and Jorge Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, 4(2):74-123, 1985. Google Scholar
  26. David Günther, Jan Reininghaus, Hubert Wagner, and Ingrid Hotz. Efficient Computation of 3D Morse-Smale Complexes and Persistent Homology using Discrete Morse Theory. The Visual Computer, 28(10):959-969, October 2012. Google Scholar
  27. Attila Gabor Gyulassy. Combinatorial Construction of Morse-smale Complexes for Data Analysis and Visualization. PhD thesis, University of California, Davis, CA, USA, 2008. Google Scholar
  28. Frank Harary. Graph Theory. Addison-Wesley, 1969. Google Scholar
  29. Allen Hatcher. Algebraic Topology. Cambridge Univ. Press, Cambridge, 2000. Google Scholar
  30. Henry King, Kevin Knudson, and Neža Mramor Kosta. Birth and Death in Discrete Morse Theory. Journal of Symbolic Computation, 78:41-60, 2017. Google Scholar
  31. Henry King, Kevin Knudson, and Neža Mramor. Generating Discrete Morse Functions from Point Data. Experimental Mathematics, 14(4):435-444, 2005. Google Scholar
  32. V. A. Kovalevsky. Finite Topology as Applied to Image Analysis. Computer Vision, Graphics and Image Processing, 46(2):141-161, 1989. Google Scholar
  33. David Letscher and Jason Fritts. Image Segmentation Using Topological Persistence. In Conference on Computer Analysis of Images and Patterns, pages 587-595, Vienna, Austria, 2007. Google Scholar
  34. Thomas Lewiner, Helio Lopes, and Geovan Tavares. Applications of Forman’s Discrete Morse Theory to Topology Visualization and Mesh Compression. IEEE Transactions on Visualization and Computer Graphics, 10(5):499-508, 2004. Google Scholar
  35. P. Magillo, E. Danovaro, L. Floriani, L. Papaleo, and M. Vitali. A Discrete Approach to Compute Terrain Morphology. In J. Braz, A. Ranchordas, H. Araújo, and J.M. Pereira, editors, Computer Vision and Computer Graphics. Theory and Applications, volume 21 of Communications in Computer and Information Science, pages 13-26. Springer Berlin Heidelberg, 2009. Google Scholar
  36. Martti Mäntylä. An Introduction to Solid Modeling. Computer Science Press, Inc., New York, NY, USA, 1987. Google Scholar
  37. J. W. Milnor. Morse Theory. Annals of Mathematics Studies. Princeton University Press, 1963. Google Scholar
  38. Elías Gabriel Minian. Some Remarks on Morse Theory for Posets, Homological Morse Theory and Finite Manifolds. Topology and its Applications, 159(12):2860-2869, 2012. Google Scholar
  39. Konstantin Mischaikow and Vidit Nanda. Morse Theory for Filtrations and Efficient Computation of Persistent Homology. Discrete & Computational Geometry, 50(2):330-353, 2013. Google Scholar
  40. Helena Molina-Abril and Pedro Real. Homological Optimality in Discrete Morse Theory Through Chain Homotopies. Pattern Recognition Letters, 33(11):1501-1506, 2012. Google Scholar
  41. NASA. Jet Propulsion Laboratory, 2019. URL: http://www.jpl.nasa.gov.
  42. Sylvain Paris and Fredo Durand. A Topological Approach to Hierarchical Segmentation using Mean Shift. In IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, Los Alamitos, CA, USA, 2007. Google Scholar
  43. J. Reininghaus, N. Kotava, D. Gunther, J. Kasten, H. Hagen, and I. Hotz. A Scale Space Based Persistence Measure for Critical Points in 2D Scalar Fields. IEEE Transactions on Visualization and Computer Graphics, 17(12):2045-2052, 2011. Google Scholar
  44. Vanessa Robins, Peter John Wood, and Adrian P. Sheppard. Theory and Algorithms for Constructing Discrete Morse Complexes from Grayscale Digital Images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8):1646-1658, 2011. Google Scholar
  45. Nithin Shivashankar and Vijay Natarajan. Parallel Computation of 3D Morse-Smale Complexes. Computer Graphics Forum, 31(3pt1):965-974, 2012. Google Scholar
  46. A. Sole, V. Caselles, G. Sapiro, and F. Arandiga. Morse Description and Geometric Encoding of Digital Elevation Maps. IEEE Transactions on Image Processing, 13(9):1245-1262, 2004. Google Scholar
  47. J. Tierny, G. Favelier, J. A. Levine, C. Gueunet, and M. Michaux. The topology toolkit. IEEE Transactions on Visualization and Computer Graphics, 24(1):832-842, 2018. Google Scholar
  48. USGS. United States Geological Survey, 2019. URL: http://www.usgs.gov.
  49. Lidija Čomić, Leila De Floriani, and Federico Iuricich. Simplifying Morphological Representations of 2D and 3D Scalar Fields. In ACM International Conference on Advances in Geographic Information Systems, pages 437-440, Chicago, IL, USA, 2011. Google Scholar
  50. Hubert Wagner, Paweł Dłotko, and Marian Mrozek. Computational Topology in Text Mining. In Massimo Ferri, Patrizio Frosini, Claudia Landi, Andrea Cerri, and Barbara Fabio, editors, Computational Topology in Image Context, volume 7309 of Lecture Notes in Computer Science, pages 68-78. Springer Berlin Heidelberg, 2012. Google Scholar
  51. Bei Wang. Separating Features from Noise with Persistence and Statistics. PhD thesis, Duke University, Durham, NC, USA, 2010. Google Scholar
  52. Kenneth Weiss, Federico Iuricich, Riccardo Fellegara, and Leila De Floriani. A Primal/Dual Representation for Discrete Morse Complexes on Tetrahedral Meshes. Computer Graphics Forum, 32(3pt3):361-370, 2013. Google Scholar
  53. A. Zomorodian. Computing and Comprehending Topology: Persistence and Hierarchical Morse Complexes. PhD thesis, University of Illinois at Urbana-Champaign, 2001. Google Scholar
  54. A. Zomorodian. Computational Topology. In M. Atallah and M. Blanton, editors, Algorithms and Theory of Computation Handbook, volume 2, chapter 3. Chapman & Hall/CRC Press, second edition, 2010. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact