Habi Hablóg

Compresión noir

Habi -

27/01/2013 15:47:12 -

Tecnoesoterismo

Supongamos que queremos reducir el tamaño de varias imágenes. Es un problema ampliamente tratado, así que vamos a particularizar:

Esas imágenes tendrían a lo sumo 4 colores y transparencia. Podemos comprimir sobre los datos tal cual, o separar en 4 planos de transparencia y color correspondiente.
El tamaño de las mismas sería "pequeño", 320x200 a lo sumo. Podría no compensar usar ciertas técnicas estándar.
Queremos un sistema simple y relativamente rápido de descompresión en ensamblador y para un Z80. Eso elimina cosas como compresión aritmética.
Tenemos restricciones de memoria, lo que limita el uso de métodos de diccionario.

Por todo ello, haremos pruebas combinadas con diferentes formas de compresión y empaquetado (Run-Length, Huffman (siempre canónico), LZ77, Deflate, diccionario rotatorio) y ciertas transformaciones (Haar, tiles, subdivisión, algunos predictores). Dejamos fuera LZ78, LZW, y diccionarios varios cuando su tamaño se dispare.

Hagamos otra hipótesis:

Las imágenes tendrán estética tipo comic, sólo tendrán blanco y negro (y muy ocasionalmente algo de gris o rojo). Además, cualquier fondo parte de un lienzo en blanco.

Por ello es que nos compensa tratar los planos por separado, y comprimir cada uno con una técnica especializada para imágenes monocromas.

Así pues, podemos empezar a hacer pruebas para un fondo, es decir, imágenes transparente + negro. Además, eso nos da una cota superior: si el archivo comprimido ocupa Ancho*Alto/8 o más es obvio que hemos fracasado, pues es el tamaño que ocuparía empaquetando cada pixel en un bit (equivalente al caso trivial de Huffman con 2 valores, óptimo por tanto trabajando con bits completos).

Tras todas las pruebas mis conclusiones son:

Tenemos pocos datos, así que métodos como Deflate, LZ77 o LZW no son particularmente buenos (y más si vuelcan datos de partida como el primero de ellos). Cuando los valores están muy concentrados los mejor es usar Huffman a secas. Corolario: comprimir o transformar con algo que genere valores concentrados.
No merece la pena usar predicción, son sólo dos valores. Tampoco merece la pena crear valores intermedios para compensar, pues aumenta la cantidad de datos distintos. Corolario: no merece la pena usar transformaciones tampoco.
Ya podían haberle puesto los ingenieros de Zilog un multiplicador / divisor al Z80, o al menos instrucciones de rotación múltiple. Y el poder efectuar operaciones aritmético-lógicas de 8 bits sobre otro registro que no fuese el acumulador. Pero bueno, tampoco es que los del ordenador en cuestión se hayan lucido. Corolario: nos acordaremos de su familia mientras escribimos el código descompresor.

Así que mis recomendaciones son:

Tipo fax (RLE y Huffman alternos).

Una forma muy usada es la compresión de los faxes: básicamente consisten en contar cuántos unos o ceros hay (run-length) y comprimir esas longitudes con códigos de Huffman (modificados). No es necesario indicar cuál es el valor que se repite pues al ser sólo dos se van alternando. Se usan árboles de Huffman distintos para las longitudes de cada valor.

En mi caso usaré árboles creados aposta para la imagen en vez de unos genéricos y no usaré códigos modificados pues no hay longitudes grandes al ser una imagen pequeña.

Debo decir que no funciona nada mal el algoritmo, es el segundo mejor de todas mis pruebas; como ejemplo:

Se comprime en 2987 bytes + diccionario aparte (las longitudes en bits de los códigos Huffman canónicos, para reconstruir los árboles / tablas). Los diccionarios van aparte por si se quieren unificar códigos en toda la aplicación, compartir, o lo que sea. Pongamos unos 40-60 bytes extras.

En cualquier caso, estamos hablando de unas 3K en una imagen cuyo límite estaba en 8K. Es decir, un 37,5% del original, que no está nada mal. Este algoritmo funciona de vicio en cualquier tipo de imágenes.

Subdivisión recursiva + Huffman.

Sin embargo, dadas mis restricciones de espacio necesito más compresión que el método anterior. Y dada la estética de mis imágenes haré otra hipótesis:

Las imágenes serán claroscuros, es decir, con masas sólidas. Pero por joder, serán más pequeñas ya que irán en viñetas tipo cómic.

Cogemos una imagen, le ajustamos la exposición y gamma y empezamos a comprimir:

Tenemos el límite en 128x96/8=1546 bytes. El método anterior lo deja en 499 + diccionarios. Pongamos 550 bytes en total.

Empezamos extendiendo las dimensiones para que la imagen entre en un cuadrado cuyo lado sea potencia de 2. Ahora construimos un árbol cuaternario donde las hojas sean los cuadrados de color a dibujar. Es decir, sólo codificamos el color, y si un nodo no es hoja entonces no se dibuja (es de soporte). Por tanto, cada nodo se puede codificar con 4 bits indicando si tiene o no hijos en cualquiera de las 4 direcciones.

Se generan 1700 nodos (1025 hojas), empaquetando tal cual son 850 bytes. Pero no vamos a empaquetar sino aplicar huffman.

Nos quedan 534 bytes, todo incluido. Pero se puede hacer mejor: reordenemos el árbol, que se emita en orden de recorrido por anchura en vez de profundidad; de esta forma todas las hojas del último nivel (a 0) estarán juntas, y por tanto se pueden quitar asumiendo que a partir de que terminen los datos siempre se da ese valor (quedando 1065 de 1700 nodos).

Y así se queda en 433 bytes, incluyendo diccionario, flags y dimensiones (sólo necesita el Log₂ del lado del cuadrado). En total un 28,19% del total, nada mal para una imagen no especialmente buena, y dejando abierta la posibilidad de comprimirse aún más (hay muchas rachas de 0's y 15's antes de pasar por Huffman).

¿Me dará para lo que quiero? No lo sé, pero ha sido entretenido.

SyX - 27/01/2013 20:50:29

¡Estos matemáticos son unos abusones! :P Pobre ZX xDDD

Habi - 27/01/2013 21:08:41

Creo que en el texto hay pruebas suficientes como para pensar que no se trata de una máquina de Sinclair. Si bien todo esto es aplicable, por supuesto. ;)

Post cerrado

Acerca de

Red antisocial

Últimos posts

Últimos comentarios

Calendario

Categorías

Cenas de Abj

Frase célebre

Compresión noir