Optimización y paralelización de un algoritmo de generación de Skeletons a partir de mallas geométricas aplicado a estructuras biológicas

Abstract

El estudio cuantitativo de estructuras microscópicas 3D requiere de herramientas computacionales, tanto para realizar mediciones como para su visualización, dada su complejidad y gran volumen. Una de las herramientas para medir y visualizar estas estructuras es el skeleton. Un skeleton es la representacion simplificada de la estructura en forma de grafo, compuesta por nodos y segmentos. Si bien existen múltiples algoritmos para su generación, estos buscan generalmente mantener propiedades topológicas y geométricas del objeto de estudio. Actualmente se cuenta con la implementación de un algoritmo de generación de skeletons [2], basado en el algoritmo propuesto por Au et al [3]. Esta implementación, si bien entrega resultados satisfactorios, presenta tiempos de cálculo muy extensos. Dado lo anterior, es que esta memoriam tiene como objetivo analizar y optimizar el tiempo de ejecución de esta implementación. En este trabajo se realizaron optimizaciones seriales y la paralelización del cálculo. La optimización serial incluyó: (1) implementación del algoritmo con una nueva estructura de datos: Halfedge, (2) optimización en la actualización de costos de arcos, (3) optimización en el uso de la cola de costos y (4) optimización de estructuras de datos. La paralelización fue realizada sobre una de las etapas más demandantes del algoritmo usando la unidad de procesamiento gráfico (GPU). Para validar las optimizaciones y paralelización, se realizaron pruebas de la correctitud y speed-up alcanzado en: (1) modelos 3D creados simples, (2) modelos sintéticos de estructuras biológicas y (3) modelos de estructuras biológicas obtenidas de imágenes de microscopía. Con las optimizaciones y paralelización implementados, se logró una mejora sustancial en el tiempo, pasando de días a minutos o incluso segundos. Además, se verificó que estas mejoras mantienen los skeletons resultantes bien definidos, vale decir, mantienen las propiedades que deben cumplir.