Ingeniero Civil en Computación / 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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/116207 |
| Date | January 2014 |
| Creators | Rojas Hernández, Iván Yerko |
| Contributors | Hitschfeld Kahler, Nancy Viola, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ciencias de la Computación, Hartel Grundler, Steffen, Paredes Moraleda, Rodrigo |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0079 seconds