Specifiche per WebP Lossless Bitstream

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

Abstract

WebP lossless è un formato di immagine per la compressione senza perdita di 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 del flusso che contiene e i bit di ogni byte vengono letti nell'ordine bit-first meno significativo. Quando vengono letti più bit contemporaneamente, il numero intero viene creato nell'ordine originale. I frammenti più significativi 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;

Partiamo dal presupposto che ogni componente del colore (alfa, rosso, blu e verde) sia rappresentati utilizzando un byte a 8 bit. Definiamo il tipo corrispondente come uint8. R l'intero pixel ARGB è rappresentato da un tipo chiamato uint32, che è un modello non firmato numero intero composto 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 senza perdita di dati WebP contiene dati di intestazione, trasforma le informazioni e i dati effettivi delle immagini. 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 necessario 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 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 delle distanze

Modifica le distanze LZ77 per ottenere i valori più piccoli per i pixel in di 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 piccolo numero intero (fino a 16 bit) che indicizza un elemento nel meta-prefisso .

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 numeri interi più grandi, che codificano alcuni bit del numero intero utilizzando un codice di entropia e codifica i bit rimanenti non elaborati. Ciò consente le descrizioni dei codici di entropia a rimanere relativamente piccole anche quando l'intervallo di simboli è grande.

ordine linea di scansione

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

3 Intestazione RIFF

L'inizio dell'intestazione include il container RIFF. Si tratta di i seguenti 21 byte:

1. Stringa "RIFF".
2. Un valore small-endian a 32 bit della lunghezza del blocco, che corrisponde all'intera dimensione del blocco controllato dall'intestazione RIFF. Solitamente, equivale a la dimensione del payload (dimensione del file meno 8 byte: 4 byte per il "RIFF" e 4 byte per l'archiviazione del valore stesso).
3. Stringa "WEBP" (nome del container RIFF).
4. Stringa "VP8L" (FourCC per dati di immagine con codifica senza perdita di dati).
5. Un valore small-endian a 32 bit del numero di byte nella 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 la dimensione massima di un Immagine senza perdita di dati WebP a 16384x16384 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 dell'immagine che possono ridurre l'entropia simbolica rimanente modellando le correlazioni spaziali e dei colori. 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.

Tipicamente, un encoder utilizza queste trasformazioni per ridurre l'entropia di Shannon nell'immagine residua. Inoltre, i dati di trasformazione possono essere stabiliti in base all'entropia minimizzazioni.

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 Transform contengono le informazioni necessarie per applicare la trasformazione inversa e dipende e il tipo di trasformazione. Le trasformazioni inverse vengono applicate nell'ordine inverso che vengono letti prima dal flusso di bit, ossia l'ultimo.

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 usano la stessa modalità di previsione.

I primi 3 bit di dati di previsione definiscono la larghezza e l'altezza del blocco in numeri 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 di blocchi, transform_width, è utilizzato in modelli dell'indicizzazione. Per un pixel (x, y), è possibile calcolare il rispettivo blocco filtro indirizzo da:

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

Esistono 14 diverse modalità di previsione. In ogni modalità di previsione, il valore pixel è previsto da uno o più pixel vicini i cui valori sono noto.

Abbiamo scelto i pixel vicini (TL, T, TR e L) del pixel corrente (P) come che 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 significa in alto, TR significa in alto a destra e L significa 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.

Modalità	Valore previsto di ciascun canale del pixel corrente
0	0xff000000 (rappresenta il colore nero solido 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	Media 2(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 è 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);
}

Per alcuni pixel del bordo esistono regole di gestione speciali. 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'impostazione del pixel TR per i pixel nella 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

L'obiettivo della trasformazione del colore è decorare i valori R, G e B di ciascuno 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 effettiva del colore viene eseguita definendo un delta di trasformazione del colore. La 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 e 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 effettuata usando una maggiore precisione (con almeno 16 bit precisione). La proprietà di estensione del segno dell'operazione di spostamento non è importante qui; dal risultato vengono usati solo gli 8 bit più bassi ed è qui che lo spostamento delle estensioni e quello senza firma sono coerenti tra loro.

Adesso descriviamo i contenuti dei dati di trasformazione del colore in modo che la decodifica possa essere applicata la trasformazione del colore inverso e recuperare i valori originali di rosso e blu. 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. Ciascuna ColorTransformElement 'cte' viene considerato un pixel in un'immagine a risoluzione inferiore il cui componente alpha è 255, il componente rosso è cte.red_to_blue, verde il componente è cte.green_to_blue, mentre il componente blu è cte.green_to_red.

Durante la decodifica, vengono decodificate ColorTransformElement istanze dei blocchi e la trasformazione del colore inverso viene applicata ai valori ARGB dei pixel. Come Come accennato prima, la trasformazione inversa dei colori aggiunge ColorTransformElement ai canali rosso e blu. Alfa e verde i canali 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 Sottrarre la trasformazione verde

La trasformazione verde di sottrazione sottrae i valori verdi dai valori rosso 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 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, ma poiché non ci sono dati aggiuntivi qui, la trasformazione verde di sottrazione può essere codificata utilizzando meno bit rispetto a una trasformazione di 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. Il colore la trasformazione di indicizzazione raggiunge questo obiettivo. Nel contesto di WebP senza perdita di dati, in particolare non chiamarla "Tavolozza di trasformazione" perché un modello simile il concetto dinamico esiste nella codifica senza perdita di dati WebP: 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 la dimensione della tabella dei colori e le voci nel colore . 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 il formato di archiviazione delle immagini stesso. 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 delle tavolozze di colori contengono in genere molta meno entropia rispetto ai colori con conseguente risparmio significativo per le immagini più piccole. Nella decodifica, ogni colore finale nella tabella dei colori può essere ottenuto aggiungendo il colore colore per ogni componente ARGB separatamente e memorizzando il minimo a 8 bit 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 colori è piccola (uguale o inferiore a 16 colori), diversi pixel sono raggruppati in un unico pixel. Il raggruppamento di pixel ne contiene diversi (2, 4 o 8) pixel in un singolo pixel, riducendo rispettivamente la larghezza dell'immagine. Pixel Il bundling consente una codifica più efficiente dell'entropia della distribuzione congiunta di pixel vicini e offre alcuni vantaggi, simili a quelli di un codice aritmetico, alla codice di entropia, ma può essere usato solo se ci sono 16 o meno 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 bundling deve essere eseguito per l'immagine. Il valore 1 indica che due pixel sono e ciascun pixel ha un intervallo di [0-15]. Il valore 2 indica che sono combinati quattro pixel e ognuno ha un intervallo di [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, il valore di image_width viene sottocampionato da width_bits. Questo influisce sulla dimensione 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 delle immagini

Utilizziamo i dati immagine in cinque diversi ruoli:

1. Immagine ARGB: memorizza i pixel effettivi dell'immagine.
2. Immagine a entropia: archivia i metacodici 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 con trasformazione del colore: creata da ColorTransformElement valori (definita in "Color Transform") per diversi blocchi dell'immagine.
5. Immagine di indicizzazione dei colori: un array di dimensioni color_table_size (fino a 256 ARGB di indicizzazione) memorizzando i metadati per la trasformazione di indicizzazione dei colori (vedi "Trasformazione Indicizzazione dei colori").

5.2 Codifica dei dati di immagine

La codifica dei dati di immagine è indipendente dal loro ruolo.

L'immagine viene prima divisa in un insieme di blocchi di dimensioni fisse (in genere 16 x 16) isolati). 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 blocchi statisticamente simili condividono un codice di entropia, memorizzando quindi quel codice 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. Valori letterali codificati per prefisso: ogni canale (verde, rosso, blu e alfa) viene codificata con l'entropia in modo indipendente.
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 Valori letterali codificati con prefisso

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 length e codice distanza:

• La lunghezza indica quanti pixel devono essere copiati in ordine della linea di scansione.
• Il codice di distanza è un numero che indica la posizione di un pixel, da cui devono essere copiati i pixel. La mappatura esatta è descritti di seguito.

I valori relativi a 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 prefisso viene archiviato utilizzando un codice di entropia, mentre i bit aggiuntivi vengono archiviati così come sono (senza un codice entropia).

Motivazione: questo approccio riduce il requisito di archiviazione per l'entropia le API nel tuo codice. Inoltre, di solito i valori grandi sono rari, quindi vengono usati bit in più per alcuni valori presenti nell'immagine. Pertanto, questo approccio migliora la compressione nel complesso.

La seguente tabella indica i codici prefisso e i bit aggiuntivi utilizzati per la memorizzazione 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 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 delle distanze

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.

I codici di distanza superiori a 120 indicano la distanza in pixel nell'ordine della linea di scansione, compensato con 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] tale pixel = 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 (0, 1) per la pixel adiacente, ovvero il pixel sopra il pixel corrente (0 pixel differenza nella direzione X e differenza di 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 cache a colori

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

Motivazione:in questo modo, a volte i colori utilizzati di recente possono essere indicati come in modo più efficiente rispetto a emetterle con gli altri due metodi (descritti in 5.2.1 e 5.2.2).

I codici colore della cache vengono archiviati come segue. Innanzitutto, c'è un valore a 1 bit indica se è in uso 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 le dimensioni 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 bitstream danneggiato per altri valori.

Una cache dei 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 color cache viene convertito in questo colore nel giorno in fase di 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.

6 Codice a entropia

6.1 Panoramica

La maggior parte dei dati viene codificata utilizzando un codice prefisso canonico. Pertanto, i codici vengono trasmessi inviando le lunghezze del codice prefisso, come al contrario degli effettivi codici prefisso.

In particolare, il formato utilizza la codifica spaziale delle varianti. In altre parole, blocchi diversi dell'immagine possono potenzialmente usare entropia diversa i codici di accesso.

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 immagine codificati sono costituiti da diverse parti:

1. Decodifica e crea i codici dei prefissi.
2. Codici prefisso.
3. Dati immagine con codifica 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 dei riferimenti a ritroso e cache dei colori.
• Codice prefisso 2, 3 e 4: utilizzato per i canali rosso, blu e alfa. rispettivamente.
• Codice prefisso 5: utilizzato per la distanza di riferimento a ritroso.

Da qui in poi, facciamo riferimento a questo insieme come un gruppo di codice 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 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 esserci lunghezze di codice non utilizzate che fanno ancora parte del flusso di dati. Potrebbe non essere efficace, ma è consentito dal formato. L'albero descritto deve essere un albero binario completo. Un nodo a foglia singola considerata un albero binario completo e può essere codificata utilizzando il codice di lunghezza del codice o il codice di lunghezza normale. Quando codifichi una singola foglia utilizzando il codice di lunghezza del codice normale, tutti i codici tranne uno sono zeri, e il valore del nodo a foglia singola è contrassegnato con la lunghezza pari a 1, anche quando nessuna i bit vengono consumati quando si utilizza questo albero con nodo a foglia singola.

Codice lunghezza 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 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 con 1 o 8 bit, a seconda del valore di is_first_8bits. L'intervallo è rispettivamente [0..1] o [0..255]. Il secondo se presente, si presume sempre che sia nell'intervallo [0..255] e codificato a 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 poco efficiente.

Nota: un altro caso speciale è quando tutte le lunghezze dei codici 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, questa richiesta non richiede una gestione speciale, i codici prefissi vuoti possono essere codificati come quelli contenenti un singolo simbolo 0.

Codice lunghezza codice normale

La lunghezza del codice del prefisso è di 8 bit e viene letta 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 a loro volta codificate utilizzando codici prefissi; codice di livello inferiore lunghezze, code_length_code_lengths, devono essere lette. Gli altri code_length_code_lengths (in base all'ordine in kCodeLengthCodeOrder) corrispondono a 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) è impostato sul relativo dimensione dell'alfabeto:

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

In caso contrario, viene 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 è stato codificato nessun 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 il codice 16 viene usato prima di un numero diverso da zero è stato emesso un valore pari a 8.
• Il codice 17 emette una serie di zeri di lunghezza [3..10], ovvero 3 + ReadBits(3) volte.
• Il codice 18 emette una striscia di zeri di lunghezza [11..138], cioè, 11 + ReadBits(7) volte.

Una volta lette le lunghezze dei codici, un codice prefisso per ogni tipo di simbolo (A, R, G, B e distanza) vengono generati utilizzando le rispettive dimensioni alfabetiche.

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

6.2.2 Decodifica dei codici metaprefissi

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

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

Esistono due possibilità per i meta codici prefisso, 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 metadati vengono memorizzati come immagine di entropia (descritta di seguito).

I componenti rosso e verde di un pixel definiscono un meta prefisso a 16 bit utilizzato un particolare 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'entropia le immagini provengono 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 è come definito in precedenza.

I bit successivi contengono un'immagine entropia con larghezza e altezza pari a prefix_image_width prefix_image_height.

Interpretazione dei codici prefisso

Il numero di gruppi di codici prefissi nell'immagine ARGB può essere ottenuto trovando il più grande meta prefisso dall'immagine 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 il prefisso corrispondente codici utilizzabili 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 decoder utilizza quindi il gruppo di codici prefisso prefix_group per decodificare il pixel (x, y), come spiegato in "Decodificare un'immagine con codice entropia Dati".

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, 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 indica qualsiasi numero intero 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 il flusso di bit utilizzando il codice prefisso 3.
   4. Leggi la versione alpha del bitstream utilizzando il codice prefisso 4.
2. Se S >= 256 e P < 256 + 24
   1. Utilizza il prefisso S-256 come prefisso di lunghezza.
   2. Leggere bit extra per la lunghezza dallo stream di bit.
   3. Stabilire la lunghezza del riferimento a ritroso dal codice del prefisso di lunghezza e bit extra letti.
   4. Leggi il codice del prefisso della distanza dal bitstream utilizzando il codice prefisso 5.
   5. Leggere bit aggiuntivi per la distanza dal flusso di bit.
   6. Determinare la distanza D con riferimento a ritroso dal codice prefisso della distanza e i bit extra vengono letti.
   7. Copia L pixel (in ordine della linea di scansione) dalla sequenza di pixel che inizia nella 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 complessiva del formato

Di seguito è riportata una panoramica del formato in Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. e non tutti i dettagli. La fine dell'immagine (EOI) è codificato implicitamente solo nel numero di pixel (larghezza_immagine * altezza_immagine).

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 di 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