Abstract
Region merging methods consist of improving an initial segmentation by merging some pairs of neighboring regions. We consider a segmentation as a set of connected regions, separated by a frontier. If the frontier set cannot be reduced without merging some regions then we call it a watershed. In a general graph framework, merging two regions is not straightforward. We define four classes of graphs for which we prove that some of the difficulties for defining merging procedures are avoided. Our main result is that one of these classes is the class of graphs in which any watershed is thin. None of the usual adjacency relations on ℤ2 and ℤ3 allows a satisfying definition of merging. We introduce the perfect fusion grid on ℤn, a regular graph in which merging two neighboring regions can always be performed by removing from the frontier set all the points adjacent to both regions.
Chapter PDF
Similar content being viewed by others
References
Rosenfeld, A., Kak, A.: 10. In: Digital picture processing, vol. 2, Academic Press, London (1982); Section 10.4.2.d (region merging)
Pavlidis, T.: 4–5. In: Structural Pattern Recognition. Springer Series in Electrophysics, vol. 1, pp. 90–123. Springer, Heidelberg (1977) (segmentation techniques)
Beucher, S., Lantuéjoul, C.: Use of watersheds in contour detection. In: Procs. Int. Workshop on Image Processing Real-Time Edge and Motion Detection/Estimation (1979)
Vincent, L., Soille, P.: Watersheds in digital spaces: An efficient algorithm based on immersion simulations. PAMI 13(6), 583–598 (1991)
Meyer, F.: Un algorithme optimal de ligne de partage des eaux. In: Actes du 8ème Congrès AFCET, Lyon-Villeurbanne, France, pp. 847–859 (1991)
Couprie, M., Bertrand, G.: Topological grayscale watershed transform. In: SPIE Vision Geometry V Proceedings, vol. 3168, pp. 136–146 (1997)
Bertrand, G.: On topological watersheds. JMIV 22(2-3), 217–230 (2005)
Couprie, M., Najman, L., Bertrand, G.: Quasi-linear algorithms for the topological watershed. JMIV 22(2-3), 231–249 (2005)
Najman, L., Couprie, M., Bertrand, G.: Watersheds, mosaics and the emergence paradigm. DAM 147(2-3), 301–324 (2005)
Jasiobedzki, P., Taylor, C., Brunt, J.: Automated analysis of retinal images. IVC 1(3), 139–144 (1993)
Cousty, J., Bertrand, G., Couprie, M., Najman, L.: Fusion graphs: merging properties and watershed. CVIU (submitted, 2006), also in technical report IGM2005-04, http://igm.univ-mlv.fr/LabInfo/rapportsInternes/2005/04.pdf
Beineke, L.: On derived graphs and digraphs. In: Sachs, H., Voss, H., Walther, H. (eds.) Beiträge zur graphen theorie, pp. 17–23 (1968)
Cousty, J., Couprie, M., Najman, L., Bertrand, G.: Grayscale watersheds on perfect fusion graphs. In: Reulke, R., Eckardt, U., Flach, B., Knauer, U., Polthier, K. (eds.) IWCIA 2006. LNCS, vol. 4040, pp. 60–73. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cousty, J., Bertrand, G., Couprie, M., Najman, L. (2006). Fusion Graphs, Region Merging and Watersheds. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds) Discrete Geometry for Computer Imagery. DGCI 2006. Lecture Notes in Computer Science, vol 4245. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11907350_29
Download citation
DOI: https://doi.org/10.1007/11907350_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-47651-1
Online ISBN: 978-3-540-47652-8
eBook Packages: Computer ScienceComputer Science (R0)