Especificación para WebP sin pérdida de bits

Dr. Jyrki Alakuijala Google Inc. 19/06/2012

El 16 de septiembre de 2014 se enmendaron los párrafos marcados como [AMENDED].

El 13 de mayo de 2022 se modificaron los párrafos marcados como [AMENDED2].

El 21 de noviembre de 2022 se enmendaron los párrafos marcados como [AMENDED3].

Resumen

WebP sin pérdida es un formato de imagen para la compresión sin pérdida de imágenes ARGB. El formato sin pérdida almacena y restablece los valores de píxel exactamente, incluidos los valores de color para los píxeles cuyo valor alfa es 0. El formato usa imágenes de subresolución, incorporadas de manera recurrente en el formato, para almacenar datos estadísticos sobre las imágenes, como los códigos de entropía usados, los predictores espaciales, la conversión de espacio de color y la tabla de colores. LZ77, la codificación de prefijos y una caché de color se usan para la compresión de datos masivos. Se demostraron velocidades de decodificación más rápidas que PNG, así como una compresión un 25% más densa que la que se puede lograr con el formato PNG actual.

1 Introducción

En este documento, se describe la representación de datos comprimidos de una imagen WebP sin pérdida. Está diseñado como una referencia detallada para la implementación del codificador y el decodificador WebP sin pérdida.

En este documento, usamos ampliamente la sintaxis del lenguaje de programación C para describir el flujo de bits y suponemos que existe una función para leer bits, ReadBits(n). Los bytes se leen en el orden natural de la transmisión que los contiene, y los bits de cada byte se leen en el orden de importancia de menor bit. Cuando se leen varios bits al mismo tiempo, el número entero se construye a partir de los datos originales en el orden original. Los bits más significativos del número entero que se muestra también son los bits más significativos de los datos originales. Entonces, la declaración

b = ReadBits(2);

es equivalente a las siguientes dos afirmaciones:

b = ReadBits(1);
b |= ReadBits(1) << 1;

Suponemos que cada componente de color (p.ej., Alfa, rojo, azul y verde) se representa con un byte de 8 bits. Definimos el tipo correspondiente como uint8. Un píxel ARGB completo se representa mediante un tipo llamado uint32, un número entero sin firma que consta de 32 bits. En el código que muestra el comportamiento de las transformaciones, el valor alfa se codifica en los bits 31.24, rojo en los bits 23, 16, verde en los bits 15.8 y azul en los bits 7.0, pero las implementaciones del formato son libres de usar otra representación internamente.

En términos generales, una imagen WebP sin pérdida contiene datos de encabezado, información de transformación y datos de una imagen real. Los encabezados contienen el ancho y la altura de la imagen. Una imagen WebP sin pérdida puede pasar por cuatro tipos diferentes de transformación antes de ser codificada por la entropía. La información de transformación en el flujo de bits contiene los datos necesarios para aplicar las respectivas transformaciones inversas.

2 nomenclaturas

RGB

Es un valor de píxel compuesto por valores alfa, rojo, verde y azul.

Imagen de ARGB

Es un array bidimensional que contiene píxeles ARGB.

caché de color

Es un pequeño array con direcciones hash para almacenar colores usados recientemente a fin de recuperarlos con códigos más cortos.

imagen de indexación de colores

Imagen unidimensional de colores que se puede indexar mediante un número entero pequeño (hasta 256 en WebP sin pérdida).

imagen de transformación de color

Imagen de subresolución bidimensional que contiene datos sobre las correlaciones de los componentes de color.

mapeo de distancia

Cambia las distancias de LZ77 a fin de que tengan los valores más pequeños para los píxeles de proximidad en 2D.

imagen de entropía

Una imagen de subresolución bidimensional que indica qué codificación de entropía se debe usar en un cuadrado respectivo en la imagen, es decir, cada píxel es un código de prefijo de meta.

código de prefijo

Es una forma clásica de codificar entropía en la que se usa una menor cantidad de bits para los códigos más frecuentes.

LZ77

Algoritmo de compresión de ventanas deslizantes basado en diccionario que emite símbolos o los describe como secuencias de símbolos pasados.

código de meta prefijo

Es un número entero pequeño (de hasta 16 bits) que indexa un elemento en la tabla de prefijo de meta.

imagen de Predictor

Imagen de subresolución bidimensional que indica qué predictor espacial se usa para un cuadrado en particular de la imagen.

codificación de prefijos

Una forma de entropizar números enteros más grandes que codifican algunos bits del número entero con un código de entropía y codifica los bits restantes sin procesar. Esto permite que las descripciones de los códigos de la entropía se mantengan relativamente pequeñas, incluso cuando el rango de símbolos es grande.

orden de la línea de análisis

Es un orden de procesamiento de píxeles que va de izquierda a derecha, de arriba hacia abajo, y comienza desde el píxel de la izquierda, hacia la derecha. Una vez que se complete una fila, continúa desde la columna de la izquierda de la siguiente fila.

3 RIFF Header

El comienzo del encabezado tiene el contenedor RIFF. Esto consiste en los siguientes 21 bytes:

1. String "RIFF"
2. Un valor little-endian de 32 bits de la longitud del bloque, todo el tamaño del bloque controlado por el encabezado RIFF. Por lo general, es igual al tamaño de la carga útil (tamaño del archivo menos 8 bytes: 4 bytes para el identificador “RIFF”) y 4 bytes para almacenar el valor en sí.
3. String "WEBP" (nombre del contenedor RIFF).
4. String "VP8L" (etiqueta de fragmento para datos de imagen codificados sin pérdida).
5. Un valor little-endian de 32 bits de la cantidad de bytes en la transmisión sin pérdidas.
6. Firma de un byte 0x2f.

Los primeros 28 bits del flujo de bits especifican el ancho y la altura de la imagen. El ancho y la altura se decodifican como números enteros de 14 bits de la siguiente manera:

int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;

La dinámica de 14 bits para el tamaño de imagen limita el tamaño máximo de una imagen WebP sin pérdida a 16,384 px 16,384 píxeles.

El bit alpha_is_used es solo una sugerencia y no debe afectar la decodificación. Se debe establecer en 0 cuando todos los valores alfa son 255 en la imagen y 1 en el caso contrario.

int alpha_is_used = ReadBits(1);

El version_number es un código de 3 bits que se debe establecer en 0. Cualquier otro valor debe tratarse como un error. [MODIFICACIÓN]

int version_number = ReadBits(3);

Cuatro transformaciones

Las transformaciones son manipulaciones reversibles de los datos de la imagen que pueden reducir la entropía simbólica restante mediante el modelado de las correlaciones espaciales y de color. Las transformaciones pueden hacer que la compresión final sea más densa.

Una imagen puede pasar por cuatro tipos de transformaciones. Un bit de 1 indica la presencia de una transformación. Cada transformación se puede usar solo una vez. Las transformaciones se usan solo para la imagen ARGB de nivel principal: las imágenes de subresolución no tienen transformaciones, ni siquiera el bit 0 que indica el final de las transformaciones.

Por lo general, un codificador usa estas transformaciones para reducir la entropía Shannon en la imagen residual. Además, los datos de transformación se pueden decidir en función de la minimización de la entropía.

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 4).

Si hay una transformación presente, los dos bits siguientes especifican el tipo de transformación. Existen cuatro tipos de transformaciones.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

A los tipos de transformación los siguen los datos de transformación. Los datos de transformación contienen la información necesaria para aplicar la transformación inversa y dependen del tipo de transformación. A continuación, describimos los datos de transformación para diferentes tipos.

4.1 Transformación Predictor

La transformación del predictor se puede usar para reducir la entropía mediante la explotación del hecho de que los píxeles vecinos a menudo están correlacionados. En la transformación del predictor, el valor de píxel actual se predice a partir de los píxeles ya decodificados (en orden de línea de análisis) y solo se codifica el valor residual (real-predicdo). El modo de predicción determina el tipo de predicción que se usará. Dividimos la imagen en cuadrados y todos los píxeles de un cuadrado usan el mismo modo de predicción.

Los primeros 3 bits de datos de predicción definen el ancho y el alto del bloque en cantidad de bits. La cantidad de columnas de bloque, block_xsize, se usa en la indexación bidimensional.

int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) ((num) + (den) - 1) / (den))
int block_xsize = DIV_ROUND_UP(image_width, 1 << size_bits);

Los datos de transformación contienen el modo de predicción para cada bloque de la imagen. Todos los block_width * block_height píxeles de un bloque usan el mismo modo de predicción. Los modos de predicción se tratan como píxeles de una imagen y se codifican con las mismas técnicas descritas en el Capítulo 5.

Para un píxel x, y, se puede calcular la dirección del bloque de filtros correspondiente de la siguiente manera:

int block_index = (y >> size_bits) * block_xsize +
                  (x >> size_bits);

Existen 14 modos de predicción diferentes. En cada modo de predicción, el valor de píxel actual se predice a partir de uno o más píxeles vecinos cuyos valores ya son conocidos.

Elegimos los píxeles vecinos (TL, T, TR y L) del píxel actual (P) de la siguiente manera:

O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    TL   T    TR   O    O    O    O
O    O    O    O    L    P    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X

donde el TL significa superior izquierda, T superior, TR superior derecha, L izquierdo píxel. En el momento de predecir un valor para P, todos los píxeles O, TL, T, TR y L ya se procesaron y el píxel P y todos los píxeles X son desconocidos.

Dados los píxeles cercanos anteriores, los diferentes modos de predicción se definen de la siguiente manera:

Mode	Valor previsto de cada canal para el píxel actual
0	0xff000000 (representa un color negro liso en ARGB)
1	(izq.)
2	T
3	TR
4	TL
5	Promedio2(Promedio2(L, TR), T)
6	Promedio2(L, TL)
7	Promedio2(L, T)
8	Promedio2(TL, T)
9	Promedio2(T, TR)
10	Promedio2(Promedio2(L, TL), Promedio2(T, TR))
11	Seleccionar(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Promedio2(L, T), TL)

Average2 se define de la siguiente manera para cada componente de ARGB:

uint8 Average2(uint8 a, uint8 b) {
  return (a + b) / 2;
}

El predictor Select se define de la siguiente manera:

uint32 Select(uint32 L, uint32 T, uint32 TL) {
  // L = left pixel, T = top pixel, TL = top left pixel.

  // ARGB component estimates for prediction.
  int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
  int pRed = RED(L) + RED(T) - RED(TL);
  int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
  int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);

  // Manhattan distances to estimates for left and top pixels.
  int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
           abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
  int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
           abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));

  // Return either left or top, the one closer to the prediction.
  if (pL < pT) {     // \[AMENDED\]
    return L;
  } else {
    return T;
  }
}

Las funciones ClampAddSubtractFull y ClampAddSubtractHalf se realizan para cada componente de ARGB de la siguiente manera:

// Clamp the input value between 0 and 255.
int Clamp(int a) {
  return (a < 0) ? 0 : (a > 255) ?  255 : a;
}

int ClampAddSubtractFull(int a, int b, int c) {
  return Clamp(a + b - c);
}

int ClampAddSubtractHalf(int a, int b) {
  return Clamp(a + (a - b) / 2);
}

Existen reglas de control especiales para algunos píxeles del borde. Si hay una transformación de predicción, independientemente del modo [0.13] para estos píxeles, el valor previsto para el píxel superior izquierdo de la imagen es 0xff000000, L-píxel para todos los píxeles en la fila superior y T-píxel para todos los píxeles en la columna más a la izquierda.

[AMENDED2] Se ofrece una excepción al TR-píxel de píxeles en la columna de la derecha. Los píxeles de la columna más a la derecha se predicen usando los modos [0.13] al igual que los píxeles que no están en el borde, pero el píxel más a la izquierda en la misma fila que el píxel actual se usa como el TR-píxel.

4.2 Transformación del color

[AMENDED2]

El objetivo de la transformación de color es decorar los valores de R, G y B de cada píxel. La transformación de color mantiene el valor verde (G) tal como está, transforma el rojo (R) en verde y transforma el azul (B) en verde y, luego, en rojo.

Al igual que con la transformación del predictor, primero la imagen se divide en bloques y el mismo modo de transformación se usa para todos los píxeles en un bloque. Para cada bloque hay tres tipos de elementos de transformación de color.

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

La transformación de color real se realiza definiendo un delta de transformación de color. El delta de la transformación de color depende de ColorTransformElement, que es igual para todos los píxeles de un bloque en particular. El delta se resta durante la transformación de color. La transformación inversa del color está agregando esos deltas.

La función de transformación de color se define de la siguiente manera:

void ColorTransform(uint8 red, uint8 blue, uint8 green,
                    ColorTransformElement *trans,
                    uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the transform is just subtracting the transform deltas
  tmp_red  -= ColorTransformDelta(trans->green_to_red_,  green);
  tmp_blue -= ColorTransformDelta(trans->green_to_blue_, green);
  tmp_blue -= ColorTransformDelta(trans->red_to_blue_, red);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

ColorTransformDelta se calcula mediante un número entero de 8 bits con firma que representa un número de punto fijo de 3.5 puntos y un canal de color RGB firmado de 8 bits (c) [-128..127] y se define de la siguiente manera:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

Se requiere una conversión de la representación sin firma de 8 bits (uint8) a la firmada de 8 bits (int8) antes de llamar a ColorTransformDelta(). Debe realizarse mediante el complemento de 8 bits de dos (es decir, el rango uint8 [128..255] se asigna al rango [-128.--1] del valor int8 convertido).

La multiplicación se realiza con más precisión (con dinámicas de al menos 16 bits). La propiedad de la extensión de signo de la operación de cambio no importa aquí: solo se usan los 8 bits más bajos del resultado y el cambio de extensión de signo y el cambio sin firma son coherentes entre sí.

Ahora describimos el contenido de los datos de transformación de color para que la decodificación pueda aplicar la transformación de color inversa y recuperar los valores rojo y azul originales. Los primeros 3 bits de los datos de transformación de color contienen el ancho y la altura del bloque de imagen en cantidad de bits, al igual que la transformación del predictor:

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

La parte restante de los datos de transformación de color contiene instancias ColorTransformElement correspondientes a cada bloque de la imagen. Las instancias de ColorTransformElement se tratan como píxeles de una imagen y se codifican con los métodos que se describen en el capítulo 5.

Durante la decodificación, las instancias ColorTransformElement de los bloques se decodifican y la transformación de color inversa se aplica en los valores ARGB de los píxeles. Como se mencionó anteriormente, esa transformación inversa de color solo agrega valores ColorTransformElement a los canales rojo y azul. [AMENDED3]

void InverseTransform(uint8 red, uint8 green, uint8 blue,
                      ColorTransformElement *trans,
                      uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the inverse transform is just adding the
  // color transform deltas
  tmp_red  += ColorTransformDelta(trans->green_to_red, green);
  tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue +=
      ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

4.3 Restar transformación verde

Resta una transformación verde de los valores verdes de los valores rojo y azul de cada píxel. Cuando esta transformación está presente, el decodificador debe agregar el valor verde a rojo y azul. No hay datos asociados con esta transformación. El decodificador aplica la transformación inversa de la siguiente manera:

void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
  *red  = (*red  + green) & 0xff;
  *blue = (*blue + green) & 0xff;
}

Esta transformación es redundante, ya que se puede modelar mediante la transformación de color, pero suele ser útil. Debido a que puede extender la dinámica de la transformación de color y no hay datos adicionales aquí, la transformación verde de resta se puede codificar con menos bits que una transformación de color total.

4.4 Transformación de la indexación de colores

Si no hay muchos valores de píxel únicos, puede ser más eficiente crear un arreglo de índice de color y reemplazar los valores de píxeles por los índices del arreglo. La transformación de indexación de colores lo logra. (En el contexto de WebP sin pérdida, no lo llamamos una transformación de paleta porque existe un concepto similar, pero más dinámico, en la codificación WebP sin pérdida: caché de color).

La transformación de indexación de colores verifica la cantidad de valores ARGB únicos en la imagen. Si ese número es inferior a un umbral (256), crea un arreglo de esos valores ARGB, que luego se usa para reemplazar los valores de píxeles con el índice correspondiente: el canal verde de los píxeles se reemplazan con el índice; todos los valores alfa se establecen en 255; todos los valores rojo y azul en 0.

Los datos de transformación contienen el tamaño de la tabla de colores y las entradas de la tabla de colores. El decodificador lee los datos de transformación de la indexación de colores de la siguiente manera:

// 8 bit value for color table size
int color_table_size = ReadBits(8) + 1;

La tabla de colores se almacena con el formato de almacenamiento de imágenes propio. La tabla de colores se puede obtener mediante la lectura de una imagen, sin el encabezado RIFF, el tamaño de la imagen y las transformaciones, suponiendo que se requiere una altura de un píxel y un ancho de color_table_size. La tabla de colores siempre está codificada mediante resta para reducir la entropía de imágenes. Los deltas de colores de la paleta suelen contener mucho menos entropía que los colores en sí, lo que genera un ahorro significativo para las imágenes más pequeñas. En la decodificación, cada color final en la tabla de colores se puede obtener si agregas los valores de los componentes de color anteriores por cada componente de ARGB y almacenas los 8 bits menos significativos del resultado.

La transformación inversa de la imagen es simplemente reemplaza los valores de píxeles (que son índices de la tabla de colores) por los valores reales de la tabla de colores. La indexación se realiza según el componente verde del color ARGB.

// Inverse transform
argb = color_table[GREEN(argb)];

Si el índice es igual o mayor que color_table_size, el valor de color de argb debe establecerse en 0x00000000 (negro transparente). [MODIFICACIÓN]

Cuando la tabla de colores es pequeña (igual o inferior a 16 colores), se agrupan varios píxeles en uno solo. La agrupación de píxeles empaqueta varios píxeles (2, 4 u 8) en un solo píxel, lo que reduce el ancho de la imagen respectivamente. La agrupación de píxeles permite una codificación de entropía de distribución conjunta más eficiente de los píxeles vecinos y brinda algunos beneficios similares a la codificación aritmética para el código de entropía, pero solo se puede usar cuando hay 16 valores únicos o menos.

color_table_size especifica cuántos píxeles se combinan:

int width_bits;
if (color_table_size <= 2) {
  width_bits = 3;
} else if (color_table_size <= 4) {
  width_bits = 2;
} else if (color_table_size <= 16) {
  width_bits = 1;
} else {
  width_bits = 0;
}

width_bits tiene un valor de 0, 1, 2 o 3. Un valor de 0 indica que no se realizará ninguna agrupación de píxeles para la imagen. Un valor de 1 indica que se combinan dos píxeles y que cada píxel tiene un rango de [0.15]. Un valor de 2 indica que se combinan cuatro píxeles y cada píxel tiene un rango de [0.3]. Un valor de 3 indica que se combinan ocho píxeles y que cada píxel tiene un rango de [0.1], es decir, un valor binario.

Los valores se empaquetan en el componente verde de la siguiente manera:

• width_bits = 1: Por cada valor x en el que x ≡ 0 (mod 2), un valor verde en x se posiciona en los 4 bits menos significativos del valor verde en x / 2, un valor verde en x + 1 en los 4 bits más significativos del valor verde en x / 2.
• width_bits = 2: por cada valor x en el que x ≡ 0 (mod 4), un valor verde en x se posiciona en los 2 bits menos significativos del valor verde en x / 4, los valores verdes en x + 1 a x + 3 se ordenan en los bits más significativos del valor verde en x / 4.
• width_bits = 3: para cada valor x en el que x ≡ 0 (mod 8), un valor verde en x se posiciona en el bit menos significativo del valor verde en x / 8, los valores verdes en x + 1 a x + 7 se posicionan en los bits más significativos del valor verde en x / 8.

5 Datos de imagen

Los datos de imagen son una matriz de valores de píxeles en línea de análisis.

5.1 Funciones de los datos de imagen

Usamos datos de imagen en cinco roles diferentes:

1. Imagen de ARGB: Almacena los píxeles reales de la imagen.
2. Imagen de entropía: Almacena los códigos de prefijos de meta. Los componentes rojo y verde de un píxel definen el código de prefijo meta que se usa en un bloque específico de la imagen ARGB.
3. Imagen de Predictor: Almacena los metadatos de la Transformación Predictor. El componente verde de un píxel define cuál de los 14 predictores se usa dentro de un bloque específico de la imagen ARGB.
4. Imagen de transformación de color. Se crea con los valores ColorTransformElement (definidos en la Transformación de color) para diferentes bloques de la imagen. Cada 'cte' de ColorTransformElement se trata como un píxel cuyo componente alfa es 255, el componente rojo es cte.red_to_blue, el componente verde es cte.green_to_blue y el componente azul es cte.green_to_red.
5. Imagen de indexación de colores: un arreglo de tamaño color_table_size (hasta 256 valores ARGB) que almacenan los metadatos para la Transformación Indexación de colores. Esto se almacena como una imagen de ancho color_table_size y alto 1.

5.2 Codificación de datos de imágenes

La codificación de los datos de imagen es independiente de su función.

Primero, la imagen se divide en un conjunto de bloques de tamaño fijo (por lo general, bloques de 16 × 16). Cada uno de estos bloques se modela usando sus propios códigos de entropía. Además, es posible que varios bloques compartan los mismos códigos de entropía.

Razón: Almacenar un código de entropía genera un costo. Este costo se puede minimizar si los bloques con estadísticas similares comparten un código de entropía, por lo que se almacena ese código solo una vez. Por ejemplo, un codificador puede encontrar bloques similares si los agrupas en clústeres mediante sus propiedades estadísticas, o si unes repetidamente un par de clústeres seleccionados al azar cuando reduce la cantidad general de bits necesarios para codificar la imagen.

Cada píxel se codifica mediante uno de los tres métodos posibles:

1. Literal con prefijo de codificación: cada canal (verde, rojo, azul y alfa) tiene codificación entropía de manera independiente.
2. Referencia inversa LZ77: Se copia una secuencia de píxeles de cualquier otra parte de la imagen.
3. Código de caché de color: mediante un código hash multiplicativo corto (índice de caché de color) de un color visto recientemente.

Las siguientes subsecciones describen cada una de ellas en detalle.

5.2.1 Literales codificados en prefijos

El píxel se almacena como valores codificados en prefijos de verde, rojo, azul y alfa (en ese orden). Consulta esta sección para obtener más detalles.

5.2.2 Referencia hacia atrás LZ77

Las referencias inversas son tuplas de length y distance code:

• La longitud indica la cantidad de píxeles de la línea de análisis que se deben copiar.
• El código de distancia es un número que indica la posición de un píxel visto anteriormente, desde el cual se deben copiar los píxeles. La asignación exacta se describe a continuación.

Los valores de longitud y distancia se almacenan mediante la codificación del prefijo LZ77.

La codificación de prefijo LZ77 divide los números enteros grandes en dos partes: el código de prefijo y los bits adicionales: el código de prefijo se almacena mediante un código de entropía, mientras que los bits adicionales se almacenan como están (sin un código de entropía).

Razón: Este enfoque reduce el requisito de almacenamiento para el código de entropía. Además, los valores grandes suelen ser poco frecuentes, por lo que se usarían bits adicionales para muy pocos valores en la imagen. Por lo tanto, este enfoque da como resultado una mejor compresión general.

En la siguiente tabla, se indican los códigos de prefijo y los bits adicionales que se usan para almacenar diferentes rangos de valores.

Nota: La longitud máxima de la referencia inversa se limita a 4,096. Por lo tanto, solo los primeros 24 códigos de prefijo (con los bits adicionales correspondientes) son significativos para los valores de longitud. Sin embargo, para los valores de distancia, los 40 códigos de prefijo son válidos.

Rango de valores	Código de prefijo	Bits adicionales
1	0	0
2	1	0
3	2	0
4	3	0
5,6	4	1
7,8	5	1
9.12	6	2
13.16	7	2
…	…	…
3,072..4096	23	10
…	…	…
524,289..786432	38	18
786,433..1048576	39	18

El pseudocódigo para obtener un valor (longitud o distancia) del código de prefijo es el siguiente:

if (prefix_code < 4) {
  return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;

Mapa de distancia:

Como se indicó anteriormente, un código de distancia es un número que indica la posición de un píxel visto anteriormente, desde el cual se deben copiar los píxeles. En esta subsección, se define la asignación entre un código de distancia y la posición de un píxel anterior.

Los códigos de distancia mayores a 120 indican la distancia de píxeles en el orden de línea de análisis, desplazada por 120.

Los códigos de distancia más pequeños [1..120] son especiales y están reservados para un barrio cercano del píxel actual. Este barrio tiene 120 píxeles:

• Píxeles de 1 a 7 filas por encima del píxel actual y hasta 8 columnas a la izquierda o hasta 7 columnas a la derecha del píxel actual. [Total de píxeles de este tipo = 7 * (8 + 1 + 7) = 112].
• Píxeles en la misma fila que el píxel actual y hasta 8 columnas a la izquierda del píxel actual. [8 píxeles].

La asignación entre el código de distancia i y la compensación de píxeles vecinas (xi, yi) es la siguiente:

(0, 1),  (1, 0),  (1, 1),  (-1, 1), (0, 2),  (2, 0),  (1, 2),
(-1, 2), (2, 1),  (-2, 1), (2, 2),  (-2, 2), (0, 3),  (3, 0),
(1, 3),  (-1, 3), (3, 1),  (-3, 1), (2, 3),  (-2, 3), (3, 2),
(-3, 2), (0, 4),  (4, 0),  (1, 4),  (-1, 4), (4, 1),  (-4, 1),
(3, 3),  (-3, 3), (2, 4),  (-2, 4), (4, 2),  (-4, 2), (0, 5),
(3, 4),  (-3, 4), (4, 3),  (-4, 3), (5, 0),  (1, 5),  (-1, 5),
(5, 1),  (-5, 1), (2, 5),  (-2, 5), (5, 2),  (-5, 2), (4, 4),
(-4, 4), (3, 5),  (-3, 5), (5, 3),  (-5, 3), (0, 6),  (6, 0),
(1, 6),  (-1, 6), (6, 1),  (-6, 1), (2, 6),  (-2, 6), (6, 2),
(-6, 2), (4, 5),  (-4, 5), (5, 4),  (-5, 4), (3, 6),  (-3, 6),
(6, 3),  (-6, 3), (0, 7),  (7, 0),  (1, 7),  (-1, 7), (5, 5),
(-5, 5), (7, 1),  (-7, 1), (4, 6),  (-4, 6), (6, 4),  (-6, 4),
(2, 7),  (-2, 7), (7, 2),  (-7, 2), (3, 7),  (-3, 7), (7, 3),
(-7, 3), (5, 6),  (-5, 6), (6, 5),  (-6, 5), (8, 0),  (4, 7),
(-4, 7), (7, 4),  (-7, 4), (8, 1),  (8, 2),  (6, 6),  (-6, 6),
(8, 3),  (5, 7),  (-5, 7), (7, 5),  (-7, 5), (8, 4),  (6, 7),
(-6, 7), (7, 6),  (-7, 6), (8, 5),  (7, 7),  (-7, 7), (8, 6),
(8, 7)

Por ejemplo, el código de distancia 1 indica un desplazamiento de (0, 1) para el píxel vecino, es decir, el píxel sobre el píxel actual (diferencia de 0 píxeles en la dirección X y 1 píxel en la dirección Y). Del mismo modo, el código de distancia 3 indica el píxel superior izquierdo.

El decodificador puede convertir un código de distancia i en una distancia de pedido de línea de análisis dist de la siguiente manera:

[AMENDED3]

(xi, yi) = distance_map[i - 1]
dist = xi + yi * xsize
if (dist < 1) {
  dist = 1
}

donde distance_map es la asignación que se mencionó antes y xsize es el ancho de la imagen en píxeles.

5.2.3 Codificación de caché de color

La caché de color almacena un conjunto de colores que se han utilizado recientemente en la imagen.

Razón: De esta manera, a veces se puede referir a los colores usados de manera más eficiente que a emitirlos mediante los otros dos métodos (descritos en 5.2.1 y 5.2.2).

Los códigos de caché de color se almacenan de la siguiente manera. Primero, hay un valor de 1 bit que indica si se usa la caché de colores. Si este bit es 0, no existen códigos de caché de color, y no se transmiten en el código de prefijo que decodifica los símbolos verdes y los códigos de prefijo de longitud. Sin embargo, si este bit es 1, el tamaño de la caché de colores se lee a continuación:

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits define el tamaño de color_cache por (1 <<color_cache_code_bits). El rango de valores permitidos para color_cache_code_bits es [1.11]. Los decodificadores compatibles deben indicar un flujo de bits dañado para otros valores.

Una caché de color es una matriz de tamaño color_cache_size. Cada entrada almacena un color ARGB. Los colores se buscan mediante su indexación por (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Solo se realiza una búsqueda en una caché de color; no hay resolución de conflictos.

Al comienzo de la decodificación o codificación de una imagen, todas las entradas en todos los valores de caché de color se establecen en cero. El código de caché de color se convierte en este color en el momento de la decodificación. El estado de la caché de color se mantiene mediante la inserción de cada píxel, ya sea que se produzca mediante una referencia inversa o, como literales, a la caché en el orden en que aparecen en la transmisión.

6 Código de entropía

6.1 Descripción general

La mayoría de los datos se codifican mediante un código de prefijo canónico. Por lo tanto, los códigos se transmiten mediante el envío de las longitudes de código de prefijos, a diferencia de los códigos de prefijos reales.

En particular, el formato utiliza la codificación de prefijo de variante espacial. En otras palabras, diferentes bloques de la imagen pueden utilizar diferentes códigos de entropía.

Razón: Las diferentes áreas de la imagen pueden tener características diferentes. Por lo tanto, permitirles usar diferentes códigos de entropía proporciona más flexibilidad y, posiblemente, una mejor compresión.

6.2 Detalles

Los datos de la imagen codificada constan de varias partes:

1. Decodificación y compilación de códigos de prefijo [AMENDED2]
2. Códigos de prefijos de Meta
3. Datos de imágenes con codificación de entropía

6.2.1 Decodificación y compilación de códigos de prefijo

Existen varios pasos para decodificar los códigos de prefijo.

Cómo decodificar las longitudes de código:

En esta sección, se describe cómo leer las longitudes de código de prefijos del flujo de bits.

Las longitudes de código del prefijo se pueden codificar de dos maneras. El método utilizado se especifica mediante un valor de 1 bit.

• Si este bit es 1, es un código simple de longitud del código.
• Si este bit es 0, es un código de longitud de código normal.

En ambos casos, puede haber longitudes de código sin usar que aún forman parte de la transmisión. Esto puede ser ineficiente, pero el formato lo permite.

(i) Código simple de longitud del código:

[AMENDED2]

Esta variante se usa en el caso especial cuando solo 1 o 2 símbolos de prefijo están en el rango [0.255] con longitud de código 1. Todas las demás longitudes de código del prefijo son ceros implícitamente.

El primer bit indica el número de símbolos:

int num_symbols = ReadBits(1) + 1;

A continuación, se presentan los valores de símbolos.

Este primer símbolo se codifica mediante 1 u 8 bits, según el valor de is_first_8bits. El rango es [0.1] o [0.255], respectivamente. El segundo símbolo, si está presente, siempre se supone que está dentro del rango [0.255] y está codificado con 8 bits.

int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
  symbol1 = ReadBits(8);
  code_lengths[symbol1] = 1;
}

Nota: Otro caso especial es cuando todas las longitudes de código de prefijos son cero (un código de prefijo vacío). Por ejemplo, un código de prefijo para la distancia puede estar vacío si no hay referencias inversas. Del mismo modo, los códigos de prefijo para Alfa, rojo y azul pueden estar vacíos si todos los píxeles dentro del mismo código de prefijo se producen con la caché de color. Sin embargo, este caso no necesita un manejo especial, ya que los códigos de prefijo vacíos se pueden codificar como los que contienen un solo símbolo 0.

(ii) Código de longitud normal de código:

Las longitudes de código del código de prefijo se ajustan a 8 bits y se leen de la siguiente manera. Primero, num_code_lengths especifica la cantidad de longitudes de código.

int num_code_lengths = 4 + ReadBits(4);

Si num_code_lengths es mayor que 19, la transmisión continua no es válida. [AMENDED3]

Las longitudes de código se codifican mediante códigos de prefijo: longitudes de código de nivel inferior, code_length_code_lengths, primero deben leerse. El resto de esos code_length_code_lengths (de acuerdo con el orden en kCodeLengthCodeOrder) son ceros.

int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
  17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 };  // All zeros
for (i = 0; i < num_code_lengths; ++i) {
  code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}

A continuación, si ReadBits(1) == 0, la cantidad máxima de símbolos de lectura diferentes es num_code_lengths. De lo contrario, se define de la siguiente manera:

int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);

Luego, se crea una tabla de prefijos desde code_length_code_lengths y se usa para leer hasta max_symbol longitudes de código.

• El código [0.15] indica las longitudes de código literal.
  • El valor 0 significa que no se codificaron símbolos.
  • Los valores [1..15] indican la longitud de bits del código respectivo.
• El código 16 repite el valor anterior que no es cero [3.6], es decir, 3 + ReadBits(2) veces Si se usa el código 16 antes de que se emita un valor distinto de cero, se repite un valor de 8.
• El código 17 emite una racha de ceros [3.10], es decir, 3 + ReadBits(3) veces
• El código 18 emite una racha de ceros de longitud [11..138], es decir, 11 + ReadBits(7) veces

Una vez que se leen las longitudes de código, se forma un código de prefijo para cada tipo de símbolo (A, R, G, B, distancia) con sus respectivos tamaños de alfabeto:

• G: 256 + 24 + color_cache_size
• otros literales (A,R,B): 256
• código de distancia: 40

6.2.2 Decodificación de códigos de prefijos de Meta

Como se señaló antes, el formato permite el uso de diferentes códigos de prefijo para distintos bloques de la imagen. Los códigos de prefijos de meta son índices que identifican los códigos de prefijo que se deben usar en diferentes partes de la imagen.

Los códigos de prefijo meta se usan solo cuando la imagen se usa en la función de una imagen ARGB.

Hay dos posibilidades para los códigos de prefijos de meta, que se indican con un valor de 1 bit:

• Si este bit es cero, solo hay un metacódigo de meta en todas las partes de la imagen. No hay más datos almacenados.
• Si este bit es uno, la imagen usa varios códigos de prefijo de meta. Estos códigos de prefijos se almacenan como una imagen de entropía (que se describe a continuación).

Imagen de la entropía:

La imagen de entropía define los códigos de prefijo que se usan en diferentes partes de la imagen, como se describe a continuación.

Los primeros 3 bits contienen el valor prefix_bits. Las dimensiones de la imagen de entropía se derivan de prefix_bits.

int prefix_bits = ReadBits(3) + 2;
int prefix_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);

donde DIV_ROUND_UP es como se definió antes.

Los siguientes bits contienen una imagen entrópica de ancho prefix_xsize y alto prefix_ysize.

Interpretación de los códigos de prefijos de los metadatos:

Para un píxel determinado (x, y), hay un conjunto de cinco códigos de prefijo asociados. Estos códigos están (en orden de bits):

• Código de prefijo n.o 1: Se usa para el canal verde, la longitud de referencia inversa y la caché de color.
• Prefijo 2, 3 y 4: Se usan para los canales rojo, azul y alfa, respectivamente.
• Código de prefijo n.o 5: Se usa para la distancia de referencia inversa.

A partir de ahora, este conjunto se denomina grupo de códigos de prefijo.

La cantidad de grupos de código de prefijos de la imagen ARGB se puede obtener si buscas el código de prefijo de mayor tamaño de la imagen de entropía:

int num_prefix_groups = max(entropy image) + 1;

donde max(entropy image) indica el código de prefijo más grande almacenado en la imagen de entropía.

Como cada grupo de código de prefijo contiene cinco códigos de prefijo, la cantidad total de códigos de prefijo es:

int num_prefix_codes = 5 * num_prefix_groups;

Con un píxel (x, y) en la imagen ARGB, podemos obtener los códigos de prefijo correspondientes para usarlos de la siguiente manera:

int position =
    (y >> prefix_bits) * prefix_xsize + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[pos] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];

en el que se supone que existe una estructura PrefixCodeGroup, que representa un conjunto de cinco códigos de prefijo. Además, prefix_code_groups es un array de PrefixCodeGroup (de tamaño num_prefix_groups).

El decodificador usa el grupo de código de prefijo prefix_group para decodificar el píxel (x, y), como se explica en la sección siguiente.

6.2.3 Decodificación de datos de imágenes con codificación de entropía

[AMENDED2]

Para la posición actual (x, y) en la imagen, el decodificador primero identifica el grupo de código del prefijo correspondiente (como se explica en la última sección). Dado el grupo de código de prefijo, el píxel se lee y decodifica de la siguiente manera:

Lee el siguiente símbolo S de la transmisión de bits con el código de prefijo 1. Ten en cuenta que S es cualquier número entero entre 0 y (256 + 24 + color_cache_size- 1).

La interpretación de S depende de su valor:

1. si S < 256
   1. Usa S como componente verde.
   2. Lee en rojo de la transmisión de bits con el código de prefijo 2.
   3. Lee azul de la transmisión de bits con el código de prefijo 3.
   4. Lee la versión alfa de la transmisión de bits con el código de prefijo 4.
2. si S >= 256 && S < 256 + 24
   1. Usa S-256 como código de prefijo de longitud.
   2. Lee bits adicionales para la longitud desde el flujo de bits.
   3. Determina la longitud L de referencia inversa a partir del código de prefijo de longitud y los bits adicionales que se leen.
   4. Lee el código de prefijo de la distancia desde el flujo de bits con el prefijo 5.
   5. Lee los bits adicionales para la distancia desde el flujo de bits.
   6. Determina la distancia de referencia inversa D desde el código de prefijo de distancia y los bits adicionales que se leen.
   7. Copia los píxeles L (en orden de línea de análisis) de la secuencia de píxeles anterior a ellos en D píxeles.
3. si S >= 256 + 24
   1. Usa S - (256 + 24) como índice en la caché de colores.
   2. Obtén el color ARGB de la caché de color en ese índice.

7 Estructura general del formato

A continuación, se muestra una vista en el formato en formato Augmented Backus-Naur Form (ABNF). No abarca todos los detalles. El fin de la imagen (EOI) solo se codifica de forma implícita en la cantidad de píxeles (xsize * ysize).

7.1 Estructura básica

format       = RIFF-header image-size image-stream
RIFF-header  = "RIFF" 4OCTET "WEBP" "VP8L" 4OCTET %x2F
image-size   = 14BIT 14BIT ; width - 1, height - 1
image-stream = optional-transform spatially-coded-image

7.2 Estructura de las transformaciones

optional-transform   =  (%b1 transform optional-transform) / %b0
transform            =  predictor-tx / color-tx / subtract-green-tx
transform            =/ color-indexing-tx

predictor-tx         =  %b00 predictor-image
predictor-image      =  3BIT ; sub-pixel code
                        entropy-coded-image

color-tx             =  %b01 color-image
color-image          =  3BIT ; sub-pixel code
                        entropy-coded-image

subtract-green-tx    =  %b10

color-indexing-tx    =  %b11 color-indexing-image
color-indexing-image =  8BIT ; color count
                        entropy-coded-image

7.3 Estructura de los datos de la imagen

[AMENDED2]

spatially-coded-image =  color-cache-info meta-prefix data
entropy-coded-image   =  color-cache-info data

color-cache-info      =  %b0
color-cache-info      =/ (%b1 4BIT) ; 1 followed by color cache size

meta-prefix           =  %b0 / (%b1 entropy-image)

data                  =  prefix-codes lz77-coded-image
entropy-image         =  3BIT ; subsample value
                         entropy-coded-image

prefix-codes          =  prefix-code-group *prefix-codes
prefix-code-group     =
    5prefix-code ; See "Interpretation of Meta Prefix Codes" to
                 ; understand what each of these five prefix
                 ; codes are for.

prefix-code           =  simple-prefix-code / normal-prefix-code
simple-prefix-code    =  ; see "Simple Code Length Code" for details
normal-prefix-code    =  code-length-code encoded-code-lengths
code-length-code      =  ; see section "Normal Code Length Code"

lz77-coded-image      =
    *((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)

Una posible secuencia de ejemplo:

RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image