[Índice Proyecto 3MF: Datos de Imagen LZW]
[Índice del Sitio Web]
[Índice del Foro]

Proyecto 3MF: Qué Hay en un GIF — Datos de Imagen LZW

Ahora veamos exactamente cómo logramos almacenar una imagen en un archivo GIF. El formato GIF es un formato de mapa de bits (rastro, o raster), lo que significa que este almacena datos de imagen al recordar el color de cada pixel en la imagen. Más específicamente, los archivos GIF recuerdan el índice del color en una tabla de color para cada pixel. Para hacerlo más claro, déjame mostrarte la imagen de muestra que usamos en la primera sección una vez más.

Tamaño Real

sample gif, actual size
(10x10)

Aumentado

sample gif, enlarged
(100x100)

Tabla de Color

ÍndiceColor
0Blanco
1Rojo
2Azul
3Negro

La Tabla de Color vino del bloque de Tabla Global de Color. Los colores están listados en el orden en que aparecen en el archivo. Al primer color se le da un índice de 0. Cuando enviamos los códigos, siempre comenzamos en la esquina superior izquierda de la imagen y seguimos nuestro camino hacia la derecha. Cuando llegamos al final de una línea, el código siguiente es el que comienza en la siguiente línea. (El decodificador "ajustará" la línea de la imagen basándose en las dimensiones de la imagen.) Podríamos decodificar nuestra imagen de muestra de la siguiente manera:

1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 2, 2, 2, ...

La lista anterior muestra la secuencia requerida para renderizar las primeras cuatro líneas de la imagen. Podríamos continuar con este método hasta haber especificado el color para cada pixel; sin embargo, esto puede resultar en un archivo bastante grande. Por suerte para nosotros, el formato GIF nos permite sacar ventaja de la repetición en nuestra salida y comprimir nuestros datos.



Compresión LZW

El método de compresión que podemos usar se llama compresión LZW. (De hecho, esta es una ligera variación del estándar LZW para utilizarse en imágenes GIF.) Para comenzar usando este método, necesitamos una tabla de color. Esta tabla de color nos permitirá usar códigos especiales para indicar una secuencia de colores en lugar de solo uno a la vez. Lo primero que hacemos es inicializar la tabla de color. Comenzamos agregando un código para cada uno de los colores en la tabla de color. Esta sería una tabla de color local si se proporciona una, o la tabla global de color. (Comenzaré todos los códigos con "#" para distinguirlos de los índices de color.)

CódigoColor(es)
#00
#11
#22
#33
#4Código Clear
#5Final de Código de Información

Agregué un código para cada uno de los colores en la tabla global de color de nuestra imagen de muestra. También agregué 2 códigos especiales de control. (Estos códigos especiales son usados solamente en la versión LZW de GIF, no en la compresión LZW estándar.) Nuestra tabla de código ahora se considera inicializada.

Déjame explicar ahora para qué son esos códigos. El primer nuevo código es el código clear (CC). Siempre que encuentras este código en los datos de imagen, es tu señal para reinicializar la tabla de códigos. (Explicaré por qué puedes necesitar hacer esto en un momento.) El segundo código nuevo es el código de final de información, o end of information (EOI). Cuando encuentras este código, eso significa que has alcanzado el final de la imagen. Aquí he colocado los códigos especiales justo después de los códigos de color, pero de hecho el valor de los códigos especiales depende del tamaño de código LZW mínimo del bloque de datos de imagen. Si el código LZW mínimo es el mismo que el tamaño de la tabla de color, entonces los códigos especiales siguen inmediatamente a los colores; sin embargo, es posible especificar un tamaño de código LZW mínimo más grande que puede dejar una ranura en los códigos en donde no hay colores asignados. Esto puede resumirse en la siguiente tabla:

Tamaño
Código LZW Mín
Códigos de
Color
Código
Clear
Código
EOI
2#0-#3#4#5
3#0-#7#8#9
4#0-#15#16#17
5#0-#31#32#33
6#0-#63#64#65
7#0-#127#128#129
8#0-#255#256#257

Antes de proceder, déjame definir dos términos adicionales: Primero el flujo de índice será la lista de índices del color para cada uno de los pixeles. Esta es la entrada que comprimiremos. El flujo de código será la lista de códigos que generamos como salida. El búfer de índice será la lista de índices de color que nos importa "estar mirando actualmente". El búfer de índice contendrá una lista de uno o más índices de color. Ahora podemos recorrer el algoritmo de compresión LZW. Primero, simplemente listaré los pasos. Después de eso te guiaré a través de los pasos con nuestro ejemplo específico.

Parece suficientemente simple, ¿verdad? Realmente no es tan malo. Recorramos nuestra imagen de muestra para mostrarte cómo funciona. (Los pasos que voy a describir se resumen en la siguiente tabla. Los números resaltados en verde están en el búfer de índice; los números en morado son el valor actual de K.) Ya hemos inicializado nuestra tabla de códigos. Comenzamos haciendo dos cosas: devolvemos nuestro código clear a la salida (#4) al flujo de código, y ponemos el primer índice de color del flujo de índices, 1, en nuestro búfer de índices [Paso 0].

Ahora entramos en el bucle principal del algoritmo. Ponemos el siguiente índice en el flujo de índices, 1, en K [Paso 1]. Luego vemos si hay un registro para el búfer de índices + K en el flujo de códigos. En este caso estamos buscando 1,1. Actualmente nuestra tabla de códigos solamente contiene colores individuales así que este valor no está ahí. Ahora agregaremos de hecho una nueva fila a nuestra tabla de códigos que contenga este valor. El siguiente código disponible es #6; haremos que el #6 sea 1,1. Nota que de hecho no hemos enviado este código al flujo de códigos, y en lugar de eso solamente enviamos el código para el o los valores en el búfer de índices. El búfer de índices solamente es 1 y el código para 1 es #1. Este es el código que devolvemos. Ahora reinicializamos el búfer de índices a solo el valor en K y K se vuelve nada. [Paso 2].

Continuamos al poner el siguiente índice en K. [Paso 3]. Ahora K es 1 y el búfer de índices es 1. Nuevamente vemos si hay un valor en nuestra tabla de códigos para el búfer + K (1,1), y esta vez lo hay. (De hecho acabamos de agregarlo.) Por lo tanto agregamos K al final del búfer de índices y limpiamos K. Ahora nuestro búfer de índices es 1,1. [Paso 4].

El siguiente índice en el flujo es otro 1. Este es nuestro nuevo K. [Paso 5]. Ahora el búfer de índices + K es 1,1,1 para el cual no tenemos un código en nuestra tabla de códigos. Como hicimos anteriormente, definimos un nuevo código y lo agregamos a la tabla de códigos. El siguiente código sería #7; así que #7 = 1,1,1. Ahora movemos el código solo para los valores en el búfer de índices (#6 = 1,1) al flujo de códigos y establecemos el búfer de índices a K. [Paso 6].

.
Paso Acción Flujo de Índices Nueva Fila de Tabla de Códigos Flujo de Código
0 Init 11111222221111...   #4
1 Leído 11111222221111...   #4
2 No Encontrado 11111222221111... #6 - 1, 1 #4 #1
3 Leído 11111222221111...   #4 #1
4 Encontrado 11111222221111...   #4 #1
5 Leído 11111222221111...   #4 #1
6 No Encontrado 11111222221111... #7 - 1, 1, 1 #4 #1 #6
7 Leído 11111222221111...   #4 #1 #6
8 Encontrado 11111222221111...   #4 #1 #6
9 Leído 11111222221111...   #4 #1 #6
10 No Encontrado 11111222221111... #8 - 1, 1, 2 #4 #1 #6 #6
11 Leído 11111222221111...   #4 #1 #6 #6
12 No Encontrado 11111222221111... #9 - 2, 2 #4 #1 #6 #6 #2
13 Leído 11111222221111...   #4 #1 #6 #6 #2
14 Encontrado 11111222221111...   #4 #1 #6 #6 #2
15 Leído 11111222221111...   #4 #1 #6 #6 #2
16 No Encontrado 11111222221111... #10 - 2, 2, 2 #4 #1 #6 #6 #2 #9
17 Leído 11111222221111...   #4 #1 #6 #6 #2 #9
18 Encontrado 11111222221111...   #4 #1 #6 #6 #2 #9
19 Leído 11111222221111...   #4 #1 #6 #6 #2 #9
20 No Encontrado 11111222221111... #11 - 2, 2, 1 #4 #1 #6 #6 #2 #9 #9
21 Leído 11111222221111...   #4 #1 #6 #6 #2 #9 #9
22 Encontrado 11111222221111...   #4 #1 #6 #6 #2 #9 #9
23 Leído 11111222221111...   #4 #1 #6 #6 #2 #9 #9
24 Encontrado 11111222221111...   #4 #1 #6 #6 #2 #9 #9
25 Leído 11111222221111...   #4 #1 #6 #6 #2 #9 #9
26 No Encontrado 11111222221111... #12 - 1, 1, 1, 1 #4 #1 #6 #6 #2 #9 #9 #7

He incluido unos cuantos pasos más para ayudarte a ver el patrón. Tú sigues avanzando hasta que te quedas sin índices en el flujo de índices. Cuando no hay nada nuevo que leer, simplemente escribes el código para cualesquiera valores que puedas tener en tu búfer de índice. Finalmente deberías enviar el código de final de información al flujo de códigos. En este ejemplo, ese código es #5. (Mira la tabla de códigos completa.)

Como puedes ver, hemos construido dinámicamente muchos códigos para nuestra tabla de códigos a medida que comprimimos los datos. Para archivos grandes, esto puede convertirse en un número grande de códigos. Resulta que el formato GIF especifica un código máximo de #4095 (resulta que este es el número más grande de 12 bits). Si deseas usar un nuevo código, entonces tienes que descartar todos tus códigos antiguos. Tú haces esto al enviar el código clear (que para nuestra muestra era el #4). Esto le dice al decodificador que estás reinicializando tu tabla de códigos y que este también debería hacerlo. Entonces comienzas a construir tus propios códigos nuevamente comenzando justo después del valor para tu código de fin de información (en nuestro ejemplo, comenzaríamos nuevamente en #6).

El flujo de datos final se vería así:

#4 #1 #6 #6 #2 #9 #9 #7 #8 #10 #2 #12 #1 #14 #15 #6 #0 #21 #0 #10 #7 #22 #23 #18 #26 #7 #10 #29 #13 #24 #12 #18 #16 #36 #12 #5

Estos son solo 36 códigos contra 100, que serían requeridos sin compresión.



Descompresión LZW

En algún punto probablemente necesitaremos convertir este flujo de códigos de vuelta a una imagen. Para hacer esto, solo necesitamos conocer los valores en el flujo y el tamaño de la tabla de color que fue utilizada. Eso es todo. ¿Recuerdas aquella gran tabla de códigos que generamos durante la compresión? De hecho, tenemos suficiente información en el flujo de código mismo para poder reconstruirlo.

Listaré nuevamente el algoritmo y luego te guiaré a través de un ejemplo. Permíteme definir unos cuantos términos que estaré usando. CODIGO será el código actual con el que estamos trabajando. CODIGO-1 será el código justo antes de CODIGO en el flujo de códigos. {CODIGO} será el valor para CODIGO en la tabla de códigos. Por ejemplo, usando la tabla que creamos durante la compresión, si CODIGO=#7 entonces {CODIGO}=1,1,1. Del mismo modo, {CODIGO-1} sería el valor en la tabla de códigos que estaba antes de CODIGO. Viendo el paso #26 desde la compresión, si CODIGO=#7, entonces {CODIGO-1} sería {#9}, no {#6}, el cual era 2,2.

  1. Inicializar la tabla de códigos.
  2. Hacer que CODIGO sea el primer código en el flujo de códigos.
  3. Devolver {CODIGO} al flujo de índices.
  4. <PUNTO DE BUCLE>
  5. Hacer que CODIGO sea el siguiente código en el flujo de códigos
  6. ¿Está CODIGO en la tabla de códigos?
  7. Sí:

    1. Devolver {CODIGO} al flujo de índices.
    2. Hace que K sea el primer índice en {CODIGO}.
    3. Agregar {CODIGO-1}+K a la tabla de códigos.
  8. No:
    1. Hacer que K sea el primer índice de {CODIGO-1}.
    2. Devolver {CODIGO-1}+K al flujo de índices.
    3. Agregar {CODIGO-1}+K a la tabla de códigos.
  9. Regresar al PUNTO DE BUCLE.

Comencemos leyendo a través del flujo de códigos que hemos creado para demostrar cómo convertirlo nuevamente a una lista de índices de color. El primer valor en el flujo de códigos debería ser un código clear. Esto significa que deberíamos inicializar nuestra tabla de códigos. Para hacer esto, debemos saber cuántos colores hay en nuestra tabla de color. (Esta información proviene del primer byte en el bloque de datos de imagen en el archivo. Más sobre esto más adelante.) Nuevamente configuraremos los códigos #0-#3 para que correspondan a cada uno de los 4 colores y agregaremos el código clear (#4) y un código de fin de información (#5).

El siguiente paso es leer el primer código de color. En la siguiente tabla verás los valores de CODIGO resaltados en morado, y los valores para CODIGO-1 resaltados en verde. Nuestro primer valor de CODIGO es #1. Entonces devolvemos {#1}, o simplemente 1, al flujo de índices [Paso 0].

Ahora entramos en el bucle principal del algoritmo. El siguiente código se asigna a CODIGO, el cual ahora tiene el valor #6. A continuación verificamos para ver si este valor está en nuestra tabla de códigos. En este momento, no lo está. Esto significa que debemos encontrar el primer índice en el valor de {CODIGO-1} y llamarle a este K. De esta forma, K = primer índice de {CODIGO-1} = primer índice de {#1} = 1. Ahora devolvemos {CODIGO-1} + K al flujo de índices y agregamos este valor a nuestra tabla de códigos. Eso significa que devolvemos 1,1, y le damos a este valor, un código de #6 [Paso 1].

Paso Acción Flujo de Códigos Nueva Fila de Tabla de Color Flujo de Índices
0 Init #4 #1 #6 #6 #2 #9 #9 #7 ...   1
1 No Encontrado #4 #1 #6 #6 #2 #9 #9 #7 ... #6 - 1, 1 1, 1, 1
2 Encontrado #4 #1 #6 #6 #2 #9 #9 #7 ... #7 - 1, 1, 1 1, 1, 1, 1, 1
3 Encontrado #4 #1 #6 #6 #2 #9 #9 #7 ... #8 - 1, 1, 2 1, 1, 1, 1, 1, 2
4 No Encontrado #4 #1 #6 #6 #2 #9 #9 #7 ... #9 - 2, 2 1, 1, 1, 1, 1, 2, 2, 2
5 Encontrado #4 #1 #6 #6 #2 #9 #9 #7 ... #10 - 2, 2, 2 1, 1, 1, 1, 1, 2, 2, 2, 2, 2
6 Encontrado #4 #1 #6 #6 #2 #9 #9 #7 ... #11 - 2, 2, 1 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1

Comenzamos nuevamente el bucle leyendo el siguiente código. CODIGO sería ahora #6 y esta vez tenemos un registro para este código en nuestra tabla de códigos. De esta forma, volcamos el código {#6} al flujo de índices el cual sería 1,1. Ahora tomamos el primer índice en {#6} y lo llamamos K. Aquí, {#6} tiene 2 índices, el primero de los cuales es 1; por lo tanto K = 1. Antes de movernos, agregamos {CODIGO-1}+K a la tabla de códigos. Este #7 es ahora 1,1,1 [Paso 2].

He incluido unos pocos pasos más para que puedas ver el algoritmo en acción. Si bien la explicación puede sonar complicada, puedes ver que de hecho es bastante simple. También notarás que terminas generando exactamente la misma tabla de códigos que la que creamos durante la compresión. Esta es la razón por la que LZW es tan maravilloso; podemos simplemente compartir los códigos y no la tabla.



Guardando el Flujo de Código como Bytes

Te he mostrado cómo ír de ida y vuelta entre flujo de índices y de códigos, pero no te he dicho qué hacer con ellos. El flujo de índices se usa para especificar el color de cada pixel de tu imagen y realmente solo se muestra en pantalla. Es el flujo de códigos el que realmente se almacena en los archivos GIF en tu computadora o es transmitido por Internet. A fin de guardar estos flujos de códigos, debemos convertirlos en bytes. La primer idea podría ser almacenar cada uno de estos códigos en su propio byt; sin embargo esto limitaría el código máximo solamente a #255 y resultaría en muchos bits desperdiciados para los códigos pequeños. Para resolver estos problemas, el formato GIF usa de hecho tamaños de códigos flexibles.

Los tamaños de códigos flexibles permiten mayor compresión al limitar los bits requeridos para guardar el flujo de códigos como bytes. El tamaño de código es el número de bits que se necesitan para almacenar el valor del código. Cuando hablamos sobre esto, nos referimos a los 1's y 0's que conforman un byte. Los códigos son convertidos a sus valores binarios para llegar al punto de estos bits. Para especificar el código para #4, mirarías su equivalente binario, que es 100b, y verías que necesitas 3 bits para almacenar este valor. El valor de código más grande en nuestro flujo de códigos es #36 (binario: 100100), el cual tomaría 6 bits para ser codificado. Nota que el número de bits que acabo de dar es el número mínimo. Puedes hacer que el número tome más bits agregando ceros al frente.

Bloque de Datos de Imagen

Necesitamos una manera de saber qué tamaño tiene cada uno de los códigos. Recuerda que el bloque de datos de imagen comienza con un byte llamado el tamaño mínimo de código LZW. El formato GIF permite tamaños tan pequeños de hasta 2 bits y tan grandes de hasta 12 bits. Este tamaño mínimo de código típicamente es el número de bits por pixel de la imagen. Así que si tienes 32 colores en tu imagen, necesitarás 5 bits por pixel (para los números 0-31 porque 31 en binario es 11111b). Por lo tanto, este más probablemente será un bit más que el valor de bits para el tamaño de la tabla de color que estás usando. (Aun si tienes solo 2 colores, el tamaño mínimo de código debe ser al menos 2.) Refiérete a la tabla de color anterior para recordarte cómo es que esto funciona.

Lo gracioso es esto: el valor para el tamaño mínimo de código de hecho no es el tamaño de código más pequeño que se usa en el proceso de codificación. Ya que el tamaño mínimo de código te dice cuántos bits se necesitan solo para los diferentes colores de la imagen, todavía tienes que contabilizar los dos códigos especiales que siempre agregamos a la tabla de código. Por lo tanto, el tamaño de código más pequeño que de hecho será usado es uno más que el valor especificado en el byte de tamaño "mínimo" de código. A este nuevo valor le llamaré el tamaño del primer código.

Sabemos cuántos bits tendrá el primer código. Este tamaño probablemente funcionará para los próximos pocos códigos también, pero recuerda que el formato GIF permite tamaños de códigos flexibles. A medida que se agregan códigos más grandes a tu tabla de códigos, pronto te darás cuenta que necesitas tamaños de códigos más grandes si fueras a devolver esos valores. Cuando estás codificando los datos, incrementas tu tamaño de código tan pronto como escribas el código igual a 2^(tamaño actual de código)-1. Si estás decodificando de códigos a índices, necesitas incrementar tu tamaño de código tan pronto como agregues el valor de código que sea igual a 2^(tamaño actual de código)-1 a tu tabla de códigos. Es decir, la próxima vez que tomes la siguiente sección de bits, tú tomas un bit más.

Nota que el tamaño de código más grande permitido es 12 bits. Si llegas a este límite, el siguiente código que encontrarás debería ser el código clear el cual te diría que reinicialices la tabla de códigos. Entonces regresarías a usar el primer tamaño de código y lo harías crecer nuevamente cuando fuera necesario.

Volviendo a nuestra imagen de muestra, vemos que tenemos un tamaño mínimo de código de 2, lo que significa que nuestro primer tamaño de código será de 3 bits. Nuestros primeros tres códigos, #1 #6 y #6, estarían codificados como 011 y 110 y 100. Si miras el Paso 6 de la codificación, agregamos un código de #7 a nuestra tabla de códigos. Esta es nuestra pista para incrementar nuestro tamaño de código porque 7 es igual a 2^3-1 (en donde 3 es nuestro tamaño de código actual). Así, el siguiente código que escribimos, #2, usará el nuevo tamaño de código de 4 y por lo tanto se verá como 0010b. En el proceso de decodificación, nuevamente incrementaríamos nuestro tamaño de código cuando leyéramos el código #7 y leeríamos los siguientes 4, en lugar de 3 bits, para obtener el código. En la tabla de muestra anterior esto ocurre en el Paso 2.

Finalmente debemos convertir todos estos valores de bits en bytes. El bit de menor peso del valor de bits del código está ubicado en el bit de menor peso del byte. Después de que has rellenado los 8 bits en el byte, tomas cualesquiera otros bits restantes y comienzas un nuevo byte. Dale un vistazo a la siguiente ilustración para que veas cómo funciona eso con los códigos de nuestra imagen de muestra.

lzw_encoding_codes.gif

Puedes ver en el primer byte que recuperamos ( 8C ) que los tres bits de menor peso (porque ese era nuestro primer tamaño de código) contiene 110b, el cual es el valor binario de 4, así que ese sería el código clear con el que empezamos, #4. En los 3 bits a la izquierda, miras 001b, que es nuestro primer código de datos de #1. También puedes ver cuando cambiamos a un tamaño de códigos de 4 bits en el segundo byte ( 2D ).

Cuando te quedas sin códigos pero has llenado menos de 8 bits del byte, simplemente deberías rellenar los bits restantes con ceros. Recuerda que los datos de imagen deben dividirse en sub-bloques de datos. Cada uno de los sub-bloques de datos comienza con un byte que especifica cuántos bytes de datos hay. El valor estará entre 1 y 255. Después de que lees esos bytes, el siguiente byte indica nuevamente cuántos bytes de datos siguen. Te detienes cuando encuentras un sub-bloque que tiene una longitud de 0. Eso te dice cuándo has alcanzado el final de los datos de imagen. En nuestra imagen de ejemplo, el byte justo después del tamaño de código LZW es 0x16 lo que indica que siguen 22 bytes de datos. Después de que los alcanzamos, vemos que el siguiente byte es 00, lo que significa que hemos terminado.

Devolver códigos a partir de bytes es básicamente el mismo proceso pero a la inversa. A continuación una ilustración de muestra del proceso, la cual muestra cómo extraerías códigos si el primer tamaño de código fuera de 5 bits.

lzw_decoding _bytes.gif



Siguiente: Animación y Transparencia

Eso es prácticamente todo lo que necesitas saber para leer o generar un archivo básico. Una de las razones por las que los GIF se convirtieron en un formato tan popular fue porque también permitía características más "vistosas". Estas características incluyen animación y transparencia. A continuación veremos cómo estas funcionan. Continuar...

[Índice Proyecto 3MF: Qué Hay en un GIF]
[Índice del Sitio Web]
[Índice del Foro]