Abstract
Component-trees are hierarchical structures developed in the framework of mathematical morphology. They model images via the inclusion relationships between the connected components of their successive threshold sets. There exist many variants of component-trees, but to the best of our knowledge, none of them deals with the representation of the image at different scales. In this article, we propose such a variant of component-tree that tackles this issue, namely the Multi-Scale Component-Tree (MSCT). We describe an algorithmic scheme for building the MSCT from the standard computation of component-trees of the image, seen from its lowest to its highest scale. At each step, a local upscaling is performed on relevant parts of the image, corresponding to nodes of the MSCT which are selected according to a stability analysis. The last step builds elements which are part of the standard component-tree (at the highest, native scale of the image). The MSCT provides a compact, efficient representation of images compared to the standard (single-scale) component-tree. In particular, the MSCT is especially suited to analyse images containing sparse objects, which require to be represented at a high scale, vs. large background regions that can be losslessly represented at a lower scale. We illustrate the relevance of the MSCT in the context of cellular image segmentation.
This work was supported by the French Agence Nationale de la Recherche (ArtIC, Grant ANR-20-THIA-0006, and Grant ANR-23-CE45-0015).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Although we only consider integer values, Najman and Couprie’s algorithm uses Tarjan’s Union-Find method and is able to efficiently process floating-point values as well.
- 2.
References
Berger, C., Géraud, T., Levillain, R., Widynski, N., Baillard, A., Bertin, E.: Effective component tree computation with application to pattern recognition in astronomical imaging. In: ICIP, pp. 41–44 (2007)
Blin, N., Carlinet, E., Lemaitre, F., Lacassagne, L., Geraud, T.: Max-tree computation on GPUs. IEEE Trans. Parallel Distrib. Syst. 33, 3520–3531 (2022)
Bosilj, P., Duckett, T., Cielniak, G.: Connected attribute morphology for unified vegetation segmentation and classification in precision agriculture. Comput. Ind. 98, 226–240 (2018)
Breen, E.J., Jones, R.: Attribute openings, thinnings, and granulometries. Comput. Vis. Image Underst. 64(3), 377–389 (1996)
Carlinet, E., Géraud, T.: A comparative review of component tree computation algorithms. IEEE Trans. Image Process. 23, 3885–3895 (2014)
Gazagnes, S., Wilkinson, M.H.F.: Distributed component forests in 2-D: hierarchical image representations suitable for tera-scale images. Int. J. Pattern Recogn. Artif. Intell. 33, 1940012 (2019)
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ötz, M., Cavallaro, G., Géraud, T., Book, M., Riedel, M.: Parallel computation of component trees on distributed memory machines. IEEE Trans. Parallel Distrib. Syst. 29, 2582–2598 (2018)
Guigues, L., Cocquerez, J.P., Le Men, H.: Scale-sets image analysis. Int. J. Comput. Vis. 68, 289–317 (2006)
Hartigan, J.A.: Statistical theory in clustering. J. Classif. 2, 63–76 (1985)
Jones, R.: Connected filtering and segmentation using component trees. Comput. Vis. Image Underst. 75, 215–228 (1999)
Kurtz, C., Naegel, B., Passat, N.: Connected filtering based on multivalued component-trees. IEEE Trans. Image Process. 23, 5152–5164 (2014)
Matas, J., Chum, O., Urban, M., Pajdla, T.: Robust wide-baseline stereo from maximally stable extremal regions. Image Vis. Comput. 22, 761–767 (2004)
Meyer, C., Baudrier, É., Schultz, P., Naegel, B.: Combining max-tree and CNN for segmentation of cellular FIB-SEM images. In: Kerautret, B., Colom, M., Krähenbühl, A., Lopresti, D., Monasse, P., Perret, B. (eds.) RRPR 2022. LNCS, vol. 14068, pp. 77–90. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-40773-4_7
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., Couprie, M.: Building the component tree in quasi-linear time. IEEE Trans. Image Process. 15, 3531–3539 (2006)
Passat, N., Mendes Forte, J., Kenmochi, Y.: Morphological hierarchies: a unifying framework with new trees. J. Math. Imaging Vis. 65(5), 718–753 (2023)
Passat, N., Naegel, B.: Component-hypertrees for image segmentation. In: Soille, P., Pesaresi, M., Ouzounis, G.K. (eds.) ISMM 2011. LNCS, vol. 6671, pp. 284–295. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21569-8_25
Passat, N., Naegel, N.: Component-trees and multivalued images: structural properties. J. Math. Imaging Vis. 49, 37–50 (2014)
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)
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)
Wilkinson, M.H.F., Westenberg, M.A.: Shape preserving filament enhancement filtering. In: Niessen, W.J., Viergever, M.A. (eds.) MICCAI 2001. LNCS, vol. 2208, pp. 770–777. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45468-3_92
Xu, Y., Géraud, T., Najman, L.: Connected filtering on tree-based shape-spaces. IEEE Trans. Pattern Anal. Mach. Intell. 38, 1126–1140 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Perrin, R., Leborgne, A., Passat, N., Naegel, B., Wemmert, C. (2024). Multi-scale Component-Tree: A Hierarchical Representation for Sparse Objects. In: Brunetti, S., Frosini, A., Rinaldi, S. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2024. Lecture Notes in Computer Science, vol 14605. Springer, Cham. https://doi.org/10.1007/978-3-031-57793-2_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-57793-2_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-57792-5
Online ISBN: 978-3-031-57793-2
eBook Packages: Computer ScienceComputer Science (R0)