Fully Parallel Homological Region Adjacency Graph via Frontier Recognition
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-...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-05-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/6/284 |
| _version_ | 1797596468875362304 |
|---|---|
| author | Fernando Díaz-del-Río Pablo Sanchez-Cuevas María José Moron-Fernández Daniel Cascado-Caballero Helena Molina-Abril Pedro Real |
| author_facet | Fernando Díaz-del-Río Pablo Sanchez-Cuevas María José Moron-Fernández Daniel Cascado-Caballero Helena Molina-Abril Pedro Real |
| author_sort | Fernando Díaz-del-Río |
| collection | DOAJ |
| description | 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 <i>HomDuRAG</i> of an image; that is, the dual graph of the <i>HomRAG</i> (a topologically consistent extended version of the classical <i>RAG</i>). 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mo>(</mo><mi>M</mi><mo>×</mo><mi>N</mi><mo>)</mo><mo>)</mo></mrow></semantics></math></inline-formula> , <i>M</i> and <i>N</i> 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. |
| first_indexed | 2024-03-11T02:51:48Z |
| format | Article |
| id | doaj.art-768a7a1cdbc941d8997b228777cf4959 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T02:51:48Z |
| publishDate | 2023-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-768a7a1cdbc941d8997b228777cf49592023-11-18T08:56:46ZengMDPI AGAlgorithms1999-48932023-05-0116628410.3390/a16060284Fully Parallel Homological Region Adjacency Graph via Frontier RecognitionFernando Díaz-del-Río0Pablo Sanchez-Cuevas1María José Moron-Fernández2Daniel Cascado-Caballero3Helena Molina-Abril4Pedro Real5Department of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, SpainDepartment of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, SpainDepartment of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, SpainDepartment of Computer Architecture and Technology, Universidad de Sevilla, 41012 Seville, SpainDepartment of Applied Mathematics I, Universidad de Sevilla, 41012 Seville, SpainDepartment of Applied Mathematics I, Universidad de Sevilla, 41012 Seville, SpainRelating 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 <i>HomDuRAG</i> of an image; that is, the dual graph of the <i>HomRAG</i> (a topologically consistent extended version of the classical <i>RAG</i>). 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mo>(</mo><mi>M</mi><mo>×</mo><mi>N</mi><mo>)</mo><mo>)</mo></mrow></semantics></math></inline-formula> , <i>M</i> and <i>N</i> 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.https://www.mdpi.com/1999-4893/16/6/284digital imageparallel computingabstract cell complexregion adjacency graphdual graphEuler number |
| spellingShingle | Fernando Díaz-del-Río Pablo Sanchez-Cuevas María José Moron-Fernández Daniel Cascado-Caballero Helena Molina-Abril Pedro Real Fully Parallel Homological Region Adjacency Graph via Frontier Recognition Algorithms digital image parallel computing abstract cell complex region adjacency graph dual graph Euler number |
| title | Fully Parallel Homological Region Adjacency Graph via Frontier Recognition |
| title_full | Fully Parallel Homological Region Adjacency Graph via Frontier Recognition |
| title_fullStr | Fully Parallel Homological Region Adjacency Graph via Frontier Recognition |
| title_full_unstemmed | Fully Parallel Homological Region Adjacency Graph via Frontier Recognition |
| title_short | Fully Parallel Homological Region Adjacency Graph via Frontier Recognition |
| title_sort | fully parallel homological region adjacency graph via frontier recognition |
| topic | digital image parallel computing abstract cell complex region adjacency graph dual graph Euler number |
| url | https://www.mdpi.com/1999-4893/16/6/284 |
| work_keys_str_mv | AT fernandodiazdelrio fullyparallelhomologicalregionadjacencygraphviafrontierrecognition AT pablosanchezcuevas fullyparallelhomologicalregionadjacencygraphviafrontierrecognition AT mariajosemoronfernandez fullyparallelhomologicalregionadjacencygraphviafrontierrecognition AT danielcascadocaballero fullyparallelhomologicalregionadjacencygraphviafrontierrecognition AT helenamolinaabril fullyparallelhomologicalregionadjacencygraphviafrontierrecognition AT pedroreal fullyparallelhomologicalregionadjacencygraphviafrontierrecognition |