{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T15:04:42Z","timestamp":1781103882714,"version":"3.54.1"},"reference-count":35,"publisher":"IGI Global Scientific Publishing","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,10,1]]},"abstract":"<p>This paper proposes and develops a parallel algorithm for the watershed transform, with application on graphics hardware. The existing proposals are discussed and its aspects briefly analysed. The algorithm is proposed as a procedure of four steps, where each step performs a task using different approaches inspired by existing techniques. The algorithm is implemented using the CUDA libraries and its performance is measured on the GPU and compared to a sequential algorithm running on the CPU, achieving an average speed of twice the execution time of the sequential approach. This work improves on previous results of hybrid approaches and parallel algorithms with many steps of synchronisation and iterations between CPU and GPU.<\/p>","DOI":"10.4018\/jncr.2010100102","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T11:58:22Z","timestamp":1319025502000},"page":"16-28","source":"Crossref","is-referenced-by-count":3,"title":["Analysis of a Step-Based Watershed Algorithm Using CUDA"],"prefix":"10.4018","volume":"1","author":[{"given":"Giovani Bernardes","family":"Vitor","sequence":"first","affiliation":[{"name":"Universidade Estadual de Campinas, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"K\u00f6rbes","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto de Alencar","family":"Lotufo","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Janito Vaqueiro","family":"Ferreira","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"jncr.2010100102-0","unstructured":"AMD. (2010). ATI Radeon X1950 Specifications. Retrieved from http:\/\/www.amd.com\/us\/products\/desktop\/graphics\/other\/Pages\/x1950-specifications.aspx"},{"key":"jncr.2010100102-1","unstructured":"Audigier, R., & Lotufo, R. A. (2007). Watershed by image foresting transform, tie-zone, and theoretical relationships with other watershed definitions. In Proceedings of the 8th International Symposium on Mathematical Morphology, Rio De Janeiro, Brazil (pp. 277-288)."},{"key":"jncr.2010100102-2","unstructured":"Baggio, D. L. (2007). Gpu based image segmentation livewire algorithm implementation. Unpublished doctoral dissertation, Technological Institute of Aeronautics, Sao Jos\u00e9 dos Campos, Brazil."},{"key":"jncr.2010100102-3","unstructured":"Bieniek, A., Burkhardt, H., Marschner, H., N\u00f6lle, M., & Schreiber, G. (1997). A parallel watershed algorithm. In Proceedings of the 10th Scandinavian Conference on Image Analysis (pp. 237-244)."},{"key":"jncr.2010100102-4","unstructured":"Bieniek, A., & Moga, A. (1998). A connected component approach to the watershed segmentation. In Proceedings of the Fourth International Symposium on Mathematical Morphology and its Applications to Image and Signal Processing (pp. 215-222)."},{"issue":"6","key":"jncr.2010100102-5","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1016\/S0031-3203(99)00154-5","article-title":"An efficient watershed algorithm based on connected components.","volume":"33","author":"A.Bieniek","year":"2000","journal-title":"Pattern Recognition Letters"},{"key":"jncr.2010100102-6","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.173"},{"key":"jncr.2010100102-7","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.71"},{"key":"jncr.2010100102-8","unstructured":"Digabel, H., & Lantu\u00e9joul, C. (1978). Iterative algorithms. In J.-L. Chermant (Ed.), Proceedings of the Second European Symposium on Quantitative Analysis of Microstructures in Material Science, Biology and Medicine (pp. 85-99)."},{"key":"jncr.2010100102-9","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1261076"},{"key":"jncr.2010100102-10","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.253280"},{"key":"jncr.2010100102-11","author":"R. C.Gonzalez","year":"2002","journal-title":"Digital image processing"},{"key":"jncr.2010100102-12","unstructured":"Halfhill, T. R. (2008). Parallel processing with CUDA: Nvidia\u2019s high-performance computing platform uses massive multithreading. Microprocessor, 1-8."},{"key":"jncr.2010100102-13","unstructured":"Hawick, K. A., Leist, A., & Playne, D. P. (2009). Parallel graph component labelling with GPUs and CUDA (Tech. Rep. No. CSTN-089). Auckland, New Zealand: Massey University Institute of Information and Mathematical Sciences."},{"key":"jncr.2010100102-14","doi-asserted-by":"crossref","unstructured":"Kauffmann, C., & Piche, N. (2008). A cellular automaton for ultra-fast watershed transform on gpu. In Proceedings of the 19th International Conference on Pattern Recognition (pp. 1-4).","DOI":"10.1109\/ICPR.2008.4761628"},{"key":"jncr.2010100102-15","author":"D. B.Kirk","year":"2010","journal-title":"Programming massively parallel processors: A hands-on approach"},{"key":"jncr.2010100102-16","doi-asserted-by":"crossref","unstructured":"K\u00f6rbes, A., & Lotufo, R. (2009). Analysis of the watershed algorithms based on the breadth-first and depth-first exploring methods. In Proceedings of the Twenty-second Brazilian Symposium on Computer Graphics and Image Processing, Rio de Janiero, Brazil (pp. 133-140).","DOI":"10.1109\/SIBGRAPI.2009.43"},{"key":"jncr.2010100102-17","unstructured":"K\u00f6rbes, A., Vitor, G., Ferreira, J., & Lotufo, R. (2009). A proposal for a parallel watershed transform algorithm for real-time segmentation. Paper presented at the Workshop de Visao Computacional, Sao Paulo, Brazil."},{"key":"jncr.2010100102-18","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2005.860996"},{"key":"jncr.2010100102-19","doi-asserted-by":"crossref","unstructured":"Lotufo, R., & Falc\u00e3o, A. (2000). The ordered queue and the optimality of the watershed approaches. In Proceedings of the 5th International Symposium on Mathematical Morphology and its Applications to Image and Signal Processing (Vol. 18, pp. 341-350).","DOI":"10.1007\/0-306-47025-X_37"},{"key":"jncr.2010100102-20","doi-asserted-by":"crossref","unstructured":"Meijster, A., & Roerdink, J. B. T. M. (1995). A proposal for the implementation of a parallel watershed algorithm. In V. Hlavac & R. Sara (Eds.), Proceedings of the 6th International Conference on Computer Analysis of Images and Patterns (LNCS 970, pp. 790-795).","DOI":"10.1007\/3-540-60268-2_382"},{"key":"jncr.2010100102-21","unstructured":"Meijster, A., & Roerdink, J. B. T. M. (1998). A disjoint set algorithm for the watershed transform. In Proceedings of the 9th European Conference on Signal Processing (pp. 1665-1668)."},{"key":"jncr.2010100102-22","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(94)90060-4"},{"key":"jncr.2010100102-23","first-page":"281","article-title":"Implementation of a distributed watershed algorithm","author":"A.Moga","year":"1994","journal-title":"Mathematical morphology and its applications to image processing (Computational Imaging and Vision)"},{"key":"jncr.2010100102-24","doi-asserted-by":"publisher","DOI":"10.1145\/1365490.1365500"},{"key":"jncr.2010100102-25","unstructured":"NVIDIA. (2009). CUDA Programming Guide, 2.1. Retrieved from http:\/\/developer.download.nvidia.com\/compute\/cuda\/2 1\/toolkit\/docs\/NVIDIA CUDA  Programming Guide 2.1.pdf"},{"key":"jncr.2010100102-26","unstructured":"NVIDIA. (2010). GeForce GTX 295 Specifications. Retrieved from http:\/\/www.nvidia.com\/object\/product_geforce_gtx_295_us.html"},{"issue":"3","key":"jncr.2010100102-27","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1016\/j.patcog.2006.06.025","article-title":"An improved watershed algorithm based on efficient computation of shortest paths.","volume":"40","author":"V.Osma-Ruiz","year":"2007","journal-title":"Pattern Recognition Letters"},{"key":"jncr.2010100102-28","unstructured":"Podlozhnyuk, V. (2007). Image convolution with CUDA. Retrieved from http:\/\/developer.download.nvidia.com\/compute\/cuda\/1.1-  Beta\/x86_64_website\/projects\/convolutionSeparable\/doc\/convolutionSeparable.pdf"},{"issue":"1-2","key":"jncr.2010100102-29","doi-asserted-by":"crossref","first-page":"187","DOI":"10.3233\/FI-2000-411207","article-title":"The watershed transform: Definitions, algorithms and parallelization strategies.","volume":"41","author":"J. B. T. M.Roerdink","year":"2000","journal-title":"Fundamenta Informaticae"},{"key":"jncr.2010100102-30","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2004.11.007"},{"key":"jncr.2010100102-31","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","author":"R. E.Tarjan","year":"1983","journal-title":"Data structures and network algorithms (CBMS-NSF regional conference series in applied mathematics)"},{"key":"jncr.2010100102-32","doi-asserted-by":"publisher","DOI":"10.1007\/s11554-007-0051-z"},{"key":"jncr.2010100102-33","doi-asserted-by":"publisher","DOI":"10.1109\/34.87344"},{"key":"jncr.2010100102-34","unstructured":"Vitor, G., Ferreira, J., & K\u00f6rbes, A. (2009, November 8-11). Fast image segmentation by watershed transform on graphical hardware. Paper presented at the 30th Iberian-Latin-American Congress on Computational Methods in Engineering, Arma\u00e7ao dos Bu\u2019zios, Brazil."}],"container-title":["International Journal of Natural Computing Research"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=52612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T17:06:49Z","timestamp":1654103209000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jncr.2010100102"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2010,10,1]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,10]]}},"URL":"https:\/\/doi.org\/10.4018\/jncr.2010100102","relation":{},"ISSN":["1947-928X","1947-9298"],"issn-type":[{"value":"1947-928X","type":"print"},{"value":"1947-9298","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,1]]}}}