Spécification pour le flux de bits sans perte WebP

Jyrki Alakuijala, docteur en médecine, Google Inc., 09/03/2023

Extrait

WebP est un format d'image conçu pour la compression sans perte des images ARVB. La sans perte stocke et restaure les valeurs de pixels exactement, y compris les des valeurs de couleur pour les pixels entièrement transparents. Un algorithme universel pour les la compression des données (LZ77), le codage de préfixe et un cache de couleurs sont utilisés pour la compression des données groupées. Le décodage est plus rapide que le format PNG. ainsi qu'une compression plus dense de 25% qu'avec une le format PNG d'aujourd'hui.

1 Introduction

Ce document décrit la représentation sous forme de données compressées d'un pipeline sans perte WebP. l'image. Il constitue une référence détaillée pour l'encodeur sans perte WebP et implémentation du décodeur.

Dans ce document, nous utilisons beaucoup la syntaxe du langage de programmation C pour décrire le flux de bits et supposer l'existence d'une fonction pour lire les bits, ReadBits(n) Les octets sont lus dans l'ordre naturel du flux contenant eux, et les bits de chaque octet sont lus en premier dans l’ordre des bits les moins significatifs. Quand ? plusieurs bits sont lus en même temps, l'entier est construit à partir du les données d'origine dans l'ordre d'origine. Les bits les plus significatifs des les nombres entiers sont également les bits les plus significatifs des données d’origine. Ainsi, instruction

b = ReadBits(2);

équivaut aux deux instructions ci-dessous:

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

Nous supposons que chaque composant de couleur, c'est-à-dire alpha, rouge, bleu et vert, est représentées à l'aide d'un octet de 8 bits. Nous définissons le type correspondant comme uint8. A le pixel ARVB entier est représenté par un type appelé uint32, qui est entier composé de 32 bits. Dans le code montrant le comportement transformées, ces valeurs sont codifiées dans les bits suivants: alpha en bits. 31..24, rouge sur les bits 23..16, vert sur les bits 15..8 et bleu sur les bits 7..0. Toutefois, les implémentations du format sont libres d'utiliser une autre représentation en interne.

De manière générale, une image sans perte WebP contient des données d'en-tête, des informations de transformation et des données d'image réelles. Les en-têtes contiennent la largeur et la hauteur de l'image. Un WebP une image sans perte peut passer par quatre types différents de transformation avant d'être à l'entropie. Les informations de transformation du flux de bits contiennent les données nécessaires pour appliquer les transformations inverses respectives.

2 Nomenclature

ARVB

Valeur de pixel composée de valeurs alpha, rouge, vert et bleu.

Image ARVB

Tableau bidimensionnel contenant des pixels ARVB.

cache de couleurs

Petit tableau avec adresse de hachage pour stocker les couleurs récemment utilisées à des fins de les rappeler avec des codes plus courts.

image d'indexation des couleurs

Image unidimensionnelle de couleurs pouvant être indexées à l'aide d'un petit entier (jusqu'à 256 en mode WebP sans perte).

image de transformation des couleurs

Image de sous-résolution bidimensionnelle contenant des données sur les corrélations de composants couleur.

cartographie des distances

Modifie les distances LZ77 afin d'obtenir les valeurs les plus faibles pour les pixels dans la proximité bidimensionnelle.

image d'entropie

Image de sous-résolution bidimensionnelle indiquant quel codage d'entropie doit être utilisé dans un carré respectif de l'image, c'est-à-dire que chaque pixel est une balise Meta indicatif.

LZ77

Algorithme de compression de fenêtres glissantes basé sur un dictionnaire qui émet ou les décrit comme des séquences de symboles passés.

code de préfixe Meta

Petit entier (jusqu'à 16 bits) qui indexe un élément du préfixe Meta .

image du prédicteur

Image de sous-résolution bidimensionnelle indiquant quel prédicteur spatial est utilisée pour un carré particulier de l'image.

code de préfixe

Méthode classique de codage d'entropie impliquant un plus petit nombre de bits pour obtenir des codes plus fréquemment.

codage de préfixe

Moyen d'entropie du code de nombres entiers plus grands, c'est-à-dire de coder quelques bits de l'entier à l'aide d'un code d'entropie et codifie les bits restants bruts. Cela permet les descriptions des codes d'entropie restent relativement petites, même lorsque la gamme de symboles est large.

ordre de la ligne de numérisation

Ordre de traitement des pixels (de gauche à droite et de haut en bas), commençant par à partir du pixel en haut à gauche. Lorsqu'une ligne est remplie, continuez dans la colonne de gauche de la ligne suivante.

En-tête 3 RIFF

Le début de l'en-tête contient le conteneur RIFF. Il s'agit des les 21 octets suivants:

1. Chaîne "RIFF".
2. Valeur small-endian de 32 bits de la longueur des fragments, qui correspond à la taille totale du fragment contrôlé par l'en-tête RIFF. Normalement, cela équivaut à la taille de la charge utile (taille du fichier moins 8 octets: 4 octets pour la valeur et 4 octets pour stocker la valeur elle-même).
3. Chaîne 'WEBP' (nom du conteneur RIFF).
4. Chaîne 'VP8L' (FourCC pour les données d'image encodées sans perte).
5. Valeur 32 bits du nombre d'octets dans la sans perte.
6. Signature 0x2f de 1 octet.

Les 28 premiers bits du flux de bits spécifient la largeur et la hauteur de l'image. La largeur et la hauteur sont décodées sous forme de nombres entiers de 14 bits comme suit:

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

La précision de 14 bits pour la largeur et la hauteur d'image limite la taille maximale d'une Image WebP sans perte jusqu'à 16 384 × 16 384 pixels.

Le bit alpha_is_used n'est qu'une indication et ne devrait pas avoir d'incidence sur le décodage. Il doit être défini sur 0 lorsque toutes les valeurs alpha sont égales à 255 sur l'image, et à 1 dans le cas contraire.

int alpha_is_used = ReadBits(1);

"version_number" est un code 3 bits qui doit être défini sur 0. Toute autre valeur doit doit être traité comme une erreur.

int version_number = ReadBits(3);

4 transformations

Les transformations sont des manipulations réversibles des données d'image qui peuvent réduire l'entropie symbolique restante en modélisant les corrélations spatiales et colorées. Ils peut rendre la compression finale plus dense.

Une image peut passer par quatre types de transformations. 1 bit indique que la présence d'une transformation. Chaque transformation ne peut être utilisée qu'une seule fois. La Les transformations ne sont utilisées que pour l'image ARVB de niveau principal. les images de sous-résolution (image de transformation des couleurs, image d'entropie et image de prédicteur) ne comportent aucune transformation. et pas même le bit 0 indiquant la fin des transformations.

En règle générale, un encodeur utilise ces transformations pour réduire l'entropie de Shannon dans l'image résiduelle. Il est également possible de déterminer les données de transformation en fonction de l'entropie. la minimisation.

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 5).

Si une transformation est présente, les deux bits suivants spécifient le type de transformation. Il existe quatre types de transformations.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

Le type de transformation est suivi des données de transformation. Les données de transformation contiennent les informations requises pour appliquer la transformation inverse et dépend du type de transformation. Les transformations inverses sont appliquées dans l'ordre inverse : elles sont lues à partir du flux de bits, c'est-à-dire le dernier en premier.

Ensuite, nous décrirons les données transformées pour différents types.

4.1 Transformation du prédicteur

La transformation "prédicteur" peut être utilisée pour réduire l'entropie en exploitant le fait que les pixels voisins sont souvent corrélés. Dans la transformation "prédicteur", la valeur actuelle en pixels est prédite à partir des pixels déjà décodés (dans la ligne de recherche commande) et seule la valeur résiduelle (réelle - prédite) est encodée. Le vert composant d'un pixel définit lequel des 14 prédicteurs est utilisé dans un un bloc spécifique de l'image ARVB. Le mode de prédiction détermine le type à utiliser. Nous divisons l'image en carrés et tous les pixels d'une utilisent le même mode de prédiction.

Les trois premiers bits des données de prédiction définissent la largeur et la hauteur du bloc en nombre. de bits.

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

Les données de transformation contiennent le mode de prédiction pour chaque bloc de l'image. Il est une sous-résolution d'image où le composant vert d'un pixel définit lequel de les 14 prédicteurs sont utilisés pour tous les block_width * block_height pixels dans un bloc particulier de l'image ARVB. Cette image de sous-résolution est encodée les mêmes techniques que celles décrites dans le chapitre 5.

Le nombre de colonnes de blocs, transform_width, est utilisé pour les données ou l'indexation. Pour un pixel (x, y), on peut calculer le bloc de filtre correspondant adresse par:

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

Il existe 14 modes de prédiction différents. Dans chaque mode de prédiction, valeur de pixel est prédite à partir d'un ou de plusieurs pixels voisins dont les valeurs sont déjà connues.

Nous avons choisi les pixels voisins (TL, T, TR et L) du pixel actuel (P) comme suit : ce qui suit:

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

TL signifie haut à gauche, T signifie haut, TR signifie haut à droite et L L signifie gauche. À au moment de la prédiction d'une valeur pour P, tous les pixels O, TL, T, TR et L ont déjà traité, et que le pixel P et tous les pixels X sont inconnus.

Étant donné les pixels voisins précédents, les différents modes de prédiction sont défini comme suit.

Mode	Valeur prédite de chaque canal du pixel actuel
0	0xff000000 (représente la couleur noire unie en ARVB)
1	L
2	T
3	TR
4	TL
5	Moyenne2(Moyenne2(L, TR), T)
6	Moyenne2(L, TL)
7	Moyenne2(L, T)
8	Moyenne2(TL, T)
9	Moyenne2(T, TR)
10	Moyenne2(Moyenne2(L, TL), Moyenne2(T, TR))
11	Sélectionner(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

Average2 est défini comme suit pour chaque composant ARVB:

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

Le prédicteur "Sélectionner" est défini comme suit:

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

Les fonctions ClampAddSubtractFull et ClampAddSubtractHalf sont exécutées pour chaque composant ARVB, comme suit:

// 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);
}

Des règles de gestion spéciales s'appliquent à certains pixels de bordure. S'il y a un la transformation du prédicteur, quel que soit le mode [0...13] pour ces pixels, la valeur prédite pour le pixel situé tout en haut à gauche de l'image est 0xff000000, les pixels de la ligne du haut sont des L pixels et tous les pixels de la colonne la plus à gauche sont T-pixel

L'adressage du pixel TR pour les pixels de la colonne la plus à droite est exceptionnelle. Les pixels de la colonne la plus à droite sont prédits à l'aide des modes [0..13], comme si le pixel n'est pas sur la bordure, mais le plus à gauche la même ligne que le pixel actuel est utilisée comme pixel TR.

La valeur finale des pixels est obtenue en ajoutant chaque canal de la valeur prédite à la valeur résiduelle encodée.

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 Transformation des couleurs

L'objectif de la transformation de couleur est de décorréler les valeurs R, V et B de chaque Pixel. La transformation "color" conserve la valeur du vert (G) en l'état, transforme la valeur rouge (R) basée sur la valeur du vert et transforme la valeur bleue (B) en fonction sur la valeur en vert, puis sur la valeur en rouge.

Comme pour la transformation "prédicteur", d'abord l'image est divisée en et le même mode de transformation est utilisé pour tous les pixels d'un bloc. Pour chaque bloc, il existe trois types d'éléments de transformation des couleurs.

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

La transformation de couleur réelle s'effectue en définissant un delta de transformation de couleur. La delta de la transformation des couleurs dépend de ColorTransformElement, qui est identique pour tous les pixels d'un bloc donné. Le delta est soustrait lors de la la transformation des couleurs. La transformation de couleur inverse consiste alors simplement à ajouter ces deltas.

La fonction de transformation des couleurs est définie comme suit:

void ColorTransform(uint8 red, uint8 blue, uint8 green,
                    ColorTransformElement *trans,
                    uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the transform is just subtracting the transform deltas
  tmp_red  -= ColorTransformDelta(trans->green_to_red,  green);
  tmp_blue -= ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue -= ColorTransformDelta(trans->red_to_blue, red);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

ColorTransformDelta est calculé à l'aide d'un entier signé de 8 bits représentant une Nombre à virgule fixe à 3,5 et canal de couleur RVB 8 bits signé (c) [-128..127] et est défini comme suit:

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

Une conversion de la représentation non signée 8 bits (uint8) vers la représentation signée 8 bits un (int8) est requis avant d'appeler ColorTransformDelta(). La valeur signée doit être interprété comme un nombre de complément à deux de 8 bits (c'est-à-dire la plage uint8). [128..255] est mappé à la plage [-128..-1] de sa valeur int8 convertie).

La multiplication doit être effectuée avec une plus grande précision (avec au moins 16 bits la précision). La propriété d'extension de signe de l'opération Shift n'a pas d'importance ici : seuls les 8 bits les plus faibles sont utilisés à partir du résultat, et là, le signe le changement d'extension et le décalage non signé sont cohérents.

Nous décrivons maintenant le contenu des données de transformation des couleurs afin que le décodage puisse s'appliquer la transformation de couleur inverse et de récupérer les valeurs rouge et bleu d'origine. La les 3 premiers bits des données de transformation des couleurs contiennent la largeur et la hauteur du bloc d'image en nombre de bits, tout comme la transformation du prédicteur:

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

La partie restante des données de transformation de couleur contient ColorTransformElement. correspondant à chaque bloc de l'image. Chaque ColorTransformElement 'cte' est traité comme un pixel dans une image de sous-résolution. dont le composant alpha est 255, le composant rouge est cte.red_to_blue, vert le composant est cte.green_to_blue et le composant bleu est cte.green_to_red.

Lors du décodage, les instances ColorTransformElement des blocs sont décodées et la transformation de couleur inverse est appliquée aux valeurs ARVB des pixels. En tant que mentionné précédemment, cette transformation de couleur inverse consiste simplement à ajouter ColorTransformElement aux canaux rouge et bleu. Les couches alpha et verte sont laissés tels quels.

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 Soustraire la transformation verte

La transformation "soustraire le vert" soustrait les valeurs vertes des valeurs rouge et bleue de chaque pixel. Lorsque cette transformation est présente, le décodeur doit ajouter le code vert les valeurs rouge et bleue. Aucune donnée n'est associée à cet élément une transformation. Le décodeur applique la transformation inverse comme suit:

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

Cette transformation est redondante, car elle peut être modélisée à l'aide de la transformation de couleur, mais puisqu'il n'y a pas de données supplémentaires ici, la transformation verte soustrayant peut être codées en utilisant moins de bits qu’une transformation de couleur complète.

4.4 Transformation "Color Indexing"

S'il n'y a pas beaucoup de valeurs de pixels uniques, il peut être plus efficace de créer une color index et remplacer les valeurs en pixels par les index du tableau. La couleur la transformation d'indexation. Dans le contexte d'une technologie WebP sans perte, en particulier, ne l'appelez pas "Palette transform", car une transformation similaire, le concept dynamique existe dans l'encodage sans perte WebP: le cache de couleurs.)

La transformation d'indexation des couleurs vérifie le nombre de valeurs ARVB uniques dans les l'image. Si ce nombre est inférieur à un certain seuil (256), une série de ces valeurs ARVB, qui sont ensuite utilisées pour remplacer les valeurs en pixels par le l'index correspondant: le canal vert des pixels est remplacé par le index, toutes les valeurs alpha sont définies sur 255, et toutes les valeurs rouge et bleue sont définies sur 0.

Les données de transformation contiennent la taille du tableau de couleurs et les entrées de la couleur tableau. Le décodeur lit les données de transformation de l'indexation des couleurs comme suit:

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

La table de couleurs est stockée dans le format de stockage d'image lui-même. Tableau des couleurs peut être obtenue en lisant une image, sans en-tête RIFF, taille d'image et , en supposant que la hauteur est de 1 pixel et que la largeur est de color_table_size. Le tableau de couleurs est toujours codé par soustraction afin de réduire l'entropie de l'image. Les deltas des couleurs de la palette contiennent généralement beaucoup moins d'entropie que les couleurs ce qui permet de réaliser d'importantes économies pour les images de petite taille. En décodage, chaque couleur finale du tableau de couleurs peut être obtenue en ajoutant la les valeurs de chaque composant ARVB séparément et en stockant 8 bits importants du résultat.

La transformation inverse de l'image consiste simplement à remplacer les valeurs en pixels (qui sont des indices du tableau de couleurs) par les valeurs réelles du tableau de couleurs. L'indexation est effectuée en fonction de la composant vert de la couleur ARVB.

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

Si l'indice est supérieur ou égal à color_table_size, la valeur de couleur a rgb doit être défini sur 0x00000000 (noir transparent).

Lorsque le tableau de couleurs est petit (égal ou inférieur à 16 couleurs), plusieurs pixels sont regroupés en un seul pixel. Le regroupement de pixels contient plusieurs (2, 4 ou 8) de pixels en un seul pixel, ce qui réduit respectivement la largeur de l'image. Pixel le regroupement permet un codage de l'entropie de distribution commune plus efficace les pixels voisins et offre des avantages liés au codage arithmétique code d'entropie, mais il ne peut être utilisé que lorsqu'il existe 16 valeurs uniques ou moins.

color_table_size spécifie le nombre de pixels combinés:

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 a une valeur de 0, 1, 2 ou 3. Une valeur de 0 indique l'absence de pixel pour l'image. Une valeur de 1 indique que deux pixels sont combinés, et chaque pixel a une plage de [0...15]. Une valeur de 2 indique que quatre pixels sont combinés, et chaque pixel a une plage de [0 à 3]. Une valeur de 3 indique que huit pixels sont combinés et que chaque pixel a une plage de [0..1], c'est-à-dire une valeur binaire.

Les valeurs sont empaquetées dans le composant vert comme suit:

• width_bits = 1: pour chaque valeur x, où x ≡ 0 (mod 2), un vert la valeur de x est placée dans les 4 bits les moins significatifs du la valeur en vert à x / 2, et une valeur en vert à x + 1 est positionnée dans la Les 4 bits les plus significatifs de la valeur verte au niveau de x / 2.
• width_bits = 2: pour chaque valeur x, où x ≡ 0 (mod 4), un vert la valeur de x est positionnée dans les 2 bits les moins significatifs du la valeur en vert à x / 4 et les valeurs en vert à x + 1 à x + 3 sont positionnées dans l’ordre aux bits les plus significatifs de la valeur verte à x / 4.
• width_bits = 3: pour chaque valeur x, où x ≡ 0 (mod 8), un vert la valeur de x est positionnée dans le bit le moins significatif de la valeur à x / 8 et les valeurs vertes à x + 1 à x + 7 sont positionnées dans l'ordre aux bits les plus significatifs de la valeur verte à x / 8.

Après avoir lu cette transformation, image_width est sous-échantillonné par width_bits. Ce affecte la taille des transformations ultérieures. La nouvelle taille peut être calculée DIV_ROUND_UP, tel que défini précédemment.

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

5. Données d'image

Les données de l'image correspondent à un tableau de valeurs en pixels classées par ligne de recherche.

5.1 Rôles des données d'image

Nous utilisons les données d'image dans cinq rôles différents:

1. Image ARVB: stocke les pixels réels de l'image.
2. Image d'entropie: stocke les codes de préfixe Meta (voir "Decoding of Meta Prefix Codes" (Décodage des codes de préfixe Meta).
3. Image du prédicteur: stocke les métadonnées pour la transformation du prédicteur (voir Transformation du prédicteur).
4. Image de transformation de couleur: créée par ColorTransformElement valeurs (défini dans "Color Transform") pour différents blocs de l'image.
5. Image d'indexation des couleurs: tableau de taille color_table_size (jusqu'à 256 ARVB) valeurs) stockant les métadonnées pour la transformation d'indexation des couleurs (voir "Color Indexing Transform").

5.2 Encodage des données d'images

L'encodage des données d'image est indépendant de leur rôle.

L'image est d'abord divisée en un ensemble de blocs de taille fixe (généralement 16 x 16). blocs). Chacun de ces blocs est modélisé à l'aide de son propre code d'entropie. Par ailleurs, plusieurs blocs peuvent partager les mêmes codes d'entropie.

Logique:Le stockage d'un code d'entropie entraîne des frais. Ce coût peut être réduit si des blocs statistiquement similaires partagent un code d'entropie, ce qui les stocke une seule fois. Par exemple, un encodeur peut trouver des blocs similaires en les regroupant à l'aide de leurs propriétés statistiques ou en associant plusieurs fois les clusters sélectionnés, ce qui réduit la quantité globale de bits nécessaires pour encoder l'image.

Chaque pixel est encodé à l'aide de l'une des trois méthodes possibles:

1. Littéraux codés en préfixe: chaque canal (vert, rouge, bleu et alpha) est de manière indépendante.
2. Référence arrière LZ77: séquence de pixels copiée ailleurs dans l'image.
3. Code de mise en cache des couleurs: en utilisant un code de hachage multiplicatif court de couleur) d'une couleur récemment détectée.

Les sous-sections suivantes décrivent chacun de ces éléments en détail.

5.2.1 Littéraux codés avec un préfixe

Le pixel est stocké sous forme de valeurs codées en préfixe (vert, rouge, bleu et alpha, dans cette commande). Consultez la section 6.2.3 pour en savoir plus plus de détails.

5.2.2 Référence arrière LZ77

Les références arrière sont des tuples de length et distance code:

• La longueur indique le nombre de pixels à copier, dans l'ordre de la ligne de numérisation.
• Le code de distance est un nombre indiquant la position d'un élément précédemment vu pixel, à partir duquel les pixels doivent être copiés. Le mappage exact est décrites ci-dessous.

Les valeurs de longueur et de distance sont stockées à l'aide du codage de préfixe LZ77.

Le codage de préfixe LZ77 divise les grands nombres entiers en deux parties: le préfixe code et les bits supplémentaires. Le code préfixe est stocké à l'aide d'un code d'entropie, tandis que les bits supplémentaires sont stockés tels quels (sans code d'entropie).

Justification: Cette approche réduit l'espace de stockage requis pour l'entropie. du code source. De plus, les valeurs élevées sont généralement rares, donc des bits supplémentaires seraient utilisés pour des peu de valeurs dans l'image. Cette approche améliore donc la compression dans son ensemble.

Le tableau suivant indique les codes de préfixe et les bits supplémentaires utilisés pour stocker différentes plages de valeurs.

Plage de valeurs	Code préfixe	Bits supplémentaires
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

Le pseudo-code permettant d'obtenir une valeur (longueur ou distance) à partir du code préfixe est le suivant : ce qui suit:

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;

Cartographie des distances

Comme indiqué précédemment, un code de distance est un nombre indiquant la position d'un pixel déjà vu, à partir duquel les pixels doivent être copiés. Cette sous-section définit le mappage entre un code de distance et la position d'un Pixel.

Les codes de distance supérieurs à 120 indiquent la distance en pixels dans l'ordre des lignes de recherche. de 120.

Les codes de plus petite distance [1..120] sont spéciaux et sont réservés quartier du pixel actuel. Ce quartier comprend 120 pixels:

• Pixels se trouvant entre une et sept lignes au-dessus du pixel actuel et comportant jusqu'à huit colonnes à gauche ou jusqu'à sept colonnes à droite du pixel actuel. [Total de tels pixels = 7 * (8 + 1 + 7) = 112].
• Pixels sur la même ligne que le pixel actuel et jusqu'à 8 colonnes à gauche du pixel actuel. [8 de tels pixels].

Le mappage entre le code de distance distance_code et le pixel voisin la valeur de décalage (xi, yi) est la suivante:

(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)

Par exemple, le code de distance 1 indique un décalage de (0, 1) pour le pixel voisin, c'est-à-dire le pixel au-dessus du pixel actuel (0 pixel dans la direction X et de 1 pixel dans la direction Y). De même, le code de distance 3 indique le pixel en haut à gauche.

Le décodeur peut convertir un code de distance distance_code en ordre de ligne de recherche. distance dist comme suit:

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

où distance_map est le mappage noté ci-dessus, et image_width est la largeur. de l'image en pixels.

5.2.3 Codage du cache de couleurs

Le cache de couleurs stocke un ensemble de couleurs récemment utilisées dans l'image.

Logique:Ainsi, les couleurs récemment utilisées sont parfois appelées plus efficacement que de les émettre via les deux autres méthodes (décrites dans 5.2.1 et 5.2.2).

Les codes de cache de couleurs sont stockés comme suit. Tout d'abord, il y a une valeur de 1 bit qui indique si le cache de couleurs est utilisé. Si ce bit est 0, aucun code de cache de couleurs et elles ne sont pas transmises dans le code du préfixe qui décode les les symboles et les codes de préfixe de longueur. Cependant, si ce bit est égal à 1, le cache des couleurs est lu ensuite:

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits définit la taille du cache de couleurs (1 << color_cache_code_bits). La plage de valeurs autorisées pour color_cache_code_bits est [1..11]. Les décodeurs conformes doivent indiquer un flux de bits corrompu pour les autres valeurs.

Un cache de couleurs est un tableau de taille color_cache_size. Chaque entrée stocke un ARVB couleur. Les couleurs sont recherchées en les indexant par (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Une seule recherche est effectuée dans un cache de couleurs ; il n'y a pas la résolution des conflits.

Au début du décodage ou de l'encodage d'une image, toutes les entrées les valeurs de cache sont définies sur zéro. Le code de cache de couleurs est converti dans cette couleur à le temps de décodage. L'état du cache de couleurs est maintenu en insérant toutes les le pixel, qu'il soit produit par rétroréférence ou sous forme de littéraux, dans le cache leur ordre d'apparition dans le flux.

6. Code d'entropie

6.1 Présentation

La plupart des données sont codées à l'aide d'un code de préfixe canonique. Par conséquent, les codes sont transmis en envoyant la longueur du code de préfixe, comme par opposition aux codes de préfixe réels.

En particulier, ce format fait appel au codage de préfixe spatialisé des variantes. Dans d'autres différents blocs de l'image peuvent utiliser une entropie différente codes.

Logique: Chaque zone de l'image peut présenter des caractéristiques différentes. Le fait de leur permettre d'utiliser différents codes d'entropie leur offre donc plus de flexibilité et potentiellement une meilleure compression.

6.2 Détails

Les données d'image encodées se composent de plusieurs parties:

1. Décoder et construire les codes de préfixe.
2. Codes de préfixe Meta.
3. Données d'image codées entropie

Pour tout pixel (x, y), il existe un ensemble de cinq codes de préfixe associés au Ces codes sont (par ordre de flux de bits):

• Code préfixe n° 1: utilisé pour le canal vert, la longueur de référence arrière et cache de couleurs.
• Préfixe n° 2, n° 3 et n° 4: utilisé pour les canaux rouge, bleu et alpha. respectivement.
• Code préfixe n° 5: utilisé pour la distance de référence arrière.

Désormais, cet ensemble est appelé groupe de préfixes.

6.2.1 Décodage et construction des codes de préfixe

Cette section explique comment lire les longueurs de code de préfixe à partir du flux de bits.

La longueur du préfixe peut être codée de deux manières. La méthode utilisée est spécifiée par une valeur de 1 bit.

• Si ce bit est égal à 1, il s'agit d'un code simple de longueur de code.
• Si ce bit est égal à 0, il s'agit d'un code de longueur de code normale.

Dans les deux cas, il peut y avoir des longueurs de code inutilisées qui font toujours partie du flux. Cette méthode peut s'avérer inefficace, mais elle est autorisée par le format. L'arborescence décrite doit être une arborescence binaire complète. Un nœud feuille unique est est considérée comme un arbre binaire complet et peut être encodée code de longueur de code ou le code de longueur de code normal. Lors du codage d'une seule feuille à l'aide du code de longueur de code normale, mais une seule longueur de code est égale à zéro. et la valeur d'un nœud feuille unique porte la longueur 1, même si aucune bits sont consommés lors de l'utilisation de cette arborescence à nœud feuille unique.

Code de longueur de code simple

Cette variante est utilisée dans le cas particulier où seuls un ou deux préfixes sont présents La plage [0..255] avec une longueur de code de 1. Toutes les autres longueurs de préfixe sont implicitement zéros.

Le premier bit indique le nombre de symboles:

int num_symbols = ReadBits(1) + 1;

Voici les valeurs de symboles.

Ce premier symbole est codé à l’aide de 1 ou 8 bits, en fonction de la valeur de is_first_8bits La plage est respectivement [0..1] ou [0..255]. Le deuxième s'il est présent, il est toujours considéré comme compris dans la plage [0...255] et codé à l'aide de 8 bits.

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

Les deux symboles doivent être différents. Les symboles en double sont autorisés, mais inefficace.

Remarque:Autre cas particulier, lorsque toutes les longueurs de code de préfixe sont des zéros (une valeur préfixe vide). Par exemple, un préfixe de distance peut être vide si il n'y a pas de références ascendantes. De même, les codes de préfixe des caractères alpha, rouge et le bleu peut être vide si tous les pixels appartenant au même code de préfixe Meta sont générés. à l'aide du cache de couleurs. Ce cas ne nécessite toutefois pas de traitement particulier, les codes de préfixe vides peuvent être codés comme ceux contenant un seul symbole 0.

Code avec longueur de code normale

Les longueurs de code du code préfixe sont de huit bits, et sont lues comme suit. Tout d'abord, num_code_lengths spécifie le nombre de longueurs de code.

int num_code_lengths = 4 + ReadBits(4);

Les longueurs de code sont elles-mêmes encodées à l'aide de codes de préfixe ; code de niveau inférieur les longueurs, code_length_code_lengths, doivent d'abord être lues. Le reste de ces code_length_code_lengths (selon l'ordre dans kCodeLengthCodeOrder) sont des zéros.

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);
}

Ensuite, si la valeur est ReadBits(1) == 0, le nombre maximal de symboles lus différents (max_symbol) pour chaque type de symbole (A, R, G, B et distance) est défini sur taille alphabétique:

• Canal G: 256 + 24 + color_cache_size
• Autres littéraux (A, R et B): 256
• Code de distance: 40

Sinon, il est défini comme suit:

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

Si max_symbol est supérieur à la taille de l'alphabet pour le type de symbole, le Le flux de bits n'est pas valide.

Une table de préfixes est ensuite créée à partir de code_length_code_lengths et utilisée pour lire à max_symbol longueurs de code.

• Le code [0..15] indique les longueurs de code littérales.
  • La valeur 0 signifie qu'aucun symbole n'a été codé.
  • Les valeurs [1..15] indiquent la longueur en bits du code correspondant.
• Le code 16 répète la précédente valeur non nulle [3..6], c'est-à-dire 3 + ReadBits(2) fois. Si le code 16 est utilisé avant une valeur non nulle a été émise, la valeur 8 est répétée.
• Le code 17 émet une série de zéros de longueur [3..10], soit 3 + ReadBits(3) fois.
• Le code 18 émet une série de zéros de longueur [11..138], c'est-à-dire 11 + ReadBits(7) fois.

Une fois les longueurs de code lues, un code de préfixe pour chaque type de symbole (A, R, G, B et distance) est formée en utilisant leurs tailles alphabétiques respectives.

Le code de longueur de code normale doit coder un arbre de décision complet, c'est-à-dire la somme des La valeur 2 ^ (-length) de tous les codes non nuls doit être exactement un. Il existe cependant une exception à cette règle, l'arborescence d'un nœud feuille unique, où le nœud feuille est marquée par la valeur 1 et les autres valeurs sont des zéros.

6.2.2 Décodage des codes de préfixe Meta

Comme indiqué précédemment, le format permet d'utiliser différents codes de préfixe pour différents blocs de l'image. Les codes de préfixe Meta sont des index qui identifient à utiliser dans différentes parties de l'image.

Les codes de préfixe Meta ne peuvent être utilisés que lorsque l'image est utilisée dans la role d'une image ARVB.

Il existe deux possibilités pour les codes de préfixe Meta, indiqués par un préfixe de 1 bit :

• Si ce bit est égal à zéro, il n'y a qu'un seul code de préfixe Meta utilisé partout dans l'image. Plus aucune donnée n'est stockée.
• Si ce bit est égal à un, l'image utilise plusieurs méta-préfixes. Ces méta codes de préfixe sont stockés sous forme d'image d'entropie (décrite ci-dessous).

Les composants rouge et vert d'un pixel définissent un code de préfixe Meta 16 bits utilisé dans un bloc particulier de l'image ARVB.

Image d'entropie

L'image d'entropie définit les codes de préfixe utilisés dans différentes parties du l'image.

Les trois premiers bits contiennent la valeur prefix_bits. Les dimensions de l'entropie image sont dérivées de 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);

où DIV_ROUND_UP est tel que défini précédemment.

Les bits suivants contiennent une image d'entropie de prefix_image_width de largeur et de hauteur prefix_image_height

Interprétation des codes de préfixe Meta

Le nombre de groupes de préfixes de l'image ARVB peut être obtenu en recherchant plus grand code de méta-préfixe de l'image d'entropie:

int num_prefix_groups = max(entropy image) + 1;

où max(entropy image) indique le plus grand code de préfixe stocké dans le image d'entropie.

Comme chaque groupe de préfixes contient cinq codes de préfixe, le nombre total de codes de préfixe est le suivant:

int num_prefix_codes = 5 * num_prefix_groups;

À partir d'un pixel (x, y) de l'image ARVB, nous pouvons obtenir le préfixe correspondant à utiliser comme suit:

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

Ici, nous avons supposé l'existence de la structure PrefixCodeGroup, qui représente un ensemble de cinq codes de préfixe. De plus, prefix_code_groups est un tableau de PrefixCodeGroup (de num_prefix_groups).

Le décodeur utilise ensuite le groupe de codes de préfixe prefix_group pour décoder le pixel (x, y), comme expliqué dans la section "Décoder les images Données.

6.2.3 Décoder des données d'images codées entropie

Pour la position actuelle (x, y) dans l'image, le décodeur identifie d'abord le le groupe de codes préfixe correspondant (comme expliqué dans la dernière section). Étant donné le groupe de codes préfixes, le pixel est lu et décodé comme suit.

Ensuite, lisez le symbole S du flux de bits en utilisant le code de préfixe #1. Notez que S correspond tout entier compris dans la plage 0 à (256 + 24 + color_cache_size- 1)

L'interprétation de S dépend de sa valeur:

1. Si S < 256 <ph type="x-smartling-placeholder">
   </ph>
   1. Utilisez le S comme composant vert.
   2. Lisez le rouge à partir du flux de bits à l'aide du code de préfixe 2.
   3. Lisez le bleu du flux de bits à l'aide du code de préfixe 3.
   4. Lisez la version alpha du flux de bits à l'aide du code de préfixe n° 4.
2. Si S >= 256 & D < 256 + 24 <ph type="x-smartling-placeholder">
   </ph>
   1. Utilisez S-256 comme préfixe de longueur.
   2. Lire les bits supplémentaires pour la longueur du flux de bits.
   3. Déterminez la longueur faisant référence à l'arrière-plan L à partir du préfixe de longueur et du bits supplémentaires lus.
   4. Lisez le code du préfixe de distance du flux de bits à l'aide du code de préfixe #5.
   5. Lire les bits supplémentaires pour la distance à partir du flux de bits.
   6. Déterminer la distance de référence arrière D par rapport au préfixe de distance et les bits supplémentaires sont lus.
   7. Copier les L pixels (dans l'ordre de la ligne de numérisation) à partir de la séquence de pixels qui commence à la position actuelle moins D pixels.
3. Si S >= 256 + 24 <ph type="x-smartling-placeholder">
   </ph>
   1. Utilisez S - (256 + 24) comme index dans le cache de couleurs.
   2. Obtenez la couleur ARVB à partir du cache de couleurs à cet indice.

7 Structure globale du format

Vous trouverez ci-dessous un aperçu du format du formulaire de Backus-Naur augmenté (ABNF, Augmented Backus-Naur Form). RFC 5234 RFC 7405. Il ne couvre pas tous les détails. Fin de l'image (EOI) est seulement implicitement codé dans le nombre de pixels (image_width * image_height).

Notez que *element signifie que element peut être répété zéro fois ou plus. 5element signifie que element est répété exactement cinq fois. %b représente une valeur binaire.

7.1 Structure de 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 Structure des transformations

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 Structure des données d'image

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)

Voici un exemple de séquence possible:

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