Specifiche per WebP Lossless Bitstream

Jyrki Alakuijala, Ph.D., Google LLC 2023-03-09

Abstract

WebP lossless è un formato per la compressione senza perdita di dati delle immagini ARGB. Il formato senza perdita di dati memorizza e ripristina esattamente i valori dei pixel, inclusi i valori dei colori per i pixel completamente trasparenti. Per la compressione dei dati in blocco vengono utilizzati un algoritmo universale per la compressione sequenziale dei dati (LZ77), la codifica dei prefissi e una cache dei colori. È stata dimostrata una velocità di decodifica maggiore rispetto al formato PNG, nonché una compressione più densa del 25% rispetto a quella che è possibile ottenere utilizzando il formato PNG odierno.

1 Introduzione

Questo documento descrive la rappresentazione dei dati compressi di un'immagine senza perdita di dati WebP. È inteso come riferimento dettagliato per l'implementazione di encoder e decoder senza perdita di dati WebP.

In questo documento, utilizziamo ampiamente la sintassi del linguaggio di programmazione C per descrivere il flusso di bit e presumere l'esistenza di una funzione per la lettura di bit, ReadBits(n). I byte vengono letti nell'ordine naturale del flusso che li contiene e i bit di ogni byte vengono letti nell'ordine meno significativo in bit. Quando vengono letti più bit contemporaneamente, il numero intero viene creato a partire dai dati originali nell'ordine originale. I bit più significativi del numero intero restituito sono anche i bit più significativi dei dati originali. Pertanto, la dichiarazione

b = ReadBits(2);

equivale alle due dichiarazioni seguenti:

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

Supponiamo che ogni componente del colore, ovvero alfa, rosso, blu e verde, sia rappresentato utilizzando un byte a 8 bit. Definiamo il tipo corrispondente come uint8. Un pixel ARGB completo è rappresentato da un tipo chiamato uint32, ovvero un numero intero non firmato costituito da 32 bit. Nel codice che mostra il comportamento delle trasformazioni, questi valori sono codificati nei seguenti bit: alfa nei bit 31..24, rosso nei bit 23..16, verde nei bit 15..8 e blu nei bit 7..0. Tuttavia, le implementazioni del formato sono libere di utilizzare un'altra rappresentazione interna.

In generale, un'immagine senza perdita di dati WebP contiene dati di intestazione, informazioni sulla trasformazione e dati effettivi dell'immagine. Le intestazioni contengono la larghezza e l'altezza dell'immagine. Un'immagine WebP senza perdita di dati può subire quattro tipi diversi di trasformazioni prima di essere codificata entropia. Le informazioni sulla trasformazione nel flusso di bit contengono i dati necessari per applicare le rispettive trasformazioni inverse.

2 Nomenclatura

ARGB

Un valore di pixel composto da valori alfa, rosso, verde e blu.

Immagine ARGB

Un array bidimensionale contenente pixel ARGB.

cache dei colori

Un piccolo array con indirizzi hash per archiviare i colori utilizzati di recente in modo da poterli richiamare con codici più brevi.

immagine di indicizzazione dei colori

Un'immagine unidimensionale di colori che possono essere indicizzati utilizzando un numero intero piccolo (fino a 256 in WebP senza perdita di dati).

immagine con trasformazione del colore

Un'immagine a sottorisoluzione bidimensionale contenente dati sulle correlazioni tra componenti di colore.

mappatura distanza

Modifica le distanze LZ77 in modo che abbiano i valori più bassi per i pixel in prossimità bidimensionale.

immagine di entropia

Un'immagine a sottorisoluzione bidimensionale che indica quale codifica entropia deve essere utilizzata in un rispettivo quadrato nell'immagine, ovvero ogni pixel è un codice prefisso.

LZ77

Un algoritmo di compressione di finestre scorrevoli basato su dizionario che emette simboli o li descrive come sequenze di simboli del passato.

meta prefisso codice

Un piccolo numero intero (fino a 16 bit) che indicizza un elemento nella tabella del prefisso del meta.

immagine predittore

Un'immagine a sottorisoluzione bidimensionale che indica quale predittore spaziale viene utilizzato per un determinato quadrato nell'immagine.

prefisso

Un modo classico per effettuare la codifica entropia in cui viene utilizzato un numero minore di bit per codici più frequenti.

codifica prefisso

Un modo per entropia di codificare numeri interi più grandi, che codifica alcuni bit del numero intero utilizzando un codice entropia e codifica i bit rimanenti non elaborati. In questo modo le descrizioni dei codici entropia rimangono relativamente piccole anche quando l'intervallo di simboli è ampio.

ordine riga di scansione

Un ordine di elaborazione dei pixel (da sinistra a destra e dall'alto in basso), a partire dal pixel in alto a sinistra. Una volta completata una riga, continua dalla colonna di sinistra della riga successiva.

3 Intestazione RIFF

All'inizio dell'intestazione si trova il container RIFF. Si compone dei seguenti 21 byte:

1. Stringa "RIFF".
2. Un valore small-endian a 32 bit della lunghezza del blocco, ovvero l'intera dimensione del blocco controllato dall'intestazione RIFF. Normalmente, corrisponde alle dimensioni del payload (dimensione del file meno 8 byte: 4 byte per l'identificatore "RIFF" e 4 byte per l'archiviazione del valore stesso).
3. Stringa "WEBP" (nome contenitore RIFF).
4. Stringa "VP8L" (FourCC per dati di immagini con codifica senza perdita di dati).
5. Un valore small-endian a 32 bit del numero di byte nel flusso senza perdita di dati.
6. Firma a 1 byte 0x2f.

I primi 28 bit del flusso di bit specificano la larghezza e l'altezza dell'immagine. Larghezza e altezza sono decodificate come numeri interi a 14 bit come segue:

int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;

La precisione a 14 bit per la larghezza e l'altezza dell'immagine limita le dimensioni massime di un'immagine senza perdita di dati WebP a 16.384 x 16.384 pixel.

Il bit alpha_is_used è solo un suggerimento e non dovrebbe influire sulla decodifica. Deve essere impostato su 0 quando tutti i valori alfa sono 255 nell'immagine e 1 negli altri casi.

int alpha_is_used = ReadBits(1);

version_number è un codice a 3 bit che deve essere impostato su 0. Qualsiasi altro valore dovrebbe essere considerato un errore.

int version_number = ReadBits(3);

4 trasformazioni

Le trasformazioni sono manipolazioni reversibili dei dati dell'immagine che possono ridurre l'entropia simbolica rimanente mediante la modellazione delle correlazioni spaziali e cromatiche. Possono rendere la compressione finale più densa.

Un'immagine può essere sottoposta a quattro tipi di trasformazioni. Un bit indica la presenza di una trasformazione. Ogni trasformazione può essere utilizzata una sola volta. Le trasformazioni vengono utilizzate solo per l'immagine ARGB a livello principale; le immagini a subrisoluzione (immagine trasformazione colore, immagine entropia e immagine predittiva) non hanno trasformazioni, nemmeno lo 0 bit indica la fine delle trasformazioni.

In genere, un encoder utilizza queste trasformazioni per ridurre l'entropia di Shannon nell'immagine residua. Inoltre, i dati di trasformazione possono essere decisi in base alla minimizzazione di 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 è presente una trasformazione, i due bit successivi specificano il tipo di trasformazione. Esistono quattro tipi di trasformazioni.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

Il tipo di trasformazione è seguito dai dati di trasformazione. I dati di trasformazione contengono le informazioni necessarie per applicare la trasformazione inversa e dipendono dal tipo di trasformazione. Le trasformazioni inverse vengono applicate nell'ordine inverso in cui vengono lette dal bitstream, ovvero prima dell'ultima.

Quindi, descriviamo i dati delle trasformazioni per tipi diversi.

4.1 Trasformazione del preveditore

La trasformazione predittiva può essere utilizzata per ridurre l'entropia sfruttando il fatto che i pixel vicini sono spesso correlati. Nella trasformazione predittiva, il valore di pixel corrente viene previsto dai pixel già decodificati (nell'ordine della riga di scansione) e solo il valore residuo (effettivo - previsto) viene codificato. Il componente verde di un pixel definisce quale dei 14 predittori viene utilizzato all'interno di un determinato blocco dell'immagine ARGB. La modalità di previsione determina il tipo di previsione da utilizzare. Dividiamo l'immagine in quadrati e tutti i pixel di un quadrato utilizzano la stessa modalità di previsione.

I primi 3 bit di dati di previsione definiscono la larghezza e l'altezza del blocco in numero di bit.

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

I dati della trasformazione contengono la modalità di previsione per ogni blocco dell'immagine. È un'immagine a sottorisoluzione in cui il componente verde di un pixel definisce quale dei 14 predittori viene utilizzato per tutti i block_width * block_height pixel all'interno di un determinato blocco dell'immagine ARGB. Questa immagine a subrisoluzione viene codificata utilizzando le stesse tecniche descritte nel Capitolo 5.

Il numero di colonne di blocchi, transform_width, viene utilizzato nell'indicizzazione bidimensionale. Per un pixel (x, y), è possibile calcolare l'indirizzo del blocco filtro corrispondente:

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

Esistono 14 diverse modalità di previsione. In ciascuna modalità di previsione, il valore del pixel corrente viene previsto da uno o più pixel vicini i cui valori sono già noti.

Abbiamo scelto i pixel vicini (TL, T, TR e L) del pixel corrente (P) come segue:

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

dove TL significa in alto a sinistra, T significa in alto, TR significa in alto a destra e L significa a sinistra. Al momento della previsione di un valore per P, tutti i pixel O, TL, T, TR e L sono già stati elaborati e il pixel P e tutti i pixel X sono sconosciuti.

Dati i pixel vicini precedenti, le diverse modalità di previsione sono definite come segue.

Modalità	Valore previsto di ciascun canale del pixel corrente
0	0xff000000 (rappresenta il colore nero a tinta unita in ARGB)
1	L
2	T
3	TR
4	TL
5	Media2(Media2(L, TR), T)
6	Media2(L, TL)
7	Media2(L, T)
8	Media2(TL, T)
9	Media2(T, TR)
10	Media2(Media2(L; TL); Media2(T; TR))
11	Seleziona(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

Average2 viene definito come segue per ciascun componente ARGB:

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

Il predittore Seleziona è definito come segue:

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;
  }
}

Le funzioni ClampAddSubtractFull e ClampAddSubtractHalf vengono eseguite per ciascun componente ARGB nel seguente modo:

// 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);
}

Esistono regole di gestione speciali per alcuni pixel del bordo. Se è presente una trasformazione di previsione, indipendentemente dalla modalità [0..13] per questi pixel, il valore previsto per il pixel più in alto a sinistra dell'immagine è 0xff000000, tutti i pixel nella riga superiore sono L-pixel e tutti i pixel nella colonna più a sinistra sono T-pixel.

Indirizzare i pixel TR per i pixel nella colonna più a destra è eccezionale. I pixel nella colonna più a destra vengono previsti utilizzando le modalità [0..13], proprio come i pixel non sul bordo, ma il pixel più a sinistra sulla stessa riga del pixel corrente viene utilizzato come pixel TR.

Il valore del pixel finale si ottiene aggiungendo ogni canale del valore previsto al valore residuo codificato.

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 Trasformazione del colore

L'obiettivo della trasformazione del colore è decorare i valori di R, G e B di ciascun pixel. La trasformazione del colore mantiene il valore verde (G) così com'è, trasforma il valore rosso (R) in base a quello verde e trasforma il valore blu (B) in base al valore verde e poi a quello rosso.

Come nel caso della trasformazione predittiva, prima l'immagine viene divisa in blocchi e viene utilizzata la stessa modalità di trasformazione per tutti i pixel in un blocco. Per ogni blocco, esistono tre tipi di elementi di trasformazione del colore.

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

L'effettiva trasformazione del colore viene eseguita definendo un delta di trasformazione del colore. Il delta della trasformazione del colore dipende dal valore ColorTransformElement, che è lo stesso per tutti i pixel di un determinato blocco. Il delta viene sottratto durante la trasformazione del colore. La trasformazione del colore inverso non è altro che l'aggiunta dei delta.

La funzione di trasformazione del colore viene definita come segue:

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;
}

Il valore ColorTransformDelta viene calcolato utilizzando un numero intero a 8 bit firmato che rappresenta un numero a 3,5 punti fissi e un canale di colore RGB a 8 bit firmato (c) [-128..127] ed è definito come segue:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

Prima di chiamare ColorTransformDelta(), è necessaria una conversione dalla rappresentazione non firmata a 8 bit (uint8) alla rappresentazione con firma a 8 bit (int8). Il valore firmato deve essere interpretato come un numero in complemento a due a 8 bit (ossia, l'intervallo uint8 [128..255] è mappato all'intervallo [-128..-1] del relativo valore int8 convertito).

La moltiplicazione deve essere eseguita utilizzando una maggiore precisione (con una precisione di almeno 16 bit). La proprietà dell'estensione del segno dell'operazione di spostamento non è importante qui; dal risultato vengono utilizzati solo gli 8 bit più bassi e qui lo spostamento dell'estensione del segno e lo spostamento senza segno sono coerenti tra loro.

Ora descriviamo i contenuti dei dati sulla trasformazione del colore, in modo che la decodifica possa applicare la trasformazione di colore inverso e recuperare i valori rosso e blu originali. I primi 3 bit dei dati sulla trasformazione del colore contengono la larghezza e l'altezza del blocco dell'immagine in numero di bit, proprio come la trasformazione predittiva:

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

La parte rimanente dei dati sulla trasformazione del colore contiene ColorTransformElement istanze, corrispondenti a ogni blocco dell'immagine. Ciascun 'cte' ColorTransformElement viene trattato come un pixel in un'immagine a subrisoluzione il cui componente alfa è 255, il componente rosso è cte.red_to_blue, il componente verde è cte.green_to_blue e il componente blu è cte.green_to_red.

Durante la decodifica, le istanze ColorTransformElement dei blocchi vengono decodificate e la trasformazione del colore inverso viene applicata ai valori ARGB dei pixel. Come accennato in precedenza, la trasformazione del colore inverso aggiunge solo valori ColorTransformElement ai canali rosso e blu. I canali alfa e verde sono rimasti invariati.

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 Sottrai la trasformazione verde

La trasformazione di sottrazione di verde sottrae i valori verdi dai valori rosso e blu di ciascun pixel. Quando è presente questa trasformazione, il decoder deve aggiungere il valore verde a entrambi i valori rosso e blu. Non esistono dati associati a questa trasformazione. Il decoder applica la trasformazione inversa come segue:

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

Questa trasformazione è ridondante, in quanto può essere modellata utilizzando la trasformazione del colore. Tuttavia, poiché qui non ci sono dati aggiuntivi, la trasformazione verde sottrazione può essere codificata utilizzando meno bit rispetto a una trasformazione colore completa.

4.4 Trasformazione dell'indicizzazione dei colori

Se non ci sono molti valori di pixel univoci, potrebbe essere più efficiente creare un array di indice dei colori e sostituire i valori dei pixel con gli indici dell'array. La trasformazione di indicizzazione dei colori permette di ottenere questo risultato. (Nel contesto di WebP senza perdita di dati, nello specifico non chiamiamo questa trasformazione tavolozza perché esiste un concetto simile ma più dinamico nella codifica WebP senza perdita di dati: cache dei colori).

La trasformazione di indicizzazione dei colori controlla il numero di valori ARGB univoci nell'immagine. Se il numero è inferiore a una soglia (256), viene creato un array di questi valori ARGB, che viene quindi utilizzato per sostituire i valori dei pixel con l'indice corrispondente: il canale verde dei pixel viene sostituito con l'indice, tutti i valori alfa vengono impostati su 255 e tutti i valori rosso e blu sono pari a 0.

I dati della trasformazione contengono le dimensioni della tabella colori e le voci nella tabella dei colori. Il decoder legge i dati della trasformazione di indicizzazione dei colori come segue:

// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;

La tabella dei colori viene archiviata utilizzando il formato di archiviazione delle immagini stesso. La tabella dei colori può essere ottenuta leggendo un'immagine, senza l'intestazione RIFF, le dimensioni dell'immagine e le trasformazioni, assumendo l'altezza di 1 pixel e la larghezza di color_table_size. La tabella dei colori è sempre codificata tramite sottrazione per ridurre l'entropia dell'immagine. I delta dei colori della tavolozza contengono in genere molto meno entropia rispetto ai colori stessi, il che comporta risparmi significativi per le immagini più piccole. Durante la decodifica, ogni colore finale della tabella dei colori può essere ottenuto aggiungendo separatamente i valori dei componenti di colore precedenti per ogni componente ARGB e memorizzando gli 8 bit meno significativi del risultato.

La trasformazione inversa dell'immagine sostituisce semplicemente i valori dei pixel (che sono indici della tabella dei colori) con i valori effettivi della tabella dei colori. L'indicizzazione viene eseguita in base alla componente verde del colore ARGB.

// Inverse transform
argb = color_table[GREEN(argb)];

Se l'indice è uguale o superiore a color_table_size, il valore del colore agsuite deve essere impostato su 0x00000000 (nero trasparente).

Quando la tabella dei colori è piccola (uguale o inferiore a 16 colori), diversi pixel vengono raggruppati in un unico pixel. Il raggruppamento di pixel racchiude diversi (2, 4 o 8) pixel in un unico pixel, riducendo rispettivamente la larghezza dell'immagine. Il raggruppamento di pixel consente una codifica entropia di distribuzione congiunta più efficiente dei pixel vicini e offre vantaggi simili alla codifica aritmetica al codice entropia, ma può essere utilizzato solo se ci sono al massimo 16 valori univoci.

color_table_size specifica quanti pixel vengono combinati:

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 ha un valore pari a 0, 1, 2 o 3. Il valore 0 indica che non è necessario eseguire alcun raggruppamento di pixel per l'immagine. Un valore pari a 1 indica che sono stati combinati due pixel e che ogni pixel ha un intervallo di [0..15]. Un valore pari a 2 indica che vengono combinati quattro pixel e che ogni pixel ha un intervallo di [0..3]. Un valore pari a 3 indica che vengono combinati otto pixel e che ogni pixel ha un intervallo di [0..1], ovvero un valore binario.

I valori vengono inseriti nel componente verde come segue:

• width_bits = 1: per ogni valore x, dove x ≡ 0 (mod 2), un valore verde in x viene inserito nei 4 bit meno significativi del valore verde in x / 2, mentre un valore verde in x + 1 viene inserito tra i 4 bit più significativi del valore verde in x / 2.
• width_bits = 2: per ogni valore x, dove x ≡ 0 (mod 4), un valore verde in x viene inserito nei 2 bit meno significativi del valore verde in x / 4, mentre i valori verdi in x + 1 a x + 3 vengono posizionati in ordine dei bit più significativi del valore verde in x / 4.
• width_bits = 3: per ogni valore x, dove x ≡ 0 (mod 8), un valore verde in x viene posizionato nel bit meno significativo del valore verde in x / 8, mentre i valori verdi in x + 1 a x + 7 vengono posizionati in ordine dei bit più significativi del valore verde in x / 8.

Dopo aver letto questa trasformazione, image_width viene sottocampionato da width_bits. Questo influisce sulle dimensioni delle trasformazioni successive. La nuova dimensione può essere calcolata utilizzando DIV_ROUND_UP, come definito in precedenza.

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

5 Dati immagine

I dati di immagine sono un array di valori di pixel in ordine di riga di scansione.

5.1 Ruoli dei dati delle immagini

Utilizziamo i dati delle immagini in cinque diversi ruoli:

1. Immagine ARGB: memorizza i pixel effettivi dell'immagine.
2. Immagine entropia: memorizza i codici del meta prefisso (consulta la sezione "Decodifica dei codici del prefisso del meta").
3. Immagine predittore: archivia i metadati per la trasformazione predittiva (consulta la sezione "Trasformazione predittore").
4. Immagine con trasformazione del colore: creata da valori ColorTransformElement (definiti in "Trasformazione colore") per diversi blocchi dell'immagine.
5. Immagine di indicizzazione dei colori: un array di dimensioni color_table_size (fino a 256 valori ARGB) che memorizza i metadati per la trasformazione di indicizzazione dei colori (consulta la sezione "Trasformazione di indicizzazione dei colori").

5.2 Codifica dei dati delle immagini

La codifica dei dati delle immagini è indipendente dal loro ruolo.

L'immagine viene prima divisa in un insieme di blocchi a dimensioni fisse (in genere blocchi di 16 x 16). Ciascuno di questi blocchi viene modellato utilizzando i propri codici entropia. Inoltre, diversi blocchi possono condividere gli stessi codici entropia.

Motivazione:l'archiviazione di un codice entropia prevede un costo. Questo costo può essere ridotto al minimo se blocchi statisticamente simili condividono un codice entropia, memorizzando così il codice una sola volta. Ad esempio, un codificatore può trovare blocchi simili raggruppandoli utilizzando le loro proprietà statistiche o unendo ripetutamente una coppia di cluster selezionati casualmente quando si riduce la quantità complessiva di bit necessaria per codificare l'immagine.

Ogni pixel viene codificato utilizzando uno dei tre metodi possibili:

1. Valori letterali codificati con prefisso: ogni canale (verde, rosso, blu e alfa) è codificato entropia in modo indipendente.
2. Riferimento indietro LZ77: una sequenza di pixel viene copiata altrove nell'immagine.
3. Codice cache dei colori: utilizzo di un breve codice hash moltiplicativo (indice di cache dei colori) di un colore rilevato di recente.

Nelle sottosezioni seguenti sono descritti in dettaglio ognuno di questi elementi.

5.2.1 Valori letterali con prefisso

Il pixel viene memorizzato come valori codificati in prefisso di verde, rosso, blu e alfa (in questo ordine). Consulta la Sezione 6.2.3 per i dettagli.

5.2.2 Riferimento indietro LZ77

I riferimenti a ritroso sono tuple di length e distance code:

• La lunghezza indica il numero di pixel da copiare in ordine di riga di scansione.
• Il codice distanza è un numero che indica la posizione di un pixel precedentemente rilevato, da cui devono essere copiati i pixel. Il mapping esatto è descritto di seguito.

I valori di lunghezza e distanza vengono memorizzati utilizzando la codifica del prefisso LZ77.

La codifica del prefisso LZ77 suddivide i valori interi grandi in due parti: il codice del prefisso e i bit aggiuntivi. Il codice del prefisso viene memorizzato utilizzando un codice entropia, mentre i bit aggiuntivi vengono archiviati così come sono (senza codice entropia).

Motivazione: questo approccio riduce il requisito di archiviazione per il codice entropia. Inoltre, i valori grandi sono in genere rari, quindi i bit extra verranno utilizzati solo per pochissimi valori nell'immagine. Questo approccio si traduce in una migliore compressione nel complesso.

La seguente tabella indica i codici dei prefissi e i bit aggiuntivi utilizzati per memorizzare diversi intervalli di valori.

Intervallo di valori	Codice prefisso	Punte extra
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

Lo pseudocodice per ottenere un valore (lunghezza o distanza) dal codice del prefisso è il seguente:

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;

Mappatura delle distanze

Come indicato in precedenza, un codice di distanza è un numero che indica la posizione di un pixel precedentemente rilevato, da cui devono essere copiati i pixel. Questa sottosezione definisce la mappatura tra un codice di distanza e la posizione di un pixel precedente.

I codici di distanza superiori a 120 indicano la distanza in pixel nell'ordine della riga di scansione, con deviazione di 120.

I codici di distanza più piccoli [1..120] sono speciali e sono riservati a un vicino vicino del pixel corrente. Questo quartiere è costituito da 120 pixel:

• Pixel che si trovano da 1 a 7 righe sopra il pixel corrente e fino a 8 colonne a sinistra o fino a 7 colonne a destra del pixel corrente. [Totale di tali pixel = 7 * (8 + 1 + 7) = 112].
• Pixel che si trovano nella stessa riga del pixel corrente e fino a 8 colonne a sinistra del pixel corrente. [8 di questi pixel].

La mappatura tra il codice di distanza distance_code e l'offset di pixel vicini (xi, yi) è la seguente:

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

Ad esempio, il codice di distanza 1 indica un offset di (0, 1) per il pixel vicino, ovvero il pixel sopra il pixel corrente (differenza di 0 pixel nella direzione X e differenza di 1 pixel nella direzione Y). Analogamente, il codice di distanza 3 indica il pixel superiore sinistro.

Il decoder può convertire un codice di distanza distance_code in una distanza dell'ordine della riga di scansione dist come segue:

(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
  dist = 1
}

dove distance_map è la mappatura indicata sopra e image_width è la larghezza dell'immagine in pixel.

5.2.3 Codifica della cache colore

La cache dei colori memorizza un insieme di colori utilizzati di recente nell'immagine.

Motivazione: in questo modo, a volte è possibile fare riferimento ai colori utilizzati di recente in modo più efficiente rispetto alla loro emissione utilizzando gli altri due metodi (descritti in 5.2.1 e 5.2.2).

I codici cache dei colori vengono memorizzati nel seguente modo. Il primo è un valore a 1 bit che indica se si utilizza la cache dei colori. Se questo bit è pari a 0, non esistono codici cache colore e non vengono trasmessi nel codice del prefisso che decodifica i simboli verdi e i codici del prefisso della lunghezza. Tuttavia, se questo bit è 1, la dimensione della cache dei colori viene letta come segue:

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits definisce la dimensione della cache dei colori (1 << color_cache_code_bits). L'intervallo di valori consentiti per color_cache_code_bits è [1..11]. I decoder conformi devono indicare un flusso di bit danneggiato per altri valori.

Una cache dei colori è un array di dimensioni color_cache_size. Ogni voce memorizza un colore ARGB. I colori vengono cercati indicizzandoli in base a (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Viene eseguita una sola ricerca nella cache dei colori, senza risoluzione dei conflitti.

All'inizio della decodifica o codifica di un'immagine, tutte le voci in tutti i valori della cache a colori vengono impostate su zero. Il codice della cache dei colori viene convertito in questo colore durante il momento della decodifica. Lo stato della cache dei colori viene mantenuto inserendo ogni pixel, prodotto tramite riferimento a ritroso o valori letterali, nella cache nell'ordine in cui appaiono nel flusso.

6 Codice entropia

6.1 Panoramica

La maggior parte dei dati è codificata utilizzando un codice prefisso canonico. Di conseguenza, i codici vengono trasmessi inviando le lunghezze dei codici del prefisso, anziché gli effettivi codici del prefisso.

In particolare, il formato utilizza la codifica del prefisso delle varianti spaziali. In altre parole, blocchi diversi dell'immagine possono utilizzare codici entropia diversi.

Motivazione: aree diverse dell'immagine possono avere caratteristiche diverse. Pertanto, consentire loro di utilizzare diversi codici di entropia offre maggiore flessibilità e una compressione potenzialmente migliore.

6.2 Dettagli

I dati delle immagini codificate sono costituiti da diverse parti:

1. Decodifica e creazione dei codici dei prefissi.
2. Codici di meta prefisso.
3. Dati di immagini con codifica entropia.

A ogni pixel (x, y) è associato un insieme di cinque prefissi. Questi codici sono (in ordine di flusso di bit):

• Codice prefisso n. 1: utilizzato per il canale verde, la lunghezza di riferimento indietro e la cache dei colori.
• Codice prefisso #2, #3 e #4: utilizzato rispettivamente per i canali rosso, blu e alfa.
• Codice prefisso n. 5: utilizzato per la distanza di riferimento a ritroso.

D'ora in poi, facciamo riferimento a questo insieme come a un gruppo di codici di prefisso.

6.2.1 Decodifica e creazione dei codici di prefisso

Questa sezione descrive come leggere le lunghezze del codice del prefisso dal bitstream.

La lunghezza del codice del prefisso può essere codificata in due modi. Il metodo utilizzato è specificato da un valore a 1 bit.

• Se questo bit corrisponde a 1, è un codice semplice con lunghezza di codice.
• Se questo bit corrisponde a 0, si tratta di un codice a lunghezza normale.

In entrambi i casi, potrebbero esserci lunghezze di codice inutilizzate che fanno ancora parte del flusso. Potrebbe non essere efficace, ma è consentito dal formato. La struttura ad albero descritta deve essere un albero binario completo. Un singolo nodo foglia è considerato un albero binario completo e può essere codificato utilizzando il codice di lunghezza del codice semplice o il codice di lunghezza normale del codice. Quando codifichi un nodo foglia utilizzando il codice con lunghezza del codice normale, tutte le lunghezze del codice tranne una sono zeri e il valore del nodo foglia è contrassegnato con la lunghezza 1, anche se non vengono consumati bit quando viene utilizzato l'albero di nodo foglia singolo.

Codice lunghezza codice semplice

Questa variante viene utilizzata nel caso speciale quando solo 1 o 2 simboli di prefisso rientrano nell'intervallo [0..255] con lunghezza del codice 1. Tutte le altre lunghezze del codice prefisso sono implicitamente zeri.

Il primo bit indica il numero di simboli:

int num_symbols = ReadBits(1) + 1;

Di seguito sono riportati i valori dei simboli.

Questo primo simbolo è codificato utilizzando 1 o 8 bit, a seconda del valore di is_first_8bits. L'intervallo è rispettivamente [0..1] o [0..255]. Si presume sempre che il secondo simbolo, se presente, rientri nell'intervallo [0..255] e sia codificato utilizzando 8 bit.

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;
}

I due simboli devono essere diversi. Sono consentiti simboli duplicati, ma inefficienti.

Nota: un altro caso speciale si verifica quando tutte le lunghezze del codice del prefisso sono zeri (un codice del prefisso vuoto). Ad esempio, il prefisso per la distanza può essere vuoto se non ci sono riferimenti a ritroso. Allo stesso modo, i codici dei prefissi per le versioni alfa, rosso e blu possono essere vuoti se tutti i pixel all'interno dello stesso codice del prefisso meta vengono generati utilizzando la cache dei colori. Tuttavia, questo caso non richiede una gestione speciale, poiché i codici dei prefissi vuoti possono essere codificati come quelli contenenti un singolo simbolo 0.

Codice lunghezza normale

Le lunghezze del codice del prefisso rientrano in 8 bit e vengono lette come segue. Innanzitutto, num_code_lengths specifica il numero di lunghezze del codice.

int num_code_lengths = 4 + ReadBits(4);

Le lunghezze dei codici vengono codificate a loro volta utilizzando codici di prefisso; le lunghezze dei codici di livello inferiore, code_length_code_lengths, devono prima essere lette. Il resto di questi code_length_code_lengths (in base all'ordine in kCodeLengthCodeOrder) sono zeri.

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);
}

Successivamente, se ReadBits(1) == 0, il numero massimo di simboli di lettura diversi (max_symbol) per ogni tipo di simbolo (A, R, G, B e distanza) viene impostato sulle dimensioni dell'alfabeto:

• Canale G: 256 + 24 + color_cache_size
• Altri valori letterali (A, R e B): 256
• Codice distanza: 40

In caso contrario, si definisce come:

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

Se max_symbol è superiore alle dimensioni dell'alfabeto per il tipo di simbolo, il flusso di bit non è valido.

Viene quindi creata una tabella con prefisso a partire da code_length_code_lengths e utilizzata per leggere fino a max_symbol lunghezze di codice.

• Il codice [0..15] indica le lunghezze del codice letterale.
  • Il valore 0 indica che non è stato codificato alcun simbolo.
  • I valori [1..15] indicano la lunghezza in bit del rispettivo codice.
• Il codice 16 ripete il precedente valore diverso da zero [3..6] volte, ovvero 3 + ReadBits(2) volte. Se viene utilizzato il codice 16 prima di emettere un valore diverso da zero, viene ripetuto il valore 8.
• Il codice 17 emette una serie di zeri di lunghezza [3..10], ovvero 3 + ReadBits(3) volte.
• Il codice 18 emette una serie di zeri di lunghezza [11..138], ovvero 11 + ReadBits(7) volte.

Una volta lette le lunghezze dei codici, si forma un prefisso per ogni tipo di simbolo (A, R, G, B e distanza) utilizzando le rispettive dimensioni dell'alfabeto.

Il codice con lunghezza del codice normale deve codificare un albero decisionale completo, ovvero la somma di 2 ^ (-length) per tutti i codici diversi da zero deve essere esattamente uno. Esiste tuttavia un'eccezione a questa regola, l'albero di nodo foglia, in cui il valore del nodo foglia è contrassegnato con il valore 1 e gli altri valori sono 0.

6.2.2 Decodifica dei codici di meta-prefisso

Come indicato in precedenza, il formato consente l'utilizzo di prefissi diversi per blocchi differenti dell'immagine. I codici prefissi meta sono indici che identificano i codici di prefisso da utilizzare in diverse parti dell'immagine.

I codici del meta prefisso possono essere utilizzati solo quando l'immagine viene utilizzata nel ruolo di un'immagine ARGB.

Esistono due possibilità per i codici del meta prefisso, indicati da un valore a 1 bit:

• Se questo bit è pari a zero, viene utilizzato un solo codice con prefisso meta ovunque nell'immagine. I dati non vengono più archiviati.
• Se questo bit è uno, l'immagine utilizza più codici di meta prefisso. Questi meta codici di prefisso vengono memorizzati come un'immagine entropia (descritta di seguito).

I componenti rosso e verde di un pixel definiscono il codice del meta prefisso a 16 bit utilizzato in un determinato blocco dell'immagine ARGB.

Immagine entropia

L'immagine entropia definisce quali codici prefisso vengono utilizzati in diverse parti dell'immagine.

I primi 3 bit contengono il valore prefix_bits. Le dimensioni dell'immagine entropia derivano da 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);

dove DIV_ROUND_UP è definito in precedenza.

I bit successivi contengono un'immagine entropia di larghezza prefix_image_width e altezza prefix_image_height.

Interpretazione dei codici di prefisso

Il numero di gruppi di codici prefisso nell'immagine ARGB può essere ottenuto individuando il codice prefisso meta più grande dall'immagine entropia:

int num_prefix_groups = max(entropy image) + 1;

dove max(entropy image) indica il codice prefisso più grande archiviato nell'immagine entropia.

Poiché ogni gruppo di codici di prefisso contiene cinque codici di prefisso, il numero totale di codici di prefisso è:

int num_prefix_codes = 5 * num_prefix_groups;

Dato un pixel (x, y) nell'immagine ARGB, possiamo ottenere i codici prefissi corrispondenti da utilizzare come segue:

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];

dove abbiamo ipotizzato l'esistenza della struttura PrefixCodeGroup, che rappresenta un insieme di cinque codici di prefissi. Inoltre, prefix_code_groups è un array di PrefixCodeGroup (di dimensione num_prefix_groups).

Il decoder utilizza quindi il gruppo di codice prefisso prefix_group per decodificare il pixel (x, y), come spiegato in "Decodifica dei dati delle immagini con codifica entropia".

6.2.3 Decodifica dei dati delle immagini con codifica entropia

Per la posizione corrente (x, y) nell'immagine, il decoder identifica prima il gruppo di codice prefisso corrispondente (come spiegato nell'ultima sezione). Dato il gruppo di codici del prefisso, il pixel viene letto e decodificato come segue.

Quindi, leggi il simbolo S del bitstream usando il prefisso codice #1. Tieni presente che S è un numero intero compreso nell'intervallo da 0 a (256 + 24 + color_cache_size- 1).

L'interpretazione di S dipende dal suo valore:

1. Se S < 256
   1. Usa S come componente verde.
   2. Leggi in rosso dal bitstream utilizzando il codice prefisso 2.
   3. Leggi in blu dal bitstream utilizzando il codice prefisso 3.
   4. Leggi la versione alpha dal bitstream utilizzando il codice prefisso 4.
2. Se S >= 256 e S < 256 + 24
   1. Utilizza S - 256 come prefisso di lunghezza.
   2. Leggi i bit aggiuntivi per la lunghezza dal flusso di bit.
   3. Determina la lunghezza di riferimento a ritroso L dal codice del prefisso della lunghezza e dai bit aggiuntivi letti.
   4. Leggi il codice del prefisso della distanza dal bitstream utilizzando il codice del prefisso #5.
   5. Leggi i bit aggiuntivi per la distanza dal flusso di bit.
   6. Determina la distanza di riferimento a ritroso D dal codice del prefisso della distanza e dai bit aggiuntivi letti.
   7. Copia L pixel (nell'ordine della riga di scansione) dalla sequenza di pixel a partire dalla posizione attuale meno D pixel.
3. Se S >= 256 + 24
   1. Usa S - (256 + 24) come indice nella cache dei colori.
   2. Recupera il colore ARGB dalla cache dei colori in quell'indice.

7 Struttura complessiva del formato

Di seguito è riportata una visualizzazione nel formato in Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Non tratta tutti i dettagli. La fine dell'immagine (EOI) viene codificata implicitamente nel numero di pixel (image_width * image_height).

Tieni presente che *element significa che element può essere ripetuto 0 o più volte. 5element significa che element viene ripetuto esattamente 5 volte. %b rappresenta un valore binario.

7.1 Struttura di base

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 Struttura delle trasformazioni

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 Struttura dei dati delle immagini

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)

Di seguito è riportata una possibile sequenza di esempio:

RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image