Some equivalence relation between persistent homology and morphological dynamics. (English) Zbl 07645599
Summary: In mathematical morphology, connected filters based on dynamics are used to filter the extrema of an image. Similarly, persistence is a concept coming from persistent homology and Morse theory that represents the stability of the extrema of a Morse function. Since these two concepts seem to be closely related, in this paper we examine their relationship, and we prove that they are equal on \(n\)-D Morse functions, \(n\ge 1\). More exactly, pairing a minimum with a 1-saddle by dynamics or pairing the same 1-saddle with a minimum by persistence leads exactly to the same pairing, assuming that the critical values of the studied Morse function are unique. This result is a step further to show how much topological data analysis and mathematical morphology are related, paving the way for a more in-depth study of the relations between these two research fields.
MSC:
| 68U10 | Computing methodologies for image processing |
| 55N31 | Persistent homology and applications, topological data analysis |
| 57Q70 | Discrete Morse theory and related ideas in manifold topology |
| 68U03 | Computational aspects of digital topology |
Keywords:
mathematical morphology; Morse theory; computational topology; persistent homology; dynamics; persistenceReferences:
| [1] | https://higra.readthedocs.io/en/stable/python-tree_attributes.html, 2021. Accessed: 2021-06-17 |
| [2] | Audin, M., Damian, M.: Morse theory and floer homology. Springer (2014) · Zbl 1281.57001 |
| [3] | Bertrand, G., On the dynamics, Image Vision Comput, 25, 4, 447-454 (2007) · doi:10.1016/j.imavis.2006.04.017 |
| [4] | Bertrand, G, Everat, J-C, Couprie, M.: Topological approach to image segmentation. In: SPIE’s 1996 International Symposium on Optical Science, Engineering, and Instrumentation, vol. 2826, pp. 65-76. International Society for Optics and Photonics (1996) |
| [5] | Beucher, S., Meyer, F.: The morphological approach to segmentation: the watershed transformation. Optical Engineering, New York, Marcel Dekker Incorporated 34: 433 (1992) |
| [6] | Boutry, N., Géraud, T., Najman, L.: An equivalence relation between Morphological Dynamics and Persistent Homology in 1D. In: International Symposium on Mathematical Morphology. volume 11564 of Lecture Notes in Computer Science Series, pp. 57-68. Springer, (2019) · Zbl 1445.68244 |
| [7] | Boutry, N., Géraud, T., Najman, L.: An equivalence relation between morphological dynamics and persistent homology in \(n\)-D. In: International Conference on Discrete Geometry and Mathematical Morphology, pp. 525-537. Springer (2021) · Zbl 1484.68289 |
| [8] | Carlinet, E., Crozet, S., Géraud, T.: The tree of shapes turned into a max-tree: a simple and efficient linear algorithm. In: 2018 25th IEEE International Conference on Image Processing (ICIP), pp. 1488-1492. IEEE (2018) |
| [9] | Carlinet, E.; Géraud, T., A comparative review of component tree computation algorithms, IEEE Trans. Image Process., 23, 9, 3885-3895 (2014) · Zbl 1374.94055 · doi:10.1109/TIP.2014.2336551 |
| [10] | Carr, H.; Snoeyink, J.; Axen, U., Computing contour trees in all dimensions, Comput. Geom., 24, 2, 75-94 (2003) · Zbl 1052.68098 · doi:10.1016/S0925-7721(02)00093-7 |
| [11] | Carr, H., Snoeyink, J., Van De Panne, M.: Simplifying flexible isosurfaces using local geometric measures. In: IEEE Visualization 2004, pp 497-504. IEEE (2004) |
| [12] | Caselles, V., Monasse, P.: Geometric description of images as topographic maps. Springer (2009) · Zbl 1191.68759 |
| [13] | Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Extending persistence using Poincaré and Lefschetz duality, Found. Comput. Math., 9, 1, 79-103 (2009) · Zbl 1189.55002 · doi:10.1007/s10208-008-9027-z |
| [14] | Čomić, L.; De Floriani, L.; Iuricich, F.; Magillo, P., Computing a discrete Morse gradient from a watershed decomposition, Comput. Graph., 58, 43-52 (2016) · doi:10.1016/j.cag.2016.05.020 |
| [15] | Čomić, L., De Floriani, L., Papaleo, L.: Morse-smale decompositions for modeling terrain knowledge. In: International Conference on Spatial Information Theory, pp. 426-444. Springer (2005) |
| [16] | Cousty, J.; Bertrand, G.; Couprie, M.; Najman, L., Collapses and watersheds in pseudomanifolds of arbitrary dimension, J. Math. Imaging Vis., 50, 3, 261-285 (2014) · Zbl 1312.68220 · doi:10.1007/s10851-014-0498-z |
| [17] | Cousty, J.; Bertrand, G.; Najman, L.; Couprie, M., Watershed cuts: Minimum spanning forests and the drop of water principle, IEEE Trans. Pattern Anal. Mach. Intell., 31, 8, 1362-1374 (2009) · doi:10.1109/TPAMI.2008.173 |
| [18] | Cousty, J.; Najman, L.; Kenmochi, Y.; Guimarães, S., Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps, J. Math. Imaging Vis., 60, 4, 479-502 (2018) · Zbl 1420.94010 · doi:10.1007/s10851-017-0768-7 |
| [19] | Crozet, S., Géraud, T.: A first parallel algorithm to compute the morphological tree of shapes of nd images. In: 2014 IEEE International Conference on Image Processing (ICIP), pp. 2933-2937. IEEE (2014) |
| [20] | Dey, TK; Wenger, R., Stability of critical points with interval persistence, Discre. Comput. Geom., 38, 3, 479-512 (2007) · Zbl 1147.55006 · doi:10.1007/s00454-007-1356-1 |
| [21] | Edelsbrunner, H.; Harer, J., Persistent Homology - A survey, Contemp. Math., 453, 257-282 (2008) · Zbl 1145.55007 · doi:10.1090/conm/453/08802 |
| [22] | Edelsbrunner H., Harer J.: Computational topology: an introduction. Am. Math. Soc. (2010) · Zbl 1193.55001 |
| [23] | Edelsbrunner, H., Harer, J., Natarajan, V., Pascucci, V.: Morse-Smale complexes for piecewise linear 3-manifolds. In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 361-370 (2003) · Zbl 1375.68125 |
| [24] | Edelsbrunner, H.; Harer, J.; Zomorodian, A., Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds, Discre. Comput. Geom., 30, 1, 87-107 (2003) · Zbl 1029.57023 · doi:10.1007/s00454-003-2926-5 |
| [25] | Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Found. Comput. Sci. pp 454-463. IEEE (2000) · Zbl 1011.68152 |
| [26] | Forman, R.; Yau, S-T, A Discrete Morse Theory for cell complexes, Geometry (1995), Somerville MA: Topology for Raoul Bott. International Press, Somerville MA · Zbl 0602.58044 |
| [27] | Forman, R.: Morse Theory for cell complexes (1998) · Zbl 0896.57023 |
| [28] | Forman, R.: A user’s guide to Discrete Morse Theory. In: Sém. Lothar. Combin. pp. 48:35 (2002) · Zbl 1048.57015 |
| [29] | Freeman, H.; Morse, SP, On searching a contour map for a given terrain elevation profile, J. Franklin Inst., 284, 1, 1-25 (1967) · doi:10.1016/0016-0032(67)90568-6 |
| [30] | Géraud, T., Carlinet, E., Crozet, S., Najman, L.: A quasi-linear algorithm to compute the tree of shapes of n-D images. In: International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing, volume 7883 of Lecture Notes in Computer Science. pp. 98-110. Springer (2013) · Zbl 1382.68261 |
| [31] | Grimaud, M.: La géodésie numérique en Morphologie Mathématique. Application à la détection automatique des microcalcifications en mammographie numérique. PhD thesis, École des Mines de Paris (1991) |
| [32] | Grimaud, M.: New measure of contrast: the dynamics. In: Image Algebra and Morphological Image Processing III. 1769, 292-306. International Society for Optics and Photonics (1992) |
| [33] | Gueunet, C.; Fortin, P.; Jomier, J.; Tierny, J., Task-based augmented contour trees with fibonacci heaps, IEEE Trans. Parallel Distrib. Syst., 30, 8, 1889-1905 (2019) · doi:10.1109/TPDS.2019.2898436 |
| [34] | Günther, D.; Reininghaus, J.; Wagner, H.; Hotz, I., Efficient computation of 3D Morse-Smale complexes and Persistent Homology using Discrete Morse Theory, Vis. Comput., 28, 10, 959-969 (2012) · doi:10.1007/s00371-012-0726-8 |
| [35] | Jöllenbeck, M., Welker, V.: Minimal resolutions via Algebraic Discrete Morse Theory. Am. Math. Soc. (2009) · Zbl 1160.13007 |
| [36] | Lukasczyk, J.; Garth, C.; Maciejewski, R.; Tierny, J., Localized topological simplification of scalar data, IEEE Trans. Vis. Comput. Graph., 27, 572 (2020) · doi:10.1109/TVCG.2020.3030353 |
| [37] | M, Talha Bin, Budin, J., Falk, M., Favelier, G., Garth, C., Gueunet, C., Guillou, P., Hofmann, L., Hristov, P., Kamakshidasan, A., et al.: An overview of the topology toolkit. In: TopoInVis 2019-Topological Methods in Data Analysis and Visualization (2019) |
| [38] | Matheron, G., Random sets theory and its applications to stereology, J. Microsc., 95, 1, 15-23 (1972) · doi:10.1111/j.1365-2818.1972.tb03708.x |
| [39] | Meyer, F., Skeletons and perceptual graphs, Signal Process., 16, 4, 335-363 (1989) · doi:10.1016/0165-1684(89)90030-3 |
| [40] | Milnor, JW, Michael Spivak, Robert Wells, and Robert Wells (1963), Morse Theory, Princeton: Princeton University Press, Morse Theory, Princeton · Zbl 0108.10401 |
| [41] | Najman, L., On the equivalence between hierarchical segmentations and ultrametric watersheds, J. Math. Imaging Vis., 40, 3, 231-247 (2011) · Zbl 1255.68258 · doi:10.1007/s10851-011-0259-1 |
| [42] | Najman, L.; Schmitt, M., Geodesic saliency of watershed contours and hierarchical segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 18, 12, 1163-1173 (1996) · doi:10.1109/34.546254 |
| [43] | Najman L., Talbot H.: Mathematical morphology: from theory to applications. Wiley (2013) · Zbl 1198.94012 |
| [44] | Perret, B.; Chierchia, G.; Cousty, J.; Guimaraes, SJF; Kenmochi, Y.; Najman, L., Higra: hierarchical graph analysis, Software, 10 (2019) · doi:10.1016/j.softx.2019.100335 |
| [45] | Salembier, P., Oliveras, A., Garrido, L.: Antiextensive connected operators for image and sequence processing. IEEE Trans. Image Process. 7(4), 555-570 (1998) |
| [46] | Salembier, P., Wilkinson, M.H.F.: Connected operators. IEEE Signal Process. Mag. 26(6), 136-157 (2009) |
| [47] | Serra, J., Introduction to mathematical morphology, Comput. Vis. Graph. Image Process., 35, 3, 283-305 (1986) · Zbl 0648.92001 · doi:10.1016/0734-189X(86)90002-2 |
| [48] | Serra J., Soille P.: Mathematical morphology and its applications to image processing, vol. 2. Springer (2012) · Zbl 0823.00019 |
| [49] | Tierny, J.; Favelier, G.; Levine, JA; Gueunet, C.; Michaux, M., The topology toolkit, IEEE Trans. Vis. Comput. Graph., 24, 1, 832-842 (2017) · doi:10.1109/TVCG.2017.2743938 |
| [50] | Urbach, ER; Roerdink, JBTM; Wilkinson, MHF, Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images, IEEE Trans Pattern Anal. Mach. Intell., 29, 2, 272-285 (2007) · doi:10.1109/TPAMI.2007.28 |
| [51] | Vachier, C.: Extraction de caractéristiques, segmentation d’image et Morphologie Mathématique. PhD thesis, École Nationale Supérieure des Mines de Paris (1995) |
| [52] | Vincent, L.; Soille, P., Watersheds in digital spaces: an efficient algorithm based on immersion simulations, IEEE Trans. Pattern Anal. Mach. Intell., 13, 6, 583-598 (1991) · doi:10.1109/34.87344 |
| [53] | Yongchao, X.; Géraud, T.; Najman, L., Connected filtering on tree-based shape-spaces, IEEE Trans. Pattern Anal. Mach. Intell., 38, 6, 1126-1140 (2015) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
