Especificação para o Bitstream sem perda do WebP

Mantenha tudo organizado com as coleções Salve e categorize o conteúdo com base nas suas preferências.

Jyrki Alakuijala, Ph.D., Google, Inc., 19-06-2012

Os parágrafos marcados como [AMENDED] foram alterados em 16/09/2014.

Os parágrafos marcados como [AMENDED2] foram alterados em 13/05/2022.

Resumo

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 cores para zero pixel Alfa. O formato usa imagens de subresolução, incorporadas recursivamente no próprio formato para armazenar dados estatísticos sobre as imagens, como códigos de entropia usados, preditores espaciais, conversão de espaço de cores e tabela de cores. LZ77, codificação de prefixo e um cache de cores são usados para compactação dos dados em massa. Foram demonstradas velocidades de decodificação mais rápidas que do PNG e uma compactação 25% mais densa do que é possível atingir com o formato PNG atual.

1 Introdução

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

Neste documento, usamos amplamente a sintaxe da linguagem de programação C para descrever o bitstream e presumir a existência de uma função para ler 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 de menor bit primeiro de importância. Quando vários bits são lidos ao mesmo tempo, o número inteiro é criado 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 instruções abaixo:

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

Presumimos que cada componente de cor (por exemplo, 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, um número inteiro sem assinatura composto de 32 bits. No código que mostra o comportamento das transformações, o valor Alfa é codificado nos bits 31..24, vermelho em bits 23..16, verde nos bits 15..8 e azul nos bits 7..0, mas as implementações do formato são livres para usar outra representação internamente.

De modo geral, uma imagem sem perda do WebP 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 sem perda do WebP pode passar por quatro tipos diferentes de transformação antes de ser codificada em entropia. As informações de transformação no bitstream contêm os dados necessários para aplicar as respectivas transformações inversas.

2 Nomenclatura

RGB
Um valor de pixel composto de valores alfa, vermelho, verde e azul.
Imagem ARGB
Uma matriz bidimensional contendo pixels ARGB.
cache de cores
Uma pequena matriz endereçada a hash para armazenar cores usadas recentemente, para ser recuperada com códigos mais curtos.
imagem de indexação de cores
Uma imagem unidimensional de cores que pode ser indexada com um número inteiro pequeno (até 256 em WebP sem perda).
imagem da transformação de cor
Uma imagem de subresolução bidimensional com dados sobre correlações de componentes de cor.
mapeamento de distância
Mudança nas distâncias de LZ77 para os menores valores de pixels em proximidade 2D.
imagem de entropia
Uma imagem de subresolução de duas dimensões indicando qual codificação de entropia precisa ser usada em um respectivo quadrado na imagem, ou seja, cada pixel é um código de prefixo meta.
código do prefixo
Uma maneira clássica de fazer programação de entropia em que um número menor de bits é usado para códigos mais frequentes.
LZ77
Algoritmo de compactação de janela deslizante com base em dicionário que emite símbolos ou os descreve como sequências de símbolos anteriores.
código do metaprefixo
Um pequeno número inteiro (até 16 bits) que indexa um elemento na tabela de prefixos meta.
imagem do preditor
Uma imagem de subresolução de duas dimensões indicando qual preditor espacial é usado para um quadrado específico na imagem.
programação com prefixo
Uma forma de entropia em código de números inteiros maiores que codifica alguns bits do número inteiro usando um código de entropia e codifica os bits brutos 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 leitura
Uma ordem de processamento de pixels, da esquerda para a direita, de cima para baixo, começando do pixel da esquerda para a parte superior, indo para a direita. Depois que uma linha for concluída, prossiga da coluna à esquerda da próxima linha.

Cabeçalho RIFF 3

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

  1. String "RIFF"
  2. É um valor pequeno de 32 bits do comprimento do bloco, que é o tamanho completo do bloco controlado pelo cabeçalho RIFF. Normalmente, isso equivale ao tamanho do payload (tamanho do arquivo menos 8 bytes: 4 bytes para o identificador 'RIFF' e 4 bytes para armazenar o próprio valor).
  3. String "WEBP" (nome do contêiner RIFF).
  4. String "VP8L" (tag de bloco para dados de imagem codificados sem perda).
  5. Um valor de 32 bits pequeno para o 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 dinâmica de 14 bits para o tamanho da imagem limita o tamanho máximo de uma imagem sem perda do WebP a 16.384 × 16.384 pixels.

A bit alpha_is_used é apenas uma dica e não deve afetar a decodificação. Defina esse valor 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 precisa ser tratado como um erro. [ALTERAÇÕES]

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 cor. As transformações podem tornar a compactação final mais densa.

Uma imagem pode passar por quatro tipos de transformação. Um bit 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 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 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 4).

Se uma transformação estiver presente, 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                  = 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. 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 de que pixels vizinhos costumam ser correlacionados. Na transformação do preditor, o valor do pixel atual é previsto a partir dos pixels já decodificados (em ordem de linha de verificação), e apenas o valor residual (real, previsto) é codificado. O modo de previsão determina o tipo de previsão que será usado. Dividimos a imagem em quadrados e todos os pixels em um quadrado usam o mesmo modo de previsão.

Os primeiros 3 bits de dados de previsão definem a largura e a altura do bloco em número de bits. O número de colunas de bloco, block_xsize, é usado na indexação bidimensional.

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 block_xsize = 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. Todos os block_width * block_height pixels de um bloco usam o mesmo modo de previsão. Os modos de previsão são tratados como pixels de uma imagem e codificados usando as mesmas técnicas descritas no Capítulo 5.

Para um pixel x, y, é possível calcular o respectivo endereço de bloco de filtro:

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

Há 14 modos de previsão diferentes. Em cada modo de previsão, o valor atual de pixels é previsto com base em um ou mais pixels vizinhos com valores já conhecidos.

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

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

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

Modo Valor previsto de cada canal do pixel atual
0 0xff000000 (representa a cor preta sólida em ARGB)
1 L
2 T
3 Turquia
4 TL
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 Selecionar(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 preditor de seleção é definido da seguinte forma:

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) {     // \[AMENDED\]
    return L;
  } else {
    return T;
  }
}

As funções ClampAddSubtractFull e ClampAddSubtractHalf são executadas para cada componente ARGB desta 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 de manuseio especiais para alguns pixels de borda. Se houver uma transformação de previsão, independentemente do modo [0..13] para esses pixels, o valor previsto para o pixel mais alto à esquerda da imagem é 0xff000000, L-pixel para todos os pixels na linha de cima e T-pixel para todos os pixels na coluna mais à esquerda.

[AMENDED2] Abordar o TR-pixel para pixels na coluna mais à direita é excecional. Os pixels na coluna mais à direita são previstos usando os modos [0...13] da mesma forma que os pixels que não estão na borda, mas o pixel mais à esquerda na mesma linha do pixel atual é usado como o TR-pixel.

4.2 Transformação de cor

[AMENDEDO]

O objetivo da transformação de cor é decorar os valores de R, G e B de cada pixel. A transformação de cores mantém o valor verde (G), do modo em que está, transforma em vermelho (R) com base em verde e transforma em azul (B) com base em verde e depois em vermelho.

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

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

A transformação de cor real é feita definindo o delta de transformação de cores. O delta de transformação de cor depende da ColorTransformElement, que é a mesma para todos os pixels de um bloco específico. O delta é subtraído durante a transformação de cor. 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;
}

O ColorTransformDelta é calculado usando um número inteiro de 8 bits assinado que representa um número de ponto fixo de 3, 5 e um canal de cores RGB assinado de 8 bits (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 de 8 bits (int8) é necessária antes de chamar ColorTransformDelta(). Ela deve ser realizada usando o complemento de dois e dois bits de 8 bits, ou seja: intervalo uint8 [128-255] é mapeado para o intervalo [-128, -1] do valor int8 convertido.

A multiplicação precisa ser feita com mais precisão (com pelo menos dinâmicas de 16 bits). A propriedade da extensão de sinal da operação de mudança não importa aqui: apenas os oito bits mais baixos são usados do resultado, e a mudança da extensão de sinal e da mudança não assinada 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 de cores inversas e recuperar os valores originais vermelhos e azuis. Os primeiros 3 bits dos dados de transformação de cor contêm a largura e a altura do bloco de imagens 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 de ColorTransformElement correspondentes a cada bloco da imagem. As instâncias de ColorTransformElement são tratadas como pixels de uma imagem e codificadas usando os métodos descritos no Capítulo 5.

Durante a decodificação, as instâncias ColorTransformElement dos blocos são decodificadas e a transformação de cor inversa é aplicada nos valores de ARGB dos pixels. Como mencionado anteriormente, essa transformação de cor inversa está apenas subtraindo valores ColorTransformElement dos canais vermelhos e azuis.

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

A transformação subtrair verde subtrai os valores verdes dos valores vermelhos e azuis de cada pixel. Quando essa transformação está presente, o decodificador precisa adicionar o valor verde para vermelho e azul. Não há dados associados a essa transformação. O decodificador aplica a transformação inversa desta maneira:

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

Essa transformação é redundante porque pode ser modelada usando a transformação de cores, mas ainda é útil. Como ela pode estender a dinâmica da transformação de cores e não houver dados adicionais aqui, a transformação subtrair verde pode ser codificada usando menos bits do que uma transformação de cores completa.

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

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

A transformação de indexação de cores verifica o número de valores exclusivos de ARGB na imagem. Se esse número estiver abaixo de um limite (256), ele criará uma matriz desses valores de ARGB, que é usada para substituir os valores de pixel pelo í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 de cores. O decodificador lê os dados de transformação da indexação de cores da seguinte maneira:

// 8 bit value for 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 acessada lendo uma imagem, sem o cabeçalho RIFF, o tamanho da imagem e as transformações, supondo uma altura de um pixel e uma 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 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 recebida adicionando os valores anteriores do componente de cor por cada componente ARGB separadamente e armazenando os oito bits menos significativos do resultado.

A transformação inversa da imagem está simplesmente substituindo 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 apreditivo precisa ser definido como 0x00000000 (preto transparente). [ALTERAÇÕES]

Quando a tabela de cores for pequena (igual a ou menor que 16 cores), vários pixels serão agrupados em um único pixel. O agrupamento de pixels agrupa vários pixels (2, 4 ou 8) em um único pixel, reduzindo a largura da imagem, respectivamente. O agrupamento de pixels permite uma programação de entropia de distribuição conjunta mais eficiente de pixels vizinhos e oferece alguns benefícios semelhantes à programação aritmética para o código de entropia, mas só pode ser usado quando há um pequeno número de valores exclusivos.

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 nenhum agrupamento de pixels será feito para a imagem. Um valor de 1 indica que dois pixels são combinados, e cada um 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 um tem um intervalo de [0...1], ou seja, um valor binário.

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

  • width_bits = 1: para cada valor de x em que x ≡ 0 (mod 2), um valor verde em x é posicionado nos quatro bits menos significativos do valor verde em x / 2. 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. 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 de x em que x ≡ 0 (moda 8), um valor verde em x é posicionado no bit menos significativo do valor verde em x / 8. Os valores verdes em x + 1 a x + 7 são posicionados para os bits mais significativos do valor verde em x / 8.

5 Dados de imagem

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

5.1 Papéis de 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. Os componentes vermelho e verde de um pixel definem o código de prefixo meta usado em um bloco específico da imagem ARGB.
  3. Imagem do preditor: armazena os metadados da Predictor Transform. O componente verde de um pixel define qual dos 14 preditores é usado dentro de um bloco específico da imagem ARGB.
  4. Imagem que transforma a cor. Ela é criada pelos valores ColorTransformElement (definidos em Color Transform) para diferentes blocos da imagem. Cada ColorTransformElement 'cte' é tratado como um pixel com componente Alfa, 255, vermelho, cte.red_to_blue, verde cte.green_to_blue, e azul, cte.green_to_red.
  5. Imagem de indexação de cores: uma matriz de tamanho color_table_size (até 256 valores ARGB) que armazena os metadados para a Transformação de indexação de cores. Ela é armazenada como uma imagem de largura color_table_size e altura 1.

5.2 Codificação de dados de imagem

A codificação dos dados de imagem é independente do papel dela.

A imagem é dividida primeiro em um conjunto de blocos de tamanho fixo (geralmente blocos de 16x16). Cada um desses blocos é modelado usando seus próprios códigos de entropia. Além disso, vários blocos podem compartilhar os mesmos códigos de entropia.

Justificativa: o armazenamento de 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 mesclando repetidamente um par de clusters aleatoriamente selecionados quando ele reduz a quantidade total de bits necessários para codificar a imagem.

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

  1. Literal de prefixo codificado: cada canal (verde, vermelho, azul e alfa) é codificado individualmente para entropia.
  2. Referência LZ77 de volta: uma sequência de pixels é copiada de outros lugares na imagem; ou
  3. Código de cache de cores: usar um código hash de multiplicação curto (índice de cache de cores) de uma cor vista recentemente.

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

5.2.1 Literais codificados com prefixo

O pixel é armazenado como valores codificados em prefixo de verde, vermelho, azul e alfa (nessa ordem). Consulte esta seção para ver mais detalhes.

5.2.2 Referência LZ77 para trás

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

  • O comprimento indica quantos pixels na ordem da linha de verificação 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 está 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 grandes valores inteiros 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 do código de entropia. Além disso, valores grandes geralmente são raros, então bits extras seriam usados para poucos valores na imagem. Assim, essa abordagem resulta em uma melhor compactação geral.

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

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

O pseudocódigo para receber um valor (tamanho ou distância) do código do 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:

Conforme observado anteriormente, o código de distância é um número que indica a posição de um pixel visto anteriormente, do qual 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.

Os códigos de distância maiores que 120 indicam a distância em pixels na ordem de linha de verificação, com deslocamento de 120.

Os códigos de menor distância [1..120] são especiais e estão reservados para um vizinho próximo do pixel atual. Esta vizinhança é composta por 120 pixels:

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

O mapeamento entre o código de distância i e o deslocamento de 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 de 1 pixel de diferença 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 i em uma distância da ordem de linha de verificação dist da seguinte maneira:

(xi, yi) = distance_map[i]
dist = x + y * xsize
if (dist < 1) {
  dist = 1
}

em que distance_map é o mapeamento anotado acima e xsize é a largura da imagem em pixels.

5.2.3 Programaçã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 de forma mais eficiente do que emitir usando os outros dois métodos (descritos em 5.2.1 e 5.2.2).

Os códigos de cache de cor são armazenados da seguinte maneira. Primeiro, há um valor de 1 bits 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 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 color_cache por (1 << color_cache_code_bits). O intervalo de valores permitidos para color_cache_code_bits é [1..11]. Os decodificadores em conformidade precisam indicar uma bitstream corrompida 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 conflito.

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 de cache de cores é convertido para essa cor no momento da decodificação. O estado do cache de cores é mantido inserindo cada pixel, seja produzido por referência para trás 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 pelo tamanho do código de prefixo, em vez dos códigos de prefixo reais.

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

Justificativa: áreas diferentes da imagem podem ter características distintas. Isso permite que eles usem diferentes códigos de entropia para aumentar a flexibilidade e melhor compactação.

6.2 Detalhes

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

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

6.2.1 Decodificar e criar os códigos de prefixo

Há várias etapas para decodificar os códigos de prefixo.

Como decodificar os tamanhos de código:

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

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

  • Se esse bit é 1, significa um código de comprimento de código simples.
  • Se esse bit é 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 do stream. Isso pode ser ineficiente, mas é permitido pelo formato.

(i) Código de tamanho de código simples:

[AMENDEDO]

Essa variante é usada no caso especial em que apenas um ou dois símbolos de prefixo estão no intervalo [0,255] com comprimento do código 1. Todos os outros tamanhos 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;

Veja a seguir os valores de símbolos. Esse 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, é considerado como se estivesse 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;
}

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

(ii) Código de tamanho normal de código:

Os tamanhos do código de prefixo se encaixam em oito 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);

Se num_code_lengths for > 18, o bitstream será inválido.

Os tamanhos de código são codificados usando códigos de prefixo: tamanhos de código de nível inferior code_length_code_lengths primeiro precisam ser lidos. O restante das 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);
}

Depois, se ReadBits(1) == 0, o número máximo de símbolos de leitura diferentes é num_code_lengths. Em outros casos, ele é definido como:

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

Uma tabela de prefixo é criada usando code_length_code_lengths e usada para ler até max_symbol comprimentos de código.

  • O código [0...15] indica o comprimento literal do código.
    • O valor 0 significa que nenhum símbolo foi codificado.
    • Os valores [1..15] indicam o comprimento do bit do respectivo código.
  • O código 16 repete o valor anterior diferente de zero [3..6] vezes, ou seja, 3 + ReadBits(2) vezes. Se o código 16 for usado antes da emissão de um valor diferente de zero, um valor de 8 será repetido.
  • O código 17 emite uma sequência de zeros [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 tamanhos de código são lidos, um código de prefixo para cada tipo de símbolo (A, R, G, B, distância) é formado usando os respectivos tamanhos de alfabeto:

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

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

Conforme observado anteriormente, o formato permite o uso de diferentes códigos de prefixo para diferentes blocos da imagem. Os códigos de metacódigo são índices que identificam os códigos de prefixo a serem usados em diferentes partes da imagem.

Os códigos de metacódigo podem ser usados somente quando a imagem estiver sendo usada no papel de uma imagem ARGB.

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

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

Imagem entropia:

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

Os primeiros 3 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_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);

em que DIV_ROUND_UP é definido anteriormente.

Os próximos bits contêm uma imagem de entropia de largura prefix_xsize e altura prefix_ysize.

Interpretação de códigos de prefixo de metal:

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

  • código de prefixo 1: usado para canal verde, comprimento de referência reverso e cache de cores.
  • códigos de prefixo 2, 3 e 4: usados para canais vermelhos, azuis e Alfa, respectivamente.
  • código do prefixo 5: usado para distância de referência inversa.

Daqui em diante, nos referimos a esse conjunto como um grupo de código de prefixos.

Para saber o número de grupos de códigos de prefixo na imagem ARGB, encontre o maior código de prefixo de 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 de códigos de prefixo contém cinco códigos de prefixo, o número total de códigos de prefixo é:

int num_prefix_codes = 5 * num_prefix_groups;

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

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

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

O decodificador usa o grupo de código de prefixo prefix_group para decodificar o pixel (x, y), conforme explicado na próxima seção.

6.2.3 Decodificar dados de imagens codificadas em entropia

[AMENDEDO]

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

Leia o próximo símbolo S a partir do bitstream usando o código de prefixo no 1. Observe que S é qualquer número inteiro no intervalo de 0 a (256 + 24 + color_cache_size- 1).

A interpretação dos S depende do valor deles:

  1. Se S < 256
    1. Use S como o componente verde.
    2. Leia o vermelho no bitstream usando o código de prefixo no 2.
    3. Leia o azul no bitstream usando o código de prefixo no 3.
    4. Leia o Alfa do bitstream usando o código de prefixo no 4.
  2. se S >= 256 && S < 256 + 24
    1. Use S - 256 como um código de prefixo de tamanho.
    2. Leia bits extras para comprimento do bitstream.
    3. Determina o comprimento da referência inversa L do código de prefixo do comprimento e os bits extras lidos.
    4. Leia o código de prefixo da distância do bitstream usando o código de prefixo #5.
    5. Ler bits extras para distância do bitstream.
    6. Determina a distância D de referência inversa do código de prefixo da distância e os bits extras lidos.
    7. Copie os pixels L (em ordem de verificação) da sequência de pixels antes de D pixels.
  3. Se S >= 256 + 24
    1. Use S - (256 + 24) como o índice no cache de cores.
    2. Receber cor ARGB do cache de cores nesse índice.

7 Estrutura geral do formato

Veja abaixo uma visualização do formato no formulário de Backus-Naur. Ele não abrange todos os detalhes. O fim da imagem (EOI, na sigla em inglês) é apenas codificado implicitamente para o número de pixels (xsize * ysize).

7.1 Estrutura básica

<format> ::= <RIFF header><image size><image stream>
<image stream> ::= <optional-transform><spatially-coded image>

7.2 Estrutura das transformações

<optional-transform> ::=
    (1-bit value 1; <transform> <optional-transform>) | 1-bit value 0
<transform> ::= <predictor-tx> | <color-tx> | <subtract-green-tx> |
                <color-indexing-tx>
<predictor-tx> ::= 2-bit value 0; <predictor image>
<predictor image> ::= 3-bit sub-pixel code ; <entropy-coded image>
<color-tx> ::= 2-bit value 1; <color image>
<color image> ::= 3-bit sub-pixel code ; <entropy-coded image>
<subtract-green-tx> ::= 2-bit value 2
<color-indexing-tx> ::= 2-bit value 3; <color-indexing image>
<color-indexing image> ::= 8-bit color count; <entropy-coded image>

7.3 Estrutura dos Dados da Imagem

[AMENDEDO]

<spatially-coded image> ::= <color cache info><meta prefix><data>
<entropy-coded image> ::= <color cache info><data>
<color cache info> ::=
    1 bit value 0 | (1-bit value 1; 4-bit value for color cache size)
<meta prefix> ::= 1-bit value 0 |
                  (1-bit value 1; <entropy image>)
<data> ::= <prefix codes><lz77-coded image>
<entropy image> ::= 3-bit subsample value; <entropy-coded image>
<prefix codes> ::= <prefix code group> |
                   <prefix code group><prefix codes>
<prefix code group> ::= <prefix code><prefix code><prefix code>
                        <prefix code><prefix 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> ::= <code length code>; encoded code lengths
<code length code> ::= see section "Normal code length code"
<lz77-coded image> ::= ((<argb-pixel> | <lz77-copy> |
                         <color-cache-code>) <lz77-coded image>) | ""

Um possível exemplo de sequência:

<RIFF header><image size>1-bit value 1<subtract-green-tx>
1-bit value 1<predictor-tx>1-bit value 0<color cache info>
1-bit value 0<prefix codes><lz77-coded image>