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

Jyrki Alakuijala, Ph.D., Google, Inc., 2023-03-09

Resumo

O WebP sem perda é um formato de imagem para compactação sem perda de imagens ARGB. O formato sem perda armazena e restaura os valores de pixel exatamente, incluindo os valores de cor para pixels totalmente transparentes. Um algoritmo universal para compactação de dados sequenciais (LZ77), codificação de prefixo e um cache de cores são usados para compactar os dados em massa. Já foram demonstradas velocidades de decodificação mais rápidas do que o PNG, além de uma compactação 25% mais densa do que a possível com o formato PNG atual.

1 Introdução

Este documento descreve a representação de dados compactados de uma imagem WebP sem perda. Ele foi criado como uma referência detalhada para a implementação do codificador e decodificador sem perda do WebP.

Neste documento, usamos extensivamente a sintaxe da linguagem de programação C para descrever o fluxo de bits e presumimos a existência de uma função para leitura de bits, ReadBits(n). Os bytes são lidos na ordem natural do fluxo que os contém, e os bits de cada byte são lidos na ordem do bit menos significativo primeiro. Quando vários bits são lidos ao mesmo tempo, o número inteiro é construído com base nos dados originais na ordem original. Os bits mais significativos do número inteiro retornado também são os bits mais significativos dos dados originais. Assim, a instrução

b = ReadBits(2);

é equivalente às duas declarações abaixo:

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

Vamos supor que cada componente de cor (alfa, vermelho, azul e verde) seja representado 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 sem sinal composto por 32 bits. No código que mostra o comportamento das transformações, esses valores são codificados nos seguintes bits: alfa nos 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, as implementações do formato podem usar outra representação internamente.

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

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 cores

Uma imagem bidimensional de subresolução que contém dados sobre correlações de componentes de cor.

mapeamento de distância

Muda as distâncias LZ77 para ter os menores valores de pixels na proximidade bidimensional.

imagem de entropia

Uma imagem bidimensional de subresolução que indica qual codificação de entropia deve ser usada em um quadrado respectivo na imagem. Ou seja, cada pixel é um metacódigo de prefixo.

LZ77

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

código de prefixo meta

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

imagem de previsão

Uma imagem bidimensional de subresolução que indica qual preditor espacial é usado para um determinado quadrado na imagem.

código de prefixo

Uma maneira 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 maneira de codificar por entropia números inteiros maiores, 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 quando o intervalo de símbolos é grande.

ordem de varredura de linha

Uma ordem de processamento de pixels (da esquerda para a direita e de cima para baixo), começando pelo pixel superior esquerdo. Quando uma linha for concluída, continue da coluna à esquerda da próxima linha.

3 Cabeçalho RIFF

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

1. String "RIFF".
2. Um valor little-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 em si).
3. String "WEBP" (nome do contêiner RIFF).
4. String "VP8L" (FourCC para dados de imagem codificados sem perda).
5. Um valor little-endian de 32 bits do número de bytes no fluxo sem perdas.
6. Assinatura de 1 byte 0x2f.

Os primeiros 28 bits do fluxo de bits 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 forma:

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

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

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

int alpha_is_used = ReadBits(1);

O version_number é um código de 3 bits que precisa 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 modelando correlações espaciais e de cores. Elas podem tornar a compressã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. As transformações são usadas apenas para a imagem ARGB de nível principal. As imagens de subresoluçã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 minimização da entropia.

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

// Decode actual image data (Section 5).

Se uma transformação estiver presente, os dois bits seguintes vão especificar 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 dependem do tipo de transformação. As transformações inversas são aplicadas na ordem inversa em que são lidas do fluxo de bits, ou seja, a última primeiro.

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

4.1 Transformação de preditor

A transformação de previsão pode ser usada para reduzir a entropia aproveitando o fato de que pixels vizinhos geralmente são correlacionados. Na transformação do preditor, o valor atual do pixel é previsto com base nos pixels já decodificados (na ordem de linha de varredura), e apenas o valor residual (real - previsto) é codificado. O componente 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 de previsão a ser usado. 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. É uma imagem de subresolução em que o componente verde de um pixel define qual dos 14 preditores é usado para todos os pixels block_width * block_height em 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 blocos, transform_width, é usado na indexação bidimensional. Para um pixel (x, y), é possível calcular o endereço do bloco de filtro respectivo da seguinte forma:

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 valor do pixel atual é previsto com base em um ou mais pixels vizinhos cujos valores já são conhecidos.

Escolhemos os pixels vizinhos (TL, T, TR e L) do pixel atual (P) da seguinte forma:

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 superior, TR significa canto superior direito e L significa esquerda. No momento de prever um valor para P, todos os pixels O, TL, T, TR e L já foram processados, e o pixel P e todos os pixels X são desconhecidos.

Considerando os pixels vizinhos anteriores, os diferentes modos de previsão são definidos da seguinte forma.

Average2 é definido da seguinte maneira para cada componente ARGB:

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

O preditor "Select" é 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 realizadas 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 tratamento para alguns pixels de borda. Se houver uma transformação de preditor, independente do modo [0..13] para esses pixels, o valor previsto para o pixel superior esquerdo da imagem será 0xff000000, todos os pixels na linha superior serão L-pixel e todos os pixels na coluna mais à esquerda serão T-pixel.

Abordar o pixel TR para pixels na coluna mais à direita é excepcional. Os pixels na coluna mais à direita são previstos usando os modos [0..13], assim como os pixels que não estão na borda. No entanto, o pixel mais à esquerda na mesma linha do pixel atual é usado como o pixel TR.

O valor final do pixel é obtido adicionando 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 cores é desvincular os valores R, G e B de cada pixel. A transformação de cor mantém o valor verde (G) como está, 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.

Assim como na transformação de previsão, primeiro a imagem é dividida em blocos, e o mesmo modo de transformação é usado para todos os pixels em um bloco. Para 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 delta de transformação de cor depende do ColorTransformElement, que é o mesmo para todos os pixels em um bloco específico. O delta é subtraído durante a transformação de cor. A transformação inversa de cores adiciona esses deltas.

A função de transformação de cor é definida da seguinte forma:

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 com sinal que representa um número de ponto fixo de 3,5 e um canal de cor RGB de 8 bits com sinal (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 com sinal 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 deve ser feita com mais precisão (pelo menos 16 bits). 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, o deslocamento de 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 transformação inversa e recuperar os valores originais de vermelho e azul. Os três primeiros bits dos dados de transformação de cor contêm a largura e a altura do bloco de imagem em número de bits, assim como a transformação de previsão:

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 ColorTransformElement instâncias, correspondentes a cada bloco da imagem. Cada ColorTransformElement 'cte' é tratado como um pixel em uma imagem de subresolução cujo componente alfa é 255, o componente vermelho é cte.red_to_blue, o componente verde é 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 inversa de cores é aplicada aos valores ARGB dos pixels. Como mencionado anteriormente, essa transformação de cor inversa apenas adiciona valores 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 Transformação "Subtrair verde"

A transformação "subtrair verde" subtrai valores verdes dos valores vermelhos e azuis de cada pixel. Quando essa transformação está presente, o decodificador precisa adicionar o valor verde aos valores vermelho e azul. Não há dados associados a essa transformação. 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. No entanto, como não há outros dados aqui, a transformação de subtração de verde pode ser codificada usando menos bits do que uma transformação de cor completa.

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

Se não houver muitos valores de pixel exclusivos, talvez seja mais eficiente criar uma matriz de índice de cores e substituir os valores de pixel pelos índices da matriz. A transformação de indexação de cores faz isso. No contexto do WebP sem perda, não chamamos isso de transformação de paleta porque um conceito semelhante, mas mais dinâmico, existe na codificação WebP sem perda: o cache de cores.

A transformação de indexação de cores verifica o número de valores ARGB exclusivos na 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 como 0.

Os dados de transformação contêm o tamanho da tabela de cores e as entradas nela. O decodificador lê os dados de 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 obtida lendo uma imagem, sem o cabeçalho RIFF, o tamanho da imagem e as transformações, presumindo 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 das cores da paleta geralmente contêm muito menos entropia do que as próprias cores, o que gera uma economia significativa para imagens menores. Na decodificação, cada cor final na tabela de cores pode ser obtida adicionando os valores dos componentes de cor anteriores por cada componente ARGB separadamente e armazenando os 8 bits menos significativos do resultado.

A transformação inversa para a imagem é simplesmente substituir os valores de pixel (que são índices da tabela de cores) pelos 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 ARGB deverá ser definido como 0x00000000 (preto transparente).

Quando a tabela de cores é pequena (igual ou menor que 16 cores), vários pixels são agrupados em um único pixel. O agrupamento de pixels junta vários (2, 4 ou 8) pixels em um único pixel, reduzindo a largura da imagem. A junção de pixels permite uma codificação de entropia de distribuição conjunta mais eficiente de pixels vizinhos e oferece alguns benefícios semelhantes à codificação aritmética para o código de entropia, mas só pode ser usada 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. Um valor de 0 indica que não é necessário agrupar pixels para a imagem. 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..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 agrupados no componente verde da seguinte forma:

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

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

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

5 Dados de imagem

Os dados de imagem são uma matriz de valores de pixels em ordem de linha de varredura.

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 do preditor").
4. Imagem de transformação de cor: criada por valores ColorTransformElement (definidos em "Transformação de cor") para diferentes blocos da imagem.
5. Imagem de indexação de cores: uma matriz do tamanho de color_table_size (até 256 valores ARGB) que armazena os metadados da 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 dela.

Primeiro, a imagem é dividida em um conjunto de blocos de tamanho fixo (normalmente 16 x 16). 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.

Justificativa:armazenar um código de entropia gera um custo. Esse custo pode ser minimizado se blocos estatisticamente semelhantes compartilharem um código de entropia, armazenando esse código apenas uma vez. Por exemplo, um codificador pode encontrar blocos semelhantes agrupando-os usando as propriedades estatísticas ou unindo repetidamente um par de clusters selecionados aleatoriamente quando isso reduz a quantidade geral de bits necessários para codificar a imagem.

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

1. Literais com codificação de prefixo: cada canal (verde, vermelho, azul e alfa) é codificado por entropia de forma independente.
2. Referência de volta do LZ77: uma sequência de pixels é copiada de outro lugar na imagem.
3. Código de cache de cores: usa 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 por prefixo

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

5.2.2 Referência de volta do LZ77

As referências anteriores são tuplas de comprimento e código de distância:

• O comprimento indica quantos pixels na ordem de linha de varredura devem ser copiados.
• O código de distância é um número que indica a posição de um pixel visto anteriormente, de onde os pixels serão copiados. O mapeamento exato é descrito 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 valores inteiros grandes em duas partes: o código de prefixo e os bits extras. O código de prefixo é armazenado usando um código de entropia, enquanto os bits extras são armazenados como estão (sem um código de entropia).

Justificativa: essa abordagem reduz o requisito de armazenamento para o código de entropia. Além disso, valores grandes geralmente são raros, então bits extras seriam usados para muito poucos valores na imagem. Assim, essa abordagem resulta em uma compressão melhor no geral.

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

O pseudocódigo para extrair um valor (comprimento ou distância) do código de prefixo é o seguinte:

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

Como observado anteriormente, um código de distância é um número que indica a posição de um pixel 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 do pixel em ordem de linha de varredura, com um deslocamento de 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 consiste em 120 pixels:

• Pixels que estão de 1 a 7 linhas acima do pixel atual e até 8 colunas à esquerda ou até 7 colunas à direita do pixel atual. [Total such pixels = 7 * (8 + 1 + 7) = 112].
• Pixels que estão na mesma linha do pixel atual e até 8 colunas à esquerda dele. [8 pixels desse tipo].

O mapeamento entre o código de distância distance_code e o deslocamento do pixel vizinho (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 superior esquerdo.

O decodificador pode converter um código de distância distance_code em uma distância de ordem de linha de varredura dist da seguinte maneira:

(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 de cache de cores

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

Justificativa:dessa forma, as cores usadas recentemente podem ser referenciadas com mais eficiência do que emitidas 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, não haverá códigos de cache de cores e eles não serão transmitidos 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 tamanho do cache de cores será lido em seguida:

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 precisam indicar um bitstream corrompido para outros valores.

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

No início da decodificação ou codificação de uma imagem, todas as entradas em todos os valores de cache de cores são definidas como zero. O código do cache de cores é convertido para essa cor no momento da decodificação. O estado do cache de cores é mantido inserindo todos os pixels, sejam eles produzidos por referências anteriores ou como literais, no cache na ordem em que aparecem no fluxo.

6 Código de entropia

6.1 Visão geral

A maioria 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, em vez dos códigos de prefixo reais.

Em especial, o formato usa a codificação de prefixo espacialmente variante. Em outras palavras, diferentes blocos da imagem podem usar códigos de entropia diferentes.

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

6.2 Detalhes

Os dados de imagem codificados consistem em várias partes:

1. Decodificação e criação dos códigos de prefixo.
2. Códigos de prefixo da Meta.
3. Dados de imagem codificados por entropia.

Para qualquer pixel (x, y), há um conjunto de cinco códigos de prefixo associados a ele. Estes códigos estão em ordem de fluxo de bits:

• Prefixo de código nº 1: usado para canal verde, comprimento de referência anterior e cache de cores.
• Códigos de prefixo nº 2, 3 e 4: usados para canais vermelho, azul e alfa, respectivamente.
• Código de prefixo nº 5: usado para distância de referência anterior.

Daqui em diante, vamos nos referir 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 do código de prefixo do fluxo de bits.

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

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

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

Código de comprimento 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 são implicitamente zeros.

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

int num_symbols = ReadBits(1) + 1;

Confira a seguir os valores dos símbolos.

O primeiro símbolo é codificado usando 1 ou 8 bits, dependendo do valor de is_first_8bits. O intervalo é [0..1] ou [0..255], respectivamente. O segundo símbolo, se presente, sempre será considerado 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 ineficientes.

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 houver referências anteriores. Da mesma forma, os códigos de prefixo para alfa, vermelho e azul podem estar vazios se todos os pixels dentro do mesmo código de prefixo de metadados 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 normal

Os comprimentos de código 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 a ordem em kCodeLengthCodeOrder) é zero.

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 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) será definido como o 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, ele é 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 fluxo de bits será inválido.

Uma tabela de prefixos é criada com base em code_length_code_lengths e usada para ler até max_symbol comprimentos de código.

• O código [0..15] indica comprimentos de código literais.
  • O valor 0 significa que nenhum símbolo foi codificado.
  • Os valores [1..15] indicam o comprimento de bits do código respectivo.
• O código 16 repete o valor diferente de zero anterior [3..6] vezes, ou seja, 3 + ReadBits(2) vezes. 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) é formado usando os respectivos tamanhos de alfabeto.

O código de comprimento normal precisa 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ó único, em que o valor do nó folha é marcado com o valor 1 e os outros valores são 0.

6.2.2 Decodificação de códigos de prefixo da Meta

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

Os códigos de prefixo meta podem ser usados somente quando a imagem é usada na função de uma imagem ARGB.

Há duas possibilidades para os códigos de prefixo meta, indicadas por um valor de 1 bit:

• Se esse bit for zero, haverá apenas um código de prefixo meta usado em toda a imagem. Nenhum outro dado é armazenado.
• Se esse bit for um, a imagem usará vários códigos de prefixo de metadados. Esses códigos de prefixo meta são armazenados como uma imagem de entropia (descrita abaixo).

Os componentes vermelho e verde de um pixel definem um código de prefixo meta 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 três primeiros bits contêm o valor prefix_bits. As dimensões da imagem de entropia são derivadas 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 é como definido antes.

Os bits a seguir contêm uma imagem de entropia de largura prefix_image_width e altura prefix_image_height.

Interpretação de códigos de prefixo de metadados

Para saber o número de grupos de códigos de prefixo na imagem ARGB, encontre o maior código de prefixo de metadados na imagem de entropia:

int num_prefix_groups = max(entropy image) + 1;

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

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

int num_prefix_codes = 5 * num_prefix_groups;

Dado um pixel (x, y) na imagem ARGB, podemos extrair os códigos de prefixo correspondentes para serem usados da seguinte maneira:

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 presumimos 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 (de tamanho num_prefix_groups).

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

6.2.3 Decodificação de dados de imagem codificados por entropia

Para a posição atual (x, y) na imagem, o decodificador primeiro identifica o grupo de códigos de prefixo correspondente (conforme explicado na última seção). Dado o grupo 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 nº 1. S é qualquer número inteiro no intervalo de 0 a (256 + 24 + color_cache_size- 1).

A interpretação de S depende do valor dele:

1. Se S < 256
   1. Use S como o componente verde.
   2. Leia o vermelho do fluxo de bits usando o código de prefixo nº 2.
   3. Leia o azul do fluxo de bits usando o código de prefixo nº 3.
   4. Leia o alfa do fluxo de bits usando o código de prefixo nº 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 da referência anterior com base no código de prefixo de comprimento e nos bits extras lidos.
   4. Leia o código de prefixo de distância do fluxo de bits usando o código de prefixo nº 5.
   5. Leia bits extras para a distância do bitstream.
   6. Determine a distância de referência D do código de prefixo de distância e dos bits extras lidos.
   7. Copia L pixels (em ordem de linha de varredura) 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 o índice no cache de cores.
   2. Recebe a cor ARGB do cache de cores nesse índice.

7 Estrutura geral do formato

Confira abaixo uma visão do formato na forma aumentada de Backus-Naur (ABNF) RFC 5234 RFC 7405. Ele não inclui todos os detalhes. O fim da imagem (EOI) é codificado implicitamente no número de pixels (image_width * image_height).

*element significa que element pode ser repetido nenhuma 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 das 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 um exemplo de sequência possível:

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