Especificación para la transmisión de bits sin pérdida de WebP

Dra. Jyrki Alakuijala, Google LLC, 9 de marzo de 2023

Resumen

WebP sin pérdida es un formato de imagen para la compresión sin pérdida de imágenes ARGB. El el formato sin pérdida almacena y restaura los valores de los píxeles con exactitud, incluido el valores de color para píxeles completamente transparentes. Un algoritmo universal para modelos secuenciales como la compresión de datos (LZ77), la codificación de prefijos y el caché de color compresión de los datos masivos. La decodificación de velocidades es mayor que la de 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 un archivo WebP sin pérdida imagen. Está pensado como una referencia detallada para el codificador sin pérdida de WebP y de codificador-decodificador.

En este documento, usamos ampliamente la sintaxis del lenguaje de programación C para describir el flujo de bits y suponer la existencia de una función para leer bits ReadBits(n) Los bytes se leen en el orden natural de la transmisión, que contiene y los bits de cada byte se leen en el orden menos significativo en el que se priorizan los bits. Cuándo se leen varios bits al mismo tiempo, el número entero se construye a partir de la datos originales en el orden original. Los bits más significativos de los enteros también son los bits más importantes de los datos originales. Por lo tanto, el declaración

b = ReadBits(2);

es equivalente con las siguientes dos afirmaciones:

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

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

2 Nomenclatura

ARGB

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 dirigido con hash para almacenar los colores usados recientemente para poder puedes recuperarlos con códigos más cortos.

imagen con indexación de colores

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 bidimensional de subresolución que contiene datos sobre correlaciones de componentes de color.

mapeo de distancia

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

imagen de entropía

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

LZ77

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 metaprefijo

Un número entero pequeño (hasta 16 bits) que indexa un elemento en el prefijo meta .

imagen de predictor

Una imagen de subresolución bidimensional que indica cuál es el predictor espacial que se usa para un cuadrado particular de la imagen.

código de prefijo

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

codificación de prefijo

Es una forma de codificar entropía números enteros más grandes, que codifican unos cuantos 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 entropía sean relativamente pequeñas, el rango de símbolos es amplio.

orden de las líneas de análisis

Un orden de procesamiento de píxeles (de izquierda a derecha y de arriba abajo), que comienza con desde el píxel superior izquierdo. Cuando se complete una fila, continúa desde la columna de la izquierda de la fila siguiente.

3 Encabezado RIFF

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

1. Cadena “RIFF”
2. Un valor Little endian de 32 bits de la longitud del fragmento, que es el tamaño completo. del fragmento controlado por el encabezado RIFF. Normalmente, esto equivale a el tamaño de la carga útil (tamaño del archivo menos 8 bytes: 4 bytes para el archivo “RIFF”) y 4 bytes para almacenar el valor en sí).
3. Cadena “WEBP” (Nombre del contenedor RIFF).
4. Cadena “VP8L” (FourCC para datos de imágenes con codificación sin pérdidas).
5. Un valor de 32 bits bit-endian de la cantidad de bytes en la una transmisión sin pérdida.
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 de la siguiente manera:

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

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

El bit alpha_is_used es solo una sugerencia y no debería afectar la decodificación. Debe establecerse en 0 cuando todos los valores alfa son 255 en la imagen, y en 1 de lo contrario.

int alpha_is_used = ReadBits(1);

El número de versión es un código de 3 bits que se debe establecer en 0. Cualquier otro valor debe tratarse como un error.

int version_number = ReadBits(3);

4 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 correlaciones espaciales y de color. Ellas puede hacer que la compresión final sea más densa.

Una imagen puede atravesar cuatro tipos de transformaciones. Un bit 1 indica la la presencia de una transformación. Cada transformación se puede usar solo una vez. El Las transformaciones solo se usan para la imagen ARGB de nivel principal las imágenes de subresolución (imagen de transformación de color, imagen de entropía e imagen de predictor) no tienen transformaciones, ni siquiera el bit 0 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 pueden decidirse en función de la entropía minimización.

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 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,
};

Al tipo de transformación le siguen los datos de transformación. Los datos de transformación contienen la información necesaria para aplicar la transformación inversa y depende 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, del último primero.

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

4.1 Transformación de Predictor

La transformación de predictor se puede usar para reducir la entropía aprovechando el hecho de que los píxeles vecinos suelen estar correlacionados. En la transformación de predictor, la el valor del píxel actual se predice a partir de los píxeles ya decodificados (en la línea de búsqueda orden) y solo se codifica el valor residual (real - previsto). El verde de un píxel define cuál de los 14 predictores se usa en un bloque específico de la imagen ARGB. El modo de predicción determina el tipo de que usarías. Dividimos la imagen en cuadrados y todos los píxeles de una 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 número. de bits.

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 transform_width = 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. Integra es una imagen de subresolución en la que el componente verde de un píxel define cuál de los 14 predictores se usan para todos los píxeles block_width * block_height dentro un bloque determinado de la imagen ARGB. Esta imagen de subresolución se codifica con las mismas técnicas descritas en el Capítulo 5.

La cantidad de columnas de bloque, transform_width, se usa en dos dimensiones. la indexación de datos. Para un píxel (x, y), se puede calcular el bloque de filtro correspondiente. dirección de:

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

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

Elegimos los píxeles vecinos (TL, T, TR y L) del píxel actual (P) como sigue:

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 TL significa superior izquierda, T significa superior, TR significa superior derecha y L significa izquierda. En el tiempo de predicción de un valor para P, todos los píxeles O, TL, T, TR y L ya se procesaron y se desconocen el píxel P y todos los X píxeles.

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

Modo	Valor predicho de cada canal del píxel actual
0	0xff000000 (representa el color negro sólido en ARGB)
1	L
2	T
3	TR
4	TL
5	Promedio2(Average2(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(Average2(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;
  }
}

Se realizan las funciones ClampAddSubtractFull y ClampAddSubtractHalf. para cada componente 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 un elemento de predicción, sin importar el modo [0..13] de estos píxeles, la el valor predicho para el píxel superior izquierdo de la imagen es 0xff000000, todo píxeles de la fila superior son píxeles L y todos los píxeles de la columna de la izquierda T-pixel.

Se trata de abordar el TR-pixel para los píxeles en la columna más a la derecha. excepcional. Los píxeles de la columna de la derecha se predicen con los modos [0..13], al igual que los píxeles que no están en el borde, sino que son el píxel más a la izquierda del se usa la misma fila que el píxel actual como TR-pixel.

El valor final del píxel se obtiene sumando 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 colores

El objetivo de la transformación de color es decorar los valores R, G y B de cada uno píxel. La transformación de color mantiene el valor verde (G) tal como está y transforma la rojo (R) basado en el valor verde y transforma el valor azul (B) según en el 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 en cada bloque, existen 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 El delta de la transformación de color depende de ColorTransformElement, que es el mismo para todos los píxeles de un bloque en particular. El delta se resta durante el transformación de color. Entonces, 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 con un número entero de 8 bits firmado que representa un Número de punto fijo de 3.5 y un canal de color RGB de 8 bits firmado (c) [-128..127] y se define de la siguiente manera:

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

Una conversión de la representación sin firma de 8 bits (uint8) a la de 8 bits con firma se requiere uno (int8) antes de llamar a ColorTransformDelta(). El valor con signo debe interpretarse como un número de complemento de dos de 8 bits (es decir: rango de uint8) [128..255] se asigna al rango [-128..-1] de su valor int8 convertido.

La multiplicación debe hacerse utilizando más precisión (con al menos 16 bits precisión). 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 y el cambio sin signo son coherentes entre sí.

Ahora, describimos el contenido de los datos de transformación de color para que la decodificación pueda aplicarse la transformación inversa del color y recuperar los valores originales de rojo y azul. El los primeros 3 bits de los datos de transformación de color contienen el ancho y la altura de la 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 ColorTransformElement. correspondientes 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, el componente rojo es cte.red_to_blue, verde el componente es cte.green_to_blue, y el componente azul es cte.green_to_red.

Durante la decodificación, se decodifican instancias ColorTransformElement de los bloques y se aplica la transformación de color inversa en los valores ARGB de los píxeles. Como mencionamos antes, esa transformación inversa de color solo agrega ColorTransformElement a los canales rojo y azul. Alfa y verde canales no sufrirán cambios.

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 Transformación verde de resta

La transformación verde resta los valores verdes de los valores rojo y azul de cada píxel. Cuando esta transformación está presente, el decodificador necesita agregar el bloque valor a los valores rojo y azul. No hay datos asociados con esto transformará. 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 con menos bits que en una transformación de color completa.

4.4 Transformación de indexación de colores

Si no hay muchos valores de píxeles únicos, puede ser más eficiente crear un y reemplaza los valores de píxeles por los índices del array. El color la transformación de indexación para lograrlo. (En el contexto de WebP sin pérdida, específicamente, no la llames una transformación de paleta porque es una transformación existe un concepto 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 el imagen. Si ese número está por debajo de un umbral (256), crea un array de esos 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 establecen en 255 y 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 en el color desde una tabla de particiones. El decodificador lee los datos de transformación de 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 guarda utilizando el formato de almacenamiento de imágenes en sí. La tabla de colores se pueden obtener leyendo una imagen, sin el encabezado RIFF, el tamaño de la imagen y Si se supone la altura de 1 píxel y el ancho de color_table_size. La tabla de colores siempre está codificada con restas para reducir la entropía de la imagen. Deltas de los colores de la paleta contienen generalmente mucha menos entropía que los colores por sí mismos, lo que genera ahorros significativos para las imágenes más pequeñas. En la decodificación, cada color final en la tabla de colores se puede obtener sumando el valor anterior de componentes de color por cada componente ARGB por separado y almacenando 8 bits significativos del resultado.

La transformación inversa para la imagen simplemente reemplaza los valores de píxeles (que son índices de la tabla de colores) con los valores reales de la tabla de colores. La herramienta de 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 RGB debe establecerse en 0x00000000 (negro transparente).

Cuando la tabla de colores es pequeña (igual a 16 colores o menos), varios píxeles se agrupan en un solo píxel. El paquete de píxeles incluye varios elementos (2, 4 u 8) en un solo píxel, lo que reduce el ancho de la imagen, respectivamente. Píxel la agrupación permite una codificación más eficiente de la entropía de distribución conjunta de píxeles cercanos y ofrece algunos beneficios de programación aritmética al código de entropía, pero solo se puede usar cuando hay 16 o menos valores únicos.

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. El valor 0 indica que no hay píxeles realizar la agrupación para la imagen. El valor 1 indica que dos píxeles tienen combinado y cada píxel tiene un rango de [0... 15]. Un valor de 2 indica que se combinan cuatro píxeles y cada uno tiene un rango de [0....3]. Un valor de 3 indica que se combinan ocho píxeles y cada uno 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, donde x ⁕ 0 (mod 2), un verde el valor en x se posiciona en los 4 bits menos significativos de valor verde en x / 2 y un valor verde en x + 1 se posiciona en el Los 4 bits más significativos del valor verde en x / 2.
• width_bits = 2: Por cada valor x, donde x ⁕ 0 (mod 4), un verde valor en x se posiciona en los 2 bits menos significativos de el valor verde en x / 4 y los valores en verde en x + 1 a x + 3 se posicionan en en orden a los bits más significativos del valor verde en x / 4.
• width_bits = 3: Por cada valor x, donde x Local 0 (mod 8), un color verde valor en x se posiciona en la parte menos significativa del verde el valor en x / 8 y los valores en verde en x + 1 a x + 7 se posicionan en orden a los bits más significativos del valor verde en x / 8.

Después de leer esta transformación, width_bits realiza un submuestreo de image_width. Esta afecta el tamaño de las transformaciones posteriores. El nuevo tamaño se puede calcular usando 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 orden de línea 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 metacódigos prefijos (consulta la sección "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 ColorTransformElement valores (definido en "Color Transform") para diferentes bloques de la imagen.
5. Imagen de indexación de color: Un array de tamaño color_table_size (hasta 256 ARGB) valores) almacenando los metadatos para la transformación de indexación de color (consulta "Transformación de indexación de color").

5.2 Codificación de datos de imagen

La codificación de los datos de imágenes es independiente de su función.

La imagen se divide primero en un conjunto de bloques de tamaño fijo (por lo general, de 16 x 16 bloques). Cada uno de estos bloques se modela con sus propios códigos de entropía. Además, varios bloques comparten los mismos códigos de entropía.

Razón: El almacenamiento de un código de entropía genera un costo. Este costo se puede minimizar si bloques estadísticamente similares comparten un código de entropía, lo que almacena ese código una sola vez. Por ejemplo, un codificador puede encontrar bloques similares agrupándolos en clústeres. usando sus propiedades estadísticas o uniendo repetidamente un par de clústeres seleccionados cuando reduce la cantidad total de bits necesarios para codificar la imagen.

Cada píxel se codifica a través de uno de los tres métodos posibles:

1. Literales con código de prefijo: cada canal (verde, rojo, azul y alfa) es de forma independiente.
2. Referencia inversa de LZ77: se copia una secuencia de píxeles desde cualquier otro lugar de la imagen.
3. Código de caché de color: Mediante un código hash multiplicativo corto (caché de color índice) de un color visto recientemente.

Las siguientes subsecciones describen cada una de ellas en detalle.

5.2.1 Literales codificados con prefijo

El píxel se almacena como valores con código de prefijo verde, rojo, azul y alfa (en ese pedido). Consulta la sección 6.2.3 para obtener más detalles.

5.2.2 Referencia de retroactiva de LZ77

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

• La columna Longitud indica la cantidad de píxeles que se copiarán en el orden de las líneas de búsqueda.
• El código de distancia es un número que indica la posición de un del que se copiarán los píxeles. El mapeo exacto es se describe a continuación.

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

La codificación de prefijo LZ77 divide los valores enteros grandes en dos partes: el prefijo código 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 como están (sin un código de entropía).

Razón: Este enfoque reduce el requisito de almacenamiento para la entropía. código. Además, los valores grandes suelen ser poco frecuentes, por lo que se algunos valores en la imagen. Por lo tanto, este enfoque da como resultado una mejor compresión en términos generales.

La siguiente tabla denota los códigos de prefijo y los bits adicionales utilizados para almacenar diferentes rangos de valores.

Nota: La longitud máxima de la referencia inversa se limita a 4,096. Por lo tanto, solo el los primeros 24 códigos de prefijo (con los bits extra respectivos) son significativos para la longitud de salida. 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 a 6	4	1
7 a 8	5	1
9-12	6	2
13-16	7	2
…	…	…
3072.4096	23	10
…	…	…
524289..786432	38	18
786433-1048576	39	18

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

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 distancias

Como se indicó anteriormente, un código de distancia es un número que indica la posición de una píxel visto anteriormente, del que se copiarán los píxeles. Esta subsección define la asignación entre un código de distancia y la posición de un píxel.

Los códigos de distancia superiores a 120 denotan la distancia en píxeles en el orden de la línea de escaneo. y se descuenta de 120.

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

• Píxeles que estén entre 1 y 7 filas sobre el píxel actual y hasta 8 columnas a la izquierda o hasta 7 columnas a la derecha del píxel actual. [Total esos píxeles = 7 * (8 + 1 + 7) = 112].
• Píxeles que se encuentran en la misma fila que el píxel actual y son de hasta 8 columnas a la izquierda del píxel actual. [8 píxeles como este].

La asignación entre el código de distancia distance_code y el píxel vecino la compensación (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 la píxel próximo, es decir, el que se encuentra por encima del píxel actual (0 píxeles diferencia en la dirección X y 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 distance_code en un pedido de líneas de escaneo distancia dist de la siguiente manera:

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

donde distance_map es la asignación mencionada anteriormente y image_width es el ancho. de la imagen en píxeles.

5.2.3 Codificación de la caché de colores

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 hace referencia a los colores usados recientemente. de forma más eficiente que emitirlos utilizando 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 utiliza la caché de color. Si este bit es 0, no hay códigos de caché de color. existen y no se transmiten en el código de prefijo que decodifica la línea símbolos y los códigos de prefijo de longitud. Sin embargo, si este bit es 1, la caché de color el tamaño 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 de 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 ARGB color. Para buscar colores, se indexan 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 de todo color los valores de caché están establecidos en cero. El código de caché de color se convierte a este color en el tiempo de decodificación. El estado de la caché de color se mantiene al insertar cada o píxel, ya sea producido mediante referencia inversa o como literales, en la caché el orden en el que aparecen en las novedades.

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 enviando las longitudes de código de prefijo, como a diferencia de los códigos de prefijo reales.

En particular, el formato utiliza codificación de prefijo de variantes espacial. En otro palabras, diferentes bloques de la imagen pueden usar diferentes entropía en la nube.

Razón: Diferentes áreas de la imagen pueden tener distintas características. 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 imágenes codificadas constan de varias partes:

1. Decodificar y compilar los códigos de prefijo
2. Meta códigos de prefijo.
3. Datos de imágenes con código de entropía.

Para cada píxel (x, y), hay un conjunto de cinco códigos de prefijo asociados con que la modifica. Estos códigos son (en orden de flujo de bits):

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

De ahora en adelante, nos referiremos a este conjunto como 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 los códigos de prefijo del flujo de bits.

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

• Si este bit es 1, es un código simple de longitud de 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 formen parte del en tiempo real. Esto puede ser ineficiente, pero el formato lo permite. El árbol descrito debe ser un árbol binario completo. Un único nodo de hoja es se considera un árbol binario completo y se puede codificar el código de longitud normal o el código de longitud normal. Cuando se programa una sola hoja con el código de longitud normal, todas las longitudes de código excepto uno son ceros, y el valor del nodo de hoja único se marca con una longitud de 1, incluso cuando no hay los bits se consumen cuando se usa ese único árbol de nodos de hoja.

Código simple de longitud del código

Esta variante se utiliza en el caso especial cuando solo hay 1 o 2 símbolos de prefijo el rango [0..255] con la longitud del código 1. Todas las demás longitudes de prefijos de códigos implícitamente ceros.

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

int num_symbols = ReadBits(1) + 1;

Los siguientes son los valores de símbolo.

Este primer símbolo se codifica con 1 u 8 bits, dependiendo del valor de is_first_8bits El rango es [0..1] o [0..255], respectivamente. El segundo si está presente, siempre se supone que está dentro del 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 es ineficiente.

Nota: Otro caso especial es cuando todas las longitudes de los códigos del prefijo son ceros (una 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 el azul puede estar vacío si se producen todos los píxeles dentro del mismo código de metaprefijo utilizando la caché de color. Sin embargo, este caso no necesita un tratamiento 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 normal del código

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 del código.

int num_code_lengths = 4 + ReadBits(4);

Las longitudes de los códigos se codifican a sí misma con códigos de prefijo. código de nivel inferior de longitud, code_length_code_lengths, primero se deben leer. El resto de los code_length_code_lengths (según el pedido de 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 del alfabeto:

• Canal de G: 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 más grande que el tamaño del alfabeto para el tipo de símbolo, el valor El flujo de bits no es válido.

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

• El código [0..15] indica longitudes de código literales.
  • El valor 0 significa que no se ha codificado ningún símbolo.
  • Los valores [1..15] indican la longitud de bits del código respectivo.
• El código 16 repite el valor anterior distinto de cero [3..6] veces, es decir, 3 + ReadBits(2) veces. Si se usa el código 16 antes de un valor distinto de cero emitido, se repite un valor de 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 leídas las longitudes de los códigos, aparecerá un código de prefijo para cada tipo de símbolo (A, R, G, B y distancia) se forma con sus respectivos tamaños de alfabeto.

El código de longitud normal debe codificar un árbol de decisión 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 nodos de hoja único, donde el nodo de hoja el valor se marca con el valor 1 y los demás valores, 0.

6.2.2 Decodificación de códigos de prefijos meta

Como se mencionó antes, el formato permite el uso de diferentes códigos de prefijo para diferentes bloques de la imagen. Los metacódigos de prefijos son índices que identifican cuáles códigos de prefijo que se deben utilizar en diferentes partes de la imagen.

Los metacódigos prefijos se pueden usar solo cuando se use la imagen en el El rol de una imagen ARGB.

Existen dos posibilidades para los metacódigos prefijos, indicados por un código de valor:

• Si este bit es cero, solo se utiliza un código metafijo en todas partes en la imagen. No se almacenan más datos.
• Si este bit es uno, la imagen utiliza varios metacódigos de prefijo. Estos metadatos los códigos de prefijo se almacenan como una imagen de entropía (como se describe a continuación).

Los componentes rojo y verde de un píxel definen un código metaprefijo de 16 bits que se utiliza en un bloque determinado 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 entropía derivan de prefix_bits:

int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
    DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
    DIV_ROUND_UP(image_height, 1 << prefix_bits);

donde DIV_ROUND_UP es como se definió antes.

Los siguientes bits contienen una imagen de entropía de ancho prefix_image_width y alto prefix_image_height

Interpretación de los códigos de prefijos meta

Para obtener el número de grupos de códigos de prefijo en la imagen ARGB el código de metaprefijo más grande 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 con una imagen de entropía única.

Como cada grupo de códigos de prefijo contiene cinco códigos de prefijo, el número total de código es:

int num_prefix_codes = 5 * num_prefix_groups;

Con un píxel (x, y) en la imagen ARGB, se puede obtener el prefijo correspondiente códigos que se usarán de la siguiente manera:

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

en el que asumimos la existencia de la estructura PrefixCodeGroup, que representa un conjunto de cinco códigos de prefijo. Además, prefix_code_groups es un array de PrefixCodeGroup (con un tamaño de 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 "Decodificación de imágenes codificadas por entropía datos”.

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 primero identifica el grupo de códigos de prefijo correspondiente (como se explica en la última sección). Dado el código de prefijo, el píxel se lee y se decodifica de la siguiente manera:

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

La interpretación de S depende de su valor:

1. Si la S < (256)
   1. Usa S como componente verde.
   2. Lee el color rojo del flujo de bits con el código de prefijo #2.
   3. Lee el azul del flujo de bits con el código de prefijo 3.
   4. Lee alfa del flujo 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 del flujo de bits.
   3. Determina la longitud L de la referencia inversa a partir del código de prefijo de longitud y el bits adicionales leídos.
   4. Lee el código de prefijo de distancia del flujo de bits con el código de prefijo 5.
   5. Lee bits adicionales para la distancia desde el flujo 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 el orden de la línea de búsqueda) de la secuencia de píxeles inicial en la posición actual menos 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 colores en ese índice.

7 Estructura general del formato

A continuación, se incluye una vista del formato en Formato Backus-Naur Aumentado (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 (image_width * image_height).

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 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 imagen

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)

La siguiente es una secuencia de ejemplo posible:

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