Spécification pour le flux de bits sans perte WebP

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

Extrait

WebP sans perte est un format d'image permettant la compression sans perte des images ARGB. Le format sans perte stocke et restaure exactement les valeurs des pixels, y compris les valeurs de couleur des pixels entièrement transparents. Un algorithme universel de compression de données séquentielles (LZ77), un codage par préfixe et un cache de couleurs sont utilisés pour compresser les données brutes. Des vitesses de décodage plus rapides que celles du format PNG ont été démontrées, ainsi qu'une compression 25% plus dense que celle obtenue avec le format PNG actuel.

1. Introduction

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

Dans ce document, nous utilisons largement la syntaxe du langage de programmation C pour décrire le flux de bits et supposons l'existence d'une fonction de lecture des bits, ReadBits(n). Les octets sont lus dans l'ordre naturel du flux qui les contient, et les bits de chaque octet sont lus dans l'ordre du bit le moins significatif au bit le plus significatif. Lorsque plusieurs bits sont lus en même temps, l'entier est construit à partir des données d'origine dans l'ordre d'origine. Les bits les plus significatifs de l'entier renvoyé sont également les bits les plus significatifs des données d'origine. Ainsi, l'affirmation

b = ReadBits(2);

est équivalent aux deux affirmations ci-dessous :

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

Nous partons du principe que chaque composant de couleur (alpha, rouge, bleu et vert) est représenté par un octet de 8 bits. Nous définissons le type correspondant comme uint8. Un pixel ARGB entier est représenté par un type appelé uint32, qui est un entier non signé composé de 32 bits. Dans le code montrant le comportement des transformations, ces valeurs sont codifiées dans les bits suivants : alpha dans les bits 31 à 24, rouge dans les bits 23 à 16, vert dans les bits 15 à 8 et bleu dans les bits 7 à 0. Toutefois, les implémentations du format sont libres d'utiliser une autre représentation en interne.

En général, une image WebP sans perte contient des données d'en-tête, des informations de transformation et les données d'image proprement dites. Les en-têtes contiennent la largeur et la hauteur de l'image. Une image WebP sans perte peut subir quatre types de transformations différents avant d'être encodée par entropie. Les informations de transformation du flux de bits contiennent les données requises pour appliquer les transformations inverses respectives.

2 Nomenclature

ARGB

Valeur de pixel composée des valeurs alpha, rouge, verte et bleue.

Image ARVB

Tableau bidimensionnel contenant des pixels ARGB.

cache de couleur

Un petit tableau adressé par hachage pour stocker les couleurs récemment utilisées afin de pouvoir 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 nombre entier (jusqu'à 256 dans WebP sans perte).

transformer la couleur d'une image

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

mappage de distance

Modifie les distances LZ77 pour que les pixels de proximité bidimensionnelle aient les valeurs les plus petites.

image d'entropie

Image de sous-résolution bidimensionnelle indiquant quel codage entropique doit être utilisé dans un carré respectif de l'image, c'est-à-dire que chaque pixel est un code de préfixe méta.

LZ77

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

code de préfixe méta

Petit entier (jusqu'à 16 bits) qui indexe un élément dans la table des préfixes de métadonnées.

image de prédiction

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

code de préfixe

Méthode classique de codage entropique, où un plus petit nombre de bits est utilisé pour les codes plus fréquents.

codage par préfixe

 Méthode d'encodage entropique des grands nombres entiers, qui code quelques bits de l'entier à l'aide d'un code entropique et codifie les bits restants à l'état brut. Cela permet aux descriptions des codes d'entropie de rester relativement petites, même lorsque la plage de symboles est grande.

ordre des lignes de balayage

 Ordre de traitement des pixels (de gauche à droite et de haut en bas), en commençant par le pixel en haut à gauche. Une fois une ligne terminée, passez à la colonne de gauche de la ligne suivante.

3 En-tête RIFF

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

1. Chaîne "RIFF".
2. Valeur little-endian de 32 bits de la longueur du bloc, qui correspond à la taille totale du bloc 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 l'identifiant "RIFF" 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 little-endian de 32 bits indiquant le nombre d'octets dans le flux sans perte.
6. Signature de 1 octet 0x2f.

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 en tant qu'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 de l'image limite la taille maximale d'une image WebP sans perte à 16 384 x 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 de l'image sont définies sur 255, et sur 1 dans le cas contraire.

int alpha_is_used = ReadBits(1);

version_number est un code de 3 bits qui doit être défini sur 0. Toute autre valeur doit être traitée 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 de couleur. Elles peuvent rendre la compression finale plus dense.

Une image peut subir quatre types de transformations. Un bit à 1 indique la présence d'une transformation. Chaque transformation ne peut être utilisée qu'une seule fois. 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édiction) n'ont pas de transformations, 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. De plus, les données de transformation peuvent être décidées en fonction de la minimisation de l'entropie.

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. "Transformer les données" contient 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 de celui dans lequel elles sont lues à partir du flux de bits, c'est-à-dire la dernière en premier.

Nous décrivons ensuite la transformation des données pour différents types.

4.1 Transformation des prédicteurs

La transformation du 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 du prédicteur, la valeur de pixel actuelle est prédite à partir des pixels déjà décodés (dans l'ordre des lignes de balayage) et seule la valeur résiduelle (réelle - prédite) est codée. Le composant vert d'un pixel définit lequel des 14 prédicteurs est utilisé dans un bloc particulier de l'image ARGB. Le mode de prédiction détermine le type de prédiction à utiliser. Nous divisons l'image en carrés, et tous les pixels d'un carré 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 s'agit d'une image de sous-résolution où le composant vert d'un pixel définit lequel des 14 prédicteurs est utilisé pour tous les pixels block_width * block_height d'un bloc particulier de l'image ARGB. Cette image de sous-résolution est encodée à l'aide des mêmes techniques que celles décrites dans le chapitre 5.

Le nombre de colonnes de blocs, transform_width, est utilisé dans l'indexation bidimensionnelle. Pour un pixel (x, y), il est possible de calculer l'adresse du bloc de filtre respectif en procédant comme suit :

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, la valeur du pixel actuel 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 :

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

où TL signifie "en haut à gauche", T signifie "en haut", TR signifie "en haut à droite" et L signifie "à gauche". Au moment de prédire une valeur pour P, tous les pixels O, TL, T, TR et L ont déjà été traités, et le pixel P ainsi que tous les pixels X sont inconnus.

Compte tenu des pixels voisins précédents, les différents modes de prédiction sont définis comme suit.

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

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

Le sélecteur de prédictions 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 ARGB 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);
}

Il existe des règles de traitement spécifiques pour certains pixels de bordure. S'il existe une transformation du prédicteur, quelle que soit la valeur du mode [0..13] pour ces pixels, la valeur prédite pour le pixel en haut à gauche de l'image est 0xff000000, tous les pixels de la ligne supérieure sont des pixels L et tous les pixels de la colonne la plus à gauche sont des pixels T.

Le traitement du pixel TR pour les pixels de la colonne la plus à droite est exceptionnel. Les pixels de la colonne la plus à droite sont prédits à l'aide des modes [0..13], comme les pixels qui ne sont pas sur la bordure. Toutefois, le pixel le plus à gauche de la même ligne que le pixel actuel est utilisé comme pixel TR.

La valeur de pixel finale 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 des couleurs est de décorréler les valeurs R, G et B de chaque pixel. La transformation de couleur conserve la valeur verte (G) telle quelle, transforme la valeur rouge (R) en fonction de la valeur verte, et transforme la valeur bleue (B) en fonction de la valeur verte, puis de la valeur rouge.

Comme pour la transformation du prédicteur, l'image est d'abord divisée en blocs, 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 des couleurs est effectuée en définissant un delta de transformation des couleurs. Le delta de transformation des couleurs dépend de ColorTransformElement, qui est le même pour tous les pixels d'un bloc donné. Le delta est soustrait lors de la transformation des couleurs. La transformation inverse des couleurs consiste 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 un nombre à virgule fixe de 3,5, et d'un canal de couleur RVB signé de 8 bits (c) [-128..127]. Il est défini comme suit :

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

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

La multiplication doit être effectuée avec une précision supérieure (au moins 16 bits). La propriété d'extension du signe de l'opération de décalage n'a pas d'importance ici. Seuls les 8 bits les moins significatifs sont utilisés à partir du résultat. Dans ces bits, le décalage d'extension du signe 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 appliquer la transformation inverse des couleurs et récupérer les valeurs d'origine du rouge et du bleu. Les trois 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;

Le reste des données de transformation des couleurs contient des instances 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, le composant vert 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 inverse des couleurs est appliquée aux valeurs ARVB des pixels. Comme mentionné précédemment, cette transformation de couleur inverse consiste simplement à ajouter des valeurs ColorTransformElement aux canaux rouge et bleu. Les canaux alpha et vert restent inchangés.

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 Transformation "Soustraire le vert"

La transformation "Soustraire le vert" soustrait les valeurs vertes des valeurs rouges et bleues de chaque pixel. Lorsque cette transformation est présente, le décodeur doit ajouter la valeur verte aux valeurs rouge et bleue. Aucune donnée n'est associée à cette 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. Toutefois, comme il n'y a pas de données supplémentaires ici, la transformation de soustraction du vert peut être codée en utilisant moins de bits qu'une transformation de couleur complète.

4.4 Transformation de l'indexation des couleurs

S'il n'y a pas beaucoup de valeurs de pixels uniques, il peut être plus efficace de créer un tableau d'index de couleurs et de remplacer les valeurs de pixels par les index du tableau. La transformation d'indexation des couleurs permet d'y parvenir. (Dans le contexte de WebP sans perte, nous ne parlons pas spécifiquement de transformation de palette, car un concept similaire, mais plus dynamique, existe dans l'encodage WebP sans perte : le cache de couleurs.)

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

Les données de transformation contiennent la taille de la table de couleurs et les entrées de la table de couleurs. Le décodeur lit les données de transformation d'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 à l'aide du format de stockage d'image lui-même. La table de couleurs peut être obtenue en lisant une image, sans l'en-tête RIFF, la taille d'image et les transformations, en supposant une hauteur d'un pixel et une largeur de color_table_size. La table de couleurs est toujours codée par soustraction pour 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 elles-mêmes, ce qui permet de réaliser des économies importantes pour les petites images. Lors du décodage, chaque couleur finale du tableau de couleurs peut être obtenue en ajoutant les valeurs des composants de couleur précédents par chaque composant ARVB séparément et en stockant les 8 bits les moins significatifs du résultat.

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

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

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

Lorsque la table de couleurs est petite (16 couleurs ou moins), plusieurs pixels sont regroupés en un seul. Le regroupement de pixels consiste à regrouper plusieurs pixels (2, 4 ou 8) en un seul, ce qui réduit la largeur de l'image. Le regroupement de pixels permet un codage entropique conjoint plus efficace des pixels voisins et offre certains avantages de codage arithmétique au code entropique, mais il ne peut être utilisé que lorsqu'il y a 16 valeurs uniques ou moins.

color_table_size indique 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 pour valeur 0, 1, 2 ou 3. La valeur 0 indique qu'aucun regroupement de pixels ne doit être effectué 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 que 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 regroupées dans le composant vert comme suit :

• width_bits = 1 : pour chaque valeur x, où x ≡ 0 (mod 2), une valeur verte à x est placée dans les 4 bits de poids faible de la valeur verte à x / 2, et une valeur verte à x+1 est placée dans les 4 bits de poids fort de la valeur verte à x / 2.
• width_bits = 2 : pour chaque valeur x, où x ≡ 0 (mod 4), une valeur verte à x est placée dans les deux bits les moins significatifs de la valeur verte à x / 4, et les valeurs vertes à x+1 à x+3 sont placées dans l'ordre dans les bits les plus significatifs de la valeur verte à x / 4.
• width_bits = 3 : pour chaque valeur x, où x ≡ 0 (mod 8), une valeur verte à x est placée dans le bit le moins significatif de la valeur verte à x / 8, et les valeurs vertes de x+1 à x+7 sont placées dans l'ordre dans les bits les plus significatifs de la valeur verte à x / 8.

Après avoir lu cette transformation, image_width est sous-échantillonné par width_bits. Cela affecte la taille des transformations ultérieures. La nouvelle taille peut être calculée à l'aide de DIV_ROUND_UP, comme défini précédemment.

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

5 Données d'image

Les données d'image sont un tableau de valeurs de pixels dans l'ordre des lignes de balayage.

5.1 Rôles des données d'image

Nous utilisons les données d'image de cinq manières différentes :

1. Image ARGB : stocke les pixels réels de l'image.
2. Image d'entropie : stocke les codes de préfixe méta (voir "Décodage des codes de préfixe méta").
3. Image du prédicteur : stocke les métadonnées de la transformation du prédicteur (voir Transformation du prédicteur).
4. Image de transformation des couleurs : créée par les valeurs ColorTransformElement (définies dans Transformation des couleurs) pour différents blocs de l'image.
5. Image d'indexation des couleurs : tableau de la taille de color_table_size (jusqu'à 256 valeurs ARVB) qui stocke les métadonnées de la transformation d'indexation des couleurs (voir Transformation d'indexation des couleurs).

5.2 Encodage des données d'image

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

L'image est d'abord divisée en un ensemble de blocs de taille fixe (généralement des blocs 16x16). Chacun de ces blocs est modélisé à l'aide de ses propres codes d'entropie. De plus, plusieurs blocs peuvent partager les mêmes codes d'entropie.

Justification : Le stockage d'un code d'entropie entraîne des coûts. Ce coût peut être minimisé si des blocs statistiquement similaires partagent un code d'entropie, ce qui permet de stocker ce code 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 joignant à plusieurs reprises une paire de clusters sélectionnés de manière aléatoire lorsqu'il 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 à code préfixe : chaque canal (vert, rouge, bleu et alpha) est codé par entropie de manière indépendante.
2. Référence arrière LZ77 : une séquence de pixels est copiée depuis un autre emplacement de l'image.
3. Code de cache de couleur : utilisation d'un code de hachage multiplicatif court (index de cache de couleur) d'une couleur récemment vue.

Les sous-sections suivantes décrivent chacune de ces étapes en détail.

5.2.1 Littéraux avec préfixe

Le pixel est stocké sous forme de valeurs préfixées de vert, rouge, bleu et alpha (dans cet ordre). Pour en savoir plus, consultez la section 6.2.3.

5.2.2 Référence arrière LZ77

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

• La longueur indique le nombre de pixels à copier dans l'ordre des lignes de balayage.
• Le code de distance est un nombre indiquant la position d'un pixel déjà vu, à partir duquel les pixels doivent être copiés. Le mappage exact est décrit ci-dessous.

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

Le codage par préfixe LZ77 divise les grandes valeurs entières en deux parties : le code de préfixe et les bits supplémentaires. Le code de 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 le code d'entropie. De plus, les valeurs élevées sont généralement rares. Des bits supplémentaires ne seraient donc utilisés que pour très peu de valeurs dans l'image. Cette approche permet donc d'obtenir une meilleure compression globale.

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

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

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 précédent.

Les codes de distance supérieurs à 120 indiquent la distance en pixels dans l'ordre des lignes de balayage, avec un décalage de 120.

Les codes de distance les plus petits [1..120] sont spéciaux et réservés à un voisinage proche du pixel actuel. Ce voisinage se compose de 120 pixels :

• Pixels situés entre une et sept lignes au-dessus du pixel actuel, et jusqu'à huit colonnes à gauche ou jusqu'à sept colonnes à droite du pixel actuel. [Nombre total de pixels de ce type : 7 * (8 + 1 + 7) = 112].
• Pixels situés sur la même ligne que le pixel actuel et jusqu'à huit colonnes à sa gauche. [8 pixels].

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

(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 (différence de 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 une distance d'ordre de ligne de balayage dist comme suit :

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

où distance_map correspond au mappage indiqué ci-dessus et image_width à 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.

Justification : de cette façon, les couleurs récemment utilisées peuvent parfois être référencées plus efficacement que si elles étaient émises à l'aide des deux autres méthodes (décrites dans les sections 5.2.1 et 5.2.2).

Les codes de cache de couleur sont stockés comme suit. Tout d'abord, il existe une valeur de 1 bit qui indique si le cache de couleurs est utilisé. Si ce bit est défini sur 0, aucun code de cache de couleur n'existe et n'est transmis dans le code de préfixe qui décode les symboles verts et les codes de préfixe de longueur. Toutefois, si ce bit est défini sur 1, la taille du cache de couleurs est lue 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 une couleur ARGB. 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 de résolution des conflits.

Au début du décodage ou de l'encodage d'une image, toutes les entrées de toutes les valeurs du cache de couleurs sont définies sur zéro. Le code du cache de couleurs est converti en cette couleur au moment du décodage. L'état du cache de couleurs est maintenu en insérant chaque pixel, qu'il soit produit par référence arrière ou en tant que littéraux, dans le cache dans l'ordre dans lequel ils apparaissent 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 les longueurs de code de préfixe, et non les codes de préfixe eux-mêmes.

En particulier, le format utilise le codage par préfixe spatialement variable. En d'autres termes, différents blocs de l'image peuvent potentiellement utiliser différents codes d'entropie.

Justification : Différentes zones de l'image peuvent présenter des caractéristiques différentes. Ainsi, leur permettre d'utiliser différents codes d'entropie offre 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 créer les codes de préfixe.
2. Codes de préfixe Meta.
3. Données d'image codées par entropie.

Pour chaque pixel (x, y), il existe un ensemble de cinq codes de préfixe associés. Ces codes sont (dans l'ordre du flux binaire) :

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

À partir de maintenant, nous désignerons cet ensemble sous le nom de groupe de codes de préfixe.

6.2.1 Décodage et création des codes de préfixe

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

Les longueurs de code de préfixe peuvent être codées de deux manières. La méthode utilisée est spécifiée par une valeur de 1 bit.

• Si ce bit est défini sur 1, il s'agit d'un code de longueur de code simple.
• Si ce bit est défini sur 0, il s'agit d'un code de longueur 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 être inefficace, mais elle est autorisée par le format. L'arbre décrit doit être un arbre binaire complet. Un nœud feuille unique est considéré comme un arbre binaire complet et peut être encodé à l'aide du code de longueur simple ou du code de longueur normal. Lorsque vous codez un nœud feuille unique à l'aide du code de longueur normale, toutes les longueurs de code sont nulles, sauf une, et la valeur du nœud feuille unique est marquée avec la longueur 1, même si aucun bit n'est consommé lorsque cet arbre de nœud feuille unique est utilisé.

Code de longueur de code simple

Cette variante est utilisée dans le cas particulier où un ou deux symboles de préfixe seulement se trouvent dans la plage [0..255] avec une longueur de code 1. Toutes les autres longueurs de code de préfixe sont implicitement nulles.

Le premier bit indique le nombre de symboles :

int num_symbols = ReadBits(1) + 1;

Voici les valeurs des symboles.

Ce premier symbole est codé sur 1 ou 8 bits, selon la valeur de is_first_8bits. La plage est [0..1] ou [0..255], respectivement. Le deuxième symbole, s'il est présent, est toujours considéré comme étant dans la plage [0..255] et codé sur 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 inefficaces.

Remarque : Un autre cas particulier se produit lorsque toutes les longueurs de code de préfixe sont nulles (un code de préfixe vide). Par exemple, un code de préfixe pour la distance peut être vide s'il n'y a pas de références antérieures. De même, les codes de préfixe pour les canaux alpha, rouge et bleu peuvent être vides si tous les pixels du même code de préfixe méta sont produits à l'aide du cache de couleurs. Toutefois, ce cas ne nécessite pas de traitement spécial, car les codes de préfixe vides peuvent être codés comme ceux contenant un seul symbole 0.

Code de longueur normale

Les longueurs de code du code de préfixe tiennent dans 8 bits et se lisent 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. Les longueurs de code de niveau inférieur, 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 ReadBits(1) == 0, le nombre maximal de symboles de lecture différents (max_symbol) pour chaque type de symbole (A, R, G, B et distance) est défini sur la taille de son alphabet :

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

Sinon, elle est définie 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 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 jusqu'à 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 valeur non nulle précédente [3..6] fois, c'est-à-dire 3 + ReadBits(2) fois. Si le code 16 est utilisé avant qu'une valeur non nulle ait été émise, la valeur 8 est répétée.
• Le code 17 émet une série de zéros de longueur [3..10], c'est-à-dire 3 + ReadBits(3) fois.
• Le code 18 émet une série de zéros de longueur [11..138], soit 11 + ReadBits(7) fois.

Une fois les longueurs de code lues, un code de préfixe est créé pour chaque type de symbole (A, R, G, B et distance) à l'aide de la taille de l'alphabet correspondant.

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

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 les codes de préfixe à 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 le rôle d'une image ARGB.

Il existe deux possibilités pour les codes de préfixe méta, indiquées par une valeur de 1 bit :

• Si ce bit est défini sur zéro, un seul code de préfixe méta est utilisé partout dans l'image. Aucune autre donnée n'est stockée.
• Si ce bit est défini sur "1", l'image utilise plusieurs codes de préfixe de métadonnées. Ces codes de préfixe méta 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 de métadonnées de 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 les différentes parties de l'image.

Les trois premiers bits contiennent la valeur prefix_bits. Les dimensions de l'image d'entropie 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 défini plus haut.

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

Interprétation des codes de préfixe Meta

Le nombre de groupes de codes de préfixe dans l'image ARGB peut être obtenu en recherchant le plus grand code de préfixe méta dans 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 l'image d'entropie.

Comme chaque groupe de codes de préfixe 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;

Étant donné un pixel (x, y) dans l'image ARGB, nous pouvons obtenir les codes de préfixe correspondants à 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];

où nous avons supposé l'existence d'une structure PrefixCodeGroup, qui représente un ensemble de cinq codes de préfixe. De plus, prefix_code_groups est un tableau de PrefixCodeGroup (de taille 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 "Décodage des données d'image codées par entropie".

6.2.3 Décodage des données d'image codées par entropie

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

Ensuite, lisez le symbole S à partir du flux de bits à l'aide du code de préfixe 1. Notez que S est un entier compris entre 0 et (256 + 24 + color_cache_size- 1).

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

1. Si S < 256
   1. Utilisez S comme composant vert.
   2. Lire le rouge à partir du flux de bits à l'aide du code de préfixe 2.
   3. Lisez le bleu à partir du flux de bits à l'aide du code de préfixe 3.
   4. Lire l'alpha du flux de bits à l'aide du code de préfixe 4.
2. Si S >= 256 et S < 256 + 24
   1. Utilisez S-256 comme code de préfixe de longueur.
   2. Lire les bits supplémentaires pour la longueur à partir du flux de bits.
   3. Déterminez la longueur de la référence arrière L à partir du code de préfixe de longueur et des bits supplémentaires lus.
   4. Lisez le code de préfixe de distance à partir 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éterminez la distance de référence arrière D à partir du code de préfixe de distance et des bits supplémentaires lus.
   7. Copie L pixels (dans l'ordre des lignes de balayage) à partir de la séquence de pixels commençant à la position actuelle moins D pixels.
3. Si S >= 256 + 24
   1. Utilisez S - (256 + 24) comme index dans le cache de couleurs.
   2. Obtenez la couleur ARVB à partir du cache de couleurs à cet index.

7 Structure générale du format

Vous trouverez ci-dessous un aperçu du format en Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Il ne couvre pas tous les détails. La fin de l'image (EOI) est codée de manière implicite dans le nombre de pixels (image_width * image_height).

Notez que *element signifie que element peut être répété zéro ou plusieurs fois. 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