INGENIERÍA DE SISTEMAS
APLICACIÓN DEL ALGORITMO FAST MARCHING EN
AMBIENTES TRIDIMENSIONALES:
CASO DE ESTUDIO EN IMÁGENES MÉDICAS
JUNIO 2009
Autor:
Luis Andrés Almanza Caicedo
Director
Leonardo Flórez Valencia
Temas
•
•
•
•
•
•
Introducción
Objetivos
Soporte Teorico – Dijkstra , Fast Marching
Explicación Fast Marching.
Resultados.
Conclusiones.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES: CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Causas de muerte en el mundo
Se calcula que en 2005
murieron 17,5 millones de
personas a causa de las ECV.
Tomando de OMS - http://www.who.int/cardiovascular_diseases/en/
Enfermedades vasos sanguíneos
Angiografía
Tomando de WIKIPEDIA
Angiografía
Tomando de Custom Medical Stock Photo
Temas
•
•
•
•
•
•
Introducción
Objetivos
Soporte Teorico – Dijkstra , Fast Marching
Explicación Fast Marching.
Resultados.
Conclusiones.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES: CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Objetivos
Objetivo General
Estudiar y analizar el algoritmo Fast Marching en un contexto
de imágenes médicas tridimensionales.
Objetivos Específicos
1. Implementar una versión del algoritmo Fast Marching en tres
dimensiones.
2. Describir las entradas, las salidas y el comportamiento del
algoritmo implementado en imágenes tridimensionales.
3. Proponer un método de visualización de los datos asociados
al algoritmo (entradas, salidas y parámetros).
4. Explorar las posibilidades para la segmentación de
estructuras cilíndricas, usando el algoritmo implementado.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN
AMBIENTES TRIDIMENSIONALES:
CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Temas
•
•
•
•
•
•
Introducción
Objetivos
Soporte Teorico – Dijkstra , Fast Marching
Explicación Fast Marching.
Resultados.
Conclusiones.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES: CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Algoritmo Dijkstra
• Sea G=(V,A) un grafo dirigido y etiquetado.
• Sean los vértices a ∈ V y z ∈ V; a es el vértice de
origen y z el vértice de destino.
• Sea un conjunto C ⊂ V, que contiene los vértices de V
cuyo camino más corto desde a todavía no se conoce.
• Sea un vector D, con tantas dimensiones como
elementos tiene V, y que “guarda” las distancias entre
a y cada uno de los vértices de V.
• Sea, finalmente, otro vector, P, con las mismas
dimensiones que D, y que conserva la información
sobre qué vértice precede a cada uno de los vértices
en el camino.
Tomando de - Aplicación del método de Dijkstra en
Java - http://www.cif.acuareladelsur.org/tutoriales/prim.pdf
Algoritmo Dijkstra
1. C ← V
2. Para todo vértice i ∈ C, i ≠ a, se establece
Di ← ∞ ; Da ← 0
3. Para todo vértice i ∈ C se establece Pi = a
4. Se obtiene el vértice s ∈ C tal que no existe otro
vértice w ∈ C tal que Dw < Ds
▫ Si s = z entonces se ha terminado el algoritmo.
5. Se elimina de C el vértice s: C ← C−{s}
6. Para cada arista e ∈ A de longitud l, que une el
vértice s con algún otro vértice t ∈ C,
▫ o Si l+Ds < Dt, entonces:
 1. Se establece Dt ← l+Ds
 2. Se establece Pt ← s
7. Se regresa al paso 4
Tomando de - Aplicación del método de Dijkstra en
Java - http://www.cif.acuareladelsur.org/tutoriales/prim.pdf
Algoritmo Fast Marching
• Se marcan todos los putos aceptados(vivo) de la grilla
en D.
• Se marcan todos los puntos considerados(frente) de
la grilla en D.
• Solucionar la ecuación Eikonal para los puntos
considerados.
• Se marcan los considerados como aceptados,
dependiendo de la solución de la ecuación Eikonal.
• Marcar como lejanos todos los puntos restantes de la
grilla en D.
• Repetir hasta recorrer el dominio D o cumplir una
condición de salida
Algoritmo Fast Marching
Similitudes
• Inicialización.
• Manejo de prioridad de nodos.
Retornar
vecinos
2
1
• Actualización de costos de los
nodos.
Actualizar
costos
Temas
•
•
•
•
•
•
Introducción
Objetivos
Soporte Teorico – Dijkstra , Fast Marching.
Explicación Fast Marching.
Resultados.
Conclusiones.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES: CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Aporte Trabajo de Grado
o Taxonomía UML
o Algoritmo colisión de frentes.
o Algoritmo de camino básico entre puntos
semilla.
Diagrama de clases
Diagrama de actividad - Inicializar
Diagrama de actividad - Base
Temas
•
•
•
•
•
•
Introducción
Objetivos
Soporte Teorico – Dijkstra , Fast Marching.
Explicación Fast Marching.
Resultados.
Conclusiones.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES: CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Explicacion de Resultados
• Resultados del trabajo de grado
• Muestra del video
• Mostrar los casos funcionales
Temas
•
•
•
•
•
•
Introducción
Objetivos
Soporte Teorico – Dijkstra , Fast Marching.
Explicación Fast Marching.
Resultados.
Conclusiones.
APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES: CASO DE ESTUDIO EN IMÁGENES MÉDICAS
Conclusiones
• Conclusiones del trabajo de grado
• Explicacion de cada uno
Bibliografía
• OMS – Organización Mundial de la Salud
• Aplicación del método de Dijkstra en Java http://www.cif.acuareladelsur.org/tutoriales/pr
im.pdf
• LEVEL SET METHODS and FAST MARCHING
METHODS http://math.berkeley.edu/~sethian/
Descargar

Slide 1