1 Procesamiento de Imágenes digitalesTransformada de Haar 15/04/2017 Analizador de la transformada de Haar desde un punto de vista 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

2 Í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.

3 Usaremos para nuestro estudio imágenes:1. Introducción. Usaremos para nuestro estudio imágenes: Binarias. De dimensión 8x8. El analizador no admite imágenes en escala de grises. • Nuestra investigación se centra en el análisis de transformadas de líneas rectas.

4 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.

5 Usar dicho analizador en: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.

6 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.

7 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 =

8 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.

9 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.

10 3. La transformada de Haar.15/04/2017 3. La transformada de Haar. Algoritmo.  Paso 1:  Calcular las medias para cada pareja:

11 3. La transformada de Haar.Algoritmo.  Paso 1: Vector original: Vector que llevamos calculado:  Calcular las diferencias:

12 3. La transformada de Haar.Algoritmo.  Paso 2: Media + Diferencias Permanece igual!!

13 3. La transformada de Haar.Algoritmo.  Paso 3: Media + Diferencia Permanece igual!!

14 3. La transformada de Haar. Todas estas transformaciones sucesivas aplicadas a un vector se pueden ver de forma matricial:

15 3. La transformada de Haar. Todas estas transformaciones sucesivas aplicadas a un vector se pueden ver de forma matricial:

16 3. La transformada de Haar. Todas estas transformaciones sucesivas aplicadas a un vector se pueden ver de forma matricial:

17 3. La transformada de Haar.Matriz de Haar

18 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).

19 3. La transformada de Haar.Ejemplo:

20 3. La transformada de Haar. Ejemplo:  Aplicar el algoritmo anterior por filas a la matriz M: M H1

21 3. La transformada de Haar. Ejemplo:  Aplicar el algoritmo anterior por columnas a la matriz H1: H1 N

22 3. La transformada de Haar.Ejemplo:  De esta forma obtenemos la nueva matriz N que representa a la imagen:

23 4. Propiedades de la transformada de Haar.15/04/2017 4. Propiedades de la transformada de Haar. 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. Sobre todo a la compresión de señales estacionarias o “spiky” • 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.

24 5. Conclusiones e investigación.Número de iteraciones del algoritmo. Compresión de imágenes.  Comportamiento topológico frente al ruído.

25 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=2 n=3 n=4

26 5. Conclusiones e investigación.Número de iteraciones:  Ejemplo para n=4 iteraciones. Imagen original Imagen codificada Imagen obtenida No se recupera la imagen original!!

27 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.

28 5. Conclusiones e investigación.Compresión: Elegir una d tal que los valores de la matriz N que sean menores que dicha d toman automáticamente el valor 0. Ejemplo:

29 5. Conclusiones e investigación. Compresión - ejemplo: Elegimos d = 0

30 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!!

31 5. Conclusiones e investigación.Compresión - ejemplo:  Si aumentamos el número de iteraciones: n=2 Imagen original 11 % n=4 13 % No conserva la topología!!!

32 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.  Ejemplo con pérdida de información: Ruido

33 5. Conclusiones e investigación. Comportamiento topológico frente al ruído. 22 % Con 1 iteración Imagen original Imagen transformada Imagen obtenida

34 5. Conclusiones e investigación. Comportamiento topológico frente al ruído. 33 % Con 3 iteraciones Imagen original Imagen obtenida Imagen transformada A más iteraciones, menos se conserva la topología

35 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.

36 6. Bibliografía y documentación.Gonzalez, R.C. y Woods, R.E. Procesamiento de Imágenes Digitales. Addison-Wesley, 1992.