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
Í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.
• 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.
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:
 Calcular las medias para cada pareja:
4
6
10
4
....
3. La transformada de Haar.
 Algoritmo.
 Paso 1:
Vector original:
Vector que llevamos calculado:
 Calcular las diferencias:
4
6 10
4 1
2 3
1 ]
3. La transformada de Haar.
 Algoritmo.
 Paso 2:
Media +
Diferencias
[5
7 1
3
Permanece igual!!
3. La transformada de Haar.
 Algoritmo.
 Paso 3:
Media +
Diferencia
[6  1
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.
• 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.
• 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.
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=2
n=3
n=4
5. Conclusiones e investigación.
Número de iteraciones:
 Ejemplo para n=4 iteraciones.
Imagen original
Imagen codificada
No se recupera la imagen
original!!
Imagen obtenida
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 d tal que los valores de la
matriz N que sean menores que dicha d
toman automáticamente el valor 0.
 Ejemplo:
5. Conclusiones e investigación.
 Compresión - ejemplo:
Elegimos d = 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:
Imagen original
11 %
n=2
n=4
13 %
No conserva la
topología!!!
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
5. Conclusiones e investigación.
 Comportamiento topológico frente al ruído.
22 %
Imagen original
Con 1 iteración
Imagen transformada
Imagen obtenida
5. Conclusiones e investigación.
 Comportamiento topológico frente al ruído.
33 %
Imagen original
Con 3 iteraciones
Imagen transformada
Imagen obtenida
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. AddisonWesley, 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/
Descargar

Transformada de Haar