PDF de programación - Herramientas de modelado multirresolución de imágenes 3D utilizando wavelets

Herramientas de modelado multirresolución de imágenes 3D

utilizando wavelets

José Miguel Espadero †, Luis Rincón ‡

† U. Politécnica de Madrid. Dep. de Tecnología Fotónica.

Campus de Montegancedo s/n. 28660 Boadilla del Monte. Madrid, España.

‡ U. Rey Juan Carlos. Dep. de Ciencias Experimentales.

C. Tulipán, s/n. 28933 Móstoles. Madrid, España.

19 de octubre de 1999

Resumen

El procesamiento de objetos tridimensionales requiere la utilización de técnicas que manejen eficien-
temente una gran cantidad de datos. Las transformadas wavelet se han revelado como una herramienta
muy potente en situaciones en las que es preciso tratar un elevado volumen de datos. Este tipo de trans-
formadas permite representar los objetos en distintos niveles de resolución, con lo que es posible realizar
manipulaciones sobre los mismos más eficientemente. Se presentan dos herramientas de modelado multir-
resolución, una de las cuales ajusta nubes de puntos 3D a mallas con una determinada topología, mientras
que la otra es capaz de efectuar diferentes procesos sobre mallas tridimensionales utilizando wavelets.
Los objetos se pueden visualizar mediante mallas en alambre de celdas hexagonales o mediante mallas de
facetas triangulares.

Palabras Clave: Visualización 3D, Modelado 3D, Wavelets.

1 Introducción

Las aplicaciones relacionadas con el procesamiento de imágenes y la visión por computador se caracterizan
habitualmente por su gran voracidad de recursos de memoria y cómputo. Por ello, es muy importante contar
con modelos de representación del mundo real y de los objetos que lo componen que por un lado permitan
describir sus propiedades de forma sencilla, sin implicar elevados requerimientos de memoria, y por otro
favorezcan el desarrollo de algoritmos y herramientas eficientes que posibiliten su manipulación, reduciendo
al máximo el tiempo de procesamiento y manteniendo en todo caso la precisión necesaria en los resultados.

No es extraño entonces el interés que tradicionalmente han despertado las técnicas de representación
jerárquica y multirresolución en el campo de la visión por computador [1][2]. Estas técnicas permiten rep-
resentar los objetos en varios niveles de resolución con distintos niveles de detalle y que a su vez conllevan
diferentes necesidades en cuanto a almacenamiento y cómputo. En particular, la manipulación de repre-
sentaciones con bajo nivel de resolución implica requerimientos de memoria bajos y velocidades de cálculo
elevadas. Como inconveniente, la precisión de los resultados obtenidos es menor. De cualquier modo, ciertas
tareas como, por ejemplo, la clasificación de objetos, pueden beneficiarse del análisis de los datos a distintas
escalas.

Desde el punto de vista del modelado de objetos, las técnicas basadas en la transformada wavelet se han
considerado como una nueva formalización de los métodos multirresolución desarrollados en la década de los

1

80. Estas transformadas han renovado el interés sobre las técnicas multirresolución, proporcionando una for-
malización matemática rigurosa, de la cual se deriva un marco en el que se están desarrollando constantemente
nuevos algoritmos y técnicas extremadamente eficientes con aplicaciones muy diversas.

En este artículo se presentan dos herramientas que permiten trabajar con un modelo multirresolución
de representación de objetos en tres dimensiones. La primera, denominada SAI, es una herramienta que
aproxima una nube de puntos extraída de un objeto 3D al modelo utilizado. La segunda, denominada Xwave,
presenta un interfaz gráfico a partir del cual es posible efectuar de manera eficiente diversas operaciones
sobre la representación tridimensional proporcionada por SAI. Xwave puede trabajar en múltiples niveles de
resolución, con lo que es capaz de procesar los datos del objeto con diferentes niveles de detalle. SAI y Xwave
han sido desarrolladas utilizando herramientas de libre distribución, lo que ha asegurado su transportabilidad
a diferentes plataformas sin necesidad de efectuar modificación ninguna en su código fuente.

En primer lugar se presenta el modelo multirresolución de representación de objetos utilizado. A contin-
uación se procede a la descripción de SAI y Xwave, exponiendo las ventajas que proporciona el empleo de
herramientas de procesamiento multirresolución. Seguidamente se muestran ejemplos de utilización de Xwave
sobre objetos provenientes de diversas fuentes. Por último, analizaremos las herramientas de libre distribución
empleadas durante la fase de desarrollo.

2 Modelo 3D multirresolución utilizando wavelets

Los objetos tridimensionales considerados proceden de conjuntos discretos de muestras tomadas sobre los
objetos, conformando una nube de puntos que contiene información superficial de los mismos. En cada punto
se registran sus coordenadas espaciales, aunque puede almacenarse también información de naturaleza no
geométrica como color, temperatura, textura o cualquier otra magnitud asociada al mismo. Las nubes de
puntos pueden proceder de diversas fuentes, entre las que pueden encontrarse sensores de posición manuales,
sensores láser, sistemas de visión con varias cámaras o con luz estructurada, ultrasonidos, imágenes adquiridas
mediante tomografía, imágenes sintéticas generadas con herramientas CAD, etc.

En [4] y en [5] se describe un sistema que permite obtener una representación multirresolución de un
conjunto disperso de puntos pertenecientes a la superficie de objetos reales mediante wavelets esféricos. A
continuación vamos a detallar el proceso efectuado.

Una vez obtenida la nube de puntos, y antes de definir el modelo multirresolución, es preciso construir
una relación de vecindad que sirva para conectar los puntos de la nube con sus vecinos más próximos. Esta
relación de vecindad se genera estableciendo conexiones entre los puntos de la nube de acuerdo con una
cierta topología generada de forma que cumpla la propiedad de conectividad por subdivisión. Se ha utilizado
como modelo inicial un icosaedro, que conforma una malla cuyas caras (facetas) triangulares se subdividen
recursivamente. En cada operación de subdivisión de la malla completa, cada una de las facetas triangulares
se particiona en otras cuatro, todas ellas de igual área. Así se obtiene una superficie esférica discretizada en
una malla de 20

4 j pequeñas facetas triangulares, siendo j el orden o nivel de resolución de la malla.

La estructura geométrica dual del icosaedro es el domo geodésico, constituido por una malla de alambre
de celdas hexagonales. Cada vértice del domo presenta la propiedad de que todos los nodos de la malla
tienen valencia (número de vecinos) constante e igual a 3. Si en el icosaedro subdividido de resolución j hay
4 j nodos en la malla de alambre. Así puede establecerse
20
un homomorfismo que hace corresponder cada vértice o nodo del domo a una faceta triangular del icosaedro
subdividido.

4 j facetas triangulares, igualmente existen 20

El siguiente paso consiste en aproximar la nube de puntos original a una malla de celdas hexagonales,
conservando en ésta la topología del domo geodésico. Para ello, se asociará cada punto de la nube a un vértice
del domo (en la representación dual de la malla de triángulos, al centro de una faceta). Entre las distintas

2



soluciones existentes para realizar tal operación, se encuentra el proceso descrito por Ikeuchi et al. en [7].
El ajuste se lleva a cabo mediante un proceso iterativo, en el que interviene una combinación de fuerzas que
regularizan la curvatura local de la malla de alambre e intentan ajustarla a la nube de puntos de entrada. Así
se obtendrá la malla de alambre que representa la superficie original. En cada vértice o nodo se almacenará la
información geométrica (coordenadas espaciales) y la información no geométrica contenida en cada punto de
la nube.

En este punto se dispone de la malla que representa al objeto, encontrándose ésta en su nivel de resolución
original, que es el máximo posible. Utilizando el esquema de subdivisión con wavelets esféricos planteado
en [4], es posible reducir el nivel de resolución utilizado para representar el objeto, y regenerar posterior-
mente la información de la malla en el nivel de resolución original. La generación de la representación de
nivel inmediatamente inferior se efectúa mediante un proceso de análisis, consistente en fusionar las facetas
triangulares de 4 a 1 de acuerdo con las relaciones de vecindad presentes en la malla dual de alambre. Así
será entonces posible obtener representaciones del objeto en niveles de resolución inferior hasta llegar al nivel
mínimo (nivel de resolución 1), en el cual la malla estaría compuesta por 20 vértices, y la malla dual por 20
facetas triangulares. La regeneración de la representación del nivel inmediato superior, denominada síntesis,
se obtiene mediante la subdivisión de las facetas de 1 a 4.

El esquema de wavelets esféricos empleado asegura que, si sobre una malla se efectúan únicamente opera-
ciones de análisis y de síntesis, la representación del objeto en un determinado nivel j siempre será la misma.
Es decir, las operaciones de análisis y de síntesis no destruyen la información de la malla, sino que sirven para
trabajar con representaciones del objeto en distintos niveles de resolución, y siempre será posible reconstruir
la información sin cambios con la resolución original y con cualquiera de las resoluciones inferiores. És-
tas últimas no son sino aproximaciones groseras de la representación original, eliminando de ella una mayor
cantidad de detalles a medida que desciende la resolución.

Para las operaciones de análisis y síntesis nos valdremos de la transformada de Haar, que presenta una
, lo que la constituye en una herramienta extremadamente eficiente para tratar

complejidad de orden O
n
problemas con un gran volumen de datos.

El modelo multirresolución pretende representar el objeto con un grado de detalle escogido según la
voluntad del operador: un nivel de detalle mayor requerirá m