Morphological Hierarchies: A Unifying Framework with New Trees
Tóm tắt
Morphological hierarchies constitute a rich and powerful family of graph-based structures that can be used for image modeling, processing and analysis. In this article, we focus on an important subfamily of morphological hierarchies, namely the trees that model partial partitions of the image support. This subfamily includes in particular the component-tree and the tree of shapes. In this context, we provide some new graph-based structures (one directed acyclic graph and three trees): the graph of valued shapes, the tree of valued shapes, the complete tree of shapes and the topological tree of shapes. These new objects create a continuum between the two notions of component-tree and tree of shapes. In particular, they allow to establish that these two trees (together with a third notion of adjacency tree generally considered in topological image analysis) can be defined and handled in a unified framework. In addition, this framework enables to enrich the component-tree with additional information, leading on the one hand to a topological description of grey-level images that relies on the same paradigm as persistent homology, and on the other hand to the proposal of a topological version of tree of shapes. This article provides a theoretical analysis of these new morphological hierarchies and their links with the usual ones. It also proposes an algorithmic description of two ways of building these new morphological hierarchies, and a discussion on the links that exist between these morphological hierarchies and certain topological invariants and descriptors.
Tài liệu tham khảo
Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1, 131–137 (1972)
Bertrand, G., Couprie, M., Passat, N.: A note on 3-D simple points and simple-equivalence. Inf. Process. Lett. 109, 700–704 (2009)
Bertrand, G., Everat, J.C., Couprie, M.: Image segmentation through operators based on topology. J. Electron. Imaging 6, 395–405 (1997)
Bertrand, G., Malandain, G.: A new characterization of three-dimensional simple points. Pattern Recogn. Lett. 15, 169–175 (1994)
Boutry, N., Najman, L., Géraud, T.: Some equivalence relation between persistent homology and morphological dynamics. J. Math. Imaging Vis. 64, 807–824 (2022)
Braga-Neto, U., Goutsias, J.K.: A theoretical tour of connectivity in image processing and analysis. J. Math. Imaging Vis. 19, 5–31 (2003)
Brouwer, L.E.J.: Über Jordansche Mannigfaltigkeiten. Math. Ann. 71, 320–327 (1911)
Carlinet, E., Géraud, T.: A comparative review of component tree computation algorithms. IEEE Trans. Image Process. 23, 3885–3895 (2014)
Carlinet, E., Géraud, T.: MToS: a tree of shapes for multivariate images. IEEE Trans. Image Process. 24, 5330–5342 (2015)
Couprie, M., Bertrand, G.: New characterizations of simple points in 2D, 3D, and 4D discrete spaces. IEEE Trans. Pattern Anal. Mach. Intell. 31, 637–648 (2009)
Couprie, M., Nivando Bezerra, F., Bertrand, G.: Topological operators for grayscale image processing. J. Electron. Imaging 10, 1003–1015 (2001)
Cousty, J., Perret, B., Phelippeau, H., Carneiro, S., Kamlay, P., Buzer, L.: An algebraic framework for out-of-core hierarchical segmentation algorithms. In: DGMM, Discrete Geometry and Mathematical Morphology, Proceedings. Lecture Notes in Computer Science, vol. 12708, pp. 378–390. Springer (2021)
Edelsbrunner, H., Harrer, J.: Persistent homology - A survey. Contemp. Math. 453, 257–282 (2008)
Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533 (2002)
Gazagnes, S., Wilkinson, M.H.F.: Distributed connected component filtering and analysis in 2D and 3D tera-scale data sets. IEEE Trans. Image Process. 30, 3664–3675 (2021)
Géraud, T., Carlinet, E., Crozet, S., Najman, L.: A quasi-linear algorithm to compute the tree of shapes of \(n\)D. In: ISMM, International Symposium on Mathematical Morphology, Proceedings. Lecture Notes in Computer Science, vol. 7883, pp. 98–110. Springer (2013)
Jones, R.: Connected filtering and segmentation using component trees. Comput. Vis. Image Underst. 75, 215–228 (1999)
Kerautret, B., Ngo, P., Kenmochi, Y., Vacavant, A.: Greyscale image vectorization from geometric digital contour representations. In: DGCI, Discrete Geometry for Computer Imagery, Proceedings. Lecture Notes in Computer Science, vol. 10502, pp. 319–331. Springer (2017)
Kiran, B., Serra, J.: Braids of partitions. In: ISMM, International Symposium on Mathematical Morphology, Proceedings. Lecture Notes in Computer Science, vol. 9082, pp. 217–228. Springer (2015)
Kong, T.Y., Litherland, R., Rosenfeld, A.: Problems in the topology of binary digital images. In: van Mill, J., Reed, G.M. (eds.) Open Problems in Topology, chap. 23, pp. 377–385. Elsevier Science Publishers B.V. (North-Holland) (1990)
Kovalevsky, V.A.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46, 141–161 (1989)
Kurtz, C., Naegel, B., Passat, N.: Connected filtering based on multivalued component-trees. IEEE Trans. Image Process. 23, 5152–5164 (2014)
Latecki, L.J., Eckhardt, U., Rosenfeld, A.: Well-composed sets. Comput. Vis. Image Underst. 61, 70–83 (1995)
Malgouyres, R., Francés, A.R.: Determining whether a simplicial 3-complex collapses to a 1-complex is NP-complete. In: DGCI, Discrete Geometry for Computer Imagery, Proceedings. Lecture Notes in Computer Science, vol. 4992, pp. 177–188. Springer (2008)
Mazo, L., Passat, N., Couprie, M., Ronse, C.: Paths, homotopy and reduction in digital images. Acta Appl. Math. 113, 167–193 (2011)
Mazo, L., Passat, N., Couprie, M., Ronse, C.: Digital imaging: a unified topological framework. J. Math. Imaging Vis. 44, 19–37 (2012)
Monasse, P., Guichard, F.: Fast computation of a contrast-invariant image representation. IEEE Trans. Image Process. 9, 860–872 (2000)
Montanvert, A., Meer, P., Rosenfeld, A.: Hierarchical image analysis using irregular tessellations. IEEE Trans. Pattern Anal. Mach. Intell. 13, 307–316 (1991)
Morimitsu, A., Passat, N., Luz Alves, W.A., Hashimoto, R.F.: Efficient component-hypertree construction based on hierarchy of partitions. Pattern Recogn. Lett. 135, 30–37 (2020)
Moschini, U., Meijster, A., Wilkinson, M.H.F.: A hybrid shared-memory parallel max-tree algorithm for extreme dynamic-range images. IEEE Trans. Pattern Anal. Mach. Intell. 40, 513–526 (2018)
Najman, L., Schmitt, M.: Geodesic saliency of watershed contours and hierarchical segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 18, 1163–1173 (1996)
Najman, L., Talbot, H. (eds.): Mathematical Morphology: From Theory to Applications. ISTE/J. Wiley, Hoboken (2010)
Ngo, P., Passat, N., Kenmochi, Y., Debled-Rennesson, I.: Geometric preservation of 2D digital objects under rigid motions. J. Math. Imaging Vis. 61, 204–223 (2019)
Ngo, P., Passat, N., Kenmochi, Y., Talbot, H.: Topology-preserving rigid transformation of 2D digital images. IEEE Trans. Image Process. 23, 885–897 (2014)
Osgood, W.F.: On the existence of the Green’s function for the most general simply connected plane region. Trans. Am. Math. Soc. 1, 310–314 (1900)
Passat, N., Kenmochi, Y.: A topological tree of shapes. In: DGMM, Discrete Geometry and Mathematical Morphology, Proceedings. Lecture Notes in Computer Science, vol. 13493, pp. 221–235. Springer (2022)
Passat, N., Kenmochi, Y., Ngo, P., Pluta, K.: Rigid motions in the cubic grid: A discussion on topological issues. In: DGCI, Discrete Geometry for Computer Imagery, Proceedings. Lecture Notes in Computer Science, vol. 11414, pp. 127–140. Springer (2019)
Passat, N., Mazo, L.: An introduction to simple sets. Pattern Recogn. Lett. 30, 1366–1377 (2009)
Passat, N., Naegel, B.: Component-hypertrees for image segmentation. In: ISMM, International Symposium on Mathematical Morphology, Proceedings. Lecture Notes in Computer Science, vol. 6671, pp. 284–295. Springer (2011)
Passat, N., Naegel, B., Kurtz, C.: Component-graph construction. J. Math. Imaging Vis. 61, 798–823 (2019)
Passat, N., Naegel, N.: Component-trees and multivalued images: structural properties. J. Math. Imaging Vis. 49, 37–50 (2014)
Perret, B., Chierchia, G., Cousty, J., Ferzoli Guimarães, S.J., Kenmochi, Y., Najman, L.: Higra: hierarchical graph analysis. SoftwareX 10, 100335 (2019)
Perret, B., Cousty, J., Tankyevych, O., Talbot, H., Passat, N.: Directed connected operators: asymmetric hierarchies for image filtering and segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 37, 1162–1176 (2015)
Perret, B., Lefèvre, S., Collet, C., Slezak, É.: Hyperconnections and hierarchical representations for grayscale and multiband image processing. IEEE Trans. Image Process. 21, 14–27 (2012)
Randrianasoa, J.F., Kurtz, C., Desjardin, E., Passat, N.: Binary partition tree construction from multiple features for image segmentation. Pattern Recogn. 84, 237–250 (2018)
Ronse, C.: Set-theoretical algebraic approaches to connectivity in continuous or digital spaces. J. Math. Imaging Vis. 8, 41–58 (1998)
Ronse, C.: Partial partitions, partial connections and connective segmentation. J. Math. Imaging Vis. 32, 97–125 (2008)
Ronse, C.: A topological characterization of thinning. Theor. Comput. Sci. 43, 31–41 (1986)
Rosenfeld, A.: Adjacency in digital pictures. Inf. Control 26, 24–33 (1974)
Rosenfeld, A.: Digital topology. Am. Math. Mon. 86, 621–630 (1979)
Rosenfeld, A.: Fuzzy digital topology. Inf. Control 40, 76–87 (1979)
Salembier, P., Garrido, L.: Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. IEEE Trans. Image Process. 9, 561–576 (2000)
Salembier, P., Oliveras, A., Garrido, L.: Anti-extensive connected operators for image and sequence processing. IEEE Trans. Image Process. 7, 555–570 (1998)
Salembier, P., Serra, J.: Flat zones filtering, connected operators, and filters by reconstruction. IEEE Trans. Image Process. 4, 1153–1160 (1995)
Santana Maia, D., Cousty, J., Najman, L., Perret, B.: Characterization of graph-based hierarchical watersheds: theory and algorithms. J. Math. Imaging Vis. 62, 627–658 (2020)
Soille, P.: Constrained connectivity for hierarchical image decomposition and simplification. IEEE Trans. Pattern Anal. Mach. Intell. 30, 1132–1145 (2008)
Song, Y., Zhang, A.: Monotonic tree. In: DGCI, Discrete Geometry for Computer Imagery, Proceedings. Lecture Notes in Computer Science, vol. 2301, pp. 114–123. Springer (2002)
Tochon, G., Dalla Mura, M., Veganzones, M.A., Géraud, T., Chanussot, J.: Braids of partitions for the hierarchical representation and segmentation of multimodal images. Pattern Recogn. 95, 162–172 (2019)
Woodard, D.W.: On two-dimensional analysis situs with special reference to the Jordan curve theorem. Fundam. Math. 13, 121–145 (1929)
Yau, M.M., Srihari, S.N.: A hierarchical data structure for multidimensional digital images. Commun. ACM 26, 504–515 (1983)