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 dati delle immagini ARGB. Il formato senza perdita di dati 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 del prefisso e una cache dei colori. 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. È pensato come riferimento dettagliato per l'implementazione di codificatori e decodificatori WebP lossless.

In questo documento utilizziamo estensivamente 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 bit più significativi dell'intero restituito sono anche i bit più significativi dei dati originali. Pertanto, l'affermazione

b = ReadBits(2);

è equivalente alle due dichiarazioni riportate di seguito:

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. 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'immagine WebP senza perdita di dati può essere sottoposta a quattro diversi tipi di trasformazioni prima di essere codificata in base all'entropia. Le informazioni sulla trasformazione nel flusso di bit 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 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 risoluzione inferiore bidimensionale contenente dati sulle correlazioni dei componenti di colore.

mappatura delle distanze

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

immagine entropia

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

LZ77

Un algoritmo di compressione con 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 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, vai alla colonna di 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 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 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. Larghezza e altezza sono decodificate come numeri interi a 14 bit come segue:

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

La precisione a 14 bit per la larghezza e l'altezza dell'immagine limita le dimensioni massime di un'immagine 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 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 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 di blocchi, transform_width, è utilizzato in modelli dell'indicizzazione. 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 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 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.

Modalità	Valore previsto di ogni 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	Media2(T, TR)
10	Media2(Media2(L; TL); Media2(T; TR))
11	Seleziona(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

Average2 è 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 di 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'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

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 per la trasformazione del predittore, innanzitutto l'immagine viene 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 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 consiste semplicemente 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;
}

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; in questi bit, lo spostamento delle estensioni dei segni e lo spostamento non firmato 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. 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 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 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. Non sono presenti dati associati a questa trasformazione. Il decoder applica la trasformazione inversa come segue:

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

Questa trasformazione è ridondante, in quanto può essere modellata utilizzando la trasformazione del colore, 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 di 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 le dimensioni della tabella dei colori e le voci nella tabella. Il decodificatore legge i dati della trasformazione di indicizzazione del colore 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 per l'immagine consiste semplicemente nella sostituzione dei valori dei pixel (che sono indici della tabella di colori) con i valori effettivi della tabella di colori. 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. Un valore pari a 0 indica che non è necessario eseguire il raggruppamento di pixel 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, image_width viene sottocampionato per 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 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 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 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: la memorizzazione 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. 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.

Le sottosezioni seguenti descrivono ciascuna di queste opzioni in dettaglio.

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

Il 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 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 a un imbastimento prossimo 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 l'offset del pixel adiacente (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 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 decodificatore può convertire un codice di distanza distance_code in una distanza di ordinamento delle righe di scansione dist come segue:

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

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

5.2.3 Codifica 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 della cache dei colori vengono memorizzati come segue. Innanzitutto, c'è un valore a 1 bit indica se è in uso la cache dei colori. Se questo bit è 0, non esistono codici cache dei colori e non vengono trasmessi nel codice prefisso che decodifica i simboli verdi e i codici prefisso della 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 tempo 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 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 immagine codificati 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 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. Questa operazione potrebbe non essere efficiente, ma è consentita 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 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. 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

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 dei codici sono a loro volta codificate utilizzando codici prefissi; codice di livello inferiore lunghezze, code_length_code_lengths, devono prima essere lette. 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 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 delle dimensioni dell'alfabeto per il tipo di simbolo, il stream di bit 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 valore precedente 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 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 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 metadati dei 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 codici prefisso meta 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 meta

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 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 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 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 è 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 la versione alpha del bitstream 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 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 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 complessiva del formato

Di seguito è riportata una visualizzazione 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