dc.contributor.advisor | Díaz Pernil, Daniel | es |
dc.contributor.advisor | Real Jurado, Pedro | es |
dc.creator | Reina Molina, Raúl | es |
dc.date.accessioned | 2018-02-02T12:51:16Z | |
dc.date.available | 2018-02-02T12:51:16Z | |
dc.date.issued | 2018-01-18 | |
dc.identifier.citation | Reina Molina, R. (2018). Parallelization strategies for extraction of (co)homological information of digital objects.. (Tesis Doctoral Inédita). Universidad de Sevilla, Sevilla. | |
dc.identifier.uri | https://hdl.handle.net/11441/69925 | |
dc.description.abstract | Un objeto digital es un conjunto de n-xels en de una imagen digital n-dimensional. El estudio de la conectividad de estos objetos, interpretados de manera discreta, subdividida o continua, ha sido una custión prioritaria desde los inicios del tratamiento de Imagen Digital. Las herramientas topológicas que se han usado exhaustivamente en esta tarea son las nociones de componente conexa, punto simple o la característica de Euler. Otros invariantes topológicos con una creciente popularidad son los grupos de (co)homología de objetos digitales tratados como complejos celulares. En esta tesis proponemos estrategias de paralelización basadas en métodos de extracción de información (co)homológica como la Teoría Discreta de Morse, la homología efectiva o los modelos AM.
La primera aproximación que realizamos está relacionada con la Computación Natural, que es un área de investigación fructífera que proporciona formas interesantes de abordar problemas computacionales inspirándose en la forma en la que la Naturaleza “computa”. Concretamente, usamos Computación con Membranas, que resume mediante reglas de computación, la manera en la que trabajan las células de los seres vivos. Este área ha proporcionado resultados interesantes en trabajos teóricos y aplicados. La aplicación de estas ideas al proceso de cálculo de los grupos de (co)homología de objetos digitales nos permite desarrollar mejores algoritmos, ya que los algoritmos de Computación con Membranas son naturalmente paralelos.
En la actualidad no existe ningún dispositivo capaz de ejecutar (no emular) algoritmos de Computación con Membranas, por lo que los algoritmos citados anteriormente necesitan ser adaptados para su ejecución en dispositivos de computación ordinarios. De esta manera, en esta tesis presentamos una serie de algoritmos que proporcionan una representación compacta, de alguna manera óptima, de un objeto digital junto con una transformación bidireccional que nos permite no solo calcular los grupos de (co)homología sino computar algunos invariantes algebraicos mediante operaciones que involucren clases de (co)homología que puedan usarse como información intrínseca del objeto digital.
El trabajo presentado en esta tesis se centra fundamentalmente en dos contribuciones. La primera de ellas está relacionada con la Computación Natural. Presentamos un marco de trabajo en Computación con Membranas usado para hacer más fácil el desarrollo de algoritmos en Computación con Membranas sobre Topología Algebraica Computacional. Este marco de trabajo está fuertemente relacionado con la Teoría Discreta de Morse.
La segunda contribución principal es la aplicación del marco de trabajo anterior para desarrollar un algoritmo paralelo qu compute una reducción de un complejo celular cúbico en un CW complejo con una cantidad minimal de celdas, esta reducción hace que la extracción de información (co)homológica sea más simple. Este algoritmo se centra en complejos cúbicos n-dimensionales y usa ℤ como anillo base, lo que lo convierte en una herramienta muy útil para el cálculo de la torsión. | es |
dc.description.abstract | Digital objects are nite subsets of n-xels within a n-dimensional
digital image. The study of the connectivity of these objects,
interpreted from a discrete, subdivided or continuous way, has been
a priority issue from the very beginning of Digital Imagery. The
topological tools that have been exhaustively used in this setting
are the notions of connected component, simple point and Euler
characteristic. Others topological invariants with a recent increasing
popularity are (co)homology groups of digital objects treated as cell
complexes. In this thesis, we propose parallelization strategies based
on extraction methods of (co)homological information, like Discrete
Morse Theory, E ective Homology or AT-model.
The rst approach is related with Natural Computing, which
is a fruitful research area that provides interesting approaches
to computational problems inspiring in the way that Nature
\computes". Concretely, we use Membrane Computing, which
summarizes with computational rules, the manner living cells work.
This area has provided interesting results in theoretical and applied
works. The application of these ideas to the process of calculating
(co)homology groups of digital objects allows us to develop better
algorithms as it brings a natural parallelization of the algorithms
implemented in Membrane Computing.
Nowadays, there is no current device capable of executing
Membrane Computing algorithms, hence the previous processes
need to be adapted to be executed by ordinary computing devices.
Therefore, in this thesis we present a set of algorithms that provides
a compact representation, optimal in some way, of a digital object
along with a bidirectional transformation that allows us to compute
not only the (co)homology groups but compute some algebraic
invariants or operation involving (co)homology classes which can be
used as intrinsic information of the digital object.
The work presented in this thesis focuses in two main contri-
butions. The rst of all is related with Natural Computing. We
present a Membrane Computing framework used to make easier the
development of Membrane Computing algorithms in Computational
Algebraic Topology. This framework is strongly connected with Dis-
crete Morse Theory.
The second main contribution is the application of the framework
mentioned above for developing a parallel algorithm used to compute
a reduction from a cubical cell complex to a CW complex with a minimal amount of cells. This reduction makes the extraction of
(co)homological information simpler. This algorithm focus on n-
dimensional cubical complexes and uses Z as the ground ring, which
makes it useful for computing torsion. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Parallelization strategies for extraction of (co)homological information of digital objects. | es |
dc.type | info:eu-repo/semantics/doctoralThesis | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
idus.format.extent | 82 p. | es |