Especificación para WebP sin pérdida de bits

Dra. Jyrki Alakuijala Google LLC, 09-03-2023

Se puede abstraer

WebP sin pérdida es un formato de imagen para la compresión sin pérdida de imágenes ARGB. El formato sin pérdidas almacena y restablece con exactitud los valores de píxeles, incluidos los valores de color de los píxeles cuyo valor alfa es 0. El formato usa imágenes de subresolución, incorporadas de manera recurrente en el formato en sí, para almacenar datos estadísticos sobre las imágenes, como los códigos de entropía usados, los predictores espaciales, la conversión del espacio de color y la tabla de colores. A fin de comprimir los datos masivos, se utiliza un algoritmo universal para la compresión secuencial de datos (LZ77), la codificación con prefijos y una caché de color. Se demostraron velocidades de decodificación más rápidas que las de PNG y 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ñada como una referencia detallada para la implementación del codificador y 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 asumir la existencia de una función para leer bits, ReadBits(n). Los bytes se leen en el orden natural del flujo que los contiene, y los bits de cada byte se leen en el orden de primer bits menos significativo. 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. Por lo tanto, la instrucción

b = ReadBits(2);

equivale a las dos siguientes instrucciones:

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

Suponemos que cada componente de color (alfa, rojo, azul y verde) se representa con un byte de 8 bits. El tipo correspondiente se define como uint8. Un píxel ARGB completo se representa con un tipo llamado uint32, que es un número entero sin firma que consta de 32 bits. En el código que muestra el comportamiento de las transformaciones, estos valores se codifican en los siguientes bits: alfa en los bits 31..24, rojo en los bits 23..16, verde en los bits 15..8 y azul en los bits 7..0. Sin embargo, las implementaciones del formato pueden 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 imagen reales. Los encabezados contienen el ancho y la altura de la imagen. Una imagen WebP sin pérdida puede pasar por cuatro tipos diferentes de transformaciones antes de que se codifique la entropía. La información de transformación en el flujo de bits contiene los datos necesarios para aplicar las transformaciones inversas respectivas.

2 Nomenclatura

ARGB

Es un valor de píxel que consta de valores alfa, rojo, verde y azul.

Imagen ARGB

Es un array bidimensional que contiene píxeles ARGB.

caché de color

Un pequeño array con dirección hash para almacenar los colores usados recientemente a fin de poder recuperarlos con códigos más cortos.

imagen de indexación de colores

Es una 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

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

mapeo de distancia

Cambia las distancias LZ77 para tener los valores más pequeños para los píxeles de proximidad bidimensional.

imagen de entropía

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

LZ77

Es un algoritmo de compresión de ventana deslizante basado en diccionarios que emite símbolos o los describe como secuencias de símbolos pasados.

código de prefijo

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

imagen de predictor

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

código prefijo

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

codificación con prefijos

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

orden de líneas de análisis

Es un orden de procesamiento de píxeles (de izquierda a derecha y de arriba a abajo) que comienza desde el de la parte superior izquierda. Cuando completes una fila, continúa desde la columna de la izquierda de la siguiente.

3 Encabezado de la sección RIFF

El comienzo del encabezado tiene el contenedor RIFF. Esto consta de los siguientes 21 bytes:

1. Cadena "RIFF"
2. Es un valor de 32 bits de tipo little-endian de la longitud del fragmento, que es el tamaño completo del fragmento controlado por el encabezado RIFF. Por lo general, esto equivale 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 de RIFF).
4. String “VP8L” (FourCC para datos de imagen con codificación sin pérdidas).
5. Es un valor de 32 bits de tipo little-endian de la cantidad de bytes en la transmisión sin pérdidas.
6. Firma de 1 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, como se indica a continuación:

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

La precisión de 14 bits para el ancho y el alto de la imagen limita el tamaño máximo de una imagen sin pérdida de WebP a 16,384 ✕ 16,384 píxeles.

El bit alpha_is_used es solo una sugerencia y no debería 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 se debe tratar como un error.

int version_number = ReadBits(3);

4 transformaciones

Las transformaciones son manipulaciones reversibles de los datos de imágenes que pueden reducir la entropía simbólica restante mediante el modelado de las correlaciones espaciales y de color. 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 puede usarse solo una vez. Las transformaciones se usan solo para la imagen ARGB de nivel principal. Las imágenes de subresolución (imagen de transformación de color, imagen de entropía y de predictor) no tienen transformaciones, ni siquiera el 0 bit que indica el final de las transformaciones.

Por lo general, un codificador usaría estas transformaciones para reducir la entropía de 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 5).

Si hay una transformación, 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,
};

Los datos de transformación le siguen al tipo 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. Las transformaciones inversas se aplican en el orden inverso en que se leen desde el flujo de bits, es decir, la última primero.

A continuación, describimos los datos de transformación para diferentes tipos.

4.1 Transformación de Predictor

La transformación de predictor se puede usar para reducir la entropía, ya que se aprovecha el hecho de que los píxeles cercanos a menudo están correlacionados. En la transformación de predictor, el valor de píxel actual se predice a partir de los píxeles ya decodificados (en el orden de la línea de análisis) y solo se codifica el valor residual (real - previsto). El componente verde de un píxel define cuál de los 14 predictores se usa dentro de un bloque particular de la imagen ARGB. 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 la altura del bloque en cantidad de bits. La cantidad de columnas de bloque, block_xsize, se usa en la indexación de dos dimensiones.

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. Es una imagen de subresolución en la que el componente verde de un píxel define cuál de los 14 Predictores se usa para todos los píxeles block_width * block_height dentro de un bloque particular de la imagen ARGB. Esta imagen de subresolución se codifica usando las mismas técnicas que se describen en el Capítulo 5.

Para un píxel (x, y), se puede calcular la dirección del bloque de filtro respectiva 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 cercanos cuyos valores ya se conocen.

Elegimos los píxeles cercanos (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

TL significa arriba a la izquierda, T significa arriba, TR significa parte superior derecha y L significa izquierda. En el momento de predecir un valor para P, ya se procesaron todos los píxeles O, TL, T, TR y L, y se desconocen el píxel P y todos los píxeles X.

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

Modo	El valor previsto de cada canal del píxel actual
0	0xff000000 (representa un color negro sólido en ARGB)
1	L
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 y TL)
13	ClampAddSubtractHalf(Promedio2(L, T), TL)

Average2 se define de la siguiente manera para cada componente 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) {
    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 manejo especiales para algunos píxeles de 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, todos los píxeles de la fila superior son píxeles L y todos los píxeles de la columna más a la izquierda son píxeles T.

Abordar el píxel TR para los píxeles en la columna más a la derecha es excepcional. Los píxeles de la columna más a la derecha se predicen con los modos [0..13], al igual que los píxeles que no están en el borde, pero el píxel de la izquierda en la misma fila que el píxel actual se usa como píxel TR.

El valor del píxel final se obtiene agregando cada canal del valor predicho al valor residual codificado.

void PredictorTransformOutput(uint32 residual, uint32 pred,
                              uint8* alpha, uint8* red,
                              uint8* green, uint8* blue) {
  *alpha = ALPHA(residual) + ALPHA(pred);
  *red = RED(residual) + RED(pred);
  *green = GREEN(residual) + GREEN(pred);
  *blue = BLUE(residual) + BLUE(pred);
}

4.2 Transformación de color

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

Como en el caso de la transformación de predictor, primero la imagen se divide en bloques, y se usa el mismo modo de transformación para todos los píxeles de 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. La transformación delta de color depende del ColorTransformElement, que es el mismo para todos los píxeles de un bloque en particular. El delta se resta durante la transformación de color. Luego, la transformación inversa del color solo agrega 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 signo que representa un número de punto fijo de 3.5 y un canal de color RGB de 8 bits con firma (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 de 8 bits con firma (int8) antes de llamar a ColorTransformDelta(). El valor con firma debe interpretarse como un número de complemento de dos de 8 bits (es decir, el rango de uint8 [128..255] se asigna al rango [-128..-1] de su valor int8 convertido).

La multiplicación se debe realizar con más precisión (con una precisión de al menos 16 bits). La propiedad de 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, allí, 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 originales de rojo y azul. 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 de 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 de ColorTransformElement, que corresponden a cada bloque de la imagen. Cada ColorTransformElement 'cte' se trata como un píxel en una imagen de subresolución cuyo componente alfa es 255, rojo es cte.red_to_blue, verde es cte.green_to_blue y componente azul es cte.green_to_red.

Durante la decodificación, se decodifican las instancias de ColorTransformElement de los bloques y se aplica la transformación de color inversa en los valores ARGB de los píxeles. Como se mencionó antes, esa transformación de color inversa solo agrega valores ColorTransformElement a los canales rojo y azul. Los canales alfa y verde quedan tal como están.

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

La transformación verde resta los valores verdes de los valores rojos y azules de cada píxel. Cuando esta transformación está presente, el decodificador debe agregar el valor verde a los valores 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 con la transformación de color, pero como no hay datos adicionales aquí, la transformación verde de resta se puede codificar con menos bits que una transformación de color completa.

4.4 Transformación de la indexación de colores

Si no hay muchos valores de píxeles únicos, puede ser más eficiente crear un array de índice de color y reemplazar los valores de píxeles por los índices del array. Esto se logra mediante la transformación de indexación de colores. (En el contexto de WebP sin pérdida, específicamente no llamamos a esto una transformación de paleta porque existe un concepto similar pero más dinámico en la codificación sin pérdida de WebP: 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 está por debajo de un umbral (256), crea un array 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 reemplaza por el índice, todos los valores alfa se configuran en 255 y todos los valores rojos y azules 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 the color table size
int color_table_size = ReadBits(8) + 1;

La tabla de colores se almacena usando el formato de almacenamiento de imágenes. La tabla de colores se puede obtener leyendo una imagen sin el encabezado RIFF, el tamaño de la imagen y las transformaciones, si se supone la altura de 1 píxel y el ancho de color_table_size. La tabla de colores siempre está codificada para restas a fin de reducir la entropía de la imagen. Los deltas de los colores de la paleta suelen contener mucha menos entropía que los colores en sí, lo que genera ahorros significativos para imágenes más pequeñas. En la decodificación, cada color final de la tabla de colores se puede obtener si se agregan los valores anteriores de componentes de color de cada componente ARGB por separado y se almacenan los 8 bits menos significativos del resultado.

La transformación inversa de la imagen solo 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 en función del 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 se debe establecer en 0x00000000 (negro transparente).

Cuando la tabla de colores es pequeña (igual o inferior a 16 colores), se agrupan varios píxeles en un solo píxel. 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 de los píxeles cercanos y brinda al código de entropía algunos beneficios similares a la codificación aritmética, 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 debe agrupar ningún píxel para la imagen. Un valor de 1 indica que dos píxeles se combinan y 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 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: Para cada valor x, donde x ≡ 0 (mod 2), un valor verde en x se posiciona en los 4 bits menos significativos del valor verde en x / 2, y un valor verde en x + 1 se posiciona en los 4 bits más significativos del valor verde en x / 2.
• width_bits = 2: Para cada valor x, donde x ≡ 0 (mod 4), un valor verde en x se posiciona en los 2 bits menos significativos del valor verde en x / 4, y los valores verdes en x + 1 a x + 3 se colocan en orden de los bits más significativos del valor verde en x / 4.
• width_bits = 3: Para cada valor x, donde x ≡ 0 (mod 8), un valor verde en x se posiciona en el bit menos significativo del valor verde en x / 8, y los valores verdes en x + 1 a x + 7 se posicionan en orden de los bits más significativos del valor verde en x / 8.

Después de leer esta transformación, width_bits submuestra con image_width. Esto afecta el tamaño de las transformaciones posteriores. El tamaño nuevo se puede calcular con DIV_ROUND_UP, como se definió antes.

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

5 Datos de imágenes

Los datos de imágenes son un array de valores de píxeles en el orden de las líneas de escaneo.

5.1 Roles de los Datos de Imágenes

Usamos los datos de imágenes en cinco roles diferentes:

1. Imagen ARGB: Almacena los píxeles reales de la imagen.
2. Imagen de entropía: Almacena los códigos de prefijos meta (consulta "Decodificación de códigos de prefijos meta").
3. Imagen de Predictor: Almacena los metadatos para la transformación de Predictor (consulta “Transformación de Predictor”).
4. Imagen de transformación de color: Creada por valores ColorTransformElement (definidos en “Color Transform”) para diferentes bloques de la imagen.
5. Imagen de indexación de colores: Es un array de tamaño color_table_size (hasta 256 valores ARGB) que almacena los metadatos para la transformación de indexación de color (consulta “Transformación de indexación de colores”).

5.2 Codificación de Datos de Imágenes

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

La imagen primero 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 con sus propios códigos de entropía. Además, varios bloques pueden compartir 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 estadísticamente similares comparten un código de entropía, que almacena ese código solo una vez. Por ejemplo, un codificador puede encontrar bloques similares agrupándolos en clústeres mediante sus propiedades estadísticas o uniendo repetidamente un par de clústeres seleccionados al azar cuando reduce la cantidad total de bits necesarios para codificar la imagen.

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

1. Literales con código de prefijo: Cada canal (verde, rojo, azul y alfa) se codifica de forma independiente.
2. Referencia inversa de LZ77: Se copia una secuencia de píxeles de otra parte de la imagen.
3. Código de caché de colores: Uso de un código hash multiplicativo corto (índice de caché de color) de un color visto recientemente

En las siguientes subsecciones, se describe cada una de ellas en detalle.

5.2.1 Literales codificados por prefijos

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

5.2.2 Referencia anterior a LZ77

Las referencias hacia atrás son tuplas de longitud y código de distancia:

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

Los valores de longitud y distancia se almacenan mediante la codificación con prefijos LZ77.

La codificación con prefijo LZ77 divide los valores enteros grandes en dos partes: el código de prefijo y los bits adicionales. El código de prefijo se almacena con un código de entropía, mientras que los bits adicionales se almacenan tal 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 raros, por lo que se usarán bits adicionales para muy pocos valores en la imagen. Por lo tanto, este enfoque da como resultado una mejor compresión en 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 respectivos) son significativos para los valores de longitud. Sin embargo, para los valores de distancia, todos los códigos de prefijo de 40 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
…	…	…
3072..4096	23	10
…	…	…
524289..786432	38	18
786433..1048576	39	18

El pseudocódigo para obtener un valor (longitud o distancia) a partir 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;

Mapas de distancia

Como se señaló anteriormente, un código de distancia es un número que indica la posición de un píxel visto anteriormente, desde el que se copiarán 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 superiores a 120 denotan la distancia de píxeles en el orden de la línea de escaneo, con una compensación de 120.

Los códigos de distancia más pequeña [1..120] son especiales y se reservan para una zona cercana del píxel actual. Este vecindario consta de 120 píxeles:

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

La asignación entre el código de distancia i y el desplazamiento del píxel cercano (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 cercano, es decir, el píxel por encima del píxel actual (diferencia de 0 píxeles en la dirección X y de 1 píxel en la dirección Y). De manera similar, 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 orden de líneas de escaneo dist de la siguiente manera:

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

En el ejemplo anterior, 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 la caché de colores

La caché de colores almacena un conjunto de colores que se usaron recientemente en la imagen.

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

Los códigos de caché de colores se almacenan de la siguiente manera. Primero, hay un valor de 1 bit que indica si se usa la caché de color. Si este bit es 0, no existen códigos de caché de colores y estos 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 color 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 la caché de color (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 un array de tamaño color_cache_size. Cada entrada almacena un color ARGB. Los colores se buscan mediante su indexación con (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Solo se realiza una búsqueda en la caché de color; no hay resolución de conflictos.

Al comienzo de la decodificación o codificación de una imagen, todas las entradas de todos los valores de caché de color se establecen en cero. El código de caché de color se convierte a este color en el momento de la decodificación. Para mantener el estado de la caché de color, se inserta cada píxel, ya sea mediante una referencia inversa o como literales, en 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 con un código de prefijo canónico. Por lo tanto, los códigos se transmiten mediante el envío de longitudes de código de prefijos, a diferencia de los códigos de prefijos reales.

En particular, el formato utiliza la codificación de prefijos de variantes espaciales. En otras palabras, es posible que diferentes bloques de la imagen usen diferentes códigos de entropía.

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

6.2 Detalles

Los datos de imagen codificados constan de varias partes:

1. Decodificar y compilar códigos de prefijo
2. Códigos de prefijos meta
3. Datos de imagen con codificación entropía

Para cualquier píxel determinado (x, y), hay un conjunto de cinco códigos prefijos asociados a él. Estos códigos son (en orden de transmisión 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.
• Código de prefijo n.o 2, n.o 3 y n.o 4: Se usa 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, nos referimos a este conjunto como un grupo de códigos de prefijo.

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

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

Las longitudes de los códigos de prefijo se pueden codificar de dos maneras. El método utilizado se especifica con un valor de 1 bit.

• Si este bit es 1, es un código de longitud de código simple.
• 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 todavía formen parte de la transmisión. Esto puede resultar ineficiente, pero el formato lo permite. El árbol descrito debe ser un árbol binario completo. Un nodo de hoja único se considera un árbol binario completo y se puede codificar con el código de longitud de código simple o el código de longitud de código normal. Cuando se codifica un solo nodo de hoja con el código de longitud de código normal, todas las longitudes del código, excepto una, son ceros, y el valor del nodo de hoja único se marca con una longitud de 1, incluso cuando no se consumen bits cuando se usa ese único árbol de nodo de hoja.

Código de longitud de código simple

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 una longitud de código 1. Todas las demás longitudes de código de prefijo son implícitamente ceros.

El primer bit indica la cantidad de símbolos:

int num_symbols = ReadBits(1) + 1;

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

Este primer símbolo se codifica con 1 o 8 bits, según el valor de is_first_8bits. El rango es [0..1] o [0..255], respectivamente. Se supone que el segundo símbolo, si está presente, siempre está en el rango [0..255] y se codifica 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;
}

Los dos símbolos deben ser diferentes. Se permiten símbolos duplicados, pero son ineficientes.

Nota: Otro caso especial es cuando todas las longitudes del código de prefijo son ceros (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. De manera similar, 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 metaprefijo 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 aquellos que contienen un solo símbolo 0.

Código de longitud de código normal

Las longitudes del código del prefijo caben en 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);

Las longitudes del código se codifican mediante códigos prefijos. Primero, se deben leer las longitudes de código de nivel inferior, code_length_code_lengths. El resto de los code_length_code_lengths (según 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);
}

Luego, si es ReadBits(1) == 0, la cantidad máxima de símbolos de lectura diferentes (max_symbol) para cada tipo de símbolo (A, R, G, B y distancia) se establece en su tamaño de alfabeto:

• G channel: 256 + 24 + color_cache_size
• Otros literales (A, R y B): 256
• Código de distancia: 40

De lo contrario, se define de la siguiente manera:

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

Si max_symbol es mayor que el tamaño del alfabeto para el tipo de símbolo, el flujo de bits no es válido.

Luego, se compila una tabla de prefijo a partir de code_length_code_lengths y se usa para leer longitudes de código hasta max_symbol.

• El código [0..15] indica longitudes de código literal.
  • El valor 0 significa que no se codificó ningún símbolo.
  • Los valores [1..15] indican la longitud de bits del código correspondiente.
• El código 16 repite el valor distinto de cero anterior [3..6] veces, 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 el valor 8.
• El código 17 emite una racha de ceros de longitud [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 los códigos, se forma un código de prefijo para cada tipo de símbolo (A, R, G, B y distancia) con sus respectivos tamaños de alfabeto.

El código de longitud de código normal debe codificar un árbol de decisiones completo, es decir, la suma de 2 ^ (-length) para todos los códigos que no sean cero debe ser exactamente uno. Sin embargo, hay una excepción a esta regla, el árbol de nodo de hoja único, en el que el valor del nodo de hoja se marca con el valor 1 y los otros son 0.

6.2.2 Decodificación de códigos de prefijos 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 meta son índices que identifican los códigos de prefijo que se deben usar en diferentes partes de la imagen.

Los códigos de prefijos meta solo se pueden usar cuando la imagen se usa en la función de una imagen ARGB.

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

• Si este bit es cero, solo se usa un código de prefijo en toda la imagen. No se almacenan más datos.
• Si este bit es uno, la imagen usa varios códigos meta de prefijo. Estos códigos meta de prefijo se almacenan como una imagen de entropía (descrita a continuación).

Los componentes rojo y verde de un píxel definen un código de prefijo de 16 bits que se usa en un bloque particular de la imagen ARGB.

Imagen de entropía

La imagen de entropía define qué códigos de prefijo se usan en diferentes partes de la imagen.

Los primeros 3 bits contienen el valor prefix_bits. Las dimensiones de la imagen 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 se define antes.

Los siguientes bits contienen una imagen de entropía de ancho prefix_xsize y altura prefix_ysize.

Interpretación de códigos de prefijos meta

La cantidad de grupos de códigos con prefijo en la imagen ARGB se puede obtener si buscas el código de prefijo más grande en 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ódigos de prefijo contiene cinco códigos de prefijo, la cantidad total de códigos de prefijo es la siguiente:

int num_prefix_codes = 5 * num_prefix_groups;

Dado un píxel (x, y) en la imagen ARGB, podemos obtener los códigos de prefijo correspondientes que se usarán de la siguiente manera:

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

donde asumimos la existencia de la estructura PrefixCodeGroup, que representa un conjunto de cinco códigos prefijos. Además, prefix_code_groups es un array de PrefixCodeGroup (de tamaño num_prefix_groups).

Luego, el decodificador usa el grupo de código de prefijo prefix_group para decodificar el píxel (x, y), como se explica en “Cómo decodificar datos de imágenes codificadas por entropía”.

6.2.3 Decodificación de datos de imágenes codificadas por entropía

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

Luego, lee el símbolo S del flujo de bits con el código de prefijo n.o 1. Ten en cuenta que S es cualquier número entero en el rango de 0 a (256 + 24 + color_cache_size- 1).

La interpretación de S depende de su valor:

1. Si S < 256
   1. Usa la S como el componente verde.
   2. Lee el rojo del flujo de bits con el código de prefijo n.o 2.
   3. Lee el color azul del flujo de bits con el código de prefijo n.o 3.
   4. Lee el valor alfa de la transmisión de bits con el código de prefijo n.o 4.
2. Si S >= 256 y S < 256 + 24
   1. Usa S-256 como código de prefijo de longitud.
   2. Lee bits adicionales para la longitud de la transmisión de bits.
   3. Determina la longitud de la referencia inversa L a partir del código de prefijo de longitud y los bits adicionales que se leen.
   4. Lee el código de prefijo de distancia del flujo de bits con el código de prefijo n.o 5.
   5. Lee bits adicionales para la distancia desde la transmisión de bits.
   6. Determina la distancia D de referencia inversa a partir del código de prefijo de distancia y los bits adicionales leídos.
   7. Copia los píxeles L (en orden de línea de escaneo) de la secuencia de píxeles que comienza en la posición actual menos los píxeles D.
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 del formato en formato Aumentado de Backus-Naur (ABNF) RFC 5234 RFC 7405. No abarca todos los detalles. El final de la imagen (EOI) solo se codifica de forma implícita en la cantidad de píxeles (xsize * ysize).

Ten en cuenta que *element significa que element se puede repetir 0 o más veces. 5element significa que element se repite exactamente 5 veces. %b representa un valor binario.

7.1 Estructura básica

format        = RIFF-header image-header image-stream
RIFF-header   = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header  = %x2F image-size alpha-is-used version
image-size    = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version       = 3BIT ; 0
image-stream  = optional-transform spatially-coded-image

7.2 Estructura de 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 imágenes

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    =  ; see "Normal Code Length Code" for details

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

A continuación, se muestra 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