miércoles, 29 de mayo de 2013

Ultima entrega - Transformada "Haar"

Que tal para esta ultima entrega se nos encargo hacer un python que comprimiera una imagen y se nos dio como base la transformada de Wavelet.

El proceso a seguir para el desarrollo de este programa es el siguiente:

Diagrama de flujo.


Como se muestra en la imagen anterior, el algoritmo actúa en sobre un imagen(no importa el tipo) y mediante una serie de procesos obtiene la imagen comprimida.

Introducción

La comprensión consiste en sustituir una cadena de datos por otra mas corta cuando se guarda un archivo. Ciertos metodos son reversibles("lossless data compression"), porque permite la reconstrucción exacte de la original. Pero con otros("lossy data compression""), la información original solo se recupera aproximadamente, ya que se descarta una parte de los datos.

Pero ambos metodos intentan cumplir objetivos:

  • El código de compresión debe ser lo mas compacto posible que el original.
  • Eliminar toda o casi toda la redundancia existente en la imagen original. 

Foto tomada de:
http://tesis.bnct.ipn.mx/dspace/bitstream/123456789/5745/1/ALGORITMODECOMPR.pdf

Comparación entre los diferentes tipos de compresión.



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.

Distribución de pixeles


Linealidad 
  • Se basa en sumas, restas y divisiones
  • Supongamos 2 números a y b vecinos.
  • Transformada que sustituye a y b por su media(m) y su diferencia(d):

m = (a + b) / 2 
d = b - a


Idea

Si a y b estan cercanos almacenar su diferencia es mas eficiente. 

Algoritmo






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








Codificación 


Pruebas

*Todas la imagenes que se toman deben tener un ancho de potencia de 2, esto por la dimension de la matriz que usa los wavelet(por lo general es de 8*8).


Imagen de 128 * 128 pixeles





Detalles de los umbrales y su calidad reflejada en las imagenes.

Obviamente el resultado se ve aceptable aunque no es lo mejor; la calidad depende mucho del valor de umbral mientras mas pequeño sea la calidad de la imagen de conserva un poco mas pero su compresión no es del todo buena.

En la siguiente imagen su toma la imagen original, un imagen con umbral de 20 y la ultima con umbral de 300.

Observen como cambia drásticamente la calidad dependiendo de la memoria que ocupa en disco.




Imagen de 1024 * 1024 pixeles


Imagen original



Imagen con un umbral de 100



Propiedades de las imagenes



Referencias

http://compresiondeimagenes.wikispaces.com/9.+LA+APLICACI%C3%93N+DE+LA+TRANSFORMADA+DE+HAAR+WAVELET+A+IM%C3%81GENES+DE+TAMA%C3%91O+COMPLETO

http://www.redusers.com/noticias/wp-content/uploads/2011/06/paper4.pdf

presentacion