APLICACIÓN DEL ALGORITMO FAST MARCHING EN AMBIENTES TRIDIMENSIONALES:CASO DE ESTUDIO EN IMÁGENES MÉDICAS

Autor:Luis Andrés Almanza CaicedoDirectorLeonardo Flórez Valencia

INGENIERÍA DE SISTEMAS

JUNIO 2009

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

Tomando de OMS - http://www.who.int/cardiovascular_diseases/en/

Se calcula que en 2005 murieron 17,5 millones de personas a causa de las ECV.

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 GeneralEstudiar y analizar el algoritmo Fast Marching en un

contexto de imágenes médicas tridimensionales.Objetivos Específicos1. 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 enJava - http://www.cif.acuareladelsur.org/tutoriales/prim.pdf

Algoritmo Dijkstra1. C ← V2. Para todo vértice i ∈ C, i ≠ a, se establece

Di ← ∞ ; Da ← 03. Para todo vértice i ∈ C se establece Pi = a4. 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 enJava - 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.

Actualización de costos de los nodos.

1Retornar vecinos

2Actualizar 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

oTaxonomía UMLoAlgoritmo colisión de frentes.oAlgoritmo de camino básico entre puntos

semilla.

Diagrama de clases

Dia

gra

ma d

e a

ctivid

ad -

Inicia

lizar

Dia

gra

ma d

e a

ctivid

ad - B

ase

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/prim.pdf

•LEVEL SET METHODS and FAST MARCHING METHODS -http://math.berkeley.edu/~sethian/