Jyrki Alakuijala, Ph.D., Google LLC 2023-03-09
Com abstração
WebP sem perda é um formato de imagem para compactação sem perda 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 compactação de dados sequencial (LZ77), codificação de prefixo e um cache de cores são usados para compactar os dados em massa. Foram demonstradas velocidades de decodificação mais rápidas que o PNG, bem como uma compactação 25% mais densa do que é possível conseguir com o formato PNG atual.
1 Introdução
Este documento descreve a representação de dados compactada de uma imagem WebP sem perda. Ele é uma referência detalhada para a implementação do codificador e decodificador do WebP sem perdas.
Neste documento, usamos extensivamente 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 stream que os contém, e os bits de cada byte são lidos na ordem menos significativa do primeiro bits. Quando vários bits são lidos ao mesmo tempo, o número inteiro é criado a partir dos 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 declaração
b = ReadBits(2);
é equivalente às duas instruções abaixo:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Presumimos 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 com 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 estão livres para usar outra representação interna.
De modo geral, uma imagem WebP sem perda contém dados de cabeçalho, informações de transformação e dados de imagem reais. Os cabeçalhos contêm a largura e a altura da imagem. Uma imagem do WebP sem perdas pode passar por quatro tipos diferentes de transformações 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
- ARGB
- Um valor de pixel consistindo em valores alfa, vermelho, verde e azul.
- Imagem ARGB
- Uma matriz bidimensional contendo pixels ARGB.
- cache de cores
- Uma pequena matriz endereçada por hash para armazenar cores usadas recentemente e poder chamá-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 perda).
- imagem com transformação de cor
- Uma imagem de subresolução bidimensional que contém dados sobre correlações de componentes de cor.
- mapeamento de distância
- Muda as distâncias de LZ77 para ter os menores valores de pixels na proximidade bidimensional.
- imagem de entropia
- Uma imagem de subresolução bidimensional que indica qual codificação de entropia precisa ser usada em um respectivo quadrado na imagem, ou seja, cada pixel é um código de metaprefixo.
- LZ77
- Um algoritmo de compactação de janela deslizante baseado em dicionário que emite símbolos ou os descreve como sequências de símbolos passados.
- código de prefixo meta
- Um número inteiro pequeno (até 16 bits) que indexa um elemento na tabela de prefixos meta.
- imagem do preditor
- Uma imagem de subresolução bidimensional que indica qual preditor espacial é usado para um quadrado específico na imagem.
- código de prefixo
- Uma maneira clássica de fazer a codificação de entropia, em que um número menor de bits é usado para códigos mais frequentes.
- codificação de prefixo
- Uma maneira de codificar números inteiros maiores, que codifica alguns bits do inteiro usando um código de entropia e codifica os bits brutos restantes. Isso permite que as descrições dos códigos de entropia permaneçam relativamente pequenas, mesmo quando o intervalo de símbolos for grande.
- pedido de linha de digitalização
- Uma ordem de processamento de pixels (da esquerda para a direita e de cima para baixo), começando no pixel superior esquerdo. Quando uma linha for concluída, continue na coluna esquerda da linha seguinte.
3 Cabeçalho RIFF
O início do cabeçalho tem o contêiner RIFF. Isso consiste nos 21 bytes a seguir:
- String "RIFF".
- Um valor pouco endian de 32 bits do comprimento do bloco, que é o tamanho total 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).
- String "WEBP" (nome do contêiner RIFF).
- String "VP8L" (FourCC para dados de imagem codificados sem perdas).
- Um valor pouco endian de 32 bits do número de bytes no stream sem perdas.
- 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 perda a 16384✕16384 pixels.
O bit alpha_is_used é apenas uma dica e não deve afetar a decodificação. Ele precisa ser definido como 0 quando todos os valores Alfa forem 255 na imagem e 1 se não forem.
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.
int version_number = ReadBits(3);
Quatro 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 cores. Eles podem tornar a compactação final mais densa.
Uma imagem pode passar por quatro tipos de transformações. Um bit indica a presença de uma transformação. Cada transformação pode ser usada apenas uma vez. As transformações são usadas apenas para a imagem ARGB de nível principal. As imagens de subresolução (imagem de transformação de cor, imagem de entropia e imagem de previsão) não têm transformações, nem mesmo o bit 0 que indica o fim das transformações.
Normalmente, um codificador usaria essas transformações para reduzir a entropia de Shannon na imagem residual. Além disso, os dados de transformação podem ser decididos com base na minimização da entropia.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
Se uma transformação estiver presente, os 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 dependem do tipo de transformação. As transformações inversas são aplicadas na ordem inversa em que são lidas a partir do bitstream, ou seja, a última delas 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 de que 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 da linha de verificação), e somente 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 um quadrado 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. É
uma imagem de sub-resoluçã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 em blocos, transform_width, é usado na indexação
bidimensional. Para um pixel (x, y), é possível calcular o respectivo endereço do bloco de filtro:
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 atual do pixel é previsto com base em um ou mais pixels vizinhos cujos valores já são conhecidos.
Escolhemos os pixels vizinhos (TL, T, TR e L) do pixel atual (P) da seguinte 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 significa superior, TR significa superior direito e L significa esquerda. No momento da previsão de um valor para P, todos os pixels O, TL, T, TR e L já foram processados, e o pixel P e todos os pixels X são desconhecidos.
Considerando os pixels vizinhos anteriores, os diferentes modos de previsão são definidos da maneira a seguir.
| Modo | Valor previsto de cada canal do pixel atual |
|---|---|
| 0 | 0xff000000 (representa a cor preta sólida em ARGB) |
| 1 | L |
| 2 | T |
| 3 | TRY |
| 4 | TL |
| 5 | Médio2(Média2(L, TR), T) |
| 6 | Médio2(L, TL) |
| 7 | Médio2(L, T) |
| 8 | Média 2(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) |
O Average2 é definido da seguinte maneira para cada componente ARGB:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
O preditor "Selecionar" é 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);
}
Existem regras de processamento 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 superior esquerdo da imagem será 0xff000000, todos os pixels na linha superior serão L-pixel e todos os pixels na coluna mais à esquerda serão T-pixel.
Lidar com o pixel TR para pixels na coluna mais à direita é excepcional. Os pixels na coluna mais à direita são previstos usando os modos [0..13], assim como os pixels não na borda, mas o pixel mais à esquerda na mesma linha do pixel atual é usado como o pixel TR.
O valor de pixel final é conseguido adicionando cada canal do valor previsto ao valor residual codificado.
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.2 Transformação de cor
O objetivo da transformação de cor é decorar os valores R, G e B de cada pixel. A transformação de cor mantém o valor verde (G) como está, transforma o valor vermelho (R) com base no valor de verde e transforma o valor azul (B) com base no valor de verde e, por fim, no valor vermelho.
Como é o caso da 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. Para cada bloco, há três tipos de elementos de transformação de cor.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
A transformação de cor real é feita definindo um delta de transformação de cor. O
delta de transformação de cor depende de ColorTransformElement, que é o mesmo
para todos os pixels em um bloco específico. O delta é subtraído durante a
transformação 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 assinado de 8 bits que representa um
número de ponto fixo de 3,5 e um canal de cores RGB assinado (c) [-128..127],
e é definido da seguinte maneira:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
É necessária uma conversão da representação não assinada de 8 bits (uint8) para a assinada
de 8 bits (int8) antes de chamar ColorTransformDelta(). O valor com sinal
precisa ser interpretado como um número de complemento de dois de 8 bits (ou seja: o intervalo uint8
[128..255] é mapeado para o intervalo [-128..-1] do valor int8 convertido).
A multiplicação deve ser feita com mais precisão (com precisão de pelo menos 16 bits). A propriedade de extensão de sinal da operação de deslocamento não importa aqui. Apenas os 8 bits mais baixos são usados do resultado, e a mudança da extensão de sinal e a mudança não assinada são consistentes entre si.
Agora, descrevemos o conteúdo dos dados de transformação de cor para que a decodificação possa aplicar a transformação inversa de cor e recuperar os valores originais de vermelho e azul. Os primeiros 3 bits dos dados de transformação de cor contêm a largura e a altura do bloco de imagem em número de bits, assim como a transformação 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. Cada
ColorTransformElement 'cte' é tratado como um pixel em uma imagem de subresolução
com um componente alfa 255, o componente vermelho é cte.red_to_blue, o componente
verde é cte.green_to_blue e o componente azul é cte.green_to_red.
Durante a decodificação, as instâncias de ColorTransformElement dos blocos são decodificadas, e
a transformação de cor inversa é aplicada aos valores ARGB dos pixels. Como
mencionado anteriormente, essa transformação de cor inversa está apenas adicionando
valores de ColorTransformElement aos canais vermelho e azul. Os canais alfa e verde
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 transformação verde
A transformação "Subtrair verde" subtrai os valores de verde dos valores de vermelho e azul de cada pixel. Quando essa transformação está presente, o decodificador precisa adicionar o valor verde aos valores vermelho e azul. Não há dados associados a essa transformação. O decodificador aplica a transformação inversa da seguinte maneira:
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
Essa transformação é redundante, porque pode ser modelada usando a transformação de cor. No entanto, como não há mais dados aqui, a transformação de subtração verde pode ser codificada usando menos bits do que uma transformação de cor completa.
4.4 Transformação de indexação de cores
Se não houver muitos valores de pixel exclusivos, pode ser mais eficiente criar uma matriz de índice de cores e substituir os valores de pixel pelos índices da matriz. A transformação de indexação de cores consegue isso. No contexto do WebP sem perda, nós especificamente não chamamos isso de transformação de paleta porque há um conceito semelhante, mas mais dinâmico, na codificação do WebP sem perda: cache de cores.
A transformação de indexação de cores verifica o número de valores ARGB exclusivos na imagem. Se esse número estiver abaixo de um limite (256), ele vai criar uma matriz desses valores ARGB, que será usada para substituir os valores de pixel pelo índice correspondente: o canal verde dos pixels é substituído pelo índice, todos os valores Alfa são definidos como 255 e todos os valores 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 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 recebida pela leitura de uma imagem, sem o cabeçalho RIFF, o tamanho da imagem e as
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
das cores da paleta normalmente contêm muito menos entropia do que as próprias cores, levando a 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
8 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 de cor argb
precisa ser definido como 0x00000000 (preto transparente).
Quando a tabela de cores é pequena (igual ou menor que 16 cores), vários pixels são agrupados em um único pixel. O agrupamento de pixels empacota vários pixels (2, 4 ou 8) 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 dos 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 exclusivos ou menos.
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 pixel tem um intervalo de [0..15]. Um valor de 2 indica que
quatro pixels são combinados e cada pixel tem um intervalo de [0..3]. Um valor de 3
indica que oito pixels são combinados e cada pixel tem um intervalo de [0..1],
ou seja, um valor binário.
Os valores são 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 quatro 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 2 bits menos significativos do valor verde em x / 4, e valores verdes em x + 1 a x + 3 são posicionados em ordem aos bits mais significativos do valor verde em x / 4.width_bits= 3: para cada valor x, em que x ≡ 0 (mod 8), um valor verde em x é posicionado no bit menos significativo do valor verde em x / 8, e valores verdes em x + 1 a x + 7 são posicionados nos bits mais significativos do valor verde em x / 8.
Depois de ler essa transformação, image_width passa por uma subamostragem de 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
Os dados da imagem são uma matriz de valores de pixel na ordem das linhas de verificação.
5.1 Funções dos dados de imagem
Usamos dados de imagem em cinco funções diferentes:
- Imagem ARGB: armazena os pixels reais da imagem.
- Imagem de entropia: armazena os códigos de prefixo meta (consulte Decodificação de códigos de prefixo meta").
- Imagem do preditor: armazena os metadados da transformação do preditor. Consulte "Transformação do preditor".
- Imagem de transformação de cor: criada por valores
ColorTransformElement(definidos em "Transformar cor") para diferentes blocos da imagem. - Imagem de indexação de cores: uma matriz de tamanho
color_table_size(até 256 valores ARGB) que armazena os metadados da transformação de indexação de cores. Consulte Transformação de indexação de cores.
5.2 Codificação de dados de imagem
A codificação de dados de imagem é independente da função dela.
A imagem é primeiro dividida em um conjunto de blocos de tamanho fixo (normalmente blocos de 16 x 16). 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.
Lógica: o armazenamento de um código de entropia incorre em um custo. Esse custo poderá 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 propriedades estatísticas ou mesclando repetidamente um par de clusters selecionados aleatoriamente quando isso reduz a quantidade geral de bits necessários para codificar a imagem.
Cada pixel é codificado usando um dos três métodos possíveis:
- Literais codificados de prefixo: cada canal (verde, vermelho, azul e alfa) é codificado de entropia de forma independente.
- Referência LZ77: uma sequência de pixels é copiada de outro lugar na imagem.
- Código do cache de cores: usa um código hash multiplicativo curto (índice de cache de cores) de uma cor vista recentemente.
As subseções a seguir descrevem cada um deles em detalhes.
5.2.1 Literais codificados por prefixo
O pixel é armazenado como valores codificados de prefixo de verde, vermelho, azul e alfa (nessa ordem). Consulte a Seção 6.2.3 para mais detalhes.
5.2.2 Referência LZ77 para versões anteriores
As referências invertidas são tuplas de length e distance code:
- O comprimento indica quantos pixels na ordem da linha de verificação devem ser copiados.
- O código de distância é um número que indica a posição de um pixel visto anteriormente, de onde os pixels serão copiados. O mapeamento exato 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 valores inteiros grandes em duas partes: o código de prefixo e os bits extras. O código de prefixo é armazenado usando um código de entropia, enquanto os bits extras são armazenados como estão (sem um código de entropia).
Lógica: esta abordagem reduz o requisito de armazenamento do código de entropia. Além disso, valores grandes geralmente são raros, portanto, bits extras seriam usados para pouquíssimos valores na imagem. Assim, essa abordagem resulta em uma melhor compactação em 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 de prefixo | Bits extras |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| 3 | 2 | 0 |
| 4 | 3 | 0 |
| 5..6 | 4 | 1 |
| 7..8 | 5 | 1 |
| 9 a 12 | 6 | 2 |
| 13..16 | 7 | 2 |
| ... | ... | ... |
| 3072..4096 | 23 | 10 |
| ... | ... | ... |
| 524289..786432 | 38 | 18 |
| 786433..1048576 | 39 | 18 |
O pseudocódigo para extrair um valor de comprimento ou distância do código de prefixo é o seguinte:
if (prefix_code < 4) {
return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;
Mapeamento de distância
Conforme observado anteriormente, um código de distância é um número que indica a posição de um pixel visto anteriormente, de onde os pixels serão copiados. Esta subseção define o mapeamento entre um código de distância e a posição de um pixel anterior.
Códigos de distância maiores que 120 indicam a distância em pixels na ordem da linha de leitura, com deslocamento de 120.
Os códigos de menor distância [1..120] são especiais e reservados para uma vizinhança próxima do pixel atual. Esta vizinhança consiste em 120 pixels:
- Pixels que estejam de 1 a 7 linhas acima do pixel atual e com até oito colunas
à esquerda ou até 7 colunas à direita do pixel atual. [Total de pixels =
7 * (8 + 1 + 7) = 112]. - Pixels que estão na mesma linha que o pixel atual e são até oito
colunas à esquerda do pixel atual. [
8pixels desses].
O mapeamento entre o código de distância distance_code e o deslocamento de pixels
vizinha (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 na direção Y).
Da mesma forma, o código de distância 3 indica o pixel superior esquerdo.
O decodificador pode converter um código de distância distance_code em uma distância dist do pedido da linha de leitura da seguinte maneira:
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
em que distance_map é o mapeamento indicado 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.
Lógica:dessa forma, às vezes, as cores usadas recentemente podem ser referenciadas de forma mais eficiente do que a emissão delas 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 desta forma: Primeiro, há um valor de 1 bit que indica se o cache de cores será 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 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 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. Não há
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 do 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 inversa 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. Assim, os códigos são transmitidos enviando os tamanhos de código de prefixo, em vez de códigos de prefixo reais.
Especificamente, o formato usa codificação de prefixo de variante espaciais. Em outras palavras, blocos diferentes da imagem podem usar diferentes códigos de entropia.
Lógica: diferentes áreas da imagem podem ter diferentes características. Portanto, permitir que eles usem diferentes códigos de entropia proporciona mais flexibilidade e uma compactação potencialmente melhor.
6.2 Detalhes
Os dados da imagem codificada consistem em várias partes:
- Decodificar e criar os códigos de prefixo.
- Códigos de prefixo meta.
- Dados de imagem codificados em entropia.
Para cada pixel (x, y), há um conjunto de cinco códigos de prefixo associados a ele. Esses códigos são (em ordem de bitstream):
- Código de prefixo #1: usado para canal verde, comprimento de referência anterior e cache de cores.
- Código de prefixo #2, #3 e #4: usado para os canais vermelho, azul e alfa, respectivamente.
- Código de prefixo #5: usado para distância de referência inversa.
A partir daqui, vamos nos referir a esse conjunto como um grupo de códigos de prefixo.
6.2.1 Decodificação e criação dos códigos de prefixo
Esta seção descreve como ler os comprimentos do código de prefixo do bitstream.
Os comprimentos do 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 simples de comprimento de código.
- Se esse bit for 0, significa um código de tamanho 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. A árvore descrita precisa ser uma árvore binária completa. Um nó de folha única é considerado uma árvore binária completa e pode ser codificado usando o código de comprimento de código simples ou o código de tamanho normal. Ao codificar um único nó de folha usando o código de comprimento de código normal, todos os comprimentos do código são zero, e o valor do nó de folha única é marcado com o comprimento de 1, mesmo quando nenhum bito é consumido quando essa árvore de nó é usada.
Código simples de comprimento
Essa variante é usada no caso especial, em que apenas um ou dois símbolos de prefixo estão no
intervalo [0..255] com comprimento de código 1. Todos os outros comprimentos de código de prefixo são
implicitamente zeros.
O primeiro bit indica o número de símbolos:
int num_symbols = ReadBits(1) + 1;
Confira a seguir os valores de símbolo.
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, é sempre considerado no intervalo [0..255] e codificado
usando 8 bits.
int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
symbol1 = ReadBits(8);
code_lengths[symbol1] = 1;
}
Os dois símbolos devem ser diferentes. Símbolos duplicados são permitidos, mas não são eficientes.
Observação:outro caso especial é quando todos os comprimentos do código de prefixo são zeros (um
código vazio). Por exemplo, um código de prefixo para distância poderá ficar vazio se
não houver referências anteriores. Da mesma forma, os códigos de prefixo alfa, vermelho e
azul poderão ficar vazios 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 processamento especial, já que
códigos de prefixo vazios podem ser codificados como aqueles que contêm um único símbolo 0.
Código de comprimento do código normal
Os comprimentos do código do prefixo se encaixam em 8 bits e são lidos da seguinte maneira.
Primeiro, num_code_lengths especifica o número de comprimentos de código.
int num_code_lengths = 4 + ReadBits(4);
Os comprimentos do código são codificados com o uso de códigos de prefixo. Os comprimentos de código de nível mais baixo, code_length_code_lengths, primeiro precisam ser lidos. O restante desses
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) vai ser definido como o
tamanho do alfabeto:
- Canal G: 256 + 24 +
color_cache_size - Outros literais (A, R e B): 256
- Código de distância: 40
Caso contrário, ele é definido como:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
Se max_symbol for maior que o tamanho do alfabeto para o tipo de símbolo, o
bitstream será inválido.
Uma tabela de prefixos é criada a partir de code_length_code_lengths e usada para ler
códigos de até max_symbol comprimentos.
- 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 de bits 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 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 do código são lidos, um código de prefixo para cada tipo de símbolo (A, R, G, B e distância) é formado usando os respectivos tamanhos de alfabeto.
O código de comprimento do 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 Meta
Conforme observado anteriormente, o formato permite o uso de diferentes códigos de prefixo para diferentes blocos da imagem. Os códigos de prefixo meta são índices que identificam quais códigos de prefixo usar em diferentes partes da imagem.
Os códigos de prefixo meta podem ser usados apenas quando a imagem está sendo utilizada no papel de uma imagem ARGB.
Há duas possibilidades para os códigos de prefixo meta, indicados por um valor de 1 bit:
- Se esse bit for zero, haverá apenas um código de prefixo meta usado em todos os lugares da imagem. Não há mais dados armazenados.
- Se esse bit for um, a imagem usará vários códigos de prefixo meta. Esses códigos de prefixo são armazenados como uma imagem de entropia (descrita abaixo).
Os componentes vermelhos e verdes 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 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_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 é conforme definido anteriormente.
Os próximos bits contêm uma imagem de entropia de largura prefix_image_width e altura
prefix_image_height.
Interpretação de códigos de metaprefixo
O número de grupos de códigos de prefixo na imagem ARGB pode ser obtido encontrando o maior código de prefixo meta na imagem de entropia:
int num_prefix_groups = max(entropy image) + 1;
em que max(entropy image) indica o maior código de prefixo armazenado na imagem de entropia.
Como cada grupo 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;
Com um pixel (x, y) na imagem ARGB, podemos extrair os códigos de prefixo correspondentes a serem usados da seguinte maneira:
int position =
(y >> prefix_bits) * prefix_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];
em que presumimos a existência da estrutura PrefixCodeGroup, que
representa um conjunto de cinco códigos de prefixo. Além disso, prefix_code_groups é uma matriz de
PrefixCodeGroup (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 "Dados de imagem codificados por entropia
de decodificação".
6.2.3 Decodificação de dados de imagem codificados por entropia
Para a posição atual (x, y) na imagem, o decodificador primeiro identifica o grupo de códigos de prefixo correspondente (como explicado na última seção). Considerando o 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 de seu valor:
- Se S < 256
- Use S como o componente verde.
- Leia o vermelho do bitstream usando o código de prefixo 2.
- Leia em azul do bitstream usando o código de prefixo 3.
- Leia o alfa do bitstream usando o código de prefixo 4.
- Se S >= 256 e S < 256 + 24
- Utilize S - 256 como código de prefixo de comprimento.
- Leia os bits extras para o comprimento do bitstream.
- Determina o comprimento de referência anterior L com base no código de prefixo de comprimento e nos bits extras lidos.
- Leia o código de prefixo de distância do bitstream usando o código de prefixo #5.
- Lê bits extras para a distância do bitstream.
- Determine a distância D de referência inversa com o código de prefixo de distância e os bits extras lidos.
- Copie L pixels (na ordem da linha de verificação) da sequência de pixels começando na posição atual menos D pixels.
- Se S >= 256 + 24
- Usar S - (256 + 24) como o índice no cache de cores.
- Extrai a cor ARGB do cache de cores nesse índice.
7 Estrutura geral do formato
Veja abaixo uma visualização do formato em Formato aumentado de Backus-Naur (ABNF, na sigla em inglês) RFC 5234 RFC 7405 (links em inglês). Ele não abrange todos os detalhes. O fim da imagem (EOI, na sigla em inglês) só é codificado implicitamente no número de pixels (image_width * image_height).
Observe que *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 das transformações
optional-transform = (%b1 transform optional-transform) / %b0
transform = predictor-tx / color-tx / subtract-green-tx
transform =/ color-indexing-tx
predictor-tx = %b00 predictor-image
predictor-image = 3BIT ; sub-pixel code
entropy-coded-image
color-tx = %b01 color-image
color-image = 3BIT ; sub-pixel code
entropy-coded-image
subtract-green-tx = %b10
color-indexing-tx = %b11 color-indexing-image
color-indexing-image = 8BIT ; color count
entropy-coded-image
7.3 Estrutura dos Dados de Imagem
spatially-coded-image = color-cache-info meta-prefix data
entropy-coded-image = color-cache-info data
color-cache-info = %b0
color-cache-info =/ (%b1 4BIT) ; 1 followed by color cache size
meta-prefix = %b0 / (%b1 entropy-image)
data = prefix-codes lz77-coded-image
entropy-image = 3BIT ; subsample value
entropy-coded-image
prefix-codes = prefix-code-group *prefix-codes
prefix-code-group =
5prefix-code ; See "Interpretation of Meta Prefix Codes" to
; understand what each of these five prefix
; codes are for.
prefix-code = simple-prefix-code / normal-prefix-code
simple-prefix-code = ; see "Simple Code Length Code" for details
normal-prefix-code = ; see "Normal Code Length Code" for details
lz77-coded-image =
*((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)
Confira a seguir um possível exemplo de sequência:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image