Home   >   CSC-OpenAccess Library   >    Manuscript Information
Analyses of the Watershed Transform
Ramzi Mahmoudi, Mohamed AKIL
Pages - 521 - 541     |    Revised - 01-11-2011     |    Published - 15-12-2011
Volume - 5   Issue - 5    |    Publication Date - November / December 2011  Table of Contents
MORE INFORMATION
KEYWORDS
Watershed Transform, Flooding, Path-cost Minimization, Topology Preservation, Local Condition, Minimum Spanning Forest
ABSTRACT
In the framework of mathematical morphology, watershed transform (WT) represents a key step in image segmentation procedure. In this paper, we present a thorough analysis of some existing watershed approaches in the discrete case: WT based on flooding, WT based on path-cost minimization, watershed based on topology preservation, WT based on local condition and WT based on minimum spanning forest. For each approach, we present detailed description of processing procedure followed by mathematical foundations and algorithm of reference. Recent publications based on some approaches are also presented and discussed. Our study concludes with a classification of different watershed transform algorithms according to solution uniqueness, topology preservation, prerequisites minima computing and linearity.
CITED BY (2)  
1 Komang, B. (2015). Implementasi Metode Watershed Transformation Dalam Segmentasi Tulisan Aksara Bali Berbasis Histogram. Proceedings Konferensi Nasional Sistem dan Informatika (KNS&I).
2 Li Chunfeng, Jia Hongzhi, & Xie Min. (2013). Based on a new level ridge watershed algorithm optical instruments, (3), 63-69.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
A. X. Falcão, J. Stolfi, and R. A. Lotufo. “The Image Foresting Transform: Theory,Algorithms, and Applications.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, pp.19-29, 2004.
E. Dougherty and R. Lotufo. “Hands-on Morphological Image Processing.” SPIE Publications, 2003.
E.N. Mortensen and W.A. Barrett. “Toboggan-based intelligent scissors with a fourparameter edge model.” In IEEE Conf. Computer Vision and Pattern Recognition, pp. 452–458, 1999.
E.W. Dijkstra. “A Note on Two Problems in Connection with Graphs.” Numeriche Mathematik, vol 1, pp. 269-271, 1959.
F. Meyer. “Minimum Spanning Forests for Morphological Segmentation.” Proc. Second International Conference on Math. Morphology. and Its Applications to Image Processing,pp. 77-84, 1994.
F. Meyer. “Topographic distance and watershed lines.” Signal Processing, vol. 38, pp. 113-125,1993.
J. Cousty, G. Bertrand, L. Najman and M. Couprie. “Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle.” IEEE Transaction on Pattern Analysis and Machine Intelligence, pp. 1362-1374, 2009.
J. Maxwell. “On hills and dales.” Philosophical Magazine, vol. 4/40, pp. 421-427, Dec. 1870.
J. Serra. “Image Analysis and Mathematical Morphology.” Academic Press, New York,1982.
J.B.T.M. Roerdink and A. Meijster. “The watershed transform: Definitions, algorithms and parallelization strategies.” Fundamenta Informaticae, Special issue on mathematical morphology vol. 41, pp. 187-228, Jan. 2001.
L. Najman and M. Couprie. “Watershed algorithms and contrast preservation.” Lecture Notes in Computer Science, vol. 2886, pp. 62-71, 2003.
L. Najman and M. Schmitt. “Watershed of a continuous function.” Signal Processing, vol.38, pp. 68-86, 1993.
L. Najman, M. Couprie and G. Bertrand. “Watersheds, mosaics and the emergence paradigm.” Discrete Applied Mathematics, vol. 147, pp. 301-324, April 2005.
L. Vincent and P. Soille. “Watersheds in digital spaces - An efficient algorithm based on immersion simulations.” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, pp.583-598, 1991.
M. Couprie and G. Bertrand. “Topological grayscale watersheds transform.” SPIE Vision Geometry V Proceedings, vol. 3168, pp. 136-146, 1997.
M. Couprie, L. Najman and G. Bertrand. “Quasi-linear algorithms for the topological watershed.” Journal of Mathematical Imaging and Vision, vol. 22, pp. 231-249, 2005.
M. Straka, A. La Cruz, A. Köchl, M. Šrámek, E. Gröller and D. Fleischmann. “3D Watershed Transform Combined with a Probabilistic Atlas for Medical Image Segmentation.” Journal of Medical Informatics & Technologies, 2003.
P. Shengcai and G. Lixu. “A Novel Implementation of Watershed Transform Using MultiDegree Immersion Simulation.” 27th Annual International Conference of the Engineering in Medicine and Biology Society, pp. 1754 – 1757, 2005.
P. Soille. “Morphological Image Analysis.” Springer-Verlag Berlin and Heidelberg GmbH & Co. K, April 1999.
R. A. Lotufo and A. X. Falcão. “The Ordered Queue and the Optimality of the Watershed Approaches.” Procs. 5th International Symposium on Mathematical Morphology, pp. 341-350, 2000.
R. Audigier and R.A. Lotufo. “Watershed by image foresting transform, tie-zone, and theoretical relationship with other watershed definitions.” In Mathematical Morphology and its Applications to Signal and Image Processing, pp. 277–288, 2007.
R. B. Dial, F. Glover, D. Karney, and D. Klingman. “A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees.” In Networks, vol 9,pp. 215-248,1979.
R.A. Lotufo, A. X. Falcão and F. A. Zampirolli. “IFT-Watershed from Gray-Scale Marker.”15th Brazilian Symposium on Computer Graphics and Image Processing, Vol 2, 2002.
S. Beucher and C. Lantuéjoul. “Use of watersheds in contour detection.” International Workshop on Image Processing, Real-Time Edge and Motion Detection/ Estimation, 1979.
S. Beucher and F. Meyer. “The morphological approach to segmentation: the watershed transformation.” In Dougherty, E., ed.: Mathematical Morphology in Image Processing, Marcel Decker, pp. 433-481,1993.
U. Pape. “Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem.” Mathematical Programming, vol. 7, pp. 212-222, 1974.
V.O. Ruiz, J.I.G. Llorente, N. S. Lechon and P.G. Vilda. “An improved watershed algorithm based on efficient computation of shortest paths.” Pattern Recognition, vol. 40,pp. 1078-1090, 2007.
Y.C. Lin, Y.P. Tsai, Y.P Hung and Z.C. Shih. “Comparison Between Immersion-Based and Toboggan-Based Watershed Image Segmentation.” 15th IEEE Transactions on Image Processing, vol. 3, pp. 632-640, 2006.
Dr. Ramzi Mahmoudi
ESIEE Engineering - Paris - France
mahmoudr@esiee.fr
Professor Mohamed AKIL
ESIEE Engineering - France