Specifiche per WebP Lossless Bitstream

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

Abstract

WebP lossless è un formato di immagine per la compressione senza perdita di dati delle immagini ARGB. La il formato senza perdita di dati archivia e ripristina esattamente i valori dei pixel, compreso il valore valori di colore per pixel completamente trasparenti. Un algoritmo universale per la compressione dati (LZ77), la codifica dei prefissi e una cache dei colori, compressione dei dati in blocco. La velocità di decodifica è superiore a quella del formato PNG dimostrato, nonché una compressione più densa del 25% rispetto a quella ottenibile con PNG.

1 Introduzione

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

In questo documento viene ampiamente utilizzata la sintassi del linguaggio di programmazione C per descrivere il flusso di bit e presupporre 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 dal bit meno significativo al bit più significativo. Quando vengono letti più bit contemporaneamente, il numero intero viene creato nell'ordine originale. I bit più significativi dell'intero restituito sono anche i bit più significativi dei dati originali. Di conseguenza, dichiarazione

b = ReadBits(2);

equivale alle due seguenti affermazioni:

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

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

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

2 Nomenclatura

ARGB

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

Immagine ARGB

Un array bidimensionale contenente pixel ARGB.

cache dei colori

Un piccolo array con indirizzo hash per archiviare i colori utilizzati di recente per consentire richiamarli con codici più brevi.

immagine di indicizzazione dei colori

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

immagine con trasformazione del colore

Un'immagine a subrisoluzione bidimensionale contenente dati sulle correlazioni di 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 entropia

Un'immagine a subrisoluzione bidimensionale che indica quale codifica di entropia dovrebbe essere utilizzato in un rispettivo quadrato nell'immagine, ovvero ogni pixel è del prefisso.

LZ77

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

meta prefisso

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

immagine del predittore

Un'immagine a subrisoluzione bidimensionale che indica quale predittore spaziale è per un particolare quadrato nell'immagine.

codice prefisso

Un metodo classico per la codifica entropia in cui viene utilizzato un numero inferiore di bit per codici più frequenti.

codifica del 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 riga 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 dal colonna a sinistra della riga successiva.

3 Intestazione RIFF

All'inizio dell'intestazione è presente il contenitore RIFF. Si tratta di i seguenti 21 byte:

1. Stringa "RIFF".
2. Un valore little-endian a 32 bit della lunghezza del chunk, ovvero l'intera dimensione del chunk controllata dall'intestazione RIFF. Normalmente, corrisponde alle dimensioni del payload (dimensioni del file meno 8 byte: 4 byte per l'identificatore "RIFF" e 4 byte per la memorizzazione del valore stesso).
3. Stringa "WEBP" (nome del contenitore RIFF).
4. Stringa "VP8L" (FourCC per dati di immagine con codifica senza perdita di dati).
5. Un valore little-endian a 32 bit del numero di byte nello stream lossless.
6. Firma a 1 byte 0x2f.

I primi 28 bit del flusso di bit specificano la larghezza e l'altezza dell'immagine. La larghezza e l'altezza vengono 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 WebP lossless a 16384 x 16384 pixel.

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

int alpha_is_used = ReadBits(1);

Il valore version_number è un codice a 3 bit che deve essere impostato su 0. Qualsiasi altro valore deve da considerare come un errore.

int version_number = ReadBits(3);

4 trasformazioni

Le trasformazioni sono manipolazioni reversibili dei dati delle immagini che possono ridurre l'entropia simbolica rimanente modellando le correlazioni spaziali e di colore. Loro può rendere la compressione finale più densa.

Un'immagine può essere sottoposta a quattro tipi di trasformazioni. 1 bit indica che e la presenza di una trasformazione. Ogni trasformazione può essere utilizzata una sola volta. La le trasformazioni vengono utilizzate solo per l'immagine ARGB di livello principale; le immagini a bassa risoluzione (immagine con trasformazione colore, immagine entropia e immagine del predittore) non hanno trasformazioni, nemmeno lo 0 bit 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. I dati della trasformazione contengono le informazioni necessarie per applicare la trasformazione inversa e dipendono dal tipo di trasformazione. Le trasformazioni inverse vengono applicate nell'ordine inverso rispetto a come vengono lette dal flusso di bit, ovvero dall'ultima all'inizio.

Quindi, descriviamo i dati della trasformazione per diversi tipi.

4.1 Trasformazione dei predittori

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 pixel corrente è previsto dai pixel già decodificati (nella riga di scansione dell'ordine) e solo il valore residuo (effettivo - previsto) viene codificato. Il verde di un pixel definisce quale dei 14 predittori viene utilizzato in un blocco specifico dell'immagine ARGB. La modalità di previsione determina il tipo di la previsione di utilizzo. Dividiamo l'immagine in quadrati e tutti i pixel in un i quadrati usano 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. it è un'immagine a subrisoluzione in cui il componente verde di un pixel definisce quale di i 14 predittori vengono utilizzati per tutti i block_width * block_height pixel all'interno un particolare blocco dell'immagine ARGB. Questa immagine a subrisoluzione è 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 il rispettivo indirizzo del blocco di filtri:

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 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 in alto, TR in alto a destra e L a sinistra. Alle ore il tempo per prevedere un valore per P, tutti i pixel O, TL, T, TR ed L sono già e il pixel P e tutti gli X pixel sono sconosciuti.

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

Average2 è definito come segue per ogni componente ARGB:

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

Il predittore Seleziona viene 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 come segue:

// 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 esiste un la trasformazione del predittore, indipendentemente dalla modalità [0..13] per questi pixel, la il valore previsto per il pixel più in alto a sinistra dell'immagine è 0xff000000, tutti i pixel nella riga superiore sono L-pixel, mentre tutti i pixel nella colonna più a sinistra sono Pixel T.

L'indirizzo del pixel TR per i pixel della colonna più a destra è eccezionale. I pixel nella colonna di destra vengono previsti utilizzando le modalità [0..13], proprio come i pixel non sul bordo, ma il pixel più a sinistra sul la stessa riga del pixel corrente viene invece utilizzata come pixel TR.

Il valore pixel finale si ottiene sommando ciascun 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 ogni pixel. La trasformazione del colore mantiene il valore verde (G) invariato, trasforma il rosso (R) basato sul valore verde e trasforma il valore blu (B) in base al valore sul valore verde e poi sul valore rosso.

Come nel caso della trasformazione del predittore, prima l'immagine viene divisa in blocchi e viene utilizzata la stessa modalità di trasformazione per tutti i pixel di un blocco. Per in ogni blocco ci sono 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 della trasformazione del colore dipende da 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 sta quindi aggiungendo i 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;
}

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

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

Una conversione dalla rappresentazione senza firma a 8 bit (uint8) alla rappresentazione con firma a 8 bit è necessario uno (int8) prima di chiamare ColorTransformDelta(). Il valore firmato dovrebbe essere interpretato come un numero in complemento di 8 bit 2 (ossia l'intervallo uint8) [128..255] è mappato nell'intervallo [-128..-1] del suo valore int8 convertito).

La moltiplicazione deve essere eseguita con una precisione maggiore (con almeno 16 bit). La proprietà di estensione del segno dell'operazione di spostamento non è importante qui; dal risultato vengono usati solo gli 8 bit più bassi; in questi bit, lo spostamento delle estensioni dei segni e lo spostamento non firmato 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 di rosso e blu originali. La i primi 3 bit dei dati della trasformazione del colore contengono la larghezza e l'altezza blocco di immagini 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 relativi alla trasformazione del colore contiene ColorTransformElement di Compute Engine, corrispondenti a ogni blocco dell'immagine. Ogni ColorTransformElement 'cte' viene trattato come un pixel in un'immagine a risoluzione inferiore 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 la trasformazione di colore inversa viene applicata ai valori ARGB dei pixel. Come accennato in precedenza, la trasformazione del colore inverso consiste semplicemente nell'aggiungere valori ColorTransformElement ai canali rosso e blu. I canali alpha e verde rimangono 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 Sottrarre la trasformazione verde

La trasformazione Sottrai verde sottrae i valori verdi dai valori rossi e blu di ogni pixel. Quando è presente questa trasformazione, il decoder deve aggiungere il token verde ai valori rosso e blu. Nessun dato associato e trasformerai automaticamente. Il decodificatore 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, ma poiché non sono presenti dati aggiuntivi, la trasformazione sottrazione verde può essere codificata utilizzando meno bit di una trasformazione del colore completa.

4.4 Trasformazione Indicizzazione dei colori

Se non sono presenti molti valori di pixel univoci, potrebbe essere più efficace creare un'immagine dell'indice di colore e sostituisci i valori dei pixel con gli indici dell'array. La trasformazione di indice di colore consente di ottenere questo risultato. Nel contesto di WebP lossless, non la chiamiamo esplicitamente una trasformazione della tavolozza perché nella codifica WebP lossless esiste un concetto simile, ma più dinamico: la cache dei colori.

La trasformazione di indicizzazione dei colori verifica il numero di valori ARGB univoci nella dell'immagine. Se questo numero è al di sotto di una soglia (256), viene creato un array di questi Valori ARGB, che vengono poi utilizzati per sostituire i valori pixel con indice corrispondente: il canale verde dei pixel è sostituito dal l'indice, tutti i valori alfa sono impostati su 255 e tutti i valori rossi e blu su 0.

I dati di trasformazione contengono le dimensioni della tabella dei colori e le voci nel colore tabella. Il decoder legge i dati di trasformazione dell'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 lo stesso formato di archiviazione delle immagini. Tabella dei colori che può essere ottenuta leggendo un'immagine, senza l'intestazione RIFF, le dimensioni dell'immagine , assumendo l'altezza di 1 pixel e la larghezza di color_table_size. La tabella dei colori è sempre codificata per sottrazione per ridurre l'entropia dell'immagine. I delta degli colori della tavolozza contengono in genere molta meno entropia rispetto ai colori stesse, con un conseguente risparmio significativo per le immagini più piccole. Durante la 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 gli 8 bit meno significativi del risultato.

La trasformazione inversa dell'immagine sta semplicemente sostituendo i valori dei pixel (che sono indici della tabella dei colori) con i valori effettivi della tabella. Lo strumento di indicizzazione viene eseguita in base al 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 a/#. deve essere impostato su 0x00000000 (nero trasparente).

Quando la tabella dei colori è piccola (uguale o inferiore a 16 colori), più pixel vengono raggruppati in un unico pixel. Il raggruppamento dei pixel comprime diversi (2, 4 o 8) pixel in un singolo pixel, riducendo rispettivamente la larghezza dell'immagine. Il raggruppamento di pixel consente una codifica dell'entropia della distribuzione congiunta più efficiente dei pixel vicini e offre alcuni vantaggi simili alla codifica aritmetica al codice di entropia, ma può essere utilizzato solo se sono presenti 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 nessun pixel il raggruppamento in set per l'immagine. Il valore 1 indica che due pixel sono e ciascun 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 compreso tra [0..3]. Un valore pari a 3 indica che sono combinati otto pixel e che ogni pixel ha un intervallo di [0..1], cioè un valore binario.

I valori sono pacchettizzati nel componente verde come segue:

• width_bits = 1: per ogni valore x, dove x ⌘ 0 (mod 2), un simbolo verde valore x sia posizionato nei 4 bit meno significativi della valore verde in x / 2 e un valore verde in x + 1 viene posizionato nella 4 bit più significativi del valore verde in x / 2.
• width_bits = 2: per ogni valore x, dove x ⌘ 0 (mod 4), un simbolo verde valore x viene posizionato nei 2 bit meno significativi della valore verde in x / 4, e i valori verdi in x + 1 a x + 3 sono 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 simbolo verde il valore x sia posizionato nel bit meno significativo del valore a x / 8 e i valori verdi a x + 1 a x + 7 sono posizionati nell'ordine ai bit più significativi del valore verde in x / 8.

Dopo aver letto questa trasformazione, image_width viene sottocampionato per 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 immagine sono un array di valori di pixel in ordine di linea di scansione.

5.1 Ruoli dei dati immagine

Utilizziamo i dati immagine in cinque diversi ruoli:

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

5.2 Codifica dei dati delle immagini

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

L'immagine viene prima divisa in un insieme di blocchi di dimensioni fisse (in genere blocchi di 16 x 16). Ciascuno di questi blocchi viene modellato utilizzando i propri codici di entropia. Inoltre, diversi 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, memorizzandolo quindi solo una volta. Ad esempio, un codificatore può trovare blocchi simili raggruppandoli utilizzando le loro proprietà statistiche o unendo ripetutamente cluster selezionati quando si riduce la quantità complessiva di bit necessari per la codifica dell'immagine.

Ogni pixel viene codificato utilizzando uno dei tre metodi possibili:

1. Letterali con prefisso codificato: ogni canale (verde, rosso, blu e alfa) viene codificato in modo indipendente in base all'entropia.
2. Riferimento all'indietro LZ77: una sequenza di pixel viene copiata da un altro punto in dell'immagine.
3. Codice cache colorato: uso di un breve codice hash moltiplicativo (cache dei colori) indice) di un colore rilevato di recente.

Ciascuna di queste sottosezioni viene descritta in dettaglio nelle sottosezioni riportate di seguito.

5.2.1 Letterali con prefisso codificato

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

5.2.2 Riferimento all'indietro LZ77

I riferimenti a ritroso sono tuple di lunghezza e codice distanza:

• La lunghezza indica il numero di pixel nell'ordine delle righe di scansione da copiare.
• Il codice di distanza è un numero che indica la posizione di un pixel visto in precedenza da cui devono essere copiati i pixel. La mappatura esatta è описана di seguito.

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

La codifica del prefisso LZ77 divide grandi valori interi in due parti: il 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 l'entropia le API nel tuo codice. Inoltre, i valori grandi sono in genere rari, pertanto i bit aggiuntivi verrebbero utilizzati per pochissimi valori nell'immagine. Di conseguenza, questo approccio consente una compressione migliore complessivamente.

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

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

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 osservato in precedenza, un codice di distanza è un numero che indica la posizione di un visto in precedenza, 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 maggiori di 120 indicano la distanza in pixel in ordine di riga di scansione, con un offset di 120.

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

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

Il decoder può convertire un codice di distanza distance_code in un ordine a linee di scansione distanza 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 dei colori

La cache 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 in 5.2.1 e 5.2.2).

I codici della cache dei colori vengono memorizzati come segue. Innanzitutto, è presente un valore di 1 bit che indica se viene utilizzata la cache dei colori. Se questo bit è 0, nessun codice della cache colore esistenti e non vengono trasmessi nel codice prefisso che decodifica il codice e i codici di prefisso di lunghezza. Tuttavia, se questo bit è 1, la cache dei colori la dimensione viene letta dopo:

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 decodificatori conformi devono indicare un bitstream danneggiato per altri valori.

Una cache di colori è un array di dimensioni color_cache_size. Ogni voce memorizza un ARGB colore. I colori vengono cercati eseguendone l'indicizzazione in base a (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Viene effettuata una sola ricerca nella cache dei colori. non c'è la risoluzione dei conflitti.

All'inizio della decodifica o della codifica di un'immagine, tutte le voci in tutti i colori i valori della cache sono impostati 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 prodotta facendo riferimento a versioni precedenti o sotto forma di valori letterali, nella cache nell'ordine in cui appaiono nello stream.

Codice di entropia 6

6.1 Panoramica

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

In particolare, il formato utilizza la codifica dei prefissi con varianti spaziali. In altre parole, blocchi diversi dell'immagine possono potenzialmente usare entropia diversa i codici.

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

6.2 Dettagli

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

1. Decodifica e crea i codici dei prefissi.
2. Codici prefisso.
3. Dati immagine con codifica in base all'entropia.

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

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

Da qui in poi, facciamo riferimento a questo insieme come un gruppo di codici del prefisso.

6.2.1 Decodifica e creazione dei codici prefisso

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

La lunghezza dei codici prefisso può essere codificata in due modi. Il metodo utilizzato è specificato per un valore a 1 bit.

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

In entrambi i casi, possono essere presenti lunghezze di codice inutilizzate che fanno ancora parte dello stream. Potrebbe non essere efficace, 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 della lunghezza del codice semplice o il codice della lunghezza del codice normale. Quando si codifica un singolo node lo utilizzando il codice della lunghezza del codice normale, tutte le lunghezze del codice tranne una sono pari a zero e il valore del singolo node lo è contrassegnato con la lunghezza di 1, anche se non vengono consumati bit quando viene utilizzato l'albero del singolo node.

Codice di lunghezza del codice semplice

Questa variante viene utilizzata nel caso speciale quando sono presenti solo 1 o 2 simboli di prefisso l'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.

Questo primo simbolo è codificato con 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. I simboli duplicati sono consentiti, ma inefficienti.

Nota: un altro caso speciale si verifica quando tutte le lunghezze del codice prefisso sono zero (un codice prefisso vuoto). Ad esempio, il codice prefisso per la distanza può essere vuoto se non ci sono riferimenti a versioni precedenti. Analogamente, i codici prefisso per alpha, red e il blu può essere vuoto se vengono generati tutti i pixel all'interno dello stesso meta prefisso usando la cache dei colori. Tuttavia, questo caso non richiede un'elaborazione speciale, poiché i codici di prefisso vuoti possono essere codificati come quelli contenenti un singolo simbolo 0.

Codice di lunghezza del codice normale

Le lunghezze del codice del prefisso si adattano a 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 del codice sono a loro volta codificate utilizzando codici di prefisso. Per prima cosa, devono essere lette le lunghezze del codice di livello inferiore, code_length_code_lengths. Il resto di questi code_length_code_lengths (in base all'ordine in kCodeLengthCodeOrder) è zero.

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) è impostato sul relativo dimensione dell'alfabeto:

• Canale G: 256 + 24 + color_cache_size
• Altri 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 è superiore alla dimensione dell'alfabeto per il tipo di simbolo, il valore bitstream non è valido.

Da code_length_code_lengths viene quindi creata una tabella con prefisso che viene utilizzata per leggere con una lunghezza di codice pari a max_symbol.

• Il codice [0..15] indica le lunghezze del codice letterale.
  • Il valore 0 indica che non sono stati codificati simboli.
  • 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 il codice 16 viene utilizzato prima che sia stato emesso un valore diverso da zero, viene ripetuto un valore di 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 del codice, viene formato un codice prefisso per ogni tipo di simbolo (A, R, G, B e distanza) utilizzando le rispettive dimensioni dell'alfabeto.

Il codice della lunghezza normale del codice deve codificare una struttura ad albero di decisione completa, ovvero la somma di 2 ^ (-length) per tutti i codici diversi da zero deve essere esattamente 1. Esiste tuttavia una eccezione a questa regola, l'albero con un singolo 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 prefisso meta

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

I metadati dei codici prefisso possono essere utilizzati solo se l'immagine viene utilizzata nel campo role di un'immagine ARGB.

Ci sono due possibilità per i meta prefissi, indicati da un codice a 1 bit valore:

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

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

Immagine a entropia

L'immagine entropia definisce i codici prefissi utilizzati in parti diverse del 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 prefisso nell'immagine ARGB può essere ottenuto trovando il codice 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 dell'entropia.

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

int num_prefix_codes = 5 * num_prefix_groups;

Dato un pixel (x, y) nell'immagine ARGB, possiamo ottenere i codici prefisso 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];

in cui abbiamo assunto l'esistenza della struttura PrefixCodeGroup, che rappresenta un insieme di cinque prefissi. Inoltre, prefix_code_groups è un array di PrefixCodeGroup (di dimensioni num_prefix_groups).

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

6.2.3 Decodifica di dati di immagini con codice entropia

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

Quindi, leggi il simbolo S dal flusso di bit utilizzando il codice di prefisso 1. Tieni presente che S è qualsiasi 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. Usa S come componente verde.
   2. Leggi in rosso dal bitstream utilizzando il codice prefisso 2.
   3. Leggi in blu il flusso di bit utilizzando il codice prefisso 3.
   4. Leggi l'alfa dal flusso di bit utilizzando il codice prefisso 4.
2. Se S >= 256 e S < 256 + 24
   1. Utilizza S - 256 come codice prefisso della lunghezza.
   2. Leggere bit extra per la lunghezza dal flusso di bit.
   3. Determina la lunghezza del riferimento a ritroso L dal codice del prefisso della lunghezza e dai bit extra letti.
   4. Leggi il codice del prefisso di distanza dal flusso di bit utilizzando il codice prefisso 5.
   5. Leggere bit aggiuntivi per la distanza dal flusso di bit.
   6. Determina la distanza di riferimento a ritroso D dal codice prefisso della distanza e dai bit extra letti.
   7. Copia L pixel (in ordine di riga di scansione) dalla sequenza di pixel che inizia dalla posizione corrente 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 generale del formato

Di seguito è riportata una panoramica del formato in Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Non copre tutti i dettagli. Il codice di fine immagine (EOI) viene codificato solo 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 è riportato un possibile esempio di sequenza:

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