Date post: | 23-Jan-2016 |
Category: |
Documents |
Upload: | ricardo-oquendo |
View: | 215 times |
Download: | 0 times |
Ernesto Coto
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE
SUPERFICIES GENERADAS UTILIZANDO MODELOS
DEFORMABLES
Laboratorio de Computación GráficaUniversidad Central de Venezuela
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• La segmentación de imágenes por computadora ha cobrado una gran importancia en el tratamiento de imágenes médicas, biológicas, geológicas, etc.
• Dificultad: La gran cantidad de formas y las variaciones en la calidad de las imágenes
Segmentación de MRI del ventrículo izquierdo del corazón
usando umbralización
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Los modelos deformables son una estrategia bien reconocida en lo que respecta a la segmentación, ajuste y rastreo de imágenes
• Basados en un modelo y soportan mecanismos de interacción
Segmentación de MRI del ventrículo izquierdo del corazón
usando modelos deformables paramétricos activos
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• La popularidad de los modelos deformables se debe a los Modelos de Contorno Activo o snakes
• Spline minimizador de energía que se deforma en dirección de características de interés en la imagen, como líneas y bordes
• Inicialización del snake
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Corrección interactiva del contorno
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Variantes– Programacion Dinámica (Animi et al., 1990)
– B-Snakes (Menet et al., 1990)
– Balloons (Cohen, 1991)
– Algoritmo Voraz (Williams y Shah, 1992)
– Contornos Activos Duales (Gunn y Nixon, 1994)
– G-Snakes (Lai y Chin, 1995)
– T-Snakes (Terzopoulos y McInerney, 1999)
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Se presenta una estrategia de generación de mallas volumétricas tridimensionales a partir de un conjunto de contornos obtenidos de las imágenes de cortes transversales de un objeto
• Se propone una nueva variante de la técnica de T-Snakes
Reconstrucción de segmento de tibia
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Adquirir imágenes de cortes transversales
• Detectar el contorno de la estructura en un corte
• Propagar la detección de contornos al resto de los cortes
• Generar la superficie de la estructura usando los contornos detectados
• Generar el volumen de tetraedros de la estructura
Adquisición de la Data
Construcción de la Superficie
Detección de Contornos
Propagación de la deformación
Construcción del Volumen
• Etapas de la reconstrucción
• Para la detección de contornos se utiliza el modelo T-Snake
• Fase de Deformación
• Fase de Reparametrización
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Cuadrícula (grid) T-Snake
• Reparametrización Fase I
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
(a) (b) (c)
Ajuste del modelo a la cuadrícula luego
de la Fase de Deformación
• Reparametrización Fase II
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
(a) (b) (c)
Cálculo de vertices “quemados” (burned) de acuerdo
al principio de propagación de flamas
• Algoritmo T-Snake
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
1. Por M pasos de tiempo
(a) Calcule las fuerzas internas y externas que actúan sobre
los nodos del modelo y actualizar sus posiciones
2. Reparametrización Fase I
3. Reparametrización Fase II
4. Determine el conjunto correspondiente de triángulos de borde
5. Para todos los elementos actuales, determinar si el elemento
todavía es válido
6. Verificar condición de terminación: Todos los nodos deben estar
congelados
• Características y restricciones del T-Snake– Transformación Topológicas– Flexibilidad Geométrica– Multiples T-Snakes
• Detección de colisiones y evasión– Capacidades de Multiresolución– Control Interactivo– Preservación de Topología
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Limitaciones del T-Snake– Puede expandirse o contraerse, pero no ambas a la
vez– La cuadricula es arbitraria. Es posible generar
demasiados o muy pocos nodos– No se garantiza correctitud topológica solo
consistencia topológica– La resolución de la cuadricula limita el tamaño de la
característica mínima segmentable
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Cuadrícula
alternativa
• Este trabajo utiliza una nueva variante del T-Snake con preservación de Topología– Se conserva igual la Fase de Deformación
• Solo se elimina un parámetro
– En la reparametrización se utiliza otra cuadrícula para simplificar cálculos
– Se calcula la temperatura de todo el T-Snake en lugar de en cada nodo
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Cuadrícula
de la variante
• Reparametrización Fase I:
– Se verifica que cada nodo sigue la dirección correcta de deformación y se aplica una corrección de movimiento de ser necesario
• Reparametrización Fase II:
– Calcula los puntos de intersección con la cuadricula para calcular los nuevos nodos del modelo
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• La nueva variante vs. el T-Snake original
– Mismas limitaciones– Mismas características y restricciones, con
excepción de la adaptabilidad topológica
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• La nueva variante vs. el T-Snake original– Cantidad de Memoria
CM(T-Snake)>CM(T-Snake var)
– Tiempo de Ejecución
T(T-Snake)>T(T-Snake var)
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Adquirir imágenes de cortes transversales
• Detectar el contorno de la estructura en un corte
• Propagar la detección de contornos al resto de los cortes
• Generar la superficie de la estructura usando los contornos detectados
• Generar el volumen de tetraedros de la estructura
Adquisición de la Data
Construcción de la Superficie
Detección de Contornos
Propagación de la deformación
Construcción del Volumen
• Etapas de la reconstrucción
• Extensión a 3D: T-Surfaces
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Aproximación de esferaCelda de grid
• Propagación de la deformación (Cohen, 1991)
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Propagación vs. T-Surface– Elimina la necesidad de la cuadrícula – Sólo es preciso mantener en memoria la
imagen que se está tratando • Ahorro de al menos (I-1)*B + 3C3 bytes,
para un conjunto de I imágenes de B bytes, y una cuadricula de CxCxC
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Adquirir imágenes de cortes transversales
• Detectar el contorno de la estructura en un corte
• Propagar la detección de contornos al resto de los cortes
• Generar la superficie de la estructura usando los contornos detectados
• Generar el volumen de tetraedros de la estructura
Adquisición de la Data
Construcción de la Superficie
Detección de Contornos
Propagación de la deformación
Construcción del Volumen
• Etapas de la reconstrucción
• Construcción de la superficie– Se usa un esquema simple de triangulación
entre cada par de cortes
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Construcción de la superficie– Es posible que los contornos entre pares de cortes no estén alineados
– Haciendo necesario un alineamiento
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Construcción de la superficie– Se utiliza un triangulador 2D para generar los
triangulos superiores e inferiores de la superficie
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Ejemplo sencillo de superficie de cilindro
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Adquirir imágenes de cortes transversales
• Detectar el contorno de la estructura en un corte
• Propagar la detección de contornos al resto de los cortes
• Generar la superficie de la estructura usando los contornos detectados
• Generar el volumen de tetraedros de la estructura
Adquisición de la Data
Construcción de la Superficie
Detección de Contornos
Propagación de la deformación
Construcción del Volumen
• Etapas de la reconstrucción
• Construcción del Volumen– Por lo general se usan hexaedros o tetraedros– Se construyen volúmenes de calidad en donde
las primitivas que lo conforman cumplen ciertas restricciones geométricas que hacen el volumen adecuado para su análisis
– Se estudiaron cuatro técnicas de generación de mallas volumétricas de tetraedros
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Técnicas de tetraedrización– Octrees– Avance Frontal– Delaunay– Tranformaciones Locales
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Resultados– Reconstruir de estructuras sencillas
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Resultados
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Análisis de Elementos Finitos de un segmento de tibia usando MSC.Nastran. 20377 tetraedros.
• Resultados
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Segmento del hombro izquierdo del Hombre Visible. 131 imágenes de 1748x966 pixeles. 4730 triángulos.
• Resultados
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Segmento de la pierna derecha del Hombre Visible. Extraída a partir de 465 imágenes de 1748x966 pixeles. 113895 triángulos.
• Conclusiones– Se desarrolló una nueva variante de la técnica de
T-Snakes con preservación de topología
– La técnica planteada para la generación de la superficie es rápida, efectiva y sencilla
– Se experimentó satisfactoriamente con la generación de mallas de volúmenes con tetraedros
– Este trabajo demuestra que es posible generar mallas volumétricas a partir de las superficies generadas con las técnicas planteadas
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Recomendaciones y Trabajos Futuros
– Realizar la detección de los contornos usando un T-Snake sin preservación de topología
– Generalizar la técnica de reconstrucción de la superficie o utilizar un modelo deformable 3D
– Mejorar la fase de deformación del T-Snake original
– Incorporar un mecanismo de inicialización automática
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
DEMOSTRACION
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
CM(T-Snake var) = CM(Parámetros) + CM(Nodos) +CM(Imagen) + CM(Frontera) + CM(Temperatura) + CM(Cuadrícula)
CM(T-Snake) = CM(Parámetros) + CM(Nodos) +CM(Imagen)+CM(Frontera)+ CM(Cuadricula) + CM(Quemados)
Asumiendo N nodos, la misma imagen y que los tipos elementales ocupan una palabra de memoria…
CM(T-Snake) – CM(T-Snake var)=N – 1 + CM(Cuadricula) + CM(Quemados)
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
– Esto es debido a la eliminación de :
• Cálculo de los vertices quemados O(N)• Actualización de la temperatura de los
nodos O(N)• Actualización de las aristas de la cuadrícula
O(C2)
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES