Resumen de Parallelization strategies for extraction of (co)homological information of digital objects
- español
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.
- English
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.
