Analizador de la transformada Analizador de la transformada de Haar desde un punto de de Haar desde un punto de

vista topológicovista topológico

Procesamiento de Imágenes digitales

Curso 2002/2003

J. Roberto Moreno Guerra

Fco. Javier Rojas Guerrero

José Luis Salas Espina

Ricardo Toro Llano

Índice

1. Introducción.

2. Nuestro trabajo.3. La transformada de Haar.

4. Propiedades de la transformada de Haar.

5. Conclusiones e investigación.

6. Bibliografía y documentación.

1. Introducción.

• Nuestra investigación se centra en el análisis de transformadas de líneas rectas.

• Usaremos para nuestro estudio imágenes:– Binarias.– De dimensión 8x8.

• El analizador no admite imágenes en escala de grises.

1. Introducción.

• Gracias a las propiedades de las transformadas, y en particular de las transformadas bidimensionales se pueden conseguir mejoras, restauraciones, compresiones, codificaciones y descripción de imágenes.

• Usos de la transformada de Haar:– Compresión de datos de señales no estacionarias.

– Extracción de aristas.

– Compresión de imágenes.

2. Nuestro trabajo.

Diseño de un analizador de imágenes usando la transformada de Haar en Matlab.

Usar dicho analizador en: Compresión de imágenes. Comportamiento topológico de las imágenes

frente al ruído.

3. La transformada de Haar.

• Propiedades:– Lineal.– Real.– Muy rápida (de orden O(N) ).

• Se basa en una clase de matrices que cumplen:– Son ortogonales (traspuesta = inversa).– Sus valores son 0 ó potencias de dos.

3.- La transformada de Haar.

Distribución de píxeles:

Píxeles más significativos (los de mayor valor)

Píxeles menos significativos (los de valor más pequeño)

T =

3. La transformada de Haar.

Linealidad:

Se basa en sumas, restas y divisiones.

Supongamos dos números a y b vecinos.

Transformada que sustituye a y b por su media (m) y su diferencia (d):

Idea: Si a y b están cercanos almacenar su diferencia es más eficiente.

3. La transformada de Haar.

Linealidad:

Con este método no perdemos información, podemos recuperar a y b así:

Podemos realizar este procedimiento invirtiendo una matriz 2x2 (en este caso).

Esta es la idea que utiliza la transformada de Haar.

3. La transformada de Haar. Algoritmo.

Paso 1:

....41064

Calcular las medias para cada pareja:

3. La transformada de Haar.

Algoritmo. Paso 1:

41064 1 2 3 1 ]

Calcular las diferencias:

Vector que llevamos calculado:

Vector original:

3. La transformada de Haar.

Algoritmo.

Paso 2:

75[ 31

Media

Diferencias

+

Permanece igual!!

3. La transformada de Haar.

Algoritmo.

Paso 3:

6[ 1

Media

Diferencia

+

Permanece igual!!

3. La transformada de Haar.

Todas estas transformaciones sucesivas aplicadas a un vector se pueden ver de forma matricial:

3. La transformada de Haar.

Todas estas transformaciones sucesivas aplicadas a un vector se pueden ver de forma matricial:

3. La transformada de Haar.

Todas estas transformaciones sucesivas aplicadas a un vector se pueden ver de forma matricial:

3. La transformada de Haar.

Matriz de Haar

3. La transformada de Haar.

Luego, las transformaciones se pueden realizar aplicando las fórmulas:

Esta es la llamada transformada rápida de Haar. Es de orden O(N log N).

3. La transformada de Haar.

Ejemplo:

3. La transformada de Haar.

Ejemplo:

Aplicar el algoritmo anterior por filas a la matriz M:

M H1

3. La transformada de Haar.

Ejemplo:

Aplicar el algoritmo anterior por columnas a la matriz H1:

H1 N

3. La transformada de Haar.

Ejemplo:

De esta forma obtenemos la nueva matriz N que representa a la imagen:

4. Propiedades de la transformada de Haar.

• Esta transformada no ha recibido últimamente demasiada atención, debido a las mejoras que se consiguen con otras transformadas, aunque éstas sean más complejas.

• Aplicaciones:– Compresión de imágenes.– Extracción de aristas.

• Con un algoritmo rápido esta transformada puede ser más eficiente en cuanto a la compresión de datos.

5. Conclusiones e investigación.

Número de iteraciones del algoritmo.

Compresión de imágenes.

Comportamiento topológico frente al ruído.

5. Conclusiones e investigación. Número de iteraciones:

Para una imagen de 8x8 el número máximo de iteraciones es 3.

n=1

n=3

n=2

n=4

5. Conclusiones e investigación.

Número de iteraciones:

Ejemplo para n=4 iteraciones.

Imagen original Imagen codificada Imagen obtenida

No se recupera la imagenoriginal!!

5. Conclusiones e investigación.

Compresión:

Obtenemos la nueva imagen N mediante el algoritmo de medias y diferencias visto a partir de la matriz original M.

Eliminamos información innecesaria de la matriz N.

Se reconstruye la imagen original M.

5. Conclusiones e investigación. Compresión:

Elegir una tal que los valores de la matriz N que sean menores que dicha toman automáticamente el valor 0.

Ejemplo:

5. Conclusiones e investigación.

Compresión - ejemplo:

Elegimos = 0

5. Conclusiones e investigación.

Compresión - ejemplo:

Se obtiene la imagen original a partir de la matriz N’

Comprimida al 6%

¡¡Se mantiene la topología!!

5. Conclusiones e investigación.

Compresión - ejemplo:

Si aumentamos el número de iteraciones:

No conserva latopología!!!

n=2

n=4

Imagen original 11 %

13 %

5. Conclusiones e investigación.

Comportamiento topológico frente al ruído.

Si no hay pérdida de información, la imagen se recupera en su totatidad junto con el ruido que ya tuviese.

Ruido

Ejemplo con pérdida de información:

5. Conclusiones e investigación.

Comportamiento topológico frente al ruído.

Con 1 iteración

Imagen original Imagen transformada Imagen obtenida

22 %

5. Conclusiones e investigación.

Comportamiento topológico frente al ruído.

Con 3 iteraciones

Imagen original Imagen transformada Imagen obtenida

33 %

A más iteraciones, menos se conserva la topología

5. Conclusiones e investigación. (Resumen)

• Para imágenes 8x8 sólo es posible aplicar 3 iteraciones.

• Comprimiendo una imagen, la topología se mantiene hasta la iteración 2.

• Para imágenes con ruido y sin pérdida de información, la topología se mantiene hasta la iteración 3.

• Para imágenes con ruido y con pérdida de información, la topología se conserva sólo con 1 iteración.

6. Bibliografía y documentación.

Gonzalez, R.C. y Woods, R.E. Procesamiento de Imágenes Digitales. Addison-Wesley, 1992.

http://www.iro.umontreal.ca/~pigeon/science/ondelettes/Haar/Haar.html

http://amath.colorado.edu/courses/4720/2000Spr/Labs/Haar/haar.html

http://ikpe1101.ikp.kfa-juelich.de/briefbook_data_analysis/node113.html

http://www.owlnet.rice.edu/~elec539/Projects99/NSJS/project1/

http://perso.wanadoo.fr/polyvalens/clemens/transforms/