Abstract
Binary partition hierarchies and minimum spanning trees are key structures for numerous hierarchical analysis methods, as those involved in computer vision and mathematical morphology. In this article, we consider the problem of their computation in an out-of-core manner, i.e., by minimizing the size of the data structures that are simultaneously needed at the different computation steps. Out-of-core algorithms are necessary when the data are too large to fit entirely in the main memory of the computer, which can be the case with very large images in 2-, 3-, or higher dimension space. We propose a new algebraic framework composed of four main operations on hierarchies: edge-addition, select, insert, and join. Based on this framework, we propose and establish the correctness of an out-of-core calculus for binary partition hierarchies and for minimum spanning trees. First applications to image processing suggest the practical efficiency of this calculus.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Chierchia, G., Perret, B.: Ultrametric fitting by gradient descent. In: NeurIPS, pp. 3181–3192 (2019)
Cousty, J., Najman, L., Kenmochi, Y., Guimarães, S.: Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps. JMIV 60(4), 479–502 (2018)
Cousty, J., Najman, L., Perret, B.: Constructive links between some morphological hierarchies on edge-weighted graphs. In: ISMM, pp. 86–97 (2013)
Farabet, C., Couprie, C., Najman, L., LeCun, Y.: Learning hierarchical features for scene labeling. TPAMI 35(8), 1915–1929 (2012)
Gazagnes, S., Wilkinson, M.H.: Distributed component forests in 2-D: hierarchical image representations suitable for tera-scale images. IJPRAI 33(11), 1940012 (2019)
Gigli, L., Velasco-Forero, S., Marcotegui, B.: On minimum spanning tree streaming for hierarchical segmentation. PRL 138, 155–162 (2020)
Götz, M., Cavallaro, G., Geraud, T., Book, M., Riedel, M.: Parallel computation of component trees on distributed memory machines. TPDS 29(11), 2582–2598 (2018)
Guimarães, S., Kenmochi, Y., Cousty, J., Patrocinio, Z., Najman, L.: Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity: the case of the Felzenszwalb-Huttenlocher method. MMTA 2(1), 55–75 (2017)
Havel, J., Merciol, F., Lefèvre, S.: Efficient tree construction for multiscale image representation and processing. J. Real-Time Image Proc. 16(4), 1129–1146 (2016). https://doi.org/10.1007/s11554-016-0604-0
Kazemier, J.J., Ouzounis, G.K., Wilkinson, M.H.: Connected morphological attribute filters on distributed memory parallel machines. In: ISMM, pp. 357–368 (2017)
Maninis, K.K., Pont-Tuset, J., Arbeláez, P., Van Gool, L.: Convolutional oriented boundaries: from image segmentation to high-level tasks. TPAMI 40(4), 819–833 (2017)
Najman, L., Cousty, J., Perret, B.: Playing with kruskal: algorithms for morphological trees in edge-weighted graphs. In: ISMM, pp. 135–146 (2013)
Najman, L., Schmitt, M.: Geodesic saliency of watershed contours and hierarchical segmentation. TPAMI 18(12), 1163–1173 (1996)
Perret, B., Cousty, J., Guimarães, S.J.F., Kenmochi, Y., Najman, L.: Removing non-significant regions in hierarchical clustering and segmentation. PRL 128, 433–439 (2019)
Ronse, C.: Partial partitions, partial connections and connective segmentation. JMIV 32(2), 97–125 (2008)
Ronse, C.: Ordering partial partitions for image segmentation and filtering: Merging, creating and inflating blocks. JMIV 49(1), 202–233 (2014)
Salembier, P., Garrido, L.: Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. TIP 9(4), 561–576 (2000)
Soille, P.: Constrained connectivity for hierarchical image partitioning and simplification. TPAMI 30(7), 1132–1145 (2008)
Acknowledgements
This work was partly supported by the ANR under grant ANR-20-CE23-0019.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Cousty, J., Perret, B., Phelippeau, H., Carneiro, S., Kamlay, P., Buzer, L. (2021). An Algebraic Framework for Out-of-Core Hierarchical Segmentation Algorithms. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2021. Lecture Notes in Computer Science(), vol 12708. Springer, Cham. https://doi.org/10.1007/978-3-030-76657-3_27
Download citation
DOI: https://doi.org/10.1007/978-3-030-76657-3_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-76656-6
Online ISBN: 978-3-030-76657-3
eBook Packages: Computer ScienceComputer Science (R0)
