{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T12:28:51Z","timestamp":1770726531920,"version":"3.49.0"},"reference-count":37,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T00:00:00Z","timestamp":1604102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Universidad Aut\u00f3noma de Tamaulipas","award":["Facultad de Ingenier\u00eda y Ciencias"],"award-info":[{"award-number":["Facultad de Ingenier\u00eda y Ciencias"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Distance transform (DT) and Voronoi diagrams (VDs) have found many applications in image analysis. Euclidean distance transform (EDT) can generate forms that do not vary with the rotation, because it is radially symmetrical, which is a desirable characteristic in distance transform applications. Recently, parallel architectures have been very accessible and, particularly, GPU-based architectures are very promising due to their high performance, low power consumption and affordable prices. In this paper, a new parallel algorithm is proposed for the computation of a Euclidean distance map and Voronoi diagram of a binary image that mixes CUDA multi-thread parallel image processing with a raster propagation of distance information over small fragments of the image. The basic idea is to exploit the throughput and the latency in each level of memory in the NVIDIA GPU; the image is set in the global memory, and can be accessed via texture memory, and we divide the problem into blocks of threads. For each block we copy a portion of the image and each thread applies a raster scan-based algorithm to a tile of m\u00d7m pixels. Experiment results exhibit that our proposed GPU algorithm can improve the efficiency of the Euclidean distance transform in most cases, obtaining speedup factors that even reach 3.193.<\/jats:p>","DOI":"10.3390\/sym12111808","type":"journal-article","created":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T21:39:56Z","timestamp":1604180396000},"page":"1808","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Parallel Raster Scan for Euclidean Distance Transform"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0794-8967","authenticated-orcid":false,"given":"Juan Carlos","family":"Elizondo-Leal","sequence":"first","affiliation":[{"name":"Facultad de Ingenier\u00eda y Ciencias, Universidad Aut\u00f3noma de Tamaulipas, Ciudad Victoria 87149, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 Gabriel","family":"Ramirez-Torres","sequence":"additional","affiliation":[{"name":"Center for Research and Advanced Studies, Cinvestav Tamaulipas, Ciudad Victoria 87149, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jose Hugo","family":"Barr\u00f3n-Zambrano","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda y Ciencias, Universidad Aut\u00f3noma de Tamaulipas, Ciudad Victoria 87149, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2847-8316","authenticated-orcid":false,"given":"Alan","family":"Diaz-Manr\u00edquez","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda y Ciencias, Universidad Aut\u00f3noma de Tamaulipas, Ciudad Victoria 87149, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0102-8227","authenticated-orcid":false,"given":"Marco Aurelio","family":"Nu\u00f1o-Maganda","sequence":"additional","affiliation":[{"name":"Intelligent Systems Department, Polytechnic University of Victoria, Ciudad Victoria 87138, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6036-0994","authenticated-orcid":false,"given":"Vicente Paul","family":"Saldivar-Alonso","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda y Ciencias, Universidad Aut\u00f3noma de Tamaulipas, Ciudad Victoria 87149, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"103490","DOI":"10.1016\/j.jbi.2020.103490","article-title":"A visual framework to create photorealistic retinal vessels for diagnosis purposes","volume":"108","author":"Tegolo","year":"2020","journal-title":"J. Biomed. Inform."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1322432.1322434","article-title":"2D Euclidean distance transform algorithms: A comparative survey","volume":"40","author":"Fabbri","year":"2008","journal-title":"ACM Comput. Surv."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1007\/3-540-45103-X_87","article-title":"Image matching using distance transform","volume":"Volume 2749","author":"Bigun","year":"2003","journal-title":"Image Analysis"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O.C. (2000). Computational Geometry: Algorithms and Applications, Springer.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1109\/TPAMI.2010.140","article-title":"Distance-Driven Skeletonization in Voxel Images","volume":"33","author":"Arcelli","year":"2011","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Noreen, I., Khan, A., Asghar, K., and Habib, Z. (2019). A Path-Planning Performance Comparison of RRT*-AB with MEA* in a 2-Dimensional Environment. Symmetry, 11.","DOI":"10.3390\/sym11070945"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1109\/34.161346","article-title":"Thinning methodologies-a comprehensive survey","volume":"14","author":"Lam","year":"1992","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1145\/321356.321357","article-title":"Sequential Operations in Digital Picture Processing","volume":"13","author":"Rosenfeld","year":"1966","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0031-3203(68)90013-7","article-title":"Distance functions on digital pictures","volume":"1","author":"Rosenfeld","year":"1968","journal-title":"Pattern Recognit."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/S0734-189X(86)80047-0","article-title":"Distance transformations in digital images","volume":"34","author":"Borgefors","year":"1986","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1477","DOI":"10.1109\/83.718487","article-title":"Optimum design of chamfer distance transforms","volume":"7","author":"Maragos","year":"1998","journal-title":"IEEE Trans. Image Process."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0146-664X(80)90054-4","article-title":"Euclidean distance mapping","volume":"14","author":"Danielsson","year":"1980","journal-title":"Comput. Vis. Graph. Image Process."},{"key":"ref_13","unstructured":"Ye, Q.-Z. (November, January 14). The signed Euclidean distance transform and its applications. Proceedings of the 9th International Conference on Pattern Recognition, Rome, Italy."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/1049-9660(92)90008-Q","article-title":"Fast raster scan distance propagation on the discrete rectangular lattice","volume":"55","author":"Leymarie","year":"1992","journal-title":"CVGIP Image Underst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1016\/0167-8655(93)90152-4","article-title":"The Euclidean distance transform in arbitrary dimensions","volume":"14","author":"Ragnemalm","year":"1993","journal-title":"Pattern Recognit. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cuisenaire, O., and Macq, V. (1999, January 15\u201319). Fast and exact signed Euclidean distance transformation with linear complexity. Proceedings of the ICASSP99 (Cat. No.99CH36258), Phoenix, AZ, USA.","DOI":"10.1109\/ICASSP.1999.757545"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1109\/TIP.2004.826098","article-title":"The Efficient Algorithms for Achieving Euclidean Distance Transformation","volume":"13","author":"Shih","year":"2004","journal-title":"IEEE Trans. Image Process."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.cviu.2003.09.004","article-title":"Fast Euclidean distance transformation in two scans using a 3 \u00d7 3 neighborhood","volume":"93","author":"Shih","year":"2004","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.cviu.2004.05.002","article-title":"The \u201cdead reckoning\u201d signed distance transform","volume":"95","author":"Grevera","year":"2004","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/1049-9652(92)90034-U","article-title":"Distance transforms: Properties and machine vision applications","volume":"54","author":"Paglieroni","year":"1992","journal-title":"CVGIP Graph. Models Image Process."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01213529","article-title":"A unified distance transform algorithm and architecture","volume":"5","author":"Paglieroni","year":"1992","journal-title":"Mach. Vis. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1016\/0031-3203(94)90133-3","article-title":"New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applications","volume":"27","author":"Saito","year":"1994","journal-title":"Pattern Recognit."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1016\/0031-3203(87)90030-6","article-title":"Computing distance transformations in convex and non-convex domains","volume":"20","author":"Piper","year":"1987","journal-title":"Pattern Recognit."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/34.19041","article-title":"An efficient uniform cost algorithm applied to distance transforms","volume":"11","author":"Verwer","year":"1989","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/1049-9660(92)90050-D","article-title":"Neighborhoods for distance transformations using ordered propagation","volume":"56","author":"Ragnemalm","year":"1992","journal-title":"CVGIP Image Underst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1006\/cviu.1997.0596","article-title":"Two Fast Euclidean Distance Transformations in Z2 Based on Sufficient Propagation","volume":"69","author":"Eggers","year":"1998","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1016\/0167-8655(94)90036-1","article-title":"A graph-theoretic approach to distance transformations","volume":"15","author":"Sharaiha","year":"1994","journal-title":"Pattern Recognit. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/TPAMI.2004.1261076","article-title":"The image foresting transform: Theory, algorithms, and applications","volume":"26","author":"Falcao","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1006\/cviu.1999.0783","article-title":"Fast Euclidean Distance Transformation by Propagation Using Multiple Neighborhoods","volume":"76","author":"Cuisenaire","year":"1999","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Cao, T.-T., Tang, K., Mohamed, A., and Tan, T.-S. (2010, January 19\u201321). Parallel Banding Algorithm to compute exact distance transform with the GPU. Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games-I3D 10, Maryland, MD, USA.","DOI":"10.1145\/1730804.1730818"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"5322","DOI":"10.1109\/TIP.2019.2916741","article-title":"A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform","volume":"28","author":"Manduhu","year":"2019","journal-title":"IEEE Trans. Image Process."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"de Assis Zampirolli, F., and Filipe, L. (2017, January 17). A Fast CUDA-Based Implementation for the Euclidean Distance Transform. Proceedings of the 2017 International Conference on High Performance Computing & Simulation (HPCS), Genoa, Italy.","DOI":"10.1109\/HPCS.2017.123"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Rong, G., and Tan, T.-S. (2006, January 14\u201317). Jump flooding in GPU with applications to Voronoi diagram and distance transform. Proceedings of the 2006 symposium on Interactive 3D graphics and games-SI3D \u201906, Redwood City, CA, USA.","DOI":"10.1145\/1111411.1111431"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.cag.2019.03.011","article-title":"GPU-based efficient computation of power diagram","volume":"80","author":"Zheng","year":"2019","journal-title":"Comput. Graph."},{"key":"ref_35","unstructured":"Schneider, J., Kraus, M., and Westermann, R. (2009, January 5). GPU-based real-time discrete Euclidean distance transforms with precise error bounds. Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, Lisboa, Portugal."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Honda, T., Yamamoto, S., Honda, H., Nakano, K., and Ito, Y. (2017, January 14). Simple and Fast Parallel Algorithms for the Voronoi Map and the Euclidean Distance Map, with GPU Implementations. Proceedings of the 2017 46th International Conference on Parallel Processing (ICPP), Bristol, UK.","DOI":"10.1109\/ICPP.2017.45"},{"key":"ref_37","unstructured":"Cao, T.-T., Tang, K., Mohamed, A., and Tan, T.-S. (2020, September 22). Parallel Banding Algorithm Plus to Compute Exact Distance Transform with the GPU. Available online: https:\/\/www.comp.nus.edu.sg\/~tants\/pba.htm."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/11\/1808\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:27:37Z","timestamp":1760178457000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/11\/1808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,31]]},"references-count":37,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["sym12111808"],"URL":"https:\/\/doi.org\/10.3390\/sym12111808","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,31]]}}}