Jyrki Alakuijala, Ph.D., Google, Inc., 2023-03-09
Resumo
WebP sem perda é um formato de imagem para compactação sem perda de imagens ARGB. O formato sem perdas armazena e restaura exatamente os valores de pixels, incluindo os valores de cores para pixels cujo valor alfa é 0. O formato usa imagens de subresolução, incorporadas recursivamente ao próprio formato, para armazenar dados estatísticos sobre as imagens, como os códigos de entropia usados, os preditores espaciais, a conversão de espaço de cores e a tabela de cores. LZ77, codificação de prefixo e cache de cores são usados para compactação de dados em massa. Foram demonstradas velocidades de decodificação mais rápidas que o PNG, bem como 25% de compressão mais densa do que é possível com o formato PNG atual.
1 Introdução
Este documento descreve a representação de dados compactados de uma imagem WebP sem perda. Ele é uma referência detalhada para a implementação do codificador sem perdas e do decodificador WebP.
Neste documento, usamos bastante a sintaxe da linguagem de programação C para descrever o bitstream e presumimos a existência de uma função para bits de leitura, 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 primeira ordem do bit menos significativo. Quando vários bits são lidos ao mesmo tempo, o número inteiro é construído 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 instruçã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, um número inteiro não assinado que consiste em 32 bits. No código que mostra o comportamento das transformações, o valor alfa é codificado nos bits 31..24, vermelho nos 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 WebP sem perdas contém dados de cabeçalho, informações de transformação e dados de imagens reais. Os cabeçalhos contêm largura e 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 que consiste em valores Alfa, vermelho, verde e azul.
- Imagem ARGB
- Uma matriz bidimensional com pixels ARGB.
- cache de cores
- Uma pequena matriz endereçada por hash para armazenar cores usadas recentemente, para lembrá-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 de transformação de cor
- Uma imagem de subresolução bidimensional com dados sobre correlações de componentes de cor.
- mapeamento de distância
- Altera as distâncias de LZ77 para ter os menores valores de pixels em proximidade 2D.
- imagem de entropia
- Uma imagem de subresolução bidimensional indicando qual codificação de entropia precisa ser usada em um quadrado quadrado na imagem, ou seja, cada pixel é um código de metaprefixo.
- código de prefixo
- Uma maneira clássica de fazer codificação de entropia em que um número menor de bits é usado para códigos mais frequentes.
- Lz 77
- Algoritmo de compactação de janela deslizante baseado em dicionário que emite símbolos ou os descreve como sequências de símbolos antigos.
- código do meta-prefixo
- Um número inteiro pequeno (até 16 bits) que indexa um elemento na tabela de prefixo meta.
- imagem do preditor
- Uma imagem de subresolução bidimensional que indica qual preditor espacial é usado para um quadrado específico na imagem.
- codificação de prefixo
- Uma maneira de entropiar códigos inteiros maiores que codificam alguns bits do número 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 é grande.
- ordem de verificação
- Uma ordem de processamento de pixels, da esquerda para a direita, de cima para baixo, a partir do pixel superior esquerdo, passando para a direita. Após a conclusão de uma linha, continue a partir da coluna da esquerda da próxima linha.
Cabeçalho RIFF 3
O início do cabeçalho tem o contêiner RIFF. Isso consiste nos 21 bytes a seguir:
- String "RIFF"
- Um valor de 32 bits pouco específico 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 do RIFF).
- String "VP8L" (tag de bloco para dados de imagem codificados sem perda).
- Um valor de 32 bits do back-end 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 forma:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
A precisão de 14 bits para largura e altura limita o tamanho máximo de uma imagem sem perda do WebP a 16.384 × 16.384 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);
4 transformações
Transformações são manipulações reversíveis dos dados da imagem que podem reduzir a entropia simbólica restante ao modelar 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 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 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_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. 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 os pixels vizinhos geralmente são correlacionados. Na transformação do preditor, o valor de 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 a 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 do 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 é 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
TL significa superior esquerdo, T superior, TR superior direito, L pixel esquerdo. No momento de 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 | TRY |
| 4 | líder de equipe |
| 5 | Média2(Média2(L; TR); T) |
| 6 | Média2(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 | ClampAddSubtrairFull(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 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 tratamento 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 na parte superior esquerda da imagem será 0xff000000, L-pixel para todos os pixels na linha superior e T pixels para todos os pixels na coluna mais à esquerda.
Resolver o TR-pixel para pixels na coluna mais à direita é uma exceção. Os pixels na coluna mais à direita são previstos usando os modos [0..13], assim como os pixels que não estão na borda, mas o pixel mais à esquerda na mesma linha que o pixel atual é usado como o TR-pixel.
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 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. 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 cores depende do ColorTransformElement, que é o mesmo
para todos os pixels em um bloco específico. O delta é subtraído durante a transformação de cor. A transformação da 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 assinado que representa um número de ponto fixo de 3,5 bits e um canal de cor RGB assinado de 8 bits (c) [-128..127], definido da seguinte maneira:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
Antes de chamar ColorTransformDelta(), é necessária uma conversão da representação não assinada de 8 bits (uint8) para a de 8 bits (int8). Ela precisa ser executada usando o complemento de dois de 8 bits, ou seja: o intervalo uint8 [128..255] é mapeado para o intervalo [-128..-1] do valor int8 convertido.
A multiplicação precisa ser feita com mais precisão (com pelo menos 16 bits). A propriedade da extensão de sinal da operação de mudança não importa aqui: apenas os 8 bits mais baixos são usados do resultado, e a mudança de 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 de cor inversa e recuperar os valores vermelhos e azuis originais. 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, exatamente 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 cores contém instâncias de ColorTransformElement correspondentes a cada bloco da imagem. As instâncias 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 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 ColorTransformElement aos canais vermelho e azul.
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 verde subtrair subtrai os valores verdes dos valores vermelho e azul 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 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, mas como não há dados adicionais aqui, a transformação verde de subtração pode ser codificada usando menos bits do que uma transformação de cor completa.
4.4 Transformação da 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, especificamente, não a chamamos de transformação de paleta, porque existe um conceito semelhante, mas mais dinâmico, na codificação WebP sem perda: cache de cor.
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 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, todos os valores vermelhos e azuis são 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 obtida 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 subtraída 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 obtida 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 para a 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 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 (2, 4 ou 8) pixels em um único pixel, reduzindo a largura da imagem, respectivamente. O agrupamento de pixels permite uma codificação de entropia de distribuição conjunta mais eficiente de pixels vizinhos e oferece alguns benefícios aritméticos, como códigos de aritmética, ao código de entropia, mas só pode ser usado quando há 16 ou menos 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 deve 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 foram combinados, e cada pixel tem um intervalo de [0..3]. Um valor de 3 indica que oito pixels são combinados e cada pixel tem um intervalo de [0..1], ou seja, um valor binário.
Os valores são agrupados no componente verde da seguinte 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, um valor verde em x + 1 é posicionado nos quatro bits mais significativos do valor verde em x / 2.width_bits= 2: para cada valor x em que x ≡ 0 (moda 4), um valor verde em x é posicionado nos dois bits menos significativos do valor verde em x / 4, os valores verdes em x + 1 a x + 3 são posicionados em ordem para os bits mais significativos do valor verde em x / 4.width_bits= 3: para cada valor x em que x ≡ 0 (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
Dados de imagem são uma matriz de valores em pixels na ordem da linha de verificação.
5.1 Funções dos dados de imagens
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. Os componentes vermelho e verde de um pixel definem o código de metatag usado em um bloco específico da imagem ARGB.
- Imagem do preditor: armazena os metadados da transformação do Predictor. O componente verde de um pixel define qual dos 14 preditores é usado dentro de um bloco específico da imagem ARGB.
- Imagem da transformação de cor. Ela é criada por valores
ColorTransformElement(definidos em Transformação de cor) para diferentes blocos da imagem. CadaColorTransformElement'cte'é tratado como um pixel cujo componente Alfa é255, o componente vermelho écte.red_to_blue, o componente verde écte.green_to_bluee o componente azul écte.green_to_red. - 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. É armazenado como uma imagem de larguracolor_table_sizee altura1.
5.2 Codificação de dados de imagem
A codificação de dados de imagem é independente da sua função.
Primeiro, a imagem é 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 as propriedades estatísticas dele ou unindo repetidamente um par de clusters selecionados aleatoriamente quando reduz a quantidade total de bits necessários para codificar a imagem.
Cada pixel é codificado usando um dos três métodos possíveis:
- Literal de codificação de prefixo: cada canal (verde, vermelho, azul e alfa) é codificado de forma independente na entropia.
- Referência inversa da LZ77: uma sequência de pixels é copiada de outro lugar na imagem.
- Código de cache de cores: uso de um código hash multiplicador multiplicador (í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 por prefixo verde, vermelho, azul e alfa (nessa ordem). Consulte a Seção 6.2.3 para mais detalhes.
5.2.2 Referência do LZ77
Referências anteriores são tuplas de length e distance code:
- 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).
Lógica: esta abordagem reduz a exigência de armazenamento para o código de entropia. Além disso, valores grandes geralmente são raros e, portanto, bits extras seriam usados para pouquíssimos valores na imagem. Assim, essa abordagem resulta em uma melhor compressão geral.
A tabela a seguir indica os códigos de prefixo e os bits extras usados para armazenar intervalos diferentes de valores.
| Intervalo de valor | Código do 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 |
| … | ... | ... |
| 3.072,4096 | 23 | 10 |
| ... | ... | ... |
| 524289... 786432 | 38 | 18 |
| 786433...1048576 | 39 | 18 |
O pseudocódigo para receber um valor (comprimento ou distância) do código de prefixo é o seguinte:
if (prefix_code < 4) {
return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;
Mapeamento de distância:
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. Essa 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 verificação, com deslocamento de 120.
Os menores códigos de distância [1..120] são especiais e reservados para uma proximidade do pixel atual. Esta vizinhança é composta por 120 pixels:
- Pixels que ficam de uma a sete linhas acima do pixel atual e têm até oito colunas à esquerda ou até sete 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 têm até 8 colunas à esquerda do pixel atual. [
8desses pixels].
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 diferença de 1 pixel na direção Y).
Da mesma forma, o código de distância 3 indica o pixel na parte superior esquerda.
O decodificador pode converter um código de distância i em uma distância do pedido de linha de verificação dist da seguinte maneira:
(xi, yi) = distance_map[i - 1]
dist = xi + yi * xsize
if (dist < 1) {
dist = 1
}
em que distance_map é o mapeamento indicado acima e xsize é 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 maneira, as cores usadas recentemente podem ser referidas de forma mais eficiente do que emitindo-as usando os outros dois métodos (descritos em 5.2.1 e 5.2.2).
Os códigos de cache de cor são armazenados da seguinte forma. Primeiro, há um valor de 1 bit que indica se o cache de cores é usado. Se esse bit for 0, não haverá códigos de cache de cor 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 este 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 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). Somente uma pesquisa é feita em um cache de cores. Não há resolução de conflitos.
No início da decodificação ou codificação de uma imagem, todas as entradas em todos os valores do cache de cores são definidas como zero. O código do cache de cores é convertido nessa cor no momento da decodificação. O estado do cache de cores é mantido inserindo cada pixel, seja produzido por referência reversa ou como literais, no cache na ordem que aparece 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 envio dos comprimentos de código de prefixo, e não pelos códigos de prefixo reais.
Especificamente, o formato usa a codificação de prefixo com variação espacial. Em outras palavras, blocos diferentes da imagem podem usar diferentes códigos de entropia.
Lógica: áreas diferentes da imagem podem ter características diferentes. Portanto, permitir que eles usem códigos de entropia diferentes oferece mais flexibilidade e compactação melhor.
6.2 Detalhes
Os dados da imagem codificada consistem em várias partes:
- Como decodificar e criar os códigos de prefixo
- Códigos de prefixo meta
- Dados de imagem codificados por entropia
6.2.1 Como decodificar e criar os códigos de prefixo
Há várias etapas para decodificar os códigos de prefixo.
Como decodificar os comprimentos do código:
Esta seção descreve como ler os comprimentos de código do 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 este bit é 1, é um código de comprimento de código simples e
- 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. A árvore descrita precisa ser uma árvore binária completa. Um único nó de folha é 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 comprimento de código normal. Ao codificar um nó de folha única usando o código normal de comprimento do código, todos, exceto um comprimento de código, precisam ser zero. O valor do nó de folha única é marcado com o comprimento de 1, mesmo quando nenhum bit é consumido quando essa árvore de nós de folha única é usada.
(i) Código de tamanho de código simples:
Essa variante é usada no caso especial em que apenas um ou dois símbolos de prefixo estão no intervalo [0..255] com o comprimento de código 1. Todos os outros comprimentos de código de prefixo são implicitamente zeros.
O primeiro 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 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 comprimentos 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 para alfa, vermelho e azul poderão estar vazios se todos os pixels no mesmo código de prefixo 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 aqueles que contêm um único símbolo 0.
(ii) Código de tamanho normal do código:
Os comprimentos do código de prefixo cabem em 8 bits e são lidos da seguinte maneira.
Primeiro, num_code_lengths especifica o número de comprimentos de código.
int num_code_lengths = 4 + ReadBits(4);
Se num_code_lengths for maior que 19, o bitstream será inválido.
Os comprimentos de código são codificados usando códigos de prefixo: comprimentos de código de nível inferior, code_length_code_lengths, primeiro precisam ser lidos. O restante dessas
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 será num_code_lengths. Caso contrário, ele será definido como:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
Uma tabela de prefixo é criada a partir de code_length_code_lengths e usada para ler
até comprimentos de código max_symbol.
- 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 tamanho do bit do respectivo código.
- O código 16 repete o valor diferente de zero anterior [3..6] vezes, ou seja,
3 + ReadBits(2)vezes. Se o código 16 for usado antes da emissão de um valor diferente de zero, um valor 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 comprimentos 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 do G: 256 + 24 +
color_cache_size - outros literais (A,R,B): 256
- código de distância: 40
O código de tamanho normal do código 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 uma. 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 outros valores são 0s.
6.2.2 Decodificação de códigos de prefixos meta
Conforme observado anteriormente, o formato permite o uso de diferentes códigos de prefixo para diferentes blocos da imagem. Códigos de prefixo de meta são índices que identificam quais códigos de prefixo usar em diferentes partes da imagem.
Só é possível usar códigos de prefixo somente quando a imagem está sendo usada 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 qualquer lugar 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 são armazenados como uma imagem de entropia (descrita abaixo).
Imagem de 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 metaprefixo:
Para qualquer 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 para trás e cache de cores.
- Código de prefixo 2, 3 e 4: usado para canais vermelho, azul e alfa, respectivamente.
- Prefixo código 5: usado para distância de referência inversa.
De agora em diante, nos referimos a esse conjunto como um grupo de códigos de prefixo.
O número de grupos de códigos de prefixo na imagem ARGB pode ser conseguido encontrando 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 deles é:
int num_prefix_codes = 5 * num_prefix_groups;
Considerando um pixel (x, y) na imagem ARGB, podemos obter os códigos de prefixo correspondentes a serem usados da seguinte maneira:
int position =
(y >> prefix_bits) * prefix_xsize + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];
onde 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 na próxima seção.
6.2.3 Como decodificar dados de imagem codificados por entropia
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 do prefixo, o pixel é lido e decodificado da seguinte maneira:
Leia o próximo símbolo S do bitstream usando o código de prefixo #1. S é qualquer número inteiro no intervalo de 0 a (256 + 24 + color_cache_size- 1).
A interpretação de S depende do valor dele:
- se P < 256
- Use S como o componente verde.
- Leia o vermelho do bitstream usando o código de prefixo #2.
- Leia o azul no bitstream usando o código de prefixo #3.
- Leia o alfa do bitstream usando o código de prefixo 4.
- Se S >= 256 && S < 256 + 24
- Use S - 256 como um código de prefixo de tamanho.
- Leia bits extras para o comprimento do bitstream.
- Determine o comprimento L de referência anterior do código do prefixo do comprimento e os bits extras lidos.
- Leia o código de prefixo de distância do bitstream usando o código de prefixo #5.
- Leia bits extras para distância do bitstream.
- Determina a distância de referência anterior D do código de prefixo de distância e os bits extras lidos.
- Copie os pixels L (em ordem de linha de verificação) da sequência de pixels antes deles por D pixels.
- Se S >= 256 + 24
- Use S - (256 + 24) como o índice no cache de cores.
- Obtém cor ARGB do cache de cores nesse índice.
7 Estrutura geral do formato
Veja abaixo uma visualização do formato no formulário aumentado de Backus-Naur (ABNF, na sigla em inglês). Ele não abrange todos os detalhes. O fim da imagem (EOI, na sigla em inglês) é codificado implicitamente apenas no número de pixels (xsize * ysize).
7.1 Estrutura básica
format = RIFF-header image-header image-stream
RIFF-header = "RIFF" 4OCTET "WEBP" "VP8L" 4OCTET %x2F
image-header = 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 da 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)
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