{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T00:25:04Z","timestamp":1775089504975,"version":"3.50.1"},"reference-count":28,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T00:00:00Z","timestamp":1685491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Ministerio de Econom\u00eda","award":["PID2019-110455GB-I00"],"award-info":[{"award-number":["PID2019-110455GB-I00"]}]},{"name":"Ministerio de Econom\u00eda","award":["CIUCAP-HSF:US-1381077"],"award-info":[{"award-number":["CIUCAP-HSF:US-1381077"]}]},{"name":"Ministerio de Econom\u00eda","award":["SANEVEC TED2021-130825B-I00"],"award-info":[{"award-number":["SANEVEC TED2021-130825B-I00"]}]},{"name":"Industria y Competitividad","award":["PID2019-110455GB-I00"],"award-info":[{"award-number":["PID2019-110455GB-I00"]}]},{"name":"Industria y Competitividad","award":["CIUCAP-HSF:US-1381077"],"award-info":[{"award-number":["CIUCAP-HSF:US-1381077"]}]},{"name":"Industria y Competitividad","award":["SANEVEC TED2021-130825B-I00"],"award-info":[{"award-number":["SANEVEC TED2021-130825B-I00"]}]},{"name":"Agencia Estatal de Investigaci\u00f3n (AEI)","award":["PID2019-110455GB-I00"],"award-info":[{"award-number":["PID2019-110455GB-I00"]}]},{"name":"Agencia Estatal de Investigaci\u00f3n (AEI)","award":["CIUCAP-HSF:US-1381077"],"award-info":[{"award-number":["CIUCAP-HSF:US-1381077"]}]},{"name":"Agencia Estatal de Investigaci\u00f3n (AEI)","award":["SANEVEC TED2021-130825B-I00"],"award-info":[{"award-number":["SANEVEC TED2021-130825B-I00"]}]},{"name":"Gobierno de Espa\u00f1a (MINECO)","award":["PID2019-110455GB-I00"],"award-info":[{"award-number":["PID2019-110455GB-I00"]}]},{"name":"Gobierno de Espa\u00f1a (MINECO)","award":["CIUCAP-HSF:US-1381077"],"award-info":[{"award-number":["CIUCAP-HSF:US-1381077"]}]},{"name":"Gobierno de Espa\u00f1a (MINECO)","award":["SANEVEC TED2021-130825B-I00"],"award-info":[{"award-number":["SANEVEC TED2021-130825B-I00"]}]},{"DOI":"10.13039\/501100003329","name":"MCIN\/AEI","doi-asserted-by":"publisher","award":["PID2019-110455GB-I00"],"award-info":[{"award-number":["PID2019-110455GB-I00"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003329","name":"MCIN\/AEI","doi-asserted-by":"publisher","award":["CIUCAP-HSF:US-1381077"],"award-info":[{"award-number":["CIUCAP-HSF:US-1381077"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003329","name":"MCIN\/AEI","doi-asserted-by":"publisher","award":["SANEVEC TED2021-130825B-I00"],"award-info":[{"award-number":["SANEVEC TED2021-130825B-I00"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union","award":["PID2019-110455GB-I00"],"award-info":[{"award-number":["PID2019-110455GB-I00"]}]},{"name":"European Union","award":["CIUCAP-HSF:US-1381077"],"award-info":[{"award-number":["CIUCAP-HSF:US-1381077"]}]},{"name":"European Union","award":["SANEVEC TED2021-130825B-I00"],"award-info":[{"award-number":["SANEVEC TED2021-130825B-I00"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Relating image contours and regions and their attributes according to connectivity based on incidence or adjacency is a crucial task in numerous applications in the fields of image processing, computer vision and pattern recognition. In this paper, the crucial incidence topological information of 2-dimensional images is extracted in an efficient manner through the computation of a new structure called the HomDuRAG of an image; that is, the dual graph of the HomRAG (a topologically consistent extended version of the classical RAG). These representations are derived from the two traditional self-dual square grids (in which physical pixels play the role of 2-dimensional cells) and encapsulate the whole set of topological features and relations between the three types of objects embedded in a digital image: 2-dimensional (regions), 1-dimensional (contours) and 0-dimensional objects (crosses). Here, a first version of a fully parallel algorithm to compute this new representation is presented, whose timing complexity order (in the worst case and supposing one processing element per 0-cell) is O(log(M\u00d7N)) , M and N being the height and width of the image. Efficient implementations of this parallel algorithm would allow images to be processed in real time, as well as permit us to uncover fast algorithms for contour detection and segmentation, opening new perspectives within the image processing field.<\/jats:p>","DOI":"10.3390\/a16060284","type":"journal-article","created":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T02:12:45Z","timestamp":1685585565000},"page":"284","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fully Parallel Homological Region Adjacency Graph via Frontier Recognition"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6184-1629","authenticated-orcid":false,"given":"Fernando","family":"D\u00edaz-del-R\u00edo","sequence":"first","affiliation":[{"name":"Department of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6827-6159","authenticated-orcid":false,"given":"Pablo","family":"Sanchez-Cuevas","sequence":"additional","affiliation":[{"name":"Department of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3291-7297","authenticated-orcid":false,"given":"Mar\u00eda Jos\u00e9","family":"Moron-Fern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Department of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6138-1009","authenticated-orcid":false,"given":"Daniel","family":"Cascado-Caballero","sequence":"additional","affiliation":[{"name":"Department of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5595-132X","authenticated-orcid":false,"given":"Helena","family":"Molina-Abril","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics I, Universidad de Sevilla, 41012 Seville, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6853-0505","authenticated-orcid":false,"given":"Pedro","family":"Real","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics I, Universidad de Sevilla, 41012 Seville, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,5,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/83.663500","article-title":"Antiextensive Connected Operators for Image and Sequence Processing","volume":"7","author":"Salembier","year":"1998","journal-title":"IEEE Trans. Image Process."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2201","DOI":"10.1109\/TIP.2008.2002841","article-title":"Binary Partition Trees for Object Detection","volume":"17","author":"Vilaplana","year":"2008","journal-title":"IEEE Trans. Image Process."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1109\/83.841950","article-title":"Regions adjacency graph applied to color image segmentation","volume":"9","author":"Tremeau","year":"2000","journal-title":"IEEE Trans. Image Process."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.5566\/ias.v27.p39-45","article-title":"Region merging via graph-cuts","volume":"27","author":"Stawiaski","year":"2008","journal-title":"Image Anal. Stereol."},{"key":"ref_5","first-page":"59","article-title":"Topological models for Boundary Representation : A comparison with n-dimensional generalized maps","volume":"23","author":"Lienhardt","year":"1991","journal-title":"Comput.-Aided Des."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1016\/j.imavis.2008.06.009","article-title":"Directly computing the generators of image homology using graph pyramids","volume":"27","author":"Peltier","year":"2009","journal-title":"Image Vis. Comput."},{"key":"ref_7","unstructured":"Fiorio, C. (1996). Discrete Geometry for Computer Imagery, Springer."},{"key":"ref_8","unstructured":"Kovalevsky, V. (2008). Geometry of Locally Finite Spaces, House Dr. Baerbel Kovalevski."},{"key":"ref_9","first-page":"366","article-title":"Algorithms in Digital Geometry Based on Cellular Topology","volume":"Volume 3322","author":"Kovalevsky","year":"2004","journal-title":"Proceedings of the 10th IWCIA"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kovalevsky, V. (2021). Image Processing with Cellular Topology, Springer.","DOI":"10.1007\/978-981-16-5772-6"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1109\/34.244673","article-title":"An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation","volume":"15","author":"Wu","year":"1993","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Windisch, D., Kaever, C., Juckeland, G., and Bieberle, A. (2023). Parallel Algorithm for Connected-Component Analysis Using CUDA. Algorithms, 16.","DOI":"10.3390\/a16020080"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"69","DOI":"10.55708\/js0110009","article-title":"Fast Labeled Spanning Tree in Binary Irregular Graph Pyramids","volume":"1","author":"Banaeyan","year":"2022","journal-title":"J. Eng. Res. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kovalevsky, V. (2019). Modern Algorithms for Image Processing: Computer Imagery by Example Using C#, Apress.","DOI":"10.1007\/978-1-4842-4237-7"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Damiand, G., and Lienhardt, P. (2014). Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing, A. K. Peters, Ltd.. [1st ed.].","DOI":"10.1201\/b17403"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Asano, T., Klette, R., and Ronse, C. (2003). Geometry, Morphology, and Computational Imaging, Springer.","DOI":"10.1007\/3-540-36586-9"},{"key":"ref_17","unstructured":"Tavares, J.M.R.S., Papa, J.P., and Gonz\u00e1lez Hidalgo, M. (2021, January 10\u201313). A Topologically Consistent Color Digital Image Representation by a Single Tree. Proceedings of the Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, Porto, Portugal."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gasparovic, E., Robins, V., and Turner, K. (2022). Research in Computational Topology 2, Springer International Publishing.","DOI":"10.1007\/978-3-030-95519-9"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"D\u00edaz-del R\u00edo, F., Real, P., and Onchis, D. (2015, January 23\u201327). A Parallel Implementation for Computing the Region-Adjacency-Tree of a Segmentation of a 2D Digital Image. Proceedings of the Image and Video Technology\u2014PSIVT 2015 Workshops, Auckland, New Zealand.","DOI":"10.1007\/978-3-319-30285-0_9"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1109\/TPAMI.2011.95","article-title":"Theory and Algorithms for Constructing Discrete Morse Complexes from Grayscale Digital Images","volume":"33","author":"Robins","year":"2011","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.patrec.2019.11.039","article-title":"Parallel Connected-Component-Labeling based on Homotopy Trees","volume":"131","author":"Real","year":"2020","journal-title":"Pattern Recognit. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"D\u00edaz-del R\u00edo, F., Real, P., and Onchis, D. (2017, January 22\u201324). Labeling Color 2D Digital Images in Theoretical Near Logarithmic Time. Proceedings of the Computer Analysis of Images and Patterns, Ystad, Sweden.","DOI":"10.1007\/978-3-319-64698-5_33"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1016\/0167-8655(93)90148-7","article-title":"Parallel computation of the Euler number via connectivity graph","volume":"14","author":"Chiavetta","year":"1993","journal-title":"Pattern Recognit. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00453-003-1052-3","article-title":"Parallel Computation of the Topology of Level Sets","volume":"38","author":"Pascucci","year":"2004","journal-title":"Algorithmica"},{"key":"ref_25","unstructured":"D\u00edaz-del R\u00edo, F. (2023, March 31). HomDuRAG. MATLAB Central File Exchange. Available online: https:\/\/es.mathworks.com\/matlabcentral\/fileexchange\/127149-homdurag."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.ins.2021.02.039","article-title":"An Adaptive Polyploid Memetic Algorithm for Scheduling Trucks at a Cross-Docking Terminal","volume":"565","author":"Dulebenets","year":"2021","journal-title":"Inf. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ins.2019.08.069","article-title":"An Online-Learning-Based Evolutionary Many-Objective Algorithm","volume":"509","author":"Zhao","year":"2020","journal-title":"Inf. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"65635","DOI":"10.1109\/ACCESS.2018.2874439","article-title":"A Comprehensive Evaluation of Weak and Strong Mutation Mechanisms in Evolutionary Algorithms for Truck Scheduling at Cross-Docking Terminals","volume":"6","author":"Dulebenets","year":"2018","journal-title":"IEEE Access."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/6\/284\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:46:42Z","timestamp":1760125602000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/6\/284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,31]]},"references-count":28,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["a16060284"],"URL":"https:\/\/doi.org\/10.3390\/a16060284","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,31]]}}}