lunes, 27 de mayo de 2013

Métodos de codificación. Compresión de imágenes.

Que tal gente, esta publicación corresponde a la ultima tarea de la clase de métodos de codificación, en esta ocasión se nos encargo realizar una implementación de un programa que fuera capaz de comprimir imágenes, en mi caso como ya había trabajado algo parecido en el laboratorio de clase de visión computacional, opte por reciclar parte del código y trabajar con la compresión mediante la transformada de onduleta (Wavelet).

Compresión y transmisión de imágenes.

Actualmente los dispositivos de captura de imágenes generan cada vez imágenes con mejor calidad, lo cual permite un mejor procesamiento de las mismas y obtener resultados mas exactos, el inconveniente llega a la hora la hora de almacenamiento o transmisión de dichas imágenes, ya que a imágenes de mayor calidad, imágenes de mayor peso. Debido a esto, es necesario emplear mecanismos de compresión ya sea para almacenar o transmitir este tipo de información.

Existen dos tipos de compresión de imágenes, con perdida o sin perdida, en la compresión con perdida la imagen resultante se ve afectada en cuanto a la calidad de detalle en relación a la original, aspecto que es directamente proporcional al porcentaje de compresión de la imagen, entre mas compresión, mayor sera la perdida de calidad de imagen.

La implementación o no de la compresión dependerá del fin del proceso, en ocasiones se debe priorizar la velocidad de transmisión, un ejemplo donde se puede ver esto fácilmente es cuando vas a google y quieres ver una imagen en su tamaño completo, inicialmente se ve algo pixeleada, pero no pasan mas de unos segundo cuando lo imagen ya se observa perfectamente bien, esto es porque los servidores envían la versión compresa de la imagen, y posteriormente mandan el detalle, visualmente parece que carga rápido, pero realmente hace la carga en dos pasos para evitar verse lento con imágenes grandes.

Teoria, Transformada Wavelet.

La transformada Wavelet básicamente es una función que es valida para ciertas condiciones especificas, es una variante de las transformadas de fourier, pero dado su modelo matemático este concepto está siendo llevado a muchos campos reinventando la forma de aplicación en relación a las transformadas de fourier, ahora se estudiara como se aplica esta transformada en la compresión de imágenes.

Como funciona?
Supongamos que tenemos una matriz de 8 x 8 como la siguiente:
En este caso se estudia la transformada "Haar" que es considerada la transformada wavelet mas sencilla.

El proceso se divide en dos pasos, la matriz se debe procesar por renglones generando una nueva matriz, misma que se procesara de la misma manera, pero ahora por columnas, el resultado final, sera la matriz de la transformada Wavelet.

Para cada renglón, lo que se hace es:
Se agrupan por pares de valores, para cada par se busca el promedio de ambos, y se almacena, entonces, si tenemos 8 valores, la siguiente fila tendrá esos 4 promedios al inicio, para completar el largo de la fila, lo que se hace es obtener la diferencia del promedio respecto al primer valor que genero dicho promedio, con esos 4 valores se complementa la fila, la fila resultante se vuelve a procesar de la misma manera. 

Las iteraciones de procesamiento para un renglón están regidas por la potencia de dos a la que es igual el numero de elementos de la fila, para el primer renglón de la imagen anterior, el resultado del proceso seria el siguiente:

Entonces, una vez obtenida la matiz resultante por renglón  se repite el mismo proceso pero ahora procesando por columnas, lo cual nos generara una matriz con los valores comunes empaquetados, ademas de generar los valores de detalle, mismos que son procesados para lograr la compresión.

Compresión.

Existen varias formas de lograr la compresión  el caso implementado es de los mas sencillos, ya que consiste en manipular los valores de la transformada obtenidos para que al momento de aplicar la transformada inversa, obtener una matriz con menor peso en bits que al final se vera reflejado en la imagen final.

Al aplicar la transformada sobre la matriz, se generan un conjunto de matrices, donde una de ellas contiene el "detalle" de la imagen, esta matriz es la que se va a modificar eliminando el detalle de menos peso, de la forma que se describe a continuación.

La compresión es bastante sencilla, lo que se hace es evaluar la matriz de detalle respecto a un valor umbral, lo que se trata de hacer, es quitar detalle de la imagen cuyo peso especifico este entre el rango del umbral, los valores se igualan a cero, al hacer esto la imagen resultante perderá peso en k's porque el peso lo generan todos los valores distintos de cero contenidos en la imagen, es cuestión de jugar con el valor umbral y ver que tanto se presta la imagen para hacerla mas ligera, si perder demasiado detalle, por lógica, entre mayor sea el umbral, mayor sera la compresión obtenida, pero también sera mayor el detalle perdido.

Como lo mencionaba antes, una vez que el detalle fue umbralizado, se aplica la transformada inversa, y el valor resultante sera la matriz de nuestra imagen resultante.

Código.

A continuación el código de la implementación.

Y ahora el script de gnuplot para las gráficas.

Pruebas.
Para las pruebas se hizo el ejercicio de probar el script múltiples veces (58) para cada imagen modificando el parámetro umbral, para así poder estudiar hasta que grado se alcanzaba compresion ademas de los tiempos de ejecución del sistema.

Prueba 1.
Tamaño: 128 x 128 px.
La imagen original es la siguiente:
La siguiente gráfica muestra la comparativa del porcentaje de compresión alcanzado en relación al umbral de compresión.

Como se puede observar en la gráfica, se logra una compresión bastante alta, misma que se alcanza con un umbral de 140 aprox. y se mantiene constante para valores mayores.


En la siguiente imagen gif si se presta atención se puede observar como la imagen resultante pierde detalle conforme el parámetro umbral aumenta.

Finalmente se muestra la captura de los pesos desde las propiedades de cada imagen, cabe mencionar un detalle detectado hasta apenas ahora, los valores que se muestran arriba, son porcentajes en relación a la imagen original, y en la evidencia de abajo se esta observando la imagen en escala de grises y la imagen resultante con umbral 300, el filtro de escala de grises automáticamente disminuye el tamaño de la imagen, por lo que es probable que no coincidan los valores de la gráfica con lo que se pudiesen calcular de la siguiente imagen:


Tiempo de ejecución del ciclo completo(58 imágenes) : 5.1019411087 segundos.

Prueba 2.
Tamaño: 256 x 256 px.
La imagen original es la siguiente:

La siguiente imagen muestra la comparacion porcentaje/umbral obtenido en las pruebas.
Se puede observar que se alcanza un máximo de compresión de 83% aprox, y se alcanza a partir del umbral 125 aprox. y se mantiene.


El siguiente gif muestra la perdida de calidad de la imagen conforme aumenta el valor umbral.
Se muestra en menor cantidad la perdida de detalle, esto debido a que el tamaño de la imagen aumento.


Finalmente se muestra los pesos y la evidencia de reducción desde las propiedades de cada imagen.

Tiempo de ejecución del ciclo completo(58 imágenes) : 18.5702998638 segundos.

Prueba 3.
Tamaño de la imagen: 512 x 512 px.
La imagen original es la siguiente:

La siguiente gráfica muestra la comparacion compresión/umbral de los valores resultantes.

Como se puede observar, para umbrales muy bajos en esta imagen la compresión es pésima  ya que incluso la imagen gana peso, en lugar de perder, esto se debe la naturaleza de la imagen y el tamaño, como se puede ver, en la imagen predominan los colores grises, al convertir a grises, el programa se confunde pensando que la imagen cuenta con aun mas detalle, por lo que se genera esta situación.

De todas maneras, a partir de un umbral 30-35 aprox, se empieza a normalizar el funcionamiento y a obtener ganancia, aunque el máximo valor obtenido es mucho menor en relación a las pruebas anteriores, con un 37% de compresión aprox. Aspecto que termina siendo proporcional, ya que la imagen es mucho mayor a la anterior, aunque se tenga menos porcentaje, son mas bits los que se logran perder en la imagen.


El siguiente gif muestra el deterioro de la imagen respecto a umbral.


Finalmente la evidencia desde las propiedades de imagen.

Tiempo de ejecución del ciclo completo(58 imágenes) : 71.8033628464 segundos.

Prueba 4.
Tamaño: 1024 x 1024 px.


Tiempo de ejecución del ciclo completo(58 imágenes) : 414.194577932 segundos.

Tiempos.

La siguiente imagen muestra el comportamiento de los tiempos de ejecución respecto a los tamaños de imagen:

Conclusiones.
En base a lo anterior se pueden deducir un par de cosas:
  • El tiempo de procesamiento aumenta considerablemente conforme aumenta el tamaño de la imagen.
  • Para imágenes grandes, es mejor manejar umbrales mayores, se logran perder mas bytes y la perdida de detalle tiene menos impacto.
  • Para imágenes pequeñas, en mejor manejar umbrales bajos, ya que para umbrales grandes, se pierde mucho detalle al grado de perder la estructura básica de la figura.

Bien, por mi parte es todo.

Saludos!

Referencias.
http://gtwavelet.bme.gatech.edu/wp/kidsA.pdf
http://www-scf.usc.edu/~hbalan/wavelets.pdf
http://www.iberchip.net/VIII/docs/posters/p13.pdf
http://www.pybytes.com/pywavelets/regression/dwt-idwt.html

1 comentario:

  1. 8 por el reporte; por el código van 6 ya que la originalidad del método el poca pero usas matemáticas no triviales.

    ResponderEliminar