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

Resumen

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.