nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

An Updated Review on Watershed Algorithms

verfasst von : R. Romero-Zaliz, J.F. Reinoso-Gordo

Erschienen in: Soft Computing for Sustainability Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Watershed identification is one of the main areas of study in the field of topography. It is critical in countless applications including sustainability and flood risk evaluation. Beyond its original conception, the watershed algorithm has proved to be a very useful and powerful tool in many different applications beside topography, such as image segmentation. Although there are a few publications reviewing the state-of-the-art of watershed algorithms, they are now outdated. In this chapter we review the most important works done on watershed algorithms, including the problem over-segmentation and parallel approaches. Open problems and future work are also investigated.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Fault Diagnosis in a Steam Generator Applying Fuzzy Clustering Techniques

Nächstes Kapitel An Application Sample of Machine Learning Tools, Such as SVM and ANN, for Data Editing and Imputation

Ancin, H., Roysam, B., Dufresne, T., Chestnut, M., Ridder, G., Szarowski, D., Turner, J.: Advances in automated 3-d image analysis of cell populations imaged by confocal microscopy. Cytometry 25(3), 221–234 (1996)CrossRef

Andreatta, S., Wallinger, M., Posch, T., Psenner, R.: Detection of subgroups from flow cytometry measurements of heterotrophic bacterioplankton by image analysis. Cytometry 44(3), 218–225 (2001)CrossRef

Angel Viji, K., Jayakumari, J.: Performance evaluation of standard image segmentation methods and clustering algorithms for segmentation of mri brain tumor images. Euro. J. Sci. Res. 79(2), 166–179 (2012)

Arslan, S., Ozyurek, E., Gunduz-Demir, C.: A color and shape based algorithm for segmentation of white blood cells in peripheral blood and bone marrow images. Cytometry Part A 85(6), 480–490 (2014)CrossRef

Barriuso, P.Q., Heras, D., Argüello, F.: Efficient gpu asynchronous implementation of a watershed algorithm based on cellular automata, pp. 79–86, (2012)

Becattini, G., Mattos, L., Caldwell, D.: A novel framework for automated targeting of unstained living cells in bright field microscopy. pp. 195–198 (2011)

Beucher, S., Bilodeau, M.: Road segmentation and obstacle detection by a fast watershed transformation. pp. 296–301 (1994)

Beucher, S., Lantuéjoul, C.: Use of watersheds in contour detection. workshop published (1979)

Beucher, S., Meyer, F.: The morphological approach to segmentation: the watershed transformation. mathematical morphology in image processing. Opt. Eng. 34, 433–481 (1993)

10.

Bieniecki, W.: Oversegmentation avoidance in watershed-based algorithms for color images. pp. 169–172 (2004)

11.

Bieniek, A., Moga, A.: An efficient watershed algorithm based on connected components. Pattern Recognit. 33(6), 907–916 (2000)CrossRef

12.

Bullet, J., Gaujoux, T., Borderie, V., Bloch, I., Laroche, L.: A reproducible automated segmentation algorithm for corneal epithelium cell images from in vivo laser scanning confocal microscopy. Acta Ophthalmol. 92(4), e312–e316 (2014)CrossRef

13.

Camilus, K., Govindan, V., Sathidevi, P.: Pectoral muscle identification in mammograms. J. Appl. Clin. Med. Phys. 12(3), 215–230 (2011)CrossRef

14.

Chen, L.-C., Nguyen, T.-H., Lin, S.-T.: Viewpoint-independent 3d object segmentation for randomly stacked objects using optical object detection. Meas. Sci. Technol. 26(10) (2015)

15.

Chen, T.: Gushing and immersion alternative watershed algorithm, pp. 246–248 (2001)

16.

Cheng, J.-Z., Chen, K.-W., Chou, Y.-H., Chen, C.-M.: Cell-Based Image Partition and Edge Grouping: A Nearly Automatic Ultrasound Image Segmentation Algorithm for Breast Cancer Computer Aided Diagnosis. vol. 6915 (2008)

17.

Chien, S.-Y., Chen, L.-G.: Reconfigurable morphological image processing accelerator for video object segmentation. J. Signal Process. Syst. 62(1), 77–96 (2011)CrossRef

18.

Christ, M.., Parvathi, R.: Segmentation of medical image using clustering and watershed algorithms. Am. J. Appl. Sci. 8(12), 1349–1352 (2011)

19.

Chung, K.-L., Lai, Y.-S., Huang, P.-L.: An efficient predictive watershed video segmentation algorithm using motion vectors. J. Inf. Sci. Eng. 26(2), 699–711 (2010)

20.

Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: Minimum spanning forests and the drop of water principle. IEEE Trans. Pattern Anal. Mach. Intell. 31(8), 1362–1374 (2009)CrossRef

21.

De Smet, P., Pires, R.L.V.: Implementation and analysis of an optimized rainfalling watershed algorithm. SPIE Int. Soc. Opt. Eng. 3974, 759–766 (2000)

22.

Digabel, H., Lantuejoul, C.: Iterative algorithms. pp. 85–89 (1978)

23.

Dubey, R., Hanmandlu, M., Gupta, S.: A comparison of two methods for the segmentation of masses in the digital mammograms. Comput. Med. Imaging Graph. 34(3), 185–191 (2010)CrossRef

24.

Elsalamony, H.: Detecting distorted and benign blood cells using the hough transform based on neural networks and decision trees. In: Deligiannidis, L., Arabnia, H. (eds.) Emerging Trends in Image Processing, Computer Vision and Pattern Recognition, pp. 457–473 (2014)

25.

Gao, H., Xue, P., Lin, W.: A new marker-based watershed algorithm. vol. 2, pp. II81–II84 (2004)

26.

Gao, L., Yang, S., Xia, J., Liang, J., Qin, Y.: A new marker-based watershed algorithm (2007)

27.

Gies, V., Bernard, T.: Statistical solution to watershed over-segmentation. Int. Conf. Image Process. 3, 1863–1866 (2004)

28.

Guo, Z., Xin, Y., Liu, S., Lv, X., Li, S.: Comparisons of fat quantification methods based on mri segmentation, pp. 1817–1821 (2014)

29.

Hagyard, D., Razaz, M., Atkin, P.: Analysis of watershed algorithms for greyscale images. Proc. 3rd IEEE Int. Conf. Image Process. 3, 41–44 (1996)CrossRef

30.

Held, C., Wenzel, J., Webel, R., Marschall, M., Lang, R., Palmisano, R., Wittenberg, T.: Using multimodal information for the segmentation of fluorescent micrographs with application to virology and microbiology. In: Conference proceedings : ... Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Conference, pp. 6487–6490 (2011)

31.

Hucko, M., Srámek, M.: Streamed watershed transform on gpu for processing of large volume data, pp. 137–141 (2012)

32.

Idbraim, S., Mammass, D., Aboutajdine, D., Ducrot, D.: An automatic system for urban road extraction from satellite and aerial images. WSEAS Trans. Signal Process. 4(10), 563–572 (2008)

33.

Ikedo, Y., Fukuoka, D., Hara, T., Fujita, H., Takada, E., Endo, T., Morita, T.: Development of a fully automatic scheme for detection of masses in whole breast ultrasound images. Med. Phys. 34(11), 4378–4388 (2007)CrossRef

34.

Jabid, T., Mohammad, T., Ahsan, T., Abdullah-Al-Wadud, M., Chae, O.: An edge-texture based moving object detection for video content based application. pp. 112–116 (2011)

35.

Jiafu, L., Yan, L., Wenfeng, Z., Jing, L.: Storm floods risk assessments by ga-bp: a case study of seven countries in Asia. Int. J. Adv. Comput. Technol. 3(10), 323–329 (2011)

36.

Jianhua, L., Shuang, W., Licheng, J.: Method to reduce over-segmentation of images using immune clonal algorithm. vol. 6786 (2007)

37.

Jouini, M., Vega, S., Mokhtar, E.: Multiscale characterization of pore spaces using multifractals analysis of scanning electronic microscopy images of carbonates. Nonlinear Process. Geophys. 18(6), 941–953 (2011)CrossRef

38.

JW, L., JA, D.: Optimal identification of lumped watershed models. Water Resour. Res. 5(3), 583–590 (1969)CrossRef

39.

Kauffmann, C., Piche, N.: A cellular automaton for ultra-fast watershed transform on gpu (2008)

40.

Kekre, H., Sarode, T., Gharge, S.: Vector quantization for tumor demarcation of mammograms. Commun. Comput. Inf. Sci. 70, 157–163 (2010)

41.

Kollorz, E., Angelopoulou, E., Beck, M., Schmidt, D., Kuwert, T.: Using power watersheds to segment benign thyroid nodules in ultrasound image data, pp. 124–128 (2011)

42.

Kong, J., Cooper, L., Kurc, T., Brat, D., Saltz, J.: Towards building computerized image analysis framework for nucleus discrimination in microscopy images of diffuse glioma, pp. 6605–6608 (2011)

43.

Körbes, A., Lotufo, R.: Analysis of the watershed algorithms based on the breadth-first and depth-first exploring methods. pp. 133–140 (2009)

44.

Körbes, A., Vitor, G., De Alencar Lotufo, R., Ferreira, J.: Advances on watershed processing on gpu architecture. In: Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence. Lecture Notes in Bioinformatics, vol. 6671, pp. 260–271, LNCS (2011)

45.

Linguraru, M., Howe, R.: Texture-based instrument segmentation in 3d ultrasound images, vol. 6144 II (2006)

46.

Liu, J., Chen, K.: Novel method of mri medical image segmentation combining watershed algorithm and wkfcm algorithm. Appl. Mech. Mater. 121–126, 4518–4522 (2012)

47.

Lotufo, R., Falcao, A.: The ordered queue and the optimality of the watershed approaches. Math. Morphol. Appl. Image Signal Process. 18, 341–350 (2000)CrossRefMATH

48.

Mahmoudi, R., Akil, M.: Real time topological image smoothing on shared memory parallel machines, vol. 7871 (2011)

49.

Malpica, N., De Solórzano, C., Vaquero, J., Santos, A., Vallcorba, I., García-Sagredo, J., Del Pozo, F.: Applying watershed algorithms to the segmentation of clustered nuclei. Cytometry 28(4), 289–297 (1997)CrossRef

50.

Mei, T., Li, D., Qin, Q.: Application of knowledge based watershed transform approach to road detection, vol. 6045 II (2005)

51.

Meijster, A., Roerdink, J.B.T.M.: A disjoint set algorithm for the watershed transform. In: Proceedings EUSIPCO ’98, IX European Signal Processing Conference, pp. 1665–1668 (1998)

52.

Mendonca, A.S., Rezende, R.A.: Application of geographical information systems and stochastic hydrology to the siting and design of water reservoirs. In: International Geoscience and Remote Sensing Symposium. IGARSS’99, vol. 2, pp. 1220–1222 (1999)

53.

Meyer, F.: Topographic distance and watershed lines. Signal Process. 38(1), 113–125 (1994)CrossRefMATH

54.

Moga, A., Cramariuc, B., Gabbouj, M.: Parallel watershed transformation algorithms for image segmentation. Parallel Comput. 24(14), 1981–2001 (1998)CrossRef

55.

Moga, A., Gabbouj, M.: Parallel marker-based image segmentation with watershed transformation. J. Parallel Distrib. Comput. 51(1), 27–45 (1998)CrossRefMATH

56.

Mohan, E., Sugumaran, R., Venkatachalam, K.: Automatic brain and tumor segmentation in mri using fuzzy classification with integrated bayesian model. Int. J. Appl. Eng. Res. 9(24), 25859–25870 (2014)

57.

Mortensen, E.N., Barrett, W.A.: Toboggan-based intelligent scissors with a four-parameter edge model. In: CVPR, IEEE Computer Society, pp. 2452–2458 (1999)

58.

Moumoun, L., El Far, M., Chahhou, M., Gadi, T., Benslimane, R.: Solving the 3d watershed over-segmentation problem using the generic adjacency graph (2010)

59.

Muzylev, E., Uspensky, A.: Modelling the Hydrological Cycle of River Basins Using High Resolution Satellite Information, pp. 241–248. IAHS-AISH Publication, Wallingford (2001)

60.

Najman, L., Couprie, M.: Watershed algorithms and contrast preservation. In: Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 2886, pp. 62–71 (2003)

61.

Nithya, A., Kayalvizhi, R.: Extended fuzzy switching median filter and morphological algorithm for medical image segmentation. ARPN J. Eng. Appl. Sci. 10(1), 80–90 (2015)

62.

Noguet, D.: Massively parallel implementation of the watershed based on cellular automata, pp. 42–52 (1997)

63.

Osma-Ruiz, V., Godino-Llorente, J., Sáenz-Lechón, N., Gómez-Vilda, P.: An improved watershed algorithm based on efficient computation of shortest paths. Pattern Recognit. 40(3), 1078–1090 (2007)CrossRefMATH

64.

Patino, L.: Fuzzy relations applied to minimize over segmentation in watershed algorithms. Pattern Recognit. Lett. 26(6), 819–828 (2005)CrossRef

65.

Peng, B., Xu, A., Li, H., Han, Y.: Road extraction based on object-oriented from high-resolution remote sensing images (2011)

66.

Perry, E., Norton, S., Kamman, N., Lorey, P., Driscoll, C.: Deconstruction of historic mercury accumulation in lake sediments, Northeastern United States. Ecotoxicology 14(1–2), 85–99 (2005)CrossRef

67.

Plaza, A., Plaza, J., Valencia, D., Martinez, P.: Parallel segmentation of multi-channel images using multi-dimensional mathematical morphology (2008)

68.

Procházka, A., Vysata, O., Jerhotova, E.: Wavelet use for reduction of watershed transform over-segmentation in biomedical images processing (2010)

69.

Rambabu, C., Rathore, T., Chakrabarti, I.: A new watershed algorithm based on hillclimbing technique for image segmentation. In: TENCON 2003. Conference on Convergent Technologies for Asia-Pacific Region, vol. 4, pp. 1404–1408 (2003)

70.

Rambabu, C., Chakrabarti, I.: An efficient hillclimbing-based watershed algorithm and its prototype hardware architecture. J. Signal Process. Syst. 52(3), 281–295 (2008)CrossRef

71.

Randhir, T., Lee, J., Engel, B.: Multiple criteria dynamic spatial optimization to manage water quality on a watershed scale. Trans. Am. Soc. Agric. Eng. 43(2), 291–299 (2000)CrossRef

72.

Roerdink, J., Meijster, A.: The watershed transform: definitions, algorithms and parallelization strategies. Fundamenta Informaticae 41(1–2), 187–228 (2000)MathSciNetMATH

73.

Rong, J., Pan, Y.-L.: Accuracy improvement of graph-cut image segmentation by using watershed. Adv. Mater. Res. 341–342, 546–549 (2012)

74.

Shen, W.-C., Chang, R.-F.: A nearest neighbor graph based watershed algorithm, pp. 6300–6303 (2005)

75.

Sheshadri, H., Kandaswamy, A.: Application of watershed algorithms to mammogram image analysis. IETE Tech. Rev. 23(3), 173–178 (2006)CrossRef

76.

Shrimali, V., Anand, R., Kumar, V.: Current trends in segmentation of medical ultrasound b-mode images: a review. IETE Tech. Rev. 26(1), 8–17 (2009)CrossRef

77.

Sinha, K., Sinha, G.: Efficient segmentation methods for tumor detection in mri images (2014)

78.

Smistad, E., Falch, T., Bozorgi, M., Elster, A., Lindseth, F.: Medical image segmentation on gpus - a comprehensive review. Med. Image Anal. 20(1), 1–18 (2015)CrossRef

79.

Sridhar, B., Reddy, K., Prasad, A.: An artificial neural network and mathematical morphology based computer aided detection system for cancer detection in mammograms. Int. J. Appl. Eng. Res. 9(23), 21079–21097 (2014)

80.

Su, H., Yang, Z.-L., Dickinson, R., Wilson, C., Niu, G.-Y.: Multisensor snow data assimilation at the continental scale: the value of gravity recovery and climate experiment terrestrial water storage information. J. Geophys. Res. Atmospheres 115(10) (2010)

81.

Sun, H., Yang, J., Ren, M.: A fast watershed algorithm based on chain code and its application in image segmentation. Pattern Recognit. Lett. 26(9), 1266–1274 (2005)CrossRef

82.

Świercz, M., Iwanowski, M.: Fast, parallel watershed algorithm based on path tracing. In: Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 6375, pp. 317–324, LNCS(PART 2) (2010)

83.

Swiercz, M., Iwanowski, M.: Waterball-iterative watershed algorithm with reduced oversegmentation. Adv. Intell. Soft Comput. 95(4), 385–394 (2011)

84.

Tolosa, S., Blacher, S., Denis, A., Marajofsky, A., Pirard, J.-P., Gommes, C.: Two methods of random seed generation to avoid over-segmentation with stochastic watershed: application to nuclear fuel micrographs. J. Microsc. 236(1), 79–86 (2009)MathSciNetCrossRef

85.

Tonti, S., Di Cataldo, S., Bottino, A., Ficarra, E.: An automated approach to the segmentation of hep-2 cells for the indirect immunofluorescence ana test. Comput. Med. Imaging Graph. 40, 62–69 (2015)CrossRef

86.

Tung, C.-P.: Climate change impacts on water resources of the tsengwen creek watershed in Taiwan. J. Am. Water Resour. Assoc. 37(1), 167–176 (2001)CrossRef

87.

Uchida, S.: Image processing and recognition for biological images. Dev. Growth Differ. 55(4), 523–549 (2013)CrossRef

88.

Van Neerbos, J., Najman, L., Wilkinson, M.: Towards a parallel topological watershed: First results. In: Lecture Notes in Computer Science Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 6671, pp. 248–259, LNCS (2011)

89.

Vibha, L., Harshavardhan, G., Pranaw, K., Shenoy, P., Venugopal, K., Patnaik, L.: Lesion detection using segmentation and classification of mammograms, pp. 311–316(2007)

90.

Vincent, L., Soille, P.: Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Trans. Pattern Anal. Mach. Intell. 13(6), 583–598 (1991)CrossRef

91.

Wagner, B., Dinges, A., Müller, P., Haase, G.: Parallel volume image segmentation with watershed transformation. In: Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 5575, pp. 420–429, LNCS (2009)

92.

Wang, W., Shi, H., Wang, A.: Analysis on the future runoff changes in shiyang river basin based on genetic algorithm models (2012)

93.

Wu, S., Hu, Y.: Parallelization research watershed algorithm 2012, 1524–1527 (2012)

94.

Xu, G., Zhang, D., Liu, X.: Road extraction in high resolution images from google earth (2009)

95.

Yang, F., Li, J., Xu, S.-H., Pan, G.-F.: The research of video segmentation algorithm based on image fusion in the wavelet domain, vol. 7659 (2010)

96.

Yu, P.-Y., Zhang, G.-P., Yan, J.-W., Liu, M.-S.: The application of the watershed algorithm based on line-encoded in lung ct image segmentation (2011)

97.

Zhang, X., Chen, L., Pan, L., Xiong, L.: Study on the image segmentation based on ica and watershed algorithm, pp. 505–508 (2012)

98.

Zhang, X., Cheng, Y., Qian, Y., Zhuang, X.: Automatic video object segmentation based on spatio-temporal information, pp. 5314–5317 (2011)

99.

Zhu, H., Zhang, B., Song, A., Zhang, W.: An improved method to reduce over-segmentation of watershed transformation and its application in the contour extraction of brain image, pp. 407–412 (2009)

Titel: An Updated Review on Watershed Algorithms
verfasst von: R. Romero-Zaliz
J.F. Reinoso-Gordo
Verlag: Springer International Publishing
Buch: Soft Computing for Sustainability Science
Print ISBN: 978-3-319-62358-0

Electronic ISBN: 978-3-319-62359-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-62359-7_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner