Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(367.03KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Publications from CSC-OpenAccess Library are being accessed from over 74 countries worldwide.
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 
1 J. Maxwell. “On hills and dales.” Philosophical Magazine, vol. 4/40, pp. 421-427, Dec. 1870.
2 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.
3 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.
4 J. Serra. “Image Analysis and Mathematical Morphology.” Academic Press, New York,1982.
5 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.
6 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.
7 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.
8 L. Najman and M. Couprie. “Watershed algorithms and contrast preservation.” Lecture Notes in Computer Science, vol. 2886, pp. 62-71, 2003.
9 P. Soille. “Morphological Image Analysis.” Springer-Verlag Berlin and Heidelberg GmbH & Co. K, April 1999.
10 E. Dougherty and R. Lotufo. “Hands-on Morphological Image Processing.” SPIE Publications, 2003.
11 L. Najman, M. Couprie and G. Bertrand. “Watersheds, mosaics and the emergence paradigm.” Discrete Applied Mathematics, vol. 147, pp. 301-324, April 2005.
12 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.
13 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.
14 F. Meyer. “Topographic distance and watershed lines.” Signal Processing, vol. 38, pp. 113-125,1993.
15 L. Najman and M. Schmitt. “Watershed of a continuous function.” Signal Processing, vol.38, pp. 68-86, 1993.
16 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.
17 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.
18 E.W. Dijkstra. “A Note on Two Problems in Connection with Graphs.” Numeriche Mathematik, vol 1, pp. 269-271, 1959.
19 U. Pape. “Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem.” Mathematical Programming, vol. 7, pp. 212-222, 1974.
20 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.
21 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.
22 M. Couprie and G. Bertrand. “Topological grayscale watersheds transform.” SPIE Vision Geometry V Proceedings, vol. 3168, pp. 136-146, 1997.
23 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.
24 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.
25 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.
26 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.
27 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.
28 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.
Dr. Ramzi Mahmoudi
ESIEE Engineering - Paris - France
mahmoudr@esiee.fr
Professor Mohamed AKIL
ESIEE Engineering - France