Programación lúdica: Compresión de una imagen de alto contraste

Las imágenes, los videos, son parte fundamental del cómputo actual. Muchísimos sitios web usan videos e imágenes para ilustrar los temas de interés. Es claro que parte de esta tendencia se debe a que el ancho de banda de la red ha mejorado considerablemente y enviar información de video -entre otras- ya no resulta tan lento. Sin embargo, siempre se agradece cuando por ejemplo, en un sitio web, éste está hecho de manera tal que carga rápidamente y que no saturan de imágenes de mucha calidad (que ocupan desde luego mucho más espacio).

Así pues, a pesar de los avances en comunicación y de que hoy por ejemplo, se prometen 200 Mbits/seg. dados por ciertos proveedores, es claro que este avance se debe precisamente a que hoy recibimos/enviamos mucha información que hace algunos años y esto ha hecho crecer las necesidades de poder guardar todos estos videos e imágenes que nos interesan. Por ello, en ocasiones es importante comprimir información para que usemos menos disco duro pues la experiencia general indica que no importa cuanto almacenamiento tengas, tus datos terminarán llenándolo todo.

De hecho, el formato JPG (o JPEG) y TIFF son formatos con compresión de datos. Los archivos mp3 igualmente comprimen información. Los archivos de video usan diferentes esquemas de compresión también. Por ello, el reto de la programación lúdica en esta ocasión es el de tomar una imagen en alto contraste (en un momento explico cómo se hace eso), y lograr la mayor compresión posible. Es decir, si el archivo original es de -digamos- 300Kb, el ganador del reto será quien pueda reducir, comprimiendo la imagen, en mayor porcentaje. El programa ganador debe poder comprimir y descomprimir la imagen, regresándola a la original (en alto contraste). Es decir no se vale hacer "lossy compression" (o compresión con pérdida, que se explica más abajo).

El alto contraste en una imagen es que sólo tenga dos colores, blanco y negro. Para convertir una imagen a este formato, lo que hay que hacer es tomar cualquier imagen en color, pasarla a tonos de gris. Este funciona así: se lee cada pixel y se hace la siguiente operación: Gris = (Rojo + Verde + Azul) / 3. La división debe ser entera. En el pixel leído se coloca en cada componente de color (Rojo, Verde, Azul) el mismo valor de gris, así, el pixel ahora tendrá como valores (Gris, Gris, Gris). Esto significa que solamente puede haber 256 tonos de gris, desde (0, 0, 0) hasta (255, 255, 255). (Ojo, usamos el modelo RGB, Red, Green, Blue).

Una vez que se ha transformado a tonos de gris la imagen, para pasarla a alto contraste, lo que se hace es simple: se toma cada pixel de la imagen en tonos de gris: Si cualquiera de los componentes de cada pixel es arriba de 127, pongo un blanco (255) y si es menor de ese valor pues pongo un negro (0). Así, si el pixel de entrada es (34, 34, 34), el de salida será (0, 0, 0). Si el pixel de entrada es (192, 192, 192) el de salida será (255, 255, 255).

Teniendo la imagen en alto contraste, el siguiente paso es comprimirla. ¿Cómo puedo hacer eso? Hay muchas técnicas. Mencionaré una pero ojo, no es necesariamente la que hay que programar, puede ser cualquier técnica que comprima imágenes y quizás la que el lector que le entre al reto, si es la mejor, se llevará el premio. He aquí un simple ejemplo: Tómese una imagen y empiécese a leer cada pixel de la imagen en alto contraste. Si la imagen empieza con esta secuencia: 255, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 0, 0, 255, 255, 255, 0, ... entonces nosotros crearemos un archivo que contenga el valor del pixel y un contador que mide la cantidad de veces que ese valor se repite. Así, pondremos 255|1, 0|5, 255|5, 0|2, 255|3, 0|1... este tipo de compresión se llama RLE (Rule Length Encoded) y funciona mejor en imágenes donde hay muchas zonas donde se repiten los mismos colores (no necesariamente sirve para hacerlo en alto contraste). Obviamente, si tenemos una imagen en donde cada pixel cambia de valor, entonces la "compresión" RLE nos creará un archivo del doble de tamaño. Este es el código ejemplo en Delphi para comprimir un archivo en general (no necesariamente de una imagen) usando RLE:

La rutina que descomprime es ésta:

Repito: la compresión RLE es una posibilidad, pero se puede usar cualquier otro método de compresión.

Hay sin embargo, otros esquemas de compresión que pierden información, y se denominan "lossy compression". Esto significa que al comprimir se pierde información de la imagen original y al descomprimirla, tenemos una imagen ligeramente alterada. Quizás el ojo humano no distinga las diferencias pero las hay. En este reto no se vale hacer compresión lossy, es decir, la imagen comprimida debe descomprimirse en la imagen original de manera idéntica.

El programa debe poder cargar cualquier imagen JPG en color y pasarla a alto contraste, guardarla (para saber de qué tamaño queda) y procesarla, para poder comparar contra la imagen original y hallar el promedio de compresión.

El ganador se llevará una taza de la Morsa. Si vive fuera de la ciudad de México el premio será un USB de al menos 8 GBytes. El costo de mandar una taza fuera de la CDMX que es donde vivo es unas 10 veces el costo de la taza, lo cual es ridículamente caro. Si alguien quiere la taza de todas maneras, lo que podemos hacer es que le mande el logotipo de la misma y se la haga en OfficeMax y yo pago el costo de ello (que es menos de 100 pesos). Quiero aclarar que más allá de algunos apoyos, no tengo patrocinios para este tipo de concursos. Si logro que alguna empresa me ayude con el envío de la taza al ganador, pues con gusto se la hago llegar. Así pues, si me van a criticar por esto, mejor hagan lo inverso, apoyen la iniciativa de la Programación Lúdica, por favor.

El ganador será quien pueda comprimir en mayor porcentaje la imagen de Ilse (ver más arriba). Si hay dos o más programadores que lograron el mismo porcentaje y son los mejores, es decir, si hay empate, el primero que haya mandado la solución será el ganador. El código debe estar razonablemente comentado para ser leíble. Se agradecerá también una breve explicación del método usado.

Les recuerdo que estos concursos se hacen de buena fe. La idea es promover que la gente programe y que genere código. Cabe decir que el código que escriban pasa a código abierto como parte de las condiciones para concursar. La cuestión es que todos aprendamos algo en este c camino. El concurso tendrá una vigencias de unos 20 días, máximo un mes, para poder mandar los resultados.

¿Dudas? ¿Comentarios? A mi correo: morsa@la-morsa.com.

Gracias

Introducción a los algoritmos de compresión de imágenes

En el curso que doy de Proceso Digital de Imágenes (PDI), es siempre importante hablar de un tema que muchas veces es difícil de abordar. Se trata del de la compresión de archivos, en particular, del de la compresión de imágenes, el cual en alguna medida permite que las mismas ocupen menos espacio en los medios de almacenamiento y mejor aún, que la transmisión de las imágenes y fotos sea más rápido. Por ejemplo, si puede reducir una imagen al 10% de su tamaño en bytes, pues puedo, en principio, enviar diez imágenes por el precio de una, para decirlo de manera coloquial. Así, la compresión ayuda muchas veces a ser más eficientes en lo que se refiere al uso del ancho de banda por Internet. Por otra parte, la compresión permite usar menos espacio de almacenamiento.

Hay básicamente dos esquemas usados en este tema:

• Compresión sin pérdida de información (losseless)
• Compresión con pérdida de información (lossy)

En la primera, la compresión y descompresión del archivo (para convertir la imagen comprimida y podamos verla), no pierde información del archivo original. Vamos, al descomprimir la imagen es estrictamente igual a la original. La segunda compresión, en cambio, pierde información y el efecto de comprimir quizás no lo note el ojo humano al descomprimir y mostrar la imagen, pero si vemos a detalle veremos que habremos perdido información de la imagen original.

Cabe decir que a cambio de ahorrar bytes en el archivo original de almacenamiento, la versión comprimida debe descomprimirse y eso finalmente lleva tiempo. En cómputo no existe ningún procedimiento ganar-ganar. Si ganamos en espacio perdemos en tiempo y viceversa. Esto es un buen ejemplo de ello.

Los esquemas de compresión de imágenes son variados y los más usados son JPG o TIFF. Hace unos años, más de 20, el formato PCX, del cual hablaré en otro artículo próximamente, era uno de los más usados y simples, pero cayó en desuso ante sofisticados esquemas de compresión como los que plantean TIFF o JPG.

Pensando en cómo ejemplificar la compresión de imágenes, como una primera aproximación al problema, se me ocurrió que podía reducir a una tercera parte cualquier imagen que estuviese en tonos de grises. La razón de ello es simple: en 24 bits de color tenemos 8 bits para el rojo, 8 para el verde y otros 8 para el azul. Así, tenemos más de 16 millones de posibles colores con combinación de bytes R,G,B, que es el modelo conocido precisamente como RGB. Pero en tonos de gris tenemos solamente 256 tonos posibles. Cada tripleta R,G,B contiene R=G=B, es decir, las componentes de color en RGB son idénticas entre sí. Por ello, tenemos el tono de gris más oscuro (el negro), como (0,0,0), un poco menos negro será (1,1,1), menos negro aún será (2,2,2) y así sucesivamente. El blanco será (255,255,255).

Si esto es así, una imagen en tonos de gris puede reducirse a la tercera parte de su tamaño original leyendo una sola componente (el R, el G o el B de cada pixel de la imagen) y escribiendo en un archivo de bytes esa componente de cada pixel en la imagen. La idea es muy simple de programar y el algoritmo es éste:

(dar click en la imagen para verla más grande)

Cabe decir que cuando tengo la imagen que voy a procesar, primero la paso a tonos de gris tomando las componentes R, G y B, sumándolas y dividiendo de manera entera entre 3, es decir:

Gris := (R + G + B) div 3;

Así me aseguro que la imagen es de tonos de gris. De hecho, al convertir de color a tonos de gris ya perdemos información de color de la imagen, pero en este caso no es el asunto que discutimos.

Ahora bien, ¿cómo podríamos mostrar la compresión lossy, que es donde sí se pierde información al recuperar la imagen comprimida? Una idea sencilla resultó ésta: Tomemos una imagen en color y entonces revisemos las componentes de color (R,G,B). Tomemos el Rojo, la R y listo, digamos que ése es el tono de gris. Por lo tanto la imagen final en cada pixel tendrá el componente (R,R,R) en donde había antes un (R,G,B). ¿Qué tanto podría cambiar la imagen original en blanco y negro usando solamente la componente R de cada pixel?

He aqui dos imágenes. La de la derecha es la imagen en tonos de gris original. La de la izquierda es utilizando solamente la componente R(ed) para formar el tono de gris.

Tonos de gris vs Lossy (usando la coordenada R)

La diferencia visual quizás no es muy notable, pero de alguna manera, si nos fijamos con cuidado, veremos que la imagen "lossy" es un poco más oscura. Si en lugar de usar la componente R usáramos la B, encontraríamos un resultado "lossy" más obvio:

Tonos de gris vs Lossy (usando la coordenada B)

De hecho, se me ha ocurrido hacer un experimento más: Tomemos la imagen original en tonos de gris y saquemos los tres componentes de color, R, G y B, tomando uno de ellos al azar para formar el pixel correspondiente como (R,R,R), (G,G,G) o (B,B,B). Tal vez así, al elegir consistentemente el R, el G o el B de forma que se distribuyan esos tonos de gris formados con una sola componente, el resultado final podría ser mejor. Hice la prueba, pero me llevé una sorpresa inesperada:

Tonos de gris vs Lossy al azar (entre coordenadas R,G y B)

En resumen, usar una sola componente parece que no es tan descabellado si es que usamos la componente R o la G. Con la componente B la descompresión si muestra que se ha perdido mucha información de la imagen original. Probablemente la coordenada R sea la mejor opción en este caso.

El esquema mostrado reduce las imágenes a un 33% del tamaño original, lo cual quizás no puede considerarse malo, peor por ejemplo, esta misma imagen en JPG se reduce dos veces lo que podemos lograr con esta idea.

Aún así, no hay ninguna mejora con respecto al tamaño de la imagen comprimida. Digamos que es independiente de la componente elegida aunque para fines ilustrativos, usar el tono de gris calculado antes de procesar la imagen nos da una imagen resultante en donde no se pierde información de la imagen original.

Quien quiera mi programa de demostración, pídamelo a morsa@la-morsa.com y a vuelta de correo lo recibirá de manera gratuita.