Abstract
We study three representations of hierarchies of partitions: dendrograms (direct representations), saliency maps, and minimum spanning trees. We provide a new bijection between saliency maps and hierarchies based on quasi-flat zones as used in image processing and characterize saliency maps and minimum spanning trees as solutions to constrained minimization problems where the constraint is quasi-flat zones preservation. In practice, these results form a toolkit for new hierarchical methods where one can choose the most convenient representation. They also invite us to process non-image data with morphological hierarchies.
This work received funding from ANR (contract ANR-2010-BLAN-0205-03), CAPES/PVE (grant 064965/2014-01), and CAPES/COFECUB (grant 592/08).
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. PAMI 33(5), 898–916 (2011)
Bender, M., Farach-Colton, M.: The LCA problem revisited. In: Latin American Theoretical INformatics, pp. 88–94 (2000)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction to algorithms, vol. 2. MIT Press, Cambridge (2001)
Couprie, M., Najman, L., Bertrand, G.: Quasi-linear algorithms for the topological watershed. JMIV 22(2-3), 231–249 (2005)
Cousty, J., Najman, L.: Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. In: Soille, P., Pesaresi, M., Ouzounis, G.K. (eds.) ISMM 2011. LNCS, vol. 6671, pp. 272–283. Springer, Heidelberg (2011)
Cousty, J., Najman, L., Perret, B.: Constructive links between some morphological hierarchies on edge-weighted graphs. In: Hendriks, C.L.L., Borgefors, G., Strand, R. (eds.) ISMM 2013. LNCS, vol. 7883, pp. 86–97. Springer, Heidelberg (2013)
Felzenszwalb, P., Huttenlocher, D.: Efficient graph-based image segmentation. IJCV 59, 167–181 (2004)
Guigues, L., Cocquerez, J.P., Men, H.L.: Scale-sets image analysis. IJCV 68(3), 289–317 (2006)
Guimarães, S.J.F., Cousty, J., Kenmochi, Y., Najman, L.: A hierarchical image segmentation algorithm based on an observation scale. In: Gimel’farb, G., et al. (eds.) SSPR & SPR 2012. LNCS, vol. 7626, pp. 116–125. Springer, Heidelberg (2012)
Kiran, B.R., Serra, J.: Scale space operators on hierarchies of segmentations. In: Kuijper, A., Bredies, K., Pock, T., Bischof, H. (eds.) SSVM 2013. LNCS, vol. 7893, pp. 331–342. Springer, Heidelberg (2013)
Leclerc, B.: Description combinatoire des ultramétriques. Mathématiques et Sciences Humaines 73, 5–37 (1981)
Meyer, F., Maragos, P.: Morphological scale-space representation with levelings. In: Nielsen, M., Johansen, P., Fogh Olsen, O., Weickert, J. (eds.) Scale-Space 1999. LNCS, vol. 1682, pp. 187–198. Springer, Heidelberg (1999)
Najman, L.: On the equivalence between hierarchical segmentations and ultrametric watersheds. JMIV 40(3), 231–247 (2011)
Najman, L., Cousty, J.: A graph-based mathematical morphology reader. PRL 47(1), 3–17 (2014)
Najman, L., Cousty, J., Perret, B.: Playing with kruskal: Algorithms for morphological trees in edge-weighted graphs. In: Hendriks, C.L.L., Borgefors, G., Strand, R. (eds.) ISMM 2013. LNCS, vol. 7883, pp. 135–146. Springer, Heidelberg (2013)
Nakache, J.P., Confais, J.: Approche pragmatique de la classification: arbres hiérarchiques, partitionnements. Editions Technip (2004)
Kiran, B.R., Serra, J.: Global–local optimizations by hierarchical cuts and climbing energies. PR 47(1), 12–24 (2014)
Ronse, C.: Ordering partial partitions for image segmentation and filtering: Merging, creating and inflating blocks. JMIV 49(1), 202–233 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Cousty, J., Najman, L., Kenmochi, Y., Guimarães, S. (2015). New Characterizations of Minimum Spanning Trees and of Saliency Maps Based on Quasi-flat Zones. In: Benediktsson, J., Chanussot, J., Najman, L., Talbot, H. (eds) Mathematical Morphology and Its Applications to Signal and Image Processing. ISMM 2015. Lecture Notes in Computer Science(), vol 9082. Springer, Cham. https://doi.org/10.1007/978-3-319-18720-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-18720-4_18
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18719-8
Online ISBN: 978-3-319-18720-4
eBook Packages: Computer ScienceComputer Science (R0)