Especificação para fluxo de bits sem perda do WebP

Jyrki Alakuijala, doutorado Google LLC, 09/03/2023

Resumo

WebP sem perda é um formato de imagem para a compactação sem perdas de imagens ARGB. O formato sem perdas armazena e restaura os valores de pixel exatamente, incluindo os valores de cor para pixels totalmente transparentes. Um algoritmo universal para sequencial compactação de dados (LZ77), codificação de prefixo e cache de cores são usados para a compactação dos dados em massa. Velocidades de decodificação mais rápidas que PNG bem como uma compressão 25% mais densa do que pode ser alcançada PNG de hoje.

1 Introdução

Este documento descreve a representação de dados compactada de um WebP sem perda imagem. Ele é uma referência detalhada para o codificador sem perdas WebP e decodificador.

Neste documento, usamos extensivamente a sintaxe da linguagem de programação C para descrever o bitstream e pressupõe a existência de uma função para ler bits, ReadBits(n): Os bytes são lidos na ordem natural do stream que contém e os bits de cada byte são lidos na ordem de bits menos significativos. Quando vários bits são lidos ao mesmo tempo, o número inteiro é construído a partir do os dados originais na ordem original. Os bits mais significativos da resposta retornada número inteiro também são os bits mais significativos dos dados originais. Assim, o declaração

b = ReadBits(2);

é equivalente com as duas instruções abaixo:

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

Presumimos que cada componente de cor, ou seja, alfa, vermelho, azul e verde, é representada usando um byte de 8 bits. Definimos o tipo correspondente como uint8. Um pixel ARGB inteiro é representado por um tipo chamado uint32, que é um número inteiro não assinado composto por 32 bits. No código que mostra o comportamento transformações, esses valores são codificados nos seguintes bits: alfa em bits 31 a 24, vermelho nos bits 23 a 16, verde nos bits 15 a 8 e azul nos bits 7 a 0; No entanto, implementações do formato são livres para usar outra representação internamente.

De modo geral, uma imagem WebP sem perda contém dados de cabeçalho, transforma informações e dados reais da imagem. Os cabeçalhos contêm a largura e a altura da imagem. Um WebP sem perdas pode passar por quatro tipos diferentes de transformações antes de ser é codificada pela entropia. As informações de transformação no bitstream contêm os dados necessárias para aplicar as respectivas transformações inversas.

2 Nomenclatura

ARGB

Um valor de pixel que consiste em valores Alfa, vermelho, verde e azul.

Imagem ARGB

Uma matriz bidimensional que contém pixels ARGB.

cache de cores

Uma pequena matriz com hash para armazenar cores usadas recentemente e poder recuperá-las com códigos mais curtos.

imagem de indexação de cores

Uma imagem unidimensional de cores que pode ser indexada usando um número inteiro pequeno (até 256 no WebP sem perdas).

imagem de transformação de cor

Uma imagem de subresolução bidimensional contendo dados sobre correlações de componentes de cor.

mapeamento de distância

Altera as distâncias do LZ77 para ter os menores valores de pixels em proximidade bidimensional.

imagem de entropia

Uma imagem bidimensional de subresolução indicando qual codificação de entropia deve ser usada em um quadrado correspondente na imagem, ou seja, cada pixel é um código de metaprefixo.

LZ77

Um algoritmo de compactação de janela deslizante baseado em dicionário que emite símbolos do passado ou os descreve como sequências de símbolos do passado.

código de prefixo meta

Um número inteiro pequeno (até 16 bits) que indexa um elemento na tabela de metaprefixos.

imagem do preditor

Uma imagem de subresolução bidimensional que indica qual preditor espacial é usada para um quadrado específico na imagem.

código do prefixo

Uma forma clássica de fazer codificação de entropia em que um número menor de bits é usado para códigos mais frequentes.

codificação de prefixo

Uma forma de codificar números inteiros maiores com entropia, que codifica alguns bits do número inteiro usando um código de entropia e codifica os bits restantes brutos. Isso permite que as descrições dos códigos de entropia permaneçam relativamente pequenas mesmo o intervalo de símbolos é grande.

ordem de digitalização

Uma ordem de processamento de pixels (da esquerda para a direita e de cima para baixo), começando a partir do pixel no canto superior esquerdo. Quando uma linha estiver preenchida, continue na coluna esquerda da próxima linha.

3 Cabeçalho RIFF

O início do cabeçalho tem o contêiner RIFF. Ele consiste nos seguintes 21 bytes:

1. String "RIFF".
2. Um valor small-endian de 32 bits do comprimento do bloco, que é o tamanho total do bloco controlado pelo cabeçalho RIFF. Normalmente, isso é igual ao tamanho do payload (tamanho do arquivo menos 8 bytes: 4 bytes para o identificador "RIFF" e 4 bytes para armazenar o valor).
3. String "WEBP" (nome do contêiner RIFF).
4. String "VP8L" (FourCC para dados de imagem codificados sem perdas).
5. Um valor small-endian de 32 bits do número de bytes no fluxo sem perdas.
6. assinatura de 1 byte 0x2f.

Os primeiros 28 bits do bitstream especificam a largura e a altura da imagem. A largura e a altura são decodificadas como números inteiros de 14 bits da seguinte maneira:

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

A precisão de 14 bits para a largura e a altura da imagem limita o tamanho máximo de um Imagem WebP sem perda para 16384✕16384 pixels.

O bit alpha_is_used é apenas uma dica e não deve afetar a decodificação. Ele deveria ser definido como 0 quando todos os valores alfa forem 255 na imagem; caso contrário, como 1.

int alpha_is_used = ReadBits(1);

O version_number é um código de 3 bits que deve ser definido como 0. Qualquer outro valor deve ser tratado como um erro.

int version_number = ReadBits(3);

4 transformações

As transformações são manipulações reversíveis dos dados de imagem que podem reduzir a entropia simbólica restante ao modelar correlações espaciais e de cores. Eles podem tornar a compactação final mais densa.

Uma imagem pode passar por quatro tipos de transformações. Um bit 1 indica a presença de uma transformação. Cada transformação só pode ser usada uma vez. O as transformações são usadas apenas para a imagem ARGB de nível principal. as imagens em sub-resolução (imagem de transformação de cor, imagem de entropia e imagem de previsão) não têm transformações, nem mesmo o bit 0 que indica o fim das transformações.

Normalmente, um codificador usa essas transformações para reduzir a entropia de Shannon na imagem residual. Além disso, os dados de transformação podem ser decididos com base na entropia e minimização de vulnerabilidades.

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

// Decode actual image data (Section 5).

Se houver uma transformação, os próximos dois bits especificarão o tipo de transformação. Há quatro tipos de transformações.

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

O tipo de transformação é seguido pelos dados de transformação. Os dados de transformação contêm as informações necessárias para aplicar a transformação inversa e depende da o tipo de transformação. As transformações inversas são aplicadas na ordem inversa, eles são lidos no bitstream, ou seja, o último primeiro.

Em seguida, descrevemos os dados de transformação para diferentes tipos.

4.1 Transformação do Preditor

A transformação do preditor pode ser usada para reduzir a entropia explorando o fato que os pixels vizinhos geralmente são correlacionados. Na transformação do preditor, o valor do pixel atual é previsto a partir dos pixels já decodificados (na ordem de varredura de linha) e apenas o valor residual (real - previsto) é codificado. O verde de um pixel define qual dos 14 preditores é usado em um bloco específico da imagem ARGB. O modo de previsão determina o tipo previsão usar. Dividimos a imagem em quadrados, e todos os pixels em um quadrado usam o mesmo modo de previsão.

Os três primeiros bits de dados de previsão definem a largura e a altura do bloco em 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);

Os dados de transformação contêm o modo de previsão para cada bloco da imagem. Ela é uma imagem de subresolução em que o componente verde de um pixel define qual dos os 14 preditores são usados para todos os block_width * block_height pixels dentro um bloco específico da imagem ARGB. Essa imagem de subresolução é codificada usando as mesmas técnicas descritas no Capítulo 5.

O número de colunas de bloco, transform_width, é usado em blocos indexação. Para um pixel (x, y), é possível calcular o endereço do bloco de filtro respectivo da seguinte maneira:

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

Há 14 modos de previsão diferentes. Em cada modo de previsão, o estado o valor do pixel é previsto a partir de um ou mais pixels vizinhos cujos valores são já conhece.

Escolhemos os pixels vizinhos (TL, T, TR e L) do pixel atual (P) como segue:

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

em que TL significa canto superior esquerdo, T significa parte superior, TR significa canto superior direito e L significa esquerda. Em para prever um valor de P, todos os pixels O, TL, T, TR e L já processado e o pixel P e todos os X pixels são desconhecidos.

Dados os pixels vizinhos anteriores, os diferentes modos de previsão são definido da seguinte maneira.

Modo	Valor previsto de cada canal do pixel atual
0	0xff000000 (representa cor preta sólida em ARGB)
1	L
2	T
3	TR
4	líder de equipe
5	Média2(Média2(L, TR), T)
6	Average2(L, TL)
7	Média2(L, T)
8	Média2(TL, T)
9	Média2(T, TR)
10	Média2(Média2(L, TL), Média2(T, TR))
11	Select(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

Average2 é definido da seguinte maneira para cada componente ARGB:

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

O "Selecionar preditor" é definido da seguinte maneira:

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

As funções ClampAddSubtractFull e ClampAddSubtractHalf são executadas para cada componente ARGB da seguinte maneira:

// 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);
}

Há regras especiais de processamento para alguns pixels de borda. Se houver preditor, independentemente do modo [0..13] desses pixels, a o valor previsto para o pixel no topo à esquerda da imagem é 0xff000000, tudo na linha superior são L-pixel, e todos os pixels na coluna mais à esquerda são T-pixel.

Referenciar o pixel TR para pixels na coluna mais à direita é excepcional. Os pixels na coluna mais à direita são previstos com o uso dos modos [0..13], assim como os pixels que não estão na borda, e sim como o pixel mais à esquerda na a mesma linha do pixel atual é usada como o pixel TR.

O valor final do pixel é obtido pela soma de cada canal do valor previsto ao 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 Transformação de cor

O objetivo da transformação de cor é decorar os valores de R, G e B de cada pixelado. A transformação de cor mantém o valor verde (G), transforma o valor vermelho (R) com base no valor verde e transforma o valor azul (B) com base no valor verde e depois no valor vermelho.

Como no caso da transformação do preditor, primeiro a imagem é dividida em blocos e o mesmo modo de transformação é usado para todos os pixels de um bloco. Para em cada bloco, há três tipos de elementos de transformação de cor.

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

A transformação de cor real é feita definindo um delta de transformação de cor. O o delta de transformação de cor depende de ColorTransformElement, que é o mesmo para todos os pixels em um bloco específico. O delta é subtraído durante de cor. Então, a transformação de cor inversa está apenas adicionando esses deltas.

A função de transformação de cores é definida da seguinte maneira:

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 é calculado usando um número inteiro de 8 bits assinado que representa um número de ponto fixo 3,5 e um canal de cor RGB de 8 bits assinado (c) [-128..127] e é definido da seguinte maneira:

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

Uma conversão da representação não assinada de 8 bits (uint8) para a assinada de 8 bits (int8) é necessária antes de chamar ColorTransformDelta(). O valor assinado precisa ser interpretado como um número de complemento de dois de 8 bits (ou seja, o intervalo uint8 [128..255] é mapeado para o intervalo [-128..-1] do valor int8 convertido).

A multiplicação precisa ser feita usando mais precisão (com pelo menos 16 bits de precisão). A propriedade de extensão de sinal da operação de deslocamento não importa aqui. Apenas os 8 bits mais baixos são usados do resultado e, nesses bits, a extensão de sinal e o deslocamento sem sinal são consistentes entre si.

Agora descrevemos o conteúdo dos dados de transformação de cores para que a decodificação possa aplicar a cor inversa se transforma e recupera os valores originais de vermelho e azul. O os primeiros três bits dos dados de transformação de cor contêm a largura e a altura da bloco de imagem em número de bits, assim como a transformação do preditor:

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

A parte restante dos dados de transformação de cor contém instâncias ColorTransformElement, correspondentes a cada bloco da imagem. Cada ColorTransformElement 'cte' é tratado como um pixel em uma imagem de subresolução em que o componente Alfa é 255, o componente vermelho é cte.red_to_blue, o verde o componente é cte.green_to_blue e o componente azul é cte.green_to_red.

Durante a decodificação, as instâncias ColorTransformElement dos blocos são decodificadas e a transformação de cor inversa é aplicada aos valores ARGB dos pixels. Conforme a transformação de cor inversa apenas adiciona ColorTransformElement aos canais vermelho e azul. Os canais Alfa e Verde são deixados como estão.

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 Subtrair a transformação verde

A transformação de subtração verde subtrai valores verdes dos valores vermelhos e azuis de cada pixel. Quando essa transformação está presente, o decodificador precisa adicionar o verde aos valores vermelho e azul. Não há dados associados a este transformam. O decodificador aplica a transformação inversa da seguinte maneira:

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

Essa transformação é redundante, já que pode ser modelada usando a transformação de cor, mas como não há dados adicionais aqui, a transformação de subtração verde pode ser codificada usando menos bits do que uma transformação de cor totalmente desenvolvida.

4.4 Transformação de indexação de cores

Se não houver muitos valores únicos de pixels, pode ser mais eficiente criar uma matriz de índice de cores e substituir os valores de pixel pelos índices da matriz. A cor transformação de indexação faz isso. No contexto do WebP sem perdas, especificamente, não a chamamos de transformação de paleta, porque uma transformação semelhante existe um conceito dinâmico na codificação sem perdas do WebP: cache de cores.)

A transformação de indexação de cores verifica o número de valores ARGB exclusivos no imagem. Se esse número estiver abaixo de um limite (256), ele vai criar uma matriz desses valores ARGB, que será usada para substituir os valores de pixel pelo índice correspondente: o canal verde dos pixels é substituído pelo índice, todos os valores Alfa são definidos como 255 e todos os valores vermelho e azul são definidos como 0.

Os dados da transformação contêm o tamanho da tabela de cores e as entradas na tabela. O decodificador lê os dados da transformação de indexação de cores da seguinte maneira:

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

A tabela de cores é armazenada usando o próprio formato de armazenamento de imagens. A tabela de cores pode ser obtido lendo uma imagem, sem o cabeçalho RIFF, o tamanho da imagem e transformações, supondo a altura de 1 pixel e a largura de color_table_size. A tabela de cores sempre é codificada por subtração para reduzir a entropia da imagem. Os deltas de cores da paleta normalmente contêm muito menos entropia do que as cores o que resulta em economias significativas para imagens menores. Na decodificação, cada cor final na tabela de cores pode ser obtida pela adição da valores de componentes de cor por cada componente ARGB separadamente e armazenar os valores 8 bits significativos do resultado.

A transformação inversa para a imagem é simplesmente substituir os valores de pixel (que são índices da tabela de cores) com os valores reais da tabela de cores. A indexação é feita com base no componente verde da cor ARGB.

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

Se o índice for igual ou maior que color_table_size, o valor da cor a rgb deve ser definido como 0x00000000 (preto transparente).

Quando a tabela de cores é pequena (igual ou menor que 16 cores), diversos pixels são agrupadas em um único pixel. O pacote de pixels contém vários pacotes (2, 4 ou 8) pixels em um único pixel, reduzindo a largura da imagem, respectivamente. do Pixel o agrupamento permite uma codificação de entropia de distribuição conjunta mais eficiente em pixels vizinhos e dá alguns benefícios do tipo codificação aritmética ao código de entropia, mas só pode ser usado quando há 16 ou menos valores únicos.

color_table_size especifica quantos pixels são combinados:

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 tem um valor de 0, 1, 2 ou 3. O valor 0 indica que não há pixels o empacotamento da imagem será feito. Um valor de 1 indica que dois pixels são combinados, e cada pixel tem um intervalo de [0..15]. Um valor de 2 indica que quatro pixels são combinados, e cada pixel tem um intervalo de [0 a 3]. Um valor de 3 indica que oito pixels são combinados e cada pixel tem um intervalo de [0..1], ou seja, um valor binário.

Os valores são compactados no componente verde da seguinte maneira:

• width_bits = 1: para cada valor x, em que x Payment 0 (mod 2), um verde em x é posicionado nos quatro bits menos significativos da um valor de verde em x / 2, e um valor de verde em x + 1 é posicionado na 4 bits mais significativos do valor verde a x / 2.
• width_bits = 2: para cada valor de x, em que x ≡ 0 (mod 4), um verde em x é posicionado nos dois bits menos significativos da o valor de verde em x / 4 e os valores de verde em x + 1 a x + 3 estão posicionados em para os bits mais significativos do valor verde em x / 4.
• width_bits = 3: para cada valor x, em que x Payment 0 (mod 8), um verde o valor em x é posicionado no bit menos significativo do verde em x / 8, e os valores de verde em x + 1 a x + 7 são posicionados em ordem aos bits mais significativos do valor verde a x / 8.

Depois de ler essa transformação, image_width é subamostrado por width_bits. Isso afeta o tamanho das transformações subsequentes. O novo tamanho pode ser calculado usando DIV_ROUND_UP, conforme definido anteriormente.

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

5 Dados de imagem

Dados de imagem são uma matriz de valores de pixel em ordem de verificação da linha.

5.1 Funções dos dados de imagem

Usamos dados de imagem em cinco funções diferentes:

1. Imagem ARGB: armazena os pixels reais da imagem.
2. Imagem de entropia: armazena os códigos de prefixo meta (consulte "Decodificação de códigos de prefixo meta").
3. Imagem do Preditor: armazena os metadados da transformação do preditor. Consulte "Transformação Predictor").
4. Imagem de transformação de cor: criada por valores ColorTransformElement (definido em "Transformação de cor") para blocos diferentes da imagem.
5. Imagem de indexação de cores: uma matriz do tamanho de color_table_size (até 256 valores ARGB) que armazenam os metadados para a transformação de indexação de cores (consulte "Transformação de indexação de cores").

5.2 Codificação de dados de imagem

A codificação dos dados de imagem é independente da função.

Primeiro, a imagem é dividida em um conjunto de blocos de tamanho fixo (normalmente 16 x 16 blocos). Cada um desses blocos é modelado usando os próprios códigos de entropia. Além disso, vários blocos podem compartilhar os mesmos códigos de entropia.

Lógica: o armazenamento de um código de entropia incorre em um custo. Esse custo pode ser minimizado se blocos estatisticamente semelhantes compartilharem um código de entropia, armazenando-o apenas uma vez. Por exemplo, um codificador pode agrupar blocos semelhantes usando propriedades estatísticas ou unindo repetidamente um par de clusters selecionados quando reduz a quantidade total de bits necessária para codificar a imagem.

Cada pixel é codificado usando um dos três métodos possíveis:

1. Literais codificados por prefixo: cada canal (verde, vermelho, azul e alfa) é e a entropia é codificada de modo independente.
2. Referência LZ77 inversa: uma sequência de pixels é copiada de outro lugar a imagem.
3. Código do cache de cores: uso de um código hash multiplicativo curto (índice de cache de cores) de uma cor vista recentemente.

As subseções a seguir descrevem cada uma delas em detalhes.

5.2.1 Literais codificados com prefixo

O pixel é armazenado como valores codificados por prefixo de verde, vermelho, azul e alfa (nessa ordem). Consulte a Seção 6.2.3 para detalhes.

5.2.2 LZ77 Referência retroativa

As referências inversas são tuplas de length e distance code:

• O comprimento indica quantos pixels na ordem da linha de leitura serão copiados.
• O código de distância é um número que indica a posição de um objeto de onde os pixels serão copiados. O mapeamento exato é descritas abaixo.

Os valores de comprimento e distância são armazenados usando a codificação de prefixo LZ77.

A codificação de prefixo LZ77 divide grandes valores inteiros em duas partes: o prefixo código e os bits extras. O código do prefixo é armazenado usando um código de entropia, enquanto os bits extras são armazenados como estão (sem código de entropia).

Justificativa: esta abordagem reduz o requisito de armazenamento para a entropia o código-fonte é alterado. Além disso, valores grandes geralmente são raros, portanto bits extras seriam usados para alguns valores na imagem. Assim, essa abordagem resulta em uma melhor geral.

A tabela a seguir indica os códigos de prefixo e bits extras usados para armazenar diferentes intervalos de valores.

Intervalo de valor	Código do prefixo	Bits extras
1	0	0
2	1	0
3	2	0
4	3	0
5 a 6	4	1
7 a 8	5	1
9 a 12	6	2
13..16	7	2
…	...	…
3072..4096	23	10
…	...	…
524289..786432	38	18
786433..1048576	39	18

O pseudocódigo para obter um valor (comprimento ou distância) do código de prefixo é da segue:

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;

Mapeamento de distância

Conforme observado anteriormente, um código de distância é um número que indica a posição de um visto anteriormente, de onde os pixels serão copiados. Esta subseção define o mapeamento entre um código de distância e a posição de um pixel anterior.

Códigos de distância maiores que 120 indicam a distância em pixels na ordem de leitura das linhas, deslocado em 120.

Os códigos de distância menores [1..120] são especiais e reservados para uma vizinhança próxima do pixel atual. Essa vizinhança é composta por 120 pixels:

• Pixels que estão de 1 a 7 linhas acima do pixel atual e com até oito colunas para a esquerda ou até sete colunas à direita do pixel atual. [Total tais pixels = 7 * (8 + 1 + 7) = 112].
• Pixels que estão na mesma linha que o pixel atual e que têm até 8 colunas à esquerda do pixel atual. [8 desses pixels].

O mapeamento entre o código de distância distance_code e o pixel vizinho o deslocamento (xi, yi) é o seguinte:

(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 exemplo, o código de distância 1 indica um deslocamento de (0, 1) para o pixel vizinho, ou seja, o pixel acima do pixel atual (diferença de 0 pixel na direção X e 1 pixel na direção Y). Da mesma forma, o código de distância 3 indica o pixel no canto superior esquerdo.

O decodificador pode converter um código de distância distance_code em um pedido de linha de varredura. dist da seguinte forma:

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

em que distance_map é o mapeamento observado acima e image_width é a largura da imagem em pixels.

5.2.3 Codificação do cache de cores

O cache de cores armazena um conjunto de cores que foram usadas recentemente na imagem.

Justificativa: dessa forma, as cores usadas recentemente podem às vezes ser chamadas de de forma mais eficiente do que emiti-los usando os outros dois métodos (descritos em 5.2.1 e 5.2.2).

Os códigos de cache de cores são armazenados da seguinte forma: Primeiro, há um valor de 1 bit que indica se o cache de cores é usado. Se esse bit for 0, nenhum código de cache de cor será transmitido no código de prefixo que decodifica os símbolos verdes e os códigos de prefixo de comprimento. No entanto, se esse bit for 1, o cache de cores tamanho é a leitura a seguir:

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

color_cache_code_bits define o tamanho do cache de cores (1 << color_cache_code_bits). O intervalo de valores permitidos para color_cache_code_bits é [1..11]. Decodificadores compatíveis devem indicar um bitstream corrompido de outros valores.

Um cache de cores é uma matriz de tamanho color_cache_size. Cada entrada armazena um ARGB cor As cores são pesquisadas indexando-as por (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Apenas uma consulta é feita em um cache de cores. não há e resolução de conflitos.

No início da decodificação ou codificação de uma imagem, todas as entradas de todas as cores valores de cache são definidos como zero. O código do cache de cores é convertido para essa cor em tempo de decodificação. O estado do cache de cores é mantido ao inserir cada pixel, seja produzido por referência reversa ou como literais, no cache na ordem em que aparecem no fluxo.

6 Código de entropia

6.1 Visão geral

A maior parte dos dados é codificada usando um código de prefixo canônico. Portanto, os códigos são transmitidos enviando os comprimentos de código de prefixo, conforme ao contrário dos códigos de prefixo reais.

Em particular, o formato usa a codificação espacial de prefixos de variantes. Em outras palavras diferentes, diferentes blocos da imagem podem usar diferentes entropias e códigos personalizados.

Justificativa: áreas diferentes da imagem podem ter características distintas. Portanto, permitir que eles usem diferentes códigos de entropia oferece mais flexibilidade e possivelmente uma melhor compactação.

6.2 Detalhes

Os dados da imagem codificada consistem em várias partes:

1. Decodificar e criar os códigos de prefixo.
2. Códigos de prefixo de meta.
3. Dados de imagem codificados por entropia.

Para qualquer pixel (x, y), há um conjunto de cinco códigos de prefixo associados com reimplantá-lo. Estes códigos são (na ordem do bitstream):

• Código de prefixo no 1: usado para canal verde, comprimento de referência anterior e cache de cores.
• Códigos de prefixo 2, 3 e 4: usado para canais vermelho, azul e Alfa. respectivamente.
• Código de prefixo no 5: usado para a distância de referência anterior.

A partir de agora, nos referimos a esse conjunto como um grupo de códigos de prefixo.

6.2.1 Decodificação e criação dos códigos de prefixo

Esta seção descreve como ler os comprimentos de código de prefixo do bitstream.

Os comprimentos de código de prefixo podem ser codificados de duas maneiras. O método usado é especificado por um valor de 1 bit.

• Se esse bit for 1, é um código de comprimento de código simples.
• Se esse bit for 0, é um código de comprimento de código normal.

Em ambos os casos, pode haver comprimentos de código não utilizados que ainda fazem parte da riacho. Isso pode ser ineficiente, mas é permitido pelo formato. A árvore descrita precisa ser uma árvore binária completa. Um único nó de folha é considerado uma árvore binária completa e pode ser codificado usando o código de comprimento de código simples ou o código de comprimento de código normal. Ao codificar uma única folha nó usando o código de comprimento de código normal, todos exceto um comprimento de código são zeros, e o valor do nó de folha única é marcado com o comprimento de 1, mesmo quando nenhum Os bits são consumidos quando a árvore de nós de folha única é usada.

Código de tamanho de código simples

Essa variante é usada no caso especial em que apenas um ou dois símbolos de prefixo estão no intervalo [0..255] com comprimento de código 1. Todos os outros comprimentos de código de prefixo zeros implicitamente.

O primeiro bit indica o número de símbolos:

int num_symbols = ReadBits(1) + 1;

Veja a seguir os valores de símbolo.

O primeiro símbolo é codificado usando 1 ou 8 bits, dependendo do valor do is_first_8bits: O intervalo é [0..1] ou [0..255], respectivamente. A segunda , se presente, é sempre considerado como estando no intervalo [0..255] e codificado usando 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;
}

Os dois símbolos precisam ser diferentes. Símbolos duplicados são permitidos, mas ineficiente.

Observação:outro caso especial é quando todos os comprimentos de código de prefixo são zeros (um código de prefixo vazio). Por exemplo, um código de prefixo para distância pode ficar vazio se não há referências inversas. Da mesma forma, os códigos de prefixo para alfa, vermelho e O azul poderá ficar vazio se todos os pixels dentro do mesmo código de prefixo meta forem produzidos usando o cache de cores. No entanto, esse caso não precisa de tratamento especial, já que códigos de prefixo vazios podem ser codificados como aqueles que contêm um único símbolo 0.

Código de comprimento de código normal

Os comprimentos do código de prefixo cabem em 8 bits e são lidos da seguinte maneira. Primeiro, num_code_lengths especifica o número de comprimentos de código.

int num_code_lengths = 4 + ReadBits(4);

Os comprimentos de código são codificados usando códigos de prefixo. Os comprimentos de código de nível inferior, code_length_code_lengths, precisam ser lidos primeiro. O restante desses code_length_code_lengths (de acordo com o pedido em kCodeLengthCodeOrder) são zeros.

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

Em seguida, se for ReadBits(1) == 0, o número máximo de símbolos de leitura diferentes (max_symbol) para cada tipo de símbolo (A, R, G, B e distância) é definido como tamanho do alfabeto:

• Canal G: 256 + 24 + color_cache_size
• Outros literais (A, R e B): 256
• Código de distância: 40

Caso contrário, será definido como:

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

Se max_symbol for maior que o tamanho do alfabeto para o tipo de símbolo, o O bitstream é inválido.

Uma tabela de prefixos é criada a partir de code_length_code_lengths e usada para ler até comprimentos de código max_symbol.

• O código [0..15] indica comprimentos de código literal.
  • O valor 0 significa que nenhum símbolo foi codificado.
  • Os valores [1..15] indicam o comprimento em bits do respectivo código.
• O código 16 repete o valor anterior diferente de zero [3..6] vezes, ou seja, 3 + ReadBits(2) vez. Se o código 16 for usado antes de um valor diferente de zero ser emitido, um valor de 8 será repetido.
• O código 17 emite uma sequência de zeros de comprimento [3..10], ou seja, 3 + ReadBits(3) vezes.
• O código 18 emite uma sequência de zeros de comprimento [11..138], ou seja, 11 + ReadBits(7) vezes.

Depois que os comprimentos de código são lidos, um código de prefixo para cada tipo de símbolo (A, R, G, B e distância) é formada usando seus respectivos tamanhos de alfabeto.

O Código de comprimento de código normal deve codificar uma árvore de decisão completa, ou seja, a soma de 2 ^ (-length) para todos os códigos diferentes de zero precisa ser exatamente um. No entanto, há uma exceção a essa regra, a árvore de nó de folha única, em que o valor do nó de folha é marcado com o valor 1 e os outros valores são 0s.

6.2.2 Decodificação de códigos de prefixo de meta

Como observado anteriormente, o formato permite o uso de diferentes códigos de prefixo para diferentes blocos da imagem. Códigos de prefixo meta são índices que identificam quais códigos de prefixo para usar em diferentes partes da imagem.

Os códigos de prefixo meta podem ser usados somente quando a imagem está sendo usada no role de uma imagem ARGB.

Existem duas possibilidades para os códigos de prefixo meta, indicadas por um caractere :

• Se esse bit for zero, haverá apenas um código de prefixo meta usado em todos os lugares em a imagem. Não há mais dados armazenados.
• Se esse bit for um, a imagem usará vários códigos de prefixo meta. Essas metas são armazenados como uma imagem de entropia (descrita abaixo).

Os componentes vermelho e verde de um pixel definem um código de metaprefixo de 16 bits usado em um bloco específico da imagem ARGB.

Imagem de entropia

A imagem de entropia define quais códigos de prefixo são usados em diferentes partes da imagem.

Os primeiros três bits contêm o valor prefix_bits. As dimensões da entropia imagem são derivados 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);

em que DIV_ROUND_UP é definido anteriormente.

Os próximos bits contêm uma imagem de entropia com largura prefix_image_width e altura prefix_image_height.

Interpretação de códigos de prefixo meta

O número de grupos de códigos de prefixo na imagem ARGB pode ser obtido encontrando o maior código de prefixo meta da imagem de entropia:

int num_prefix_groups = max(entropy image) + 1;

em que max(entropy image) indica o maior código de prefixo armazenado no de entropia.

Como cada grupo contém cinco códigos de prefixo, o número total de é:

int num_prefix_codes = 5 * num_prefix_groups;

Dado um pixel (x, y) na imagem ARGB, podemos obter o prefixo correspondente a serem usados da seguinte forma:

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];

em que assumimos a existência da estrutura PrefixCodeGroup, que representa um conjunto de cinco códigos de prefixo. Além disso, prefix_code_groups é uma matriz de PrefixCodeGroup (do tamanho num_prefix_groups).

Em seguida, o decodificador usa o grupo de códigos de prefixo prefix_group para decodificar o pixel. (x, y), conforme explicado em "Decodificação de imagem codificada por entropia Dados.

6.2.3 Como decodificar dados de imagem codificados por entropia

Para a posição atual (x, y) na imagem, o decodificador primeiro identifica a grupo de códigos de prefixo correspondente (conforme explicado na última seção). Considerando do grupo de códigos de prefixo, o pixel é lido e decodificado da seguinte maneira.

Em seguida, leia o símbolo S do fluxo de bits usando o código de prefixo 1. Observe que S é qualquer número inteiro no intervalo de 0 a (256 + 24 + color_cache_size- 1).

A interpretação de S depende do valor:

1. Se S < 256
   1. Use S como o componente verde.
   2. Leia em vermelho o bitstream usando o código de prefixo #2.
   3. Leia o azul do fluxo de bits usando o código de prefixo 3.
   4. Leia a versão Alfa do bitstream usando o código de prefixo #4.
2. Se S >= 256 & S < 256 + 24
   1. Use S - 256 como um código de prefixo de comprimento.
   2. Leia bits extras para o comprimento do bitstream.
   3. Determine o comprimento L de referência anterior a partir do código de prefixo de comprimento e o bits extras lidos.
   4. Leia o código do prefixo de distância do bitstream usando o código de prefixo #5.
   5. Leia bits extras para a distância do bitstream.
   6. Determinar a distância de referência inversa D a partir do código de prefixo da distância e os bits extras lidos.
   7. Copiar L pixels (na ordem da linha de digitalização) da sequência de pixels começando na posição atual menos D pixels.
3. Se S >= 256 + 24
   1. Use S - (256 + 24) como índice no cache de cores.
   2. Consiga a cor ARGB do cache de cores desse índice.

7 Estrutura geral do formato

Confira abaixo uma visualização do formato na forma aumentada de Backus-Naur (ABNF, na sigla em inglês) RFC 5234 RFC 7405. Ele não abrange todos os detalhes. Fim da imagem (EOI) é codificado apenas implicitamente no número de pixels (image_width * image_height).

*element significa que element pode ser repetido 0 ou mais vezes. 5element significa que element é repetido exatamente cinco vezes. %b representa um valor binário.

7.1 Estrutura 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 Estrutura de transformações

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 Estrutura dos dados de imagem

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)

Confira a seguir um exemplo de sequência:

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