CAPITULO V


VISUALIZACION


§ 5.1 Introducción

Por visualización se entiende todo lo relacionado directamente con la presentación de los datos en pantalla.

Si bien el presente trabajo no pretende ser referencia de implementaciones de visualización, interesó desde el primer momento concentrar la atención en la utilidad y la posibilidad de extensión en la investigación llevada a cabo hacia diferentes métodos y/o entornos, más que en la belleza estética propiamente dicha en las presentaciones.

Dentro de la visualización de volúmenes podemos identificar, como se mencionó anteriormente, dos tendencias: volume rendering y surface rendering.

Estos distintos acercamientos al problema de la representación gráfica de volúmenes tridimensionales tienen métodos diferentes y se justifica, así, estudiarlos por separado.

§ 5.2 Volume Rendering

La visualización por medio de volume rendering se basa en la información "bruta" que posee el espacio de datos. Esto es, no se intenta hacer una representación por medio de superficies, líneas o algún otro método, sinó que el único elemento de datos es el voxel mismo.

Luego de la identificación del órgano de interés (4.2), el espacio de datos queda reducido a una escena binaria (binary scene) donde cada voxel tiene uno de dos valores posibles, indicando si el mismo pertenece, o nó, al objeto siendo estudiado.

Existen diversos métodos para representar el espacio de datos de la escena binaria. H. Samet [SAM90-1] [SAM90-2] y S. Tanimoto [TAN80] presentan las estructuras de octrees y pirámides, respectivamente. Se recomienda al lector interesado remitirse a estos trabajos para un tratamiento en detalle.

Aunque trabajar en volume rendering requiere de equipos poderosos para lograr resultados aceptables, fué de nuestro interés estudiar, aunque mas no sea de manera experimental, algun método de graficación basado en este tipo de representaciones.

A continuación se presentan un método simple de visualización de volumen, a traves de un recorrido atras-adelante del espacio de datos, y un método híbrido de representación (y visualización) que ha sido utilizado largamente por los especialistas en el area de medical imaging.

5.2.1 Método Back-To-Front para Visualización de Volúmenes

Este método [FRI85] gráfica una colección de voxel cúbicos con un mínimo de preprocesamiento y sin computar las superficies del objeto. Por esta razón, es aplicable en equipos de moderada capacidad.

La (Figura 5-1) muestra una supuesta disposición de un espacio de datos bidimensional (la extensión a 3D es directa) con tres pixels "OBJETO" y el plano de la pantalla.

El algoritmo BTF (back-to-front) recorre secuencialmente, uno por uno, todos los pixels (voxels) de la imagen (escena binaria), proyectando cada uno en la pantalla. El secreto para generar una imagen coherente está en el orden del recorrido del espacio de datos.

Tomando como ejemplo la (Figura 5-1), si el orden de barrido es A, B, C, tenemos que, al proyectar el pixel A, este ocupa (en la pantalla) la posición que debería ocupar el pixel C, por estar este último, mas "cerca" del observador. Sin embargo, cuando llegamos al pixel C, también proyectamos este, sobreescribiendo (en la pantalla), lo que hubiera y dándole el valor de intensidad de C (o, según el método de sombreado que utilicemos, un valor acorde con la distancia pantalla-pixel C).

Si el orden de barrido, en cambio, fuera tal que C sea proyectada antes que A, se generaría un error en la imagen, ya que pixels mas "lejanos" al observador obstruirian a pixels mas "cercanos".

El orden de barrido, entonces, es el punto mas importante de esté método, que se podría resumir como: "Dados un plano de proyección (pantalla) y un espacio de datos, encontrar el orden de barrido apropiado, de manera tal que los elementos mas lejanos al plano de proyección sean procesados siempre antes que los elementos relativamente mas cercanos"

Nuestro espacio de datos, como viene de los equipos TAC, tiene la disposición espacial mostrada en (Figura 5-2).

Definido este sistema coordenado (object space), determinamos ahora un sistema coordenado para la imágen (image space). Definimos este con los ejes x e y coplanares con la pantalla, y con el eje z creciente a medida que se "aleja" del observador.

Tenemos, entonces, un espacio de datos definido sobre un sistema coordenado como se muestra en (Figura 5-2). Para obtener distintas vistas de este espacio, utilizamos los ángulos A, B, y C para rotar el volumen.

Para definir un orden correcto de barrido de los voxels, transformamos este espacio de datos hasta que su sistema coordenado (ya rotado según el punto de vista deseado) coincida con el espacio de la imagen. Una vez obtenido esto, la secuencia de barrido es siempre la misma, como sigue:

1. Loop en la dirección Z (slice por slice)

2. Dentro de cada slice, loop sobre las filas (dirección Y)

3. Loop sobre la dirección X

4. Proyectar el voxel(x,y,z) y colorear

La relación entre los espacios de objeto (object space) y de imagen (image space) se muestra en (Figura 5-3).

La transformación object-space --> image-space es la siguiente:

Dado un voxel con coordenadas (x,y,z) en el espacio de objeto y los ángulos de rotación A, B, y C; las coordenadas en el espacio de imagen (x',y',z') están dadas por:

donde:

y T es la matriz de transformación, que se obtiene:

Siendo S el factor de escalamiento para orientaciones arbitrarias, y (xc, yc, zc) el centro del volúmen de datos (object space), y (xs, ys, zs) el centro del (image space). Siendo normalmente (xs, ys) el centro de la pantalla y (zs) la cantidad de colores dividido 2.

Una forma de permitir factores de escala arbitrarios es reemplazar cada voxel por un esfera cuya proyección es un disco de diámetro , donde a es el tamaño del voxel luego aplicarsele el factor de escala deseado.

Otra forma de no perder resolución la realizar transformaciones con orientaciónes arbitrarias es reemplazar cada voxel por una sucesión de superficies cuadradas (ver 5.2).

Para concluir el método, es importante hacer notar que pueden obtenerse vistas parciales (de subvolúmenes) simplemente cambiando los límites de los loops en el corazón del algoritmo.

5.2.2 Método Híbrido

El método recién descripto posee inconvenientes de pérdida de resolución cuando el volumen de datos de rota a una posición arbitraria no paralela con ninguno de los ejes. Además, la manejabilidad de el espacio de datos es cuestionable, ya que no podemos modificar, de manera simple, los órganos que allí se representan.

Investigadores del Medical Image Processing Group, de la Universidad de Pennsylvania, liderados por el Dr. Herman y J.K Udupa, propusieron, entonces, un método híbrido para representar estructuras espaciales.

Este método se denomina "híbrido" poque amalgama la representación biunívoca de cada voxel, pero lo representa por medio de entidades matemáticas.

Para llegar a la representación final, primero se genera la escena binaria (mediante los métodos de segmentación vistos anteriormente).

Luego, se ejecuta un procedimiento de seguimiento de superficie (surface tracking) que va recorriendo la escena binaria y devuelve un conjunto de superficies planas cuadradas que representan la superficie externa del órgano dentro de la escena.

Las superficies se van generando una por una, a medida que se recorre el volumen de datos. Para mantener la coherencia en la formación de las superficies, se definen "circuitos" en cada voxel (Figura 5-4).

Un objeto se forma conectando voxels unos con otros. Se usa una relación de conectividad que permite la conectividad sólo por donde pasan los circuitos (que, en realidad, son todas las caras del voxel). El objeto es, entonces, el máximo conjunto conexo de superficies.

El algoritmo empieza en un voxel cualquiera (encontrado mediante un barrido de afuera hacia adentro) y se empiezan a seguir los circuitos. Se debe definir la adyacencia de un voxel con otro. En la (Figura 5-5) se observan distintos objetos y como se comporta el algoritmo para distintos tipos de proximidad de voxels.

De esta manera, se forman los conjuntos de superficies, que luego se grafican utilizando los algoritmos estándares de computación gráfica.

§ 5.3 Surface Rendering

Los métodos de graficación de superficies tridimensionales han sido estudiados extensamente en computación gráfica, existiendo excelente literatura sobre el tema de graficación en general [FOL90], y aplicada a estructuras espaciales de datos en particular [SAM90-2].

Nos limitamos, entonces, a explicar como organizamos en nuestro sistema, los parámetros de visualización.

5.3.1 Contornos Dirigidos Nivelados

Basándonos en la disposición espacial de los cortes del equipo de TAC (Figura 5-2), tenemos que los contornos nivelados (generados en 4.3.2.1) tendrían el sistema coordenado mostrado en (Figura 5-6).

Es decir, tenemos un número indefinido de contornos en cada corte que recibimos del equipo TAC. Todos los contornos de cada corte tienen la misma coordenada Z y, debido al método utilizado para obtenerlos, están definidos en sentido horario, tomando como primer vértice al que posea menor x,y (esquina superior izquierda de la pantalla).

Ya definido el sistema coordenado de los contornos, la graficación de los mismos se logra con una simple transformación como la vista en 5.2.1.

5.3.2 Parches Triangulares

Los parches triangulares se forman a partir de los contornos dirigidos nivelados. Por este motivo, comparten el sistema de coordenadas con estos.

Sin embargo, para facilitar la graficación, los triángulos deben formarse siguiendo ciertas convenciones. Las siguientes son las que nosotros utilizamos:

§ 5.4 Sombreado (Shading)

El sombreado artificial de imágenes es un area de mucha investigación y existen numerosos trabajos sobre el tema [FOL90] [SAM90-2] [NOV90] [DUF79].

En los algoritmos estándares de sombreado, existen dos puntos principales que hay que resolver:

El primer aspecto se refiere a determinar, según la posición en el espacio, las luces, sombras, textura del objeto, y otros condicionantes apropiados un color para el objeto en cuestión.

Un método muy usado por su simplicidad es hacer una relación directa entre la intensidad del punto y su distancia al observador. Es importante hacer notar que esta distancia es muy simple de obtener, ya que es la coordenada Z, una vez que el punto ha sido transformado del object space al image space.

El segundo aspecto se refiere a como distribuir el color elegido dentro del objeto (triángulo, cuadrado, etc.). La forma más simple es pintar todo el objeto del mismo color (constant shading), pero esto se traduce en diferencias notables entre un objeto y los adyacentes.

Otro método mas interesante es calcular no un color para el objeto, sinó varios (en diferentes puntos). Luego se subdivide el objeto en elementos mas pequeños y se hace un promedio de los colores elegidos pintándose cada elemento del mismo color (interpolated shading). Manejando la cantidad de divisiones en los objetos se controla el detalle de la imagen.

Por último, la mejor forma de obtener imágenes realistas es utilizar la técnica denominada seguimiento de rayos (ray tracing). Este método simula la trayectoria de cada uno de los rayos de luz que llegan a cada pixel de la pantalla, simulando los choques con los distintos objetos del object space y, eventualmente, con alguna fuente de iluminación.

Por su alto costo computacional, el método de ray tracing no es apropiado para el diseño de un sistema interactivo, pero sí se utiliza para la generación de fotos finales, animación computada y realismo de imágenes.

5.4.1 Nuestra Implementación

Utilizamos el algoritmo de interpolated shading. Podemos resumirlo en los siguientes pasos:

  1. Cálculamos el punto medio de cada triángulo
  2. Los ordenamos según este punto, de "mas lejano" a "mas cercano"
  3. Loop a traves de los triángulos ordenados
  4. Calculamos los colores (según la coordenada Z) de cada vértice del triángulo
  5. Subdividimos el triángulo en N triángulitos mas pequeños
  6. Pintamos estos triangulitos según el gradiente de los colores obtenidos en (4)

En la (Figura 5-7) tenemos un ejemplo de los resultados de este algoritmo.

También investigamos con los algoritmos de ray tracing, pero el tiempo de respuesta era demasiado largo como para incluirlos en el sistema-de-usuario-final.

§ 5.5 Entorno GUI (Graphical User Interface)

El sistema interactivo de visualización es la parte escencial de todo el sistema. El resultado de todo el proceso se ve a través de estos "ojos". Es así que hay que poner especial cuidado en un aspecto crucial en el desarrollo de todo sistema interactivo: el tiempo de respuesta.

Otro de los objetivos fundamentales del trabajo en el análisis de desición sobre la metodología a utilizar fué la facilidad de uso. Los posibles usuarios de un sistema como el propuesto serían personas sin ningún tipo de capacitación ni experiencia en informática. Por este motivo, se decidió implementar el sistema de manera tal que pueda ser utilizado como un juego.

Un entorno GUI es el ambiente adecuado para el sistema. Para desarrollar el prototipo utilizamos Microsoft Windows pero idénticos resultados pueden obtenerse utilizando X-Windows bajo plataformas Unix.

Como dispositivo de entrada usamos principalmente el mouse. Si bien este no es ideal para el ingreso de datos tridimensionales (ya que se maneja con coordenadas planares), se puede diseñar, mediante software, modelos del espacio tridimensional para que el usuario ubique su posición exactamente en las tres dimensiones.

5.5.1 Modalidades de Visualización

El sistema de graficación debe permitir la modificación casi instantánea de los puntos de vista, hasta lograr la ubicación deseada, y la graficación completa (sombreado, coloreado) una vez lograda esta. Si bien la graficación de los contornos es rápida, al incrementar el número de cortes empieza a notarse el retardo en cada ciclo "rotación -> redibujo". Esto, sumado al hecho de que el usuario desea mover demasiado los puntos de vista hasta decidirse por alguno, motivó la realización de la caja límite (bounding box).

Cada estudio puede mostrarse como una caja del tamaño exacto (Figura 5-8) para contener todo el volúmen con los ejes dibujados en distintos colores. La graficación de esta caja es instantánea y por lo tanto, el usuario puede rotarla y/o moverla hasta encontrar la ubicación deseada, cambiando entonces la modalidad de graficación de "Axis" (o ejes) a "Default" (por defecto).

Cada ventana del sistema puede mostrarse en una de tres modalidades:

La representación por DEFAULT está basada en estructuras de alambre (wireframe) y tiene por objeto obtener una vista rápida del objeto.

La rutina de SHADING se basa en un sombreado por interpolación entre los tres vértices del triángulo que está siendo sombreado. El color en cada vértice se obtiene por una relación directa con la distancia al observador (puntos mas lejanos mas oscuros), por lo que deben ordenarse previamente los triángulos.

Ya que el objetivo del trabajo no fué diseñar un sistema completo de graficación sino demostrar la performance del enfoque dado. Se Investigó la posibilidad de incorporar rutinas de ray-tracing para obtener figuras mas realistas pero, debido a los altos costos computacionales de los algoritmos, el tiempo de respuesta era inaceptable. Existe excelente bibliografía sobre el tema, como así también paquetes preparados especialmente para visualizar datos volumétricos. Sin embargo, estos paquetes frecuentemente corren en equipos especialmente diseñados.