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:
- Stringa "RIFF".
- 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).
- Stringa "WEBP" (nome del container RIFF).
- Stringa "VP8L" (FourCC per dati di immagine con codifica senza perdita di dati).
- Un valore small-endian a 32 bit del numero di byte nella senza perdita di dati.
- 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:
- Immagine ARGB: memorizza i pixel effettivi dell'immagine.
- Immagine a entropia: archivia i metacodici prefisso (vedi "Decodifica dei codici con prefisso meta").
- Immagine predittore: archivia i metadati per la trasformazione del predittore (vedi "Trasformazione dei predittori").
- Immagine con trasformazione del colore: creata da
ColorTransformElement
valori (definita in "Color Transform") per diversi blocchi dell'immagine. - 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:
- Valori letterali codificati per prefisso: ogni canale (verde, rosso, blu e alfa) viene codificata con l'entropia in modo indipendente.
- Riferimento all'indietro LZ77: una sequenza di pixel viene copiata da un altro punto in dell'immagine.
- 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.
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:
- Decodifica e crea i codici dei prefissi.
- Codici prefisso.
- 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 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:
- Se S < 256
- Usa S come componente verde.
- Leggi in rosso dal bitstream utilizzando il codice prefisso 2.
- Leggi in blu il flusso di bit utilizzando il codice prefisso 3.
- Leggi la versione alpha del bitstream utilizzando il codice prefisso 4.
- Se S >= 256 e P < 256 + 24
- Utilizza S-256 come prefisso di lunghezza.
- Leggere bit extra per la lunghezza dallo stream di bit.
- Stabilire la lunghezza del riferimento a ritroso dal codice del prefisso di lunghezza e bit extra letti.
- Leggi il codice del prefisso della distanza dal bitstream utilizzando il codice prefisso 5.
- Leggere bit aggiuntivi per la distanza dal flusso di bit.
- Determinare la distanza D con riferimento a ritroso dal codice prefisso della distanza e i bit extra vengono letti.
- Copia L pixel (in ordine della linea di scansione) dalla sequenza di pixel che inizia nella posizione corrente meno D pixel.
- Se S >= 256 + 24
- Usa S - (256 + 24) come indice nella cache dei colori.
- 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