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

Jyrki Alakuijala, doutorado Google, Inc., 2023-03-09

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 o PNG foram demonstradas, assim como uma compactação 25% mais densa do que pode ser alcançada usando o formato PNG atual.

1 Introdução

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

Neste documento, usamos extensivamente a sintaxe da linguagem de programação C para descrever o fluxo de bits e presumir 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 do número inteiro retornado também são os mais significativos dos dados originais. Assim, a declaração

b = ReadBits(2);

é equivalente com as duas instruções abaixo:

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

Vamos supor que cada componente de cor, ou seja, 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 não assinado 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..24, vermelho nos bits 23..16, verde nos bits 15..8 e azul nos bits 7..0. No entanto, as implementações do formato podem usar outra representação internamente.

De modo geral, uma imagem WebP sem perdas contém dados de cabeçalho, informações de transformação 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 fluxo de bits contêm os dados necessários para aplicar as respectivas transformações inversas.

2 Nomenclatura

ARGB

Um valor de pixel composto por valores alfa, vermelho, verde e azul.

Imagem ARGB

Uma matriz bidimensional contendo 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 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 de subresolução bidimensional indicando qual codificação de entropia precisa ser usados em um respectivo quadrado na imagem, ou seja, cada pixel é um meta .

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 metaprefixo

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 de 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, que codifica alguns bits do número inteiro usando um código de entropia e codifica os bits restantes em bruto. Isso permite que as descrições dos códigos de entropia permaneçam relativamente pequenas mesmo o intervalo de símbolos é grande.

ordem de linhas de verificaçã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 for concluída, 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 little-endian de 32 bits do número de bytes no stream 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 largura e altura da imagem limita o tamanho máximo de uma imagem WebP sem perdas a 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 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 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 indica presença de uma transformação. Cada transformação pode ser usada apenas 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 minimização de 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, vamos descrever a transformação de dados para diferentes tipos.

4.1 Transformação do Preditor

A transformação do preditor pode ser usada para reduzir a entropia, aproveitando o fato de 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 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 de uma 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 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 bloco, transform_width, é usado na indexação bidimensional. Para um pixel (x, y), é possível computar o respectivo bloco de filtro endereço por:

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 a partir de 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. 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.

Average2 é definido da seguinte maneira para cada componente ARGB:

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

O Predictor de seleção é 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 uma transformação de preditor, independente do modo [0..13] para esses pixels, o valor previsto para o pixel superior esquerdo da imagem é 0xff000000, todos os pixels na linha de cima são pixels L e todos os pixels na coluna mais à esquerda são pixels T.

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 cores

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) 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.

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 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 a transformação de cor. A transformação de cor inversa é apenas a adição dessas diferenças.

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 com sinal que representa uma Número de ponto fixo 3,5 e um canal de cores RGB de 8 bits assinado (c) [-128..127] e é definida 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 representação assinada de 8 bits um (int8) é necessário 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 'cte' ColorTransformElement é tratado como um pixel em uma imagem de subresolução com componente Alfa 255, componente vermelho cte.red_to_blue, componente verde cte.green_to_blue e 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 de 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 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, 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 um 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 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 do limite (256), será criada uma matriz das ARGB, que são usados para substituir os valores de pixel pelos índice correspondente: o canal verde dos pixels são substituídos pelo índice, todos os valores alfa são definidos como 255 e todos os valores vermelhos e azuis como 0.

Os dados de transformação contêm o tamanho da tabela de cores e as entradas na tabela. 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 formato de armazenamento de imagens. A tabela de cores pode ser lida em uma imagem, sem o cabeçalho RIFF, o tamanho da imagem e as transformações, considerando 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 adicionando os valores de componente 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) com os valores reais da tabela de cores. A indexação é feito 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 precisa 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. O agrupamento 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 ao código de entropia, mas só pode ser usado quando há 16 valores únicos ou menos.

O 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 há pixels o agrupamento 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 ≡ 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 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 para os bits mais significativos do valor verde em x / 4.
• width_bits = 3: para cada valor x, em que x ↳ 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 é subamosada 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 Papéis 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 de meta (consulte "Decodificação de códigos de prefixo de meta").
3. Imagem do predictor: armazena os metadados da transformação do predictor (consulte "Transformação do 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.

A imagem é dividida primeiro em um conjunto de blocos de tamanho fixo (normalmente blocos 16x16). 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.

Motivação: armazenar um código de entropia gera custos. 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 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 de cache de cores: uso de um código hash multiplicativo curto (cache de cores) índice) de uma cor vista recentemente.

As subseções a seguir descrevem cada um deles 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 para trás são tuplas de comprimento e código de distância:

• 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 pixel visto anteriormente, 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. 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 melhor 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 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

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 pixelado.

Os códigos de distância maiores que 120 indicam a distância em pixels na ordem da linha de varredura, com 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 é composta por 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 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 deslocamento de pixel vizinhos (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.

Motivação: dessa forma, as cores usadas recentemente podem ser referenciadas de maneira mais eficiente do que emitindo-as 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 indica se o cache de cores é usado. Se esse bit for 0, nenhum código de cache de cores. e não são transmitidos no código de prefixo que decodifica o verde e os códigos de prefixo de comprimento. No entanto, se esse bit for 1, o tamanho do cache de cor 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]. Os 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 um ARGB cor As cores são pesquisadas por indexação com (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Apenas uma pesquisa é feita em um cache de cores. Não há resolução de conflitos.

No início da decodificação ou codificação de uma imagem, todas as entradas em 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 inserindo cada pixel, seja produzido por referência reversa ou como literais, no cache na ordem em que aparecem no stream.

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.

Mais especificamente, o formato usa a codificação de prefixo de variante espacial. Em outras palavras diferentes, diferentes blocos da imagem podem usar diferentes entropias e códigos.

Justificativa: áreas diferentes da imagem podem ter características distintas. Portanto, permitir o uso de diferentes códigos de entropia proporciona mais flexibilidade uma compressão potencialmente melhor.

6.2 Detalhes

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

1. Decodificar e criar os códigos de prefixo.
2. Códigos de prefixo 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 1: usado para canal verde, comprimento de referência para trás e cache de cores.
• Códigos de prefixo 2, 3 e 4: usado para canais vermelho, azul e Alfa. respectivamente.
• Código de prefixo 5: usado para a distância de referência para trás.

A partir de agora, vamos chamar esse conjunto de grupo de prefixo de código.

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, ele será um código de comprimento de código normal.

Em ambos os casos, pode haver comprimentos de código não usados 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 nó de folha só é considerada uma árvore binária completa e pode ser codificada usando o método código de comprimento do código 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 simples de comprimento de código

Esta variante é usada no caso especial em que há apenas um ou dois símbolos de prefixo o 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;

Confira a seguir os valores dos símbolos.

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 não são eficientes.

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 azul podem ficar vazios se todos os pixels no mesmo código de prefixo de meta forem produzidos usando o cache de cores. No entanto, esse caso não precisa de tratamento especial, porque 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 de código do código de prefixo cabem em 8 bits e são lidos da seguinte forma. 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 dos code_length_code_lengths (de acordo com a ordem 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 fluxo de bits será inválido.

Uma tabela de prefixos é criada a partir de code_length_code_lengths e usada para leitura a max_symbol tamanhos de código.

• 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 for emitido, o valor 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 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ó 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. Os códigos de prefixo de meta são índices que identificam quais códigos de prefixo usar em diferentes partes da imagem.

Os códigos de prefixo de meta podem ser usados somente quando a imagem é usada na função 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 igual a 1, a imagem usa vários códigos de prefixo de 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 três primeiros 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 de largura prefix_image_width e altura prefix_image_height.

Interpretação dos códigos de prefixo de 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 na imagem 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 receber os códigos de prefixo correspondentes para uso 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 (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 o grupo de código 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 for menor que 256
   1. Use S como componente verde.
   2. Leia o vermelho do fluxo de bits usando o código de prefixo 2.
   3. Leia o azul do bitstream usando o código de prefixo 3.
   4. Leia 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. Copia pixels L (na ordem de linhas de varredura) da sequência de pixels a partir da posição atual menos pixels D.
3. Se S >= 256 + 24
   1. Use S - (256 + 24) como o índice no cache de cores.
   2. Consiga a cor ARGB do cache de cores desse índice.

7 Estrutura geral do formato

Abaixo está 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 5 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)

Veja a seguir 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