Parallelization strategies for extraction of (co)homological information of digital objects

Résumé

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.