Tuesday, April 19, 2016

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

No comments: