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 o formato sem perda armazena e restaura exatamente os valores de pixel, incluindo 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 um pixel ARGB inteiro é representado por um tipo chamado uint32, que é uma linguagem inteiro de 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 uma imagem 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 contendo pixels ARGB.
cache de cores
Uma pequena matriz com hash para armazenar cores usadas recentemente e poder usar códigos mais curtos para o recall.
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 perda).
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 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 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 no prefixo meta tabela.
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. Isso consiste no 21 bytes seguintes:

  1. String "RIFF".
  2. Um valor small-endian de 32 bits do comprimento do bloco, que é o tamanho inteiro do bloco controlado pelo cabeçalho RIFF. Normalmente, isso equivale a o tamanho da carga (tamanho do arquivo menos 8 bytes: 4 bytes para o "RIFF" identificador e 4 bytes para armazenar o próprio 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 da imagem que podem reduzir a entropia simbólica restante modelando correlações espaciais e de cor. Eles pode 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 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, a o valor de pixel atual é previsto a partir dos pixels já decodificados (em linha de leitura ordem) e somente 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 de uma usam o mesmo modo de previsão.

Os primeiros 3 bits dos 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 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 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 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 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 Médio 2(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 preditora, 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 de verde (G) como ele está, transforma a valor de vermelho (R) com base no valor de verde e transforma o valor de azul (B) com base no valor verde e, em seguida, 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 cor é 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 deve ser interpretado como um número de complemento de dois de 8 bits (ou seja: intervalo uint8 [128..255] é mapeado para o intervalo [-128..-1] do valor int8 convertido).

A multiplicação será feita com mais precisão (com pelo menos 16 bits precisão). A propriedade de extensão de sinal da operação de deslocamento não importa aqui. somente os 8 bits mais baixos são usados no resultado, e lá o sinal a troca de extensão e a mudança sem assinatura sejam 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 ColorTransformElement instâncias correspondentes, que correspondem 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 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 valores alfa e verde os canais são mantidos 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 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 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 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 é 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 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 estão combinados, e cada pixel tem um intervalo de [0 a 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 imagens em cinco papéis 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 de tamanho color_table_size (até 256 ARGB valores) armazenando 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 sua 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 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 (no essa 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. 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 Partes 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 a 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 da seguinte forma:

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

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 menor distância [1..120] são especiais e estão reservados para fechamento mais 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 (0 pixel diferença na direção X e diferença de 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 indica se o cache de cores é usado. Se esse bit for 0, nenhum código de cache de cores. existem e não são transmitidos no código de prefixo que decodifica 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 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, 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.

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. Esses códigos são (em ordem 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 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 de tamanho de código simples

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;

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, 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 próprios comprimentos de código são codificados usando códigos de prefixo. código de nível inferior comprimentos, code_length_code_lengths, primeiro precisam ser lidos. 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 com base em 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) vez.

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ós de folha única, em que o nó de folha valor é marcado com valor 1 e outros valores são 0s.

6.2.2 Decodificação de códigos de prefixo 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 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 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 bitstream 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 componente verde.
    2. Leia o vermelho do bitstream usando o código de prefixo #2.
    3. Leia em azul no bitstream 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 o código de prefixo de comprimento de S a 256.
    2. Leia bits extras para o comprimento do bitstream.
    3. Determina o comprimento L de referência anterior a partir do código do 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 de digitalização da linha) da sequência de pixels inicial 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

Abaixo está uma visão do formato na Forma aumentada de Backus-Naur (ABNF, na sigla em inglês) RFC 5234 RFC 7405. Ela 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)

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