Specifiche per WebP Lossless Bitstream

Jyrki Alakuijala, Ph.D., Google, Inc., 09/03/2023

Abstract

WebP lossless è un formato di immagine per la compressione senza perdita di dati delle immagini ARGB. Il formato senza perdita memorizza e ripristina esattamente i valori dei pixel, inclusi i valori di colore per i pixel completamente trasparenti. Per la compressione dei dati collettivi vengono utilizzati un algoritmo universale per la compressione sequenziale dei dati (LZ77), la codifica dei prefissi e una cache dei colori. Sono state dimostrate velocità di decodifica più veloci rispetto a PNG, nonché una compressione più densa del 25% rispetto a quella ottenibile con il formato PNG attuale.

1 Introduzione

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

In questo documento utilizziamo ampiamente la sintassi del linguaggio di programmazione C per descrivere il bitstream e presupponiamo l'esistenza di una funzione per la lettura dei bit,ReadBits(n). I byte vengono letti nell'ordine naturale dello stream che li contiene e i bit di ogni byte vengono letti nell'ordine del bit meno significativo. Quando vengono letti più bit contemporaneamente, l'intero viene costruito dai dati originali nell'ordine originale. I bit più significativi dell'intero restituito sono anche i bit più significativi dei dati originali. Pertanto, l'affermazione

b = ReadBits(2);

è equivalente alle due seguenti dichiarazioni:

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

Supponiamo che ogni componente di colore, ovvero alfa, rosso, blu e verde, sia rappresentato utilizzando un byte a 8 bit. Definiamo il tipo corrispondente come uint8. Un pixel ARGB intero è rappresentato da un tipo chiamato uint32, che è un numero intero senza segno composto 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 internamente un'altra rappresentazione.

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

2 Nomenclatura

ARGB

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

Immagine ARGB

Un array bidimensionale contenente pixel ARGB.

cache dei colori

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

immagine con indicizzazione dei colori

Un'immagine unidimensionale di colori che può essere indicizzata utilizzando un piccolo numero intero (fino a 256 in WebP lossless).

immagine di trasformazione del colore

Un'immagine bidimensionale a risoluzione secondaria contenente dati sulle correlazioni dei componenti di colore.

mappatura della distanza

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

immagine di entropia

Un'immagine bidimensionale a risoluzione secondaria che indica quale codifica entropica deve essere utilizzata in un quadrato corrispondente dell'immagine, ovvero ogni pixel è un meta prefisso.

LZ77

Un algoritmo di compressione a finestra scorrevole basato su dizionario che emette simboli o li descrive come sequenze di simboli passati.

codice prefisso meta

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

immagine del pronostico

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

codice prefisso

Un modo classico per eseguire la codifica entropica in cui viene utilizzato un numero inferiore di bit per i codici più frequenti.

codifica con prefisso

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

ordine di scansione

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

3 RIFF Header

L'inizio dell'intestazione contiene il container RIFF. È costituito dai seguenti 21 byte:

1. Stringa "RIFF".
2. Un valore a 32 bit little-endian della lunghezza del chunk, ovvero la dimensione totale del chunk controllato dall'intestazione RIFF. Normalmente, questo valore è uguale alle dimensioni del payload (dimensioni del file meno 8 byte: 4 byte per l'identificatore "RIFF" e 4 byte per memorizzare il valore stesso).
3. Stringa "WEBP" (nome del contenitore RIFF).
4. Stringa "VP8L" (FourCC per i dati immagine codificati senza perdita).
5. Un valore a 32 bit little-endian del numero di byte nel flusso senza perdita.
6. Firma di 1 byte 0x2f.

I primi 28 bit del bitstream specificano la larghezza e l'altezza dell'immagine. La larghezza e l'altezza vengono decodificate come numeri interi a 14 bit nel seguente modo:

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 la dimensione massima di un'immagine WebP senza perdita a 16384 × 16384 pixel.

Il bit alpha_is_used è solo un suggerimento e non deve influire sulla decodifica. Deve essere impostato su 0 quando tutti i valori alfa sono 255 nell'immagine e su 1 in caso contrario.

int alpha_is_used = ReadBits(1);

version_number è un codice di 3 bit che deve essere impostato su 0. Qualsiasi altro valore deve 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 modellando le correlazioni spaziali e di colore. Possono rendere la compressione finale più densa.

Un'immagine può subire 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 di livello principale; le immagini a risoluzione secondaria (immagine di trasformazione del colore, immagine di entropia e immagine di previsione) non hanno trasformazioni, nemmeno il bit 0 che indica la fine delle trasformazioni.

In genere, un codificatore utilizza queste trasformazioni per ridurre l'entropia di Shannon nell'immagine residua. Inoltre, i dati di trasformazione possono essere decisi in base alla minimizzazione dell'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. Transform data contiene le informazioni necessarie per applicare la trasformazione inversa e dipende dal tipo di trasformazione. Le trasformazioni inverse vengono applicate nell'ordine inverso rispetto a quello in cui vengono lette dal bitstream, ovvero l'ultima per prima.

Successivamente, descriviamo la trasformazione dei dati per diversi tipi.

4.1 Trasformazione del predittore

La trasformazione del predittore può essere utilizzata per ridurre l'entropia sfruttando il fatto che i pixel vicini sono spesso correlati. Nella trasformazione del predittore, il valore del pixel corrente viene previsto dai pixel già decodificati (in ordine di scansione della riga) e viene codificato solo il valore residuo (effettivo - previsto). Il componente verde di un pixel definisce quale dei 14 predittori viene utilizzato all'interno di un particolare 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 dei 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 di trasformazione contengono la modalità di previsione per ogni blocco dell'immagine. Si tratta di un'immagine a risoluzione secondaria in cui il componente verde di un pixel definisce quale dei 14 predittori viene utilizzato per tutti i pixel block_width * block_height all'interno di un determinato blocco dell'immagine ARGB. Questa immagine a risoluzione secondaria viene codificata utilizzando le stesse tecniche descritte nel capitolo 5.

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

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

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

Abbiamo scelto i pixel adiacenti (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 indica in alto a sinistra, T indica in alto, TR indica in alto a destra e L indica 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 adiacenti precedenti, le diverse modalità di previsione sono definite come segue.

Average2 è definito come segue per ogni componente ARGB:

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

Il selettore di predittori è 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 ogni 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 di bordo. Se è presente una trasformazione del predittore, indipendentemente dalla modalità [0..13] per questi pixel, il valore previsto per il pixel in alto a sinistra dell'immagine è 0xff000000, tutti i pixel nella riga superiore sono pixel L e tutti i pixel nella colonna più a sinistra sono pixel T.

L'indirizzamento del pixel TR per i pixel nell'ultima colonna 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 invece utilizzato come pixel TR.

Il valore finale del pixel viene ottenuto sommando 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

Lo scopo della trasformazione del colore è decorrelare i valori R, G e B di ciascun pixel. La trasformazione del colore mantiene invariato il valore del verde (G), trasforma il valore del rosso (R) in base al valore del verde e trasforma il valore del blu (B) in base al valore del verde e poi a quello del rosso.

Come nel caso della trasformazione del predittore, l'immagine viene prima divisa in blocchi e la stessa modalità di trasformazione viene utilizzata per tutti i pixel di 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;

La trasformazione del colore effettiva viene eseguita definendo un delta di trasformazione del colore. Il delta di trasformazione del colore dipende dal ColorTransformElement, che è lo stesso per tutti i pixel di un determinato blocco. La differenza viene sottratta durante la trasformazione del colore. La trasformazione del colore inversa consiste quindi nell'aggiunta di questi delta.

La funzione di trasformazione del colore è 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;
}

ColorTransformDelta viene calcolato utilizzando un numero intero a 8 bit con segno che rappresenta un numero a virgola fissa 3.5 e un canale di colore RGB a 8 bit con segno (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 senza segno a 8 bit (uint8) a quella con segno a 8 bit (int8). Il valore con segno deve essere interpretato come un numero in complemento a due a 8 bit (ovvero l'intervallo uint8 [128..255] viene mappato all'intervallo [-128..-1] del relativo valore int8 convertito).

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

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

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

La parte rimanente dei dati di trasformazione del colore contiene ColorTransformElement istanze, corrispondenti a ogni blocco dell'immagine. Ogni ColorTransformElement 'cte' viene trattato come un pixel in un'immagine a risoluzione secondaria 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, vengono decodificate ColorTransformElement istanze dei blocchi e viene applicata la trasformazione inversa del colore ai valori ARGB dei pixel. Come accennato in precedenza, la trasformazione del colore inverso consiste semplicemente nell'aggiunta dei valori ColorTransformElement ai canali rosso e blu. I canali alfa e verde vengono lasciati 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 Trasformazione Sottrai verde

La trasformazione Sottrai verde sottrae i valori del verde dai valori del rosso e del blu di ogni pixel. Quando questa trasformazione è presente, il decodificatore deve aggiungere il valore verde sia al valore rosso che a quello blu. Non sono presenti dati associati a questa trasformazione. Il decoder applica la trasformazione inversa nel seguente modo:

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, ma poiché qui non sono presenti dati aggiuntivi, la trasformazione di sottrazione del verde può essere codificata utilizzando meno bit rispetto a una trasformazione del colore completa.

4.4 Trasformazione dell'indicizzazione dei colori

Se non ci sono molti valori di pixel unici, potrebbe essere più efficiente creare un array di indici di colore e sostituire i valori dei pixel con gli indici dell'array. La trasformazione dell'indicizzazione dei colori consente di ottenere questo risultato. Nel contesto di WebP lossless, non lo chiamiamo specificamente trasformazione della tavolozza perché esiste un concetto simile ma più dinamico nella codifica WebP lossless: la cache dei colori.

La trasformazione di indicizzazione dei colori verifica il numero di valori ARGB unici nell'immagine. Se questo numero è inferiore a una soglia (256), viene creato un array di questi valori ARGB, che viene poi 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 su 0.

I dati di trasformazione contengono le dimensioni della tabella dei colori e le voci della tabella dei colori. Il decoder legge i dati di trasformazione dell'indicizzazione del colore nel seguente modo:

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

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

La trasformazione inversa per l'immagine consiste semplicemente nel sostituire 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 al componente verde del colore ARGB.

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

Se l'indice è maggiore o uguale a color_table_size, il valore del colore ARGB 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 dei pixel unisce diversi pixel (2, 4 o 8) in un unico pixel, riducendo rispettivamente la larghezza dell'immagine. Il raggruppamento dei pixel consente una codifica dell'entropia con distribuzione congiunta più efficiente dei pixel adiacenti e offre alcuni vantaggi simili alla codifica aritmetica al codice di entropia, ma può essere utilizzato solo quando sono presenti 16 o meno valori unici.

color_table_size specifica il numero di pixel 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. Un valore pari a 0 indica che non deve essere eseguito il raggruppamento dei pixel per l'immagine. Un valore pari a 1 indica che due pixel sono combinati e ogni pixel ha un intervallo di [0..15]. Un valore pari a 2 indica che vengono combinati quattro pixel e ogni pixel ha un intervallo di valori compreso tra 0 e 3. Un valore di 3 indica che vengono combinati otto pixel e che ogni pixel ha un intervallo di [0..1], ovvero un valore binario.

I valori sono inseriti nel componente verde nel seguente modo:

• width_bits = 1: per ogni valore x, dove x ≡ 0 (mod 2), un valore verde in x viene posizionato nei 4 bit meno significativi del valore verde in x / 2 e un valore verde in x + 1 viene posizionato nei 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 posizionato nei 2 bit meno significativi del valore verde in x / 4 e i valori verdi in x + 1 a x + 3 vengono posizionati in ordine ai 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 e i valori verdi in x + 1 a x + 7 vengono posizionati in ordine nei bit più significativi del valore verde in x / 8.

Dopo aver letto questa trasformazione, image_width viene sottocampionato di width_bits. Questa impostazione 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 dell'immagine sono un array di valori dei pixel in ordine di scansione.

5.1 Ruoli dei dati immagine

Utilizziamo i dati delle immagini in cinque ruoli diversi:

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

5.2 Codifica dei dati immagine

La codifica dei dati dell'immagine è indipendente dal suo ruolo.

L'immagine viene prima suddivisa in un insieme di blocchi di dimensioni fisse (in genere 16x16 pixel). Ciascuno di questi blocchi viene modellato utilizzando i propri codici di entropia. Inoltre, più blocchi possono condividere gli stessi codici di entropia.

Motivazione:l'archiviazione di un codice di entropia comporta un costo. Questo costo può essere ridotto al minimo se i blocchi statisticamente simili condividono un codice di 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 in modo casuale quando riduce la quantità complessiva di bit necessari 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 con entropia in modo indipendente.
2. Riferimento all'indietro LZ77: una sequenza di pixel viene copiata da un'altra parte dell'immagine.
3. Codice cache colore: utilizza un codice hash moltiplicativo breve (indice della cache colore) di un colore visualizzato di recente.

Le seguenti sottosezioni descrivono in dettaglio ciascuna di queste opzioni.

5.2.1 Prefissi codificati

Il pixel viene memorizzato come valori codificati con prefisso di verde, rosso, blu e alfa (in questo ordine). Per maggiori dettagli, consulta la sezione 6.2.3.

5.2.2 Riferimento all'indietro LZ77

I riferimenti all'indietro sono tuple di lunghezza e codice di distanza:

• La lunghezza indica il numero di pixel da copiare nell'ordine della linea di scansione.
• Il codice di distanza è un numero che indica la posizione di un pixel visualizzato in precedenza, da cui copiare i pixel. La mappatura esatta è descritta di seguito.

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

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

Motivazione: questo approccio riduce il requisito di archiviazione per il codice di entropia. Inoltre, i valori elevati sono in genere rari, quindi i bit aggiuntivi verrebbero utilizzati per pochissimi valori nell'immagine. Pertanto, questo approccio si traduce in una migliore compressione complessiva.

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

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 della distanza

Come indicato in precedenza, un codice di distanza è un numero che indica la posizione di un pixel visualizzato in precedenza, da cui copiare 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 di scansione delle righe, con un offset di 120.

I codici di distanza più piccoli [1..120] sono speciali e sono riservati a un quartiere vicino al pixel corrente. Questo vicinato è composto 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 questi pixel = 7 * (8 + 1 + 7) = 112].
• I pixel che si trovano nella stessa riga del pixel corrente e che si trovano fino a 8 colonne a sinistra del pixel corrente. [8 such pixels].

La mappatura tra il codice di distanza distance_code e l'offset del pixel vicino (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 adiacente, ovvero il pixel sopra il pixel corrente (differenza di 0 pixel nella direzione X e di 1 pixel nella direzione Y). Allo stesso modo, il codice di distanza 3 indica il pixel in alto a sinistra.

Il decodificatore può convertire un codice di distanza distance_code in una distanza di ordine di scansione dist nel seguente modo:

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

dove distance_map è il mapping indicato sopra e image_width è la larghezza dell'immagine in pixel.

5.2.3 Codifica della cache dei colori

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 all'emissione utilizzando gli altri due metodi (descritti nelle sezioni 5.2.1 e 5.2.2).

I codici della cache dei colori vengono archiviati nel seguente modo. Innanzitutto, c'è un valore a 1 bit che indica se viene utilizzata la cache dei colori. Se questo bit è 0, non esistono codici della cache dei colori e non vengono trasmessi nel codice del prefisso che decodifica i simboli verdi e i codici del prefisso di lunghezza. Tuttavia, se questo bit è 1, viene letto successivamente il valore della dimensione della cache dei colori:

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 bitstream danneggiato per gli 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 in una cache dei colori; non esiste risoluzione dei conflitti.

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

6 Codice di entropia

6.1 Panoramica

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

In particolare, il formato utilizza la codifica del prefisso spazialmente variante. In altre parole, blocchi diversi dell'immagine possono potenzialmente utilizzare codici di entropia diversi.

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

6.2 Dettagli

I dati dell'immagine codificata sono costituiti da diverse parti:

1. Decodifica e creazione dei codici prefisso.
2. Codici prefisso meta.
3. Dati immagine codificati con entropia.

Per ogni pixel (x, y), esiste un insieme di cinque codici prefisso associati. Questi codici sono (in ordine di bitstream):

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

Da questo momento in poi, ci riferiremo a questo insieme come gruppo di codici prefisso.

6.2.1 Decodifica e creazione dei codici prefisso

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

Le lunghezze del codice prefisso possono essere codificate in due modi. Il metodo utilizzato è specificato da un valore a 1 bit.

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

In entrambi i casi, possono esserci lunghezze di codice inutilizzate che fanno ancora parte dello stream. Potrebbe non essere efficiente, ma è consentito dal formato. L'albero descritto deve essere un albero binario completo. Un singolo nodo foglia è considerato un albero binario completo e può essere codificato utilizzando il codice di lunghezza semplice o il codice di lunghezza normale. Quando codifichi un singolo nodo foglia utilizzando il codice di lunghezza normale, tutte le lunghezze del codice tranne una sono pari a zero e il valore del singolo nodo foglia è contrassegnato con la lunghezza 1, anche quando non vengono utilizzati bit quando viene utilizzato l'albero del singolo nodo foglia.

Codice di lunghezza semplice

Questa variante viene utilizzata nel caso speciale in cui solo 1 o 2 simboli di prefisso si trovano nell'intervallo [0..255] con lunghezza del codice 1. Tutte le altre lunghezze del codice prefisso sono implicitamente pari a zero.

Il primo bit indica il numero di simboli:

int num_symbols = ReadBits(1) + 1;

Di seguito sono riportati i valori dei simboli.

Il primo simbolo viene codificato utilizzando 1 o 8 bit, a seconda del valore di is_first_8bits. L'intervallo è [0..1] o [0..255], rispettivamente. Il secondo simbolo, se presente, viene sempre considerato nell'intervallo [0..255] e 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. I simboli duplicati sono consentiti, ma inefficienti.

Nota:un altro caso speciale si verifica quando tutte le lunghezze dei codici prefisso sono zero (un codice prefisso vuoto). Ad esempio, un codice prefisso per la distanza può essere vuoto se non sono presenti riferimenti all'indietro. Analogamente, i codici prefisso per alfa, rosso e blu possono essere vuoti se tutti i pixel all'interno dello stesso codice prefisso meta sono prodotti utilizzando la cache dei colori. Tuttavia, questo caso non richiede una gestione speciale, in quanto i codici prefisso vuoti possono essere codificati come quelli contenenti un singolo simbolo 0.

Normal Code Length Code

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 sono codificate utilizzando codici prefisso; devono essere lette prima le lunghezze dei codici di livello inferiore, code_length_code_lengths. 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 sulla dimensione dell'alfabeto:

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

In caso contrario, è definito come:

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

Se max_symbol è maggiore della dimensione dell'alfabeto per il tipo di simbolo, il bitstream non è valido.

Viene quindi creata una tabella dei prefissi da code_length_code_lengths e utilizzata per leggere fino a max_symbol lunghezze del codice.

• Il codice [0..15] indica le lunghezze letterali del codice.
  • Il valore 0 indica che non sono stati codificati simboli.
  • I valori [1..15] indicano la lunghezza in bit del codice corrispondente.
• Il codice 16 ripete il valore non nullo precedente [3..6] volte, ovvero 3 + ReadBits(2) volte. Se il codice 16 viene utilizzato prima dell'emissione di un valore diverso da zero, viene ripetuto il valore 8.
• Il codice 17 emette una sequenza di zeri di lunghezza [3..10], ovvero 3 + ReadBits(3) volte.
• Il codice 18 emette una sequenza di zeri di lunghezza [11..138], ovvero 11 + ReadBits(7) volte.

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

Il codice di lunghezza normale deve codificare un albero decisionale completo, ovvero la somma di 2 ^ (-length) per tutti i codici diversi da zero deve essere esattamente pari a 1. Esiste tuttavia un'eccezione a questa regola, l'albero a un solo 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 prefisso meta

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

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

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

• Se questo bit è zero, nell'immagine viene utilizzato un solo codice di prefisso meta. Non vengono memorizzati altri dati.
• Se questo bit è 1, l'immagine utilizza più codici prefisso meta. Questi codici prefisso meta sono memorizzati come immagine di entropia (descritta di seguito).

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

Immagine di entropia

L'immagine di 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 di 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 di entropia di larghezza prefix_image_width e altezza prefix_image_height.

Interpretazione dei codici prefisso meta

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

int num_prefix_groups = max(entropy image) + 1;

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

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

int num_prefix_codes = 5 * num_prefix_groups;

Dato un pixel (x, y) nell'immagine ARGB, possiamo ottenere i codici prefisso corrispondenti da utilizzare nel seguente modo:

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

in cui abbiamo presupposto l'esistenza di una struttura PrefixCodeGroup, che rappresenta un insieme di cinque codici prefisso. Inoltre, prefix_code_groups è un array di PrefixCodeGroup (di dimensioni num_prefix_groups).

Il decodificatore utilizza quindi il gruppo di codici prefisso prefix_group per decodificare il pixel (x, y), come spiegato in "Decodifica dei dati immagine codificati con entropia".

6.2.3 Decodifica dei dati immagine codificati con entropia

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

Successivamente, leggi il simbolo S dal bitstream utilizzando il codice prefisso n. 1. Tieni presente che S è un numero intero compreso tra 0 e (256 + 24 + color_cache_size- 1).

L'interpretazione di S dipende dal suo valore:

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

7 Struttura generale del formato

Di seguito è riportata una visualizzazione del formato in Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Non copre tutti i dettagli. La fine dell'immagine (EOI) è codificata implicitamente solo 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 immagine

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