Abstract
This paper revisits the construction of watershed and waterfall hierarchies through a thorough analysis of Boruvka’s algorithms for constructing minimum spanning trees of edge weighted graphs. In the case where the watershed of a node weighted graph is to be constructed, we propose a distribution of weights on the edges, so that the waterfall extraction on the edge weighted graph becomes equivalent with the watershed extraction on the node weighted graph.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Allène, C., Audibert, J., Couprie, M., Cousty, J., Keriven, R.: Some links between min-cuts, optimal spanning forests and watersheds. In: Proceedings of the The 8th International Symposium on Mathematical Morphology, Rio de Janeiro, Brazil, vol. 1, pp. 253–264 (2007)
Audigier, R., Lotufo, R.A.: Watershed by image foresting transform, tie-zone, and theoretical relationships with other watershed definitions. In: Proceedings of the The 8th International Symposium on Mathematical Morphology, Rio de Janeiro, Brazil, vol. 1, pp. 277–288 (2007)
Stawiaski, J.: Mathematical morphology and graphs: Application to interactive medical image segmentation. PhD Thesis. Mines ParisTech. (2008)
Meyer, F.: Grey-weighted, ultrametric and lexicographical distances. In: Computational Imaging and Vision, Mathematical Morphology: 40 Years On. Proceedings of the 7th International Symposium on Mathematical Morphology, vol. 30, pp. 289–298 (2005)
Marcotegui, B., Beucher, S.: Fast implementation of waterfall based on graphs. In: Ronse, C., Najman, L., Decencière, E. (eds.) Mathematical Morphology: 40 Years on: Proc. 7th ISMM, Paris, pp. 177–186. Springer, Heidelberg (2005)
Falcao, A., Stolfi, J., Lotufo, R.: The image foresting transform: Theory, algorithms, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 19–29 (2004)
Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: minimum spanning forests, and the drop of water principle. IEEE Trans. on Pattern Analysis and Machine Intelligence (2008) (to appear)
Beucher, S.: Segmentation d’images et morphologie mathématique. PhD thesis, Ecole des Mines de Paris, Paris (June 1990)
Beucher, S.: Watershed, hierarchical segmentation and waterfall algorithm. In: Serra, J., Soille, P. (eds.) Mathematical Morphology and its applications to signal processing (Proceedings ISMM 1994), Fontainebleau, France, pp. 69–76. Kluwer Academic Publishers, Dordrecht (1994)
Angulo, J., Jeulin, D.: Stochastic watershed segmentation. In: Proceedings of the The 8th International Symposium on Mathematical Morphology, Rio de Janeiro, Brazil, vol. 1, pp. 265–276 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meyer, F., Stawiaski, J. (2009). Morphology on Graphs and Minimum Spanning Trees. In: Wilkinson, M.H.F., Roerdink, J.B.T.M. (eds) Mathematical Morphology and Its Application to Signal and Image Processing. ISMM 2009. Lecture Notes in Computer Science, vol 5720. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03613-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-03613-2_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03612-5
Online ISBN: 978-3-642-03613-2
eBook Packages: Computer ScienceComputer Science (R0)