Download Presentación de PowerPoint - Centro de Computación Gráfica

Laboratorio de Computación Gráfica
Universidad Central de Venezuela
RECONSTRUCCIÓN DE VOLÚMENES
CON TETRAEDROS A PARTIR DE
SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
Ernesto Coto
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
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
• 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
• Etapas de la reconstrucción
Adquisición de
la Data
Detección de
Contornos
• Adquirir imágenes de cortes transversales
• Detectar el contorno de la estructura en un corte
Propagación de
la deformación
• Propagar la detección de contornos al resto de los cortes
Construcción
de la Superficie
• Generar la superficie de la estructura usando los
contornos detectados
Construcción
del Volumen
• Generar el volumen de tetraedros de la estructura
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Para la detección de contornos se utiliza el modelo
T-Snake
• Fase de Deformación
• Fase de Reparametrización
Cuadrícula (grid)
T-Snake
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Reparametrización Fase I
(a)
(b)
Ajuste del modelo a la cuadrícula luego
de la Fase de Deformación
(c)
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Reparametrización Fase II
(a)
(b)
(c)
Cálculo de vertices “quemados” (burned) de acuerdo
al principio de propagación de flamas
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Algoritmo T-Snake
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
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
Cuadrícula
alternativa
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
Cuadrícula
de la variante
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
• Etapas de la reconstrucción
Adquisición de
la Data
Detección de
Contornos
• Adquirir imágenes de cortes transversales
• Detectar el contorno de la estructura en un corte
Propagación de
la deformación
• Propagar la detección de contornos al resto de los cortes
Construcción
de la Superficie
• Generar la superficie de la estructura usando los
contornos detectados
Construcción
del Volumen
• Generar el volumen de tetraedros de la estructura
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Extensión a 3D: T-Surfaces
Celda de grid
Aproximación de esfera
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
• Etapas de la reconstrucción
Adquisición de
la Data
Detección de
Contornos
Propagación de
la deformación
Construcción
de la Superficie
Construcción
del Volumen
• 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
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
Ejemplo sencillo de superficie de cilindro
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Etapas de la reconstrucción
Adquisición de
la Data
Detección de
Contornos
Propagación de
la deformación
Construcción
de la Superficie
Construcción
del Volumen
• 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
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
Análisis de Elementos Finitos de un segmento de tibia usando
MSC.Nastran.
20377 tetraedros.
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Resultados
Segmento del hombro izquierdo del Hombre Visible.
131 imágenes de 1748x966 pixeles. 4730 triángulos.
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• Resultados
Segmento de la pierna derecha del Hombre Visible. Extraída a
partir de 465 imágenes de 1748x966 pixeles. 113895 triángulos.
RECONSTRUCCIÓN DE VOLÚMENES CON TETRAEDROS A
PARTIR DE SUPERFICIES GENERADAS UTILIZANDO
MODELOS DEFORMABLES
• 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
DEMOSTRACION
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
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)